Corruption-robust exploration in episodic reinforcement learning

Abstract

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.

arXiv commentAccepted in Mathematics of Operations Research. Preliminary version was accepted for presentation at COLT'21

References in corpus (19)

• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning
• The best of both worlds: stochastic and adversarial bandits
• Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning
• More Adaptive Algorithms for Adversarial Bandits
• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits
• Online Convex Optimization in Adversarial Markov Decision Processes
• Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound
• Learning Adversarial MDPs with Bandit Feedback and Unknown Transition
• Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation
• Stochastic Linear Optimization with Adversarial Corruption
• Worst-Case Regret Bounds for Exploration via Randomized Value Functions
• Online learning in MDPs with linear function approximation and bandit feedback
• A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spaces
• Corruption-Tolerant Gaussian Process Bandit Optimization
• Robust Dynamic Assortment Optimization in the Presence of Outlier Customers

Cited by in corpus (4)

• Defense Against Reward Poisoning Attacks in Reinforcement Learning
• Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously
• Improved Corruption Robust Algorithms for Episodic Reinforcement Learning
• Provably More Efficient Q-Learning in the One-Sided-Feedback/Full-Feedback Settings