Recherche d'arbres de Monte-Carlo par identification du meilleur bras.

Résumé Les progrès récents des outils et des techniques de bandit pour l'apprentissage séquentiel permettent régulièrement de nouvelles applications et promettent la résolution d'une série de problèmes connexes difficiles. Nous étudions le problème de la recherche dans un arbre de jeu, où le but est d'identifier rapidement le coup optimal dans un arbre de jeu donné en échantillonnant séquentiellement ses gains stochastiques. Nous développons de nouveaux algorithmes pour des arbres de profondeur arbitraire, qui fonctionnent en résumant tous les niveaux plus profonds de l'arbre en intervalles de confiance à la profondeur un, et en appliquant une procédure d'identification du meilleur bras à la racine. Nous prouvons de nouvelles garanties de complexité d'échantillon avec une dépendance raffinée sur l'instance du problème. Nous montrons expérimentalement que nos algorithmes sont plus performants que les algorithmes existants basés sur l'élimination et qu'ils égalent les méthodes spéciales précédentes pour les arbres de profondeur deux.