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

• URL: http://arxiv.org/abs/2605.08982v1
• Date: Sat, 09 May 2026 14:54:07 GMT
• Title: PMCTS: Particle Monte Carlo Tree Search for Principled Parallelized Inference Time Scaling
• Abstract summary: We introduce Particle MCTS (PMCTS), to our knowledge the first principled parallel MCTS algorithm which is suited for neural network evaluations and can preserve formal policy improvement guarantees.<n>PMCTS scales well with parallel compute and significantly outperforms the popular neural network baselines across domains.
• Score: 8.751986657630017
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Monte Carlo Tree Search (MCTS) is a widely used approach for policy improvement through search with increasing popularity for real world applications. Due to the sequential and deterministic nature of its search, runtime-scaling of MCTS with parallel compute remains a major challenge. We introduce Particle MCTS (PMCTS), to our knowledge the first principled parallel MCTS algorithm which is suited for neural network evaluations and can preserve formal policy improvement guarantees. Empirically, PMCTS scales well with parallel compute and significantly outperforms the popular heuristic-based baselines across domains.

Related papers

• Parallelizing Tree Search with Twice Sequential Monte Carlo [7.863528049670872]
  We present Twice Sequential Monte Carlo Tree Search (TSMCTS) as an alternative to the Monte Carlo Tree Search (MCTS) algorithm.<n>TSMCTS is easier to parallelize and more suitable to GPU acceleration.<n>We show that TSMCTS scales favorably with sequential compute while retaining the properties that make SMC natural to parallelize.
  arXiv  Detail & Related papers  (2025-11-18T07:54:29Z)
• Partially Observable Monte-Carlo Graph Search [15.40087235187116]
  We propose a new sampling-based algorithm, the partially observable Monte-Carlo graph search (POMCGS) to solve large POMDPs offline.<n>POMCGS folds this search tree on the fly to construct a policy graph, so that computations can be drastically reduced.<n>We demonstrate that POMCGS can generate policies on the most challenging POMDPs, which cannot be computed by previous offline algorithms.
  arXiv  Detail & Related papers  (2025-07-28T16:02:36Z)
• Trust-Region Twisted Policy Improvement [8.73717644648873]
  Monte-Carlo tree search (MCTS) has driven many recent breakthroughs in deep reinforcement learning (RL)<n>We tailor Monte-Carlo planners specifically for RL by improving data generation within the planner through constrained action sampling and explicit terminal state handling.<n>This leads to our Trust-Region Twisted SMC (TRT-SMC), which shows improved runtime and sample-efficiency over baseline MCTS and SMC methods in both discrete and continuous domains.
  arXiv  Detail & Related papers  (2025-04-08T13:47:07Z)
• LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
  The framework combines Monte Carlo Tree Search (MCTS) with iterative Self-Refine to optimize the reasoning path. The framework has been tested on general and advanced benchmarks, showing superior performance in terms of search efficiency and problem-solving capability.
  arXiv  Detail & Related papers  (2024-10-03T18:12:29Z)
• Optimized Monte Carlo Tree Search for Enhanced Decision Making in the FrozenLake Environment [0.0]
  Monte Carlo Tree Search (MCTS) is a powerful algorithm for solving complex decision-making problems. This paper presents an optimized MCTS implementation applied to the FrozenLake environment, a classic reinforcement learning task.
  arXiv  Detail & Related papers  (2024-09-25T05:04:53Z)
• Don't throw away your value model! Generating more preferable text with Value-Guided Monte-Carlo Tree Search decoding [104.77043794433777]
  Inference-time search algorithms may seem unnecessary when generating natural language text based on Proximal Policy Optimization (PPO) In this paper, we demonstrate that it is possible to get extra mileage out of PPO by integrating Monte-Carlo Tree Search (MCTS) on top. We present PPO-MCTS, which can integrate the value network from PPO to work closely with the policy network during inference-time generation.
  arXiv  Detail & Related papers  (2023-09-26T15:57:57Z)
• Learning Logic Specifications for Soft Policy Guidance in POMCP [71.69251176275638]
  Partially Observable Monte Carlo Planning (POMCP) is an efficient solver for Partially Observable Markov Decision Processes (POMDPs) POMCP suffers from sparse reward function, namely, rewards achieved only when the final goal is reached. In this paper, we use inductive logic programming to learn logic specifications from traces of POMCP executions.
  arXiv  Detail & Related papers  (2023-03-16T09:37:10Z)
• Continuous Monte Carlo Graph Search [61.11769232283621]
  Continuous Monte Carlo Graph Search ( CMCGS) is an extension of Monte Carlo Tree Search (MCTS) to online planning. CMCGS takes advantage of the insight that, during planning, sharing the same action policy between several states can yield high performance. It can be scaled up through parallelization, and it outperforms the Cross-Entropy Method (CEM) in continuous control with learned dynamics models.
  arXiv  Detail & Related papers  (2022-10-04T07:34:06Z)
• Policy Gradient Algorithms with Monte Carlo Tree Learning for Non-Markov Decision Processes [3.9311044240639568]
  Policy gradient (PG) is a reinforcement learning (RL) approach that optimize a parameterized policy model for an expected return using gradient ascent. While PG can work well even in non-Markovian environments, it may encounter plateaus or peakiness issues. In this work, we first introduce Monte Carlo Tree Learning (MCTL), an adaptation of MCTS for online RL. We then explore a combined policy approach of PG and MCTL to leverage their strengths.
  arXiv  Detail & Related papers  (2022-06-02T12:21:40Z)
• Monte Carlo Tree Search for high precision manufacturing [55.60116686945561]
  We make use of an expert-based simulator and adapt the MCTS default policy to deal with the manufacturing process. Common reasons for this are that there is no efficient simulator of the process available or there exist problems in applying MCTS to the complex rules of the process.
  arXiv  Detail & Related papers  (2021-07-28T14:56:17Z)
• On Effective Parallelization of Monte Carlo Tree Search [51.15940034629022]
  Monte Carlo Tree Search (MCTS) is computationally expensive as it requires a substantial number of rollouts to construct the search tree. How to design effective parallel MCTS algorithms has not been systematically studied and remains poorly understood. We demonstrate how proposed necessary conditions can be adopted to design more effective parallel MCTS algorithms.
  arXiv  Detail & Related papers  (2020-06-15T21:36:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.