# Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL

arXiv: https://arxiv.org/abs/2008.13319 · HTML: https://mlsanity.com/paper/2008.13319/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Aug 2020.

## Built on by (most cited first, 16 of 16)

- [Provably Efficient Algorithms for Multi-Objective Competitive RL](https://mlsanity.com/paper/2102.03192/) (2021)
- [Knapsack RL: Unlocking Exploration of LLMs via Optimizing Budget Allocation](https://mlsanity.com/paper/2509.25849/) (2025)
- [Representation Learning for General-sum Low-rank Markov Games](https://mlsanity.com/paper/2210.16976/) (2022)
- [Learning in Congestion Games with Bandit Feedback](https://mlsanity.com/paper/2206.01880/) (2022)
- [A Reduction-Based Framework for Conservative Bandits and Reinforcement Learning](https://mlsanity.com/paper/2106.11692/) (2021)
- [Efficient Planning in Combinatorial Action Spaces with Applications to Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2302.04376/) (2023)
- [Anytime-Constrained Reinforcement Learning](https://mlsanity.com/paper/2311.05511/) (2023)
- [Overcoming the Curse of Dimensionality in Reinforcement Learning Through Approximate Factorization](https://mlsanity.com/paper/2411.07591/) (2024)
- [Exploiting Causal Graph Priors with Posterior Sampling for Reinforcement Learning](https://mlsanity.com/paper/2310.07518/) (2023)
- [Learning in Factored Domains with Information-Constrained Visual Representations](https://mlsanity.com/paper/2303.17508/) (2023)
- [Scalable regret for learning to control network-coupled subsystems with unknown dynamics](https://mlsanity.com/paper/2108.07970/) (2021)
- [SHIRE: Enhancing Sample Efficiency using Human Intuition in REinforcement Learning](https://mlsanity.com/paper/2409.09990/) (2024)
- [D3HRL: A Distributed Hierarchical Reinforcement Learning Approach Based on Causal Discovery and Spurious Correlation Detection](https://mlsanity.com/paper/2505.01979/) (2025)
- [Learning Pareto-Optimal Rewards from Noisy Preferences: A Framework for Multi-Objective Inverse Reinforcement Learning](https://mlsanity.com/paper/2505.11864/) (2025)
- [Exponential Sample Complexity Separation between Flat and Hierarchical Agentic Theorem Provers](https://mlsanity.com/paper/2602.10512/) (2026)
- [Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation](https://mlsanity.com/paper/2609.39093/) (2026)

## Abstract (arXiv)

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~citeposband2014near by a factored of √H|Si|, where |Si| 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.