Super-Exponential Regret for UCT, AlphaGo and Variants

我们改进了Coquelin和Munos（2007）的下界证明，证明了在$D$-chain环境中，UCT算法可能会有$\exp(\dots\exp(1)\dots)$的遗憾（其中$\Omega(D)$个exp项），而一个“多项式”UCT变体在同一环境中的遗憾为$\exp_2(\exp_2(D - O(\log D)))$。原始证明在奖励在$[0,1]$范围内的情况下存在疏漏，我们在本文中进行了修正。我们还将证明适应于AlphaGo的MCTS及其后代（例如AlphaZero、Leela Zero），以显示$\exp_2(\exp_2(D- O(\log D)))$的遗憾。

论文旨在改进Coquelin和Munos（2007）的下界证明，以展示UCT算法在特定环境下可能具有指数级的遗憾值。同时，将证明适用于AlphaGo的MCTS及其后继算法，如AlphaZero和Leela Zero。

论文修复了原始证明中对奖励范围的疏忽，并将证明应用于AlphaGo的MCTS及其后继算法，以展示UCT算法的指数级遗憾值。为了解决这个问题，论文提出了一种新的策略。

论文的亮点包括修复了原始证明中的一个漏洞，将证明应用于AlphaGo的MCTS及其后继算法，并展示了UCT算法的指数级遗憾值。实验使用了特定的环境，并使用了一些数据集。论文未公开代码。这项工作为进一步研究提供了基础。

最近的相关研究包括：1. Browne等人（2012）的“蒙特卡罗树搜索和它的应用”；2. Silver等人（2017）的“Mastering the game of Go without human knowledge”。