The Complexity of Optimal Small Policies

References

• Gill J. Computational complexity of probabilistic Turing machines. SIAM J. Compu. (1977) 6(6):675–695Crossref, Google Scholar
• Ladner R. Polynomial space counting problems. SIAM J. Comput. (1989) 18:1087–1097Crossref, Google Scholar
• Littman M., Goldsmith J., Mundhenk M. The computational complexity of probabilistic planning. J. Artificial Intelligence Res. (1998) 9:1–36Crossref, Google Scholar
• Lovejoy W. A survey of algorithmic methods for partially observed Markov decision processes. Ann. Oper. Res. (1991) 28:47–66Crossref, Google Scholar
• Mundhenk M., Goldsmith J., Allender E. The complexity of the policy existence problem for partially observable finite-horizon Markov decision processes. Proc. 25th Mathematical Foundations of Computer Sciences (1997) (Springer-Verlag)129–138Lecture Notes in Computer Science #1295Crossref, Google Scholar
• Papadimitriou C.Computational Complexity (1994) (Addison-Wesley, Reading, MA) Google Scholar
• Papadimitriou C., Tsitsiklis J. The complexity of Markov decision processes. Math. Oper. Res. (1987) 12(3):441–450Link, Google Scholar
• Puterman M.Markov Decision Processes (1994) (John Wiley & Sons, New York) Crossref, Google Scholar
• Smallwood R., Sondik E. The optimal control of partially observed Markov processes over the finite horizon. Oper. Res. (1973) 21:1071–1088Link, Google Scholar
• Torán J. Complexity classes defined by counting quantifiers. J. ACM (1991) 38(3):753–774Crossref, Google Scholar