acceptodds
Under review as a conference paper at ICLR 2027

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 parallel MCTS algorithm which is suited for neural network evaluations, designed for GPU-acceleration with batch-parallelization and retains MCTS's principled approximate policy improvement interpretation. Empirically, PMCTS scales well with parallel compute and consistently outperforms or compares well to the popular heuristic-based baselines across a range of popular discrete- and continuous-action benchmark domains, including Chess, 19x19 Go, 9x9 Go, Gardner Chess, Snake, classical control environments from Brax and LLM reasoning in Sokoban.

Primary area:
reinforcement learning
Keywords:
MCTS, search, policy improvement, RL, parallelization

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_zYGJOpenReview ↗
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, NN 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 N=1N=1. 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 NN. The evaluation is broad (ten environments), and at large NN PMCTS is best or tied everywhere.

Critical weaknesses
  1. I don't think the experiments show that the gains come from the parallelization. At N=1N=1, where nothing is parallel, PMCTS is already about 160 Elo above VL on the board-game average, out of about 210 at N=64N=64 (Fig. 1); in 19x19 Go it is about 430 out of 500. In continuous control VM actually gains a bit more than PMCTS as NN 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 N=1N=1 (Fig. 7). The obvious missing baselines are virtual visits on top of the same Gumbel search, and sequential search with M⋅NM\cdot N simulations.

  2. 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 MM 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
  1. Can you add virtual visits on your own Gumbel-style search, and sequential GumbelMCTS with M⋅NM\cdot N simulations? If PMCTS still scales better in NN, I could raise my score.

  2. Sokoban: the appendix says 200 puzzles, but the plotted rates are all multiples of 2% and the error bands look like n=50n=50. How many puzzles were used?

  3. With Gumbel scale 0 and deterministic networks, why do the root-parallel trees in Fig 7 differ at all?

Minor: with finite tt and a VπθV^{\pi_\theta} bootstrap, Eq. (4) gives the value of following π′\pi' for tt steps and then πθ\pi_\theta, not Vπ′V^{\pi'}. Please say how many games are behind the Elo intervals.

Reviewer_tm7DOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces Particle MCTS (PMCTS), a tree-parallel MCTS algorithm. It removes the sequential selection bottleneck of standard MCTS and makes search amenable to batched GPU evaluation of the neural networks. Building on Grill et al. (2020), the authors observe that stochastic, regularised-policy selection lets many trajectories be sampled independently in parallel. They then add SMC machinery to handle duplicate trajectories:

  • a higher-entropy proposal with importance correction,
  • deduplication,
  • ESS-weighted backups,
  • retrospective reweighting of the final action.

The paper gives per-iteration consistency results for the backups. It evaluates scaling with the number of particles N against Virtual Loss and Virtual Mean baselines across board games, single-agent discrete tasks, Brax continuous control, and an LLM-guided Sokoban task.

Critical strengths

Strengths

  • The core observation is simple, stochastic Grill-style selection permits communication-free, batch-parallel selection.
  • PMCTS scales well with N against virtual-visit baselines at matched (M, N), across a reasonably wide range of domains.
  • The wall-clock results show that within a batched JAX implementation, the method scales where synchronous virtual-visit methods do not.
  • The theoretical statements are formal and clearly scoped, and the appendices are candid about limitations.
Critical weaknesses

Weaknesses

  1. No measure of the performance cost of parallelism. The paper never compares PMCTS (M iterations × N particles) to sequential MCTS with M·N simulations, so it’s unclear how much search quality is lost by parallelising.

  2. Reproducibility: “The paper refers to supplementary code (Appendix I.8) that I could not find, so I could not verify the implementation.”

  3. Selective SMC comparison. SMC/TSMCTS baselines appear only on two board games at large search budgets (Fig. 9). They are absent on the single-agent tasks (Snake, RubiksCube) where SMC-based methods were originally evaluated. Sokoban, used in prior SMC-search work (e.g. SPO), appears only as an LLM-guided task with no SMC baseline.

  4. Citation omission. SPO (Macfarlane et al., NeurIPS 2024) is closely related prior work framing SMC search as KL-regularised policy improvement and should be discussed

Questions for authors
  1. How does PMCTS (M, N) compare to sequential Gumbel/PUCT MCTS with M·N simulations?
  2. How does PMCTS compare to SMC on Snake and RubiksCube?
  3. Snake has stochastic fruit spawns. Does the search model share the environment’s random key (making transitions deterministic and effectively revealing future spawns), or are spawns resampled? If the latter, how do deduplication and the shared-evaluation assumption handle stochastic transitions?
Reviewer_S1dDOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The authors propose a parallelized MCTS algorithm that retains the theoretical guarantees of standard sequential MCTS.

Critical strengths
  • Parallelizing MCTS is very important.

  • Maintaining the theoretical support.

  • Broad evaluations.

Critical weaknesses
  • An illustrative block diagram would make things clearer.

  • Looking at Figure 1, PMCTS seems to only perform better on smaller problems. For LLMs, the performance advantage as compared to other parallelized MCTS methods is unclear. BTW, what the is the y-axis label in the third sub-graph.

  • Shouldn't the authors also compare with sequential methods? This should provide a natural win for the proposed method.

Minor:

  • What is s' in line 90? It was not defined.

  • What is N(S_t) in Alg. 1? Also, M(.,.) takes two arguments, what happened to the actions? The notation table is only in the Appendix.

Questions for authors

See above.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.