Name
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1145/2382559.2382563 | ACM Transactions on Computation Theory (TOCT) |
Keywords | DocType | Volume |
markov decision process,special case,general problem,long-standing open problem,optimal stochastic blind controller,computational complexity,corresponding decision problem,efficient global solution,computer science,np-hard problem,stochastic controller optimization,decision problem,artificial intelligent,partially observable markov decision process,polynomial time,nonlinear optimization,np hard problem | Journal | 4 |
Issue | ISSN | Citations |
4 | 1942-3454 | 10 |
PageRank | References | Authors |
0.55 | 18 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nikos A. Vlassis | 1 | 2050 | 158.24 |
| Michael L. Littman | 2 | 9798 | 961.84 |
| David Barber | 3 | 404 | 45.57 |