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 negligible 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.
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.
Scaling 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.
Note 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.
1. 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!)
2. 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. 
3. 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:
- 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.
- 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.
- 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).
- 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?
- 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.
 
- 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.
- 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…”
- 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.
 
- 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.
Some additional comments:
- 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 
- The authors may be interested in [3], which also uses a form of tree search to model human decisions in a game.
- 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.
[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.
[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.
[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.