Monte-Carlo Tree Search by Best Arm Identification
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.
This paper treats the problem of Monte Carlo Tree Search in depth-k game trees. Even though the problem was considered last year for depth-two trees in 'Optimal best arm identification with fixed confidence' (COLT 2016), the present paper considerably extends this previous work that could not directly be generalized to higher depths. 
They propose a new type of algorithm that can be run with different Best Arm Identification (BAI) algorithms and they provide the analysis for LUCB and UGapE. The idea relies on two main ingredients : First, the BAI algorithm leads the learner in its first decision departing from the root of the tree and then, the subsequent 'representative leaf' is sampled. This leaf is chosen by following a somehow greedy path along the tree, each time choosing the action that maximizes (resp. minimizes) the expected value. 
This line of work sheds a new light on MCTS problems by bringing the tools developed in the framework of Best Arm Identification. The proposed method has several qualities :
1. It is fairly intuitive and easy to understand for the reader having some ground knowledge of the BAI literature;
2. It is computationally efficient, allowing to conduct convincing experiments;
3. It outperforms the existing algorithm FindTopWinner (see comment below).
The authors also prove a problem-dependent lower bound following the now classic technics from e.g. (Garivier and Kaufmann, 2016), (Kaufmann et al., 2015). Even though the final result of Lemma 7 is not fully explicit, the optimization problem can be numerically solved. This allows in particular to have a comparison basis for the experimental section, on top of existing algorithms. Also, as mentioned in the comments of Lemma 7, such a lower bound result gives a hope towards finally obtaining an asymptotically  optimal algorithm following the Track-And-Stop technique from (Garivier and Kaufmann, 2016). This is indeed an exciting perspective, coming with a few other new problems opened by this paper.
I only have minor comments:
- The Lemmas 13 and 14 seems to be the key tools that allow to control the behavior of the algorithm with respect to the choice of the 'representative leaf'. However, this intuition is not really clear in the proof of Theorem 3 that is sketched in the main paper. Space requirements don't make it easy but this could make the idea of the proof even clearer.
- The 'update information about the arms' in the Figure 2 is quite unclear. Actually, the exact action of the algorithm is a bit tricky, I had to read several times to understand whether the algorithm only chooses the first step or all the path of actions and where the information/feedback finally shows up. This could be made a bit clearer in the algorithm pseudo-code maybe.
- l 255 : 'uniformLY at random';
- Lemma 11 in Appendix, please chose i or k to index s;
Overall, I strongly recommend accepting this paper as it opens a new path towards the understanding of MCTS problems and may lead to future major advances.