On the Computational Complexity of Stochastic Controller Optimization in POMDPs

By Nikos A. Vlassis, Michael L. Littman, David Barber. 2011

92 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Zhaoran Wang
2. Zhuoran Yang
3. Qi Cai
4. Marek Petrik
5. Ronny Luss
6. Chi Jin
7. Alekh Agarwal
8. Wen Sun

In Computational Theory and Mathematics

1. Qi Cai
2. Zhaoran Wang
3. Zhuoran Yang
4. Marek Petrik
5. Ronny Luss

Citations in the corpus

• Interpretable Policies for Dynamic Product Recommendations (2016, background): “The hardness for stochastic policies follows similarly from [34].”
• Autonomous Agents and Multi-agent Systems Manuscript No. Learning Potential Functions and Their Representations for Multi-task Reinforcement Learning (unknown): “Finding the cross-task policy μ ∗ has been shown to be NP-hard for POMDPs [82].”
• Sample-Efficient Reinforcement Learning for POMDPs with Linear Function Approximations (2022, background): “The decision-making in a POMDP is much more difficult (Vlassis et al., 2012) than that in an MDP.”