The complexity of policy evaluation for finite-horizon partially-observable markov decision processes

Martin Mundhenk; Judy Goldsmith; Eric Allender

doi:10.1007/bfb0029956

The complexity of policy evaluation for finite-horizon partially-observable markov decision processes

Martin Mundhenk, Judy Goldsmith, Eric Allender

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

9 Scopus citations

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 NP^PP , a class for which not many natural problems are known to be complete.

Original language	English
Title of host publication	Mathematical Foundations of Computer Science 1997 - 22nd International Symposium, MFCS 1997, Proceedings
Editors	Igor Privara, Peter Ruzicka
Pages	129-138
Number of pages	10
DOIs	https://doi.org/10.1007/bfb0029956
State	Published - 1997
Event	22nd International Symposium on Mathematical Foundations of Computer Science, MFCS 1997 - Bratislava, Slovakia Duration: Aug 25 1997 → Aug 29 1997

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1295
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	22nd International Symposium on Mathematical Foundations of Computer Science, MFCS 1997
Country/Territory	Slovakia
City	Bratislava
Period	8/25/97 → 8/29/97

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1997.

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/bfb0029956

Cite this

Mundhenk, M., Goldsmith, J., & Allender, E. (1997). The complexity of policy evaluation for finite-horizon partially-observable markov decision processes. In I. Privara, & P. Ruzicka (Eds.), Mathematical Foundations of Computer Science 1997 - 22nd International Symposium, MFCS 1997, Proceedings (pp. 129-138). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1295). https://doi.org/10.1007/bfb0029956

Mundhenk, Martin ; Goldsmith, Judy ; Allender, Eric. / The complexity of policy evaluation for finite-horizon partially-observable markov decision processes. Mathematical Foundations of Computer Science 1997 - 22nd International Symposium, MFCS 1997, Proceedings. editor / Igor Privara ; Peter Ruzicka. 1997. pp. 129-138 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{bebfa4c7c4154776999f7e94a55f5128,

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",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1997.; 22nd International Symposium on Mathematical Foundations of Computer Science, MFCS 1997 ; Conference date: 25-08-1997 Through 29-08-1997",

year = "1997",

doi = "10.1007/bfb0029956",

language = "English",

isbn = "3540634371",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "129--138",

editor = "Igor Privara and Peter Ruzicka",

booktitle = "Mathematical Foundations of Computer Science 1997 - 22nd International Symposium, MFCS 1997, Proceedings",

}

Mundhenk, M, Goldsmith, J & Allender, E 1997, The complexity of policy evaluation for finite-horizon partially-observable markov decision processes. in I Privara & P Ruzicka (eds), Mathematical Foundations of Computer Science 1997 - 22nd International Symposium, MFCS 1997, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1295, pp. 129-138, 22nd International Symposium on Mathematical Foundations of Computer Science, MFCS 1997, Bratislava, Slovakia, 8/25/97. https://doi.org/10.1007/bfb0029956

The complexity of policy evaluation for finite-horizon partially-observable markov decision processes. / Mundhenk, Martin; Goldsmith, Judy; Allender, Eric.
Mathematical Foundations of Computer Science 1997 - 22nd International Symposium, MFCS 1997, Proceedings. ed. / Igor Privara; Peter Ruzicka. 1997. p. 129-138 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1295).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 - http://www.scopus.com/inward/record.url?scp=84947768393&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84947768393&partnerID=8YFLogxK

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 -

Mundhenk M, Goldsmith J, Allender E. The complexity of policy evaluation for finite-horizon partially-observable markov decision processes. In Privara I, Ruzicka P, editors, Mathematical Foundations of Computer Science 1997 - 22nd International Symposium, MFCS 1997, Proceedings. 1997. p. 129-138. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/bfb0029956

The complexity of policy evaluation for finite-horizon partially-observable markov decision processes

Abstract

Publication series

Conference

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this