On the Computational Complexity of Stochastic Controller Optimization in POMDPs

DOI10.1145/2382559.2382563MaRDI QIDQ2947572zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

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
• Intractable Problems in Control Theory
• Optimistic MLE: a generic model-based algorithm for partially observable sequential decision making
• 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)