Super-Exponential Regret for UCT, AlphaGo and Variants

Abstract

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