On the Computational Complexity of Stochastic Controller Optimization in POMDPs

DOI10.1145/2382559.2382563zbMATH Open1322.68111arXiv1107.3090OpenAlexW2962946825MaRDI QIDQ2947572FDOQ2947572

Authors: Nikos Vlassis, Michael L. Littman, David Barber 

Publication date: 24 September 2015

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Abstract: We show that the problem of finding an optimal stochastic 'blind' controller in a Markov decision process is an NP-hard problem. The corresponding decision problem is NP-hard, in PSPACE, and SQRT-SUM-hard, hence placing it in NP would imply breakthroughs in long-standing open problems in computer science. Our result establishes that the more general problem of stochastic controller optimization in POMDPs is also NP-hard. Nonetheless, we outline a special case that is convex and admits efficient global solutions.

Full work available at URL: https://arxiv.org/abs/1107.3090

Recommendations

• On Near Optimality of the Set of Finite-State Controllers for Average Cost POMDP
• POMDP controllers with optimal budget
• The computational complexity of stochastic optimization
• scientific article; zbMATH DE number 1361472
• scientific article; zbMATH DE number 49106
• scientific article; zbMATH DE number 3845484
• Optimal cost almost-sure reachability in POMDPs
• Partially observable stochastic optimal control
• scientific article; zbMATH DE number 1394785

zbMATH Keywords

computational complexitynonlinear optimizationpartially observable Markov decision processcomputations on polynomialsbilinear programsum-of-square-roots problemstochastic controllerMotzkin-Straus theoremmatrix fractional program

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Markov and semi-Markov decision processes (90C40)

Cited In (13)

• The complexity of reachability in parametric Markov decision processes
• On the Complexity of Reachability in Parametric Markov Decision Processes
• Algebraic optimization of sequential decision problems
• On the \(p\)-reinforcement and the complexity
• Learning optimal admission control in partially observable queueing networks
• Optimizing active surveillance for prostate cancer using partially observable Markov decision processes
• Control Theory Meets POMDPs: A Hybrid Systems Approach
• Complexity of finite-horizon Markov decision process problems
• Optimistic MLE: a generic model-based algorithm for partially observable sequential decision making
• Intractable Problems in Control Theory
• Parameter synthesis in Markov models: a gentle survey
• Counterexample-driven synthesis for probabilistic program sketches
• POMDP controllers with optimal budget

This page was built for publication: On the Computational Complexity of Stochastic Controller Optimization in POMDPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947572)