Spending Thinking Time Wisely: Accelerating MCTS with Virtual Expansions
Authors: Weirui Ye
Pieter Abbeel
Yang Gao
Venue: NeurIPS 2022 Accept (2022)
Keywords: Computer Go
Monte-Carlo Tree Search
Reinforcement learning
Adaptive
Acceleration

Abstract: One of the most important AI research questions is to trade off computation versus performance since ``perfect rationality" exists in theory but is impossible to achieve in practice. Recently, Monte-Carlo tree search (MCTS) has attracted considerable attention due to the significant performance improvement in various challenging domains. However, the expensive time cost during search severely restricts its scope for applications. This paper proposes the Virtual MCTS (V-MCTS), a variant of MCTS that spends more search time on harder states and less search time on simpler states adaptively. We give theoretical bounds of the proposed method and evaluate the performance and computations on $9 \times 9$ Go board games and Atari games. Experiments show that our method can achieve comparable performances to the original search algorithm while requiring less than $50\%$ search time on average. We believe that this approach is a viable alternative for tasks under limited time and resources. The code is available at \url{https://github.com/YeWR/V-MCTS.git}.

Spending Thinking Time Wisely: Accelerating MCTS with Virtual Expansions
Weirui Ye* Pieter Abbeel!
Yang Gao +18
*Tsinghua University, UC Berkeley, $ Shanghai Qi Zhi Institute
Abstract
One of the most important Al research questions is to trade off computation versus performance since "perfect rationality" exists in theory but is impossible to achieve in practice. Recently, Monte-Carlo tree search (MCTS) has attracted considerable attention due to the significant performance improvement in various challenging domains. However, the expensive time cost during search severely restricts its scope for applications. This paper proposes the Virtual MCTS (V-MCTS), a variant of MCTS that spends more search time harder states and less search time simpler states adaptively. We give theoretical bounds of the proposed method and evaluate the performance and computations on 9 Go board games and Atari games. Experiments show that our method can achieve comparable performances to the original search algorithm while requiring less than 50% search time average. We believe that this approach is a viable alternative for tasks under limited time and resources. The code available at httptss: //tgt///tttt cwm/YewR, Beee//YeW////// VVCMS git
Introduction
When artificial intelligence was first studied in the 1950s, researchers have sought to find the solution the question "How build an agent with perfect rationality". The term "perfect rationality" here refers to the decision made with infinite amounts of computations. However, one can only solve small-scale problems without considering the practical computation time since classical search algorithms usually exhibit exponential running time. Therefore, recent AI research would no longer seek achieve "perfect rationality". but instead carefully trade-off computation versus the level of rationality. People have developed computational models like "bounded optimality" to model these settings (66.. The increasing level of rationality under the same computational budget has given us a lot of Al successes. Algorithms include the Monte-Carlo sampling algorithms. the variational inference algorithms, and using DNNs as universal function approximators
7 24 26
Recently, MCTS-based RL algorithms have achieved much success, mainly on board games. The most notable achievement that AlphaGo beats Hui Fan in 2015 30) It is the first time a computer program beat a human professional Go player. Afterward, AlphaGo beats two top-ranking human players, Lee Sedol 2016 and Jie Ke 2017, the latter of which ranked first worldwide at the time. Later, MCTS-based RL algorithms were further extended to other board games and Atari games (27). EfficientZero algorithms, shedding light on its future applications in the real world like robotics and self-driving.
M+ significantly improves the sample efficiency of MCTS-basee RL
Despite the impressive performance of MCTS- RL algorithms, they require massive amounts of computation to train and evaluate. For example, MuZero (27] used 1000 TPUs trained for 12 hours learn the game of Go, and for single Atari game, it needs 40 TPUs train 12 hours. Compared
208maals .ts.imanuslssttntuua...e. wewsinguaaedu.com edu. cn, gaoyangiiisttsingghn edu. "pabbeel@berkeley... "Corresponding author
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

