The Witness Algorithm: Solving Partially Observable Markov Decision Processes
Michael L. Littman · 1994
This paper describes the POMDP framework and presents some wellknown results from the field. It then presents a novel method called the witness algorithm for solving POMDP problems and analyzes its computational complexity. We argue that the witness algorithm is superior to existing algorithms for solving POMDP's in an important complexity-theoretic sense.