MCTS Based on Simple Regret
This work addresses a fundamental issue in Monte Carlo tree search for games and decision processes, offering incremental improvements over the state-of-the-art UCT algorithm.
The paper tackles the mismatch between UCT's cumulative regret minimization and MCTS's need for simple regret minimization, introducing new bandit policies and a two-stage MCTS scheme (SR+CR) that empirically outperforms UCT, and a VOI-aware sampling scheme that further improves performance over UCT and other algorithms.
UCT, a state-of-the art algorithm for Monte Carlo tree search (MCTS) in games and Markov decision processes, is based on UCB, a sampling policy for the Multi-armed Bandit problem (MAB) that minimizes the cumulative regret. However, search differs from MAB in that in MCTS it is usually only the final "arm pull" (the actual move selection) that collects a reward, rather than all "arm pulls". Therefore, it makes more sense to minimize the simple regret, as opposed to the cumulative regret. We begin by introducing policies for multi-armed bandits with lower finite-time and asymptotic simple regret than UCB, using it to develop a two-stage scheme (SR+CR) for MCTS which outperforms UCT empirically. Optimizing the sampling process is itself a metareasoning problem, a solution of which can use value of information (VOI) techniques. Although the theory of VOI for search exists, applying it to MCTS is non-trivial, as typical myopic assumptions fail. Lacking a complete working VOI theory for MCTS, we nevertheless propose a sampling scheme that is "aware" of VOI, achieving an algorithm that in empirical evaluation outperforms both UCT and the other proposed algorithms.