Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: The authors introduce Virtual MCTS which approximates its vanilla version with a smaller amount of computations. They also perform theoretical analysis as well as empirical performance analysis on 9x9 Go and the Atari game. 

strengths_and_weaknesses: While the topic seems reasonable, I have a difficulty in understanding the problem they attempt to address (see the questions).  Typically game-playing programs have time management algorithms but the authors does not mention the approach.  

For example, 

https://dke.maastrichtuniversity.nl/m.winands/documents/time_management_for_monte_carlo_tree_search.pdf

https://www.remi-coulom.fr/Publications/TimeManagement.pdf

In addition, their comparison is against vanilla UCT. But another naive baseline is to stop UCT if the best move is much better than the others. It could be estimated by considering the number of visits and the reward received so far.

Misc. 
Page 3: "Equation (1)"

Is this correct?

Page 3: "Thus, MCTS-based RL is roughly N times computationally more expansive than traditional RL algorithms"

expensive

Page 3: "It is consists of two components:" 

It consists of

Page 4: "... illustrated in Algorithm 1, 2"

Algorithms 1 and 2

questions: Does Virtual MCTS attempt the time required for MCTS only when a model is trained? Or does it also attempt to reduce the time when playing a game against its opponent?

It apparently does not look Algorithms 1-2 are for the latter case. 

limitations: NA
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposes a modification to the Monte-Carlo Tree Search paradigm---specifically, the UCT algorithm---that is more sample efficient. The method attempts to use its "thinking time" more wisely: as the authors describe it, their tree-building algorithm seeks to spend more time when evaluating "harder" states and less time on "simpler" states (i.e., states that are less positionally complex, and where the best action can be determined more easily). Identifying these situations is accomplished by noting when additional iterations of search would not appreciably change the visitation distribution of the actions at the root node (i.e., the stochastic policy at the root node). Specifically, on each iteration of tree-building, after the traditional loop of node selection-expansion-evaluation-value propagation is completed, some additional computation is performed -- what the authors term "virtual expansions". In this phase, $N-k$ "pulls" of the arms of the root node are performed, according to the selection strategy (for eg., UCB1), _but without descending down the tree further_ ($N$ = total search budget measured by iterations, $k$ = current iteration index). Instead, after each pull, the current average utiltity of that action $Q(s, a)$ is used as the reward, so that the only modification to the statistics accumulated in the nodes at level 1 in the search tree are in the visitation counts. The policy induced by the combination of "regular" tree-building and virtual expansions is tracked over time; when it begins to show signs of convergence (i.e., the norm between the policies from two sufficiently different iterations is sufficiently small), the search is terminated. The authors provide two theorems that characterize the nature of this convergence, as well as empirical evaluation in several domains---9x9 Go and five Atari games---to demonstrate the validity and benefit of their approach.
strengths_and_weaknesses: Originality:
(+) The simplicity of the approach is a strength in my opinion. The idea is fairly straightforward, and the fact that it results in significant gains in a number of application domains is noteworthy.

Significance:
(+) MCTS is of broad interest in the ML and AI communities and papers that deal with enhancements to the baseline algorithm or propose novel applications are often published at NeurIPS. So the paper is likely to be of interest to many researchers.

