Accelerating Monte Carlo Tree Search with Probability Tree State Abstraction

Summary

This paper presents a novel approach called Probability Tree State Abstraction (PTSA) to improve the efficiency of Monte Carlo Tree Search (MCTS) algorithms, which have shown remarkable performance in challenging tasks. The computational complexity of MCTS algorithms is influenced by the size of the search space, and the proposed PTSA algorithm aims to address this issue. The algorithm introduces a general tree state abstraction with path transitivity, which helps in reducing the number of mistakes during the aggregation step. The theoretical guarantees of transitivity and aggregation error bound are also provided. The PTSA algorithm is integrated with state-of-the-art MCTS-based algorithms, including Sampled MuZero and Gumbel MuZero, and experimental results on various tasks demonstrate its effectiveness. The PTSA algorithm accelerates the training process of these algorithms, achieving a search space reduction of 10% to 45%.

Strengths

1. The approach of aggregation considers the entire path, not only a state, is novel and unique. 2. The PTSA algorithm presented in this paper can be applied with any other state abstraction functions mentioned in previous studies, in a general way. 3. The paper provides extensive experimental data. It includes environments such as Atari games, as well as tasks with continuous action spaces like CartPole and LunarLander, and board games like Gomoku. The rich variety of experimental environments demonstrates the effectiveness of the proposed method across various tasks. 4. Integrate PTSA with state-of-the-art algorithms can achieve comparable performance with smaller branching factors. In other words, PTSA provides a more efficient method with less computational cost.

Weaknesses

1. The meaning of probability in PTSA (in Definition 4.3) is not well-defined and requires further clarification. This will be addressed in the Questions section below. 2. There are some errors in the proofs presented. This will be discussed in detail in the Questions section as well.

Questions

1. Why does $v_0.pruning$ do in line 17 in Algorithm 1? Any difference from $S_L.delete(b_j)$. 2. What role does the probability $\mathbb{P}$ in Definition 4.3 play in Algorithm 1?And, how to calculate $\phi$ in line 15 in Algorithm 1? In other words, when does $\phi(b_i)=\phi(b_s)$ hold true? Are both related? 3. In your paper, you mentioned a previous work titled "Monte Carlo Tree Search with Iteratively Refining State Abstractions." That method directly calculates the distance between states and performs aggregation if the distance, denoted as $d(s_1, s_2)$, is below a threshold. This approach differs from the method proposed in your paper, but both aim to reduce the branching factor of MCTS. Have you conducted any experiments comparing your method with the approach mentioned above? I couldn't find any analysis of that method in Table 1 or the experimental section below. Some insight into the reason for this omission should be provided. 4. This paper mentioned “reduce the computation time” with abstraction. My question (or curiosity) is how much overhead the checking operations (in Lines 14 and 15) incur. Note that in line 207 there is a time complexity which is required to be described in more detail, like $\log N_s$. 5. Equation (19) in the appendix is written incorrectly. Need to be fixed. For example, the final $p_{bM}(b_2, b_3)$ should be $p_{bM}(b_1, b_3)$. Also fix some other wrong indices in (19).

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

N.A.

Summary

This paper proposed a novel search algorithm, PTSA, to improve the search efficiency of MCTS. Empirical results show that PTSA can be integrated with Sampled MuZero and Gumbel MuZero and can reduce the original branching factor by 10% up to 45%.

Strengths

The proposed PTSA algorithm can reduce the branching factor of MCTS and improve the computational efficiency of MCTS-based algorithms. The authors also provide both theoretical and empirical analyses.

Weaknesses

* The author claims that the proposed method can reduce the branching factor by 10% up to 45%. However, the result is based on only five Atari games. Based on Figure 3, the aggregation percentage varies across different Atari games. Can these five games represent all Atari-57 games? It would be more convincing to run more Atari games to support the claims. * Moreover, it is unclear for the aggregation percentage on control tasks and Gomoku experiments. Without these experiments, it is inappropriate to claim “reduce branching factor by 10% up to 45%”. * The time complexity of the proposed approach is higher than the original MCTS. It is unclear whether PTSAZero will still improve its efficiency when running under a larger simulation number. Currently, the authors only run “PTSAZero N=18” in Atari experiments. Will “PTSAZero N=30” perform better than “PTSAZero N=18”? * Besides, in the board games such as Gomoku or Go, it is common to run large simulation numbers such as N=400 or N=800 during evaluation. It would be better to provide additional experiments/analyses to demonstrate the scale-up ability for PTSAZero. For example, providing the aggregation percentage/time usage/strength when using different simulation numbers.

Questions

