  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.
