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.

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

References in corpus (15)

• Provably Efficient Reinforcement Learning with Linear Function Approximation
• The best of both worlds: stochastic and 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
• 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
• Robust Dynamic Assortment Optimization in the Presence of Outlier Customers
• Corruption-Tolerant Gaussian Process Bandit Optimization

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