Accelerating monte carlo tree search with probability tree state abstraction

Y Fu, M Sun, B Nie, Y Gao - Advances in Neural …, 2023 - proceedings.neurips.cc
Y Fu, M Sun, B Nie, Y Gao
Advances in Neural Information Processing Systems, 2023proceedings.neurips.cc
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 …
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.
proceedings.neurips.cc
以上显示的是最相近的搜索结果。 查看全部搜索结果