On the Complexity of Solving Markov Decision Problems

2013/02/20 by Michael L. Littman, Littman, Michael L., Thomas Dean +3 · 13 citations
Computer Science · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Formal Methods in Verification #Reinforcement Learning in Robotics #Robotic Path Planning Algorithms

paper · pdf · doi:10.48550/arxiv.1302.4971

openalex publication_date 2013/02/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• Approximating probabilistic inference in Bayesian belief networks is NP-hard
• Learning to act using real-time dynamic programming

Cited by

• State-Augmented Graphs for Circular Economy Triage
• Survey and Tutorial of Reinforcement Learning Methods in Process Systems Engineering
• On the Hardness of Reinforcement Learning with Transition Look-Ahead
• Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes
• An Approach for Service Function Chain Routing and Virtual Function Network Instance Migration in Network Function Virtualization Architectures
• Reusing Samples in Variance Reduction
• The Efficiency of Human Cognition Reflects Planned Information Processing
• Human-Robot Red Teaming for Safety-Aware Reasoning
• Robust Policy Optimization with Baseline Guarantees
• Optimal by Design: Model-Driven Synthesis of Adaptation Strategies for Autonomous Systems
• The Value Iteration Algorithm is Not Strongly Polynomial for Discounted Dynamic Programming
• Plan Development using Local Probabilistic Models
• Optimal Threshold Policies for Robust Data Center Control
• Modular self-organization
• MDPs with Unawareness
• Age of Changed Information: Content-Aware Status Updating in the Internet of Things

Related

• The Complexity of Markov Decision Processes
• Large Markov Decision Processes and Combinatorial Optimization
• A Unifying Framework for Reinforcement Learning and Planning
• Near-Optimal Learning and Planning in Separated Latent MDPs
• Speeding Up Planning in Markov Decision Processes via Automatically Constructed Abstractions