# Near-optimal Reinforcement Learning in Factored MDPs

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

## Key facts

- Cited by 41 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Mar 2014.

## Built on by (most cited first, 30 of 41)

- [A Survey of Zero-shot Generalisation in Deep Reinforcement Learning](https://mlsanity.com/paper/2111.09794/) (2021)
- [MoCoDA: Model-based Counterfactual Data Augmentation](https://mlsanity.com/paper/2210.11287/) (2022)
- [Leveraging Factored Action Spaces for Efficient Offline Reinforcement Learning in Healthcare](https://mlsanity.com/paper/2305.01738/) (2023)
- [Approximate Thompson Sampling via Epistemic Neural Networks](https://mlsanity.com/paper/2302.09205/) (2023)
- [Factored Adaptation for Non-Stationary Reinforcement Learning](https://mlsanity.com/paper/2203.16582/) (2022)
- [Provably Efficient Algorithms for Multi-Objective Competitive RL](https://mlsanity.com/paper/2102.03192/) (2021)
- [Model-Invariant State Abstractions for Model-Based Reinforcement Learning](https://mlsanity.com/paper/2102.09850/) (2021)
- [The Benefits of Model-Based Generalization in Reinforcement Learning](https://mlsanity.com/paper/2211.02222/) (2022)
- [Continual Learning In Environments With Polynomial Mixing Times](https://mlsanity.com/paper/2112.07066/) (2021)
- [Provably Efficient Causal Model-Based Reinforcement Learning for Systematic Generalization](https://mlsanity.com/paper/2202.06545/) (2022)
- [Entity-based Reinforcement Learning for Autonomous Cyber Defence](https://mlsanity.com/paper/2410.17647/) (2024)
- [Learning Interactive World Model for Object-Centric Reinforcement Learning](https://mlsanity.com/paper/2511.02225/) (2025)
- [Learning in Congestion Games with Bandit Feedback](https://mlsanity.com/paper/2206.01880/) (2022)
- [FactorSim: Generative Simulation via Factorized Representation](https://mlsanity.com/paper/2409.17652/) (2024)
- [Disentangled Unsupervised Skill Discovery for Efficient Hierarchical Reinforcement Learning](https://mlsanity.com/paper/2410.11251/) (2024)
- [Causal Markov Decision Processes: Learning Good Interventions Efficiently](https://mlsanity.com/paper/2102.07663/) (2021)
- [Factored Latent Action World Models](https://mlsanity.com/paper/2602.16229/) (2026)
- [Efficient Planning in Combinatorial Action Spaces with Applications to Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2302.04376/) (2023)
- [Weakly Coupled Deep Q-Networks](https://mlsanity.com/paper/2310.18803/) (2023)
- [Exploiting Causal Graph Priors with Posterior Sampling for Reinforcement Learning](https://mlsanity.com/paper/2310.07518/) (2023)
- [Centrally Coordinated Multi-Agent Reinforcement Learning for Power Grid Topology Control](https://mlsanity.com/paper/2502.08681/) (2025)
- [IL-SOAR : Imitation Learning with Soft Optimistic Actor cRitic](https://mlsanity.com/paper/2502.19859/) (2025)
- [Reinforcement Learning in the Real World: A Survey of Statistical Challenges and Future Directions](https://mlsanity.com/paper/2601.15353/) (2026)
- [Polynomial Time Reinforcement Learning in Factored State MDPs with Linear Value Functions](https://mlsanity.com/paper/2107.05187/) (2021)
- [No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processes](https://mlsanity.com/paper/2510.20725/) (2025)
- [Learning Causal Dynamics Models in Object-Oriented Environments](https://mlsanity.com/paper/2405.12615/) (2024)
- [From Pixels to Factors: Learning Independently Controllable State Variables for Reinforcement Learning](https://mlsanity.com/paper/2510.02484/) (2025)
- [Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approach](https://mlsanity.com/paper/2510.18687/) (2025)
- [Scalable regret for learning to control network-coupled subsystems with unknown dynamics](https://mlsanity.com/paper/2108.07970/) (2021)
- [Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space](https://mlsanity.com/paper/2302.10667/) (2023)

## Abstract (arXiv)

Any reinforcement learning algorithm that applies to all Markov decision processes (MDPs) will suffer Omega(√SAT) regret on some MDP, where T is the elapsed time and S and A are the cardinalities of the state and action spaces. This implies T = Omega(SA) time to guarantee a near-optimal policy. In many settings of practical interest, due to the curse of dimensionality, S and A can be so enormous that this learning time is unacceptable. We establish that, if the system is known to be a factored MDP, it is possible to achieve regret that scales polynomially in the number of parameters encoding the factored MDP, which may be exponentially smaller than S or A. We provide two algorithms that satisfy near-optimal regret bounds in this context: posterior sampling reinforcement learning (PSRL) and an upper confidence bound algorithm (UCRL-Factored).