Sample-Efficient Reinforcement Learning in the Presence of Exogenous Information
This addresses the challenge of inefficient learning in real-world RL applications with high-dimensional, noisy data, providing a foundational advance for sample efficiency.
The paper tackles the problem of sample-efficient reinforcement learning in high-dimensional observation spaces with irrelevant exogenous information by introducing the Exogenous Markov Decision Process (ExoMDP) setting. It presents the ExoRL algorithm, which achieves near-optimal policy learning with sample complexity polynomial in the endogenous component size and nearly independent of the exogenous component, offering a doubly-exponential improvement over standard methods.
In real-world reinforcement learning applications the learner's observation space is ubiquitously high-dimensional with both relevant and irrelevant information about the task at hand. Learning from high-dimensional observations has been the subject of extensive investigation in supervised learning and statistics (e.g., via sparsity), but analogous issues in reinforcement learning are not well understood, even in finite state/action (tabular) domains. We introduce a new problem setting for reinforcement learning, the Exogenous Markov Decision Process (ExoMDP), in which the state space admits an (unknown) factorization into a small controllable (or, endogenous) component and a large irrelevant (or, exogenous) component; the exogenous component is independent of the learner's actions, but evolves in an arbitrary, temporally correlated fashion. We provide a new algorithm, ExoRL, which learns a near-optimal policy with sample complexity polynomial in the size of the endogenous component and nearly independent of the size of the exogenous component, thereby offering a doubly-exponential improvement over off-the-shelf algorithms. Our results highlight for the first time that sample-efficient reinforcement learning is possible in the presence of exogenous information, and provide a simple, user-friendly benchmark for investigation going forward.