Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 8: Accept
review_content: 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.
review_title: Official Blind Review #4

final_score: rating: 6: Weak Accept
review_content: 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.

The 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:

- 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).

- The focus of the paper is planning, not learning. Planning conferences such as ICAPS would maybe be a better fit than ICLR. 

Given 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.
review_title: Official Blind Review #3

final_score: rating: 8: Accept
review_content: This paper introduces a novel approach to parallelizing Monte Carlo Tree Search 
which achieves speedups roughly linear in the number of parallel workers while 
avoiding significant loss in performance. The key idea to the
approach is to keep additional statistics about the number of 
on-going simulations from each of the nodes in the tree. The approach is 
evaluated in terms of speed and performance on the Atari benchmark and in a 
user pass-rate prediction task in a mobile game.

I recommend that this paper be accepted. The approach is well motivated and clearly 
explained, and is supported by the experimental results. The experiments are reasonably thorough and 
demonstrate the claims made in the paper. The paper itself is very well-written, and all-around 
felt very polished. Overall I am enthusiastic about the paper and have only a few concerns, detailed below.

- I suggest doing more runs of the Atari experiment. Three runs of the experiment does not 
seem large enough to make valid claims about statistical significance. This is especially 
concerning because claims of statistical significance are made via t-testing, which assumes 
that the data is normally distributed. Three runs is simply too few to be making conclusions 
about statistical significance using t-testing. I think that this is a fair request to make and 
could reasonably be done before the camera-ready deadline, if the paper is accepted.

- The experiments in Atari compare against a model-free Reinforcement Learning baseline, PPO. 
Was there a set clock time that all methods had to adhere to? Or alternatively, was it verified that 
PPO and the MCTS methods are afforded approximately equal computation time? If not, it seems 
like the MCTS methods  could have an unfair advantage against PPO, especially if they are 
allowed to take as long as  necessary to complete their rollouts. This computational bias 
could potentially be remedied by  allowing PPO to use sufficiently complex function 
approximators, or by setting the number of simulations used by the MCTS methods 
such that their computation time is roughly equal to that of PPO.

- 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.
review_title: Official Blind Review #2

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)