L. Busoniu, R. Munos, B. De Schutter, and R. Babuska, "Optimistic planning for sparsely stochastic systems," Proceedings of the Workshop on Monte-Carlo Tree Search: Theory and Applications (MCTS) at the 21st International Conference on Automated Planning and Scheduling (ICAPS 2011), Freiburg, Germany, 2 pp., June 2011.
We describe an online planning algorithm for finite-action, sparsely stochastic Markov decision processes, in which the random state transitions can only end up in a small number of possible next states. The algorithm builds a planning tree by iteratively expanding states, where the most promising states are expanded first, in an optimistic procedure aiming to return a good action after a strictly limited number of expansions. The novel algorithm is called optimistic planning for sparsely stochastic systems.