Nonapproximability Results for Partially Observable Markov Decision Processes

Abstract

We show that for several variations of partially observable Markov decision processes, polynomial-time algorithms for finding control policies are unlikely to or simply don't have guarantees of finding policies within a constant factor or a constant summand of optimal. Here "unlikely" means "unless some complexity classes collapse," where the collapses considered are P=NP, P=PSPACE, or P=EXP. Until or unless these collapses are shown to hold, any control-policy designer must choose between such performance guarantees and efficient computation.

References in corpus (9)

• Decision-Theoretic Planning: Structural Assumptions and Computational Leverage
• On the Complexity of Solving Markov Decision Problems
• Solving POMDPs by Searching in Policy Space
• Learning Finite-State Controllers for Partially Observable Environments
• Policy Iteration for Factored MDPs
• Solving POMDPs by Searching the Space of Finite Policies
• Learning Policies with External Memory
• A Method for Speeding Up Value Iteration in Partially Observable Markov Decision Processes
• My Brain is Full: When More Memory Helps

Cited by in corpus (7)

• DESPOT: Online POMDP Planning with Regularization
• Planning in POMDPs Using Multiplicity Automata
• Optimal Attack and Defense for Reinforcement Learning
• Computational Techniques for Reachability Analysis of Partially Observable Discrete Time Stochastic Hybrid Systems
• Approximate Safety Verification and Control of Partially Observable Stochastic Hybrid Systems
• Optimal Control of Infinite Horizon Partially Observable Decision Processes Modeled As Generators of Probabilistic Regular Languages
• On Avoidance Learning with Partial Observability