# Bandit Algorithms for Tree Search

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Aug 2014.

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

- [Interpretable Contrastive Monte Carlo Tree Search Reasoning](https://mlsanity.com/paper/2410.01707/) (2024)
- [UCB algorithms for multi-armed bandits: Precise regret and adaptive inference](https://mlsanity.com/paper/2412.06126/) (2024)
- [IRIS: Interactive Research Ideation System for Accelerating Scientific Discovery](https://mlsanity.com/paper/2504.16728/) (2025)
- [Monte Carlo Tree Search with Boltzmann Exploration](https://mlsanity.com/paper/2404.07732/) (2024)
- [ProbeLLM: Automating Principled Diagnosis of LLM Failures](https://mlsanity.com/paper/2602.12966/) (2026)
- [Stochastic simultaneous optimistic optimization](https://mlsanity.com/paper/2604.24537/) (2026)
- [A Unified Perspective on Value Backup and Exploration in Monte-Carlo Tree Search](https://mlsanity.com/paper/2202.07071/) (2022)
- [Scale-Adaptive Balancing of Exploration and Exploitation in Classical Planning](https://mlsanity.com/paper/2305.09840/) (2023)
- [Active Inference Tree Search in Large POMDPs](https://mlsanity.com/paper/2103.13860/) (2021)
- [Lookahead Pathology in Monte-Carlo Tree Search](https://mlsanity.com/paper/2212.05208/) (2022)
- [Super-Exponential Regret for UCT, AlphaGo and Variants](https://mlsanity.com/paper/2405.04407/) (2024)
- [Sound Heuristic Search Value Iteration for Undiscounted POMDPs with Reachability Objectives](https://mlsanity.com/paper/2406.02871/) (2024)
- [Tokenized Bandit for LLM Decoding and Alignment](https://mlsanity.com/paper/2506.07276/) (2025)
- [Planning in entropy-regularized Markov decision processes and games](https://mlsanity.com/paper/2604.19695/) (2026)
- [Exponential Speedups by Rerooting Levin Tree Search](https://mlsanity.com/paper/2412.05196/) (2024)
- [Scale-free adaptive planning for deterministic dynamics & discounted rewards](https://mlsanity.com/paper/2604.18312/) (2026)
- [Agent-UCT: Upper Confidence Bounds Applied to Trees for Agentic Workflow Optimization with Cost-Awareness](https://mlsanity.com/paper/2607.24162/) (2026)
- [Second-Order Smooth Planning with Optimal-Transport Bellman Smoothing](https://mlsanity.com/paper/2609.06484/) (2026)
- [Improved Monte Carlo Planning via Causal Disentanglement for Structurally-Decomposed Markov Decision Processes](https://mlsanity.com/paper/2406.16151/) (2024)
- [AlphaBeta is not as good as you think: a simple class of synthetic games for a better analysis of deterministic game-solving algorithms](https://mlsanity.com/paper/2506.21996/) (2025)
- [An Uncertainty-Weighted Decision Transformer for Navigation in Dense, Complex Driving Scenarios](https://mlsanity.com/paper/2509.13132/) (2025)
- [An Efficient Algorithm for Thresholding Monte Carlo Tree Search](https://mlsanity.com/paper/2601.22600/) (2026)
- [Sampling-guided exploration of active feature selection policies](https://mlsanity.com/paper/2603.15110/) (2026)
- [Bandits on graphs and structures](https://mlsanity.com/paper/2605.03493/) (2026)
- [Memory--Batch Tradeoffs in Lipschitz Bandits](https://mlsanity.com/paper/2608.07922/) (2026)

## Abstract (arXiv)

Bandit based methods for tree search have recently gained popularity when applied to huge trees, e.g. in the game of go [6]. Their efficient exploration of the tree enables to re- turn rapidly a good value, and improve preci- sion if more time is provided. The UCT algo- rithm [8], a tree search method based on Up- per Confidence Bounds (UCB) [2], is believed to adapt locally to the effective smoothness of the tree. However, we show that UCT is "over-optimistic" in some sense, leading to a worst-case regret that may be very poor. We propose alternative bandit algorithms for tree search. First, a modification of UCT us- ing a confidence sequence that scales expo- nentially in the horizon depth is analyzed. We then consider Flat-UCB performed on the leaves and provide a finite regret bound with high probability. Then, we introduce and analyze a Bandit Algorithm for Smooth Trees (BAST) which takes into account ac- tual smoothness of the rewards for perform- ing efficient "cuts" of sub-optimal branches with high confidence. Finally, we present an incremental tree expansion which applies when the full tree is too big (possibly in- finite) to be entirely represented and show that with high probability, only the optimal branches are indefinitely developed. We illus- trate these methods on a global optimization problem of a continuous function, given noisy values.