Super-Exponential Regret for UCT, AlphaGo and Variants

2024-05-07 · Laurent Orseau, Remi Munos

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.

📄 PDF Abstract BibTeX arXiv:2405.04407

Code (0)

등록된 구현이 없습니다.

Methods 이 논문이 사용한 방법론

AlphaZero AlphaZero is a reinforcement learning agent for playing board games such as Go, chess, and shogi.

Convex Regularization in Monte-Carlo Tree Search

2020-07-01 · Tuan Dam, Carlo D'Eramo, Jan Peters, Joni Pajarinen

Monte-Carlo planning and Reinforcement Learning (RL) are essential to sequential decision making. The recent AlphaGo and AlphaZero algorithms have shown how to successfully combine these two paradigms in order to solve l…

Atari Games Decision Making Reinforcement Learning (RL)Sequential Decision Making

Discrete Choice Models

Super-Exponential Regret for UCT, AlphaGo and Variants

Code (0)

Methods 이 논문이 사용한 방법론

Similar Papers 제목 키워드 기반

Convex Regularization in Monte-Carlo Tree Search

Local Anti-Concentration Class: Logarithmic Regret for Greedy Linear Contextual Bandit

Convergence of Regret Matching in Potential Games and Constrained Optimization

Demystifying AlphaGo Zero as AlphaGo GAN

Nested bandits