Accelerating Monte Carlo Tree Search with Probability Tree State Abstraction
Authors: Yangqing Fu
Ming Sun
Buqing Nie
Yue Gao
Venue: NeurIPS 2023 poster (2023)
Keywords: reinforcement learning
mento carlo tree search
state abstraction

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.

Accelerating Monte Carlo Tree Search with Probability Tree State Abstraction
Ming Sun MoE Key Lab of Artificial Intelligence, Al Institute, Shanghai Jiao Tong University (frank79110, mingsun, niebuqing, yuegao)@sjtu. edu. cn
Yangqing Fu
Buging Nie Yue Gao"
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 influenced by the size the search space. To address this issue, propose novel probability tree state abstraction (PTSA) algorithm to improve the search efficiency of MCTS. 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 integrate it with state-of-the-ar MCTS-based algorithms, such Sampled MuZero and Gumbel MuZero. Experimental results on different tasks demonstrate that method can accelerate the training process of sfate-ofthhe-- algorithms with 10% 45% search space reduction.
the PTSA algorithm, we
Introduction
With the advancement of reinforcement learning (RL), AlphaGo is the first algorithm that can defeat human professional players in the game of Go [I With no supervised learning of expert moves in AlphaGo Zero to restructured self-play in AlphaZero [ until the recent MuZero that conducts Monte Carlo Tree Search (MCTS) in hidden state space with a learned dynamics model [4]. MuZero presents a powerful generalization framework that allows the algorithm learn without perfect simulator in complex tasks. Recently, EfficientZero [S) has made significant progress in the sample efficiency of MCTSS-based algorithms. This development has opened up new possibilities for real-world applications, including robotics and self-driving.
When dealing with complex decision-makin problems, increasing the search depth is necessary to achieve more accurate exploration in the decision space, but this also leads to higher time and space complexity 7] For instance, MuZero trained for 12 hours with 1000 TPUs learn the Go game, and for a single Atari game, it needs 40 TPUs for 12 hours of training 4 One approach to reduce the computation is the state abstraction method, which aggregates states based on a certain similarity measure to obtain a near-optimal policy g 9 I0]. state abstraction is a crucial technique in reinforcement learning (RL) that enables efficient planning, exploration, and generalization [IT].
To reduce the search space of MCTS, previous studies have shown the potential of specific state abstraction techniques [22 3
14 [5]. However, finding the minimum abstract state space in these
studies is an NP-Hard problem 16
To our knowledge, this work is the first to define path transitivity in the formulation of tree state abstraction, which enables the discovery of the minimum abstract space in polynomial time. Additionally, recent MCTS-based algorithms utilize neural networks to
Corresponding author.
Code available at http:///giccccbooooorrr/////////
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

estimate the value or reward of states, which may lead to errors in aggregating states with deterministic state abstraction functions. To address this issue, we proposed probability tree state abstraction function that aggregates states based on the distribution of child node values, which enhances the robustness of aggregation and ensures transitivity.
This paper proposes the probability tree state abstraction (PTSA) algorithm to improve the tree search efficiency of MCTS. The main contributions can be summarized follows: i) A general tree state abstraction is formulated, and path transitivity is also defined in the formulation. ii) The probability tree state abstraction is proposed for fewer mistakes during the aggregation step. iii) The theoretical guarantees of the transitivity and aggregation enror bound are justified. iv) We integrate PTSA with state-of the-art algorithms and achieve comparable performance with 10% 45% reduction in tree search space.
2 Related Work
2.1 MCTS-based Methods
MCTS is a rollout algorithm for solving sequential decision problems [17]. The fundamental idea of MCTS is to search for the most promising actions by randomly sampling the search space, and then expanding the search tree based on those actions [88. The computational bottlenecks arise from the
search loop, especially interacting with the real environment model of each iteration.
Combined with deep neural networks, MCTS- methods have achieved better performance and efficiency in various complex tasks, such as board games (2). autonomous driving [19]. and robot planning 20)_ The model-based algorithm MuZero [4] predicts the environmental dynamics model for more efficient simulation. Based on MuZero, EfficientZero 5 is proposed for the training with limited data, which achieves super-human human performance on Atari 100K benchmarks. However, both MuZero and EfficientZero require high computational consumption when dealing with complex action spaces. To address arbitrarily complex action spaces, the sample-based policy iteration framework 21 is proposed. Sampled MuZero extends MuZero by sub-sampling small fraction of possible moves and achieves higher sample efficiency with fewer expanded actions and simulations. The experimental results show that planning over the sampled tree provides near-optimal approximation [21]. To further reduce the number of simulations, Gumbel MuZero utilizes the Gumbel-Top Top-k trick to construct efficient planning (2)
2.2 State Abstraction
State abstraction is aimed reducing the complex state space by aggregating the similar states [ The original state space S can be mapped into a smaller abstract state space Sy. by state abstraction. By grouping similar states together, state abstraction can help identify patterns and regularities in the environment, which can inform more effective decision-making
There are two main challenges when applying state abstraction RL problems. The first challenge to decrease the value loss between and Sg. With bounded value loss, the approximate state abstractions allow the agent to learn near-optimal policy with improved training efficiency [1]] 24]
The second challenge is to compute the smallest possible abstract state space, which is proven that the computational complexity is NP-hard [16]. The transitive state abstraction [1] is defined to efficiently compute the smallest possible abstract state space. However, most transitive state abstractions with deterministic predicates have low fault tolerance. To improve the robustness of aggregation, we measure the abstraction probability of the state pairs based on the expected value distributions. In addition, some previous studies have analyzed and discussed some specific state abstractions in tree structure [12] 3 14 [5). but there is no formal definition and analysis for general tree state abstractions. To our knowledge. PTSA is the first method that defines a general formulation of tree state abstractions for deep MCTS-based methods and analyzes the transitivity and aggregation error under balanced search.
3 Preliminaries
In this section, the prerequisites for our proposed method are introduced. We consider an agent learning in a Markov decision process (MDP) represented as (S, R, T, 7), where S denotes the

---

