mlsanityData to 14 Oct 2026

Near-optimal Reinforcement Learning in Factored MDPs

arXiv 1403.3741 ↗First posted 15 Mar 2014stat.ML cs.LGcited by 41

Not on the map. Why?

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).

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 8; 2022: 5; 2023: 7; 2024: 7; 2025: 8; 2026: 6.

41 papers.

Sort:

By area:

  1. 2021A Survey of Zero-shot Generalisation in Deep Reinforcement Learningcited by 170
  2. 2022MoCoDA: Model-based Counterfactual Data Augmentationcited by 44
  3. 2023Leveraging Factored Action Spaces for Efficient Offline Reinforcement Learning in Healthcarecited by 42
  4. 2023Approximate Thompson Sampling via Epistemic Neural Networkscited by 31
  5. 2022Factored Adaptation for Non-Stationary Reinforcement Learningcited by 30
  6. 2021Provably Efficient Algorithms for Multi-Objective Competitive RLcited by 22
  7. 2021Model-Invariant State Abstractions for Model-Based Reinforcement Learningcited by 18
  8. 2022The Benefits of Model-Based Generalization in Reinforcement Learningcited by 17
  9. 2021Continual Learning In Environments With Polynomial Mixing Timescited by 14
  10. 2022Provably Efficient Causal Model-Based Reinforcement Learning for Systematic Generalizationcited by 12
  11. 2024Entity-based Reinforcement Learning for Autonomous Cyber Defencecited by 11
  12. 2025Learning Interactive World Model for Object-Centric Reinforcement Learningcited by 11
29 more
  1. 2022Learning in Congestion Games with Bandit Feedbackcited by 10
  2. 2024FactorSim: Generative Simulation via Factorized Representationcited by 10
  3. 2024Disentangled Unsupervised Skill Discovery for Efficient Hierarchical Reinforcement Learningcited by 9
  4. 2021Causal Markov Decision Processes: Learning Good Interventions Efficientlycited by 7
  5. 2026Factored Latent Action World Modelscited by 7
  6. 2023Efficient Planning in Combinatorial Action Spaces with Applications to Cooperative Multi-Agent Reinforcement Learningcited by 6
  7. 2023Weakly Coupled Deep Q-Networkscited by 6
  8. 2023Exploiting Causal Graph Priors with Posterior Sampling for Reinforcement Learningcited by 5
  9. 2025Centrally Coordinated Multi-Agent Reinforcement Learning for Power Grid Topology Controlcited by 5
  10. 2025IL-SOAR : Imitation Learning with Soft Optimistic Actor cRiticcited by 5
  11. 2026Reinforcement Learning in the Real World: A Survey of Statistical Challenges and Future Directionscited by 5
  12. 2021Polynomial Time Reinforcement Learning in Factored State MDPs with Linear Value Functionscited by 4
  13. 2025No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processescited by 4
  14. 2024Learning Causal Dynamics Models in Object-Oriented Environmentscited by 3
  15. 2025From Pixels to Factors: Learning Independently Controllable State Variables for Reinforcement Learningcited by 3
  16. 2025Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approachcited by 3
  17. 2021Scalable regret for learning to control network-coupled subsystems with unknown dynamicscited by 2
  18. 2023Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Spacecited by 2
  19. 2024SHIRE: Enhancing Sample Efficiency using Human Intuition in REinforcement Learningcited by 2
  20. 2021Reinforcement Learning for Markovian Bandits: Is Posterior Sampling more Scalable than Optimism?cited by 1
  21. 2024Why Online Reinforcement Learning is Causalcited by 1
  22. 2024Formally Verified Approximate Policy Iterationcited by 1
  23. 2025Model-Based Reinforcement Learning in Discrete-Action Non-Markovian Reward Decision Processescited by 1
  24. 2026SUSD: Structured Unsupervised Skill Discovery through State Factorizationcited by 1
  25. 2023Model-Free Learning and Optimal Policy Design in Multi-Agent MDPs Under Probabilistic Agent Dropoutcited by 0
  26. 2025Multi-agent Markov Entanglementcited by 0
  27. 2026Provably avoiding over-optimization in Direct Preference Optimization without knowing the data distributioncited by 0
  28. 2026Exponential Sample Complexity Separation between Flat and Hierarchical Agentic Theorem Proverscited by 0
  29. 2026Certified Policy Optimisation for Nested Causal Bandits via PAC-Bayes Riskcited by 0