Parallelizing Tree Search with Twice Sequential Monte Carlo

• URL: http://arxiv.org/abs/2511.14220v1
• Date: Tue, 18 Nov 2025 07:54:29 GMT
• Title: Parallelizing Tree Search with Twice Sequential Monte Carlo
• Authors: Yaniv Oren, Joery A. de Vries, Pascal R. van der Vaart, Matthijs T. J. Spaan, Wendelin Böhmer,
• Abstract summary: 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.
• Score: 7.863528049670872
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Model-based reinforcement learning (RL) methods that leverage search are responsible for many milestone breakthroughs in RL. Sequential Monte Carlo (SMC) recently emerged as an alternative to the Monte Carlo Tree Search (MCTS) algorithm which drove these breakthroughs. SMC is easier to parallelize and more suitable to GPU acceleration. However, it also suffers from large variance and path degeneracy which prevent it from scaling well with increased search depth, i.e., increased sequential compute. To address these problems, we introduce Twice Sequential Monte Carlo Tree Search (TSMCTS). Across discrete and continuous environments TSMCTS outperforms the SMC baseline as well as a popular modern version of MCTS. Through variance reduction and mitigation of path degeneracy, TSMCTS scales favorably with sequential compute while retaining the properties that make SMC natural to parallelize.

Related papers

• Fast Monte Carlo Tree Diffusion: 100x Speedup via Parallel Sparse Planning [63.07406294571171]
  Recently proposed Monte Carlo Tree Diffusion (MCTD) offers a promising solution by combining diffusion with tree-based search.<n>Fast-MCTD integrates two techniques: Parallel MCTD, which enables parallel rollouts via delayed tree updates and redundancy-aware selection; and Sparse MCTD, which reduces rollout length through trajectory coarsening.<n>Experiments show that Fast-MCTD achieves up to 100x speedup over standard MCTD while maintaining or improving planning performance.
  arXiv  Detail & Related papers  (2025-06-11T08:17:40Z)
• 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)
• MCTS-RAG: Enhancing Retrieval-Augmented Generation with Monte Carlo Tree Search [61.11836311160951]
  We introduce MCTS-RAG, a novel approach that enhances the reasoning capabilities of small language models on knowledge-intensive tasks.<n>Unlike standard RAG methods, which typically retrieve information independently from reasoning, MCTS-RAG combines structured reasoning with adaptive retrieval.<n>This integrated approach enhances decision-making, reduces hallucinations, and ensures improved factual accuracy and response consistency.
  arXiv  Detail & Related papers  (2025-03-26T17:46:08Z)
• Monte Carlo Tree Diffusion for System 2 Planning [57.50512800900167]
  We introduce Monte Carlo Tree Diffusion (MCTD), a novel framework that integrates the generative strength of diffusion models with the adaptive search capabilities of Monte Carlo Tree Search (MCTS)<n>Our method reconceptualizes denoising as a tree-structured process, allowing partially denoised plans to be iteratively evaluated, pruned, and refined.
  arXiv  Detail & Related papers  (2025-02-11T02:51:42Z)
• Anytime Sequential Halving in Monte-Carlo Tree Search [1.3820916757781068]
  This paper proposes an anytime version of the algorithm, which can be halted at any arbitrary time and still return a satisfactory result. Empirical results in synthetic MAB problems and ten different board games demonstrate that the algorithm's performance is competitive with Sequential Halving and UCB1.
  arXiv  Detail & Related papers  (2024-11-11T17:49:47Z)
• Comparison of parallel SMC and MCMC for Bayesian deep learning [3.4661537979254655]
  This work systematically compares parallel implementations of consistent (asymptotically unbiased) Bayesian deep learning algorithms.<n>We provide a proof of convergence for SMC$_parallel$ showing that it theoretically achieves the same level of convergence as a single monolithic SMC sampler.
  arXiv  Detail & Related papers  (2024-02-09T04:13:38Z)
• Bayesian Decision Trees Inspired from Evolutionary Algorithms [64.80360020499555]
  We propose a replacement of the Markov Chain Monte Carlo (MCMC) with an inherently parallel algorithm, the Sequential Monte Carlo (SMC) Experiments show that SMC combined with the Evolutionary Algorithms (EA) can produce more accurate results compared to MCMC in 100 times fewer iterations.
  arXiv  Detail & Related papers  (2023-05-30T06:17:35Z)
• 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)
• Variational Combinatorial Sequential Monte Carlo Methods for Bayesian Phylogenetic Inference [4.339931151475307]
  We introduce Vari Combinatorial Monte Carlo (VCSMC), a powerful framework that establishes variational search to learn over intricate structures. We show that VCSMC and CSMC are efficient and explore higher probability spaces than existing methods on a range of tasks.
  arXiv  Detail & Related papers  (2021-05-31T19:44:24Z)
• 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.