Search-Tree Scaling in Parallel Monte Carlo Tree Search

The exploration-exploitation tradeoff is a fundamental challenge in reinforcement learning. In Monte Carlo Tree Search (MCTS), this tradeoff is balanced explicitly by the pUCT exploration coefficient and implicitly by parallelism when the search is combined with neural network evaluations. However, the exploration coefficient is typically tuned as an algorithmic hyperparameter, while the degree of parallelism is often treated as a system detail. To this end, we characterize how these two factors shape the search-tree structure and jointly affect performance scaling. We prove that, under regularity conditions, the depth of the optimal path grows as $\Theta(\sqrt{n}/\log n)$ for $n$ simulations under the MuZero exploration coefficient formula. For tree-parallel MCTS, we prove that the search depth preserves the same asymptotic order when $T=o(\sqrt{n})$, while sufficiently large parallelism introduces contention and reduces the depth growth rate to $\Theta(n/T)$ for $T$ threads. Our empirical findings indicate that each doubling of the number of threads decreases the best-performing exploration coefficient by approximately 0.19. Overall, our characterization connects the search-tree structure with the exploration-exploitation behavior in pUCT, providing insight into how exploration coefficients and parallelism can be jointly tuned.