Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL

Xiaoyu Chen, Jiachen Hu, Lihong Li, Liwei Wang

Abstract

Reinforcement learning (RL) in episodic, factored Markov decision processes (FMDPs) offers a path toward solving high-dimensional problems that are otherwise intractable. This paper introduces FMDP-BF, an algorithm designed to leverage the structural properties of FMDPs. By utilizing a novel variance decomposition theorem, FMDP-BF achieves a regret bound that is exponentially smaller than optimal algorithms designed for non-factored MDPs. Furthermore, the algorithm improves upon the best previous results for FMDPs by a factor of $\sqrt{H|\mathcal{S}_i|}$, where $H$ is the planning horizon and $|\mathcal{S}_i|$ is the cardinality of the factored state subspace. The authors also establish a lower bound for FMDPs, demonstrating the near-optimality of their approach. Finally, the paper presents the first sample-efficient algorithm for RL with knapsack constraints (RLwK) by formulating it as an FMDP.

Introduction

Standard "tabular" reinforcement learning often falls victim to the curse of dimensionality. In these settings, the number of samples required to learn an optimal policy grows linearly with the size of the state and action spaces. For complex environments where the state is defined by numerous variables, the state space becomes astronomically large, making exhaustive exploration impossible.

However, many real-world environments possess an underlying structure where transitions and rewards are governed by local interactions. This structure is captured by Factored Markov Decision Processes (FMDPs). In an FMDP, the state is represented as a vector of factors, and each factor's transition depends only on a small subset of other factors (its "parents"). By exploiting this factorization, agents can learn about the environment much more efficiently than by treating the state as a single, monolithic entity.

The FMDP-BF Algorithm

The researchers propose FMDP-BF (Factored MDP with Bernstein-type bonuses and Filtering), which operates on the principle of "Optimism in the Face of Uncertainty." The algorithm's efficiency stems from two primary technical innovations:

1. Refined Variance Decomposition

The mathematical core of the paper is a new Bellman-type equation for the variance of factored transitions (Theorem 1). In previous FMDP research, error bounds tended to compound linearly as independent probabilities were multiplied. The authors' refined variance decomposition allows the algorithm to use Bernstein-type confidence bonuses. Unlike standard Hoeffding bonuses, Bernstein bonuses account for the actual variance of transitions, leading to significantly tighter confidence intervals and more efficient exploration.

2. Optimistic and Pessimistic Estimation

FMDP-BF maintains both an upper bound (optimistic) and a lower bound (pessimistic) on the value of each state. This dual-estimation approach, inspired by state-of-the-art algorithms like EULER, allows the agent to filter out sub-optimal actions more effectively, focusing its exploration on the most promising regions of the factored state space.

Theoretical Contributions and Results

Breaking the $\sqrt{n}$ Barrier

A major contribution of this work is the improvement of the regret bound over the previous benchmark set by Osband & Van Roy (2014). FMDP-BF improves the bound by a factor of $\sqrt{nH|S_i|}$. This means that as the number of factors ($n$) or the planning horizon ($H$) increases, FMDP-BF becomes increasingly more efficient compared to prior methods.

Near-Optimality

The authors provide a lower bound (Theorem 3) for FMDPs, which indicates that their algorithm is near-optimal with respect to the total number of timesteps $T$, the horizon $H$, and the cardinality of the factored state-action subspaces. Specifically, for symmetric settings, the regret bound is $O(\sqrt{nHJT})$, which closely matches the lower bound $\Omega(\sqrt{HJT})$ except for a factor of $\sqrt{n}$ and logarithmic terms.

Application: RL with Knapsack Constraints (RLwK)

The paper demonstrates the practical utility of FMDP theory by applying it to RL with Knapsack constraints. In RLwK, an agent must maximize rewards while ensuring that several different resources (e.g., fuel, time, or budget) do not exceed a strict limit within a single episode.

By treating the "remaining budget" of each resource as a factor in the state space, the authors show that RLwK can be modeled as an FMDP. FMDP-BF provides the first sample-efficient algorithm for this problem class that respects hard constraints (ensuring the budget is never exceeded in any episode) rather than just "soft" constraints (satisfying the budget on average).

Limitations and Future Directions

While FMDP-BF represents a significant theoretical leap, several challenges remain:

  • The $\sqrt{n}$ Gap: A small gap remains between the upper and lower regret bounds. Closing this gap is a primary objective for future theoretical work.
  • Computational Complexity: Although the algorithm is sample-efficient (requiring few trials), solving the internal planning problem for multiple hard constraints is NP-hard. This suggests that while the agent learns quickly from experience, it may require significant computation time to determine its next action.
  • Continuous Costs: The current RLwK formulation assumes costs are discrete. Extending these results to continuous cost distributions while maintaining the efficiency of the value function estimation is a promising area for future research.

Conclusion

By introducing FMDP-BF and a refined variance decomposition for factored transitions, this research provides a more efficient framework for RL in structured environments. The results not only tighten the theoretical bounds for FMDPs but also unlock new possibilities for solving complex, constrained reinforcement learning problems that were previously considered intractable.

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 factored of $\sqrt{H|\mathcal{S}_i|}$, where $|\mathcal{S}_i|$ is the cardinality of the factored state subspace and $H$ is the planning horizon. 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