Exploiting Exogenous Structure for Sample-Efficient Reinforcement Learning
Not on the map. Why?
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.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 22 of its 39 references that are in the map. First posted on arXiv 22 Sep 2024.
Builds on
22 of 39 references.
References · 22
- 2022Training language models to follow instructions with human feedbackcited by 15,712
- 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
- 2018Is Q-learning Provably Efficient?cited by 485
- 2019Introduction to Multi-Armed Banditscited by 475
- 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
- 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
- 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
- 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
- 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
- 2020Queueing Network Controls via Deep Reinforcement Learningcited by 40
- 2018Q-learning with Nearest Neighborscited by 37
- 2018Variance Reduction for Reinforcement Learning in Input-Driven Environmentscited by 30
10 more
- 2022Sample-Efficient Reinforcement Learning in the Presence of Exogenous Informationcited by 26
- 2022Hindsight Learning for MDPs with Exogenous Inputscited by 25
- 2018Discovering and Removing Exogenous State Variables and Rewards for Reinforcement Learningcited by 24
- 2018Deep reinforcement learning for search, recommendation, and online advertising: a surveycited by 23
- 2019Learning in structured MDPs with convex cost functions: Improved regret bounds for inventory managementcited by 22
- 2022Deep Inventory Managementcited by 22
- 2020Scalable Deep Reinforcement Learning for Ride-Hailingcited by 12
- 2021Adaptive Discretization in Online Reinforcement Learningcited by 12
- 2023Deep Reinforcement Learning for Inventory Networks: Toward Reliable Policy Optimizationcited by 11
- 2019Reinforcement learning for bandwidth estimation and congestion control in real-time communicationscited by 6
Built on by
Citing papers per year: 2026: 2.
2 papers.