Modification of improved upper confidence bounds for regulating exploration in Monte-Carlo tree search

作者：Liu Yun Ching^*; Tsuruoka Yoshimasa^*

来源：Theoretical Computer Science, 2016, 644: 92-105.

DOI：10.1016/j.tcs.2016.06.034

• Monte-Carlo tree search
• Multi-armed bandit
• Upper confidence bounds

The key to the success of the upper confidence bounds on trees (UCT) algorithm, which is the most widely adopted variant of the Monte-Carlo tree search (MCTS) algorithm, is that it combines MCTS with the upper confidence bounds (UCB) bandit algorithm. The improved UCB algorithm is a bandit algorithm that has a superior regret bound to the UCB algorithm. However, some characteristics of the improved UCB algorithm are not suitable for direct application to MCTS. The combined confidence bounds (CCB) bandit algorithm is a modification of the improved UCB algorithm, making it more suitable for the task of tree searches. The CCB bandit algorithm can be further extended to regulate exploration in simple regret minimization in MCTS, through the exploration regulating factor. In this paper, we present an analysis of the bound on simple regret for the CCB bandit algorithm. We also give a comprehensive overview of how different choices of the exploration factor impact the games of 9 x 9 Go and 9 x 9 Nogo.

• 出版日期2016-9-6