ML Seminar: Thomas Moerland (Delft University)

Everyone is welcome to attend the ML seminar 'Monte Carlo Tree Search for Asymmetric Trees' given by Thomas Moerland. Please visit the website for more information.
  • What English Machine Learning Seminars
  • When 04-09-2018 from 11:00 to 12:00 (Europe/Amsterdam / UTC200)
  • Where CWI, Room L016
  • Contact Name
  • Contact Phone 020-592 4189
  • Web Visit external website
  • Add event to calendar iCal

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.