# Monte-Carlo Tree Search by Best Arm Identification

arXiv: https://arxiv.org/abs/1706.02986 · HTML: https://mlsanity.com/paper/1706.02986/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jun 2017.

## Built on by (most cited first, 13 of 13)

- [Huxley-G"odel Machine: Human-Level Coding Agent Development by an Approximation of the Optimal Self-Improving Machine](https://mlsanity.com/paper/2510.21614/) (2025)
- [Improving Monte Carlo Tree Search for Symbolic Regression](https://mlsanity.com/paper/2509.15929/) (2025)
- [Monte Carlo Tree Search Algorithms for Risk-Aware and Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2211.13032/) (2022)
- [Planning in entropy-regularized Markov decision processes and games](https://mlsanity.com/paper/2604.19695/) (2026)
- [Is Policy Learning Overrated?: Width-Based Planning and Active Learning for Atari](https://mlsanity.com/paper/2109.15310/) (2021)
- [Best Arm Identification under Additive Transfer Bandits](https://mlsanity.com/paper/2112.04083/) (2021)
- [An Efficient Dynamic Sampling Policy For Monte Carlo Tree Search](https://mlsanity.com/paper/2204.12043/) (2022)
- [Scale-free adaptive planning for deterministic dynamics & discounted rewards](https://mlsanity.com/paper/2604.18312/) (2026)
- [Two-Fidelity Best-Action Identification for Stochastic Minimax Tree](https://mlsanity.com/paper/2606.01708/) (2026)
- [Second-Order Smooth Planning with Optimal-Transport Bellman Smoothing](https://mlsanity.com/paper/2609.06484/) (2026)
- [An Efficient Algorithm for Thresholding Monte Carlo Tree Search](https://mlsanity.com/paper/2601.22600/) (2026)
- [varepsilon-Good Action Identification in Fixed-Budget Monte Carlo Tree Search](https://mlsanity.com/paper/2605.11324/) (2026)
- [Quantum Monte Carlo Tree Search with Fixed Confidence](https://mlsanity.com/paper/2609.33132/) (2026)

## Abstract (arXiv)

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.