Accelerating Monte Carlo Tree Search with Probability Tree State Abstraction
This work addresses efficiency issues in MCTS-based algorithms, which are critical for applications like game AI and planning, but it appears incremental as it builds on existing methods with specific optimizations.
The paper tackles the computational complexity of Monte Carlo Tree Search (MCTS) algorithms by proposing a probability tree state abstraction (PTSA) method, which accelerates training by reducing the search space by 10%-45% in experiments with state-of-the-art algorithms like Sampled MuZero and Gumbel MuZero.
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.