Nonapproximability results for partially observable Markov decision processes

Christopher Lusena, Judy Goldsmith, Martin Mundhenk

Research output: Contribution to journalArticlepeer-review

60 Scopus citations


We show that for several variations of partially observable Markov decision processes, polynomial-time algorithms for finding control policies are unlikely to or simply don't have guarantees of finding policies within a constant factor or a constant summand of optimal. Here "unlikely" means "unless some complexity classes collapse," where the collapses considered are P = NP, P = PSPACE, or P = EXP. Until or unless these collapses are shown to hold, any control-policy designer must choose between such performance guarantees and efficient computation.

Original languageEnglish
Pages (from-to)83-103
Number of pages21
JournalJournal of Artificial Intelligence Research
StatePublished - 2001

ASJC Scopus subject areas

  • Artificial Intelligence


Dive into the research topics of 'Nonapproximability results for partially observable Markov decision processes'. Together they form a unique fingerprint.

Cite this