Exploiting Exogenous Structure for Sample-Efficient Reinforcement Learning
This work addresses sample complexity challenges in reinforcement learning for applications like inventory control and ride-sharing, though it appears incremental as it builds on existing MDP frameworks.
The paper tackles the problem of sample-efficient reinforcement learning by introducing Exo-MDPs, a structured class of MDPs with exogenous and endogenous states, and proves a regret upper bound of O(H^{3/2}d√K) for unobserved exogenous states, with experiments validating the approach on inventory control.
We study Exo-MDPs, a structured class of Markov Decision Processes (MDPs) where 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 are useful for applications including inventory control, portfolio management, and ride-sharing. Our first result is structural, establishing a representational equivalence between the classes of discrete MDPs, Exo-MDPs, and discrete linear mixture MDPs. Specifically, any discrete MDP can be represented as an Exo-MDP, and the transition and reward dynamics can be written as linear functions of the exogenous state distribution, showing that Exo-MDPs are instances of linear mixture MDPs. For unobserved exogenous states, we prove a regret upper bound of $O(H^{3/2}d\sqrt{K})$ over $K$ trajectories of horizon $H$, with $d$ as the size of the exogenous state space, and establish nearly-matching lower bounds. Our findings demonstrate how Exo-MDPs decouple sample complexity from action and endogenous state sizes, and we validate our theoretical insights with experiments on inventory control.