* In Algorithm 1, line 15, if $b_i$ and $b_s$ have different lengths, will their $\phi_{Q_{\alpha}^{psi}}(b)$ be different? In addition, what is the definition for $\phi_{Q_{\alpha}^{psi}}(b)$? Definition 4.3 only shows the probability. * In Algorithm 1, line 17, $v_0$ is root node and $b_j$ is a selection path. what does $v_0$.prunning($b_j$) mean? * In Figure 2, will PTSA get better performance when using a larger simulation (N=30)? Current experiments only used N=18. It would be better to add another experiment with a larger simulation to show the scale-up ability of PTSA. * In the Gomoku experiment, what does the expert opponent stand for? How many simulations are used in the Gomoku evaluation? As Gomoku is a two-player game, why not compare PTSAZero to other methods directly? * line 302: “The winning rates of different methods w.r.t. training time are shown in Figure 4”. Should the range of the win rate be between 0 and 1 in Figure 4? * In Figure 3, it seems that the aggregation percentage varies across different Atari games. Which type of game may have a higher aggregation percentage? Why do you choose these games? Can these five games represent Atari-57 games? Do you have more experiments on other Atari games? * In Atari experiments, “As Gumbel MuZero does not require large simulations for Atari and control tasks”. In fact, Gumbel MuZero improves training efficiency by only using N=2 in Pacman, and the result is comparable to N=50. It would be more convincing to add additional experiments to compare the training efficiency between “Gumbel MuZero N=2” and “PTSAGZero N=2“ in Atari experiments. * In Figure 2 (f), the label of the green curve is “MuZero N=50”, should it be “MuZero N=30”? * Line 17, typo: Muzero -> MuZero. * Figure 2, typo: state-of-art -> state-of-the-art. * Figure 3 is shown after Figure 4. Please fix the order of these figures.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

The authors have addressed the limitations in the paper.

Summary

The paper proposes a novel tree state abstraction function (PTSA) for use during MCTS. The primary contributions of the paper are algorithmic and empirical. The key idea involves aggregating paths in the tree if their Q-values (as probabilities) along the path closely match an existing path with the same parent node. An analysis of the abstraction quality and error bounds are included. Experiments on Atari and Gym environments show that a recent MCTS variant leveraging PTSA outperforms a number of strong baselines. UPDATE: I thank the authors for their detailed response. After reading the other reviews and comments, I'm more inclined to recommend acceptance and have updated my score to reflect that.

Strengths

+ The paper tackles an important problem of accelerating MCTS search. It does so using tree state abstraction. The approach is intuitively clear and is also supported by analysis. + The paper proposes a novel tree state abstraction function based on path transitivity. The abstraction function is based on the difference in the Q values of the nodes (converted to probabilities) in the path. Although important implementation details are not clear to me, the intuition that abstracting entire paths accelerates search makes sense as does the abstraction of only the most recent path during search leading to smaller trees during online search. The paper is accompanied by analysis showing the correctness of the approach and an error bound under certain conditions. Overall, the algorithm seems to have high novelty. + The experiments are conducted on a number of Atari and Gym environments. Sampled MuZero with the proposed abstraction (PTSA) outperforms a number of strong baselines by a significant margin. The implementation seems to work very well. This seems to be a new state of the art in state abstraction for modern MCTS variants.

Weaknesses

- The approach is intuitively clear and seems to perform well empirically, which increases confidence. However, I found the description of the implementation details of Algorithm 1 difficult to follow. Please consider including a more careful description of the implementation in Section 4. The issue is exacerbated by the absence of code. This is currently preventing me from giving the paper a higher score. - For example, the actual implementation of the algorithm in L15 of Algorithm 1 is unclear to me. I expect it to involve Eq 5 with some value of $\alpha$ like 0.7. But Eq 5 returns a real-valued prob estimate for a path pair (b_i, b_s). How is that turned into a boolean value (True / False) in L15? It's probably not real-valued equality. This is a key detail so please explain. - There are a number of other implementation details that are difficult to find or missing. See the questions for examples. - Given that the primary contribution is algorithmic and empirical, I'd have hoped to see the source code included. Reproducibility is going to be challenging without it and since this paper seems to establish a new state of the art, I'd encourage the authors to release their code.

Questions

- I had a number of questions about the exact implementation - What exactly is the implementation of the branching condition of L15 of Algorithm 1? How does it relate to Eq 5 and 6 which is defined as a function taking two inputs (b_i, b_j) and returning a probability? - What exactly is learned during offline learning vs online search? $d, v, p$ are likely learned offline. What about the abstraction function $\phi$? This seems online to me. Correct? - What is $l$ set to in the implementation? How does it value impact performance? - What is the implementation of the pruning function in L17 of Algorithm 1? - How are the legal actions for the abstracted state computed? - What is the size of $S_L$? How was it chosen? How does varying it affect performance? - As described in L346-349, there seem to be a number of choices for the designer to make. These are not clear to me at the moment besides the obvious ones (e.g., $\alpha, N$). Please enumerate what exactly needs to be hand-designed or set manually for a given domain and what can be used off-the-shelf. - Is there a reason to not include code? Will code be included in the final version?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Yes

Summary

To accelerate MCTS, the paper proposed a novel probability tree state abstraction (PTSA) algorithm to improve the search efficiency of MCTS. They define states that are similar by using path transitivity and claim that such a method can have fewer mistakes. According to the results of Atari and Gomoku, the method can be 10% ~ 45% faster.

