# Super-Exponential Regret for UCT, AlphaGo and Variants

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 5 references that are in the map.
- First posted on arXiv 7 May 2024.

## Builds on (most cited first, 2 of 2)

- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [Bandit Algorithms for Tree Search](https://mlsanity.com/paper/1408.2028/) (2014)

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

- [Exponential Speedups by Rerooting Levin Tree Search](https://mlsanity.com/paper/2412.05196/) (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)

## Abstract (arXiv)

We improve the proofs of the lower bounds of Coquelin and Munos (2007) that demonstrate that UCT can have exp(dotsexp(1)dots) regret (with Omega(D) exp terms) on the D-chain environment, and that a `polynomial' UCT variant has exp2(exp2(D - O(log D))) regret on the same environment -- the original proofs contain an oversight for rewards bounded in [0, 1], which we fix in the present draft. We also adapt the proofs to AlphaGo's MCTS and its descendants (e.g., AlphaZero, Leela Zero) to also show exp2(exp2(D - O(log D))) regret.