Table 1: Some previous state abstraction functions
23
29
Abstractions
Predicate
Transitive
dg- de- oq* oq.
az A (81) V*
yes
oi 0z (81)
V (#2) (*2)
S
no
max, Q M ($1,4)
Qir M ($2,
= 0
yes
max,
(Q M (81,a)
Q (82, a)
S
no
V ("(ara))
(+2
yes
state space, A denotes the action space, R: x A denotes the reward function, T x A + P(S) denotes the transition model, and y É [0, 1] is the discount factor. The goal is to learn a policy T + ((A) that maximizes the long-term expected reward in the MDP.
3.1 Monte Carlo Tree Search
MCTS-based algorithms typically involve four stages in the search loop: selection, expansion, simulation, and backpropagation. After N iterations of the search loop, MCTS generates a policy based on the current states. In the selection stage of each iteration, an action is selected by maximizing over UCB. Notably, AlphaZero [ and MuZero 4 two successful RL algorithms developed based on a variant of Upper Confidence Bound (UCB) 24 called probabilistic upper confidence tree (PUCT) [25). have achieved remarkable results in board games and Atari games. The formula of PUCT is given by Eq. (T)
V E.,N(s.) 1+ N+
a² argmax, Q(s, a) + c((s) a(s.a)
(I)
where is is the index of iteration, Q(s, a) denotes the value of action in state c(s) is hyperpa- rameter for balancing the value score with the visiting counts N(s, a), and P(s, a) is the policy prior obtained from neural networks.
3.2 State Abstraction in RL
State abstraction methods aggregate similar environment states compressed descriptions (26). which simplify the state spaces and significantly reduce the computation time (27] The state abstraction type is formulated as below [10]:
Definition 3.1. (State Abstraction Type) A state abstraction type set of functions o + S related to fixed predicate on state pairs: pM S x S + {0, 1]. When function ø aggregates the state pair ($1, 82) in MDP M, the predicate PM must be true: Φ (s1) (82) - PM (81, 82).
The conditions for state abstraction usually strict, which may cause insufficient compression in state spaces. Recent studies have shown that transitive state abstraction (23] is computationally efficient and achieve near-optimal decision-making, which is defined as:
Definition 3.2. (Transitive State Abstraction) For given state abstraction á with predicate pm, if V(81, 82, 83) E S satisfies [pM (81, A PM (82, 83)] - PM (81, 83), the state abstraction & is a transitive state abstraction.
Some previous state abstraction functions shown in Table which aim to abstract similar states in general reinforcement learning methods. For instance, abstraction d.. considers the optimal actions and values of states, which is also widely studied in MCTS-based methods (28).
Transitive state abstraction can reduce the computational cost of finding the smallest abstract state space. As shown in Table [ most approximate state abstractions are not transitive. However, transitivity is challenging to MCTS-based methods due the tree structure. MCTS, a path may contain multiple states, so it is necessary to derive the transitivity of the path from the transitivity of the states. Finding the smallest abstract space in the search tree becomes an NP-hard problem if the state abstraction function lacks transitivity in the path.

---

PTSA-MCTS
In this section, introduce the proposed probability tree state abstraction (PTSA) al- gorithm, which improves the tree search efficiency for MCTS. As described in Fig- ure I
Root
Selection
II. Expansion (
PTSA algorithm improves the search efficiency of MCTS in two aspects: one reducing the search space by abstract- ing the original search space, and the other finding the smallest abstract space effi- ciently by transitive probability tree state abstraction &o The organization of this section as follows: Subsection 4.1 gives the formulation of general tree state abstrac- tion. Subsection presentt our proposed probability tree state abstraction. Sub- section [.3 presents the PTSAZero algo- rithm, which integrates PTSA with Sam- pled MuZero, and more information can be found in the Appendix. Subsection [.4 provides the proofs of transitivity tree structures and bounded aggregation error under balanced exploration.
III. Simulation
G.b
IV. Backpropagation
V. Abstraction: (b,, by) bø = 4 0/
Abstracted Paths
Asgregated Paths
b,
b
Transitive
Figure 1: The overview structure of PTSA algorithm. The original tree search space in MCTS is mapped into smaller abstract space efficiently by transitive proba- bility tree state abstraction QQ
4.1 Tree State Abstraction Formulation
The formulation of our tree state abstraction is provided with general abstraction operator for the tree structure, which can be utilized with arbitrary state abstraction types. To facilitate the derivation of theorems and properties, the definition of tree state abstraction is given: Definition 4.1. (Tree State Abstraction)
For given tree, V and B denote the node set and path set respectively. A tree state abstraction is function Ø V Va & B B& with node predicate PoM and path predicate p&Mr on the sibling path pair:
Poas x V + {0.1}:
Pbas B3 x B ~ {0,
In the tree structure, path is sequence of nodes and node denotes the representation of the corresponding state. The path and node predicates abstract corresponding states of the path and node respectively. For given path pair (b,) with the same length 7, the predicate on this path pair be decomposed as:
PBM (b), b2)
(u ( A ..... Poas Pors(o (07-1 o/21)
where of 11 1,.... 1) is the i-th node of path b with length 1. When function & aggregates the path pair (b1, b2) in MDP M, the predicate pas must be true:
(b1 (b2) Post (b),b)),
and path and path b2 belong to the same abstract cluster.
The tree state abstraction is applied to two search paths of equal length that start from the same parent node. This ensures that each node along the paths has corresponding potential abstracted node, while preserving the Markov property after aggregation. For instance, the path pair (bı, b2) from different parent nodes Va, Ub can not be aggregated, which violates the Markov property in the state transitions ca e +... 1 and t. 2/² - 0211
Previous studies have proven that tree state abstraction can be an efficient approach to reducing branching factors in MCTS [1, 27 14]. However, finding the smallest abstract state space is an NP-Hard problem in the previous studies 16). Following the definition of transitive state abstraction
define the path transitivity in the tree state abstraction formulation:

---

Definition 4.2. (Path Transitivity) For a given tree state abstraction 6 with predicate РbM if v(b), b2, by) B satisfies [Pba (b), b2) A PbM (b2, by)l has path transitivity.
Pbи (b,, by), the state abstraction
The definition of path transitivity extends the equivalence of state abstraction in tree state space and general RL state space. Tree State abstraction for MCTS maps the original path space B into the abstract path space Bg. For non-transitive tree state abstraction, it is necessary to determine whether all possible path pairs belong the same abstract cluster, and paths may appear repeatedly in path pairs, which requires a massive computation cost to obtain the smallest B
4.2 Probability Tree State Abstraction
State-of-the-art MCTS-based algorithms utilize neural networks to estimate the value or reward of states. However, hard constraints from previous state abstractions can lead to incorrect aggregation during the early training stage. To reduce the probability of states being mapped the incorrect abstract space due to bias in network prediction, a novel probability tree state abstraction Φox is proposed in this work:
Definition 4.3. (Probability Tree State Abstraction Φoz) PoM and path predicate p&M, the aggregation probability of doz is defined as:
) For given a E [o, 1] with node predicate
P(pess(e b2) = 1} & P( (b1) 62x (b2)) = II (1 PI o/ =));;
(5)
P(PuM . .2/²) exp(Q-
= 1} - a(1 DJs (o
a))))
(6)
where at)) = Ejea EyeA (va)) and Das the -haannnh divergence.
& encourages nodes that have the same candidate actions with similar value distribution expecta- tions to be aggregated. Using Censen-Shamme divergence instead of Kullback-Leibler divergence is more advantageous for numerical stability during computation.
4.3 Integration with Sampled MuZero
Our proposed PTSA algorithm can be integrated with state-of-the-art MCTS-based algorithms. The integration includes two main components: offline learning and online searching. Offline learning involves updating the dynamics, prediction, and value networks by sampling trajectories from buffer. Online searching involves interacting with the environment to obtain high-quality trajectories, similar Soorithn[shhwe how PTSA can be integrated with Sampled MuZero [21] during the searching stage. Compared with the original Sampled MuZero, lines 4-12 describe how to collect all searched paths and update the corresponding node values during the multiple iterations. Lines 13-19 describe how tree state abstraction reduces the search space efficiently. Based on Theorem 4.4 abstracting the most recently searched path is enough to find the smallest abstract space for bCsS- methods. (bb)) ((bx)) returns boolean value, where "true" denotes aggregating b; and bg. This boolean value is determined by calculating the probability ((b(b;)) = x(b.)) based on Eq. and Eq. 6
to MuZero algorithm.
Sr. list records the searched paths in the current search tree, Sy.delete(b) and addddd( refer to removing and recording path in Sr, respectively. The pruning(b;) action denotes removing unique nodes of path bj compared to the other abstracted path in the search tree. denotes the hidden feature of the original real environment state. Algorithm can be generalized to all tree state abstraction functions by replacing & The selection, expansion, and backpropagation steps are the same with Sampled MuZero (21). To maintain the balance of Ns,, b). the visit count of the aggregate node needs to be accumulated into the corresponding state pair. Furthermore, aggregated nodes with different sets of legal actions could lead to unnecessary exploration of invalid or irrelevant parts of the search space, slowing down the search and potentially reducing the quality of the results. In our implementation, we ensure that the aggregated node only expands legal actions for the abstracted state, thus avoiding any negative impacts caused by illegal actions. An undoing aggregation operation has been considered in I As the value estimation becomes more accurate, some previously aggregated
5

---

Algorithm PTSAZero
1: Input: Root node Vo. dynamics network de,
11:
Expand child nodes: v v.expand h,r) Backpropagation along path by
policy network Pa. value network Va
12:
2: Initialize searched-patte list St. {[vo]}
13:
Sr.ad (b.)
3: for n = 0, 1, 2... do
14:
for b, E Sr do
4: Reset v No. searching branch b, [v]
15:
if ΦQx (b.)
ooz (b,) then
5: Selection with PUCT
16:
by = arg min(b.
6: Add child e' into b.. v =
bE(b,.b,)
7: Update hidden state and reward r:
17:
to.pruning S Sr.delet)(b))
du(u.parent.h, 9: Predict value V and policy и.:
8:
18: end if
19: end for
V, (al...h)ppss.....
20:
end for
nodes in the search will no longer be aggregated in the new search. With each new timestep. the value of the search nodes is re-evaluated, leading to changes in the following aggregation results.
In Sampled MuZero algorithm, the computational complexity of simulating from the root node be expressed O(N, (O(S) + O(D) + O(P) O(V)). N, represents the number of simulations, and (S) denotes the computational complexity of the simulation process, which includes selecting children, expanding, and backpropagating. Additionally, O(D), O(P), and O(V) denote the computational complexities of the dynamics network d9, policy network pO, and value network Vo, respectively. The dynamics network predicts the next hidden state and corresponding reward based on the current hidden state and action a. In Algorithm [ the time complexity is given by O(N, (logiA) N₂ Cp O(S) + O(D) O(P) + (VV)) under balanced search. The balanced search term log N, cp accounts for the exploration of child nodes, where |AA represents the number of possible actions, and ep is constant controlling exploration. Since tree state abstraction reduces the branching factor, our algorithm enhances the efficiency of selecting child nodes with a smaller Ng. The specific computational time of different methods can be found in Appendix F.
||
4.4 Theoretical Justification
Following the formulation of the tree state abstractions, the theoretical analysis is conducted from the following perspectives: i) Transitivity; ii) Aggregation error.
4.4.1
Transitivity
To abstract tree paths efficiently, next result shows the relationship between path transitivity and node transitivity:
Theorem 4.4. For V(v1, U2, vz) V and (b), b2, by) E B:
[[ры (bi, ba) A Paas (b2, ba)l = PbM (b1, by -
[[ (v), U2) A Poar (22, [z)] Pons (V), 0g)]-
Proof. See Appendix A.
Theorem 4.4 indicates that path transitivity is sufficient and necessary condition for node transitivity. Compared with the previous transitive state abstractions, the proposed 6qx is also transitive for paths as the following proposition given:
Proposition 4.5. The probability of transitivity for &ax can be computed as:
P (Pbar (bi, bz) A PaM (b2, ba) = Pba ba))] =
P P( (b.) dog (b)))P((gg (bz) dog (bs (ba)) (b:) = 60g (ba))+
(8)
p( (b)) = og (by) (bb))) (b2) = 6oz (ba P( (b1) = ozz
Proof. See Appendix B.
The computational complexity of computing the smallest possible abstract state space for transitive state abstraction is ([S]2... ep) [1], where ep denotes the computational complexity of evaluating for given state pair.

---

4.4.2 Aggregation Error Bound
Most approximate state abstractions are con-transitive since their cumulative aggregation value errors are unbounded. We define the aggregation error E in path set as:
E
| b
Σ
4 (b2))
(9)
For instance, consider commonly used approximate state abstraction éq:
PM ($1, 52) - max (Q1 ($1, a) Qir (52, a)l S.
(10)
with the value loss L = V' (s) o (s) S (1-7)². The aggregation error can be bounded as GeRman if two paths of length are abstracted. (1-7)*
In Algorithm the aggregation times must be less than the current branching factor The next result extends to the general tree state abstractions in Algorithm[] The path transitivity implies that the abstracted paths present in the current B& must belong different abstract clusters, which can give the following theorem:
Theorem 4.6. Considering a general tree state abstraction & with a transitive predicate p(Cs S C). the aggregation enror in Alg. 7 Junder balanced search is bounded as:
E (Ng 1)C.
(11)
If predicate plCs S () is not transitive, the aggregation error is bounded as:
E < (LA) 1) 10g 1)C.
(12)
Proof. See Appendix C.
Theorem 4.6 provides theoretical guarantee for finding the smallest B& within aggregation error bound in Algorithn[[] At the same time, this theorem also points out that the transitivity has an important effect the structure: the size of the action space |A] increases, the aggregation error upper bound for transitive tree state abstraction will decrease, while the upper bound for non-transitive state abstraction will increase.
5 Experiments
In this section, experiments focus on tree state abstraction for computational efficiency improvement. Firstly, PTSA is integrated with state-of-the-ard MCTS-based RL algorithms Sampled MuZero and Gumbel MuZero and evaluated on various RL tasks with 10 seeds. The aggregation percentages are also evaluated, which reflects the search space reduction in different tasks. In addition, the comparison between probability tree state abstraction and other state abstraction functions is also conducted.
5.1 Results on Performance
To demonstrate the improvement in computational efficiency, the PTSA is integrated with Sampled MuZero in Atari and classic control benchmarks, as well as with Gumbel MuZero in the Gomoku benchmark. The performance is compared against several MCTS- RL algorithms, including (i)
MuZero 4 (ii) Sampled MuZero (21). (iii) EfficientZero [5], (iv) Gumbel MuZero (22
5.1.1
Atari
Atari games are visually complex environments that pose challenges for MCTS- based algorithms{4] The results for each benchmark and the normalized result are shown in Figure 2 and the shaded intervals represent the standard deviation of the performance across the different random
30].
The maximum branching factor is less than |Al and [Å] in MuZero and Sampled MuZero respectively, where À the sampled action space
7

---

Tima-Feluam A iinn-anndof wun.kkkkl
Thne Returtt Freeway mhdFrameskp
Bubue lide
Tipe Rdtu
Time
Aoanin FP Eiees
Tmedmini
Timelmn)
(a) Alien
(b) Boxing
(c) Freeway
Time Reaur: Pong runttFrrnnsskpp
Time Return Tennis mameeeeeeeee
Timre Ruturtc Norallzadd Atari Resuls
Thoe Ream
bork
Tir
Timemmn)
Time
(d) Pong
(e) Tennis
(f) Normalized Score
Figure 2: Experiments results on five Atari games (10 seeds) with a normalized score plot. Sampled MuZero with PTSA (PTSAZero) is compared with three state-of-the-art MCTS-based methods:
MuZero 4. Sampled MuZero (SMuZero) [2I], and EfficientZero [5]. The tasks include Alien, Boxing, Freeway, Pong, and Tennis. N denotes the number of simulations. The x-axis is the training time, and the y-axis is the episode return w.r.t training time.
seeds. As Gumbel MuZero does not require large simulations for Atari and control tasks, we only compare its performance in the Gomoku game. When the simulation times N 18, MuZero and Sampled MuZero fail to converge within the maximum training time in some tasks. Since the search space of MCTS is mapped into the abstract space with smaller branching factor, PTSAZero (a 0.7) can converge rapidly with fewer simulations. Although EfficientZero improves the sampling efficiency of MuZero, the increased complexity of the network entails more time to converge with the same computational resources. EfficientZero is tested with different simulation times, and the best computed by Snorm = (Sagent (msnn)(Smaa - 8 Smin). ). and the normalized time is computed by foom (tagent tmin)/ (fmaz fmin). The experiment results Atari benchmarks indicate that Sampled MuZero with PTSA can achieve comparable performance with less training time. For MuZero-baser algorithms which require massive computational resources and parallel abilities, PTSA provides a more efficient method with less computational cost.
in time efficiency with N 30 is shown. The normalized score is
5.1.2 Control Tasks
In the comparison experiments conducted on Gym benchmarks, including classic control and box2d tasks, certain modifications are made to increase the tree search space in control tasks. Specifically, the action spaces of CartPole-vis v0 and LunarLander-v? are discretized into 100 and 36 dimensions, respectively. This discretization of the action space necessitates LICTS-basel algorithms to run a larger number of simulations and increases the number of sampled actions in Sampled MuZero.
For both SMuZero and PTSAZero, the number of sampled actions is set to 25 CartPole-vD and 12 in Lunarl 2. F Figure3]emmonstratee demonstrates that PTSAeero exhibits superior computational efficiency compared to other methods. In the LunarLander-v2236 task, PTSAZero significantly improves the training speed of MuZero by factor of 3.53. These results highlight the effectiveness of PTSAZero in enhancing the efficiency and performance of MuZero-based algorithms various control tasks.
5.1.3 Gomoku
Gomoku is classic board game with multi-step search, where the agent is asked to beat an expert opponent on the 15 x and 19 19 boards. Gumbel MuZero replaces heuristic mechanisms in original MCTS algorithms for smaller number of simulations [22]. In board game tasks, we integrate PTSA algorithm with Gumbel MuZero: tree state abstraction Φ is utilized to reduce the search space, as deseribed Algorithm | The observation the Gomoku task 2-dimensional matrix describing the distribution of the pieces, and the number of sampled actions for SMuZero,
8

