Everyone is welcome to attend the ML seminar 'Monte Carlo Tree Search for Asymmetric Trees' given by Thomas Moerland.
Abstract:
We present an extension of Monte Carlo Tree Search (MCTS) that strongly
increases its efficiency for trees with asymmetry and/or loops.
Asymmetric termination of search trees introduces a type of uncertainty
for which the standard upper confidence bound (UCB) formula does not
account. Our first algorithm (MCTS-T), which assumes a non-stochastic
environment, backs-up tree structure uncertainty and leverages it for
exploration in a modified UCB formula. Results show vastly improved
efficiency in a well-known asymmetric domain in which MCTS performs
arbitrarily bad. Next, we connect the ideas about asymmetric termination
to the presence of loops in the tree, where the same state appears
multiple times in a single trace. An extension to our algorithm
(MCTS-T+), which in addition to non-stochasticity assumes full state
observability, further increases search efficiency for domains with
loops as well. Benchmark testing on a set of OpenAI Gym and Atari 2600
games indicates that our algorithms always perform better than or at
least equivalent to standard MCTS, and could be first-choice tree search
algorithms for non-stochastic, fully-observable environments.
