PAL lab meeting 27, April, 2006 (Any) Solving Partially Observable Markov Decision Processes

Michael L. Littman. The witness algorithm: Solving partially observable Markov decision processes. Technical Report CS-94-40, Brown University, Department of Computer Science, Providence, RI, December 1994.

Abstract:
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. We argue that the witness algorithm is superior to existing algorithms for solving POMDP's in an important complexity-theoretic sense.

Outlines:

• Introduction to MDP
• CO(Completely Observable)-MDP vs. POMDP
  
• Definition of POMDP
• Solving POMDP
• POMDP Value Iteration