---

Time-Ratum G5mokut5at5-v0
Time Wodeer
Video Wed5
(M bec begs
se13
Madio
Alte bing
Timeminn)
Timelnaa)
1003 100 -99 190 200
(a) CartPole
(b) Lunarlander
(c) Gomoku- 15 15x
(d) Gomoku-199
Figure 3: Experiment results of Gym and Gomoku benchmarks (10 seeds). PTSAGZero denotes the
Gumbel MuZero with P7SA algorithm.
Aggnegetton Percentage
40%
50%
Fang
Tonnis
Aggregation Parcentage: Atari
Aggregatinn Percentage
40%
50%
Aggregation Percentage: Gomoku & Control
Gom0ku19x10
Gumoku15ct5
Corpale
Boodng
30%
30%
20%
20%
10%
0K
0K
50K
100K
125k 150k
175K
200k
25k
50k
7:5k
100k
125k
150K
175k
200k
Training Steps
Training Steps
(a) Atari
(b) Gomoku & Control
Figure 4: The aggregation percentage on paths during the training process on Atari, Control, and Gomoku tasks varies the network parameters are updated.
Gumbel MuZero, and PTSAGZero is 30. The training returns of different methods w.r.t. training steps shown in Figure where value of represents win and represents loss. The results demonstrate that Gumbel MuZero can speed up the training process of Sampled MuZero, and PTSA can provide incremental improvement of Gumbel MuZero. In the Gomoku-19 19 task, despite accelerating the convergence speed of the original algorithms, PTSA does not significantly improve the optimal performance of the algorithms. Experimental results also show that MuZero-based algorithms require a larger number of simulations to learn an effective policy due to the increased size of the action space.
5.2 Search Space Reduction
To analyze the abstracted tree search space, Figure 4 shows the aggregation percentage (the average proportion of aggregated paths) during the training process of PTSAZero on Atari, Control, and Gomoku tasks. Results demonstrate that tree state abstraction reduces the original branching factors by 10% up to 45%. As the network parameters are updated during the training process, the aggregation percentage tends stabilize. As the training progresses towards convergence, the aggregation percentage decreases from 23.7% to 8.1% in the Freeway task, while in the Gomoku 19x19 task, increases from 10.1% 27.8%. The trend of the aggregation percentage is influenced by the initialization of network and the initial values for the nodes. The converged aggregation percentage may vary depending on specific algorithm parameters and task environments, and does not imply certain range of branching factors for all tasks. Each task has unique characteristics and complexities, which can influence the effectiveness of different abstraction functions. It should be emphasized that a larger reduction in the state space does not guarantee improved training efficiency. While higher aggregation percentage indicates greater reduction in the search space, the aggregation quality of the abstractions also determines the impact on training efficiency. Improving the accuracy and quality of tree state abstraction during the training process is future challenge that deserves further research. Furthermore, since the search space of MCTS is reduced by tree state abstraction, the search depth of PTS ATSAo deeper than that of SMuZero with the same number of simulations. More results of search depth can be found in Appendix F.

