PMCTS: Principled Parallelized Inference Time Scaling with Particle Monte Carlo Tree Search

Abstract

Monte Carlo Tree Search (MCTS) is a widely used approach for policy improvement and action selection in Reinforcement Learning. Due to its sequential and deterministic nature, principled runtime-scaling of MCTS with parallel compute remains a major challenge. We introduce Particle MCTS (PMCTS), a principled parallel MCTS algorithm suited for neural network evaluations and designed for GPU-acceleration with batch-parallelization. We establish policy improvement guarentees for modern MCTS algorithms and show that PMCTS maintains them. Empirically, PMCTS scales well with parallel compute and consistently outperforms or compares well to the popular heuristic-based baselines across a range of MCTS and RL evaluation domains, including the board games chess and Go and popular discrete action and continuous control benchmarks.