Search papers, labs, and topics across Lattice.
The paper investigates Markov Decision Processes (MDPs) with exogenous state components, where a subset of state variables evolve independently of the agent's actions. By exploiting this structure, the authors derive improved regret bounds for reinforcement learning, demonstrating that the regret scales primarily with the size of the exogenous state space. They also prove a matching lower bound, confirming the information-theoretic optimality of this dependence, and empirically validate the approach.
Forget the curse of dimensionality: if your MDP has exogenous dynamics, you can achieve significantly better learning guarantees by exploiting the structure.
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.
