Super-Exponential Regret for UCT, AlphaGo and Variants

2024/05/07 by Laurent Orseau, Rémi Munos, Orseau, Laurent +1 · 1 citation
Computer Science · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Neural Networks and Applications

paper · pdf · doi:10.48550/arxiv.2405.04407

openalex publication_date 2024/05/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We improve the proofs of the lower bounds of Coquelin and Munos (2007) that demonstrate that UCT can have exp(…exp(1)…) regret (with Ω(D) exp terms) on the D-chain environment, and that a `polynomial' UCT variant has exp₂(exp₂(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 exp₂(exp₂(D - O(log D))) regret.

Cited by

• AlphaBeta is not as good as you think: a simple class of synthetic games for a better analysis of deterministic game-solving algorithms

Related

• A Note on Bounding Regret of the C²UCB Contextual Combinatorial Bandit
• Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs
• Explore First, Exploit Next: The True Shape of Regret in Bandit Problems
• Adaptive Minimax Regret against Smooth Logarithmic Losses over High-Dimensional ℓ₁-Balls via Envelope Complexity
• KL-UCB-switch: optimal regret bounds for stochastic bandits from both a distribution-dependent and a distribution-free viewpoints