---

Table 2: Speedup comparison of PTSAZero with different state abstraction functions. where Abs denotes the different tree state abstraction functions (the notations are shown in Table J. All state abstraction functions are evaluated under the same number of simulations and sampled actions.
Abs
Pong
Boxing
Freeway
Tennis
CartPole
Lunarlander
Acrobot
Average
Oa- 2.35=0.44
1.8+0.34
2.44=0.46
1.59+0.3
1.96+0.37
3.03+0.57
2.11=0.4
2.18#0.44
2.75+0.52
1.7740.33
2.31=0.43
1.44a0.27
2.040.38
2,9340.55
1.61+0.30
2.12+0.53
og-
2.29+0.43
2.11+0.4
2.47=0.46
1.82+0.34
1.6440331
1.8340334
1.9400377
2.00+0.26
3.01
1.9540.39
2.52=0.49
2.22=0.44
1.7440.35
3.1340.61
2.01+0.40
2.37+0.50
002
2.8120.55
1.8440.37
2.4520.48
2.0240.4
2,44+0.48
3.1940.62
1.9140.38
2.38
1.25#0.19
2.00#0.21
2.81
1.92#0.17
2.14+0.10
3.53+0.31
2,29+0.35
2.5620.39
5.3 Comparison with Other State Abstraction Functions
We compare the effectiveness of our proposed probability tree state abstraction with other state abstraction functions on Atari and gym benchmarks by integrat- ing them into PTSA algorithm. Referring to the speedup evalua- tion method in Gumbel MuZero [22]. Table Table[]show; shoows the speedup of PTSAAerr with different state abstraction functions compared to the Sampled MuZero. The specific usage and properties of other state abstraction functions can be found in previous works 29]. We adjusted hyper- parameters for different state ab- straction functions and selected the best values (e and d set to 0.5 and 0.2, respectively). The results demonstrate that the pro- posed probability tree state ab- straction ΦQ_ v can achieve better speedup performance on average compared other state abstrac- tion functions. To evaluate the robustness of & PTSAZero with different state abstraction functions with N = 10 is compared in the Pong task. As shown in Figure 5 SMuZero and MuZero can not learn an effective policy, and PTSAZero with o6- and da may aggregate incorrect states, which leads to decrease in performance. We also find that the state abstraction function d,- and ΦQ- have strict requirements for the abstract conditions, resulting in small search space reduction ( 11.5% and 2.8% respectively). Compared with other state abstraction functions, &gg can abstract the original search space more accurately and robustly, thus accelerating the training process.
Episode-Retur: Pong-ramNoFrameski.v4
MuZoro N-10
SMuZere Neto
PTSAZwn
PTB/2oro &6 Neto
PTBAZero de Nito
Episode Return
10
PTBAZoro d6- N-to
PTBAZero dup hirt dor
500
1500
2002
Episode
23
Figure 5: Results of PTSAZero with different state abstraction functions in the Pong task when N Some state abstraction functions cannot accurately abstract the search space with a small number of simulations.
Conclusion
This paper introduces PTSA algorithm for improving the computational efficiency of MCTS-based algorithms. For efficient abstraction in tree search space, we define path transitivity in the formulation of tree state abstraction. Furthermore, we evaluate that the proposed probability tree state abstraction has a better performance compared with previous state abstraction functions. The experimental results demonstrate that PTSA can be integrated with sfate-of-the art algorithms and achieve comparable performance with 10% 45% reduction in tree search space. However, the main limitation of the proposed method that the parameters some state abstraction functions need to be manually designed to obtain more accurate abstract state space. Furthermore, selecting appropriate state abstraction function based on the characteristics of the state space and transition model also potential challenge. Further research will be conducted to address these issues for better performance.
10

