# Learning in Markov Decision Processes with Exogenous Dynamics

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

## Key facts

- Cited by 2 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 10 of its 24 references that are in the map.
- First posted on arXiv 3 Mar 2026.

## 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, 10 of 10)

- [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)
- [Challenges of Real-World Reinforcement Learning](https://mlsanity.com/paper/1904.12901/) (2019)
- [Recent Advances in Reinforcement Learning in Finance](https://mlsanity.com/paper/2112.04553/) (2021)
- [Risk-Averse Trust Region Optimization for Reward-Volatility Reduction](https://mlsanity.com/paper/1912.03193/) (2019)
- [Settling the Sample Complexity of Online Reinforcement Learning](https://mlsanity.com/paper/2307.13586/) (2023)
- [Double Deep Q-Learning for Optimal Execution](https://mlsanity.com/paper/1812.06600/) (2018)
- [Reinforcement Learning with Exogenous States and Rewards](https://mlsanity.com/paper/2303.12957/) (2023)
- [Gym4ReaL: A Suite for Benchmarking Real-World Reinforcement Learning](https://mlsanity.com/paper/2507.00257/) (2025)
- [A Refined Analysis of UCBVI](https://mlsanity.com/paper/2502.17370/) (2025)

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

- [Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead](https://mlsanity.com/paper/2609.11807/) (2026)
- [Robust and Learned Online Matching in Growing Trees](https://mlsanity.com/paper/2609.40077/) (2026)

## Abstract (arXiv)

Reinforcement learning algorithms are typically designed for generic Markov Decision Processes (MDPs), where any state-action pair can lead to an arbitrary transition distribution. In many practical systems, however, only a subset of the state variables is directly influenced by the agent's actions, while the remaining components evolve according to exogenous dynamics and account for most of the stochasticity. In this work, we study a structured class of MDPs characterized by exogenous state components whose transitions are independent of the agent's actions. We show that exploiting this structure yields significantly improved learning guarantees, with only the size of the exogenous state space appearing in the leading terms of the regret bounds. We further establish a matching lower bound, showing that this dependence is information-theoretically optimal. Finally, we empirically validate our approach across classical toy settings and real-world-inspired environments, demonstrating substantial gains in sample efficiency compared to standard reinforcement learning methods.