@inproceedings{4bce86216908424bb4a220f1a53d0710,
title = "The complexity of policy evaluation for finite-horizon partially-observable markov decision processes",
abstract = "A partially-observable Markov decision process (POMDP) is a generalization of a Markov decision process that allows for incomplete information regarding the state of the system. We consider several flavors of finite-horizon POMDPs. Our results concern the complexity of the policy evaluation and policy existence problems, which are characterized in terms of completeness for complexity classes. We prove a new upper bound for the policy evaluation problem for POMDPs, showing it is complete for Probabilistic Logspace. From this, we prove policy existence problems for several variants of unobservable, succinctly represented MDPs to be complete for NPPP , a class for which not many natural problems are known to be complete.",
author = "Martin Mundhenk and Judy Goldsmith and Eric Allender",
year = "1997",
doi = "10.1007/bfb0029956",
language = "English (US)",
isbn = "3540634371",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "129--138",
editor = "Igor Privara and Peter Ruzicka",
booktitle = "Mathematical Foundations of Computer Science 1997 - 22nd International Symposium, MFCS 1997, Proceedings",
address = "Germany",
note = "22nd International Symposium on Mathematical Foundations of Computer Science, MFCS 1997 ; Conference date: 25-08-1997 Through 29-08-1997",
}