mlsanityData to 7 Oct 2026

On the Complexity of Solving Markov Decision Problems

arXiv 1302.4971 ↗First posted 20 Feb 2013cs.AIcited by 31

Not on the map. Why?

Abstract (arXiv)

Markov decision problems (MDPs) provide the foundations for a number of problems of interest to AI researchers studying automated planning and reinforcement learning. In this paper, we summarize results regarding the complexity of solving MDPs and the running time of MDP solution algorithms. We argue that, although MDPs can be solved efficiently in theory, more study is needed to reveal practical algorithms for solving large problems quickly. To encourage future research, we sketch some alternative methods of analysis that rely on the structure of MDPs.

Key facts. Cited by 31 papers in the map (data through 7 Oct 2026). First posted on arXiv 20 Feb 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2018: 1; 2019: 1; 2020: 1; 2021: 2; 2022: 6; 2023: 6; 2024: 4; 2025: 8; 2026: 2.

31 papers.

Sort:

By area:

  1. 2020Safe Imitation Learning via Fast Bayesian Reward Inference from Preferencescited by 73
  2. 2024An Introduction to Centralized Training for Decentralized Execution in Cooperative Multi-Agent Reinforcement Learningcited by 46
  3. 2019Adversarial Imitation Learning from Incomplete Demonstrationscited by 16
  4. 2022New Challenges in Reinforcement Learning: A Survey of Security and Privacycited by 7
  5. 2023The complexity of non-stationary reinforcement learningcited by 7
  6. 2024Truncated Variance Reduced Value Iterationcited by 6
  7. 2022Planning to the Information Horizon of BAMDPs via Epistemic State Abstractioncited by 4
  8. 2023Planning Multiple Epidemic Interventions with Reinforcement Learningcited by 4
  9. 2025On the Hardness of Reinforcement Learning with Transition Look-Aheadcited by 4
  10. 2018Inverse Reinforcement Learning via Nonparametric Spatio-Temporal Subgoal Modelingcited by 3
  11. 2021Hierarchical Representation Learning for Markov Decision Processescited by 3
  12. 2022Geometric Policy Iteration for Markov Decision Processescited by 3
19 more
  1. 2022Risk-Sensitive Markov Decision Processes with Long-Run CVaR Criterioncited by 3
  2. 2023Intermittently Observable Markov Decision Processescited by 3
  3. 2023CODEX: A Cluster-Based Method for Explainable Reinforcement Learningcited by 3
  4. 2022Doubly-Asynchronous Value Iteration: Making Value Iteration Asynchronous in Actionscited by 2
  5. 2025A View of the Certainty-Equivalence Method for PAC RL as an Application of the Trajectory Tree Methodcited by 2
  6. 2025Howard's Policy Iteration is Subexponential for Deterministic Markov Decision Problems with Rewards of Fixed Bit-size and Arbitrary Discount Factorcited by 2
  7. 2025Survey and Tutorial of Reinforcement Learning Methods in Process Systems Engineeringcited by 2
  8. 2021A space of goals: the cognitive geometry of informationally bounded agentscited by 1
  9. 2023Dual Formulation for Chance Constrained Stochastic Shortest Path with Application to Autonomous Vehicle Behavior Planningcited by 1
  10. 2023Indexability of Finite State Restless Multi-Armed Bandit and Rollout Policycited by 1
  11. 2024Track-MDP: Reinforcement Learning for Target Tracking with Controlled Sensingcited by 1
  12. 2024Integrated Push-and-Pull Update Model for Goal-Oriented Effective Communicationcited by 1
  13. 2025Pull-Based Query Scheduling for Goal-Oriented Semantic Communicationcited by 1
  14. 2022Multi-Agent Chance-Constrained Stochastic Shortest Path with Application to Risk-Aware Intelligent Intersectioncited by 0
  15. 2025Policy Optimization and Multi-agent Reinforcement Learning for Mean-variance Team Stochastic Gamescited by 0
  16. 2025Human-Robot Red Teaming for Safety-Aware Reasoningcited by 0
  17. 2025State-Augmented Graphs for Circular Economy Triagecited by 0
  18. 2026Reinforcement Learning with Pairwise Preferences in Long-Term Decision Problemscited by 0
  19. 2026Near-Optimal Reinforcement Learning with Multi-Step Transition Lookaheadcited by 0