Exploiting Exogenous Structure for Sample-Efficient Reinforcement Learning

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

stat.MLSep 22, 2024

Exploiting Exogenous Structure for Sample-Efficient Reinforcement Learning

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

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

Abstract

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.

Figures & tables

Setting	Algorithm / Result	Section	Regret Bound
Unobserved Exogenous States	Upper bound ( HF-UCRL-VTR + )		$\tilde{O}\!\left(Hr\sqrt{K}\right)$
Unobserved Exogenous States	Lower bound		$\Omega\!\left(Hr\sqrt{K}\right)$
Observed Exogenous States	Upper bound ( Plug-In )		$\tilde{O}\!\left(H\sqrt{rK}\right)$
Observed Exogenous States	Lower bound		$\Omega\!\left(H\sqrt{rK}\right)$
General MDPs (baseline)	Lower bound ( domingues2021episodic )	—	$\Omega\!\left(H\sqrt{\|\mathcal{S}\|\|\mathcal{A}\|K}\right)$

Table 1 : Comparison of regret bounds for Exo-MDPs across the two observability regimes. For both settings, we establish nearly matching upper and lower bounds. Observing the exogenous state improves the optimal regret by a factor of

\tilde{\Theta}(\sqrt{r})

compared to the unobserved setting, quantifying the precise statistical benefit of exogenous observability. As discussed in the introduction, our model focuses on applications where

r\ll\min\{|\mathcal{S}|,|\mathcal{A}|\}

, in which case the minimax lower bound for general discrete MDPs,

\Omega(H\sqrt{|\mathcal{S}||\mathcal{A}|K})

, is substantially larger.

Panel of Figure 1 — Figure 1 : Directed graphical models representing a generic MDP (left), and an Exo-MDP (middle). In a generic MDP, the state space is fully endogenous, the current state $S_{h}$ and action $A_{h}$ impact the next state $S_{h+1}$ and reward $R_{h}$ . In an Exo-MDP, the state is partitioned into endogenous component $S_{h}$ and exogenous component $X_{h}$ . The $X_{h}$ is drawn i.i.d from distribution $\mathbb{P}_{x}$ independent of $(S_{h},A_{h})$ . The known deterministic functions $\mathbf{f}$ , $\mathbf{g}$ are such that $S_{h+1}=\mathbf{f}(S_{h},A_{h},X_{h})$ and $R_{h}=\mathbf{g}(S_{h},A_{h},X_{h})$ . The right panel gives the structural equivalence relations between the class of Exo-MDPs, discrete MDPs and discrete linear mixture MDPs.

Explore similar work

Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs
May 19, 2026Pierre Boudart, Pierre Gaillard, Alessandro RudiMarkov Decision Processes Minimax
SIERRA · INRIA, École Normale Supérieure CNRS, PSL Research University Paris, France · Thoth +3
Minimax PAC Bounds for Learning in Exogenous Contextual MDPs
Jun 23, 2026Corentin Pla, Hugo Richard, Marc Abeille +1Markov Decision Processes Minimax
CREST, ENSAE · Criteo AI Lab · FairPlay Joint Team +1
Auto-exploration for online reinforcement learning
Dec 6, 2025Caleb Ju, Guanghui LanStochastic Exploration Offline Reinforcement Learning

May 19, 2026, cs.AIJ/K move · Enter open · S save

Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs

Pierre Boudart, Pierre Gaillard, Alessandro Rudi

SIERRA · INRIA, École Normale Supérieure CNRS, PSL Research University Paris, France · Thoth+3

Markov Decision Processes Minimax Entropy Regularized Reinforcement Learning Regret

Open paper AskPDF arXiv

We study reinforcement learning for episodic Markov Decision Processes (MDPs) whose transitions are modelled by a multinomial logistic (MNL) model. Existing algorithms for MNL mixture MDPs yield a regret of

\smash{\tilde{O}(dH^2\sqrt{T})}

(Li et al., 2024), where

d

is the feature dimension,

H

the episode length, and

T

the number of episodes. Inspired by the logistic bandit literature (Abeille et al., 2021; Faury et al., 2022; Boudart et al., 2026), we introduce a problem-dependent constant

\barσ\_T \leq 1/2

, measuring the normalised average variance of the optimal downstream value function along the learner's trajectory. We propose an algorithm achieving a regret of

\smash{\tilde{O}(dH^2\barσ\_T\sqrt{T})}

, which recovers the existing bound in the worst case and improves upon it for structured MDPs. For instance, for KL-constrained robust MDPs,

\barσ\_T = O(H^{-1})

, reducing the horizon dependence by a factor

H

. We further establish a matching

\smash{Ω(dH^2\barσ\_T\sqrt{T})}

lower bound, proving minimax optimality (up to logarithmic factors) and fully characterising the regret complexity of MNL mixture MDPs for the first time.

Abstract

Explore similar work

Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs

Minimax PAC Bounds for Learning in Exogenous Contextual MDPs

Auto-exploration for online reinforcement learning