On the Complexity of Solving Markov Decision Problems

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.

Appears in Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence (UAI1995)

Cited by in corpus (42)

• Decision-Theoretic Planning: Structural Assumptions and Computational Leverage
• Stochastic Constraint Programming
• Near Optimal Behavior via Approximate State Abstraction
• Reinforcement Learning: A Survey
• Nonapproximability Results for Partially Observable Markov Decision Processes
• Decision-Theoretic Bidding Based on Learned Density Models in Simultaneous, Interacting Auctions
• PageRank Optimization by Edge Selection
• Resource Allocation Among Agents with MDP-Induced Preferences
• Safe Imitation Learning via Fast Bayesian Reward Inference from Preferences
• Dispatching Fire Trucks under Stochastic Driving Times
• Plan Development using Local Probabilistic Models
• Minimum Cost Flows, MDPs, and ${\ell }_1$-Regression in Nearly Linear Time for Dense Instances
• The Efficiency of Human Cognition Reflects Planned Information Processing
• Inverse Reinforcement Learning via Nonparametric Spatio-Temporal Subgoal Modeling
• Joint Status Sampling and Updating for Minimizing Age of Information in the Internet of Things
• Finding Options that Minimize Planning Time
• On the Semantics of Purpose Requirements in Privacy Policies
• Real-Time Remote Estimation with Hybrid ARQ in Wireless Networked Control
• Optimal Dynamic Multicast Scheduling for Cache-Enabled Content-Centric Wireless Networks
• Hindsight is Only 50/50: Unsuitability of MDP based Approximate POMDP Solvers for Multi-resolution Information Gathering
• Cooperative Solutions to Exploration Tasks Under Speed and Budget Constraints
• Robust Policy Optimization with Baseline Guarantees
• Decision Making under Uncertainty: A Quasimetric Approach
• Proactive Caching for Energy-Efficiency in Wireless Networks: A Markov Decision Process Approach
• Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes
• Non-myopic learning in repeated stochastic games
• On Polynomial Sized MDP Succinct Policies
• Optimal Downlink-Uplink Scheduling of Wireless Networked Control for Industrial IoT
• Faster Algorithms for Quantitative Analysis of Markov Chains and Markov Decision Processes with Small Treewidth
• Optimal by Design: Model-Driven Synthesis of Adaptation Strategies for Autonomous Systems
• Optimal Threshold Policies for Robust Data Center Control
• Modular self-organization
• Age of Changed Information: Content-Aware Status Updating in the Internet of Things
• Learning Efficient Representations for Reinforcement Learning
• Success Probability of Exploration: a Concrete Analysis of Learning Efficiency
• Multi-Access Communications with Energy Harvesting: A Multi-Armed Bandit Model and the Optimality of the Myopic Policy
• The Value Iteration Algorithm is Not Strongly Polynomial for Discounted Dynamic Programming
• MDPs with Unawareness
• An Analysis of Primal-Dual Algorithms for Discounted Markov Decision Processes
• An approach to predictively securing critical cloud infrastructures through probabilistic modeling
• Risk-Sensitive Markov Decision Processes with Combined Metrics of Mean and Variance
• Biological Blueprints for Next Generation AI Systems