A Stochastic Algorithm for Partially Observable Markov Decision Processes (POMDPs)

par/by François Laviolette
Département d'Informatique
Université Laval

We introduce a new backup operator for point-based POMDP's algorithms which performs a look-ahead search at depth greater than one. We apply this operator into a new algorithm, called Stochastic Search Value Iteration (SSVI). This new algorithm relies on stochastic exploration of the environment in order to update the value function. The underlying ideas are very similar to temporal difference learning algorithms for MDPs. In particular, SSVI takes advantage of a soft-max actions selection function and of the random character of the environment itself. This is in opposition with existing POMDP's point-based algorithms. Empirical results show that our algorithm is very competitive on usual benchmark problems. This suggests that stochastic algorithms are an alternative for solving large POMDPs.