A fast point-based algorithm for POMDPs

Nikos Vlassis and Matthijs Spaan

We describe a point-based approximate value iteration algorithm
for partially observable Markov decision processes. The algorithm
performs value function updates ensuring that in each iteration the new
value function is an upper bound to the previous value function, as
estimated on a sampled set of belief points. A randomized belief-point
selection scheme allows for fast update steps. Preliminary results
indicate that the proposed algorithm achieves a good trade-off between
speed and solution quality.