---

7 Acknowledgements
This work was supported by the National Natural Science Foundation of China (Grant No. 92248303 and No. 62373242), the Shanghai Municipal Science and Technology Major Project (Grant No. 2021SHZDZX01102, and the Fundamental Research Funds for the Central Universities.
References
[1] David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driess- che, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mas- tering the game of go with deep neural networks and tree search. nature, 529(7587):484-485) 2016.
[2] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, al. Mastering the game of go without human knowledge. nature, 550(7676):354-3555 2017.
[3] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. Mastering chess and shogi by self-play with general reinforcement learning algorithm. arXiv preprint arXiv:1712.0181. 2017.
[4] Julian Schritwweser,, loannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Si- mon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, al. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588(7839):604-6))) 2020.
[5] Weirui Ye, Shaohuai I Liu, Thanard Kurutach, Pieter Abbeel, and Yang Gao. Mastering atari games with limited data. Advances in Neural Information Processing Systems, 34:25476-25488, 2021.
[6] Yuxiang Sun, Bo Yuan, Yongliang Zhang, Wanwen Zheng, Qingfeng Xia, Bojian Tang, and Xianzhong Zhou. Research on action strategies and simulations of drl and mets- based intelligent round game. International Journal of Control, Automation and Systems, 19()):98442998, 2021.
[7] Debin Zhao, Zhengyuan Hu, and Yinjian Yang. An mets-based recommender system for education complex. In 2022 International Conference on Machine Learning and Knowledge Engineering (MLKE), pages 323-326. IEEE, 2022.
[8] Sultan Javed Majeed and Mareus Hutter. Performance guarantees for homomorphisms beyond markov decision processes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 7659-7666, 2019.
[9] Marcus Hutter. Extreme state aggregation beyond markov decision processes. Theoretical Computer Science, 650:73-91, 2016.
[10] David Abel, Dilip Arumugam. Lucas Lehnert, and Michael L Littman. Toward good abstractions for lifelong learning. Proceedings of the NIPS workshop on hierarchical reinforcement learning, page 92, 2017.
[11) David Abel, Dilip Arumugam, Lucas Lehnert, and Michael Littman. State abstractions for lifelong reinforcement learning. In International Conference on Machine Learning, pages 10-19. PMLR, 2018
[12] Jesse Hostetler, Alan Fern, and Tom Dietterich. State aggregation in monte carlo tree search. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 28, 2014.
[13] Aijun Bai, Siddharth Srivastava, and Stuart Russell. Markovian state and action abstractions for mdps via hierarchical mets. In IJCAI, pages 3029-3039, 2016.
[14] Samuel Sokota, Caleb Y Ho. Zaheen Ahmad, and J Zico Kolter. Monte carlo tree search with iteratively refining state abstractions. Advances in Neural Information Processing Systems, 2021.
[15] Alexander Dockhorn, Jorge Hurtado-Grueso, Dominik Jeurissen, Linjie Xu, and Diego Perez- Liebana. Game state and action abstracting monte carlo tree search for general strategy game-playing. In 2021 IEEE Conference Games (CoG), pages 1-8. IEEE, 2021.
11

---

[16]
Eyal Even-Dar and Yishay Mansour. Approximate equivalence of markov decision processes. In Learning Theory and Kernel Machines, pages 581-594. Springer, 2003.
[17] Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[18] Cameron Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter Cowling. Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and Al in games, 4(1):1-43, 2012.
[19] Jienan Chen, Cong Zhang, Jinting Luo, Junfei Xie, and Yan Wan. Driving maneuvers prediction based autonomous driving control by deep monte carlo tree search. IEEE transactions on vehicular technology, 69(7):7146-715x 2020.
[20] Julian Schrittwieser, Thomas Hubert, Amol Mandhane. Mobammadamin Barekatain, Ioannis Antonoglou, and David Silver. Online and offline reinforcement learning by planning with learned model. Advances in Neural Information Processing Systems, 34:27580-27591, 2021.
[21] Thomas Hubert, Julian Schrittwieser, loannis Antonoglou, Mohammadamin Barekatain, Simon Schmitt, and David Silver. Learning and planning complex action spaces, In International Conference on Machine Learning, pages 4476-4486. PMLR, 2021.
[22] Ivo Danihelka, Arthur Guez, Julian Schrittwieser, and David Silver. Policy improvement by planning with gumbel. In International Conference on Learning Representations, 2022.
[23] David Abel, David Hershkowitz, and Michael Littman. Near optimal behavior via approximate state abstraction. In International Conference on Machine Learning, pages 2915-22 2923.2 PMLR, 2016.
[24] Sylvain Gelly and Yizao Wang. Exploration exploitation in go: Uct for monte-carlo go. In NIPS: Neural Information Processing Systems Conference On-line trading of Exploration and Exploitation Workshop, 2006.
[25] Christopher D Rosin. Multi-armed bandits with episode context. Annals of Mathematics and Artificial Intelligence, (1):):203 230, 2011.
[26] David Andre and Stuart Russell. State abstraction for programmable reinforcement learning agents. In Aaai/iaii, pages 1 125, 2002.
[27] Ankit Anand, Ritesh Noothigattu, Parag Singla, al. Oga-uct: On-the-go abstractions in uct. In Twenty-Sixth International Conference on Automated Planning and Scheduling, 2016.
[28] Li-Cheng Lan, Huan Zhang, Ti-Rong Wu, Meng-Yu Yu Tsai, Wu, Cho-Jui Hsieh, et al. Are alphazero-like agents robust to adversarial perturbations? Advances in Neural Information Processing Systems, 35:1 1121112211111 1240, 2022.
[29] Lihong Li, Thomas Walsh, and Michael Littman. Towards unified theory of state abstraction for mdps. In AI&M, 2006.
[30] Weirui Ye, Pieter Abbeel, and Yang Gao. Spending thinking time wisely: Accelerating mets with virtual expansions. arXiv preprint arXiv:2210. 12628, 2022.
[31] Philipp Moritz, Robert Nishihara, Stephanie Wang, Alexey Tumanov, Richard Liaw, Eric Liang, Melih Elibol, Zongheng Yang, William Paul, Michael Jordan, et al. Ray: A distributed framework for emerging {AI) applications. In 13th USENIX Symposium Operating Systems Design and Implementation (OSDI 18), pages 561-577, 2018.
12


