Title: Monte-Carlo Tree Search by Best Arm Identification,
Abstract: Recent advances in bandit tools and techniques for sequential learning are
steadily enabling new applications and are promising the resolution of a range
of challenging related problems. We study the game tree search problem, where
the goal is to quickly identify the optimal move in a given game tree by
sequentially sampling its stochastic payoffs. We develop new algorithms for
trees of arbitrary depth, that operate by summarizing all deeper levels of the
tree into confidence intervals at depth one, and applying a best arm
identification procedure at the root. We prove new sample complexity guarantees
with a refined dependence on the problem instance. We show experimentally that
our algorithms outperform existing elimination-based algorithms and match
previous special-purpose methods for depth-two trees.