Watch the Unobserved: A Simple Approach to Parallelizing Monte Carlo Tree Search
Authors: Anji Liu
Jianshu Chen
Mingze Yu
Yu Zhai
Xuewen Zhou
Ji Liu
Venue:  (2020)
Keywords: parallel Monte Carlo Tree Search (MCTS)
Upper Confidence bound for Trees (UCT)
Reinforcement Learning (RL)

Abstract: Monte Carlo Tree Search (MCTS) algorithms have achieved great success on many challenging benchmarks (e.g., Computer Go). However, they generally require a large number of rollouts, making their applications costly. Furthermore, it is also extremely challenging to parallelize MCTS due to its inherent sequential nature: each rollout heavily relies on the statistics (e.g., node visitation counts) estimated from previous simulations to achieve an effective exploration-exploitation tradeoff. In spite of these difficulties, we develop an algorithm, WU-UCT, to effectively parallelize MCTS, which achieves linear speedup and exhibits only limited performance loss with an increasing number of workers. The key idea in WU-UCT is a set of statistics that we introduce to track the number of on-going yet incomplete simulation queries (named as unobserved samples). These statistics are used to modify the UCT tree policy in the selection steps in a principled manner to retain effective exploration-exploitation tradeoff when we parallelize the most time-consuming expansion and simulation steps. Experiments on a proprietary benchmark and the Atari Game benchmark demonstrate the linear speedup and the superior performance of WU-UCT comparing to existing techniques.

