- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper proposes Particle MCTS, a way to parallelize AlphaZero/MuZero-style MCTS on GPUs. Instead of a deterministic selection rule, particles each sample a trajectory from the Gumbel-style improved policy, so no communication is needed during selection. The full method adds a tempered proposal with importance weights, merges duplicate trajectories and uses the ESS in the backups and visit counts. The theory shows that one batch backup consistently estimates the value of the selection policy and that PMCTS reduces to MCTS at . Experiments compare against virtual loss and virtual mean baselines at matched budgets on board games, Snake, Rubik's Cube, Brax and an LLM-prior Sokoban task, plus a wall-clock study and AlphaZero training.
Critical strengths
The idea is simple and fits GPUs well. Sampling instead of taking an argmax removes the communication between particles, and dealing with duplicates via SMC/ESS makes sense when network evaluations are deterministic. Runtime grows slowly with . The evaluation is broad (ten environments), and at large PMCTS is best or tied everywhere.
Critical weaknesses
-
I don't think the experiments show that the gains come from the parallelization. At , where nothing is parallel, PMCTS is already about 160 Elo above VL on the board-game average, out of about 210 at (Fig. 1); in 19x19 Go it is about 430 out of 500. In continuous control VM actually gains a bit more than PMCTS as grows. So most of the advantage seems to come from the base search (Gumbel-style selection and acting rule vs. PUCT), and sequential GumbelMCTS is already at PMCTS's level at (Fig. 7). The obvious missing baselines are virtual visits on top of the same Gumbel search, and sequential search with simulations.
-
I find the "principled policy improvement" claims oversold. The theorems are per-iteration importance-sampling consistency results, assuming independent unbiased leaf evaluations, which the paper itself says networks don't give, and nothing is said about the search after iterations. SPO (Macfarlane et al., NeurIPS 2024) is very close (an SMC planner, evaluated on the same Brax tasks and Rubik's Cube) and should be discussed.
Questions for authors
-
Can you add virtual visits on your own Gumbel-style search, and sequential GumbelMCTS with simulations? If PMCTS still scales better in , I could raise my score.
-
Sokoban: the appendix says 200 puzzles, but the plotted rates are all multiples of 2% and the error bands look like . How many puzzles were used?
-
With Gumbel scale 0 and deterministic networks, why do the root-parallel trees in Fig 7 differ at all?
Minor: with finite and a bootstrap, Eq. (4) gives the value of following for steps and then , not . Please say how many games are behind the Elo intervals.