TY - GEN
T1 - The complexity of policy evaluation for finite-horizon partially-observable markov decision processes
AU - Mundhenk, Martin
AU - Goldsmith, Judy
AU - Allender, Eric
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1997.
PY - 1997
Y1 - 1997
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/84947768393
UR - https://www.scopus.com/pages/publications/84947768393#tab=citedBy
U2 - 10.1007/bfb0029956
DO - 10.1007/bfb0029956
M3 - Conference contribution
AN - SCOPUS:84947768393
SN - 3540634371
SN - 9783540634379
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 129
EP - 138
BT - Mathematical Foundations of Computer Science 1997 - 22nd International Symposium, MFCS 1997, Proceedings
A2 - Privara, Igor
A2 - Ruzicka, Peter
T2 - 22nd International Symposium on Mathematical Foundations of Computer Science, MFCS 1997
Y2 - 25 August 1997 through 29 August 1997
ER -