Efficient dynamic-programming updates in partially observable Markov decision processes
Michael L. Littman, Anthony R. Cassandra, Leslie Pack Kaelbling · 1995
We examine the problem of performing exact dynamic-programming updates in partially observable Markov decision processes (pomdps) from a computational complexity viewpoint. Dynamic-programming updates are a crucial operation in a wide range of pomdp solution methods and we find that it is intractable to perform these updates on piecewise-linear convex value functions for general pomdps. We offer a new algorithm, called the witness algorithm, which can compute updated value functions efficiently on a restricted class of pomdps in which the number of linear facets is not too great. We compare the witness algorithm to existing algorithms analytically and empirically and find that it is the fastest algorithm over a wide range of pomdp sizes. 1 Introduction A partially observable Markov decision processes (pomdp) is a Markov decision process in which the decisions must be based solely on noisy and incomplete observations of the system's state. Although this model can be applied to a wider...