mlsanityData to 7 Oct 2026

Improved Corruption Robust Algorithms for Episodic Reinforcement Learning

arXiv 2102.06875 ↗First posted 13 Feb 2021cs.LG cs.AIcited by 20

Not on the map. Why?

Abstract (arXiv)

We study episodic reinforcement learning under unknown adversarial corruptions in both the rewards and the transition probabilities of the underlying system. We propose new algorithms which, compared to the existing results in (Lykouris et al., 2020), achieve strictly better regret bounds in terms of total corruptions for the tabular setting. To be specific, firstly, our regret bounds depend on more precise numerical values of total rewards corruptions and transition corruptions, instead of only on the total number of corrupted episodes. Secondly, our regret bounds are the first of their kind in the reinforcement learning setting to have the number of corruptions show up additively with respect to min√T, PolicyGapComplexity rather than multiplicatively. Our results follow from a general algorithmic framework that combines corruption-robust policy elimination meta-algorithms, and plug-in reward-free exploration sub-algorithms. Replacing the meta-algorithm or sub-algorithm may extend the framework to address other corrupted settings with potentially more structure.

Key facts. Cited by 20 papers in the map (data through 7 Oct 2026). Builds on 21 of its 26 references that are in the map. First posted on arXiv 13 Feb 2021.

Builds on

21 of 26 references.

References · 21

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  4. 2018Stochastic bandits robust to adversarial corruptionscited by 118
  5. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
  6. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  7. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  8. 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 91
  9. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
  10. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  11. 2020Adaptive Reward-Free Explorationcited by 77
  12. 2019Corruption-robust exploration in episodic reinforcement learningcited by 72
9 more
  1. 2020Stochastic Linear Bandits Robust to Adversarial Attackscited by 65
  2. 2019Data Poisoning Attacks on Stochastic Banditscited by 52
  3. 2020Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPscited by 49
  4. 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
  5. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 48
  6. 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
  7. 2018Exploration in Structured Reinforcement Learningcited by 34
  8. 2020Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?cited by 34
  9. 2019Stochastic Linear Optimization with Adversarial Corruptioncited by 23

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 5; 2023: 4; 2024: 2; 2025: 2; 2026: 1.

20 papers.

Sort:

By area:

  1. 2021Corruption-Robust Offline Reinforcement Learningcited by 51
  2. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  3. 2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
  4. 2022Understanding the Limits of Poisoning Attacks in Episodic Reinforcement Learningcited by 21
  5. 2021On Optimal Robustness to Adversarial Corruption in Online Decision Problemscited by 20
  6. 2024Corruption Robust Offline Reinforcement Learning with Human Feedbackcited by 20
  7. 2022Online Policy Optimization for Robust MDPcited by 19
  8. 2022Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithmscited by 19
  9. 2022Efficient Reward Poisoning Attacks on Online Deep Reinforcement Learningcited by 9
  10. 2023Efficient Adversarial Attacks on Online Multi-agent Reinforcement Learningcited by 9
  11. 2024MetaCURL: Non-stationary Concave Utility Reinforcement Learningcited by 4
  12. 2021Corruption Robust Active Learningcited by 3
8 more
  1. 2021Adversarial Parameter Defense by Multi-Step Risk Minimizationcited by 2
  2. 2023Policy Resilience to Environment Poisoning Attacks on Reinforcement Learningcited by 1
  3. 2023Corruption-Robust Lipschitz Contextual Searchcited by 1
  4. 2023Optimal Cost Constrained Adversarial Attacks For Multiple Agent Systemscited by 1
  5. 2025Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Ratescited by 1
  6. 2022User-Oriented Robust Reinforcement Learningcited by 0
  7. 2025Robust In-Context Reinforcement Learning Under Reward Poisoning Attackscited by 0
  8. 2026Truly Adapting to Adversarial Constraints in Constrained MABscited by 0