Learning in Markov Decision Processes with Exogenous Dynamics
This work addresses the problem of efficient reinforcement learning for systems with exogenous dynamics, which is significant for applications where the agent's actions only partially influence the system's behavior.
This work tackles the problem of learning in Markov Decision Processes with exogenous dynamics, achieving significantly improved learning guarantees with regret bounds dependent only on the size of the exogenous state space. The approach demonstrates substantial gains in sample efficiency, with empirical validation showing improved performance across various environments.
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.