Dans cet exposé à visée introductive, on considère le calcul pratique d’une stratégie visant à optimiser la récompense moyenne espérée dans un processus de décision markovien.
La stratégie est calculée avec un horizon glissant et à l’aide de la recherche arborescente Monte-Carlo (Monte Carlo Tree Search, MCTS),
une méthode reconnue pour sa capacité à passer à l’échelle dans des espaces d’états de grande dimension.
On présente les garanties théoriques associées à cette approche. L’analyse formelle de MCTS étant notoirement difficile, des résultats récents dans ce domaine sont discutés.
En outre, l’algorithme MCTS est enrichi par une notion de guides symboliques, et l’on montre que ses garanties théoriques sont préservées.
Ces guides symboliques sont utilisés pour biaiser les stratégies de sélection et de simulation de MCTS. Les techniques proposées sont illustrées à l’aide du jeu populaire Pac-Man.
