# Sample-Efficient Reinforcement Learning in the Presence of Exogenous Information

arXiv: https://arxiv.org/abs/2206.04282 · HTML: https://mlsanity.com/paper/2206.04282/

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 39 references that are in the map.
- First posted on arXiv 9 Jun 2022.

## Builds on (most cited first, 25 of 25)

- [Invariant Risk Minimization](https://mlsanity.com/paper/1907.02893/) (2019)
- [Curiosity-driven Exploration by Self-supervised Prediction](https://mlsanity.com/paper/1705.05363/) (2017)
- [Causal inference using invariant prediction: identification and confidence intervals](https://mlsanity.com/paper/1501.01332/) (2015)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Learning Invariant Representations for Reinforcement Learning without Reconstruction](https://mlsanity.com/paper/2006.10742/) (2020)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Learning Not to Learn: Training Deep Neural Networks with Biased Data](https://mlsanity.com/paper/1812.10352/) (2018)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [DeepMDP: Learning Continuous Latent Space Models for Representation Learning](https://mlsanity.com/paper/1906.02736/) (2019)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Provably efficient RL with Rich Observations via Latent State Decoding](https://mlsanity.com/paper/1901.09018/) (2019)
- [What are the Statistical Limits of Offline RL with Linear Function Approximation?](https://mlsanity.com/paper/2010.11895/) (2020)
- [On Calibration and Out-of-domain Generalization](https://mlsanity.com/paper/2102.10395/) (2021)
- [Representation Learning for Online and Offline RL in Low-rank MDPs](https://mlsanity.com/paper/2110.04652/) (2021)
- [Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learning](https://mlsanity.com/paper/1911.05815/) (2019)
- [Adaptive Reward-Free Exploration](https://mlsanity.com/paper/2006.06294/) (2020)
- [Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions](https://mlsanity.com/paper/2010.01374/) (2020)
- [Provable RL with Exogenous Distractors via Multistep Inverse Dynamics](https://mlsanity.com/paper/2110.08847/) (2021)
- [Discovering and Removing Exogenous State Variables and Rewards for Reinforcement Learning](https://mlsanity.com/paper/1806.01584/) (2018)
- [Sparsity in Partially Controllable Linear Systems](https://mlsanity.com/paper/2110.06150/) (2021)
- [Sample Efficient Feature Selection for Factored MDPs](https://mlsanity.com/paper/1703.03454/) (2017)

## Built on by (most cited first, 26 of 26)

- [The Role of Coverage in Online Reinforcement Learning](https://mlsanity.com/paper/2210.04157/) (2022)
- [Guaranteed Discovery of Control-Endogenous Latent States with Multi-Step Inverse Models](https://mlsanity.com/paper/2207.08229/) (2022)
- [Hindsight Learning for MDPs with Exogenous Inputs](https://mlsanity.com/paper/2207.06272/) (2022)
- [Deep Inventory Management](https://mlsanity.com/paper/2210.03137/) (2022)
- [Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL](https://mlsanity.com/paper/2304.05889/) (2023)
- [Learning Latent Dynamic Robust Representations for World Models](https://mlsanity.com/paper/2405.06263/) (2024)
- [RePo: Resilient Model-Based Reinforcement Learning by Regularizing Posterior Predictability](https://mlsanity.com/paper/2309.00082/) (2023)
- [Agent-Controller Representations: Principled Offline RL with Rich Exogenous Information](https://mlsanity.com/paper/2211.00164/) (2022)
- [Representation Learning in Deep RL via Discrete Information Bottleneck](https://mlsanity.com/paper/2212.13835/) (2022)
- [Multistep Inverse Is Not All You Need](https://mlsanity.com/paper/2403.11940/) (2024)
- [When is Agnostic Reinforcement Learning Statistically Tractable?](https://mlsanity.com/paper/2310.06113/) (2023)
- [Malign Overfitting: Interpolation Can Provably Preclude Invariance](https://mlsanity.com/paper/2211.15724/) (2022)
- [Learning an Inventory Control Policy with General Inventory Arrival Dynamics](https://mlsanity.com/paper/2310.17168/) (2023)
- [Reinforcement Learning with Exogenous States and Rewards](https://mlsanity.com/paper/2303.12957/) (2023)
- [Exploiting Exogenous Structure for Sample-Efficient Reinforcement Learning](https://mlsanity.com/paper/2409.14557/) (2024)
- [Learning a Fast Mixing Exogenous Block MDP using a Single Trajectory](https://mlsanity.com/paper/2410.03016/) (2024)
- [Minimal Value-Equivalent Partial Models for Scalable and Robust Planning in Lifelong Reinforcement Learning](https://mlsanity.com/paper/2301.10119/) (2023)
- [Generalizing Multi-Step Inverse Models for Representation Learning to Finite-Memory POMDPs](https://mlsanity.com/paper/2404.14552/) (2024)
- [Guarantees for Nonlinear Representation Learning: Non-identical Covariates, Dependent Data, Fewer Samples](https://mlsanity.com/paper/2410.11227/) (2024)
- [Reinforcement Learning under External Influence: Guarantees, Algorithms, and Sample Complexity](https://mlsanity.com/paper/2305.16056/) (2023)
- [SeMOPO: Learning High-quality Model and Policy from Low-quality Offline Visual Datasets](https://mlsanity.com/paper/2406.09486/) (2024)
- [Learning Fused State Representations for Control from Multi-View Observations](https://mlsanity.com/paper/2502.01316/) (2025)
- [Minimax PAC Bounds for Learning in Exogenous Contextual MDPs](https://mlsanity.com/paper/2606.25170/) (2026)
- [Optimizing Heat Alert Issuance with Reinforcement Learning](https://mlsanity.com/paper/2312.14196/) (2023)
- [Is Pure Exploitation Sufficient in Exogenous MDPs with Linear Function Approximation?](https://mlsanity.com/paper/2601.20694/) (2026)
- [StarWM: Self-Supervised Trained Attention Routing for Robust World Models](https://mlsanity.com/paper/2609.30667/) (2026)

## Abstract (arXiv)

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.