Corruption-robust exploration in episodic reinforcement learning
This addresses robustness in RL for applications where data may be corrupted, offering the first sublinear regret guarantee for non-i.i.d. transitions in episodic RL, though it is incremental as it builds on existing optimism-based methods.
The paper tackles the problem of episodic reinforcement learning under adversarial corruptions in rewards and transitions, extending beyond stochastic bandits. It introduces a framework combining optimism with action elimination to achieve near-optimal regret without corruptions and graceful degradation with corruption, with results for tabular and linear settings.
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.