Quality:
(+) The paper contains a nice balance of theory and experiment. The main theorems suggest that the authors' proposed approach should provide some benefits, and the empirical evaluation reinforces this.
(+) The gains in performance are particularly strong in 4/5 Atari domains, where V-MCTS (the authors' approach) outperforms vanilla MCTS while building much smaller search trees (typically, only 50% as big).
(+) The ablation experiments involving tuning the algorithm hyperparameters $r$ (the search budget ratio) and $\epsilon$ (which determines the tolerance criterion for convergence) were useful for evaluating their impact on performance.
(-) The results in 9x9 Go were however less compelling to me. The evidence here did not appear to support the authors' conclusions -- vanilla UCT was shown to be a little slower to act, but also a little stronger as a player. So claiming that V-MCTS was somehow preferable here, or a superior choice (265--266: "Therefore, such termination rule can keep strong performances with less budget.") is not borne out by the data.
(-) The qualitative analysis in Fig. 3 about V-MCTS spending more time in challenging positions and less time in less complex positions was welcome, but drawing such samples from a single game seems a little anecdotal. Aggregating information over many more such positions would have made for a stronger argument and paper. 

Clarity:
Unfortunately, this was the weakest element of the paper, which relegates it to a borderline accept
in my eyes. The lack of clear writing and visualizations made it harder to evaluate some of the claims; it also raises questions about the reproducibility of the work. More specifics are provided in the next section, but I outline some broad issues here.
(-) No details are provided about the training procedure. EfficientZero is mentioned in Section 5.1, but it's not clear if that was the training procedure that was used. It's not clear if the code for reproducing the results will be made available.
(-) I found Fig. 1(a) difficult to understand, as it lumps together different algorithms that are being parameterized in different ways. I was also a little confused by why there was a _curve_ for GnuGo, which is an off-the-shelf Go playing engine -- presumably, the authors did not retrain this agent from scratch, so why are there different points along the $x$-axis for this player?
(-) The proofs for theorems 4.1 and 4.2 are presumably in the Appendix, so their proofs could not be verified; while I understand the authors are operating under space constraints, it would have been nice to at least see a proof sketch.
questions: (1) In all of the comparisons, V-MCTS was upper-bounded in how large a tree it could build. A complementary analysis where it was given a fixed _time_ budget would have been useful to see: to see if given a fixed amount of time, it could make better decisions than a vanilla MCTS using the same amount of time.

(2) The convergence criterion appears to rely on when the L1 norm of the policy at the root node converges; but I'm wondering if this is the best choice. There is an argument to be made for the L2 norm instead: bigger deviations should be amplified more, over an accumulation of smaller deviations, as this could change what action would be picked at the root. Or to ignore the specific distribution and focus on the _ordering_ of the nodes. It would be interesting to hear from the authors whether these alternatives were considered.

(3) Lines 58--59: "Afterward, UCT algorithms have generally replaced earlier heuristic methods for Monte-Carlo tree search (MCTS), which apply UCB1 to select action at each node of the tree" -- this framing not quite accurate. UCT is a specific instantiation of the MCTS family of algorithms, so saying it has "replaced" MCTS doesn't quite make sense.

(4) Lines 63--65: "There are three kinds of bottlenecks in vanilla MCTS in the aspect of speed: the selection stage of each iteration, the evaluation stage of each iteration, and the search loop." -- I found this confusing, since the search loop _includes_ selection and evaluation steps.

(5) Line 5 in Alg. 1, Line 9 in Alg. 2 -- I believe these should read UCB1(Q, P, N), rather than UCT(Q, P, N) (UCT is the overall algorithm, UCB1 (or a variant) is the bandit algorithm that is handling the selection step). Similarly, Line 4 in Alg. 3 -- should probably read "Selection with UCB1".

(6) In Theorem 4.1(a), what does the $\Cup$ (set intersection) mean? Did you mean $\Wedge$, i.e., an AND over the bounds on all possible actions?

(7) There are also typos and grammatical issues throughout the paper, that could be eliminated with a careful and thorough read through. Here's a small sampling just from the first page:
11--12: "while requiring less than 50% number of search times on average." --> "less than 50% search time"
19: "recent AI researches" --> "research"
26--27: "It is the first time for a computer program to beat a human professional Go player." --> "first time a computer program beat a human..."
29--30: "Later, MCTS-based RL algorithms are further extended to other board games and Atari games" --> Later, MCTS-based RL algorithms were further extended..."
32--33: "...they require massive computations to train and evaluate." ---> "...they require massive amounts of computation..."

limitations: Yes -- any concerns have been raised in other sections.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposed a novel method named Virtual MCTS (V-MCTS) to reduce the computation time of vanilla MCTS with the Virtual Expended Termination Rule (VET-Rule). This paper also gives theoretical bounds of the proposed method and evaluates the performance and computations on 9 × 9 Go board games and Atari games. Experiments show that this method can achieve comparable performances to the original search algorithm while requiring less than 50% search times on average. In general, this paper shows that V-MCTS can think faster on simple states and longer on hard states. For solid theoretical analysis and positive experimental results, I would recommend the acceptance of this paper. 

strengths_and_weaknesses: *Strengths*

* This paper gives the theoretical bounds of the proposed method with proof. Namely, for any given epsilon with sufficient large N, if the policy distance between k and k/2 is smaller than epsilon, then the distance between k and N is smaller than 3*epsilon. This theoretical result supports an early stop of MCTS search, which I believe has some impact. The theoretical analysis is sound, after I verify the proofs of Theorem 4.1 and 4.2 in Appendix (a little bit hard to read though).
* In the experiments with Go 9x9 and Atari, V-MCTS shows that this method can achieve comparable performances to the original search algorithm while requiring less than 50% search times on average. 
* There is a comparison with DS-MCTS (a past work in AAAI), and V-MCTS still has better performance.

*Weaknesses*

Some minor presentation problems listed in Questions Section. 


questions: According to the proof given by the authors, V-MCTS’ Error Bound is still effective for programs that do not use virtual expansions during training. We should be able to apply V-MCTS to all pre-trained Top Go 19x19 programs, like KataGo or Leela Zero. How does V-MCTS work on these strong programs?

Some minor comments about presentations. 
* In experiments, N = 150. I am just wondering what N_0 would be to satisfy Theorem 4.2, if N=150. 
* It is unclear about ‘3 different runs’ in Tables 1~3. The authors need to clarify it. 
* Please keep the consistency of the symbols, for example, $\epsilon$ and $eps$.
* Line 186: highlighted in line 5 -> highlighted in line 6
* In Algorithm 3, the symbols in line 10 are unclear and confusing to the reader. Explain why the ratio (the visitation of an action in a state divided by N) is the policy of this state. Where is that action? This conflicts with the situation in line 8.

limitations: Yes
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposes V-MCTS, containing two main improvements over classic MCTS. First, the authors propose virtual expansion by applying rollout without actual simulation (the simulation returns are replaced by the current Q value. Next, V-MCTS uses an adaptive termination condition to decide when to stop doing rollout. The proposed algorithm is evaluated on 9x9 Go and five Atari games.
strengths_and_weaknesses: Improving the efficiency of MCTS is very important since they typically require a huge amount of computation resources. This paper proposes two techniques: virtual expansion and an early-termination condition.

Virtual expansion aims to mitigate the problem that exploratory behavior of the MCTS rollouts can "mask out" information about the action with the highest expected reward. For example, if the agent is given a budget of 100 rollouts and it has only figured out a promising path at the 95th rollout. The last 5 rollouts may not be sufficient to backpropagate this information up to the root node. In such cases, applying virtual expansion to backpropagate such information could be helpful. This is also justified by the ablation study in Sec. 5.4.

However, while virtual expansion could be useful in the above-mentioned scenario, I think it (i) could be implemented by an action selection policy for best-arm identification (BAI) and (ii) might only be useful in games with less chaotic rewards. (i): For example, it is possible that simply selecting the action that leads to the best cumulative reward seen in the rollouts can be as good as virtual expansion. (ii): For tasks where the reward function has high variance, it seems possible that virtual expansion will be fooled by some high rewards collected by chance. To allow better justification of the virtual expansion idea, it would be great if the authors could compare it with other action selection strategies (e.g., select by Q value, and some BAI strategies).

The theoretical analysis in the paper shows that V-MCTS will converge to the optimal policy as the number of rollouts increases, but it does not provide additional intuition on the comparison between vanilla MCTS and V-MCTS. Specifically, according to Thm 4.1, we still need k to be sufficiently large in order to guarantee e.g. BAI. Also, the theorems do not take into consideration the early-termination condition.
questions: - How does virtual expansion compare with other action selection strategies (e.g., select by Q value, and some BAI strategies)?

- The empirical results are only tested with very few number of rollouts (<20 rollouts on Atari, and <150 on Go), and it remains unsure whether the proposed techniques are useful in more general cases.
limitations: The authors addressed the limitations and potential negative societal impact of their work.
review_title: null

Meta-review: metareview: I found this to be an interesting paper.  As the reviewers indicated, it could be improved in terms of clarity, and I strongly encourage the authors to consider those comments carefully, as ultimately this could only make their paper more impactful.

In particular, the authors could consider how to be clearer about their claims, and how to provide stronger evidence for these.  For instance, a claim like "It can maintain comparable performances while reducing half of the time to search adaptively" is very general, and it is unclear that it is really true: for instance, is this true under _all_ conditions?

That said, I believe the paper is clear enough, and the method is simple enough, that it might be of interest to the community, and I think it would be good to accept it for presentation at the conference.  This agrees with most reviewers, three of whom voted to accept the paper.  I do agree with the one reviewer voting to reject that I'm somewhat unsure how this compares to other reasonable approaches, but I think this can be further discussed in follow-up papers as well.
confidence: Less certain
Decision: Accept