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

Understand

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.