aiqbench analysis
This research introduces Exo-MDPs to decouple sample complexity from large action spaces by leveraging structural partitions between exogenous and endogenous states. The study provides rigorous minimax regret bounds that demonstrate significant efficiency gains when external state variables are observed, directly advancing the theoretical foundations of sample-efficient reinforcement learning. These findings offer a promising framework for optimizing resource allocation in complex domains like inventory control without requiring exhaustive exploration of high-dimensional action spaces.
Exploiting Exogenous Structure for Sample-Efficient Reinforcement Learning
arXiv:2409.14557v4 Announce Type: replace-cross 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 $\Theta(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 $\Theta(H\sqrt{ r K})$, revealing a $\Theta(\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: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 \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 $\Theta(H\sqrt{ r K})$, revealing a $\Theta(\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.
Machine Learning (stat.ML); Machine Learning (cs.LG); Optimization and Control (math.OC)
arXiv:2409.14557 [stat.ML]
(or arXiv:2409.14557v4 [stat.ML] for this version)
From: Sean R. Sinclair [view email] [v1] Sun, 22 Sep 2024 18:45:38 UTC (117 KB) [v2] Mon, 14 Oct 2024 23:46:09 UTC (152 KB) [v3] Wed, 5 Feb 2025 15:49:21 UTC (768 KB) [v4] Thu, 23 Jul 2026 13:51:31 UTC (251 KB)
Full text under the publisher's open licence · 251 words
Related coverage
Score-Calibrated Flow for Sampling from Unnormalized Densities with Applications to Generative Online Reinforcement Learning
arXiv · Oct 6, 2026
Sample Complexity of Equivariant Reinforcement Learning
arXiv · Sep 30, 2026
Groupoid-Based Internal State Representations for Reinforcement Learning with Local Symmetries
arXiv · Sep 14, 2026
AI and Quantum Computing Briefing
livetradingnews.com · Aug 4, 2026