Tech Report CS-94-14

Optimal Policies for Partially Observable Markov Decision Processes

Anthony R. Cassandra

August 1994


The main objective of this report is to provide implementation details for the more popular exact algorithms for solving finite horizon partially observable Markov decision processes (POMDPs). Along with the existing algorithms, a new algorithm, Witness, is proposed that has empirically been faster than the existing exact techniques. In addition to algorithmic details, the basic formulas and concepts of POMDPs are presented, as well as explanations and discussion about the basic form of POMDP solutions. This document is aimed at those who do not have a lot of experience with the techniques or concepts of POMDPs.

(complete text in pdf or gzipped postscript)