Spending Thinking Time Wisely: Accelerating MCTS with Virtual Expansions
Authors: Weirui Ye
Pieter Abbeel
Yang Gao
Venue: ICLR 2022 Submitted (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 rational" exists in theory but it is impossible to achieve in practice. Recently, Monte-Carlo tree search (MCTS) has attracted considerable attention due to the significant improvement of performance in varieties of 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 mimics the human behavior that spends adequate amounts of time to think about different questions. Inspired by this, we propose a strategy that converges to the ground truth MCTS search results with much less computation. We give theoretical bounds of the V-MCTS and evaluate the performance in $9 \times 9$ Go board games and Atari games. Experiments show that our method can achieve similar performances as the original search algorithm while requiring less than $50\%$ number of search times on average.
We believe that this approach is a viable alternative for tasks with limited time and resources. 

Under review as a conference paper at ICLR 2022
SPENDING THINKING TIME WISELY: ACCELERATING MCTS WITH VIRTUAL EXPANSIONS
Anonymous authors Paper under double-blind review
ABSTRACT
One of the most important AI research questions is trade off computation ver- sus performance, since "perfect rational" exists in theory but it is impossible to achieve in practice. Recently, Monte-Carke tree search (MCTS) has attracted con- siderable attention due to the significant improvement of performance in varieties of 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 adequate amounts of time to think about different questions. Inspired by this, we propose a strategy that converges to the ground truth MCTS search results with much less computation. We give thcoreti- cal bounds of the the proposed method and evaluate the performance in 9 9 Go board games and Atari games. Experiments show that our method can achieve similar performances as the original search algorithm while requiring less than 50% number of search times on average. We believe that this approach is viable alternative for tasks with limited time and resources.
INTRODUCTION
When artificial intelligence was first studied in the 1950s, researchers seek to answer the question of what the solution the question if the agent were "perfect rational". The term "perfect ra- tional" here refers to the decision made with infinite amounts of computations. However, without taking into consideration the practical computation time, one can only solve small-scale problems, since classical search algorithms usually exhibit exponential running time. Recent Al researches no longer seek to achieve "perfect rational", but instead carefully trade-off computation versus the level of rationality. People have developed computational models like "bounded optimality" to model these settings (Russell & Subramanian 1994). The increasing level of rationality under the same computational budget has given lot of AT successes nowadays. Notable algorithms include the Monte-Carke sampling algorithms, the variational inference algorithms, and using neural networks as universal function approximators (Coulom) 2006 Chaslot al. 2008 Gelly & Silver 2011
Silver et al. 2016 Hoffman et al. 2013).
More recently, VICTS-based RL algorithms have achieved lot of success, mainly in board games. The most notable achievement is that AlphaGO beats Hui Fan in 2015 (Silver et al. 2016). This is the first time that a computer program beats a human professional player. After that, AlphaGo beats two top-ranking human players, Lee Sedol in 2016 and Jie Ke in 2017, the latter of which rank first worldwide at the time. Later, the MCTS-basee based RL algorithms are further extended to other board games, as well as the Atari video games (Schrittwieser et al. 2020). EfficientZero (Ye et al.) (02T) greatly improves the sample efficiency of MCTS-based RL algorithms, shedding light on its future applications in real-world applications like robotics and self-driving.
Despite the impressive performance of MCTS-based RI. algorithms, they require massive compu- tations to train and evaluate. For example, |Schiitwieser et al.) (2020) used 1000 TPUs trained for 12 hours to learn the game of GO, and for a single Atari game, it needs 40 TPUs to train 12 hours. Compared to previous algorithms the Atari games benchmark, it needs around two orders of mag- nitude more compute. This prohibitively large computational requirement has slowed down both the further development of VICTS-based RL algorithms, well as its practical use.
Under the hood, NCTSSbased RL algorithms are model-based methods, that imagine what the fu- tures look like when doing different future action sequences. However, this imaging process for the

---

