Incremental Pruning: A Simple, Fast, Exact Method for
Partially Observable Markov Decision Processes

Anthony Cassandra
Computer Science Dept.
Brown University
Providence, RI 02912
arc@cs.brown.edu

Michael L. Littman
Dept. of Computer Science
Duke University
Durham, NC 27708-0129
mlittman@cs.duke.edu

Nevin L. Zhang 
Computer Science Dept. 
The Hong Kong U. of Sci. & Tech. 
Clear Water Bay, Kowloon, HK 
HONG KONG
lzhang@cs.ust.hk

ABSTRACT

Most exact algorithms for general partially observable Markov decision
processes (POMDPs) use a form of dynamic programming in which a
piecewise-linear and convex representation of one value function is
transformed into another.  We examine variations of the ``incremental
pruning'' method for solving this problem and compare them to earlier
algorithms from theoretical and empirical perspectives.  We find that
incremental pruning is presently the most efficient exact method for
solving POMDPs.