Published as a conference paper at ICLR 2020
WATCH THE UNOBSERVED: A SIMPLE APPROACH TO PARALLELIZING MONTE CARLO TREE SEARCH
Anji L Jianshu Chen", Mingze Yu', Yu Zhai', Xuewen Zhou' & Ji Liu *Seattle AI Lab, Kwai Inc., Bellevue, WA 98004, USA {liuan j103, yumingze, zhaiyu, zhouxuewen, ji jiliu)@kuaishouu com *Tencent AI Lab, Bellevue, WA 98004, USA j sianshuchen wew.eeettettneeeennommmmmmme. com
ABSTRACT
Monte Carlo Tree Search (MCTS) algorithms have achieved great success many challenging benchmarks (e.g., Computer Go). However, they generally re- quire large number of rollouts, making their applications costly. Furthermore, it is also extremely challenging to parallelize MCTS due to its inherent sequential nature: each rollout heavily relies on the statistics (e.g., node visitation counts) es- timated from previous simulations to achieve an effective exploration-exploiittton tradeoff. In spite of these difficulties, we develop an algorithm, WU-UCT] to effectively parallelize MCTS, which achieves linear speedup and exhibits only limited performance loss with an increasing number of workers. The key idea WU-UCT is a set of statistics that we introduce to track the number of on-going yet incomplete simulation queries (named as unobserved samples). These statistics are used to modify the UCT tree policy in the selection steps in a principled man- ner to retain effective ppploration-explottaee most time-consuming expansion and simulation steps. Experiments on propri- etary henchmark and the Atari Game benchmark demonstrate the linear speedup and the superior performance of WU-UCT comparing existing techniques.
tradeoff when we parallelize the
INTRODUCTION
Recently, Monte Carlo Tree Search (MCTS) algorithms such as UCT (Kocsis et al. 2006) have achieved great success in solving many challenging artificial intelligence (Al) benchmarks, includ- ing video games (Guo al., (016)) and Go (Silver et al., 2016). However, they rely a large number (e.g. millions) of interactions with the environment emulator to construct search trees for decision-making, which leads to high time complexity (Browne et al. 2012). For this reason, there has been an increasing demand for parallelizing MCTS over multiple workers. However, paralleliz- ing MCTS without degrading its performance is difficult (Segal 2010 Mirsoleimani al.] 201 8a Chaslot et al. 2008), mainly due to the fact that each MCTS iteration requires information from all tradeoff. Specifically, parallelizing MCTS would inevitably obscure these crucial information, and we will show in Section 2.2 that this loss of information potentially results in a significant performance drop. The key question is there- fore how to acquire and utilize more available information to mitigate the information loss caused by parallelization and help the algorithm to achieve better exploration-explottaiion tradeoff.
previous iterations provide effective exploration-exploitaae
To this end, we propose WU-UCT (Watch the Unovserved in UCT), a novel parallel MCTS algo- rithm that attains linear speedup with only limited performance loss. This is achieved by a con- ceptual innovation (Section 3.1) as well as an efficient real system implementation (Section 3.2 Specifically, the key idea in WU-UCT to overcome the aforementioned challenge is a set of statis- ties that tracks the number of on-going yet incomplete simulation queries (named as unobserved samples). We combine these newly devised statistics with the original statistics of observed samples to modify UCT's policy in the selection steps in principled manner, which, shall show in Section effectively retains exploration-exploitatio tradeoff during parallelization. Our proposed "Code available at

---

Published as a conference paper at ICLR 2020
approach has been successfully deployed in production system for efficiently and accurately esti- mating the rate at which users pass levels (termed user pass-rate) in a mobile game "Joy City", with the purpose of reducing their design cycles. On this benchmark, we show that WU-UCT achieves near-optimal linear speedup and superior performance in predicting user pass-rate (Section 5. We further evaluate WU-UCT on the Atari Game benchmark and compare it to state-of-the-ar parallel MCTS algorithms (Section 5.2), which also demonstrate our superior speedup and performance.
2
ON THE DIFFICULTIES OF PARALLELIZING MCTS
We first introduce the MCTS and the UCT algorithms, along with their difficulties in parallelization.
2.1 MONTE CARLO TREE SEARCH AND UPPER CONFIDENCE BOUND FOR TREES (UCT)
We consider the Markov Decision Process (MDP) (S, A, where an agent interacts with the environment in order maximize long-term cumulative reward. Specifically, an agent at state 8, E S takes an action 0z E A according to policy I. so that the MDP transits to the next state 81+1 P(st-1|st, ae) and emits reward R(s, at) The objective of the agent is to learn an optimal policy nT" such that the long-term cumulative reward is maximized:
max E
IN NTT 84.
Σ 1=0
r R(st, az) 80 s0==]]
(I)
where s S denotes the initial state and 7 E (0, 1] is the discount factor Many reinforcement
learning (RL) algorithms have been developed to solve the above problem (Sutton & Barto 2018).
including model-free algorithms (Mnih et al.] 2013 (016)) 2 [992]KKonda & Tsitsiklis 2200
Schulman et al., 2015 2017) and model-based algorithms (Nagabandi et al. 2018 Weber et al.,
2017] Bertsekas 2005 Deisenroth & Rasmussen 2011). Monte Carlo Tree Search (MCTS) is
model-based RL algorithm that plans the best action at each time step (Browne et al. 2012) Specifically, it uses the MDP model (or its sampler) to identify the best action at each time step by constructing a search tree (Figure I(a),, where each node represents visited state, each edge from 8 denotes an action 0g that can be taken at that state, and the landing node s' denotes the state it transits to after taking ag- As shown in Figure ((a) MCTS repeatedly performs four sequential steps: selection, expansion, simulation and backpropagation. The selection step traverses over the existing search tree until the leaf node (or other termination conditions are satisfied) by choosing actions (edges) a₂ at each node according to tree policy. One widely used node-selection policy the one used in the Upper Confidence bound for Trees (UCT) (Kocsis et al., 2006):
Ver + 3// 2og N. s'EC(e)
/ N₂
0g arg max
where C(s) denotes the set of all child nodes for 8; the first term Vy is an estimate for the long-term cumulative reward that can be received when starting from the state represented by node s', and the second term represents the uncertainty (size of the confidence interval) of that estimate. The confi- dence interval is calculated based on the Upper Confidence Bound (UCB) (Auer et al., 2002 Auer 2002) using N₂ and No., which denote the number of times that the nodes and s' have been visited, respectively. Therefore, the key idea of the UCT policy (2) is to select the best action according to an optimistic estimation (i.e., the upper confidence bound) of the expected return, which strikes balance between the exploitation (first term) and the exploration (second term) with B controlling their tradeoff. Once the selection process reaches leaf node of the search tree (or other termina- tion conditions are met), we will expand the node according to prior policy by adding new child node. Then, in the simulation step, we estimate its value function (cumulative reward) V. by running the environment simulator with a default (simulation) policy. Finally, during backpropagation, we update the statistics V, and N, from the leaf node sr to the root node so of the selected path by recursively performing the following update (i.e., from = T - to = 0):
No. f- No. + 1, V., + R(st, az) + VV
Ve, ((N2, 1)V., + V...
II the context of MCTS, the action space A is assumed he finite and the transition P is assumed be deterministic, i.c., the next state st+1 is determined by the current state & and action at. We assume certain regularity conditions hold so that the cumulative reward 2 7 R(s,, ax) is always bounded (Sutton& & Barto 2018).
2

---

Published as a conference paper at ICLR 2020
Repest
Selection
Expansion
Simulation
Buckpropugution
Recunively adeei child mode (2).
Simalaz from node's
Recursivlly visted modes sirralation
chiM sconndings
(a) Each (non-parallel) MCTS rollout consists of four sequential steps: selection, expansion. simulation and backpropagation, where the expansion and the simulation steps are generally most consuming.
Warke
Worber II
Ba Rpppprpaggtion
After
Selecion
M
Tepingtee
progroo
Colorel catena (F. bean spdiad the compppdding worker. wisk saso onee (1) no spdaaci.
(b) Ideal parallelization (c) Naive parallelization
(d) WU-UCT
Figure I: MCTS and its parallelization. (a) An overview of MCTS. (b) The ideal parallelization: the most up-to-date statisties (V,, N.) } (in chromatic color) are assumed be available to all workers as soon as a simulation begins (unrealistic in practice). (c) The key challenge in parallelizing MCTS: the workers can only access outdated {V. (in gray-color), leading problems like collapse of exploration. (d) WU-UCT tracks the number of incomplete simulation queries, which is denoted as O.. and modifies the UCT policy a principled manner to retain effective exploration-exploiaee tradeoff. It achieves comparable speedup and performance as the ideal parallelization.
where Vay is the simulation return of sT; a, denotes the action selected following (2 at state 8t-
2.2 THE INTRINSIC DIFFICULTIES PARALLELIZING MCTS
The above discussion implies that the MCTS algorithm is intrinsically sequential: each selection step new rollout requires the previous rollouts to complete order deliver the updated statis- tics, V, and N,, for the UCT tree policy 2 Although this requirement of up-to-date statistics is not mandatory for implementation, it is in practice intensively required achieve effective exploration- exploitation tradeoff (Auer et al., (002). Specifically, up-to-date statistics best help the UCT tree policy to identify and prune newrrewg branches as well as extensively visiting rewarding paths for additional planning depth. Likewise, to achieve the best possible performance, when multiple workers are used, it is also important to ensure that each worker uses the most recent statistics (the colored V, and N, in Figure in its own selection step. However, this is impossible in paralleliz- ing MCTS based on the following observations. First, the expansion step and the simulation step generally more time-consuming compared to the other two steps, because they involve large number of interactions with the environment (or its simulator). Therefore, as exemplified by Figure I[c) when worker C initiates a new selection step, the other workers A and are most likely still in their simulation or expansion steps. This prevents them from updating the (global) statistics for other workers like C, which happens at their respective backpropagation steps. Using outdated statistics (the gray- golorcol V, and N₂) at different workers could lead to a significant performance exploitation fail- ure, which we shall discuss thoroughly in Section E To give an example, Figure [(c) llsttrtte the collapse of exploration, where worker C traverses over the same path as the worker A in its selection step due to the determinism of (2). Specifically, if the statistics are unchanged between the moments that worker and C begin their own selection steps, they will choose the same node according to 2). which greatly reduces the diversity of exploration. Therefore, the key question that we want to address in parallelizing MCTS is how to track the correct statistics and modify the UCT policy in a principled manner, with the hope of retaining effective exploration-exploittiio tradeoff different workers.
loss given a fixed target speedup, due to behaviors like collapes of exploration
3

---

Published as a conference paper at ICLR 2020
3 WU-UCT
In this section, we first develop the conceptual idea of our WU-UCT algorithm (Section 3. D. and then we present a real system implementation using master-worker architecture (Section 3.2
3.1 WATCH THE UNOBSERVED SAMPLES IN UCT TREE POLICY
As we pointed out earlier, the key question we want to address in parallelizing MCTS is how to deliver the most up-to-date statistics N₂} to each worker so that they can achieve effective exploration-exploitttion tradeoff in its selection step. This is assumed to be the case in the ideal parallelization in Figure [(b) Algorithmically. it is equivalent to the sequential MCTS except that the rollouts are performed in parallel by different workers. Unfortunately, in practice, the statis- tics (V., },} available to each worker are generally outdated because of the slow and incomplete simulation and expansion steps at the other workers. Specifically, since the estimated value V,, is unobservable before simulations complete and workers should not wait for the updated statisties to proceed, the (partial) loss of statistics {V., N. } is unavoidable. Now the question becomes: is there an alternative way to addressing the issue? The answer is in the affirmative and is explained below.
Aiming at bridging the gap between naive parallelization and the ideal case, we closely examine their difference in terms of the availability of statistics. As illustrated by the colors of the statistics, their only difference in Ne. ) is caused by the on-going simulation process. As suggested by (3), although V, can only be updated after a simulation step is completed, the newest N,, information can actually be available early worker initiates new rollout. This is the key insight that we leverage to enable effective parallelization in our WU-UCT algorithm. Motivated by this, we introduce another quantity, O.. to count the number of rollouts that have been initiated but not ye completed, which we name as unobserved samples. That is, our new statistics, O,, watch the number of unobserved samples, and are then used correct the UCT tree policy (2) into the following form:
2 log (N, + +O.) Vs- +BV
0, arg max s'C(s)
(4)
N₂ + +O,
The intuition of the above modified node-selection policy is that when there are O₂ workers sim- ulating (querying) node 8, the confidence interval at node s will eventually be shrunk after they complete. Therefore, adding O, and O₂ to the exploration term considers such fact beforchand and let other workers be aware of it. Despite its simple form, 44) provides a principled way to retain effective exploration-explootttio tradeoff under parallel settings; it corrects the confidence bound towards better epploration-exploitaaai
tradeoff. As the confidence level is instantly updated (i.e., the beginning of simulation), more recent workers are guaranteed to observe additional statistics, which prevent them from extensively querying the same node as well as find better nodes for them to query. For example, when multiple children are in demand for exploration, (4) allows them to be explored evenly. In contrast, when a node has been sufficiently visited (i.e., large N, and No)), adding O, and Oz from the unobserved samples have little effect on (4) because the confidence interval is sufficiently shrunk around Vv, allowing extensively exploitation of the best-valued child.
3.2 SYSTEM IMPLEMENTATION USING
ARCIITECTURES
We now proceed to explain the system implementation of WU-UCT, where the overall architecture is shown in Figure 2(a) (see Appendix A for the details). Specifically, we use master-worker ar- chitecture to implement the WU-UCT algorithm with the following considerations. First, since the expansion and the simulation steps are much more time-consuming compared to the selection and the backpropagation steps, they should be intensively parallelized. In fact, they are relatively easy to parallelize (e.g., different simulations could be performed independently). Second, as we dis- cussed earlier, different workers need to access the most up-to-date statistics (V., N., O.) in order to achieve successful exploration-exploitatio tradeoff. To this end, a centralized architecture for the selection and backpropagation step is more preferable as it allows adding strict restrictions to the retrieval and update of the statistics, making them up-to-date. Specifically, we use a central- ized master process to maintain global set of statistics (in addition to other data such as game states), and let it be in charge of the backpropagation step (i.e., updating the global statistics) and the selection step (i.e., exploiting the global statistics). As shown in Figure 2(a) the master process
4

---

Published as a conference paper at ICLR 2020
Main prucess (muasler)
Master
Worker (espension)
Perficto selection aoseeling to Eg until terninstion crietion cricilal
gunteslale, exesute action reward, spisace torainal signal. and the result game size
an rspand,
Sexekiie
Toe Suppeppaiiin
Decopled (kelg)
Worker (simulation)
If Exgarsion leedel, azd t0 exparaiun lack sufliz, otlawwie add simiatiion tnek
Ieeo (2
Teundas
Few 79
Dccepiel 194 sia
Ansiga jucher uskk to loen warkers.
%
Expaision Wolker
Va complete exparnion
fully occupted!
Larsoattl d cory of pacire modk
Tack hoffier
(b) Time consumption in the Tap game.
perform incompplete update, and
osdign simiition ook
Cirriaate novasl
Warker (espussion)
(1
20
Serinaran warkee
fully
Beigeigeheer takk from workers
2lex (92
Occupic (leia))
If simubation workers see filly occupted, wait fora complete took and par parfee complete update.
Load gime-tate, rollout
until
the cunilatve
Oscepiod (44 vig
Simulatiin workers (worker)
(c) Time consumption in the Atari games.
(a) The system architecture that implements WU-UCT.
Figure 2: Diagram of WU-UCT's system architecture and its time consumption. (a) the Green blocks and the task buffers are operated at the master, while the blue blocks are executed by the workers. (b-c) the breakdown of the time consumption on two game benchmarks (Section
repeatedly performs rollouts until predefined number of simulations is reached. During each roll- out, it selects nodes to query, assign expansion and simulation tasks to different workers, and collect the returned results to update the global statistics. In particular,
the following incomplete to track N, and O along the traversed path (see
update and complete update (shown in Figure 2(a) Figure I(d)):
fincomplete update]
O, + 0,+ 11,
(5)
[complete update]
O, + O. - 1; N + 11
(6)
where incomplete update is performed before the simulation task starts, allowing the updated statis- tics to be instantly available globally; complete update is done after the simulation return is available, resembling the backpropagation step in the sequential algorithm. In addition, V. is also updated in the complete update step using (3). Such a clear division of labor between the master and the work- ers provides sequential selection and backpropagation steps when we parallelize the costly expan- sion and simulation steps. It ensures up-to-date statistics for all workers by the centralized master process and achieves linear speedup without much performance degradation (see Section 5 for the experimental results).
To justify the above rationale of our system design, we perform a set of running time analysis for our developed WU-UCT system and report the results in Figure (b) (c). We show the time- consumption for different parts at the master and at the workers. First, we focus exclusively on the workers. With close-to- 100% occupancy rate for the simulation workers, the simulation step is fully parallelized. Although the expansion workers are not fully utilized, the expansion step is max- imumly parallelized since the number of required simulation and expansion tasks is identical. This suggests the existence of an optimal (task-dependent) ratio between the number of expansion work- and the number of simulation workers that fully parallelize both steps with the least resources (e.g. memory). Returning to the master process, on both benchmarks, we see a clear dominance of the time spent the simulation and the expansion steps even they are both parallelized by 16 workers. This supports our design to parallelize only the simulation and expansion steps. We finally focus on the communication overhead caused by parallelization. Although more time-consuning compared to simulation and backpropagation, the communication overhead is negligible compared to the time used by the expansion and the simulation steps. Other details in our system, such as the centralized game-state storage, are further discussed in Appendix A
4 THE BENEFITS OF WATCHING UNOBSERVED SAMPLES
In this section, we discuss the benefits of watching unobserved samples in WU-UCT, and compare it with several popular parallel MCTS algorithms (Figure 3), including Leaf Parallelization (LeafP),
5

---

Published as a conference paper at ICLR 2020
During simulation, milpple weckers (e A, R) vimultancasll query
Different workers periiem tree search in local different child nodes.
An vittaal loss Pou. suhimacief from offoodss that lave been trvvesed by autie worker be odded bock modes during badkgropegstion.
Selection, exparsion, and tackgropggtion sequemially executed (similar to UCT)
ARC
(a) Leaf parallelization (LcafP)
(b) Tree parallelization (TreeP)
(c) Root parallelization (RootP)
Figure 3: Three popular parallel MCTS algorithms. LeafP parallelizes the simulation steps, TreeP uses virtual loss to encourage exploration, and RootP parallelizes the subtrees of the root node.
Tree Parallelization (TreeP) with virtual loss, and Root Parallelization (RootP) LeafP parallelizes the leaf simulation, which leads to an effective hex game solver (Wang et al., 2018). TreeP with virtual loss has recently achieved great success in challenging real-world tasks such Go (Silver) et al.) 2016). And RootP parallelizes the subtrees of the root node at different workers and aggregates statistics the subtrees after all workers complete their simulations (Soejima et al. 2010).
We argue that, by introducing the additional statistics O., WU-UCT achieves better exploration- exploitation tradeoff than the above methods. First, LeafP and TreeP represent two extremes in such tradeoff. LeafP lacks diversity in exploration as all its workers are assigned to simulating the same node, leading to performance drop caused by collapse of exploration in much the same way the naive parallelization (see Figure I(c).. In contrast, although the virtual loss used in TreeP could encourage exploration diversity, this hard additive penalty could cause exploitatin failure: workers will be less likely co-simulating the same node even when they are certain that it is optimal (Mirsoleimani et al.) (017). RootP tries to avoid these issues by letting workers perform an independent search. However, this reduces the equivalent number of rollouts each worker, decreasing the accuracy of the UCT policy (2). Different from the above three approaches, WU- UCT achieves a much better exploration by using O, to "penalize" the nodes that have many in progress simulations. Meanwhile, allows multiple workers to exploit the most rewarding node since this "penalty" vanishes when N. becomes large (see 4)).
tradeoff the following manner. It encourages
5 EXPERIMENTS
This section evaluates the proposed WU-UCT algorithm a production system predict the user pass-rate a mobile game (Section 5. as well as on the public Atari Game benchmark (Sec- tion 5.2p. aiming at demonstrating the superior performance and near-linear speedup of WU-UCT.
5.1 EXPERIMENTS ON THE "JOY CITY" GAME
Joy City a level-oriented game with diverse and challenging gameplay. Players tap to eliminate connected items on the game board. To pass a level, players have to complete certain goals within a given number of steps 5 The number of steps used to pass level (termed game step) is the main performance metric, which differentiates masters from beginners. It is a challenging reinforcement learning task due to its large number of game-state (over 12 and high randomness in the tran- sition. The goal of the production system is to accurately predict the user pass-rate of different game-levels, providing useful and fast feedback for game design. Powered by WU-UCT, the system runs 16 faster while accurately predicting user pass-rate (8.6% MAB). In this subsection, we con- centrate our analysis on the speedup and performance of WU-UCT using two typical game-levels (Level-35 and Level-58 and refer the readers interested in the user pass-rate prediction system to Appendix C
We evaluate WU-UCT with different numbers of expansion and simulation workers (from 1 to 16) and report the speedup results in Figures (b).. For all experiments, we fix the total number of
20008 for more details. The pscudo-code of the three algorithms is given in Appendix B LeafP: Algorithm 4 TreeP: Algorithm 5 RootP: Algorithm
We refer the readers to Chaslot et al.
refer it as the tap game helow. See Appendix C.1 more details about the game rules.
'Level-35 is relatively simple, requiring 18 steps for average player to pass, while Level-58 is relatively
difficult and needs than 50 steps solve.

---

Published as a conference paper at ICLR 2020
87
11.
15.
F simitittion workers
16
17
16.
21.0
12:1
13.1
10.5
18
500
58
2.
8.0
61
10.1
12.9
10
1.2
37
6.8
13.3
10.2
15
11.
12.0
13
14.9
12.6
14
50.
38
26
84
34
6.1
12.6
15.
2
12.2
07
25.4
25.7
29
50.3
51
5
2.0
2
B
16
2
16
16
2
B
16
exparsion warkers
exparsion workers
exparaioon winkers
exparsion workers
(a) Speedup (level 35)
(b) Speedup (level 58)
(c) Performance (level 35) (d) Performance (level 58)
Figure 4: WU-UCT speedup and performance. Results are averaged over 10 runs, WU- UCT achieves linear speedup with negligible performance loss (measured in game steps).
The performance on 15 Atari games. Average episode return (# standard deviation) over 10 trials are reported. The best average scores among parallel algorithms are highlighted in boldface. The mark indicates that WU-UCT achieves statistically better performance (p-value < 0.0011 in paired t-test) than TreeP (no mark if both methods perform statistically similar). Similarly, the marks i and mean that WU-UCT performs statistically better than LeafP and RootP, respectively.
Table I:
Environment
WU-UCT
TreeP
LeafP
RootP
PPO
UCT
Alien
5938-18839
4200-11086
4280-11016
2206-1882
1850
6820
Boxing
100=0"F4
99:--0
95-14
98=1
94
100
Breakout
408-211Ft
390+:33
331+45
281
274
462
Centipede
1163034
10391041
439433-1:27766
162333:166555
14265-1104405
4386
652810
Freeway
32:10
32.10
31
32-10
32
32
Gravitar
50601
4880 162
3385 155
4160:t:811
737
4900
MsPacman
19804 1
14000
5378-1685
513
2096
23021
16991=16088*
23326-1-2585
25390-13659
27440=9533
6254
38455
RoadRunner
46720++1359
24680-1-316
25452-42977
38300=1191
25076
52300
Rohotank
101=11
86
10
78+t 13
82
Obert
13992_ $596
14620_15738
11655
9465
14293
17250
Spacelnvaders
3393-1292
265111828
2435+1159
8593-809
942
3535
Tennis
41.1%
11:0
1::
0.1:
-14
TimePilot
124.40
32600112165
380751-207
45100-14221
4342
52600
Zaxxon
68385
39579=394218
12300+821
13380=769
5008
46800
simulations 500. First, note that when we have the same number of expansion workers and sim- ulation workers, WU-UCT achieves linear speedup. Furthermore, Figures 3 also suggest that both the expansion workers and the simulation workers are erucial, since lowering the number of workers from either sets decreases the speedup. Besides the near-linear speedup property, WU-UCT suffers negligible performance loss with the increasing number of workers, as shown in Figures (d). The standard deviations of the performance (measured in the average game steps) over different numbers of expansion and simulation workers are only 0.67 and 1.22 for Level-35 and Level-58, respectively, which are much smaller than their average game steps (12 and 30).
5.2 EXPERIMENTS ON THE ATARI GAME BENCHMARK
We further evaluate WU-UCT on Atari Games (Bellemare et al., 2013), classical benchmark for reinforcement learning (RL) and planning algorithms (Guo et al. 2014). The Atari Games are an ideal testbed for MCTS algorithms for its long planning horizon (several thousand), sparse reward, and complex game strategy. We compare WU-UCT to three parallel MCTS algorithms discussed in Section 4 TreeP, LeafP, and RootP (additional experiment results comparing WU-UCT with variant of TreeP is provided in Appendix H We also report the results of sequential UCT (ss 16x slower than WU-UCT) and PPO (Schulman et al. (017) as reference. Generally, the performance of sequential UCT sets an upper bound for parallel UCT algorithms. PPO is included since we used a distilled PPO policy network (Hinton et al. 2015 Rusu et al. 2015) as the roll-out policy for all other algorithms. It is considered as performance lower bound for both parallel and sequential UCT algorithms. All experiments are performed with a total of 128 simulation steps, and all parallel algorithms use 16 workers (see Appendix D for the details).
We first compare the performance, measured by average episode reward, between WU-UCT and the baselines on 15 Atari games, which is done with 16 simulation workers and expansion worker (for a fair comparison, since baselines do not parallel the expansion step). Each task is repeated 10 times with the mean and standard deviation reported in Table Due to the better exploration-exploiaaion tradeoff during selection, WU-UCT per-persorms all other parallel algorithms in 12 out of 15 tasks. Pairwise student t-test further show that WU-UCT performs significantly better (adjusted by the Bonferroni method, p-value < 0.0011) than TreeP, LeafP, and RootP in 7, 9, and 7 tasks, respec- tively. Next, we examine the influence of the number of simulation workers on the speed and the
7

---

Published as a conference paper at ICLR 2020
Gravitar
MsPacman
Eapo tie ap (0
RoadRumner
Zaxxon
sky
Expod fr ner court
Epec
sCsirnadiice walker
of aasahiiis norkers
cfserniaiie watkas
WU-LICT (epraode rolmm)
TradP (epioolc retum)
Leafp (spionk
RociP (spiosiic rekim)
(U per stap)
(ime per step)
LeatP (ime per step)
RocdP (ime per skop)
Speed and performance test of our WU-UCT along with three baselines four Atari games. All experiments are repeated three times and the mean and standard deviation (for episode reward only) are reported. For WU-UCT, the number of expansion workers is fixed be one.
Figure 5:
performance. In Figure 5] we compare the average episode return as well as time consumption (per step) for 4, 8, and 16 simulation workers. The bar plots indicate that WU-UCT experiences little performance loss with increasing number of workers, while the baselines exhibit significant per- formance degradation when heavily parallelized. WU-UCT also achieves the fastest speed compared to the baselines, thanks to the efficient worker-worker architecture (Section 3.2 In conclusion, our proposed WU-UCT not only out-performs baseline approaches significantly under the same number of workers but also achieves negligible performance loss with the increasing level of parallelization.
RELATED WORK
MCTS Monte Carlo Tree Search is planning method for optimal decision making in problems with either deterministic (Silver et al. 2016) or stochastic (Schäfer et al. 2008 environments. has made a profound influence on Artificial Intelligence applications (Browne et al. 2012). and has even been applied to predict and mimic human behavior (van Opheusden et al. 2016). Recently, there has been wide range of work combining MCTS and other learning methods, providing mutual improvements to both methods. For example, Guo et al. (2014) harnesses the power of MCTS to boost the performance of model-free RI. approaches; Shhn al. (2018) bridges the gap between MCTS and graph-based search, outperforming RI. and knowledge hase completion baselines.
Parallel MCTS Many approaches have been developed to parallelize MCTS methods, with the objective being two-fold: achieve near-linear speedup under a large number of workers while main- taining the algorithm performance. Popular parallelization approaches of MCTS include leaf par- allelization, root parallelization, and tree parallelization (Chaslot et al. 2008). Leaf parallelization aims collecting better statisties by assigning multiple workers to query the same node (Cazenave & Jouandeau 2007). ). However, this comes at the cost of wasting diversity of the tree search. Therefore, its performance degrades significantly despite the near-ideal speedup with the help of a client-server network architecture (Kato & Takeuchi] 2010). In root parallelization, multiple search trees are built and assigned to different workers. Additional work incorporates periodical synchronization of statistics from different trees, which results in better performance in real-world tasks (Bourki et al.) 2010). However, a case study on Go reveals its inferiority with even a small number of workers (Soejima et al., (010)). On the other hand, tree parallelization uses multiple workers to traverse, per- form queries, and update on a shared search tree. It benefits significantly from two techniques. First, virtual loss is added to avoid querying the same node by different workers (Chaslot et al.) 2008 This has been adopted in various successful applications of MCTS such as Go (Silver et al. 2016) and Dou-di-zhu (Whithhouse et al. 2011) Additionally, architecture side improvements such as us- ing pipeline (Mirsoleimani et al.) 8b) or lock free structure (Mirsolcimani et al.) 201 8a) speedup the algorithm significantly. However, though being able increase diversity, virtual loss degrades the performance under even four workers (Mirsoleimani et al.) 2017 Bourki et al.) 2010). Finally, the idea of counting the unobserved samples to adjust the confidence interval in arm selection also appeared in Zhong et al. (201). However, it mainly focuses on parallelizing the multi-armed thresh- olding bandit problem (Chen et al. 2014) instead of the tree search problem as we do.
7 CONCLUSION
This paper proposes WU-UCT, a novel parallel MCTS algorithm that addresses the problem of outdated statisties during parallelization by watching the number of unobserved samples. Based on the newly devised statistics, it modifies the UCT mode-selection policy in a principled manner, which achieves effective exploration-exploitatie implementation, WU-UCT achieves near-optimal linear speedup with only limited performance loss across a wide range of tasks, including deployed production system and Atari games.
tradeoff. Together with our efficiency-orieee -riinntd system
8

---

Published as a conference paper at ICLR 2020
8 ACKNOWLEDGEMENTS
This work is supported by Tencent Al Lab and Seattle Al Lab, Kwai Inc. We thank Xiangru Lian for his help on the system implementation.
REFERENCES
Peter Auer. Using confidence bounds for exploitaiion-exploraioo trade-offs. Journal of Machine Learning Research, 3(Nov):397-422, 2002.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3) 2002.
Mare G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environ- ment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47: 253-279, 2013.
Dimitri P Bertsekas. Dynamic programming and suboptimal control: A survey from adp to mpc. European Journal of Control, 110455)310-334, 2005.
Amine Bourki, Guillaume Chaslot, Matthieu Coulm, Vincent Danjean, Hassen Doghmen, Jean- Baptiste Hoock, Thomas Hérault, Arpad Rimmel, Fabien Teytaud, Olivier Teytaud, et al. Scala- bility and parallelization of monte-carlo tree search. In International Conference on Computers and Games, pp. 48-58. Springer, 2010.
Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter I Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. IEEE Transactions Computational Intelligence and Al in games, 4(1):1-43 2012.
Tristan Cazenave and Nicolas Jouandeau. On the parallelization of uct. In proceedings of the Computer Games Workshop, pp. 93-101. Citeseer, 2007.
Guillaume MJ-B Chaslot, Mark HM Winands, and Jaap van Den Herik. Parallel monte-carlo tree search. In International Conference on Computers and Games, pp. 60-71. Springer, 2008.
Shouyuan Chen, Tian Lin, Irwin King, Michael R Lyu, and Wei Chen. Combinatorial pure ploration of multi-armed bandits. In Advances in Neural Information Processing Systems, pp- 379-387, 2014.
Mare Deisenroth and Carl E Rasmussen. Pilco: A model-based and data-efficient approach policy search. In Proceedings of the 28th International Conference on machine learning (ICML-11), pp- 465-472, 2011.
Xiaoxiao Guo. Satinder Singh, Honglak Lee, Richard L Lewis, and Xiaoshi Wang. Deep learning for real-time atari game play using offline monte-carlo tree search planning. In Advances in neural information processing systems, pp. 3338-3346, 2014.
Xiaoxiao Guo, Satinder Singh, Richard Lewis, and Honglak Lee. Deep learning for reward design to improve monte carlo tree search in atari games. arXiv preprint arXiv:1604.0000 2016.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. arXiv preprint 1503.005003025333 2015.
Hideki Kato and Ikuo Takeuchi. Parallel monte-carlo tree search with simulation servers. In 2010 International Conference on Technologies and Applications of Artificial Intelligence, pp. 491- 498. IEEE, 2010.
Levente Kocsis, Csaba Szepesvári, and Jan Willemson. Improved monte-carlo search. Univ. Tartu, Estonia, Tech. Rep, 2006.
Vijay Konda and John N Tsitsiklis. Actor-critic algorithms. In Advances neural information processing systems, pp. 1008-1014, 2000.

---

Published as a conference paper at ICLR 2020
S Ali Mirsoleimani, Aske Plaat, H. Jaap van den Herik, and Jos Vermaseren. An analysis of virtual loss in parallel mets. In ICAART (2). pp. 648 008-652,222 2017.
S Ali Mirsoleimani, Jaap van den Herik, Aske Plaat, and Jos Vermaseren. A lock-free algorithm for parallel mcts. In ICAART (2), pp. 589-598, 2018a.
S Ali Mirsoleimani, Jaap van den Herik, Aske Plaat, and Jos Vermaseren. Pipeline pattern for parallel mets. In ICAART (2), pp. 614-621, 2018b.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:/3/2.5602. 2013.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. International conference on machine learning, pp. 1928-1937, 2016.
Anusha Nagabandi, Gregory Kahn, Ronald S Fearing, and Sergey Levine. Neural network dynamics for model-basee deep reinforcement learning with model-free fine-tuning, In 2018 IEEE Interna- tional Conference on Robotics and Automation (ICRA), pp. 7559-7566. IEEE, 2018.
Andrei A Rusu, Sergio Gomez Colmenarejo, Caglar Gulcehre, Guillaume Desjardins, James Kirk- patrick, Razvan Pascanu, Volodymyr Mnih, Koray Kavukcuoglu, and Raia Hadsell. Policy distil- lation. arXiv preprint arXiv: trXiv:1511.06295 2015.
Jan Schäfer, Michael Buro, and Kout Hartmann. The uct algorithm applied to games with imperfect information. Diploma, Outo- Von-Guericke Univ. Magdeburg, Magdeburg, Germany, 2008
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pp. 1889-1897, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint orXiv:1707.06344 2017.
Richard B Segal. On the scalability of parallel uct. In International Conference on Computers and Games, pp. 36-47. Springer, 2010.
Yelong Shen, Jianshu Chen, Po-Sen Huang, Yuqing Guo, and Jianfeng Gao. M-walk: Learning to walk over graphs using monte carlo tree search. In Advances in Neural Information Processing Systems, pp. 6786-6797, 2018.
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 Schrittieeser, 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, 550(7676):354 2017.
Yusuke Soejima, Akihiro Kishimoto, and Osamu Watanabe. Evaluating root parallelization in go. IEEE Transactions on Computational Intelligence and Al in Games, 2(4):278-288 2010.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Bas Opheusden, Zahy Bnaya, Gianni Galbiati, and Wei Ji Ma. Do people think like computers?
In International conference on computers and games, pp. 212-224. Springer, 2016.
Shiqi Wang, Meng Ding, and Shuqin Li. Hex game system based on p-mcts. In 2018 Chinese Control And Decision Conference (CCDC), pp. 6639-6642. IEEE, 2018
Théophane Weber, Sébastien Racanière, David Reichert, Lars Buesing, Arthur Guez, Danilo Jimenez Rezende, Adria Puigdomenech Badia, Oriol Vinyals. Nicolas Heess, Yujia Li, et al. Imagination-augment arXiv: 1700: 07203, 2017.
agents for deep reinforcement learning. arXiv preprint
10

---

Published as a conference paper at ICLR 2020
Daniel Whitehouse. Edward J Powley, and Peter I Cowling. Determinization and information set monte carlo tree search for the card game dou zhu. In 2011 IEEE Conference on Computational Intelligence and Games (CIG' (C),'II), pp. 87-94. IEEE, 2011.
Ronald J Williams. Simple statistical gradient-folloing algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):22--256, 1992.
Jie Zhong, Yijun Huang, and Ji Liu. Asynchronous parallel empirical variance guided algorithms for the thresholding bandit problem. arXiv preprint arXiv: 1704.04577 2017.

---

Published as a conference paper at ICLR 2020
SUPPLEMENTARY MATERIAL
A ALGORITHM DETAILS FOR WU-UCT
The pseudo-code of WU-UCT is provided in Algorithm 1 Specifically, it provides the workflow of the master process. When the number of completed updates (tcomplete) has not exceeded the max- imum simulation step T Tmaz (a pre-defined hyperparameter), the main process repeatedly performs modified rollout that consists of the following steps: selection, expansion, simulation, and buck- propagation. The selection and backpropagation steps are performed in the main process, while the two others are assigned to the workers. The backpropagation step is divided into two sub-routines incomplete update (Algorithm 2 and complete update (A (Algorithm 3 The former is executed before simulation starts, while the latter is called after receiving simulation results. Task index 7 is added to help the main process to track different tasks returned from the workers. To maximize efficiency, the master process keeps assigning expansion and simulation tasks until all workers are fully occupied.
Communication overhead of WU-UCT The choice for centralized game-state storage stems from the following observations: (i) size of the game-state is usually small, which allows efficient inter-process transformation, and (ii) each game-state is used at most |A| + 1 times thus is ineffi- cient to store in multiple processes. Although this design may not be ideal for all tasks, is least a reasonable choice. During rollouts, game-states generated by any expansion worker may be later used by any other expansion and simulation workers. Therefore, either a per-task transformation or decentralized storage is needed. For the latter case, however, since a game-state will be used at most |A| + times, most workers will not need it, which results in inefficiency of the decentralized storage.
Another possible solution is to store the game-states in shared memory. However, to receive benefit from it, the following conditions should be satisfied: (i) each process can access (read/write) the memory relatively fast even some collisions may happen, and (ii) the shared memory is big enough to hold all game-states that may be accessed. If the two conditions hold, we may be able reduce the communication overhead. Since the communication overhead is negligible even with 16 simulation and expansion workers (as shown in Figures 2(b) and 2 should consider using more workers to speedup the algorithm.
B ALGORITHM OVERVIEW OF BASELINE APPROACHE
We give an overview of three baseline parallel UCT algorithms: Leaf Parallelization (LeafP), Tree Parallelization (TreeP) with virtual loss, and Root Parallelization (RootP), with the objective of providing a comprehensive view to the readers. We refer readers interested in the details of these al- gorithms to Chaslot et al. 2008). As suggested by their names, LeafP, TreeP, and RootP parallelized different parts of the search tree. Specifically, LeafP (Algorithm + parallelizes only the simulation process: whenever node (state) is selected to query, all workers perform simulations individually to evaluate it. The main process (master) then waits for all workers to complete simulation and return their respective cumulative rewards, which are used to update the traversed nodes' statistics.
TreeP (Algorithm 5) parallelizes the whole tree search algorithm by allowing different workers to access shared search tree simultaneously. Each worker individually performs the selection, ex- steps and update the nodes' statistics. To discourage
pansion, simulation, and querying the same node, individual workers subtract virtual loss rv (rvL of the algorithm) to each of its traversed node during the selection process, and add it back (+rvr) during back- prooppppppattion... This allows nodes currently being evaluated by some workers to have lower utility scores 4 and will be less likely to be chosen by other workers, which improves the diversity of the node visited by different workers simultaneously.
Silver et al. (201)) and Segal (0110) introduced an additional way to add pscudo reward into the traversed nodes. See Appendix for details of this variant of TreeP and more experiments of on Atari games.
II our sctup, the game state will only he used for 1 time to start simulation and [A times to initialize expansion.
12

---

Published as a conference paper at ICLR 2020
Algorithm WU-UCT
Input:
enviromment emulator &, root tree node Sroot, maximum simulation step T man, maximum simulation depth dmax, number of expansion workers Nezp. and number of simulation workers Nei Initialize: expansion worker pool Wenp, simulation worker pool Waim, game-state buffer 5, + 0, and
teomplete +
while fcompiete mmmaz
Traverse the tree top down from root node Sroot following 4 until (i) depth greater than dmner (ii) leaf nodc, (iii) expansion required then
node that has been fully expanded and random() < 0.5
shallow copy of the current node Assign expansion task (t, 8) to pool Wezp // is the task index
else
assign simulation task s) to pool Wsim if episode not terminated
Call incomplete update(s); ( episode terminated, call complete update(t, 0.0)
end if
Wezp fully occupied then
Wait for expansion with return: (task index T, game state s, reward r. terminal signal d. task index 7); expand the according T, r, and d; assign simulation task (7, 8) pool Wsin
Call incomplete update(L,
else continue
if Waim fully occupied then
Wait for simulation task with return: (lask index 7, node cumulative reward r)) Call complete update(T, F); tcomplete f Tzomplete +
else continue
t t- t+1
end while
Algorithm 2 incomplete update
Algorithm 3 complete update
input:
node s while null do
task index f, node s, reward while null do
input:
O, 11
N₂ - N₂ 1; O, + 0.
< PR(s) // PR(ss denotes the parent
Retrieve reward according to task index /
node of end while
wr: V. N. x= + N.
+ PR(s) (R(() denotes the parent node of end while
As hinted by its name, RootP (Algorithm (6) parallelizes the root node. Specifically, in an initializa- tion step, all children of the root node is expanded, and different workers assigned to perform rollouts using the expanded child nodes as the root node of the search tree. The algorithm evenly distribute the workload such that the number of rollouts starting from all child nodes is Emaz/M, where M the number workers. After the job assignment, all workers construct search trees in their own local memories and perform sequential tree search until their assigned tasks finished. Finally, the main process collects statistics from all workers and return the predicted best action of the state represented by the root node of the search tree.
C EXPERIMENT DETAILS AND SYSTEM DESCRIPTION OF THE JoY CITY TASK
This section describes the basic rules of the Joy City game (Appendix C.1 as well as details about the deployed user pass-rate prediction system (Appendix C.2
C.1 DESCRIPTION OF THE JOY CITY GAME
This section serves screenshots of the game. In the main frame, there is 9 x 9 grid, where each cell contains an item. We can click cells with connected color regions to eliminate them (i.e., if the cell represented by the purple dot in the first screenshot of Figure 6(a) is tapped, the region contains blue boxes will be "eliminated"). The remaining cells then collapse fill in the gaps of exploded ones. To goal is to fulfill all level requirements (goals) within fixed number clicks. Figure 6[a) provides consecutive snapshots for playing level 10 of the game. The goal of this level is depicted the
introduction to the basic rules of the tap game. Figure 7 depicts several
13

---

Published as a conference paper at ICLR 2020
27
(a) A demonstrated game play in level 10 of the tap game. Purple dots refers to the tapped cell, and red regions indicate directly eliminated cells.
35
24
A "boss leve!"
Small initial connectivity
Various kinds hard-to-remove obstacles and spiral layout
(b) Examples levels with diffcrent rule, difficulty, and layout.
Figure 6: Snapshots of the Tap-elimination game.
top, which 3 "cats" and 24 "balloons". The top-left corner represents the number of remaining steps. Players have to accomplish all given goals before the step runs out. Figure (oa) demonstrates successful gameplay, where only steps are used to complete the level. each of the three left frames, the cell noted by the purple circle is clicked. Immediately, the same-color region marked with a red frame is eliminated. Different goal objects/obstacle objects react differently. For instance, when some cell is exploded beside a balloon, it will also explode. Frame two demonstrates the use of props. Tapping regions with connectivity above a certain threshold will provide prop as a bonus. They have special effects that can help players pass the level faster. Finally, in the last screenshot, all goals are completed and we pass the level.
Figure 66b) further demonstrates the variety of levels. Specifically, the left-most frame depicts a special "boss level", where the goal is the "defeat" the evil cat. The cat will randomly throw objects the cells, adding additional randomness. Three other frames illustrate relatively hard levels, which is revealed from their tow-connectivity, abundance and complexity of the obstacles, and special layout.
C.2 DETAILS OF THE LEVEL PASS-RATE PREDICTION SYSTEM
During a game design cycle, to achieve the desired game pass-rates, game designer needs to hire many human testers to extensively test
14

---

Published as a conference paper at ICLR 2020
A3C learner
Policy æ (as default policy)
Perform multiple game plays using P-UCT with different number of simulations
Game play results
feature extraction
released levels (training) new levels (inference)
User pass-rate (for training only)
Pass rate, aveg. used step, (6 features in total)
Linear regression
Predicted user pass rate (for inference only)
Figure 7: Our deployed user pass-rate prediction system.
all the levels before its release, which generally takes a long time and inaccurate. Therefore, it would greatly reduce the game design cycle if we develop testing system that is able to provide quick and accurate feedback about the user pass-rates. Figure 7 gives an overview of our deployed user pass-rate prediction system, where WU-UCT is used to mimic average user perfor- mance and provide features for predicting the human pass-rate. As we have shown in the main paper, it can achieve significant speedup without significant performance loss allowing the game designer to get the feedback in 20 minutes instead of 12 hours. Specifically, we use WU-UCT with different numbers of rollouts to mimic players with different skill levels, where WU-UCT with 10 rollouts is used to represent average players while the agent with 100 rollouts mimics skillful play- ers. This is verified by the pair-wise sample t-test result provided the WU-UCT agent performs statistically similar (p-value 5%) to human players, while with 100- simulation, the agent performs statistically better (p-value < 5%). Besides, Figure shows that our pass-rate prediction system achieves 8.6% mean absolute error (MAE) on 130 released game-levels, with 93% of them having MAE less than 20%.
Table 2 With 10 simulations,
The system consists of two working phases, i.e., training and inference. Specifically, training and validation are done on 300 levels that have been released in a test version of the game. In the training phase, the system has access to both the level and players' pass-rate, while only levels are available in the inference phase, and the system needs to give quick and accurate feedback about the (predicted) user pass-rate. In both phases, the levels are first fed into an asynchronous advantage actor-critic (A3C) (Mnih et al. (0166) learner for a base policy л. It is then used by the WU-UCT agent as prior to select expand action well the default policy for simulation. We then use WU-UCT to perform multiple gameplays. The maximum depth and width (maximum number of child nodes for each node) of the search tree is 10 and 5, respectively. The number of simulations is set to 10 and 100 to get AI bots with different skill levels. Six features (three for both the 10-simulation and 100-simulation agent) are extracted from the gameplay results. Specifically, the features are Al's pass-rate, average used step divided by the provided step (the number at the top-left corner in the screenshots Figure 6). and median used step divided by the provided step. During training, the features, well as the players' pass-rate, is used learn a linear regressor, while in the inference phase, the regression model is used to predict user pass-rate.
C.3 ADDITIONAL. EXPERIMENTAL. RESULTS
In this section, we list the additional experimental results. Table 3 we report the specific speedup number for different numbers of expansion worker and simulation workers.
Due to the complexity the game, model-free RL algorithms such as A3C Mnih et al. 2016 and PPO Schulman al. (017)) fail to achieve satisfactory performance and thus cannot perform accurate prediction. On the other hand, MCTS could achieve good performance but takes long time in testing.
15

---

Published as a conference paper at ICLR 2020
Table 2: Pair-wise sample t-test of pass-rate across 130 levels between two bots (different number of MCTS rollouts) and the players. "Avg. diff" means the average difference between the pass-rate of the bot and that of the human players. p-value measures the likelihood that two sets of paired samples are statistically similar (i.e. larger means similar). Effect size measures the strength of the difference (larger means greater difference).
MAE: 8.6%
98%
15
of levels
.6%%
10
-30
-20
-10
10
20
30
AI bot rollouts
Avg. diff.
Effect size
p-value
Pass-rate prediction error (%)
WU-UCT WU-UCT
-1.54
0.07 0.88
0.4120
100
22.18
0.0000
Figure 8: Distribution of the pass-rate prediction error on 130 game-levels.
Table 3: Speedup on two levels of the tap game. Me is the number of expansion workers and M, is the number of simulation workers.
Lv.
Level 35
Level 58
M
M
1
2
4
8
16
1
2
4
8
16
1.0
2.0
2.8
3.6
4.5
1.0
1.8
4.1
4.8
5.1
1.4
2.2
4.1
5.7
6.3
1.1
3.1
5.3
6.7
8.4
1.7
2.5
4.5
8.4
8.8
1.1
3.4
6.1
10.1
12.8
2.3
3.0
5.1
10.1
12.8
1.2
3.6
6.7
13.2
16.1
16
2.9
3.7
5.7
11.2
15.5
1.2
3.8
7.6
16.1
20.9
D EXPERIMENT DETAILS OF THE ATARI GAMES
This section provides the implementation details of the experiments Atari games. Specifically, we first describe the training pipeline the default policy. then illustrate how the default policy connected with MCTS algorithm to perform simulation.
Training default policy for MCTS To allow better overall performance, we used the Proximal Policy Gradient (PPO) (Schulman al., 2017). one of the state-of-the-art on- on-policy model-free re- inforcement learning (RL) algorithms. We adopted the highest-starred third-party code of PPO on GitHub. The implementation uses the same hyper- saper-parameters with the original paper. The architec- ture of the policy network is shown in Figure The original PPO network is trained on 10 million frames for each task. To reduce computation count, we reduce the network size using network
Table Performance of the original PPO policy and our distilled policy 15 Atari games.
Environment
Origin PPO policy
Distilled policy
Alien
1850
850
Boxing
94
7
Breakout
274
191
Centipede
4386
1701
Freeway
32
32
Gravitar
737
600
MsPacman
2096
1860
TimeThiGGame
6255
6354
RoadRunner
25076
26600
Robotank
13
Qhert
14293
12725
SpaceInvaders
942
1015
Tennis
-14
-10
TimePilot
4342
4400
Zaxxon
5008
3504
16

---

Published as a conference paper at ICLR 2020
State inpat
ConvZd (out filters: 32, kernel size: 8x8, stride; 4)
State input
ReLU
Conv2d (out- nutt-filter:: 16, kemel size: 3x3, stride: 4]
Conv2d fiutff 64, kernel size: 4x4, stride: 2)
ReLU
ReLU
Conv2d (out filters: 16, kernel size: 3x3,, stride: 4]
Conv2d (out- filtefi 64, kemel size: 4x4, stride: 2)
ReLU
ReLU
Dense (fan-out out: 512)
Dense (fan-out: out: 512)
ReLU
ReLU
Policy output
Value octput
Policy output
Value output
(a) Full-size PPO network.
(b) Distilled network.
Figure 9: Architecture of the original PPO network (left) and the distilled network (right).
distillation (Hinton et al. 2015). Specifically, it is teacher-student training framework where the student (distilled) network mimics the output of the teacher network. Samples are collected by the PPO network with the c-greedy strategy (c = 0.1). The student network optimizes its parameters to minimize the mean square error of the policy's logits well the value. Performance of the original PPO policy network as well as the distilled network is provided in Table
MCTS simulation Both the policy output and the value output of the distilled network is used in the simulation phase. Particularly, if simulation is started from state rollout is performed using the policy network with an upper bound of 100 steps and reaches the leaf state s'. If the environment does not terminate, the full return is computed by the intermediate rewards plus the value function at state s'. Formally, the cumulative reward provided by the simulation is Raima. En Y'r; + (00 where V(s) denotes the value of state s. To reduce the variance of Monte Carlo sampling, we average it with the value function (s) at state s. The final simulation return is then R = 0.5R + (s).
Hyperparameters and experiment details for WU-UCT For all tree search based algorithms (i.e., WU-UCT, TreeP, LeafP, and RootP), the maximum depth of the search tree is 100. The search width is limited by 20 and the maximum number of simulations is 128. The discount factor y is set to 0.99 (note that the reported score is not discounted). When performing gameplays, a tree search subroutine is called to plan for the best action in each time step. The sub-routine iteratively constructs a search tree from its initialization with root node only. Experiments are deployed on 4 Intel x @ EE-26500 v4 CPUs and 8 NVIDIA GeForce RTX 2080 Ti GPUs. To minimize the speed fluctuation caused by different workloads on the machine, we ensure that the total number of simulation workers is smaller than the total number of CPU cores, allowing each process to fully occupy each single core. The WU-UCT is implemented with multiple processes, with an inter- process pipe between the master process and each worker process.
Hyperparameters and experiments for baseline algorithms Being unable to find appropriate third-party packages for baseline algorithms (i.e., tree parallelization leaf parallelization, and root parallelization) we built our implementation of them based on the corresponding papers. Building all algorithms in the same package additionally allows us to accurately conduct speed-tests as it elim-
10 task "Tennis" is not included in the calculation of the average percentile improvement due to the average episade return 0 in RootP.
17

---

Published as a conference paper at ICLR 2020
% of improvements
WU-UCT TreeP
WU-UCT vs. Leafp
UCT vs. RootP
+150%
+50%
-20%
Allen
Boxing
Breakout
Centipede
Freeway
Gravitar
MsPacman
Name ThisGame
RoadRunner
Robotank
Qbert Spacelnvaders
Tennis TimePilot
Zaxxon
Figure 10: Relative performance between WU-UCT and three baseline approaches on 15 Atari benchmarks. Relative performance is calculated according the mean episode reward in 3 trials. The average percentile improvement of WU-UCT on TreeP, LeafP, and RootP is 49%, 104%, and 82%, respectively
Table 5: Comparison between WU-UCT and three TreeP variants 12 Atari games. Average episode return (= standard deviation) over 10 runs are reported. The best average scores among listed algorithms are highlighted in boldface. Hyper-parameter rvL refers the virtual loss added before each simulation starts, and nvl similarly denotes the number of virtual visit counts added before each simulation starts.
TreeP (rvr. nVI. 1) (rvz nVL 2)
TreeP
TreeP
Environment
WU-UCT
(rvr. nVL 3)
Alien
5938=1839
4850#337
4935+60
5000
Boxing
100::0
99+1
99+0
99+1
Breakout
408+:21
379:143
265:1500
463:16
Freeway
32:00
32+00
32.00
32:00
Gravitar
506011568
3500=1707
4105:1463
145
MsPacman
12232-2222
13160++462
12991+851
8640+438
RoadRunner
43520
29800+2282
28550+455
29400
Qbert
+3992+-5556
17055
13425 + 194
9075 +3
SpaceInvaders
3393+1222
2305
3210+127
3020=142
Tennis
4=1
1=0
1=0
1:0
TimePilot
55130-12474
52500
49800+212
32400+1697
Zaxxon
39085:16888
24300+22228
24600-1424
37550 1096
inates other factors (e.g. different language) that may bias the result. Specifically, leaf parallelization is implemented with a master-worker structure: when the main process enters the simulation step, assigns the task all workers. When return from all workers is available, the master process performs backpropagation according to these statistics and begin a new rollout.
As suggested by Browne et al. (012), tree parallelization is implemented using decentralized structure, i.e., each worker performs rollouts on shared search tree. At the selection step. each traversed node added a fixed virtual loss -ryl to guarantee diversity of the tree search. When performing backpropagation, rvr. is added back to the traversed nodes. rvr. is chosen from 1.0 and 5.0 for each particular task. other words, we ran TreeP with rvL. = 1.0 and rvL. 5.0 for each task, and report the better result.
Root parallelization implemented according to Chaslot et al. (2008). Similar to leaf parallelization, root parallelization consists of sub-processes that do not share information with each other. At the beginning of the tree search process, each sub-process assigned several actions of the root node to query. They then perform sequential UCT rollouts until reaches pre-defined maximum number of rollouts. When all sub sabberosssses complete the jobs, statistics from them are gathered by the main process, and are used to choose the best action.
18

---

Published as a conference paper at ICLR 2020
E ADDITIONAL EXPERIMENTS ON THE ATARI GAMES
This section provides additional experiment results to compare WU-UCT with another variant of the Tree Parallelization (TreeP) algorithm. As suggested by Silver al. (2016), besides pre-adjusting the value with virtual loss TVL, pre-adjusted visit count can also be used to penalize V. In this variant of TreeP, both the virtual loss rvL and hand-crafted count correction ny L (termed the virtual pseudo-count is added to adjust V. Specifically, the value of node is adjusted as
V def N.V, - TVL
N + +VL
which is used in the UCT selection phase. Table compares WU-UCT with this TreeP variant using both virtual loss and virtual pseudo-count (i.e., Eq.. 7 Three sets of hyper-parameters are used in
TreeP, which are described in the caption of the table (i.c., TVL = nVL = 1. rVL = TVL = 2. and rVL n 3). All other experiment setups are the same as Section 5.2 and Appendix D 3 that on 9 out of 12 tasks, WU-UCT out-performs this new baseline (with its best hyper-parameters). Furthermore,
also observe that TreeP does not have optimal set of hyper- parameters that performs uniformly well on all tasks. In other words, to perform well, TreeP needs conduct per-task hyper-parameter tuning. On the other hand, WU-UCT performs consistently well across different tasks.
Conceptually, WU-UCT is designed based on the fact that on-going simulations (unobserved sam- ples) will eventually return the results, so their number should be tracked and used to adaptively adjust the UCT selection process. On the other hand, TreeP uses artificially designed virtual loss r and virtual pseudo-count n to discourage other threads from simultaneously exploring the same node. Therefore, WU-UCT achieves better tion, which leads to better performance as confirmed by the experimental results given in Table 5
tradeoff in paralleliza-
19

---

Published as a conference paper at ICLR 2020
Algorithm 4 Leaf Parallelization (LeafP)
Input: environment emulator &, prior policy म. root tree node maximum simulation step Tiax, maximum simulation depth dmaz. and number of workers Naim
Initialize:
fcomplete 4-
while loompiete < Tmas do
Traverse the tree top down from root node Syoot following 2 until (i) depth greater than dmaxs (ii)
a leaf node, or (iii) is node that has not been fully expanded and random(( <
4- expand(s, E, z)
Each of the simulation workers perform roll-out beginning from
Wait until all workers completed simulation and returned cumulative reward worker i)
W (F; is returned by
for i = Nsim do
Call back. propagation F:)
end for
tcomplete f- ccomplete + Naim
end while
Algorithm Tree Parallelization (TreeP)
Input: environment emulator E. prior policy 9, root tree node Sroot, virtual loss ry maximum simulation step T mazz maximum simulation depth dmazs and number of workers N
Initialize: Leomplete
Initialize: Nuo processes, each with access to the environment emulator, the prior policy, and the search tree
Perform asynchronously in each of the Nein workers
Traverse the tree top down from root node Sroot following 2 until (i) its depth greater than dmaz, (ii) it is a leaf node, or (iii) it is a node that has not been fully expanded and random() < 0.5
Add virtual loss to each of the traversed node: V, + V,, - rv z for each traversed 4- expand(s, E, π)) Perform roll-out beginning from
F the returned cumulative reward of the roll-out Call back propagation s,
Remove virtual loss from each of the traversed node: V, + V. + rVL for each traversed
leamplete lcomplete
if Gcomplete 2 T'ax
Terminate current process
end
end
Algorithm Root Parallelization (RootP)
Input: environment emulator prior policy म. node Sroot, maximum simulation step Tmaz. maximum simulation depth dmaas and number of workers Naim
Initialize: feomplete, t- 0 for i Naom Initialize:
Naim processes, each with access to the environment emulator, the prior policy, and the search
tree
Expand all child nodes of Syoot
Tang +- (Taaa |[A)) ([A) is the number of actions)
Averagely distribute the workload (perform tree search Tavg times on each child of Svout) to the Nam workers, and copy the corresponding child nodes to worker's local memory.
Perform asynchronously
each Sroot, Select child of sroot according to its allocated budget
Namn workers (i denotes the thread ID)
Traverse the tree top down from root node Sroot, following (2) until (i) its depth greater than dmaz.
(ii) is leaf node, or (iii) it is node that has not been fully expanded and rondom() < 0.5
Add virtual loss to each of the traversed node: V. +- V, rvr. for each traversed n.
s' + -xpanddss E, .
Perform roll-out beginning from
F f the returned cumulative reward of the roll-out
Call back propagation s, F.)
Remove virtual loss from each traversed node: V. +- V, rrr for each traversed n
toomplete, &- Loompttte,
if fcomplete, 2 Tang
Terminate current process
end if
end
Gather child nodes' statistics from all workers
20

---

Published as a conference paper at ICLR 2020
Algorithm 7 expansion
Algorithm 8 back, propagation
input: node s, environment emulator prior policy a random action drawn from .T. s)
input: node 8, cumulative reward while & # null
while has expanded a do random action drawn from (-| ())
N, +N,,
Retrieve the reward in the current node
end while
(which is collected during its expansion)
s' r, performing in according to E (d: terminal signal)
F t- yF
V.
N V. J
s
node constructed according
PR(s) PR(s) denotes the parent node of end while
Store reward signal r and termination indicator in s/
Link as the child of a by the node corresponding to a
21


Reviews:
[{"review_id": "r1gt3TnWqB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper introduces a new algorithm for parallelizing monte carlo tree search (MCTS). MCTS is hard to parallelize as we have to keep track of the statistics of the node of the tree, which are typically not up-to-date in a parallel execution. The paper introduces a new algorithm that updates the visitation counts before evaluating the rollout (which takes long), and therefore allows other workers to explore different parts of the tree as the exploration bonus is decreased for this node. The algorithm is evaluated on the atari games as well on a proprietary game and compared to other parallelized MCTS variants.\n\nThe makes intuitively a lot of sense, albeit it is very simple and it is a surprise that this has not been tried yet. Anyhow, simplicity is not a disadvantage. The algorithm seems to be effective and the evaluations are promising and the paper is also well written. I have only 2 main concerns with the paper:\n\n- The paper is very long (10 pages), and given that, we reviewers should use stricter reviewing rules. As the introduced algorithm is very simple, I do not think that 10 pages are justified. The paper should be considerably shortened (e.g. The \"user pass rate prediction system\" does not add much to the paper, could be skipped. Moreover, the exact architecture is maybe also not that important).\n\n- The focus of the paper is planning, not learning. Planning conferences such as ICAPS would maybe be a better fit than ICLR. \n\nGiven the stricter reviewing guidelines, I am leaning more towards rejects as the algorithmic contribution is small and I do not think 10 pages are justified.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "SJlF9m02qr", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces a new algorithm for parallelizing Monte-Carlo Tree Search (MCTS). Specifically, when expanding a new node in the search tree, the algorithm updates the parent nodes’ statistics of the visit counts but not their values; it is only when the expansion and simulation steps are complete that the values are updated as well. This has the effect of shrinking the UCT exploration term, and making other workers less likely to explore that part of the tree even before the simulation is complete. This algorithm is evaluated in two domains, a mobile game called “Joy City” as well as on Atari. The proposed algorithm results in large speedups compared to serial MCTS with seemingly little impact in performance, and also results in higher scores on Atari than existing parallelization methods.\n\nScaling up algorithms like MCTS is an important aspect of machine learning research. While significant effort has been made by the RL community to scale up distributed model-free algorithms, less effort has been made for model-based algorithms, so it is exciting to see that emphasis here. Overall I thought the main ideas in paper were clear, the proposed method for how to effectively parallelize MCTS was compelling, and the experimental results were impressive. Thus, I tend to lean towards accept. However, there were three aspects of the paper that I thought could be improved. (1) It was unclear to me how much the parallelization method differs from previous approaches (called “TreeP” in the paper) which adjust both the visit counts and the value estimate. (2) The paper is missing experiments showing the decrease in performance compared to a serial version of the algorithm. (3) The paper did not always provide enough detail and in some cases used confusing terminology. If these three things can be addressed then I would be willing to increase my score.\n\nNote that while I am quite familiar with MCTS, I am less familiar with methods for parallelizing it, though based on a cursory Google Scholar search it seems that the paper is thorough in discussing related approaches.\n\n1. When performing TreeP, does the traversed node also get an increased visit count (in addition to the loss which is added to the value estimate)? In particular, [1] and [2] adjust both the visit counts and the values, which makes them quite similar to the present method (which just adjusts visit counts). It’s not clear from the appendix whether TreeP means that just the values are adjusted, or both the values and nodes. If it is the former, then I would like to see experiments done where TreeP adjusts the visit counts as well, to be more consistent with prior work. (Relatedly, I thought the baselines could be described in significantly more detail than they currently are—-pseudocode would in the appendix would be great!)\n\n2. I appreciate the discussion in Section 4 of how much one would expect the proposed parallelization method to suffer compared to perfect parallelization. However, this argument would be much more convincing if there were experiments to back it up: I want to know empirically how much worse the parallel version of MCTS does in comparison to the serial version of MCTS, controlling for the same number of simulations. \n\n3. While the main ideas in the paper were clear, I thought certain descriptions/terminology were confusing and that some details were missing. Here are some specifics that I would like to see addressed, roughly in order of importance:\n\n- I strongly recommend that the authors choose a different name for their algorithm than P-UCT, which is almost identical (and pronounced the same) as PUCT, which is a frequently used MCTS exploration strategy that incorporates prior knowledge (see e.g. [1] and [2]). P-UCT is also not that descriptive, given that there are other existing algorithms for parallelizing MCTS.\n\n- Generally speaking, it was not clear to me for all the experiments whether they were run for a fixed amount of wallclock time or a fixed number of simulations, and what the fixed values were in either of those cases. The fact that these details were missing made it somewhat more difficult for me to evaluate the experiments. I would appreciate if this could be clarified in the main text for all the experiments.\n\n- The “master-slave” phrasing is a bit jarring due to the association with slavery. I’d recommend using a more inclusive set of terms like “master-worker” or “manager-worker” instead (this shouldn’t be too much to change, since “worker” is actually used in several places throughout the paper already).\n\n- Figure 7c-d: What are game steps? Is this the number of steps taken to pass the level? Why not indicate pass rate instead, which seems to be the main quantity of interest?\n\n- Page 9: are these p-values adjusted for multiple comparisons? If not, please perform this adjustment and update the results in the text. Either way, please also report in the text what adjustment method is used.\n \n- Figure 7: 3D bar charts tend to be hard to interpret (and in some cases can be visually misleading). I’d recommend turning these into heatmaps with a visually uniform colormap instead.\n\n- Page 1, bottom: the first time I read through the paper I did not know what a “user pass-rate” was (until I got to the experiments part of the paper which actually explained this term). I would recommend phrasing this in clearer way, such as “estimating the rate at which users pass levels of the mobile game…”\n\n- One suggestion just to improve the readability of the paper for readers who are not as familiar with MCTS is to reduce the number of technical terms in the first paragraph of the introduction. Readers unfamiliar with MCTS may not know what the expansion/simulation/rollout steps are, or why it’s necessary to keep the correct statistics of the search tree. I would recommend explaining the problem with parallelizing MCTS without using these specific terms, until they are later introduced when MCTS is explained.\n \n- Page 2: states correspond to nodes, so why introduce additional notation (n) to refer to nodes? It would be easier to follow if the same variable (s) was used for both.\n\nSome additional comments:\n\n- Section 5: I’m not sure it’s necessary to explain so much of the detail of the user-pass rate prediction system in the main text. It’s neat that comparing the results of different search budgets of MCTS allow predicting user behavior, but this seems to be a secondary point besides the main point of the paper (which is demonstrating that the proposed parallelization method is effective). I think the right part of Figure 5, as well as Table 1 and Figure 6, could probably go in the supplemental material. As someone with a background in cognitive modeling, I think these results are interesting, but that they are not the main focus of the paper. I was actually confused during my first read through as it was unclear to me initially why the focus had shifted from demonstrating that parallel MCTS works to \n\n- The authors may be interested in [3], which also uses a form of tree search to model human decisions in a game.\n\n- Page 9: the citation to [2] does not seem appropriate here since AlphaGo Zero did not use a pretrained search policy, I think [1] would be correct instead.\n\n[1] Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., ... & Dieleman, S. (2016). Mastering the game of Go with deep neural networks and tree search. nature, 529(7587), 484.\n[2] Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., ... & Chen, Y. (2017). Mastering the game of go without human knowledge. Nature, 550(7676), 354.\n[3] van Opheusden, B., Bnaya, Z., Galbiati, G., & Ma, W. J. (2016, June). Do people think like computers?. In International conference on computers and games (pp. 212-224). Springer, Cham.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "H1eaaz-3dr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces a novel approach to parallelizing Monte Carlo Tree Search \nwhich achieves speedups roughly linear in the number of parallel workers while \navoiding significant loss in performance. The key idea to the\napproach is to keep additional statistics about the number of \non-going simulations from each of the nodes in the tree. The approach is \nevaluated in terms of speed and performance on the Atari benchmark and in a \nuser pass-rate prediction task in a mobile game.\n\nI recommend that this paper be accepted. The approach is well motivated and clearly \nexplained, and is supported by the experimental results. The experiments are reasonably thorough and \ndemonstrate the claims made in the paper. The paper itself is very well-written, and all-around \nfelt very polished. Overall I am enthusiastic about the paper and have only a few concerns, detailed below.\n\n- I suggest doing more runs of the Atari experiment. Three runs of the experiment does not \nseem large enough to make valid claims about statistical significance. This is especially \nconcerning because claims of statistical significance are made via t-testing, which assumes \nthat the data is normally distributed. Three runs is simply too few to be making conclusions \nabout statistical significance using t-testing. I think that this is a fair request to make and \ncould reasonably be done before the camera-ready deadline, if the paper is accepted.\n\n- The experiments in Atari compare against a model-free Reinforcement Learning baseline, PPO. \nWas there a set clock time that all methods had to adhere to? Or alternatively, was it verified that \nPPO and the MCTS methods are afforded approximately equal computation time? If not, it seems \nlike the MCTS methods  could have an unfair advantage against PPO, especially if they are \nallowed to take as long as  necessary to complete their rollouts. This computational bias \ncould potentially be remedied by  allowing PPO to use sufficiently complex function \napproximators, or by setting the number of simulations used by the MCTS methods \nsuch that their computation time is roughly equal to that of PPO.\n\n- I would be careful about stating that PPO is a state-of-the-art baseline. State-of-the-art is a big claim, and I'm not quite sure that it's true for PPO. PPO's performance is typically only compared to other policy-based RL methods; it's hard to say that it's a state-of-the-art method when there's a lack of published work comparing it against the well-known value-based approaches, like Rainbow. I suggest softening the language there unless you're confident that PPO truly is considered a state-of-the-art baseline.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper investigates parallelizing MCTS.                                                                                         
The authors propose a simple method based on only updating the exploration bonus                                                   
in (P)-UCT by taking into account the number of currently ongoing / unfinished                                                               
simulations.                                                                                                                       
The approach is extensively tested on a variety of environments, notably                                                            
including ATARI games.                                                                                                             
                                                                                                                                   
This is a good paper.                                                                                                              
The approach is simple, well motivated and effective.                                                                              
The experimental results are convincing and the authors made a great effort to                                                     
further improve the paper during the rebuttal period.                                                                              
I recommend an oral presentation of this work, as MCTS has become a                                                                
core method in RL and planning, and therefore I expect a lot of interest in the                                                    
community for this work.                                                                                                           
                         
Decision: Accept (Talk)