Guided Monte Carlo Tree Search for Planning in Learned Environments


Jelle Van Eyck, Jan Ramon, Fabian Guiza, Geert MeyFroidt, Maurice Bruynooghe, Greet Van den Berghe ;
Proceedings of the 5th Asian Conference on Machine Learning, PMLR 29:33-47, 2013.


Monte Carlo tree search (MCTS) is a sampling and simulation based technique for searching in large search spaces containing both decision nodes and probabilistic events. This technique has recently become popular due to its successful application to games, e.g. Poker and Go. Such games have known rules and the alternation between self-moves and non-deterministic events or opponent moves can be used to prune uninteresting branches. In this paper we study a real-world setting where the processes in the domain have a high degree of uncertainty and the need for longer-term planning implies a sequence of (planning) decisions without any intermediate feedback. Fortunately, unlike the combinatorial complexity in strategic games, many real-world environments can be approximated by efficient algorithms on a short term. This paper proposes an MCTS variant using a new type of prior information based on estimating the effects of part of the world and explores its application to the problem of hospital planning, where machine learning algorithms can be used to predict the length of stay of patients for each of the different stages of their recovery.

Related Material