Learning in Markov Decision Processes with Exogenous Dynamics

Davide Maran; Davide Salaorni; Marcello Restelli

cs.LGMar 3, 2026

Learning in Markov Decision Processes with Exogenous Dynamics

Authors: Davide Maran, Davide Salaorni, Marcello Restelli

Organizations: Department of DEIB, Politecnico di Milano, Milan, Italy.

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1: Comparative learning curves for the TaxiEnv , averaged over $10$ training seeds with $95\%$ confidence intervals. Figure (a): Model-based algorithms ( ExAVI vs UCBVI ). Figure (b): Model-free algorithms ( ExAQ vs QL ).

Panel of Figure 2 — Figure 2: Comparative learning curves of model-free algorithms for the TradingEnv , averaged over $10$ training seeds with $95\%$ confidence intervals. Figure (a): Performance on a linear x-axis, highlighting asymptotic convergence. Figure (b): The same experiment plotted on a logarithmic x-axis, highlighting the dramatic sample efficiency gap in the early stages of training ( $10^{0}-10^{2}$ episodes).

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 3 — Figure 3: The uncontroallable part of the hard MDP family

Type	Algorithm	Space (Model + Value)	Time (Per Step / Plan)
Model-Based	UCBVI	$\mathcal{O}(HS^{2}A+HSA)$	$\mathcal{O}(S^{2}A)$ (Planning)
Model-Based	ExAVI	$\mathcal{O}(HS^{\bullet 2}+HS^{\diamond 2}A+HSA)$	$\mathcal{O}((S^{\diamond}\!+\!S^{\bullet})SA)$ (Planning)
Model-Free	QL	$\mathcal{O}(HSA)$	$\mathcal{O}(1)$
Model-Free	ExAQ	$\mathcal{O}(HSA+HS^{\diamond 2}A)$	$\mathcal{O}(S^{\diamond}A)$

Appendix

Table 1: Summary table with complexity analysis.

Panel of Figure 4 — Figure 4: Comparative learning curves for the tiny version of ElevatorEnv , averaged over $10$ random seeds. Shaded regions denote $95\%$ confidence intervals. Figure (a) Model-based performance. Figure (b) Model-free performance.

Figure 5: Inventory liquidation profiles for the optimal execution problem. ExAQ (blue) discovers a balanced strategy between the passive TWAP (pink) and the aggressive dumping of PPO / QL .

Table 8

General Settings
	Taxi		Elevator
Parameter	UCBVI	ExAVI	UCBVI	ExAVI
Discount Factor ( $\gamma$ )	$1.0$	$1.0$	$1.0$	$1.0$
Training Seeds	$[1\dots 10]$		$[1\dots 10]$
Optimization
Bonus ( $C$ )	$0.5$	$-$	$0.5$	$-$

Appendix

Table 5: Hyperparameter of model-based methods across TaxiEnv and ElevatorEnv tasks. Shared parameters are aligned, while specific tuning differences are highlighted.

General Settings
	Taxi		Elevator		Trading
Parameter	QL	ExAQ	QL	ExAQ	QL	ExAQ
Discount Factor ( $\gamma$ )	$1.0$	$1.0$	$1.0$	$1.0$	$1.0$	$1.0$
Training Seeds	$[1\dots 10]$		$[1\dots 10]$		$[1\dots 10]$
Execution
Learning Rate ( $\alpha$ )	$0.05$	$0.01$	$0.01$	$0.001$	$1.0$	$0.9$

Appendix

Table 6: Hyperparameter of model-free methods across TaxiEnv , ElevatorEnv , and TradingEnv tasks. Shared parameters are aligned, while specific tuning differences are highlighted.

General Settings
Parameter	Value
Discount Factor ( $\gamma$ )	$0.999$
Number of Parallel Envs	$16$
Training Seeds	$[1\dots 10]$
Optimization
Learning Rate ( $\alpha$ )	$10^{-4}$

Appendix

Table 7: Hyperparameter settings for PPO in the TradingEnv environment.

Markov Decision Processes

Markov decision processes model sequential choices under uncertainty, linking actions, state transitions, and rewards to planning and reinforcement learning.

See all 153 papers

Exploiting Exogenous Structure for Sample-Efficient Reinforcement Learning
Sep 22, 2024Jia Wan, Sean R. Sinclair, Devavrat Shah +1Regret Minimization in RL Markov Decision Processes
Laboratory for Information and Decision Systems, Massachusetts Institute of Technology · Department of Industrial Engineering and Management Sciences, Northwestern University
Minimax PAC Bounds for Learning in Exogenous Contextual MDPs
Jun 23, 2026Corentin Pla, Hugo Richard, Marc Abeille +1Markov Decision Processes Reinforcement Learning
CREST, ENSAE · Criteo AI Lab · FairPlay Joint Team
Joint MDPs and Reinforcement Learning in Coupled-Dynamics Environments
Mar 6, 2026Ege C. Kaya, Mahsa Ghasemi, Abolfazl HashemiSemi-Markov Decision Process Markov Decision Processes
Elmore Family School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN, USA

Sep 22, 2024J/K move · Enter open · S save

Exploiting Exogenous Structure for Sample-Efficient Reinforcement Learning

Jia Wan, Sean R. Sinclair, Devavrat Shah, Martin J. Wainwright

Laboratory for Information and Decision Systems, Massachusetts Institute of Technology · Department of Industrial Engineering and Management Sciences, Northwestern University

Regret Minimization in RL Markov Decision Processes Reinforcement Learning Markov Models Sample-Efficient RL

Open paper AskPDF 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

Θ(Hr \sqrt{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

Θ(H\sqrt{ r K})

, revealing a

Θ(\sqrt{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.

Abstract

Markov Decision Processes

Explore similar work

Exploiting Exogenous Structure for Sample-Efficient Reinforcement Learning

Minimax PAC Bounds for Learning in Exogenous Contextual MDPs

Joint MDPs and Reinforcement Learning in Coupled-Dynamics Environments