# Exploiting Exogenous Structure for Sample-Efficient Reinforcement Learning

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 22 of its 39 references that are in the map.
- First posted on arXiv 22 Sep 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [On Oracle-Efficient PAC RL with Rich Observations](https://mlsanity.com/paper/1803.00606/) (2018)
- [Queueing Network Controls via Deep Reinforcement Learning](https://mlsanity.com/paper/2008.01644/) (2020)
- [Q-learning with Nearest Neighbors](https://mlsanity.com/paper/1802.03900/) (2018)
- [Variance Reduction for Reinforcement Learning in Input-Driven Environments](https://mlsanity.com/paper/1807.02264/) (2018)
- [Sample-Efficient Reinforcement Learning in the Presence of Exogenous Information](https://mlsanity.com/paper/2206.04282/) (2022)
- [Hindsight Learning for MDPs with Exogenous Inputs](https://mlsanity.com/paper/2207.06272/) (2022)
- [Discovering and Removing Exogenous State Variables and Rewards for Reinforcement Learning](https://mlsanity.com/paper/1806.01584/) (2018)
- [Deep reinforcement learning for search, recommendation, and online advertising: a survey](https://mlsanity.com/paper/1812.07127/) (2018)
- [Deep Inventory Management](https://mlsanity.com/paper/2210.03137/) (2022)
- [Learning in structured MDPs with convex cost functions: Improved regret bounds for inventory management](https://mlsanity.com/paper/1905.04337/) (2019)
- [Deep Reinforcement Learning for Inventory Networks: Toward Reliable Policy Optimization](https://mlsanity.com/paper/2306.11246/) (2023)
- [Scalable Deep Reinforcement Learning for Ride-Hailing](https://mlsanity.com/paper/2009.14679/) (2020)
- [Adaptive Discretization in Online Reinforcement Learning](https://mlsanity.com/paper/2110.15843/) (2021)
- [Reinforcement learning for bandwidth estimation and congestion control in real-time communications](https://mlsanity.com/paper/1912.02222/) (2019)

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

- [Minimax PAC Bounds for Learning in Exogenous Contextual MDPs](https://mlsanity.com/paper/2606.25170/) (2026)
- [Is Pure Exploitation Sufficient in Exogenous MDPs with Linear Function Approximation?](https://mlsanity.com/paper/2601.20694/) (2026)
- [Offline-Online Reinforcement Learning for Linear Mixture MDPs](https://mlsanity.com/paper/2604.11994/) (2026)

## Abstract (arXiv)

We study a structured class of Markov Decision Processes, known as Exo-MDPs, in which the state space is partitioned into exogenous and endogenous components. Exogenous states evolve stochastically, independent of the agent's actions, while endogenous states evolve deterministically based on both state components and actions. Exo-MDPs capture many operations research settings, including inventory control, resource management, and ride-sharing. Our first contribution is structural: we establish a representational equivalence between discrete MDPs, Exo-MDPs, and discrete linear mixture MDPs. Our second contribution is statistical. We characterize the minimax regret of learning in Exo-MDPs when the effective dimension r is small relative to the endogenous state and action spaces. When the exogenous states are unobserved, we prove matching upper and lower regret bounds of order Theta(Hr √K) over K episodes of horizon H, where r is the effective dimension of the Exo-MDP. When exogenous states are observed, the minimax regret improves to Theta(H√ r K), revealing a Theta(√r) statistical gap due to observation of the exogenous states. These results show that Exo-MDPs decouple sample complexity from action space and endogenous state space. We validate these insights with experiments on inventory control and resource allocation.