Data to 7 Oct 2026

A Model Selection Approach for Corruption Robust Reinforcement Learning

arXiv 2110.03580 ↗First posted 7 Oct 2021cs.LG stat.MLcited by 45

Not on the map. Why?

Abstract (arXiv)

We develop a model selection approach to tackle reinforcement learning with adversarial corruption in both transition and reward. For finite-horizon tabular MDPs, without prior knowledge on the total amount of corruption, our algorithm achieves a regret bound of widetildeO(minfrac1Delta, √T+C) where T is the number of episodes, C is the total amount of corruption, and Delta is the reward gap between the best and the second-best policy. This is the first worst-case optimal bound achieved without knowledge of C, improving previous results of Lykouris et al. (2021); Chen et al. (2021); Wu et al. (2021). For finite-horizon linear MDPs, we develop a computationally efficient algorithm with a regret bound of widetildeO(√(1+C)T), and another computationally inefficient one with widetildeO(√T+C), improving the result of Lykouris et al. (2021) and answering an open question by Zhang et al. (2021b). Finally, our model selection framework can be easily applied to other settings including linear bandits, linear contextual bandits, and MDPs with general function approximation, leading to several improved or new results.

Key facts. Cited by 45 papers in the map (data through 7 Oct 2026). Builds on 49 of its 70 references that are in the map. First posted on arXiv 7 Oct 2021.

Builds on

49 of 70 references.

References · 49

2017Minimax Regret Bounds for Reinforcement Learningcited by 500
2018Is Q-learning Provably Efficient?cited by 485
2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 123
2018Stochastic bandits robust to adversarial corruptionscited by 118
2018More Adaptive Algorithms for Adversarial Banditscited by 114
2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105

37 more

2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
2016Corralling a Band of Bandit Algorithmscited by 99
2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 91
2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 91
2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
2021Adapting to Misspecification in Contextual Banditscited by 81
2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
2018Efficient Algorithms and Lower Bounds for Robust Linear Regressioncited by 76
2020Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimismcited by 75
2019Corruption-robust exploration in episodic reinforcement learningcited by 72
2020Model Selection in Contextual Stochastic Bandit Problemscited by 71
2020Stochastic Linear Bandits Robust to Adversarial Attackscited by 65
2019Model selection for contextual banditscited by 60
2019Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneouslycited by 53
2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
2021Corruption-Robust Offline Reinforcement Learningcited by 51
2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
2020Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPscited by 49
2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
2016An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial banditscited by 47
2020Regret Bound Balancing and Elimination for Model Selection in Bandits and RLcited by 45
2017An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Banditscited by 43
2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
2020Corruption-Tolerant Gaussian Process Bandit Optimizationcited by 34
2021Robust Policy Gradient against Strong Data Corruptioncited by 30
2020Online learning in MDPs with linear function approximation and bandit feedbackcited by 29
2020Stochastic Shortest Path with Adversarially Changing Costscited by 28
2021Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Casecited by 28
2020Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contaminationcited by 26
2019Stochastic Linear Optimization with Adversarial Corruptioncited by 23
2020Corralling Stochastic Bandit Algorithmscited by 23
2020Regret Balancing for Bandit and RL Model Selectioncited by 20
2021Improved Corruption Robust Algorithms for Episodic Reinforcement Learningcited by 20
2013Online Learning in Markov Decision Processes with Adversarially Chosen Transition Probability Distributionscited by 18
2020Reinforcement Learning with Feedback Graphscited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 10; 2023: 13; 2024: 11; 2025: 5; 2026: 5.

45 papers.

Sort:

By area:

2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 30
2023A Blackbox Approach to Best of Both Worlds in Bandits and Beyondcited by 29
2023Towards Robust Offline Reinforcement Learning under Diverse Data Corruptioncited by 24
2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 24
2022Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Banditscited by 22
2024Corruption Robust Offline Reinforcement Learning with Human Feedbackcited by 20
2022Reward Poisoning Attacks on Offline Multi-Agent Reinforcement Learningcited by 19
2022Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithmscited by 19
2023Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Banditscited by 18

33 more

2022When is Realizability Sufficient for Off-Policy Reinforcement Learning?cited by 17
2025RobustVLA: Robustness-Aware Reinforcement Post-Training for Vision-Language-Action Modelscited by 16
2023Robust Lipschitz Bandits to Adversarial Corruptionscited by 15
2021Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDPcited by 14
2024Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruptioncited by 12
2022A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Banditscited by 11
2022Best of Both Worlds Model Selectioncited by 11
2023Data-Driven Online Model Selection With Regret Guaranteescited by 11
2023Tracking Most Significant Shifts in Nonparametric Contextual Banditscited by 10
2023Best-of-Both-Worlds Algorithms for Linear Contextual Banditscited by 10
2023Efficient Adversarial Attacks on Online Multi-agent Reinforcement Learningcited by 9
2024Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedbackcited by 9
2023On the Model-Misspecification in Reinforcement Learningcited by 7
2022Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environmentscited by 6
2024Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecificationcited by 6
2024Learning Constrained Markov Decision Processes With Non-stationary Rewards and Constraintscited by 5
2025ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learningcited by 5
2023Robust Causal Bandits for Linear Modelscited by 4
2024MetaCURL: Non-stationary Concave Utility Reinforcement Learningcited by 4
2024Strategic Linear Contextual Banditscited by 4
2023Does Sparsity Help in Learning Misspecified Linear Bandits?cited by 3
2024Achieving Constant Regret in Linear Markov Decision Processescited by 3
2024Improved Bound for Robust Causal Bandits with Linear Modelscited by 2
2024Robust Thompson Sampling Algorithms Against Reward Poisoning Attackscited by 2
2023Policy Resilience to Environment Poisoning Attacks on Reinforcement Learningcited by 1
2025Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Ratescited by 1
2026A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptionscited by 1
2025Robust In-Context Reinforcement Learning Under Reward Poisoning Attackscited by 0
2025Online Learning to Rank under Corruption: A Robust Cascading Bandits Approachcited by 0
2026Truly Adapting to Adversarial Constraints in Constrained MABscited by 0
2026Mixing Makes Markovian Contexts Cheap for Linear Banditscited by 0
2026Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivitycited by 0
2026Robust Risk-Sensitive Reinforcement Learning from Corrupted Human Feedbackcited by 0