mlsanityData to 14 Oct 2026

Corruption-robust exploration in episodic reinforcement learning

arXiv 1911.08689 ↗First posted 20 Nov 2019cs.LG cs.AI cs.DScited by 72

Not on the map. Why?

Abstract (arXiv)

We initiate the study of multi-stage episodic reinforcement learning under adversarial corruptions in both the rewards and the transition probabilities of the underlying system extending recent results for the special case of stochastic bandits. We provide a framework which modifies the aggressive exploration enjoyed by existing reinforcement learning approaches based on "optimism in the face of uncertainty", by complementing them with principles from "action elimination". Importantly, our framework circumvents the major challenges posed by naively applying action elimination in the RL setting, as formalized by a lower bound we demonstrate. Our framework yields efficient algorithms which (a) attain near-optimal regret in the absence of corruptions and (b) adapt to unknown levels corruption, enjoying regret guarantees which degrade gracefully in the total corruption encountered. To showcase the generality of our approach, we derive results for both tabular settings (where states and actions are finite) as well as linear-function-approximation settings (where the dynamics and rewards admit a linear underlying representation). Notably, our work provides the first sublinear regret guarantee which accommodates any deviation from purely i.i.d. transitions in the bandit-feedback model for episodic reinforcement learning.

Key facts. Cited by 72 papers in the map (data through 14 Oct 2026). First posted on arXiv 20 Nov 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 20; 2022: 16; 2023: 15; 2024: 7; 2025: 9; 2026: 5.

72 papers.

Sort:

By area:

  1. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 164
  2. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 129
  3. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  4. 2021Corruption-Robust Offline Reinforcement Learningcited by 51
  5. 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
  6. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 49
  7. 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
  8. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  9. 2023Improved Sample Complexity Bounds for Distributionally Robust Reinforcement Learningcited by 44
  10. 2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
  11. 2022Provable Benefits of Representational Transfer in Reinforcement Learningcited by 38
  12. 2021Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learningcited by 34
38 more
  1. 2021Robust Policy Gradient against Strong Data Corruptioncited by 30
  2. 2022Learning in Stackelberg Games with Non-myopic Agentscited by 29
  3. 2022Performative Reinforcement Learningcited by 27
  4. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 26
  5. 2023Towards Robust Offline Reinforcement Learning under Diverse Data Corruptioncited by 24
  6. 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
  7. 2021Defense Against Reward Poisoning Attacks in Reinforcement Learningcited by 21
  8. 2021On Optimal Robustness to Adversarial Corruption in Online Decision Problemscited by 21
  9. 2021Improved Corruption Robust Algorithms for Episodic Reinforcement Learningcited by 20
  10. 2022Reward Poisoning Attacks on Offline Multi-Agent Reinforcement Learningcited by 20
  11. 2024Corruption Robust Offline Reinforcement Learning with Human Feedbackcited by 20
  12. 2022Online Policy Optimization for Robust MDPcited by 19
  13. 2022Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithmscited by 19
  14. 2023Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal Armscited by 18
  15. 2025RobustVLA: Robustness-Aware Reinforcement Post-Training for Vision-Language-Action Modelscited by 18
  16. 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 17
  17. 2023Offline Primal-Dual Reinforcement Learning for Linear MDPscited by 17
  18. 2023Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Boundscited by 14
  19. 2023Implicit Poisoning Attacks in Two-Agent Reinforcement Learning: Adversarial Policies for Training-Time Attackscited by 14
  20. 2021Can Q-Learning be Improved with Advice?cited by 13
  21. 2022Byzantine-Robust Online and Offline Distributed Reinforcement Learningcited by 13
  22. 2023No-Regret Online Reinforcement Learning with Adversarial Losses and Transitionscited by 13
  23. 2022Admissible Policy Teaching through Reward Designcited by 12
  24. 2022Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddingscited by 12
  25. 2022A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Banditscited by 11
  26. 2021Gap-Dependent Unsupervised Exploration for Reinforcement Learningcited by 10
  27. 2023Tracking Most Significant Shifts in Nonparametric Contextual Banditscited by 10
  28. 2023Efficient Adversarial Attacks on Online Multi-agent Reinforcement Learningcited by 10
  29. 2022Efficient Reward Poisoning Attacks on Online Deep Reinforcement Learningcited by 9
  30. 2022Beyond IID: data-driven decision-making in heterogeneous environmentscited by 9
  31. 2024Uncertainty-based Offline Variational Bayesian Reinforcement Learning for Robustness under Diverse Data Corruptionscited by 8
  32. 2023Robust Offline Reinforcement learning with Heavy-Tailed Rewardscited by 7
  33. 2021Improved Algorithms for Misspecified Linear Markov Decision Processescited by 6
  34. 2022Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environmentscited by 6
  35. 2025Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximationcited by 6
  36. 2025ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learningcited by 6
  37. 2024Sample Complexity Characterization for Linear Contextual MDPscited by 5
  38. 2021Multiplicative Reweighting for Robust Neural Network Optimizationcited by 4

50 most cited of 72 All 72 (JSON)