Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL

Xiaoyu Chen, Jiachen Hu, Lihong Li, Liwei Wang

Introduction

In standard Reinforcement Learning (RL), the difficulty of learning increases dramatically with the number of states and actions. Consider a robotic system with 10 joints, where each joint has 10 possible positions; the total state space is $10^{10}$. This exponential explosion—often termed the "curse of dimensionality"—renders traditional tabular RL algorithms computationally and statistically intractable.

However, many real-world systems exhibit a factored structure. In a factored system, the global state can be broken down into smaller components that evolve somewhat independently. For instance, in a manufacturing plant, the status of a specific machine might only depend on its immediate neighbors rather than the entire factory floor. This paper introduces FMDP-BF (Factored MDP with Bernstein-type confidence bounds and Filtering), a novel RL algorithm that exploits this independence to achieve near-optimal regret bounds. Furthermore, the authors demonstrate how this framework can efficiently solve complex "knapsack" constraints in RL.

The Challenge: Loose Bounds and Hard Constraints

While previous research has attempted to exploit factored structures in Markov Decision Processes (FMDPs), existing algorithms often yielded "loose" performance guarantees. Their theoretical regret bounds did not fully match the mathematical limits of what should be possible.

Additionally, the paper tackles Constrained RL, specifically Reinforcement Learning with Knapsack constraints (RLwK). In this setting, an agent operates under a hard budget (such as battery life, computing power, or financial cost) that must not be exceeded within a single episode. Combining hard constraints with massive state spaces is notoriously difficult.

Methodology: The FMDP-BF Algorithm

To overcome these challenges, the authors propose FMDP-BF, an algorithm built on the principle of "Optimism in the Face of Uncertainty" (OFU). The methodology relies on three key technical innovations:

  1. Refined Variance Decomposition: The authors introduce a new theorem for decomposing the variance of transitions in factored systems. Instead of treating the transition of an entire high-dimensional state as a single monolithic step, they break it down into the sum of variances of individual factors.
  2. Bernstein-Type Confidence Bonuses: Early RL algorithms typically rely on Hoeffding bounds, which are mathematically simpler but less precise. FMDP-BF utilizes Bernstein bounds, which incorporate the empirical variance of rewards and transitions. This allows the algorithm to create much tighter optimism bonuses, reducing unnecessary exploration.
  3. State Augmentation for Constraints: To solve RLwK, the authors augment the state space with the "remaining budget." Ordinarily, this would cause the state space to explode in size. However, they demonstrate that this augmented system naturally forms a Factored MDP, allowing FMDP-BF to solve it efficiently without falling victim to the curse of dimensionality.

Key Theoretical Results

As a theoretical machine learning paper, the evaluation relies on rigorous mathematical proofs rather than empirical datasets. The authors demonstrate several major breakthroughs:

  • Exponential Efficiency: Compared to non-factored algorithms, FMDP-BF's regret is exponentially smaller. Its performance depends on the size of the individual subspaces ($|\mathcal{S}_i|$) rather than the massive total state space ($|\mathcal{S}|$).
  • Near-Optimal Regret: The regret of FMDP-BF is proven to be near-optimal with respect to the total time $T$, the planning horizon $H$, and the size of the factored subspaces. Specifically, it improves upon the best previous work (Osband & Van Roy, 2014) by a factor of $\sqrt{nH|\mathcal{S}_i|}$, where $n$ is the number of factors.
  • First Sample-Efficient Algorithm for RLwK: By bridging FMDPs and constrained RL, the paper provides the first sample-efficient algorithm for RL with knapsack constraints, proving a regret bound that matches the lower bounds for standard tabular MDPs.

Limitations and Future Directions

While FMDP-BF represents a significant theoretical leap, the authors note several limitations and avenues for future research:

  • Computational Complexity: The algorithm is statistically efficient (requiring relatively few samples to learn), but it remains computationally expensive. Solving the knapsack component is NP-hard, meaning the runtime grows exponentially with the number of constraints.
  • The $\sqrt{n}$ Gap: There remains a small mathematical gap—roughly a factor of $\sqrt{n}$—between the algorithm's proven upper bound and the theoretical lower bound. Closing this gap is an open challenge for future theorists.
  • Continuous Budgets: The current approach to knapsack constraints assumes discrete costs and budgets. Extending this framework to handle continuous variables without sacrificing efficiency is a promising direction for future work.

Summary updated

Abstract

Reinforcement learning (RL) in episodic, factored Markov decision processes (FMDPs) is studied. We propose an algorithm called FMDP-BF, which leverages the factorization structure of FMDP. The regret of FMDP-BF is shown to be exponentially smaller than that of optimal algorithms designed for non-factored MDPs, and improves on the best previous result for FMDPs~\citep{osband2014near} by a factor of $\sqrt{nH|\mathcal{S}_i|}$, where $|\mathcal{S}_i|$ is the cardinality of the factored state subspace, $H$ is the planning horizon and $n$ is the number of factored transition. To show the optimality of our bounds, we also provide a lower bound for FMDP, which indicates that our algorithm is near-optimal w.r.t. timestep $T$, horizon $H$ and factored state-action subspace cardinality. Finally, as an application, we study a new formulation of constrained RL, known as RL with knapsack constraints (RLwK), and provides the first sample-efficient algorithm based on FMDP-BF.
BibTeX
@inproceedings{chen2021efficient,
  author = {Xiaoyu Chen and Jiachen Hu and Lihong Li and Liwei Wang},
  title = {{Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=xdghL1dyFr},
}
Figure