Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 3: Clear rejection
review_content: summary:
This paper introduces Shoot Tree Search (STS), a planning algorithm that performs a multi-step expansion in Monte-Carlo Tree Search. Standard MCTS algorithms expand the search tree by adding one node to the tree for each simulation. In contrast, the proposed STS adds multiple nodes to the search tree at each simulation, where each node corresponds to the state and action that are encountered during rollout. By multi-step expansion, the evaluation of the trajectory is less-biased, which can be analogous to n-step TD. In the experiments on Sokoban and Google research football domains, STS outperforms baselines that include Random shooting, Banding shooting, and MCTS.


Overall, my main concerns are technical novelty and presentation quality.

The most common MCTS methods assume that the leaf node is expanded one at a time in each simulation (and its evaluation is performed either by rollout policy or by function approximator), but this common practice does not necessarily mean that MCTS should always do that. The main reason for only expanding one node per simulation in standard MCTS is memory efficiency: if we fully expand the rollout trajectory and retain its information to the search tree, we may get slightly more accurate value estimates. However, the nodes located deep in the tree will not be visited more than once in most cases, thus its effect is usually not significant, leading to the common practice of one-step expansion. More importantly, multi-step expansion has already been used in existing works (e.g. in [1], the tree is expanded by adding the whole rollout trajectory), thus I am not convinced that this work introduces a technical novelty.

It seems that the relative benefit of the STS over MCTS observed in the experiments comes from the bias of the value function approximator. However, to show the effectiveness of 'multi-step' expansion compared to 'single-step' expansion, I think that more thorough ablation experiments should have been conducted. For example, we can consider the setting where both STS and MCTS perform leaf-node evaluation (i.e. UPDATE in Algorithm 5) by executing rollout policy rather than by using value function approximator. By doing so, we can focus only on the benefits of STS's retaining information of full rollout trajectory (i.e. multi-step expansion), compared to MCTS's retaining one-step information (i.e. single-step expansion) while eliminating the effect of biased value function estimation.
To relieve too much bias in the current MCTS's leaf node evaluation, mixing MC return of rollout policy and the output of the value network could also have been considered, as in AlphaGo (Silver et al. 2016). It would be great to see if STS still has advantages over MCTS in various leaf node evaluation situations.

Also, more writing effort may be required, and the current version of the manuscript seems premature to be published. There are some unclear or questionable parts.
- Algorithm 3 and Algorithm 4 are not the contributions of this work, thus they can be removed or moved to the Appendix. Instead, more discussions regarding the proposed method should have been placed in the main text.
- In Algorithm 2: the definition of CALCULATE_TARGET is missing.
- In Algorithm 5: In SELECT, the tree policy is defined by CHOOSE_ACTION that selects purely greedy action. If this describes the MCTS used in the experiments, I would say this is wrong. To make MCTS be properly working, an in-tree policy that balances exploration vs. exploitation is required (e.g. a classical choice is UCB rule).
- In Algorithm 6: In UPDATE, $N(s,a)$ and $quality$ are increased by $c$ times more, which means that the longer rollout length, the more weight is given. What is the reason for assigning more weight to the trajectory that has a longer rollout length? If the entire planning horizon is limited to finite length, this means that early simulations (short $path$ length, long $rollout$ length) have more weight than later simulations (long $path$ length, short $rollout$ length), but I do not think this is desirable. Is my understanding correct?
- For the Sokoban experiments, the pre-trained value function would significantly affect the performance of MCTS and STS, but I could not find the way how the value function was pre-trained.
- In Appendix A.2., the hyperparameters for Shooting and STS are very much different. Why did you set Shooting's hyperparameter differently from STS (e.g. VF zero-initialization, action sampling temp, etc.)?
- It seems that the choice of zero-initialization of the value network is rather arbitrary. I am not convinced that this would always work better. In some situations, optimistic initialization of the value network may be helpful to encourage exploration of the uncertain state regions.
- In Table 2, Why does RandomShooting-PPO underperform PPO? Since RandomShooting-PPO puts additional search efforts upon PPO, I expected that RandomShooting-PPO must outperform PPO.
- Table 5 could have been moved to the main text, replacing Table 2.

[1] Soemers et al., Enhancements for Real-Time Monte-Carlo Tree Search in General Video Game Playing, 2016 IEEE Conference on Computational Intelligence and Games (CIG 2016)

review_title: rather weak paper

