Improved Corruption Robust Algorithms for Episodic Reinforcement Learning

Abstract

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 \{\sqrt{T},\text{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.

References in corpus (9)

• Online Convex Optimization in Adversarial Markov Decision Processes
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Data Poisoning Attacks on Stochastic Bandits
• Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?
• Stochastic Linear Optimization with Adversarial Corruption
• Corruption-robust exploration in episodic reinforcement learning
• Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap
• Adaptive Reward-Free Exploration

Cited by in corpus (2)

• Corruption-Robust Offline Reinforcement Learning
• Adversarial Parameter Defense by Multi-Step Risk Minimization