This week's seminar (see http://www.iro.umontreal.ca/article.php3? id_article=107&lang=en):

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

by Francois Laviolette, Département d’Informatique Université Laval

Location: McConnell Engineering Building (McGill), room 437 Time: March 4th 2008, 10h00

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 explo- ration of the environment in order to update the value function. The un- derlying ideas are very similar to temporal difference learning algorithms for MDPs. In particular, SSVI takes advantage of a soft-max actions se- lection 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.