Accelerating Monte Carlo Tree Search with Probability Tree State Abstraction

Yangqing Fu, Mingdong Sun, Buqing Nie, Yue Gao
2/12/2026

No official code found. Best implementation: FYQ0919/PTSA-MCTS (16 stars, MIT, last commit 2023-10-21).

Abstract

Monte Carlo Tree Search (MCTS) algorithms such as AlphaGo and MuZero have achieved superhuman performance in many challenging tasks. However, the computational complexity of MCTS-based algorithms is influenced by the size of the search space. To address this issue, we propose a novel probability tree state abstraction (PTSA) algorithm to improve the search efficiency of MCTS. A general tree state abstraction with path transitivity is defined. In addition, the probability tree state abstraction is proposed for fewer mistakes during the aggregation step. Furthermore, the theoretical guarantees of the transitivity and aggregation error bound are justified. To evaluate the effectiveness of the PTSA algorithm, we integrate it with state-of-the-art MCTS-based algorithms, such as Sampled MuZero and Gumbel MuZero. Experimental results on different tasks demonstrate that our method can accelerate the training process of state-of-the-art algorithms with 10%-45% search space reduction.

View on arXivView PDF

Code Implementations(1)

FYQ0919/PTSA-MCTSCommunity56%
MIT

A PyTorch implementation of PTSA-MCTS from [Accelerating Monte Carlo Tree Search with Probability Tree State Abstraction].

160PythonOct 10, 20233 years agoMIT

Similar Papers

Amplifying Exploration in Monte-Carlo Tree Search by Focusing on the Unknown

80% match2024

Strategy Game-Playing with Size-Constrained State Abstraction

79% match1 repo552024

ReZero: Boosting MCTS-based Algorithms by Backward-view and Entire-buffer Reanalyze

78% match1 repo1.6k2024

Binary Search with Distributional Predictions

77% match1 repo2026

Count-based Novelty Exploration in Classical Planning

77% match1 repo2024

Time-critical and confidence-based abstraction dropping methods

77% match1 repo142025

Cite this paper

@article{fu2026accelerating,
  title  = {Accelerating Monte Carlo Tree Search with Probability Tree State Abstraction},
  author = {Yangqing Fu and Mingdong Sun and Buqing Nie and Yue Gao},
  year   = {2026},
  eprint = {2310.06513},
  archivePrefix = {arXiv},
  url    = {https://arxiv.org/pdf/2310.06513},
  journal = {NEURIPS 2023 2023}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2310.06513.svg)](https://codeofpaper.com/paper/2310.06513)

Discussion