Reviews:
[{"review_id": "UZAI8UlmNK", "reviewer": "Reviewer_CrLf", "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. ", "questions": "1. Are you planning to publish the code you used? \n2. Please check your math for some typos - eq. 19 in appendix A.\n", "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. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "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. \n\nThe 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. \nSome examples: \n1. In equation (1) Q is never explicitly defined, figure 1 appears much earlier in the paper than the definition of the probability state abstraction \n2. 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). \n3. 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). \n4. Q* usage is never explained \n5. 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. \n\nIt 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. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your uplifting review and valuable feedback. We appreciate your comments and would like to address them below.\n\n**Weaknesses:**\n\nThanks for your feedback on the paper's readability. We will include more clear and coherent explanations of our method to improve the readability.\n\n1. $Q(s, a)$ denotes the value of action $a$ in state $s$. We will explicitly define all variables and concepts used in the final version. Moreover, we will revise the paper to ensure that the definition of the probability state abstraction is presented before Figure 1. \n2. We will provide more clear and explicit definitions for the concepts of paths, states and nodes in the final version: A path is a sequence of nodes in the search tree; A node in the search tree denotes the representation of the corresponding state. According to your advice, we will use the more general state notation $s$ as the input to the abstraction function in Table 1.\n3. We apologize for not providing a clear explanation of the pruning/delete/add actions in the paper. We have provided more detailed explanations of the actions and notation used in Algorithm 1:\n$S_L $ is a list that records the searched paths in the current search tree. $S_L.delete(b)$ and $S_L.add(b)$ refer to removing and recording path $b$ in $S_L$ respectively. The $pruning(b_j)$ action denotes removing unique nodes of path $b_j$ compared to the other abstracted path in the search tree.  $h$ denotes the hidden feature of the original real environment state, which is employed to prevent MCTS from interacting with the actual environment during simulation in MuZero.\n\n\n4. $Q*(s,a)$ denotes the value of optimal action in state $s$.\n5.  We appreciate and agree with your opinion that using \"path\" instead of \"state\" is more appropriate. We will make the necessary changes in the final version.\n\n**Questions:**\n\n1. We will release our code upon acceptance, and also conduct further research to explore how different state abstraction functions can be better tailored to fit the characteristics of the environment. We hope that this research will help to enhance the performance and applicability of our method in a wider range of applications.\n2. Thanks for your careful review. We have corrected the typos in Appendix Equation (19):\n  \\begin{equation}\n  p_{bM}\\left(b_{1}, b_{2}\\right) \\wedge p_{bM}\\left(b_{2}, b_{3}\\right)\n  = p_{vM}\\left(v_{1}, v_{3}\\right) \\wedge p_{vM}\\left(v_{2}, v_{4}\\right) \\wedge p_{vM}\\left(v_{3}, v_{5}\\right) \\wedge p_{vM}\\left(v_{4}, v_{6}\\right) \n  = p_{vM}\\left(v_{1}, v_{5}\\right) \\wedge p_{vM}\\left(v_{2}, v_{6}\\right) \\\\\n  = p_{bM}\\left(b_{1}, b_{3}\\right). \n  \\end{equation}\n  We really appreciate your feedback.\n\n**Limitations:**\n\nThanks for your feedback on the limitations of our work. To further discuss the limitation of the added computational complexity, we have conducted more experiments including 9 Atari games to further discuss the limitation of the added computational complexity. Experimental results (shown in Table 1 of the uploaded PDF) demonstrate that PTSA introduces an acceptable decrease in trajectory collection efficiency (less than 8% on average), which results in a significant reduction in the whole training time."}, {"review_id": "EyEJvLrGJB", "reviewer": "Reviewer_GJR1", "summary": "To accelerate MCTS, the paper proposed a novel probability tree state abstraction (PTSA) algorithm to improve the search efficiency of MCTS. \nThey 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.\n", "questions": "1. How do you prune a path from a tree? What will happen to those branches that are on the path?\n2. Have you considered abstraction functions that also require the best action should be the same[1]?\n[1] Are AlphaZero-like Agents Robust to Adversarial Perturbations?", "limitations": "Stated in the weakness. ", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The method provides some theoretical guarantee.\n2. The experiments take place in many environments.\n3. The ablation studies have tried many abstraction functions. \n", "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. \n \n2. 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.\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your helpful comments. We hope that our answers will help to resolve your concerns.\n\n**Weaknesses:**\n\n1. For the first problem, during the early stage of training, inaccurate estimation of the V values may prevent state abstraction methods from correctly aggregating states, which is a common issue for previous state abstraction methods. Addressing this issue is indeed a significant contribution of this paper. PTSA provides improved fault tolerance compared to previous abstraction functions by probabilistically avoiding incorrect aggregations, especially during the early stage of training, which is consistent with the results presented in Section 5.2 of our experiments.\n\n    For the second problem, the aggregation cannot be applied to all the similar or same states in the tree search space. For instance, given two paths with the same start node: $b_1=(v_0,v_1,v_2,\\cdots, v_n)$ and $b_2=(v_0,v'_1,v'_2,\\cdots, v'_n)$. $v_n$ and $v'_n$ represent similar or the same states. Assume  $v_n$ and $v'\\_n$ are aggregated into the same node. However, this operation leads to a ring structure, which conflicts with the MCTS tree structure. Intuitively, this issue can be addressed by deleting the intermediate nodes $(v\\_1,\\cdots,v\\_\\{n-1\\})$ or $(v'\\_1,\\cdots,v'\\_\\{n-1\\})$. However, deleting these nodes decreases the probability of exploring from these nodes, leading to inefficient exploration. \n\n  2.  We have conducted additional experiments to demonstrate that the proposed state abstraction function does not affect the convergence and performance of the algorithm when using larger simulation counts. Please refer to Figure 3 in the uploaded PDF for the experimental results. One possible reason is that more simulations lead to more accurate estimated node values, which makes the judgment of state abstraction functions more accurate. \n\n**Questions:**\n\n1. We apologize for the lack of detail in our paper regarding the pruning operation. The $pruning(b_j)$ action denotes removing unique nodes of path $b_j$ compared to the other abstracted path in the search tree. We have provided more detailed explanations of the add/delete operations used in Algorithm 1. The specific modifications can be found in the general response. \n\n2. Thanks for your suggestion. The requirement of the same best action is a very interesting and useful property, and it is consistent with state abstraction $\\phi^\\{\\epsilon\\}_\\{a^*\\}$ described in Table 1. This property may help to improve the robustness of the existing state abstraction functions. We plan to explore and combine this property with our proposed state abstraction method in future work. Furthermore, we will cite and discuss this work [1] in the final version.\n\n[1] Are AlphaZero-like Agents Robust to Adversarial Perturbations?"}, {"review_id": "dVz5P52xFz", "reviewer": "Reviewer_GnyW", "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.\n\nUPDATE: 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.", "questions": "- I had a number of questions about the exact implementation\n  - 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?\n  - 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?\n  - What is $l$ set to in the implementation? How does it value impact performance?\n  - What is the implementation of the pruning function in L17 of Algorithm 1?\n  - How are the legal actions for the abstracted state computed?\n  - What is the size of $S_L$? How was it chosen? How does varying it affect performance?\n\n- 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.\n\n- Is there a reason to not include code? Will code be included in the final version?", "limitations": "Yes", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "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. \n\n+ 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.\n\n+ 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.\n  - 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.\n  - There are a number of other implementation details that are difficult to find or missing. See the questions for examples.\n\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable feedback. We address each comment and concern below.\n\n**Weaknesses:**\n\n1. We appreciate your feedback and will provide a more careful description of the implementation details in the final version. We have provided more detailed explanations of the pruning/delete operation used in Algorithm 1. Detailed modifications can be found in the general response.  \n2. We will release our code upon acceptance, and conduct further research to explore how different state abstraction functions can be better tailored to fit the characteristics of the environment. We hope that this research will help to enhance the performance and applicability of our approach in a wider range of applications.\n\n**Questions:**\n\n1. Questions about the exact implementation：\n\n    1. We sincerely apologize for any misunderstanding caused by the simplification of the abstraction decision in Algo. 1. $(\\phi(b\\_i)=\\phi(b\\_s))$ returns a boolean value, where \"true\" denotes aggregating $b\\_i$ and $b\\_s$. This boolean value is determined by calculating the probability $\\mathbb{p}(\\phi(b\\_i)=\\phi(b\\_s))$ based on Equations (5) and (6). In the practical implementation, once the probability is computed, a random number (0~1) is generated and compared to the probability. If the random number is less than the probability, $\\phi(b\\_i)=\\phi(b\\_s)$ holds true. We will provide a clearer explanation of this issue in the final version.\n\n    2. Yes, your understanding is correct. Offline learning involves updating the dynamics, prediction, and value networks by sampling trajectories from a buffer. Online searching involves interacting with the environment to obtain high-quality trajectories, similar to MuZero algorithm. However, due to space limitations, Algorithm 1 in the paper only provides the MCTS search process, which may cause confusion for readers. We would like to clarify this issue in the final version.\n\n    3. The parameter $l$ is determined by the number of non-shared nodes between paths $b_i$ and $b_j$. A larger value of $l$ indicates that more nodes need to be evaluated to determine if they satisfy the aggregation condition. When $l=1$, path aggregation will degrade to node aggregation.\n\n    4. We apologize for not providing a clear explanation of the pruning/delete/add actions in the paper. We have provided more detailed explanations of the actions and notation used in Algorithm 1:  $S\\_L $ is a list that records the searched paths in the current search tree. $S\\_L.delete(b)$ and $S\\_L.add(b)$ refer to removing and recording path $b$ in $S\\_L$ respectively. The $pruning(b\\_j)$ action denotes removing unique nodes of path $b\\_j$ compared to the other abstracted path in the search tree.\n\n    5. The process of obtaining legal actions is similar to MuZero, which stores hidden states rather than real states. Therefore, the legal actions at the root node are obtained based on the corresponding real states. For example, in a board game, the legal actions represent the legal moves available in the current real state. \n\n    6. $S\\_L $ is a list that records the searched paths in the current search tree. In algorithms such as MuZero, SMuZero, and EfficientZero, the size of $S\\_L$ equals the number of simulations conducted. In our proposed algorithm, the size of $S\\_L$ is adjusted by the number of simulations subtracting the number of path aggregations. A larger $S\\_L$ indicates a larger tree search space, which may lead to inefficient exploration.\n\n2. We would like to resolve your concers from the following two aspects: \n\n    a. State abstraction functions need to be selected based on different environments: For example, $\\phi_{a^*}$ requires the values of two states to be exactly equal and have consistent optimal actions. Such abstraction conditions can be inefficient for some tasks, such as Atari, where two states may have similar but not equal values. For different tasks, it may be necessary to choose suitable state abstraction functions to achieve better abstraction performance.\n\n   b. The parameters of the state abstraction function require manual tuning: Some parameters of the state abstraction function need to be adjusted manually based on the characteristics of the environment. For instance, the parameter $d$ in $\\phi\\_{Q^*\\_d}$ typically ranges from 0 to 1. If the Q-value distribution in the environment is relatively smooth, a smaller value for $d$ (e.g., 0.2) is generally preferred. The parameter $\\epsilon$ in $\\phi^{\\epsilon}\\_{Q^*}$ is adjusted according to the range of the reward function. When the reward function has a larger range, the value of $\\epsilon$ tends to be relatively larger as well. Furthermore, you mentioned some parameters used in MCTS-based algorithms, such as simulations $N$. These parameters can be informed by previous experiences with MCTS work. For example, in Atari tasks, a common choice for the number of sampled actions $K=6$.\n\n    Studying how to select suitable state abstraction functions and fine-tune the parameters accordingly can be a direction for future research. We hope these responses can resolve your concerns.\n\n3. We will release our code upon acceptance, and provide the training instructions along with the corresponding random seed settings. "}, {"review_id": "comt1752x1", "reviewer": "Reviewer_Bu9r", "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%.", "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. \n* 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?\n* 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.\n* 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?\n* 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?\n* 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?\n* 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.\n* In Figure 2 (f),  the label of the green curve is “MuZero N=50”, should it be “MuZero N=30”?\n* Line 17, typo: Muzero -> MuZero.\n* Figure 2, typo: state-of-art -> state-of-the-art.\n* Figure 3 is shown after Figure 4. Please fix the order of these figures.", "limitations": "The authors have addressed the limitations in the paper.", "rating": 7, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "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.\n\n* 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%”.\n\n* 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”?\n\n* 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed review and the explicitly listed concerns. We hope that our answers will help to resolve the concerns.\n\n**Weaknesses**:\n\n1. We appreciate your feedback and acknowledge your concern regarding the limited number of Atari games used in our evaluation. We have conducted more Atari experiments (Assault, Seaquest, Breakout, and MsPacman tasks). The experimental results can be found in Figure 1 (in the uploaded PDF), which demonstrate the effectiveness of our algorithm in training acceleration.\n2. We would like to emphasize that our method improves the training efficiency with search space reduction. In our experiments including Gomoku, Control, and Atari tasks, we observe a 10%-45% search space reduction. As shown in Figure 2 (in the uploaded PDF), we provide additional evidence of reduced branching factors in more tasks to support this statement. We will revise our claim to eliminate this ambiguity.\n3. Figure 1 in the uploaded PDF shows the training results of each method with $N \\in \\\\{ 18,30\\\\}$, indicating that PTSA exhibits superior training efficiency compared to other algorithms with the same simulations. This result demonstrates that the PTSA also improves the training efficiency with larger simulations.\nWe also compare the performance of PTSA N=30 and PTSA N=18. The results show that PTSA N=18 achieves comparable performance as PTSA N=30  with less training time. The presentation of results for N=18 in the paper aims to highlight how PTSA enables MCTS-based algorithms to achieve comparable performance even at smaller N values, thereby enhancing training efficiency.   \n\n4. We appreciate your suggestion. To compare the effectiveness and aggregation percentage of PTSAZero with different numbers of simulations ($N$), we have conducted additional experiments as shown in Figure 2&3 (in the uploaded PDF). We observe that increasing the number of simulations does not significantly affect the aggregation percentage for the same environment and state abstraction function.\n\n**Questions:**\n\n1.  The two abstracted paths are required equal in length, which aligns with the mapping principle of state abstraction theory. Given two paths to be abstracted, the mapping principle denotes that two abstracted nodes at the same depth should be mapped into the same abstracted state. If two paths are of different lengths, their abstracted path lengths will also be different, which conflicts with the mapping principle. \nSimilar to other state abstraction functions, the $\\phi_{Q^{\\psi}_{\\alpha}}(b)$ function maps a given path to a path in the abstract space. In Section 4.3, we define a method to compute the probability of two paths being mapped to the same abstract path under $\\phi\\_{Q^{\\psi}\\_{\\alpha}}(b)$. We will provide a clearer explanation in the final version.\n2. We apologize for not providing a comprehensive explanation of the pruning operation in the paper. We have provided more detailed explanations of the actions and notation used in Algorithm 1, including the pruning/delete/add operations. $S_L$ is a list that records the searched paths in the current search tree. $S_L.delete(b)$ and $S_L.add(b)$ refer to removing and recording path $b$ in $S_L$ respectively. The $pruning(b_j)$ action denotes removing unique nodes of path $b_j$ compared to the other abstracted path in the search tree. \n3. According to your suggestions, we have conducted additional experiments. The results can be found in Figure 1 (in the uploaded PDF), while the analysis is given in response to the weakness.  \n\n4. Two methods including pitting them against each other and employing the same rule-based agent as the opponent are both commonly used to evaluate AI agents in board games. Using the same rule-based agent as the opponent is sufficient for a fair comparison in our experiments, which is commonly utilized in previous works [1,2,3]. Additionally, to maintain consistency, we use the same number of simulations for evaluation as during training.\n\n  5. We apologize for the incorrect use of the term \"win rate.\" It should have been referred to as the \"return\" in the figure, where a value of 1 represents a win and -1 represents a loss during evaluation. We will rectify this typo in the final version.\n\n  6. You have raised an intriguing point that the characteristics of the state space in different tasks and the state abstraction function are the key factors influencing the reduction effect. This presents an important direction for future research. \nWe have conducted more Atari experiments, and the corresponding results can be found in the uploaded PDF. 9 Atari games are utilized in our experiment, including Pong, Alien, Breakout, etc., which are commonly used tasks in the previous works.\n\n  7. Our motivation is to enhance MCTS efficiency by reducing the branching factor. However, when N is very small, the advantages of the PTSA algorithm diminish due to the extremely limited search space. Considering that N=2 already results in a significantly small branching factor, it is unnecessary to evaluate the performance in such a small N scenario.\n\n8,9,10,11 We will correct these typos and mistakes in the final version. Thank you very much for pointing out these issues, and we will address these issues and improve readability in the final version.\n\n[1] Spending thinking time wisely: Accelerating MCTS with virtual expansions\n\n[2] Action guidance with MCTS for deep reinforcement learning\n\n[3] Opponent modeling based on action table for MCTS-based fighting game AI"}, {"review_id": "LMz7WbZF4T", "reviewer": "Reviewer_Yoim", "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%.\n", "questions": "1. Why does $v_0.pruning$ do in line 17 in Algorithm 1? Any difference from $S_L.delete(b_j)$. \n\n2. 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? \n\n3. 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. \n\n4. 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$. \n\n5. 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). \n", "limitations": "N.A.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. The approach of aggregation considers the entire path, not only a state, is novel and unique.\n\n2. The PTSA algorithm presented in this paper can be applied with any other state abstraction functions mentioned in previous studies, in a general way.\n\n3. 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.\n\n4. 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.\n", "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.\n\n2. There are some errors in the proofs presented. This will be discussed in detail in the Questions section as well.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your uplifting review and valuable feedback. We appreciate your comments and would like to address them below. \n\n**Questions:**\n\n1. We apologize for not providing a clear explanation of the pruning/delete/add actions in the paper. We have provided more detailed explanations of the actions and notation used in Algorithm 1:\n$S_L $ is a list that records the searched paths in the current search tree. $S_L.delete(b)$ and $S_L.add(b)$ refer to removing and recording path $b$ in $S_L$ respectively. The $pruning(b_j)$ action denotes removing unique nodes of path $b_j$ compared to the other abstracted path in the search tree. \n\n  2. We sincerely apologize for any misunderstanding caused by the simplification of the abstraction decision in Algo. 1. $(\\phi(b\\_i)=\\phi(b\\_s))$ returns a boolean value, where \"true\" denotes aggregating $b\\_i$ and $b\\_s$. This boolean value is determined by calculating the probability $\\mathbb{p}(\\phi(b\\_i)=\\phi(b\\_s))$ based on Equations (5) and (6). In the practical implementation, once the probability is computed, a random number (0~1) is generated and compared to the probability. If the random number is less than the probability, $\\phi(b\\_i)=\\phi(b\\_s)$ holds true. We will provide a clearer explanation of this issue in the final version.\n\n 3. The work presented in \"Monte Carlo Tree Search with Iteratively Refining State Abstractions\" makes significant contributions by introducing an alternative approach called \"abstraction refining\" to replace progressive widening in MCTS. Their experiments primarily compare the \"abstraction refining\" method with progressive widening. As \"abstraction refining\" provides an improvement during node selection and expansion, it does not conflict with our method of performing abstraction after completing the backpropagation. Additionally, due to the challenge of accurately calculating the distance between hidden states, there is a lack of a clear implementation for integrating the \"abstraction refining\" method with MuZero algorithm. Hence, this comparison is difficult to be conducted in our experiments. \nFurthermore, Table 1 focuses on describing the state abstraction functions used in previous model-free algorithms, which is why the \"abstraction refining\" method is not included in Table 1. In future work, we plan to study the impact of incorporating the criterion $d(s_1, s_2)$ in our algorithm.\n\n4. According to your suggestion, we have conducted more experiments including 9 Atari games to further discuss the limitation of the added computational complexity. Experimental results (shown in Table 1 of the uploaded PDF) demonstrate that PTSA introduces an acceptable decrease in trajectory collection efficiency (less than 8% on average), which results in a significant reduction in the whole training time.\n\n5. Thanks for your careful review. We have corrected the typos in Appendix Equation (19):\n  \\begin{equation}\n  p_{bM}\\left(b_{1}, b_{2}\\right) \\wedge p_{bM}\\left(b_{2}, b_{3}\\right)\n  = p_{vM}\\left(v_{1}, v_{3}\\right) \\wedge p_{vM}\\left(v_{2}, v_{4}\\right) \\wedge p_{vM}\\left(v_{3}, \n v_{5}\\right) \\wedge p_{vM}\\left(v_{4}, v_{6}\\right) \n  = p_{vM}\\left(v_{1}, v_{5}\\right) \\wedge p_{vM}\\left(v_{2}, v_{6}\\right) \\\\\n  = p_{bM}\\left(b_{1}, b_{3}\\right). \n  \\end{equation}\n  We appreciate your feedback and support.\n\n"}]

