A Model Selection Approach for Corruption Robust Reinforcement Learning

Abstract

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 $\tilde{\mathcal{O}}(\min \{\frac{1}{\Delta },\sqrt{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 $\tilde{\mathcal{O}}(\sqrt{(1+C)T})$, and another computationally inefficient one with $\tilde{\mathcal{O}}(\sqrt{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.

References in corpus (26)

• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Contextual Bandit Algorithms with Supervised Learning Guarantees
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• The best of both worlds: stochastic and adversarial bandits
• Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning
• More Adaptive Algorithms for Adversarial Bandits
• Learning Near Optimal Policies with Low Inherent Bellman Error
• An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits
• Online Convex Optimization in Adversarial Markov Decision Processes
• Model selection for contextual bandits
• Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning
• Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism
• Adapting to Misspecification in Contextual Bandits
• Stochastic Linear Optimization with Adversarial Corruption
• Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs
• Regret Bound Balancing and Elimination for Model Selection in Bandits and RL
• Robust Policy Gradient against Strong Data Corruption
• Regret Balancing for Bandit and RL Model Selection
• Online learning in MDPs with linear function approximation and bandit feedback
• Corruption-Tolerant Gaussian Process Bandit Optimization
• Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously
• Online Learning in Markov Decision Processes with Adversarially Chosen Transition Probability Distributions
• Corruption-Robust Offline Reinforcement Learning