final_score: rating: 4: Ok but not good enough - rejection
review_content: Summary:
This paper proposes a new algorithm named ‘Shoot Tree Search (STS)’ to perform planning in large state spaces. The authors construct STS by redesigning the expansion phase of MCTS using multi-step expansion. The authors provide pseudocode of the STS and compare the performance of STS and MCTS empirically in various domains, such as Sokoban, Google Research Football (GRF).
Comments:
Firstly, there is no intuitive explanation of why, what and how. Even after reading the paper, I do not agree that STS is good, because there is no intuition as to why it is better than naïve MCTS. More detail, I have a question - The main difference between STS and MCTS seems to be using multi-step expansion or 1-step expansion. Although multi-step expansion will gather more information about (s,a) pairs with high Q(s,a) value (because the actions chosen by argmax Q and STS expands such trajectories), but in sparse reward problem, STS and MCTS will work similarly. Moreover, before getting positive reward, STS may worse than MCTS because it requires more samples to explore (because STS uses more samples for (s,a) pairs with high Q-values, which is not meaningful yet). So I think that this paper needs at least discussion on an intuitive level about the advantage of STS.
In addition, the empirical details in appendix (figure 7 and 8 on page 18 and 19, respectively) look weird – each algorithm seems to have stopped randomly or incompletely.
Also, the authors seem to need to make an effort to make the paper more self-contained.
Minor comments
Some abbreviations are used without its full word or phrase. For examples, MCTS (it has been used in page 1, but the full phrase appears on page 3), and RL.
There are no reference for random shooting and bandit shooting. The authors should provide more explanation about them with references.
review_title:  New MCTS algorithm for large state spaces

final_score: rating: 6: Marginally above acceptance threshold
review_content: **Summary**
This paper presents a new planning algorithm, called Shoot Tree Search, to control the trade-off between depth and breath of the search. STS modifies the expansion phase of tree search by choosing multiple actions (e.g. $\gt$ 1) instead of one level expansion. The presented idea is simple and straightforward and seems to provide improvement over existing tree-based planning algorithms. The presented detailed ablation studies provides insights about the choices made in the paper. 

**Reasons for score**
Overall, I liked the paper and the simplicity of the idea. However, my major concern is the comparison with MCTS. I am not convinced that STS would outperform vanilla MCTS when the number of simulations is in order of thousands (e.g. the number of simulations in AlphaGo paper is around 1600). 

**Strengths**
+ The idea is simple and seems to outperform vanilla MCTS implementation in the environments with large action space.

**Weaknesses**
+ The comparison with the related work is not thorough which makes it hard to come into a decisive conclusion about the performance of the proposed method.
+  There are some missing related work, e.g. using policy network for multiple rounds of simulations.

**Questions**
+ What would the benefits if we have a policy network to perform the rollouts (e.g. a similar method to [1])?
+ In general, the benefit of MCTS algorithm (like AlphaGo which performs around 1600 simulations) presents itself when the number of simulations are large. Can you compare running MCTS with more number of simulations (e.g. large C) and STS?
+ Can you please provide some insights on why in 'Corner' STS underperform compared to random shooting?

[1] https://cs.brown.edu/people/gdk/pubs/analysis_mcts.pdf
review_title: The paper presents a simple extension to MCTS search by choosing multiple actions in each call to 'expansion' phase. The main concern with the paper is the number of simulations for MCTS.

final_score: rating: 3: Clear rejection
review_content: The authors present a method that combines Monte Carlo tree search (MCTS) and random rollouts. The authors their relate this to the bias-variance tradeoff observed in n-step temporal difference methods. The authors evaluate their method on Sokoban and the Google Football League environment. The results show that the authors' method leads to marginal improvements on these domains.

I do not think what the authors are doing is very novel as MCTS combined with rollouts was already used in AlphaGo. Furthermore, I believe the small difference in results can be made up by using only MCTS with a different exploration parameter (i.e. like the one that was used in the AlphaGo paper).

I would like to know what benefits this method brings that cannot be obtained from combining MCTS with rollouts as in AlphaGo or from a hyperaparameter search with MCTS. Is there an anaylsis of the bias variance tradeoff of this method?
review_title: A modification of Monte Carlo tree search that produces marginal improvements that may not be present with tuning of the Monte Carlo tree search exploration parameter

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary:
---

The paper presents "Shoot Tree Search", an approach that can basically be summarised as a variant of MCTS that expands (adds to the search tree) a longer sequence of up to H nodes to the tree per iteration, as opposed to the standard approach of expanding a single node per iteration. The experiments demonstrate improved performance in comparison to a "standard" MCTS and a variety of simpler rollout-based planning approaches, in challenging planning domains such as Sokoban and Google Research Football.

Strong Points
---

1) Well-written, mostly easy to read and understand.
2) Simple but interesting idea.
3) Thorough empirical evaluation, interesting results.

Weak Points
---

1. The paper describes the modification of MCTS into STS, which consists of making it expand a longer sequence of up to H nodes within a single iteration, as an entirely novel way to extend MCTS, but I'm not sure that that's entirely the case.  For instance, Coulom's 2006/2007 paper "Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search" already states: "In practice, not all the nodes are stored. Storing the whole tree would waste too much time and memory. Only nodes close to the root are memorized.", which suggests that something like this may have already been considered, but in that case was not found to be worthwhile. The 2016 paper "Enhancements for Real-Time Monte-Carlo Tree Search in General Video Game Playing" describes "In this paper, the tree is simply expanded by adding the whole play-out to the tree.", which seems similar.
I do still like that the paper performs a thorough evaluation of this idea, which I am not aware of appearing in previous literature, and the setting with DNNs for value / policy function approximations is also different from aforementioned papers which may lead to different trade-offs. The use of a DNNs for value function probably changes the story quite a bit here, because the longer horizon H also changes the point at which the value function is computed, as opposed to those older papers with values estimated by random rollouts (which remains the same regardless of the horizon H). So I'm not saying the idea isn't "novel enough", just that some discussion of past work seems to be missing.