Strengths

1. The method provides some theoretical guarantee. 2. The experiments take place in many environments. 3. The ablation studies have tried many abstraction functions.

Weaknesses

1. The intuition of the paper is weird. The method required of all states on the paths needs to be similar. However, there are two problems here. First, the V value might be more incorrect at the beginning. Second, even if the V value is correct for the whole path, this method reduces the chance of pruning more nodes. For example, in Atari, agents can reach the exact same state with different paths. Since the environment is MDP, we should merge those two states. 2. It is unknown for the performance when the simulation is higher. The abstract error normally increases when the simulation increase. The method might delete some good paths that can only be identified after numerous simulations.

Questions

1. How do you prune a path from a tree? What will happen to those branches that are on the path? 2. Have you considered abstraction functions that also require the best action should be the same[1]? [1] Are AlphaZero-like Agents Robust to Adversarial Perturbations?

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Stated in the weakness.

Summary

This paper suggests a method of abstracting the state space explored by a Monte Carlo Tree Search (MCTS) algorithm, in order to reduce the complexity of the search. We can create an abstraction of the state space for MCTS by considering an abstraction over entire paths in the tree - two paths of equal length, that start from the same node in the tree, can be aggregated into a single abstract state, thus reducing the search space. The paper proposes to use a probabilistic approach to the abstraction process, using the justification that this enables the algorithm to recover from aggregation errors that it commits early on. The specific probabilistic approach discussed relies on a divergence measure between the distribution of the value functions across the entire two paths, thus merging together with high probability actions that lead to similar distributions of the value function. This abstraction helps mitigate the worst weakness of MCTS - it reduces the large search space. Some theoretical guarantees are provided, as well as several experimental results for different game problems and for control tasks.

Strengths

The paper deals with the very important challenge of improving MCTS techniques. This type of research is applicable in many domains, as this is a well known and well used algorithm. The experimental results looks extensive and well-presented, and are the main strength of the paper. I especially liked the comparison of different state abstraction functions, as it showcases the contribution of the paper in coming up with a specific one that seems to work well. Adding a successful novel approach to a well established algorithm is not a trivial task, and experimental results seem very promising. This seems like a strong enough reason to publish on its own.

Weaknesses

I thought the main weakness of the paper is its readability. I had a tough time understanding the approach and the logic behind it, even though I have some experience with MCTS specifically (though admittedly, it had been awhile). Some more careful attention can be given to notation and explanations. The math in this paper requires close scrutiny and some of the explanations seem to assume a close familiarity with the specifics of MCTS, as well as state abstraction functions. This results in a reduced reading experience and lower comprehension. Some examples: 1. In equation (1) Q is never explicitly defined, figure 1 appears much earlier in the paper than the definition of the probability state abstraction 2. The complex distinction between paths, states and nodes is not explicitly stated, and sometimes ignored - table 1 is referenced during the general RL discussion that has a state notation (s1, s2) but uses a different notation, that is later used for nodes (v1, v2). 3. Some of the notation within Algorithm 1 is never explained (e.g., actions like pruning/delete/add and the usage of a hidden state h). 4. Q* usage is never explained 5. In the explanation after definition 4.3 - encourages nodes that have the same candidate actions with similar value distribution expectations to be aggregated - should that be be encourages paths ? The entire definition seems to be about aggregating paths instead of specific states, but paths that start from the same node. It is fine to delegate some details to referenced works, but a paper should at least succinctly explain its own notations and be as self-contained as possible. I trust these weaknesses in explanations and paper organization can be fixed by the authors.

Questions

1. Are you planning to publish the code you used? 2. Please check your math for some typos - eq. 19 in appendix A.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

1 poor

Contribution

3 good

Limitations

Some limitations are briefly addressed, namely the need for hyper-parameter tuning and manually selecting the underlying abstraction function. I believe another limitation may lie in the added computational complexity of this method.

Official comment

Weaknesses: 1.1 Even when utilizing PTSA, there's potential for incorrect aggregations. Consider sequences (s1, s2, s3, ..., s_n), (s1, s2, s3, ..., s_n-1, s'_n), if v(s_n) is similar with v(s'_n), then PTSA may aggregate them. However, v(s'_n) might be wrong. 1.2 For MCTS, it is acceptable to have two paths leading to the same node (s1->s2->s3, s1->s4->s3) as long as there is no cycle (s1->s2->s3->s1). This approach enables the aggregation of more nodes. 2 You need to compare baselines with PTSA using the same simulation. For example, PTSAZero n=30 looks worse than MuZero n=30 in Pong. Questions: 2 Sorry for not making [1] clear enough. Their main concept is that V can be wrong but will improve after looking forward (evaluating the next state). Let $T(s, a)$ be the transition function. [1] will require $V(T(s_1,a^*_1 )), V(T(s_1,a^*_2 )) , V(T(s_2,a^*_1 )) , V(T(s_2,a^*_2 ))$ to have a similar value. It can be extended from the optimal action to the optimal path.