Tech Report CS-94-40

The Witness Algorithm: Solving Partially Observable Markov Decision Processes

Michael L. Littman

December 1994


Markov decision processes (MDP's) are a mathematical formalization of problems in which a decision-maker must choose how to act to maximize its reward over a series of interactions with its environment. Partially observable Markov decision processes (POMDP's) generalize the MDP framework to the case where the agent must make its decisions in partial ignorance of its current situation.

This paper describes the POMDP framework and presents some well-known results from the field. It then presents a novel method called the witness algorithm for solving POMDP problems and analyzes its computational complexity. The paper argues that the witness algorithm is superior to existing algorithms for solving POMDP's in an important complexity-theoretic sense.

(complete text in pdf or gzipped postscript)