# On the Complexity of Solving Markov Decision Problems

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

## Key facts

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

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

- [Safe Imitation Learning via Fast Bayesian Reward Inference from Preferences](https://mlsanity.com/paper/2002.09089/) (2020)
- [An Introduction to Centralized Training for Decentralized Execution in Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2409.03052/) (2024)
- [Adversarial Imitation Learning from Incomplete Demonstrations](https://mlsanity.com/paper/1905.12310/) (2019)
- [Truncated Variance Reduced Value Iteration](https://mlsanity.com/paper/2405.12952/) (2024)
- [New Challenges in Reinforcement Learning: A Survey of Security and Privacy](https://mlsanity.com/paper/2301.00188/) (2022)
- [The complexity of non-stationary reinforcement learning](https://mlsanity.com/paper/2307.06877/) (2023)
- [Planning Multiple Epidemic Interventions with Reinforcement Learning](https://mlsanity.com/paper/2301.12802/) (2023)
- [Risk-Sensitive Markov Decision Processes with Long-Run CVaR Criterion](https://mlsanity.com/paper/2210.08740/) (2022)
- [Planning to the Information Horizon of BAMDPs via Epistemic State Abstraction](https://mlsanity.com/paper/2210.16872/) (2022)
- [On the Hardness of Reinforcement Learning with Transition Look-Ahead](https://mlsanity.com/paper/2510.19372/) (2025)
- [Inverse Reinforcement Learning via Nonparametric Spatio-Temporal Subgoal Modeling](https://mlsanity.com/paper/1803.00444/) (2018)
- [Hierarchical Representation Learning for Markov Decision Processes](https://mlsanity.com/paper/2106.01655/) (2021)
- [Geometric Policy Iteration for Markov Decision Processes](https://mlsanity.com/paper/2206.05809/) (2022)
- [Intermittently Observable Markov Decision Processes](https://mlsanity.com/paper/2302.11761/) (2023)
- [CODEX: A Cluster-Based Method for Explainable Reinforcement Learning](https://mlsanity.com/paper/2312.04216/) (2023)
- [Doubly-Asynchronous Value Iteration: Making Value Iteration Asynchronous in Actions](https://mlsanity.com/paper/2207.01613/) (2022)
- [A View of the Certainty-Equivalence Method for PAC RL as an Application of the Trajectory Tree Method](https://mlsanity.com/paper/2501.02652/) (2025)
- [Howard's Policy Iteration is Subexponential for Deterministic Markov Decision Problems with Rewards of Fixed Bit-size and Arbitrary Discount Factor](https://mlsanity.com/paper/2505.00795/) (2025)
- [Survey and Tutorial of Reinforcement Learning Methods in Process Systems Engineering](https://mlsanity.com/paper/2510.24272/) (2025)
- [A space of goals: the cognitive geometry of informationally bounded agents](https://mlsanity.com/paper/2111.03699/) (2021)
- [Multi-Agent Chance-Constrained Stochastic Shortest Path with Application to Risk-Aware Intelligent Intersection](https://mlsanity.com/paper/2210.01766/) (2022)
- [Dual Formulation for Chance Constrained Stochastic Shortest Path with Application to Autonomous Vehicle Behavior Planning](https://mlsanity.com/paper/2302.13115/) (2023)
- [Indexability of Finite State Restless Multi-Armed Bandit and Rollout Policy](https://mlsanity.com/paper/2305.00410/) (2023)
- [Track-MDP: Reinforcement Learning for Target Tracking with Controlled Sensing](https://mlsanity.com/paper/2407.13995/) (2024)
- [Integrated Push-and-Pull Update Model for Goal-Oriented Effective Communication](https://mlsanity.com/paper/2407.14092/) (2024)
- [Pull-Based Query Scheduling for Goal-Oriented Semantic Communication](https://mlsanity.com/paper/2503.06725/) (2025)
- [Policy Optimization and Multi-agent Reinforcement Learning for Mean-variance Team Stochastic Games](https://mlsanity.com/paper/2503.22779/) (2025)
- [Human-Robot Red Teaming for Safety-Aware Reasoning](https://mlsanity.com/paper/2508.01129/) (2025)
- [State-Augmented Graphs for Circular Economy Triage](https://mlsanity.com/paper/2512.15824/) (2025)
- [Reinforcement Learning with Pairwise Preferences in Long-Term Decision Problems](https://mlsanity.com/paper/2606.00367/) (2026)

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