Author rebuttal:
## General Response ##

We thank all reviewers for their valuable feedback. We have carefully considered your suggestions and conducted additional experiments (shown in the uploaded PDF) to address your concerns, as outlined below:

1. We have conducted more Atari experiments (Assault, Seaquest, Breakout, and MsPacman tasks). The experimental results can be found in Figure 1 (in the uploaded PDF), which demonstrate the effectiveness of our algorithm in training acceleration.
2. We have conducted more experiments to evaluate the aggregation percentage in Atari, Gomoku and Control Tasks. The experimental results can be found in Figure 2 (in the uploaded PDF), which further validate the reduction of the tree search space resulting from our proposed algorithm.
3. To compare the effectiveness and aggregation percentage of PTSAZero with different numbers of simulations ($N$), we have 
 conducted additional experiments as shown in Figure 2&3 (in the uploaded PDF). We observe that increasing the number of simulations does not significantly affect the aggregation percentage for the same environment and state abstraction function.
4. As shown in Table 1 (in the uploaded PDF), we have also conducted an analysis of the time consumption. PTSA introduces an acceptable decrease in trajectory collection efficiency (less than 8% on average), which results in a significant reduction in the whole training time.


Furthermore, we have improved the presentation to make our paper more comprehensible, which will be incorporated into the final version:

(1) We provide more detailed explanations of the notations used in Algorithm 1, including the pruning/delete/add actions and the hidden state $h$:

$S_L$ is a list that records the searched paths in the current search tree. $S_L.delete(b)$ and $S_L.add(b)$ refer to removing and recording path $b$ in $S_L$ respectively. The $pruning(b_j)$ action denotes removing unique nodes of path $b_j$ compared to the other abstracted path in the search tree.  $h$ denotes the hidden feature of the original real environment state, which is employed to prevent MCTS from interacting with the actual environment during simulation in MuZero.

(2) We have corrected a typo in Appendix Equation (19). The corrected version is as follows:
\begin{equation}
    p_{bM}\left(b_{1}, b_{2}\right) \wedge p_{bM}\left(b_{2}, b_{3}\right)
    = p_{vM}\left(v_{1}, v_{3}\right) \wedge p_{vM}\left(v_{2}, v_{4}\right) \wedge p_{vM}\left(v_{3}, v_{5}\right) \wedge p_{vM}\left(v_{4}, v_{6}\right) 
    = p_{vM}\left(v_{1}, v_{5}\right) \wedge p_{vM}\left(v_{2}, v_{6}\right) 
    = p_{bM}\left(b_{1}, b_{3}\right)
\end{equation}

Finally, we would like to express our sincere gratitude to all the reviewers for their valuable suggestions. The code will be released upon acceptance. We hope that our response will resolve your concerns.

Meta-review: The reviewers found the paper to make a solid contribution. Please take the critical feedback into account when preparing the camera ready version.
Decision: Accept (poster)