Under review as a conference paper at ICLR 2022
current method is not computationally efficient. For example, AlphaGo needs to 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 (Silver et al. 2016). Besides being computation- ally inefficient, the current MCTS algorithm deals with easy cases and hard ones with the same computational budget. On the other hand, human knows to use their time when it is most needed.
In this paper, we aim to design new algorithms that save the computational time of the MCTS-based RL methods. More specifically, we are interested in pushing the Pareto front of the rationality level computation curve. Empirical results show that our method can achieve comparable performance while requiring less than 50% simulations search on average.
2 RELATED WORK
2.1 MULEI- BANDIT PROBLEM
RL. algorithms are always brought into the exploration and exploitation dilemma. Multi-armed ban- dit (MAB) problem (Berry & Fristedt 1985) Auer et al. 2002 Lattimore & Szepesvári (020) is one of the most extensively studied but fundamental instances. The K-armed MAB problem a sequen- tial game with a collection of K unidentified but independent reward distributions, each associated with the corresponding arms. For each round, the learner pulls an arm and receives reward sampled from the corresponding distributions. The optimal policy of the learner for the MAB problem is to maximize the cumulative rewards obtained from the sequential decisions.
In the case where the cost of pulling arms is little, the learner is allowed to trial and error for enough times until convergence. series of upper confidence bound (UCB) algorithms (Auer et al. 2002 Bubeck & Cesa-Bianchi 2012) are proposed to solve the stochastic MAB problem and they have theoretical bounds. When there exist costs for each trial, pure exploration attempts to make the best use of the finite trials (Bubeck et al. 2011 Lattimore & Szepesvári 2020). Kocsis & Szepesvári (206) proposed UCT to adapt UCB algorithms to the tree structures, which is the basis of MCTS.
2.2 REINFORCEMENT LEARNING WITH MCTS
For long time, Computer Go is regarded as a very challenging game (Bouzy & Cazenave 2001
Cai & Wunsch] 2007). Researchers attempt to use Monte-Carlo techniques that evaluate the value of the node state through random playouts (Bouzy & Helmstetter) 2004] Gelly & Silver 2007 2008
Silver al. 2016). Afterwards, UCT has generally replaced those earlier heuristic methods for Monte-Carlo tree scarch (MCTS). UCT algorithms (Kocsis & Szepesvári, 2006 apply UCBI to select action at each node of the tree. Recently, MCTSS-based methods (Silver al., 2016 2017 2018 Schrittwwessr et al. 2020) have become increasingly popular and achieved super-human per- formances board games because of the strong ability to search. Modern MCTS-based RL algo- rithms include four stages in each search iteration, namely simulation: selection, expansion, eval- uation, and backpropagation. The selection stage targets selecting a new leaf node with UCT. The expansion stage expands the selected node and updates the search tree. The evaluation stage evalu- ates the value of the new node. The backpropagation stage propagates the newly computed value to the nodes along the search path to obtain more accurate Q-values with Bellman backup. However, search quite time-consuming, which prevents MCTS- -based methods to be used in wider scenarios.
2.3 ACCELERATION OF MCTS
There are two kinds of bottlenecks in MCTS in the aspect of speed: the evaluation/selection stage of each iteration and the outer search loop. In the previous research, people attempted to evaluate the node value by random playouts to the end of the game, which makes the evaluation stage quite expensive. In addition, compared to other model-free RL methods like PPO (Schulman et al.) (017) and SAC (Haarnoja et al., 2018), MCTS-based algorithms have much larger computations due to the search loop. Therefore, a lot of works are devoted to accelerating MCTS. Some heuristic pruning methods (Gelly et al. 2006. Wang & Gelly 2007 Sephton et al., 2014: Baier & Winands 2014; 2018) are developed to make the selection evaluation more effectively.
porentz[(2155 proposed early playout termination of MCTS (MCTS-EP EPT) to stop the random playouts early and use an evaluation function to assess win or loss, which is an improvement in the evaluation stage of normal
2

---

Under review as a conference paper at ICLR 2022
MCTS. Anuhh et al. (2 applied MCTS-EPT to the Chinese dark chess, Afterwards, MCTS- EPT similar ideas have been applied in the evaluation stage of AlphaGoZero Siiver et al. [017)) and later MCTS- methods (Silver et al. 2018 [chrittwieser et al. 2020 Ye et al. 2021] including our baseline models. They evaluate the Q Q-values through evaluation networks instead of running playouts the end. However, these methods focus the specific stage of the search iteration to accelerate the MCTS. We propose Virtual MCTS, which aims to terminate the outer search iteration adaptively in MCTS under distinct circumstances without sacrificing the final policy quality,
BACKGROUND
The AlphaGo series of work (Silver et al., 2016 2017 2018 Schrittwieser et al. 2020) are all MCTS-based reinforcement learning algorithms. Those algorithms assume the environment tran- sition dynamics are known or leam the environment dynamics. Based on the dynamics, they use the Monte-Carlo tree search (MCTS) as the policy improvement operator. L.c taking in the current policy, MCTS returns better policy with the search algorithm. The systematic search allows the MCTS-based RI algorithm to quickly improve the policy, and perform much better in the setring where a lot of reasoning is required. MCTS the core component in the algorithms like AlphaGo.
3.1 MCTS
In this part, give brief introduction the MCTS method implemented in reinforcement learning applications. MCTS takes in the current MDP state and runs a search algorithm guided by the current policy function. It outputs an improved policy of the current state. The improved policy is later to select an action in the environment. In the selection stage, an action will be selected by maximizing over UCB. Specifically, AlphaZero (Silver al. 2018) and MuZero (Schrittwieser et al. 2020) are developed based on a variant of UCB, P-UCT (Rosin) 2011) and have achieved great success on board games and Atari games. The formula of P-UCT in the two methods is the Eq [
VE, ((s a = arg max Q(8,a) P(8, a) 1 (s,
E ((, + + 1
[1 + log
(I)
aEAA
C2
where k is the index of the iterative step, A is the action set, Q(s, a) is the estimated Q-value, P(s. a) is the policy prior obtained from neural networks and (s, a) is the visit counts to select the action from the state The output of MCTS is the visit count of each action of the root node. After N search iterations, the final policy x (s) is defined as the normalized root visit count distribution (s), where T (s, a) (N(s, a))/ EBeA (ss, b) = N(s, ass,a)/k; kk) A. For simplification, we use Te in place of TT (s) sometimes. In our method,
propose to approximate the final policy (s) with f (s). which we name as a policy candidate, through a new expansion method and a 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 in MCTS- RL are in the MCTS procedure. For each action taken by MCTS, it needs N times neural network evaluations, where N the number of search iterations in MCTS. Traditional RL algorithms, such as PPO (Schulman al. 2017) or DQN (Mnih et al.) 2015), only need a single neural network evaluation per action. Thus, MCTS-based RL. roughly N times computationally more expansive than traditional RL algorithms.
In practice, training a single Atari game needs 12 hours of computation time on 40 TPUs (Schrit- twieser al. 2020). The computation need is roughly two orders of magnitude more than traditional RL algorithms (Schulman et al. 2017), although the final performance of MuZero is much better.
4 METHOD
In this paper, we propose an algorithm named Virtual MCTS to reduce the computation cost of MCTS-based RL algorithms. More concretely, aim to push the front of the Pareto curve of the commpuanccoompttattioonn trade-off. Intuitively, human knows when to make a quick decision and when to make slow decision in different circumstances. It gives the ability to overcome
3

---

Under review as a conference paper at ICLR 2022
more difficult problems without wasting much time easy ones. This situation- behavior is absent in current MCTS algorithms. We propose an MCTS algorithm variant that early terminates the search iteration in MCTS adaptively under distinct situations of states. It is consists of two components, the virtual expansion to estimate the final visit count based on the current partial tree; the termination rule that decides when to terminate based the hardness of the current scenario.
4.1 TERMINATION RULE
We propose to terminate the MCTS early based on the current tree statistics. Intuitively, during the MCTS tree expansion process, if we find that recent searches do not further change the root visitation distribution, then we no longer need to search further. With this intuition in mind, we propose simple modification to the MCTS search algorithm. Let (s) denote the root visitation distribution of the root state s at MCTS expansion iteration k. We propose to terminate when:
[s) (s)2())]la <
where e is a tolerance hyper-parameter. Note that, in MCTS-based RL algorithms, not only the best arm matters but the other arms matter as well. It is because MCTS is used in the exploration process, and we need to make sure proper exploration happens the non-best arms. This seems to be a heuristic rule, without any guarantees whether is close to TN. where N is the original MCTS search iteration. However, we show that under certain conditions, a bound on || (8) - (*/2(>)]] implies bound on [| (s(s))l1.
First of all, we list some notations: A is the index of the current search iteration and N is the number of total search simulations, [s,s, a) is the predicted Q-value output the t-th iteration, (s, a) denotes the total visit counts of the action from the state s after the k-th iteration, the Q-value at k-th iteration is Qu(s, a) = Σe= Re (s, a)/ (s/NN(s,, a). The Lemma here gives brief bound for the ranges of Q-values at different iterations, and the proof is attached in Appendix A.2
Lemma 1 Va E A, given that Re(s,a) a) E [-1,1] and the Qu(3,a) = Erst Nog((n)) R.(e.)) then at No, (e.0)
Ne(s.a)
iteration 1 < kn li < N, Quy (8, Qky (8, S (1
(1 (s,
NN,(
It tells that the future changes of Q-values with N - k further searches are bounded in a small range. Through the virtual expansion that we propose in Section we can generate policy candidate T. to approximate the final oracle policy TN- Furthermore, Lemma measures the distance between the oracle policy n and our current policy candidate मt and the proof is attached in Appendix If the policy candidates ft and kk/2 are close enough, so are 7. and f.. In the proof, we show that N equal to the oracle policy nN- Therefore we conclude that the current policy candidate Åेş a near-oracle policy if the termination rule [|* #tz/2()) | < is satisfied.
[A.2 [A.2]
Lemma 2 Va E A. given that E (0, if 3k E [rN, M1, [s((s) #*/2(())l < 6, then (s) (s))) <e+l-r.
4.2 VIRTUAL EXPANSION IN MCTS
In the derivation above, we assume Ti and n, are directly comparable. Here म, and denote two root node visit count distributions iteration and respectively. However, because the tree is expanded with UCT, they are not directly comparable. UCT is an algorithm that maintains the upper bound of the node values in the search tree. As the number of visits increases, the upper bound would be tighter and the latter visits are more focused on the most promising part of the tree. Thus earlier visit count distributions (smaller iteration number) can exhibit more exploratory distribution, while latter ones (larger iteration number) are more exploitative on promising parts.
To compare म; and πy properly, we propose a method called virtual expansion MCTS. nut- shell, it aligns two distributions by virtual UCT expansions until the constant budget N. When the tree is expanded at iteration i, it has N iterations to go. normal expansion would require evalu- ating neural network N - times for more accurate Q(s, a) estimate for each arm at the root node. Our proposed virtual expansion still expands N - times according to UCT, but ignores the N neural network evaluations and simply assumes that each arm't Q a) does not change. We denote the virtual expanded distribution from π. as a policy candidate म.. By doing virtual expansions on both n; and Ty. we effectively remove the different levels of exploration//xploitaaio in them.
4

---

Under review as a conference paper at ICLR 2022
Algorithm Iteration of Search in MCTS
Algorithm 2 Iteration of Search in MCTS with
Virtual Expansion
1: Current k-th iteration step:
2: Given: P,P.C Qx(5, a), Nx,
Current k-th iteration step:
3: t- Sroat
Given: A, P. (,. a), Ns(s, a), Ns(ss,)
4: repeat do search
3:
5: a' L-UCT(Q,PP N.N)
4: if Not init (s a) then
6: 6- next state(s,
5: Init: N&(8, < (x(s,a)
7: until (N, =0
end if
8: Evaluate the state value R(s.a) and P(s,
7:
9: for along the search path do
(1.a))) 10: Qx+I(s, a) = (s.a) (s.a)))Q..(saal ((6.))
s Soo
9: a" + UCT(Q, P,N)
11: (s,1(s, a) +1
10: Na(s, - ()(
12:
end for
11:
13:
Return Qs+1(s, Ne-1
12: Return (s.o)
The comparisons between the MCTS and the one with virtual expansion illustrated in Algorithm
2 Here we display the complete one-step iteration of MCTS with or without virtual expansion. The time-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 fit a better estimation of Q-values. After total of N iterations, the visit count distribution of the root node N (s) is considered as the final policy T(s). However, in the MCTS with virtual expansions, listed in Algorithm it only searches one step from the root node and selects the action based on the current estimations without changing any properties of the search tree. Furthermore, the virtual visited counts N₂ (s, a) are changed after virtual visits to balance the exploitation and the exploration issue. Then the policy candidate after virtual expansions becomes म (s, a) = N& (s, a)/N instead [s, a)/k: When = N, further searches after the root have effects on the final policy. So have A a) n (s, a). In this way, the final visit count distribution obtained through the virtual expansions is similar to the oracle one.
4.3 V-MCTS ALGORITIM SUMMARY
The procedure of MCTS with the ter- mination rule is listed as 3 Compared with the original MCTS, the line 8-13 are the pseudo code on the termination rule. In each itera- tion, we do some calculations with little cost to judge whether the condi- tion of termination is satisfied. If it is, then the search process terminated
Algorithm Virtual MCTS
Given budget N, state s, conservativeness r, error e
2: for l E N do
Selection with UCT
4: Expansion for the new node
5:
Evaluation with Neural Networks
6:
Backpropagation for updating and visit counts <- N& (s, a)/n
and returns the current policy candi- date (s). Thus, skips the next N - k model predictions from neu- ral networks in the evaluation stage highlighted in line 5. In this way, we can approximate the oracle distri- bution ny by Ah while reducing the budget of N simulations to k. Here,
7:
8:
Virtual expand N nodes and update (i a)
9:
(s) + (s a)/N
10:
if A 2 PN A A * #x/2(s)]1 < then
11:
7(s) + 7 (s)
12:
Break
13:
end if
14: TTs) + m. (s)
2 rN and r hyperparameter of the minimum budget rN. Then we can reduce the tree size by 1/r times at most. However, r cannot be tiny value as the minimum distance of distributions is bounded by r. Otherwise, the termination rule has little effect. In conclusion, this rule tells the MCTS terminate if the policy candidates have verged. On such occasions, the virtual expansion method has similar effects as the real expansion of MCTS to generate near-oracle policy, which can save the time cost of the left N A simulations.
15: end for
16: Return (T))
5

---

Under review as a conference paper at ICLR 2022
Furthermore, in the next section, we do some ablations to further investigate the effects of r, and visualizations to understand why the termination rule works. We name our method Virtual MCTS (V-MCTS), variant of MCTS with termination rule based on the virtual expansion.
EXPERIMENTS
In this section, the goal of the experiments is to prove the effectiveness and efficiency of our proposed algorithm. We compare the performance as well as the cost of the budget of the MCTS-based methods with or without the termination rule. Specifically, we evaluate the board game Go 9 x 9, and few Atari games. In addition, we do some ablations to further examine the effectiveness the virtual expansion and evaluate how sensitive our method is to the hyper-parameters. Finally, we try to understand the adaptive mechanism with visualizations and performance analysis.
5.1 SETUP
)02T) proposed EfficientZero, a variant of MuZero (Schrittwieser et al. 2020) with three extra components to improve the sample efficiency, which only requires 8 GPUs train- ing, and thus it is more affordable. Here we choose the board game Go 9 x 9 as our benchmark environment. The game of Go tests how the algorithm performs challenging planning problem. We also benchmark on few Atari games, which feature complexity on the visual side.
Recently, Ye et al.
As for the Go x we choose Tromp-Taylon rules during training and evaluation. The environment of Go is built based on an open-source codebase, GymGo (Huang (20IT). We evaluate the perfor- mance of the agent against GNU Go v3.8 at level 10 (Bump et al.) 2005) 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 to 6.5 as most papers do. As for the Atari games, we choose games with 100k environment steps, which follows the setting of EfficientZero. We evaluate all these games for 32 distinct seeds.
5.2 COMPARATIVE EVALUATION
We compare our method to EfficientZero with original MCTS, on Go 9 and some Atari games. Figure[Tajillstren the comparisons on Go among different algorithms or models against the GnuGo (level I0) agent. The x-axis the training speed and the y-axis is the winning rate. Here, we train the baseline method with different constant budgets N, noted as the blue points. Besides, we also train the V-MCTS with hyperparameters r 0.2, e 0.1. We evaluate the trained model with different to display the tradeoff between performance and the time cost, noted as the red points. The pink points are the GnuGo with different levels.
The result shows that the performance of V-MCTS is comparable to the MCTS of maximum budget (N = 150) while it requires less time to search. Notably, V-MCTS achieves a 72% winning rate against the GnuGo level 10. Meanwhile, the time cost of our method for a one-step move is 0.12s while the GnuGo engine is 0.18s. For the data points with the winning rate higher than 50%, the V- MCTS is significantly better than the original MCTS considering both the winning cost. Consequently, we believe that such termination rule of MCTS can keep the strong performance while saving lots of budgets, which means our method is effective enough and more time-efficient.
and the time
The training curve presented in Figure Tb illustrates that the budget of search times is quite signifi- cant to the MCTS method. However, the performance of V-MCTS is better than that of MCTS with N = 120 while maintaining an average tree size of less than 80. Furthermore, it is interesting that the tree size varies over training procedures. In the beginning. the outputs of the value network are close to zero because the agent usually draws in self-play and receives the zero reward signal. which means the little changes of Qu, a) during the search. The visit count distribution of the root after virtual expansions is similar to that after real expansions. Therefore, in this stage, the termination condition is easy to meet. Afterward, as the model trained better and receives more diverse reward signals during self-play, the probability of searching some valuable states becomes much larger. The value (s a) varies considerably in each iteration of the search, which results in the changes of distributions of policy candidates. Thus, it is much more difficult for the search process to terminate and leads to a larger number of tree sizes. Finally, with more training steps, the prediction of the policy network is more accurate and then gives stronger prior heuristic knowledge P(s, a) before

---

Under review as a conference paper at ICLR 2022
9x5 Go vs GnuEo (level 10)
9x8 Ge Gnubo (level 10)
50%
8g150
N-0
MCregeatte
2
120
Whn01g Pate
11.
Wheree Rate
0.6
100
0.4
0.4
20
Sea
-00
02
0.2
0.0
0.0
(a) Evaluations of Performance
Wining Rates and Tree Size Training Stage
Figure 1: Performance of Virtual MCTS on Go 9 x 9 against GnuGo (level 10). (a) Evaluating the speed of search and winning rate of MCTS, V-MCTS as well the GnuGo at different levels. The termination rule is able to reduce the search cost while keeping comparable performance and outperforms the GnuGo at level 10 in the aspect of speed and winning rate. (b) Evaluating the winning rate as well as the average tree size in different training phases. The solid lines and dashed lines display the winning probability and the tree size respectively. The dark blue curve is the oracle version of MCTS (N 150) and the red one is the version of V-MCTS. The termination rule can make the tree size adaptive in training with a little loss of performance. Directly reducing N in MCTS (the grey curve with N 90) results in larger performance drop.
Table I: Results from Atari games: scores total 32 seeds 5 environments. Here MCTS
(N = 50) is the oracle version and the best results among those versions except the oracle are marked in bold. V-MCTS outperforms MCTS (N 30) while requiring fewer search times.
MCTS (N = 50)
MCTS (N = 30)
MCTS (N = 10) Ours
Size Avg.
Pong 20.8
17.2
2.1
19.9
13
Breakout
411.1
347.4
309.0
389.2
16
Seaquest
1737.5
930.6
625.6
1340.1
15
Hero 9715.0
7499.1
7310.0
7465.0
15
Qbert
15465.6
7792.9
6035.2
10880.5
17
search. For those actions with higher prior knowledge, the changes of Qx a) have less impact on the UCT scores. The procedure of the virtual expansion is similar to the real expansion. However, the changes of Qs(s, a) are still possible during the search process. Consequently, the average num- ber of tree size keeps in reasonable range, which larger than that in the innocent beginning stage and the minimum budget r.V. Our method can determine whether to continue searching or not.
Apart from the results of Go, we 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, here choose few Atari games study how the proposed method impacts the performance under less necessity of search. We follow the setting of EffcientZero, 100k Atari benchmark, which contains only 400k frames data. The results are shown Table Generally, we find that our method works in 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 much fewer searches, which proves the effectiveness and the efficiency of the termination rule in the tree search method. The Hero game is not an outlier considering the similar performance between N 50 and N 30. Besides, the number of search times decreases more than that Go.
To sum up. Virtual MCTS shapes better policy candidates close to the oracles through the virtual ex- pansion with less cost of the budget. The performance of V-MCTS can keep sound with fewer search iterations while simply reducing the total budget of MCTS will encounter a larger performance drop. In addition, the savings of search cost is more substantial in easier environments.
7

---

Under review as a conference paper at ICLR 2022
9x3 Ge vs GnuEo (level 10)
9x8 Ge Gnubo (level 10)
340
6-0.1
0.8
Aves Age Tiee 9/ DuA TT
120
11.
Rate
0.6
2P0
100
0.4
20
0.4
20
20
10
0.2
0.2
0.0
(a) Ablation of minimum budget r
(b) Ablation of minimum distance
Figure 2: Sensitivity of the termination rules to the hyperparameter r; on Go 9 x 9. The solid lines and dashed lines display the winning probability and the average tree size respectively.
Table 2: Ablation results of different expansion methods on Go 9 9 against GnuGo (level 10).
Algorithm
Size Avg.
Winning Rate
Original expansion
30
16%
Greedy expansion
30
5%
Virtual expansion
30
32%
5.3
ABLATION STUDY
The results in the previous section suggest that our method reduces the response time of MCTS while keeping considerable performance on challenging tasks. In this section, we try to figure out which component contributes to the performance and how the hyperparameters affect
we introduce the virtual expansion and discuss the difference between the MCTS with and without virtual expansion. We compare the MCTS with virtual ex- pansion and another two expansion methods. Here introduce the two methods briefly. One is the original expansion, which does nothing once termination. samples an action directly from T& (s. a) N& a)/k. Another is the greedy expansion, which spends the left N k simula- tions in searching the current best action greedily, indicating that # (s, = (N&(s, a) + (N +)lla=arg max Nx(s.))//N Besides, we stop the search process after iterations regardless of the termination condition, where rN and r 0.2, 150.
Virtual Expansion In Section 4.2
We compare the winning rate against the GnuGo engine and the results are listed as Table 2 shows. All the versions here only search for the given minimum tree size, and the virtual expansion method can still achieve 32% winning rate, which is much better than the others. Notably, MCTS with greedy expansion does not work. It is over-exploitation and results in severe exploration issues. Consequently, the virtual expansion method can generate a better policy distribution because it can balance the exploration and exploitation problem through UCT with further virtual simulations.
Termination Rule Since the virtual expansion provides better choice of policy distributions, is significant to explore better termination rule to keep the sound performance while decreasing the tree size as much as possible. As mentioned Section 4.1 the termination rule sets two hyperpa- rameters e to determine the termination rule. Then we do ablations for the different values of and respectively. The default values of r, are set to 0.2, 0.1 in all experiments here.
Figure compares the winning rate as well as the average tree size across the training stage. Firstly, Figure 2a gives the results of different minimum search times r. The winning probability is not sensitive to when 2 0.2. But the average tree size is sensitive to search for at least rN times. In addition, there is a drop between the performance between r = 0.1 and 0.2. Therefore, it is reasonable to choose 0.2 to balance the speed and the performance.
because V-MCTS is supposed
8

---

Under review as a conference paper at ICLR 2022
Board
Figure 3: Heatmap policy distributions from the MCTS (N 150) and the V-MCTS. A darker red color represents larger visit counts of the corresponding action. The V-MCTS will terminate with different search times & according to the situations and generate a near-oracle policy distribution.
Besides, the comparisons of different minimum distance are shown in Figure A larger makes the tree size smaller because [*)()) ** < c is easier reach. In practical, we find that the performance highly correlated with e. terms of the winning probability, a smaller outperforms larger one. However, the better performance is at cost of larger response time. Therefore, it is a good choice to set = 0.2, = 0.1. We suggest selecting an appropriate minimum distance to balance the performance and the response time.
5.4 VISUALIZATION
In this section, do some visualizations to better understand the behavior of Virtual MCTS. Specif- ically, we choose some states at different time steps on one game of Go against the GnuGo with trained model and visualize the heatmap of policy distribution, Figure shows. In this figure, our player is the black one. The board states are shown in the first row, and the next two rows are the heatmap visualization for oracle MCTS and V-MCTS. The darker the color on the grid, the more the corresponding action is visited during the search. In general, d is close to the at distinct states, indicating that the termination rule is reasonable and effective. The less valuable actions there are, the sooner the V-MCTS will terminate. For example, Go games, the start states usually not complex because there are only a few stones on the board the situations are much more com- plicated in shuban, the closing stage of the game. Notably, the termination occurs earlier in the start states (columns 1, 2) but it the opposite when the situation more complicated. More importantly, the termination step k is not related to the number of Go pieces. And the policy candidate obtained after virtual expansion can be close to the oracle one at distinct states of game. Therefore, we can conclude that V-MCTS makes adaptive terminations according the situations of the current state, which is the key to maintaining comparable performances.
DISCUSSION
In this paper, we propose a novel method named V-MCTS to accelerate the MCTS to determine the termination of search iterations. It can keep comparable performances while reducing half of the time to search adaptively. We are the belief that this work can be one step toward applying the MCTS-based methods some real-time domains.

---

Under review as a conference paper at ICLR 2022
7 REPRODUCIBILITY STATEMENT
The main implementations of our proposed method are in Algorithm 2 and 3 In addition, the settings of the experiments and hyper-parameters we choose are in Appendix A. The proof of the lemma is in Appendix A.2 More significantly, the details of the design of training procedures for Go are around Xppendix A.1.2 Besides, we will release the codebase if this paper accepted.
REFERENCES
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-256 2002.
Hendrik Baier and Mark HM Winands. Mcts-minimax hybrids. IEEE Transactions on Computa- tional Intelligence and Al in Games, 7(2:1677-77, 2014.
Hendrik Baier and Mark HM Winands. Mets-minimax hybrids with state evaluations. Journal of Artificial Intelligence Research, 62: 193-231, 2018.
Donald A Berry and Bert Fristedt. Bandit problems: sequential allocation of experiments (mono- graphs on statistics and applied probability). London: Chapman and Hall, 5(71-87):7-7, 1985.
Bruno Bouzy and Tristan Cazenave. Computer go: an ai oriented survey. Artificial Intelligence, 132 (1):39-103, 2001.
Bruno Bouzy and Bernard Helmstetter. Monte-carlo go developments. In Advances in computer games, pp. 159-174. Springer, 2004.
Sébastien Bubeck and Nicolo Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi- armed bandit problems. arXiv preprint arXiv: (eXiv::204.577/ 124..7211, 2012.
Sébastien Bubeck, Rémi Munos, and Gilles Stoltz. Pure exploration in finitely-armed and continuous-armed bandits. Theoretical Computer Science, 4 2011.
Daniel Bump, Man Lung Li, Wayne Iba, and et al. Gnugo, 2005. URL http:htttt///et gnu org/
software/qnuge cacpauuuggggggg.oo.o gnugo. html
Xindi Cai and Donald C Wunsch. Computer go: A grand challenge ai. Challenges for Computa- tional Intelligence, pp. 443-465, 2007.
Guillaume Chaslot, Sander Bakkes, Istvan Szita, and Pieter Spronck. Monte-carlo tree search: A new framework for game ai. AIDDE, 8:216-217, 2008.
Rémi Coulom. Efficient selectivity and backup operators in monte-carle tree search. In International conference on computers and games, pp. 72-83. Springer, 2006.
Sylvain Gelly and David Silver. Combining online and offline knowledge uct. In Proceedings of the 24th international conference on Machine learning, pp. 273-280, 2007.
Sylvain Gelly and David Silver. Achieving master level play in 9 computer go. In AAAI, volume 8, pp. 1537-1540, 2008
Sylvain Gelly and David Silver. Monte-carlo tree search and rapid action value estimation in com- puter go. Artificial Intelligence, 175(11) :): 1856-1875. 2011.
Sylvain Gelly, Yizao Wang, Rémi Munos, and Olivier Teytaud. Modification of UCT with patterns in Monte- Monte-Carlo Go. PhD thesis, INRIA, 2006.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International confer- ence on machine learning, pp. 1861-1870. PMLR, 2018.
Matthew D Hoffman, David M Blei, Chong Wang, and John Paisley. Stochastic variational infer- ence. Journal of Machine Learning Research, 14(5), 2013.
10

---

Under review as a conference paper at ICLR 2022
Chu-Hsuan Hsueh, I-Chen Wu, Wen-Jie Tseng, Shi-Jim Yen, and Jr-Chang Chen. An analysis for strength improvement of an mets based program playing chinese dark chess. Theoretical Computer Science, 644:63-75,2016.
Eddie Huang. Gymgo. httpps///g..tuub.cco//i/aaaa///
2021.
Levente Koesis and Csaba Szepesvári. Bandit based monte-carlo planning. In European conference on machine learning, pp. 282-293. Springer, 2006.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Richard Lorentz. Early playout termination in mets. In Advances in Computer Games, pp. 12-19. Springer, 2015,
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529-53)) 2015.
Christopher Rosin. Multi-armed bandits with episode context. Annals of Mathematics and Artifi- cial Intelligence, 6 (3)::003-230 2011.
Stuart Russell and Devika Subramanian. Provably bounded-optimal agents. Journal of Artificial Intelligence Research,
1994.
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588(7839);604-609, 2020.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347. 2017.
Nick Sephton, Peter Cowling, Edward Powley, and Nicholas 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, pp. 1-7. IEEE, 2014.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484 2016.
David Silver, Julian Schrittwesser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Mathew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 55077666)3344-33))) 2017.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self self-play. Science, 362(6419)::140-- 1144, 2018
Yizao Wang and Sylvain Gelly. Modifications of uct and sequence-like like simulations for monte-carlo go. In 2007 IEEE Symposium on Computational Intelligence and Games, pp. 175-182. IEEE, 2007.
Weirui Ye, Shaohuai Liu, Thanard Kurutach, Pieter Abbeel, and Yang Gao. Mastering atari games with limited data. In NewrIPS, 2021.
A APPENDIX
A.1 EXPERIMENTAL SETUP
A.1.1 MODELS AND PAREM-TAR
Model Design As for the architecture of the networks, we follow the implementation of Effi-
cientZero Ye et al. 2021) in Atari games, which proposes three components based MuZero:
11

---

Under review as a conference paper at ICLR 2022
self- superviee consistency, value prefix, and off off-policy correction. In the implementation of Effi- cientZero, there are a representation network, a dynamics network and reward/value/policy predic- tion network. The representation network is to encode observations hidden states. The dynamics network is to predict the next hidden state given the current hidden state and an action. The re- ward/value/poliey prediction network is predict the reward/valuc/polig) Notably, they propose keep temporal consistency between 92+1 and the predicted state š1+1- The training objective is:
(.) Au,( + A2 + Az v+) + da Cimiiiiluryy (8141, 81+1) + c||0||
(2)
[()) - unroll 1=0
(i+((0),
where Ug Te. 2t are the target reward/policy/value of the state St and rt. Pt. Us are the predicted reward/policy/value of the state respectively. The prediction will do (unoll 5 times iteratively for the state on both Go and Atari games. We do some changes when dealing with board games. For example, we remove the reward prediction network because the agent will receive reward only the end of the games. The other major changes for board games are listed as follows.
Since the board game Go is harder than the Atari games, we add more residual blocks (two times blocks), Specifically, we use 2 residual blocks in the representation network, the dynamics network as well as the value/policy prediction network on Go 9 x while EfficientZero uses only residual block in those networks on Atari games. As for the representation network, we remove the down- sampling part here because there is need to do downsampling for Go states. In the value/policy prediction networks, we enlarge the dimension of the hidden layer from 32 to 128. Besides, con- sidering that the reward is sparse Go (only the final value) and the collected data sufficient, we only take the self-supervised consistency component in EfficientZero to give more temporal supervision during training.
Hyper-parameters In each case, we train EfficientZero for unrolled 5 steps and mini-batchin of size 256. Besides, the model is trained for 100k batches with 100M frames of data in board games while 100k batches with 400k frames in Atari games. We stack 8 frames in board games without frameskip while stacking 4 frames Atari games with frameskip of During both training and evaluation, EfficientZero chooses 150 simulations of budget for each search in board games while 50 simulations of budget in Atari games. Other hyper-parannn peper-parameters are listed in Table
Go
Atari
Maximum number of tree size Observation nown-sampling
150
50
No
96 x 96
Total frames
100M
400k
Replay buffer size
2M
100k
Max frames per episode
163
108k
Cost of training time
24h
8h
Komi of Go
6.5
Frame stack
8
4
Frame skip
Training steps
100k
100k
Mini batch
256
256
Learning rate
0.05
0.2
Weight decay (c)
0.0001
0.0001
Reward loss coefficient (X1)
0
Policy loss coefficient (A2)
1
Value loss coefficient (Aa)
I
0.25
Consistency loss coefficient (A4)
2
0.5
Dirichlet in P-UCT
0.03
0.3
1.25
1.25
02 in P-UCT
19652
19652
0.1
0.1
0.2
0.2
Table 3: Hyper-parameters of V-MCTS on Go 9
and Atari games
12

---

Under review as a conference paper at ICLR 2022
A.1.2 TRAINING DETAILS OF Go
The detailed implementations of Atari games are discussed in EfficientZero (Ye et al. 2021). How- ever, it is nontrivial to adapt to board games. Here we give detailed instructions for training board games Go 9 x 9 in our implementations.
Inputs We follow the designs of AlphaZero and we use the Tromp- Taylor rules, which is similar to previous work (Silver et al. 2018, Schrittwieser et al. 2020). The input states of the Go board are encoded into 17 x 9 9 arry which stacks the historical 8 frames and uses the last channels C' to identify the current player, O for black and for white. Notably, the one historical frame consists of two planes YJ, where the first plane X represents the stones of the current player and the second one [Y'] represents the stones of the opponent. Besides, if there is a stone on board, then the state of the corresponding position in the frame will be set to 1, otherwise to O. For example, if the current player is black and suppose b[i, is the current board state, X [i, = -bji.j]=hlaa stome [i. j] = = stone- In summary, we concatenate together the historical planes to generate the input state s = [X Yr-7; Xr-6: X .... X,, Yr, CJ, where X,, Y2 are the feature planes at time step t and C' gives information of the current player.
Training As for the training phase, we train the model from scratch without any human expert data, which is the same as the setting of Atari games. Besides, limited to the GPU resources, we do not use the reanalyzing mechanism of MuZero (Schrittwieser et al.] 2020) and EfficientZero (Ye al.] 2021], which targets at recalculation of the target values and policies from trajectories in the replay buffer with the current fresher model. Specifically, we use 6 GPUs for doing self-play to collect data, 1 GPU for training, and GPU for evaluation.
Exploration To make a better exploration on Go, we reduce the a in the Dirichlet noise Dir(a) from 0.3 to 0.03 and we scale the exploration noise through the typical number of legal actions, which follows these works (Silver et al.] 2018. Schrittwieser et al.] (020). In terms of sampling actions from MCTS visit distributions, we will mask the MCTS visit distributions with the legal actions and sample an action ae, where
1 <<7 T
0g a, arg max TT. 2 T
(3)
T is set to 16 in self- play and is set to 0 in evaluation, which is similar to these works (Silver et al., 2018 [Schrittwieser et al, 2020). In this way, the agent does more explorations for the previous T steps while taking the best action afterwards. But for Atari games, Vt. we choose o, ~ W, in self-play and d, = arg max n. in evaluation, which the same as these works (Schrittwieser et al.) 2020
Ye et al., 2021).
Two-player MCTS On board games, there are two players against each other, which is different from that of one-player games. Therefore, we should do some changes to the MCTS with the two- player game. For one thing, the value network always predicts the Q-value the black player instead of the current player, which provides more stable prediction. Furthermore, A significant change is that during backpropagation of MCTS, the value should be updated with the negative value from the child node. Because the child node is the opponent, the higher value of the opponent indicates a worse value of the current player. Besides, as for Q-values of the unvisited children on Go and Atari games, we follow the implementation of EfficientZero (Ye et al. 202T)
follows:
(oo 0
Q(s) Q(
Es ((s,.))oo((s,6)
1 Es IN(x6)20
(4)
a(s { a(s
a(s, >
Q(s)
N(s,)) =0
Notably, we allow the resignation for players when max. ro .a) < -09 during self-play and evaluation, which means that the predicted winning probability is less than 5%. As for other hyperparameters both Go and Atari games, note that choose the same values as those in EfficientZero. Specifically, the c₁. Cg in our mentioned P-UCT formula (Eq. are set to 1.25 and 19652, following these works (Schrittwieser al. 2020
Ye et al. 2021
13

---

Under review as a conference paper at ICLR 2022
A.2 PROOF
Lemma 1. Va E A. given that Re(s,a) E [_ and the Qu(s, = MNccomn Ra(a.a) then at
Ne(o,a)
Na, (x.0)
iteration 1 S 22 S N, Qu (8, Qic (8, S (1
[1 Qu,
Nag (8,0)
E Re(a,a)
proof. Since Qx(s,a)
Nz(s,a) we have
Na (s, (8,,a) + LI=Ne, (ea) Re(s,a)
(ag(sa)
(s,0a
(5)
(s,0)
Because Re(s, E1 then
Nk, (8, (1) S
(x, Qu (s. (8, (s,
(6)
(8,
Therefore
(s) (s, s (8, )(1 (s,a)
(7)
(1,
Lemma 2. Gäven that r E (0, if 3K E N.N,N.||(K6 #2/2(5)]1
< then
[s) -
<e+1- Ty) (s)ll
proof. Since the (s, a) is a distribution that equals to Na(a.) Therefore.
[ - (*)l1 < [s) #w/2(=))l + | #x(()]l
(8)
Then
N (s) # N (s) [0)],= + | # -xit (0)
[s) (s)l1 $
(9)
where
N 20 < k < h In addition,
[ + -لن (s) ||, - || - #x/2(s)|11 < e.
Besides, & 2 r,, then we have
| - (x)ll x
Σ
# Nx (6)
(5)
= - - - (s)
M
Σ
A (8)
$ v
(s)
+c
(10)
1=0
<1+6- 2M
$e+1-r
For the N-th iteration of the search process, the final visit count distributions keep the same between the original expansion (Algorithm) I and the virtual expansion (Algorithm 2). This because the last iteration, searching the nodes after the root has no effects the final distribution. Therefore, x = (s). So we have
[s)(s) (s)ll, <c+1-r
(11)
14


Reviews:
[{"review_id": "nBxJDsYNNx", "reviewer": "Reviewer_xM7t", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The main contribution of the paper is an early-termination rule for MCTS. While the experiments show that the proposed V-MCTS is more efficient on certain tasks, my main concern is that the termination rule might be trivial in practice (e.g., simply perform fewer queries) since it does not really depend on the values. Suppose we have a budget of $N$ nodes to query. Intuitively, Lemma 2 suggests than when we have already visited close-to-$N$ nodes, then the final policy $\\pi$ is unlikely to change too much. Although this is true, I think this does not necessarily tell us more than what we already know: since we only have a few queries left, the change in $N(s,a)$ will be minor, and so will the change in $\\pi$. Therefore, I don’t see many conceptual differences between V-MCTS and selecting a better total computational budget (the total number of queries). Although I believe there are some important differences between V-MCTS and MCTS with optimized computational budget (see details below), but base on the experiments I can’t evaluate whether this is significant.\n\nSpecifically, I believe V-MCTS can more efficiently prune queries for “simple” states, since for these states $\\pi$ could remain almost unchanged during the search. In contrast, for “harder” states, $\\pi$ could change drastically after certain “rewarding” states have been discovered. I have a strong feeling that V-MCTS works because of this reason, and I think this point makes perfect sense. However, base on the current experiments I cannot decide whether this is true. I think the paper could be improved if the authors can analyze this case better.\n\nFrom a theoretical perspective, Lemmas 1 and 2 do not provide new insights to the problem. The bound in Lemma 2 is based on the simple fact that $N(s,a)$ cannot change too much when the remaining number of queries is small. Therefore, in my humble opinion, the paper should focus more on empirically explaining the termination rule.", "summary_of_the_paper": "The paper proposes Virtual MCTS, an early-termination rule for MCTS to improve its efficiency. Roughly speaking, the termination rule prunes the search process when the final policy at the root node is unlikely to change by too much from the current policy. This strategy improves the efficiency of AlphaGoZero-style algorithms. Specifically, the authors showed that Virtual MCTS improves the learning efficiency on 9*9 Go.", "summary_of_the_review": "Overall, I tend to vote for rejection since (i) the paper’s theoretical findings are rather trivial and (ii) the paper does not provide good insight on why the termination rule works, or on what kind of problem can it performs better. But I think the proposed termination rule follows my intuition and the paper could be improved if the authors provide more detailed analyses on that.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "XyqcGqpubSZ", "reviewer": "Reviewer_i2Lg", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper incorrectly references the original MCTS/UCT version of Kocsis and Szepesvari for AlphaZero, however, AlphaZero used Rosin's P-UCT, not the original UCT.\nThe proposed method uses forward pruning/early termination in UCT to reduce the search effort. In effect, it introduces a variant of the UCT selection rule.\nThis idea is a fruitful idea, that has been tried by Lorentz in 2015 (Early Playout Termination in MCTS, Advances in Computer Games 2015) and by Hsueh in 2016 in Theoretical Computer Science for An analysis for strength improvement of an MCTS-based program playing Chinese dark chess.\nThese variations of UCT indeed also go back to the work of Auer and Cesa Bianchi (2002) on UCB1, on which UCT was based, which they reference as their first reference. \nThis idea has been shown to indeed improve performance in certain situations.\nThe proposed approach appears to be a variation on these older experiments.\n\nThe authors have  not presented comparisons to these earlier works in non-deep learning environments. I would be very interested to learn of a comparison of their new approach to these earlier selection rules. I would consider such comparisons essential for considering the new rule for publication in ICLR.\n\nThere is one unresolved reference to a section in the paper.\n", "summary_of_the_paper": "This paper proposes the Virtual MCTS (V- MCTS), a variant of MCTS that mimics the human behavior, and is 50% more sample efficient, by performing a type of forward pruning.\nMCTS is characterized as a model-based reinforcement learning algorithm, that imagines what the future would look like, using terminology borrowed from Sutton in his description of Dyna, a model-based algorithm. \nI agree with the planning part, but am less certain if I agree with the learning characterization of MCTS.\nOften, MCTS is used inside a model-based approach as the planning component. MCTS is usually not regarded as a full model-based approach.", "summary_of_the_review": "The paper presents an interesting new termination criterion for MCTS.\nThe work should include comparisons to other selection rules, and misses references to some of these.\nWithout these comparisons, it is unclear how substantive the contributions are, and I do not recommend acceptance. \nThe language of the paper must also be improved.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "IFt01wF0SRK", "reviewer": "Reviewer_d2cw", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "**Primary strengths**:\n1) Solid and extensive empirical evaluation with ablation studies.\n2) The main ideas of the paper are clearly described.\n3) The proposed approach looks interesting and useful. I especially like the idea of virtual expansions, even if (or maybe especially because) it is very simple but effective. It would be even more elegant if the changes in distributions from steps $k$ to $N$ could be computed at once, rather than in $N - k$ little steps... but I suppose that might be impossible. In practice it probably doesn't matter much, it should be really fast anyway without actually rolling out any new game states or performing any neural network evaluations.\n\n**Primary weaknesses**:\n1) There are a few technical errors (relatively easily fixable ones, but also important ones). \n\n    Firstly, section 3.1 describes Eq. (1) as \"selection rule named UCT\". This is wrong in several ways. UCT is actually a variant of the entire MCTS algorithm (not a selection rule), which uses *UCB1* as its selection rule. The selection rule described by Eq. (1) is a different one; it's the PUCT variant used by AlphaGo/AlphaGo Zero/AlphaZero/etc. That particular slowly-decreasing exploration hyperparameter was only seen (if I recall correctly) in AlphaZero, before that it was just a constant.\n\n    Secondly, there seems to be a mistake in Lemma 1: if I'm not mistaken, the $(Q_{k_1}(s, a) + 1)$ term at the end should actually be $(1 - Q_{k_1}(s, a))$. In the end this may not end up mattering too much; the extreme values that the bound can take end up being the same, but flipped around for the two different extreme values that $Q_{k_1}(s, a)$ can take, because the $Q$-values are in $[-1, 1]$... but it still looks like a mistake.\n\n2) More small mistakes (like sloppy notation a few times, see detailed comments below) and minor grammatical/spelling issues. Overall the latter don't impact comprehensibility too much though in my opinion.\n\n---\n\n**Detailed comments**:\n- shielding light --> shedding light\n- \"We propose an MCTS algorithm variant that can behave like a human.\" --> this kind of claims about \"human-like\" behaviour is always very dangerous in my opinion. \n- I found the notation where $\\hat{Q}$-values are individual outcomes from individual iterations, and $Q$-values are averages of multiple such $\\hat{Q}$-values, confusing. They're too similar, and often in other work the hat actually signifies an \"approximation\" whereas the version without a hat signifies a \"theoretical\" or \"true\" value. I would recommend changing the $\\hat{Q}$-values to $R$-values for example (since they're like rewards in reinforcement learning).\n- The text in the main paper around Lemmas 1 and 2 should at least mention that their proofs can be found in supplementary material.\n- Section ?? at end of page 4.\n- Start of section 4.3 points to \"line 5-10\" in Algorithm 3, but I think it should actually be lines 8-13?\n- Second paragraph of 5.1 mentions an agent named \"GNU\", but it's actually named \"GNU Go\"\n- What do you mean by \"100 pieces as the black player and 100 pieces as the white one\"? Should this be \"games\" instead of \"pieces\"?\n- The colours used in the plots are probably not colour-blind friendly (consider that the most common form of colour-blindness is red-green colour-blindness). \n- I don't understand why some results in Table 1 are printed in boldface and others not. Every single row actually has the best result not in boldface, but.... the second best?\n- (Coulom, 2006) --> (Coulom, 2007)\n- Capitalise \"Nature\" in (Silver et al., 2016)\n- Should cite the publication in Science instead of the arXiv one for AlphaZero\n- Descriptions of implementation details of MCTS / experiments in supplementary material are not sufficient. \"All the other implementations follows the Alpha-series paper (Silver et al., 2016; 2017; Schrittwieser, 2020)\" does not tell us a lot. There are many differences between those three cited papers (AlphaGo used human expert data, playouts, REINFORCE, etc.; AlphaGo Zero used no human expert data, no playouts, MCTS visit distributions as targets for policy, etc.), and many details on MCTS-related hyperparameters are also not sufficiently described in those papers; $C_{puct}$ value, $Q$-value assigned to unvisited children, etc.\n- In proof for Lemma 1, denominator in Eq. (3) should be $N_{k_2}(s, a)$ instead of just $N_{k_2}$.\n- In proof for Lemma 2, Eq. (5) has a $\\tilde{\\pi}_N(N/2)$ term, but $N/2$ is not a state.\n\n---\n\n**After response from authors:** I am satisfied with how the authors have addressed the issues and updated my score accordingly.", "summary_of_the_paper": "This paper proposes an approach for a significant speedup of Monte-Carlo Tree Search (MCTS) at a relatively small cost in playing strength. The basic idea is that, when the change in the distribution of visit counts between two different time points $\\frac{k}{2}$ and $k$ is less than some constant $\\epsilon$, it can also be shown that the remaining change in distributions between $k$ and $N$ (where $N$ is the maximum visit count allowed by some budget) will be bounded below some value, and if we consider such a maximum possible error to be sufficiently small we can just terminate the search early at time $k$. The paper also proposes a very simple but important idea called Virtual Expansions, which basically consists of running $N - k$ additional iterations of the bandit algorithm used by MCTS solely in the root node, providing the current estimated average values as rewards for every pull (i.e., leaving average reward estimates unchanged), in order to transform the distribution of visits at iteration $k$ into a prediction of the distribution we would end up with after $N$ iterations.\n\nSeveral empirical evaluations in Go ($9\\times9$ board) and a few Atari games, including ablation studies, demonstrate that the approach can substantially reduce the search times and self-play training times, while only decreasing playing strength by a small amount.", "summary_of_the_review": "While the paper has some interesting and well-evaluated ideas, and definitely should be publishable at some point, in its current form I feel that it is not yet ready; there are too many little (but sometimes important) errors.\n\n---\n\n**After response from authors:** I am satisfied with how the authors have addressed the issues and updated my score accordingly.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes Virtual MCTS, an early-termination rule for MCTS to improve its efficiency. 
The basic idea is to introduce a termination rule that prunes the search process when the final policy at the root node is unlikely to change from the current one. The proposed approach is empirically evaluated on 9x9 Go and Atari games.

After reading the authors' feedback, all reviewers participated in the discussion without reaching a consensus.
Although all reviewers appreciated the authors' answers to their concerns, only one reviewer voted for acceptance. The other two reviewers,  while acknowledging some merits, still have concerns: the technical contribution is minor, the theoretical findings are quite trivial, it is unclear when the proposed termination strategy is could help.
In summary, this paper is borderline and I think it still needs some work to clearly break the bar of a top conference.
Decision: Reject