Watch the Unobserved: A Simple Approach to Parallelizing Monte Carlo Tree Search
This addresses the problem of high computational costs in MCTS for researchers and practitioners in AI, offering a novel parallelization method that is incremental over existing techniques.
The paper tackles the challenge of parallelizing Monte Carlo Tree Search (MCTS) due to its sequential nature, and introduces WU-UCT, an algorithm that achieves linear speedup with limited performance loss by tracking unobserved samples to modify the UCT tree policy.
Monte Carlo Tree Search (MCTS) algorithms have achieved great success on many challenging benchmarks (e.g., Computer Go). However, they generally require a large number of rollouts, making their applications costly. Furthermore, it is also extremely challenging to parallelize MCTS due to its inherent sequential nature: each rollout heavily relies on the statistics (e.g., node visitation counts) estimated from previous simulations to achieve an effective exploration-exploitation tradeoff. In spite of these difficulties, we develop an algorithm, WU-UCT, to effectively parallelize MCTS, which achieves linear speedup and exhibits only limited performance loss with an increasing number of workers. The key idea in WU-UCT is a set of statistics that we introduce to track the number of on-going yet incomplete simulation queries (named as unobserved samples). These statistics are used to modify the UCT tree policy in the selection steps in a principled manner to retain effective exploration-exploitation tradeoff when we parallelize the most time-consuming expansion and simulation steps. Experiments on a proprietary benchmark and the Atari Game benchmark demonstrate the linear speedup and the superior performance of WU-UCT comparing to existing techniques.