to previous algorithms on the Atari games benchmark, it needs around two orders of magnitude more compute. This prohibitively large computational requirement has slowed down both the further development of MCTS-based RI. algorithms as well as its practical use.
Under the hood, MCTS-based RL algorithms imagine the futures when taking different future action sequences. However, this imaging process for the current method is not computationally efficient. For example, AlphaGo needs look ahead 1600 game states to place a single stone. On the contrary, top human professional players can only think through around 100-200 game states per minute [30]. Apart from the inefficiency, the current MCTS algorithm deals with easy and challenging cases with the same computational budget. However, human knows to use their time when it is most needed.
In this paper, aim design new algorithms that save the computational time of the MCTS- based RI. methods. We make three key contributions: (1) We present Virtual MCTS, a variant of MCTS, to approximate the vanilla MCTS search policies with less computation. Moreover, unlike previous pruning- based methods that focus on the selection or evaluation stage in MCTS, our method improves the search loop. It terminates the search iterations earlier adaptively when current states are simpler; (2) Theoretically, we provide some error bounds of the proposed method. Furthermore, the visualization results indicate that Virtual MCTS has better computation and performance trade-off than vanilla MCTS; (3) Empirically, our method can save more than 50% of search times on the challenging game Go 9 and more than 60% on the visually complex Atari games while keeping comparable performances to those of vanilla MCTS.
2 Related Work
2.1 Reinforcement Learning with MCTS
For a long time, Computer Go has been regarded as a remarkably challenging game 33 Researchers attempt use Monte-Carlo techniques that evaluate the value of the node state through random
playouts A. 12 30 Afterward, UCT algorithms have generally been applied in Monte-Carlo tree search (MCTS) algorithms, which use UCBI select action at each node of the tree 120)
31 27 have become increasingly popular and achieved super-human performances on board games because of their strong ability to search.
Recently, MCTS-based RL methods (30 32
Modern MCTS besed RL algorithms include four stages in the search loop: selection, expansion, evaluation, and backpropagation. The computation bottlenecks in vanilla MCTS come from the search loop, especially for the evaluation stage and the selection stage of each iteration. The selection stage is time-consuming when the search tree becomes wider and deeper. The evaluation stage is quite expensive because people attempt to evaluate the node value by random playouts to the end in previous researches. Due to the search loop, MCTS-based algorithms have multiple model inferences compared to other model-free RL methods like PPO PX and SAC [6]
2.2 Acceleration of MCTS
MCTS-based methods have proved their strong capability of solving complex games or tasks. However, the high computational cost of MCTS hinders its application to some real-time and more general scenarios. Therefore, numerous works are devoted to accelerating MCTS. For example, to make the selection stage more effective, some heuristic pruning methods I
aim to reduce the width and depth of the search tree with some heuristic functions. Furthermore, for more efficient evaluations, Lorentz 2 proposed early playout termination of MCTS (MCTS-EPT) to stop the random playouts early and use an evaluation function to assess win or loss. Moreover, Hsueh et al. [ل] applied MCTS-EPT to the Chinese dark chess and proved its effectiveness. Afterward, similar ideas have been applied in the evaluation stage of AlphaGoZero [ and later MCTS- based methods BI 27 M. They evaluate the Q-values through a learnable evaluation network instead of running playouts to the end. Grill et al. [15] propose novel regularized policy optimization method based on AlphaZero to decrease the search budget of MCTS, which is from the optimization perspective.
K3 29
Danihelka et al. [10] propose policy improvement algorithm based on sampling actions without replacement, named Gumbel trick to achieve better performance when planning with few simulations.
However, these methods mentioned above focus on the specific stage of the search iteration or reduce the total budget through pruning and optimization methods, which are orthogonal to us. And few works targets at the search loop. Lan et al. 21 propose DS-MCTS, which defines the uncertainty of
2

---

MCTS and approximates it by extra DNNs with specific features for board games in training. During the evaluation, DS-MCTS will check periodically and stop the search the state is certain.
Background
The AlphaGo series of work 60 32 51 27 are all MCTS- based reinforcement learning algorithms.
Those algorithms assume the environment transition dynamics are known or learn the environment dynamics. Based on the dynamics, they use the Monte-Card tree search (MCTS) as the policy improvement operator. I.e., taking in the current policy, MCTS returns better policy with the search algorithm. The systematic search allows the MCTS-based RL algorithm to quickly improve the policy and perform much better in the setting where heavy reasoning is required.
3.1 MCTS
This part briefly introduces the MCTS method implemented in reinforcement learning applications. As mentioned in the related works, modern ICCTS-baser RL algorithms include four stages in the search loop, namely selection, expansion, evaluation, and backpropagation.
MCTS takes in the current states and generates policy after the search loop of N 'tterations Here N is a constant number of iterations set by the designer, regarded as the total budget. In the selection stage of each iteration, an action will be selected by maximizing over UCB. Specifically, AlphaZero BI and MuZero [27] are developed based on variant of UCB, P-UCT [25] and have achieved great success on board games and Atari games. The formula of P-UCT the Eq T
VEDEA (ci + log(( Σ +2 1+
aEd a* arg max Q(s.a) + P(s,a) P(s,a)
BEA
where i is the index of iteration, A is the action set, (ss,a) is the estimated Q-value, P(s, a) is the policy prior obtained from neural networks, ((s a) is the visitations to select the action from the state and C1, C2 are hyper-parameters. The output of MCTS is the visitation of each action of the root node. After N search iterations, the final policy T(s) is defined as the normalized root visitation distribution N (s), where Tx (s, N(s a)/ EBEA (ss, simplification,
((s, a)/k: A. For TR in place of TT{(s) sometimes. And the detailed procedure of MCTS is introduced in Appendix. In our method, we propose to approximate the final policy n (s) with (s). which name virtual expanded policy, through new expansion method and termination rule. In this way, the number of iterations in MCTS can be reduced from N to k.
3.2 Computation Requirement
Most of the computations MCTS- RI. are the MCTS procedure. Each action taken by MCTS requires N times neural network evaluations, where N is constant number of iterations in the search loop. Traditional RL algorithms, such as PPO 28 or DQN [23], only need a single neural network evaluation per action. Thus, MCTS-based RL is roughly N times computationally more expensive than traditional RL algorithms. In practice, training a single Atari game needs 12 hours of computation time on 40 TPUs [27]. The computation need is roughly two orders of magnitude more than traditional RL algorithms
2 although the final performance of MuZero is much better.
Method
We aim to spend more search time on harder states and less on easier states. Intuitively, human knows when to make a quick decision or slow decision under different cireumstances. Unfortunately, this situation-awann aware behavior is absent in current MCTS algorithms. Therefore, we propose an MCTS variant that terminates the search iteration adaptively. consists of two components: a novel expansion method named virtual expansion to estimate the final visitation based on the current partial tree; termination rule that decides when to terminate based on the hardness of the current scenario. And will display the adaptive mechanism through visualizations in Section 5.5
3

---

4.1 Termination Rule
We propose to terminate the search loop earlier based on the current tree statistics. Intuitively, we no longer need to search further if we find that recent searches have little changes on the root visitation distribution. With this intuition algorithm. As mentioned in 3.1 (s)s) is the policy defined by the visitations of the root state at iteration k. Let (i,i,) be the difference of n. (x),,, Ty (8), namely (i = [|=T(()) T (s)]] Then we terminate the search loop when we have searched at least rN iterations and A, (k, k/2) < where c is a tolerance nyper-parametet
mind, we propose simple modification to the MCTS search
(0. 1) is the ratio of the minimum search budget and N is the full search iterations. We show that under certain conditions, bound on (, k/2) implies
a bound on A, N). A, N) measures the distance between the current policy (8) and the oracle policy (s). In this way, A, k/2) reflects the hardness of the state Consequently, once the gap is small enough, it is unnecessary for more search iterations.
4.2 Virtual Expansion in MCTS
Algorithm 1 Iteration of vanilla MCTS
Algorithm 2 Iteration of MCTS with Virtual Ex- pansion
1: Current k-th iteration step:
2: Input: A, (x, Nx
1: Current k-th iteration step:
3: Initialize: 8 <- Syool
2: Input: A, P. (s. a), Na(s, N((s,)
4: repeat do search
5: a" + UC P,N)
4: if Not init Na then
6: <- next state(s,
5: Init: Na(s,a) t (x(s,))
7: until (=
6: end if
8: Evaluate the state value R(s, a) and P(s,a)
7:
9: for along the search path do
8: s + Stoot
10:
QR+1(s,
9: a" + UCBI(Q,
11: 18,1(8,0) N)(s,a)+1 +1
10: Nu(s, + (a(s +1
12:
end for
11:
13:
Return QK+1 o), (x,1(s,a)
12: Return (s(
For the termination rule (skk; k/2) < e, we assume π; and πj are directly comparable. However, they are not directly comparable because the tree is expanded with UCT. As the number of visits increases, the upper bound would be tighter, and the latter visits are more focused on the promising parts. Thus earlier visitation distributions (smaller iteration number) can exhibit more exploratory distribution, while latter ones (larger iteration number) are more exploitative on promising parts.
To compare and n, properly, we propose a method called virtual expansion in place of the vanilla expansion. Briefly, it aligns two distributions by virtual UCT expansions until the constant budget N. When the tree is expanded at iteration k, it has N & iterations to go. A normal expansion would require evaluating neural network N k times for a more accurate Q(s, a) estimate for each arm at the root node. Our proposed virtual expansion still expands N k times according to UCT, but it ignores the N k neural network evaluations and assumes that each arm's 's Q(s, a) does not change. We denote the virtual expanded distribution from ग. as a virtual expanded policy म. By doing virtual expansions on both n; and T.. we will obtain the corresponding virtual expanded policies tr Rty. Here effectively remove the different levels of exploration/cxploittii in the two policies. Then the termination condition becomes the difference of virtual expanded policies. We name the rule VET-Rule (Virtual Expanded Termination Rule):
Å (k. k/2) (s) #t/2(s)|| <e
The comparisons between vanilla expansion and virtual expansion are illustrated in Algorithm I
and 2 The cone-consuming computations are highlighted in Algorithm [ Line 4 to 7 in Algorithm
target at searching with UCT to reach an unvisited state for exploration. Then it evaluates the state and backpropagates along the search path to better estimate Q-values. After total N iterations,
the visitation distribution of the root node x ) is considered as the final policy π (s). However,
in virtual expansion, listed in Algorithm 2 only searches one step from the root node. And
it selects actions based on the current estimations without changing any properties of the search

---

tree. Furthermore, the virtual visited counts [s a) are changed after virtual visits to balance the exploitation and the exploration issue. After N times virtual expansion, the virtual expanded policy becomes # (s, a) = (s, a)/N instead of (s, a)/k. When i N, further searches after the root have effects on the final policy. So n (s, a) a))
4.3 V-MCTS Algorithm
The procedure of MCTS with VET-
Rule is listed in Algorithm g We
Algorithm Virtual MCTS
name our method Virtual MCTS (V-
Input: budget N, state s, conservativeness r, error c
MCTS), variant of MCTS with VET- Rule. Compared with the original MCTS, lines 8- 13 are the pseudo-code for the rule. In each iteration, we do some calculations with little cost to judge whether the VET-Rule is satis- fied. If it is, then the search process terminated and returns the current
2: Notice: (s)s). ft{(s) are policy distributions.
Notice: (s, (s, ss a) are probabilities for action a.
4: for k E N do
5: Selection with UCB1
6: Expansion for the new node
7:
Evaluation with Neural Networks
8:
Backpropagation for updating Q and visitations (T a) <- N& (s, a)/k
virtual expanded policy (s). Thus, skips the next N k model pre- dictions from neural networks in the evaluation stage highlighted in line 7. In this way, we can approximate the
9:
10:
Virtual expand N - nodes and update Ñ(s, a)
11:
f a) <- N₂ (s, a)/N
12:
i 2 N A [x (s) - #x/2(+)|1 < then
13:
T(s) t Tk (s)
oracle distribution nN by it. while re- ducing the budget of N simulations
14:
Break
15:
end if
to k. Here, k 2 rN and r is a hy-
16: (T() f TT((s)
perparameter of the minimum budget
17:
end for
rN. We can reduce the tree size by 1/r times at most.
18: Return ((s)
4.4 Theoretical Justifications
Furthermore, we will give some theoretical bounds on the Q-values and Á, N) of V-MCTS. Before this, we define some notations first: & is the index of the current search iteration, and N is the number of total search iterations. .A is the action set and |A| > 1. Each action a E A is associated with value, which is random variable bounded in the interval [o, 1] with expectation Qa. At step k the empirical mean value over the k trails is Qs a). For simplification, we denote Qu a) as Q+. We denote the empirical mean value after N k virtual expansion Q.N Since we only deal with the visitation distribution of the root, we omit the state subscript for the root state. For convenience, assume that different actions are ordered by their corresponding expected values, which means that 1 2 Q 2 Q2 2 ... 2 Qa 2 ... 2 Q 2 O.
Theorem 4.1. Given r E (0, 1), confidence å E 10, finite action set A. NND > 0, VN >
No, k 2 rN, let = V 26 In 1008.
8 after l times vanilla expansion and N k times virtual
expansion, we have (a) Value Consistency in Virtual Expansion: PriNNEA Q - Qa < <x
(1 A51A 50 ); (b) Best Action Identification in Virtual Expansion: Prt QN - QN < <Ex
1 2( 50 exp ([6iv)) + 50N7 exp ))), where == arg m Q% is the Euler's number.
8
Theorem (a) gives a bound of the distance between the empirical mean values after virtual e6 All expansions and the expected values. Noticed that lim E 0 and lim 50 0. It tells that, after enough trails, the expected Q-values of all actions can be estimated by the corresponding empirical Q-values after virtual expansion. Furthermore, when the Q-values have converged, the effect of virtual expansion is the same as that of vanilla expansion. Denote the best empirical action as +, and the best expected action the Q-value of the best empirical action with virtual expansion is of high probability to be close to
because Q1 2 Qa. Theorem 4. (b) notes that
the Q-value of the best expected action with vanilla expansion. Intuitively, tells that whether or not successfully find the best expected action, the best empirical action has similar effects to the best
5

---

expected action. And, No should be larger than the action space size, otherwise it cannot satisfy the theorem conditions. The proof is attached in Appendix.
Theorem 4.2. (Error Bound of V-MCTS): Given r E (0. 1), confidence E (0, 1), finite action
ser A. Suppose the virtual expanded policy #T generated from Algorithm 3 (V-MCTS), 3ND
VN > No, k 2 rN, Ve E (0, 10. if [+*(s) - #x/2(s)] < we have Pr (x - (s]l)) <
3c} > 1 nd) (1 + ) where e is the Fuler's 's number.
50N
Theorem 4.2 tells that a bound of (k, k/2) implies a bound of A, N) with high probability. c8 e
Noticed that limv-xc 50.y= (1 _ O. Therefore, the oracle policy TN (s) can be approximated by f (s) after enough trails. The proof of this theorem is attached in Appendix.
Given the minimum distance e, for easier states, the rule (, k/2) < e easier to satisfy. That's because the Q-values of the tree nodes keep in small range the virtual expanded policy generated by V-MCTS is close to the oracle policy, and the search loop will be terminated earlier if the state is easier. In the next section, do ablations to investigate the effects of the hyper-parameters and show visualizations to verify the adaptive behavior.
with more search iterations. Thus,
5 Experiments
In this section, the goal of the experiments is to prove the effectiveness and efficiency of V-MCTS. First, we compare the performance and the cost between the vanilla MCTS and our method. Specifi- cally, we evaluate the board game Go 9 9, and few Atari games. In addition, we do some ablations to examine the virtual expansion's 's effectiveness and evaluate the sensitiveness of hypper-prameters Finally, we show the adaptive mechanism through visualizations and performance analysis.
5.1 Sctup
Models and Environments Recently, Ye al. 64 proposed EfficientZero, a variant of MuZero 20 with three extra components to improve the sample efficiency, which only requires 8 GPUs in training. and thus it is more affordable. Here we choose the board game Go 9 and a few Atari games as our benchmark environments. The game of Go tests how the algorithm performs in challenging planning problem. And Atari games feature visual complexity.
Hyper-parameters As for the Go 9 x 9, we choose Tromp-Taylor rules. The environment of Go built based on an open-source codebase, GymGo [T. We evaluate the performance of the agent against GNU Go v3.8 at level 10 [5] for 200 games. We include 100 games as the black player and 100 games as the white one with different seeds. We set the komi 6.5, as most papers do. As for the Atari games, we choose 5 games with 100k environment steps. In each setting, we use 3 training seeds and 100 evaluation seeds for each trained model. More details are attached in Appendix.
We compare our method to EfficientZero with vanilla MCTS, on Go 9 x 9 and some Atari games. Moreover, DS-MCTS (1) also terminates the MCTS adaptively through trained uncertainty networks. But it requires specific features designed for Go games, and it only works in the evaluation stage. Therefore, we also compare the final performance for Go games with the DS-MCTS.
Baselines
5.2 Results on Go
Figure [(a) illustrates the computation and performance trade-off on Go against the same GnuGo (level 10) agent. The x-axis is the training speed, and the y-axis is the winning rate. Therefore, the curve which lies to the top-left has better performance than the bottom-right in terms of the trade-off. We train the baseline method with constant budgets N, which is noted as the blue points. Besides, we also train the V-MCTS with hyperparameters r = 0.2, 0.1. We evaluate the trained model with different to display the trade-off between computation and performance, indicated as the red points. And the green points are the GnuGo with different levels. The GnuGo engine provides models of different levels (1-10). Each level is trade-off between the run time and the strength of the agent. The y-axis is the winning rate against the model of level 10. Here the green curve shows the performance-compult
trade-off of the GnuGo engine.

---

9x9 Go vs Gnuco (level 10)
9x9 Go vs Gnuco (level 10)
50% winning rate
No130
age Tainnng
140
N=150
aps=0.1
MCTS
N--5 VMCTS
GnuGo Engire
Winning Rate
NN-12
Winning Rate
N-90
pp
100
Level 10
Level
Level
1.5
2,0
2.5
3.0
3.5
4.0
0
20
40
80
100
Frame per
Millions of Frames
(a) Evaluations of Performance
(b) Wining Rates and Tree Size during Training
Figure 1: Performance of Virtual MCTS on Go 9 x 9 against GnuGo (level 10). (a) Evaluating the speed and winning rate of MCTS, V-MCTS, and GnuGo different levels. V-MCTS has better computation and performance trade-off. X-axis is the frame per second in the In scale. (For convenience, the eps in Figure (a) denotes the hyperparameter e.) (b) Evaluating the winning rate and the average tree size during the training stage. The solid lines and dashed lines display the winning rate and the tree size, respectively. The red one is V-MCTS, and the others are vanilla MCTS with different N. V-MCTS makes the tree size adaptive in training and reduces the search cost while performing comparably the vanilla MCTS (N 150). However, reducing N vanilla MCTS results in more significant performance drop.
Firstly, for all the methods, more search iterations (larger or smaller eps) lead higher winning rates but result in more response time. Secondly, V-MCTS (e = 0.1) achieves 71 % winning rate against the GnuGo level 10, which is close 75% from MCTS (N 150). And the time cost of V-MCTS (c = 0.1) for a ste- move is 0.12s while the GnuGo engine is 0.18s and MCTS (N 150) more than 0.2s. Therefore, such termination rule can keep strong performances with less budget. For more detailed breakdown of the time consumption of V-MCTS, please see the Appendix. Finally, we can find that the red dashed line lies to the right of the blue one. It indicates that V-MCTS is better than the vanilla MCTS considering the computation and performance trade-off.
Figure I(b) illustrates the changes of winning rates and the average tree size over the training stage. Here, as the red dashed line shows, the tree size of V-MCTS varies over training and keeps smaller than the maximum size (NV 150) while the winning rate keeps comparable the MCTS (WV 150). Consequently, V-MCTS can work well not only in evaluation but also in training.
We also compare method to DS-MCTS (21]), which terminates the search when the state is predicted to be certain with DNNs. To make fair comparisons, we implement the DS- MCTS and follow their design of features for Go games. We set Nmaz = 150, (30, 75, 120), thr = f.1,.1,11 in DS-MCTS. Then we compare the winning rate and the average budget among the vanilla MCTS, DS-MCTS, and V-MCTS.
Table 1: Results for Go 9 9: Comparison of the winning rate and the average budget over 200 games for separate training runs.
MCTS (N=150)
DS-MCTS 97 12.5
V-MCTS
Average budget Winning rate
150 0.0
+ 10.8
75% + 3.0%
60% + 4.0%
71% + 4.7%
Table 2: Results for Atari games: scores over 100 evaluation seeds for separate training runs. is the average budget of V-MCTS. MCTS (NV 50) the oracle one. The best results among distinct versions except the oracle are in bold. V-MCTS achieves better performance-computttio trade-off.
MCTS
N 50
N 30
N 10
Ours (V-MCTS)
Budget k
Pong
19.7 -
12.5 +
2.0 + 1.3
18.8 2.8
13.3 0.6
Breakout
410.7 - 15.1
370,9 1 34.1
303,9 1 11.3
372.8 1 18.3
15.7 0,6
Seaquest
1159.9 1 90.7
775.2 1 146.8
555,4 1: 66.9
970.0 1 339.5
14.3 1 1.2
Hero
9992.1 1. 2059.4
9241.3 3615.3
4437.0 2490.6
8928.1 1: 2922.1
15.0 1: 1.0
Qbert
14495.8 + 683.9
10429.9 + 2291.1
8149.8 2085.0
11476.6 978.2
16.3 1.2

---

9x9 Go vs Gnuco (level 10)
9x9 Go vs Gnuco (level 10)
Aver age Size During Iraining
Trainin aainnn
140
140
0pse0
aps-int
120
120
Winning Rate
Winning Rate
100
100
Awerap
0
20
40
80
100
0
20
40
80
100
Millions of frames
Millions of Frames
(a) Evaluations of Performance
(b) Wining Rates and Tree Size during Training Stage
Figure 2: Sensitivity VET-Rule to the hyperparameter r, c on Go 9 x 9. The solid lines and dashed lines display the winning probability and the average tree size, respectively.
Experiments show that V-MCTS outperforms the DS-MCTS in both aspects, listed in Table || We attribute the better performance of V-MCTS to the virtual expanded policy. DS-MCTS chooses (s) as the policy after the termination of the search, while V-MCTS chooses (s), which has theoretical guarantees to approximate N (s).
5.3 Results Atari
Apart from the results of Go, also evaluate our method on some visually complex games. Since the search space of Atari games is much smaller than that of Go and the Atari games are easier, we choose few Atari games to study how the proposed method impacts the performance. We follow the setting of EffcientZero, 100k Atari benchmark, which contains only 400k frames data. The results are shown in Table 2 Generally, we find that our method works on Atari games. The tree size is adaptive, and the performance of V-MCTS is still comparable to the MCTS with full search trails. has better performance than the MCTS(N 30) while requiring fewer searches, proving the effectiveness and efficiency of our proposed method. The Hero game is an outlier here. But our performance is very close to the vanilla MCTS (N 30) while we use half of the search iterations on average. Besides, the number of search times decreases more than that on Go.
To sum up. V-MCTS reducing the total budget of MCTS will encounter a more significant performance drop. In addition, the savings of search cost is more substantial in easier environments.
keep comparable performance under fewer search iterations while simply
5.4 Ablation Study
The results in the previous section suggest that our method reduces the response time of MCTS while keeping comparable performance on challenging tasks. This section tries to figure out which component contributes to the performance and how the hyperparameters affect it. And we also ablate the effects of different normalization criterions in VET-Rule and the larger budget (N) in MCTS.
Virtual Expansion In Section 4.2 we introduce the virtual expansion. To prove the effectiveness of virtual expansion, we compare with another two baseline expansion methods. One is the vanilla expansion, mentioned in Algorithm | which returns at iteration i and outputs πą. Another is greedy simulations
searching the current best action greedily, indicating that कt (s. a) = (N& (s. a) + (N - k)), b=) max N₂ (s.b))/N //N. Briefly, we stop the search process after k 30 iterations and do N k times virtual expansion or greedy expansion or nothing, where k = rN and
expansion, which spends the left N
0.2, N 150.
We compare the winning rate against the same engine, and the results are listed as Table shows. The winning rate of virtual expansion can achieve 32%, which is much better than the others. Besides, MCTS with greedy expansion does work because it over-exploits and results in severe exploration issues. Consequently, virtual expansion can generate better policy distribution because it can balance exploration and exploitation with UCT.

---

Termination Rule It is significant to explore better termination rule to keep the sound perfor- mance while decreasing the tree size as much as possible. As mentioned Section 4.T] VET- Rule has two hyperparameters r,C. Here r is the factor of the minimum budget rN, and
Table 3: Ablation results of different expansion
methods on Go 9 x 9 for 3 separate training runs.
Algorithm
Size Avg.
Winning Rate
Vanilla expansion
30
17% + 3.2%
Greedy expansion
30
3% = 2.0%
is the minimum distance (,, k/2). To ex- plore the VET-Rule with better computation and performance trade-off, we do ablations for the
Virtual expansion
30
32% + 3.5%
different values of and c, respectively. The default values of r, set 0.2, 0.1.
Figure compares the winning rate as well as the average tree size across the training stage. Firstly, Figure ] gives the results of different minimum search times factor r. The winning probability is not sensitive to r when r 2 0.2. Nevertheless, the average tree size is sensitive to because V-MCTS is supposed to search for at least r. times. In addition, there is performance drop between 0.1 reasonable to choose r 0.2 to balance the speed and the performance.
and r = 0.2. Therefore,
Besides, the comparisons of the different minimum distance are shown in Figure 3(b) A larger makes the tree size smaller because Á. (k, k/2) < c is easier to satisfy. In practice, the performance is highly correlated with c. In terms of the winning rate, a smaller outperforms a larger one. However, better performances are at the cost of more computations. We suggest selecting an appropriate minimum distance to balance the computation and performance (r - 0.2, 0.1).
Normalization criterion in VET-Rule The proposed VET-Rule, | - # < is a termination condition for V-MCTS. And L2 norm is another reasonable choice to amplify the bigger deviations. Therefore, we make ablations of the normalization criterion for the policy distributions. Specifically, we take a pretrained model, and compare the different strategies of L1 norm and L2 < E and | fs/)(s)) < e. The results are as Tab. 4 shows. We can find that (1) L2 norm can also work for V-MCTS; (2) L1 norm is better than L.2 norm.
norm, namely, [(x - ft)2(s)]
And we attribute this to the formulation of ucb scores. Because the ucb scores have already taken
into account the difference in the visitations (see the N(s, a) in Eq (1)). Therefore, amplifying the deviations may result in some bias.
Table 4:
Comparison of the winning rate and the average budget with different norm strategies in VET- < c and L.2 Norm means fT (8)
Rule. LI Norm means [s) **/2(s)]|,
#x/2(5) 12 <e.
Average budget
Winning rate
MCTS (N = 150)
150
82.0%
V-MCTS 1.1 Norm, N 150, 0.2, 0.1
96.2
81.5%
V-MCTS L2 Norm, N 150, 0.2, 0.1
97.1
79.8%
V-MCTS L2 Norm, = 150, r = 0.2, E 0.05
119.3
81.0%
Larger budget (N) in MCTS To investigate whether our method still holds with larger amounts of MCTS expansions, we take a pretrained model and compare two strategies: (1) vanilla expansion with
0.2, c = 0.1. The results are listed in Tab. 5 The result shows that (I) V-MCTS(N = S00, r = 0.2, e = 0.1) is better than MCTS (N = 600) in both the average budget and the winning rate, (2) V-MCTS can achieve comparable performance to the oracle MCTS(N 800) while keeping much less average budget. Therefore, V-MCTS works with larger amount of MCTS expansions.
N=150/400/600/800 nodes in MCTS (2) virtual expanded policy with N = 800,
Table 5: Comparison of the winning rate and the average budget with larger amounts of MCTS expansions. Here the hyper-parameters of our method are N = 800, 0.2, 0.1.
MCTS
N 150
N - 400
N 600
N = 800
Ours
Average budget
150
400
600
800
431.1
Winning rate
82.0%
84.5%
84.9%
85.9%
85.0%

---

MCTS
V-MCTS
Black Player
k=92
k=44
k=31
k=148
k=85
k=136
k=31
k=44
k=141
k=129
(a) Play as Black
Board state
MCTS
V-MCTS
While Player
k-120
k-51
k-34
k-40
k-150
k-32
k-144
k-150
k-32
k-88
(b) Play White
Heatmap of policy distributions from the MCTS (N = 150) and the V-MCTS. The agent play as Black in (a) and White in (b) against the GnuGo (level 10). Our agent wins in both of the games. A darker red color represents larger visitations of the corresponding action. The V-MCTS will terminate with different search times according the situations and generate a near-oracle policy distribution.
Figure 3:
5.5 Visualization of V-MCTS's Adaptive Behavior
In this section, display the adaptive mechanism through visualizations and performance analysis. We find that (1) (s) close to x (s); (2) V-MCTS terminates earlier for simpler states.
Specifically, we choose some states at different time steps one game of Go against the GnuGo with a trained model. And Figure 3 the visualization of the policy distributions heatmap. Here we add two games, which contain one black player and one white player. The last two rows in each subfigure are the heatmap visualization for oracle MCTS (x and V-MCTS (fg when A (k, k/2) < <). The darker the color is on the grid, the more the corresponding action is visited during the search. In general, it. is close the NN distinct states, indicating that the virtual expanded policy obtained after virtual expansion is close to the oracle one.
Furthermore, the less valuable actions there are, the sooner the V-MCTS will terminate. For example, on Go games, the start states are usually not complex because there are only few stones on the board, but the situations are more complicated in shuban, the closing stage of the game. Notably, termination occurs earlier the start states (columns 1, 2, 3), but is the opposite when situation is more complicated. More importantly, the termination step A: is not related to the number of Go pieces. Therefore, we can conclude that V-MCTS makes adaptive terminations according the situations of the current states and generate near-oracle policies. Specifically, it terminates the search loop earlier when handling easier states, which has better computation and performance trade-off.
6 Discussion
This paper proposes novel method named V-MCTS accelerate the MCTS to determine the termination of search iterations. It can maintain comparable performances while reducing half of the time to search adaptively.
believe that this work can one step toward applying the MCTS-based methods to some real-time domains. One limitation of our work is that it cannot deal with the environments of continuous action space. In the future, we will plan to extend to the continuous action space with early termination.
10

---

Acknowledgments and Disclosure of Funding
This work is supported by the Ministry of Science and Technology of the People Republic of China, the 2030 Innovation Megaprojects "Program on New Generation Artificial Intelligence" (Grant No. 2021AAA0150000). This work is also supported by grant from the Guoqiang Institute, Tsinghua University.
References
[1] H. Baier and M. H. Winands. Mcts-minimax hybrids. IEEE Transactions Computational Intelligence and in Games, 7(2):167-179, 2014.
[2] H. Baier and M. H. Winands. Mcts-minimax hybrids with state evaluations. Journal of Artificial Intelligence Research, 62:193-231, 2018. 2018.
[3] B. Bouzy and T. Cazenave. Computer go: an ai oriented survey, Artificial Intelligence. 132(1))39-103, 2001.
[4] B. Bouzy and B. Helmstetter. Monte-carlo go developments. In Advances in computer games. pages 159-174. Springer, 2004.
[5] D. Bump, M. L. Li, W. Iba, and et al. Gnugo, 2005.
[6] X. Cai and D. C. Wunsch. Computer go: A grand challenge ai. Challenges for Computational Intelligence, pages 443-465, 2007.
[7] R. Carnap. Logical foundations of probability. 1962.
[8] G. Chaslot, S. Bakkes, I. Szita, and P. Spronck. Monte-carlo tree search: A new framework for game ai. AIIDE, 8:216-217, 2008.
[9] R. Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In Interna- tional conference on computers and games, pages 72-83. Springer, 2006.
[10] I. Danihelka, A. Guez, J. Schrittwieser, and D. Silver. Policy improvement by planning with gumbel. In International Conference on Learning Representations, 2022.
[11] S. Gelly and D. Silver. Combining online and offline knowledge in uct. In Proceedings of the 24th international conference on Machine learning, pages 273-280, 2007.
[12] Gelly and D. Silver. Achieving master level play in 9 computer go. In AAAI, volume pages 1537-1540, 2008.
[13] S. Gelly and D. Silver. Monte-carlo tree search and rapid action value estimation in computer go. Artificial Intelligence, (7((1)::156-1188 2011.
[14] S. Gelly, Y. Wang, R. Munos, and O. Teytaud. Modification of UCT with patterns in Monte Carlo Go. PhD thesis, INRIA, 2006.
[15] J.-B. Grill, F. Altché, Y. Tang, T. Hubert, M. Valko, I. Antonoglou, and R. Munos. Monte- carlo tree search regularized policy optimization. In International Conference Machine Learning, pages 9769-3778. PMLR, 2020.
[16) T. Haarnoja, A. Zhou, P. Abbeel, and S. Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International conference on machine learning, pages 1861-1870. PMLR, 2018.
[17] M. D. Hoffman, D. M. Blei, C. Wang, and Paisley. Stochastic variational inference. Journal of Machine Learning Research, 14(5), 2013.
[18] C.H.. Hsueh, I.-C Wu, W.-. Tseng, S.-J. Yen, and J.-C. Chen. An analysis for strength improvement of an mets-based program playing chinese dark chess. Theoretical Computer Science, 644:63-75, 2016.

---

[19] E. Huang. Gymgo. httpps///t thub. www.ub..ommaggaaaia htt.ghhw....m.aaiggg////////aaaa
2021.
[20] L. Kocsis and C. Szepesvári. Bandit based monte-carlo planning. In European conference machine learning, pages 282-293. Springer, 2006.
[21] L.-C. Lan, M.-Y. Tsai, T.-R. Wu, I. Wu, C.-J. Hsich, et al. Learning to stop: Dynamic simulation monte-carlo tree search. arXiv preprint arXiv:2012.07910, 2020.
[22] R. Lorentz. Early playout termination in mets. Advances in Computer Games, pages 12-19. Springer, 2015.
[23] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al. Human-level control through deep rein- forcement learning. Nature, 51897540):52-533,, 2015.
[24] A. Newell. The knowledge level. Artificial intelligence, 18(1)877-227, 1982.
[25] C. D. Rosin. Multi-armed bandits with episode context. Annals of Mathematics and Artificial Intelligence, 61(3):203 2000000--3022200 2011.
[26] S. J. Russell and D. Subramanian. Provably bounded-optimal agents. Journal of Artificial Intelligence Research, 2:575-609, 1994.
[27] J. Schritwieserr, I. Antonoglou, T. Hubert, K. Simonyan, L. Sifre, S. Schmitt, A. Guez, E. Lock- hart, D. Hassabis, T. Graepel, al. Mastering atari, go, chess and shogi by planning with learned model. Nature, 588(7839):044-699 2020.
[28] Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 1:xiv:/707:00 170..06377 2017.
[29] N. Sephton, P. I. Cowling, E. Powley, and N. H. Slaven. Heuristic move pruning in monte carlo tree search for the strategic card game lords of war. In 2014 IEEE Conference on Computational Intelligence and Games, pages 1-7. IEFE, 2014.
[30] D. Silver, A. Huang, C. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, Antonoglou, V. Panneershelvam, M. Lanetot, et al. Mastering the game go with deep neural networks and tree search. Nature, 529(7587):484 4894 2016.
[31] D. Silver, T. Hubert, Schrittieserr, Antonoglou, Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel. et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419):1 1144,14, 2018
[32] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, Huang, A. Guez, T. Hubert, Baker, M. Lai, A. Bolton, al. Mastering the game of go without human knowledge. Nature, 550(7676):354-33) -599554-3599,00 2017.
[33] Y. Wang and S. Gelly. Modifications of uct and sequence-like simulations for monte-carlo go. In 2007 IEEE Symposium on Computational Intelligence and Games, pages 175-182, IEEE, 2007.
[34] W. Ye, S. Liu, T. Kurutach, P. Abbeel, and Y. Gao. Mastering atari games with limited data. In NeurlPS, 2021.
References
[1] H. Baier and M. H. Winands. Mcts-minimax hybrids. IEEE Transactions Computational Intelligence and Al in Games, 7(2):167-179, 2014.
[2] H. Baier and M. H. Winands. Mets-minimax hybrids with state evaluations. Journal of Artificial Intelligence Research, 62:193-231, 2018.
[3] B. Bouzy and Cazenave. Computer go: an oriented survey. Artificial Intelligence, (2(1)):9-1133, 2001.
12

---

[4] B. Bouzy and B. Helmstetter. Monte-carlo go developments. In Advances in computer games, pages 159-174. Springer, 2004.
[5] D. Bump, M. L. Li, W. Iba, and et Gnugo, 2005.
[6] X. Cai and D. C. Wunsch. Computer go: A grand challenge to ai. Challenges for Computational Intelligence, pages 443-465, 2007.
[7] R. Carnap. Logical foundations probability. 1962.
[8] G. Chaslot, S. Bakkes, I. Szita, and P. Spronck. Monte-carlo tree search: A new framework for game ai. AIIDE, 8:216-217, 2008.
[9] R. Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In Interna- tional conference on computers and games, pages 72-83. Springer, 2006.
[10] I. Danihelka, A. Guez, J. Schrittwieser, and D. Silver. Policy improvement by planning with gumbel. In International Conference on Learning Representations, 2022.
[11] Gelly and D. Silver. Combining online and offline knowledge in uct. In Proceedings of the 24th international conference on Machine learning, pages 273-280, 2007.
[12] S. Gelly and D. Silver. Achieving master level play in 9 9 computer go. In AAAI, volume 8, pages 1537-1540, 2008
[13] S. Gelly and D. Silver. Monte-carlo tree search and rapid action value estimation in computer
go. Artificial Intelligence, 175(11) 2011.
[14] Gelly, Y. Wang. Munos, and O. Teytaud. Modification of UCT with patterns in Monte- Carlo Go. PhD thesis, INRIA, 2006.
[15] J.-B. Grill, F. Altché, Y. Tang, T. Hubert, M. Valko, I. Antonoglou, and R. Munos. Monte- carlo tree search as regularized policy optimization. In International Conference on Machine Learning, pages 3769-3778. PMLR, 2020.
[16] T. Haarmoja, A. Zhou, P. Abbeel, and S. Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International conference on machine learning, pages 1861-1877 1870. PMLR, 2018.
[17] M. D. Hoffman,, M. Blei, C. Wang, and Paisley, Stochastic variational inference. Journal of Machine Learning Research, 14(5). 2013.
[18] C.-H. Hsueh, L.C. Wu, W.-. Tseng, S.-J. Yen, and J.-C. Chen. An analysis for strength improvement of an mets-based program playing chinese dark chess. Theoretical Computer Science, 644:63-75, 2016.
[19] E. Huang. Gymgo. https: /tte::///ttttbb http:://ggttubb..mmm/igggoog/// cwt.a/iigogggoor///ottoooo 2021.
[20] I.. Koesis and C. Szepesvári. Bandit based monte-carlo planning. In European conference machine learning, pages 282-293, Springer, 2006.
[21] L.-C. Lan, M.-Y. Tsai, T.-R. Wu, I. Wu, C.-J. Hsich, et al. Learning to stop: Dynamic simulation monte-carlo tree search. arXiv preprint arXiv:2012.07911 2020.
[22] R. Lorentz. Early playout termination in mets. Advances in Computer Games, pages 12-19. Springer, 2015.
[23] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al. Human-level control through deep rein- forcement learning. Nature, 51807540::59-533, 2015.
[24] A. Newell. The knowledge level. Artificial intelligence, 18(1):87 1982.
[25] C. D. Rosin. Multi-armed bandits with episode context. Annals of Mathematics and Artificial Intelligence, 61(3):203-230 2011.
13

---

[26] J. Russell and D. Subramanian. Provably counded-optimal agents. Journal of Artificial Intelligence Research, 2:575 609, 1994.
[27] Schrittwieser, I. Antonoglou, T. Hubert, K. Simonyan, L. Sifre, S. Schmitt, A. Guez, E. Lock- hart, D. Hassabis, T. Graepel, al. Mastering atari, go, chess and shogi by planning with learned model. Nature, 588(7839):604 609, 2020.
[28] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 110.110077.3333 2017.
[29] N. Sephton, P. I. Cowling, Powley, and N. Slaven. Heuristic move pruning in monte carlo tree search for the strategic card game lords of war. In 2014 IEEE Conference on Computational Intelligence and Games, pages 1-7. IEEE, 2014.
[30] D. Silver, A. Huang, C. Maddison, Guez, Sifre, G. Van Den Driessche, Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484 489, 2016.
[31] D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419):1 4044144, 2018.
[32] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, al. Mastering the game of go without human knowledge. Nature, 350(7676):34-359,, 2017.
[33] Y. Wang and S. Gelly. Modifications of uct and sequence-like like simulations for monte-carlo go. In 2007 IEEE Symposium on Computational Intelligence and Games, pages 175-182. IEEE, 2007.
[34] W. Ye, S. Liu, T. Kurutach, P. Abbeel, and Y. Gao. Mastering atari games with limited data. In NeurIPS, 2021.
14


Reviews:
[{"review_id": "a58NooVzSEX", "reviewer": "Reviewer_7jdS", "summary": "This paper proposed a novel method named Virtual MCTS (V-MCTS) to reduce the computation time of vanilla MCTS with the Virtual Expended Termination Rule (VET-Rule). This paper also gives theoretical bounds of the proposed method and evaluates the performance and computations on 9 × 9 Go board games and Atari games. Experiments show that this method can achieve comparable performances to the original search algorithm while requiring less than 50% search times on average. In general, this paper shows that V-MCTS can think faster on simple states and longer on hard states. For solid theoretical analysis and positive experimental results, I would recommend the acceptance of this paper. \n", "questions": "According to the proof given by the authors, V-MCTS’ Error Bound is still effective for programs that do not use virtual expansions during training. We should be able to apply V-MCTS to all pre-trained Top Go 19x19 programs, like KataGo or Leela Zero. How does V-MCTS work on these strong programs?\n\nSome minor comments about presentations. \n* In experiments, N = 150. I am just wondering what N_0 would be to satisfy Theorem 4.2, if N=150. \n* It is unclear about ‘3 different runs’ in Tables 1~3. The authors need to clarify it. \n* Please keep the consistency of the symbols, for example, $\\epsilon$ and $eps$.\n* Line 186: highlighted in line 5 -> highlighted in line 6\n* In Algorithm 3, the symbols in line 10 are unclear and confusing to the reader. Explain why the ratio (the visitation of an action in a state divided by N) is the policy of this state. Where is that action? This conflicts with the situation in line 8.\n", "limitations": "Yes", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths*\n\n* This paper gives the theoretical bounds of the proposed method with proof. Namely, for any given epsilon with sufficient large N, if the policy distance between k and k/2 is smaller than epsilon, then the distance between k and N is smaller than 3*epsilon. This theoretical result supports an early stop of MCTS search, which I believe has some impact. The theoretical analysis is sound, after I verify the proofs of Theorem 4.1 and 4.2 in Appendix (a little bit hard to read though).\n* In the experiments with Go 9x9 and Atari, V-MCTS shows that this method can achieve comparable performances to the original search algorithm while requiring less than 50% search times on average. \n* There is a comparison with DS-MCTS (a past work in AAAI), and V-MCTS still has better performance.\n\n*Weaknesses*\n\nSome minor presentation problems listed in Questions Section. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "YdW1cVlFfj", "reviewer": "Reviewer_oRW8", "summary": "The authors introduce Virtual MCTS which approximates its vanilla version with a smaller amount of computations. They also perform theoretical analysis as well as empirical performance analysis on 9x9 Go and the Atari game. \n", "questions": "Does Virtual MCTS attempt the time required for MCTS only when a model is trained? Or does it also attempt to reduce the time when playing a game against its opponent?\n\nIt apparently does not look Algorithms 1-2 are for the latter case. \n", "limitations": "NA\n", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "While the topic seems reasonable, I have a difficulty in understanding the problem they attempt to address (see the questions).  Typically game-playing programs have time management algorithms but the authors does not mention the approach.  \n\nFor example, \n\nhttps://dke.maastrichtuniversity.nl/m.winands/documents/time_management_for_monte_carlo_tree_search.pdf\n\nhttps://www.remi-coulom.fr/Publications/TimeManagement.pdf\n\nIn addition, their comparison is against vanilla UCT. But another naive baseline is to stop UCT if the best move is much better than the others. It could be estimated by considering the number of visits and the reward received so far.\n\nMisc. \nPage 3: \"Equation (1)\"\n\nIs this correct?\n\nPage 3: \"Thus, MCTS-based RL is roughly N times computationally more expansive than traditional RL algorithms\"\n\nexpensive\n\nPage 3: \"It is consists of two components:\" \n\nIt consists of\n\nPage 4: \"... illustrated in Algorithm 1, 2\"\n\nAlgorithms 1 and 2\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WpMGchitMkh", "reviewer": "Reviewer_wBBJ", "summary": "This paper proposes a modification to the Monte-Carlo Tree Search paradigm---specifically, the UCT algorithm---that is more sample efficient. The method attempts to use its \"thinking time\" more wisely: as the authors describe it, their tree-building algorithm seeks to spend more time when evaluating \"harder\" states and less time on \"simpler\" states (i.e., states that are less positionally complex, and where the best action can be determined more easily). Identifying these situations is accomplished by noting when additional iterations of search would not appreciably change the visitation distribution of the actions at the root node (i.e., the stochastic policy at the root node). Specifically, on each iteration of tree-building, after the traditional loop of node selection-expansion-evaluation-value propagation is completed, some additional computation is performed -- what the authors term \"virtual expansions\". In this phase, $N-k$ \"pulls\" of the arms of the root node are performed, according to the selection strategy (for eg., UCB1), _but without descending down the tree further_ ($N$ = total search budget measured by iterations, $k$ = current iteration index). Instead, after each pull, the current average utiltity of that action $Q(s, a)$ is used as the reward, so that the only modification to the statistics accumulated in the nodes at level 1 in the search tree are in the visitation counts. The policy induced by the combination of \"regular\" tree-building and virtual expansions is tracked over time; when it begins to show signs of convergence (i.e., the norm between the policies from two sufficiently different iterations is sufficiently small), the search is terminated. The authors provide two theorems that characterize the nature of this convergence, as well as empirical evaluation in several domains---9x9 Go and five Atari games---to demonstrate the validity and benefit of their approach.", "questions": "(1) In all of the comparisons, V-MCTS was upper-bounded in how large a tree it could build. A complementary analysis where it was given a fixed _time_ budget would have been useful to see: to see if given a fixed amount of time, it could make better decisions than a vanilla MCTS using the same amount of time.\n\n(2) The convergence criterion appears to rely on when the L1 norm of the policy at the root node converges; but I'm wondering if this is the best choice. There is an argument to be made for the L2 norm instead: bigger deviations should be amplified more, over an accumulation of smaller deviations, as this could change what action would be picked at the root. Or to ignore the specific distribution and focus on the _ordering_ of the nodes. It would be interesting to hear from the authors whether these alternatives were considered.\n\n(3) Lines 58--59: \"Afterward, UCT algorithms have generally replaced earlier heuristic methods for Monte-Carlo tree search (MCTS), which apply UCB1 to select action at each node of the tree\" -- this framing not quite accurate. UCT is a specific instantiation of the MCTS family of algorithms, so saying it has \"replaced\" MCTS doesn't quite make sense.\n\n(4) Lines 63--65: \"There are three kinds of bottlenecks in vanilla MCTS in the aspect of speed: the selection stage of each iteration, the evaluation stage of each iteration, and the search loop.\" -- I found this confusing, since the search loop _includes_ selection and evaluation steps.\n\n(5) Line 5 in Alg. 1, Line 9 in Alg. 2 -- I believe these should read UCB1(Q, P, N), rather than UCT(Q, P, N) (UCT is the overall algorithm, UCB1 (or a variant) is the bandit algorithm that is handling the selection step). Similarly, Line 4 in Alg. 3 -- should probably read \"Selection with UCB1\".\n\n(6) In Theorem 4.1(a), what does the $\\Cup$ (set intersection) mean? Did you mean $\\Wedge$, i.e., an AND over the bounds on all possible actions?\n\n(7) There are also typos and grammatical issues throughout the paper, that could be eliminated with a careful and thorough read through. Here's a small sampling just from the first page:\n11--12: \"while requiring less than 50% number of search times on average.\" --> \"less than 50% search time\"\n19: \"recent AI researches\" --> \"research\"\n26--27: \"It is the first time for a computer program to beat a human professional Go player.\" --> \"first time a computer program beat a human...\"\n29--30: \"Later, MCTS-based RL algorithms are further extended to other board games and Atari games\" --> Later, MCTS-based RL algorithms were further extended...\"\n32--33: \"...they require massive computations to train and evaluate.\" ---> \"...they require massive amounts of computation...\"\n", "limitations": "Yes -- any concerns have been raised in other sections.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality:\n(+) The simplicity of the approach is a strength in my opinion. The idea is fairly straightforward, and the fact that it results in significant gains in a number of application domains is noteworthy.\n\nSignificance:\n(+) MCTS is of broad interest in the ML and AI communities and papers that deal with enhancements to the baseline algorithm or propose novel applications are often published at NeurIPS. So the paper is likely to be of interest to many researchers.\n\nQuality:\n(+) The paper contains a nice balance of theory and experiment. The main theorems suggest that the authors' proposed approach should provide some benefits, and the empirical evaluation reinforces this.\n(+) The gains in performance are particularly strong in 4/5 Atari domains, where V-MCTS (the authors' approach) outperforms vanilla MCTS while building much smaller search trees (typically, only 50% as big).\n(+) The ablation experiments involving tuning the algorithm hyperparameters $r$ (the search budget ratio) and $\\epsilon$ (which determines the tolerance criterion for convergence) were useful for evaluating their impact on performance.\n(-) The results in 9x9 Go were however less compelling to me. The evidence here did not appear to support the authors' conclusions -- vanilla UCT was shown to be a little slower to act, but also a little stronger as a player. So claiming that V-MCTS was somehow preferable here, or a superior choice (265--266: \"Therefore, such termination rule can keep strong performances with less budget.\") is not borne out by the data.\n(-) The qualitative analysis in Fig. 3 about V-MCTS spending more time in challenging positions and less time in less complex positions was welcome, but drawing such samples from a single game seems a little anecdotal. Aggregating information over many more such positions would have made for a stronger argument and paper. \n\nClarity:\nUnfortunately, this was the weakest element of the paper, which relegates it to a borderline accept\nin my eyes. The lack of clear writing and visualizations made it harder to evaluate some of the claims; it also raises questions about the reproducibility of the work. More specifics are provided in the next section, but I outline some broad issues here.\n(-) No details are provided about the training procedure. EfficientZero is mentioned in Section 5.1, but it's not clear if that was the training procedure that was used. It's not clear if the code for reproducing the results will be made available.\n(-) I found Fig. 1(a) difficult to understand, as it lumps together different algorithms that are being parameterized in different ways. I was also a little confused by why there was a _curve_ for GnuGo, which is an off-the-shelf Go playing engine -- presumably, the authors did not retrain this agent from scratch, so why are there different points along the $x$-axis for this player?\n(-) The proofs for theorems 4.1 and 4.2 are presumably in the Appendix, so their proofs could not be verified; while I understand the authors are operating under space constraints, it would have been nice to at least see a proof sketch.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QxGg0TO-cyG", "reviewer": "Reviewer_Gvr7", "summary": "This paper proposes V-MCTS, containing two main improvements over classic MCTS. First, the authors propose virtual expansion by applying rollout without actual simulation (the simulation returns are replaced by the current Q value. Next, V-MCTS uses an adaptive termination condition to decide when to stop doing rollout. The proposed algorithm is evaluated on 9x9 Go and five Atari games.", "questions": "- How does virtual expansion compare with other action selection strategies (e.g., select by Q value, and some BAI strategies)?\n\n- The empirical results are only tested with very few number of rollouts (<20 rollouts on Atari, and <150 on Go), and it remains unsure whether the proposed techniques are useful in more general cases.", "limitations": "The authors addressed the limitations and potential negative societal impact of their work.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Improving the efficiency of MCTS is very important since they typically require a huge amount of computation resources. This paper proposes two techniques: virtual expansion and an early-termination condition.\n\nVirtual expansion aims to mitigate the problem that exploratory behavior of the MCTS rollouts can \"mask out\" information about the action with the highest expected reward. For example, if the agent is given a budget of 100 rollouts and it has only figured out a promising path at the 95th rollout. The last 5 rollouts may not be sufficient to backpropagate this information up to the root node. In such cases, applying virtual expansion to backpropagate such information could be helpful. This is also justified by the ablation study in Sec. 5.4.\n\nHowever, while virtual expansion could be useful in the above-mentioned scenario, I think it (i) could be implemented by an action selection policy for best-arm identification (BAI) and (ii) might only be useful in games with less chaotic rewards. (i): For example, it is possible that simply selecting the action that leads to the best cumulative reward seen in the rollouts can be as good as virtual expansion. (ii): For tasks where the reward function has high variance, it seems possible that virtual expansion will be fooled by some high rewards collected by chance. To allow better justification of the virtual expansion idea, it would be great if the authors could compare it with other action selection strategies (e.g., select by Q value, and some BAI strategies).\n\nThe theoretical analysis in the paper shows that V-MCTS will converge to the optimal policy as the number of rollouts increases, but it does not provide additional intuition on the comparison between vanilla MCTS and V-MCTS. Specifically, according to Thm 4.1, we still need k to be sufficiently large in order to guarantee e.g. BAI. Also, the theorems do not take into consideration the early-termination condition.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept