Date/heure
18 janvier 2018
10:45 - 11:45
Oratrice ou orateur
Emilie Kaufmann
Catégorie d'évènement Séminaire Probabilités et Statistique
Résumé
In Monte-Carlo Tree Search (MCTS), the goal is to adaptively
explore paths in a game tree and perform random leaves evaluation, in
order to quickly discover the best action to take at the root. In this
talk, I will introduce a simple model for MCTS, that can be viewed as a
structured best arm identification problem in a multi-armed bandit
model. After a review of recent advances to tackle the standard best arm
identification (BAI) problem, I will explain how any BAI algorithm can
be converted to a MCTS algorithm. I will then present empirical results
and sample complexity guarantees for two particular algorithms,
UGapE-MCTS and LUCB-MCTS.
This is joint work with Aurélien Garivier (Université de Toulouse) and
Wouter Koolen (CWI, Amsterdam)