2. In my experience, the primary reasons historically for the typical strategy of expanding just 1 node per iteration in standard MCTS (without DNNs) are 1) to reduce memory usage (especially when copies of game states are stored inside nodes, because then every node can be quite big), and 2) efficiency, because if you store copies of game states in nodes, and create more nodes, you also need to copy more game states (whereas a random playout without node and state storing can just roll out at once without making intermediate copies of states). I'm kind of missing a discussion of these kinds of considerations. 

3. I'm not sure that I can fully understand the experiment setup, in particular looking at Table 1. C is a hyperparameter denoting the number of planning passes, and N_p is described as "the average number of passes until the solution is found". How can N_p ever exceed C? Shouldn't it be upper bounded by C? I guess C might be the number of planning passes "per time step", and N_p is total over the entire episode, something like that? But this is not really clear to me. If the algorithms are really restricted to just C iterations of MCTS, I guess it's fair to always keep C*H constant and then my points above about memory usage / efficiency are not a big deal since they would still be equal across all scenarios... but I'm a bit confused here due to N_p exceeding C.

Overall Recommendation
---

Right now I have too many little points of confusion / missing discussion, as pointed out under "weak points" above, to recommend acceptance. That said, there is also enough to like about the paper, and I can easily envision that most of the points of confusion could be relatively straightforward to clear up in a revision.

Questions for authors
---

Could you please clarify on the points raised under "weak points" above?

Minor Comments
---

- On first page, the comma in "Google Research Football is, an advanced" seems unnecessary and confusing.
- On page 6, the wording "Shooting methods perform poorly for Sokoban" could be confusing because the newly proposed "Shoot Tree Search" method can very easily be interpreted as also being a "shooting method" due to its name.
- In Lemma A.6.1, the assumption that STS and MCTS build the same tree T seems to me like it's a VERY strong assumption; the MCTS has to make very very specific choices, with very frequent overlap making identical choices across different iterations (inherently somewhat unlikely due to the visit count terms in PUCT and other Selection strategies), for this to be true.

After Discussion
---

I increased my review from marginally below to marginally above acceptance threshold. Most of the remarks I had were at least partially addressed. If the paper gets accepted, I'd still recommend looking at some of them again and clarifying more. A simple, explicit remark somewhere around Table 1 explaining that N_p can indeed exceed C due to relevant parts of the search tree being preserved across time steps would help a lot. Some more explicit discussion about why the difference between using a trained value functions vs. heuristics / terminal results matters so much that it makes this substantially different from prior work would also help (I understand that it is because in prior work the only advantage of storing all those extra nodes was really just that it could retain slightly more information from backpropgations in those nodes, whereas in your case it changes which state is the state that gets evaluated by a trained value function, but this should be more explicit in the paper).
review_title: Review

Meta-review: This paper proposes a modification to MCTS in which a sequence of nodes (obtained by following the policy prior) are added to the search tree per simulation, rather than just a single node. This encourages deeper searches that what is typically attained by vanilla MCTS. STS results in slightly improved performance in Sokoban and much larger improvements Google Research Football.

R4 and R1 both liked the simplicity of the idea, with R1 also praising the paper for the thoroughness of its evaluation. I agree that the idea is interesting and worth exploring, and am impressed by the scope of the experiments in the paper as well as the additional ones linked to in the rebuttal. However, R1 and R5 explicitly noted they had many points of confusion, and across the reviews there seemed to be many questions regarding the difference between STS and other variants of MCTS. I also needed to read parts of the paper multiple times to fully understand the approach. If this many experts on planning and MCTS are confused, then I think readers who are less familiar with the area will definitely struggle to understand the main takeaways. While I do think the clarifications and new experiments provided in the rebuttal help, my overall sense is that the paper at this stage is not written clearly enough to be ready for publication at ICLR. I would encourage the authors to try to synthesize their results and organize them more succinctly in future versions of the paper.

One comment about a point of confusion that I had: I noticed the PUCT exploration parameter was set to zero for Sokoban, and one for GRF (with an explanation given that many values were tried, though these values are unspecified). As the exploration parameter is normally considered to be the thing that controls whether MCTS acts more like BFS ($c = \infty$) or DFS ($c = 0.0$), I would encourage the authors to more explicitly report which values they tried and to be clearer about the advantage of STS's multi-step expansions over low values of the exploration parameter.
Decision: Reject