Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper proposes an approach, named SAVE, which combines model-free RL (e.g. Q-learning) with model-based search (e.g. MCTS). SAVE includes the value estimates obtained for all actions available in the root node in MCTS in the loss function that is used to train a value function. This is in contrast to closely-related approaches like Expert Iteration (as in AlphaZero etc.), which use the visit counts at the root node as a training signal, but discard the value estimates resulting from the search. 

The paper provides intuitive explanations for two situations in which training signals based on visit counts, and discarding value estimates from search, may be expected to perform poorly in comparison to the new SAVE approach:
1) If a trained Q-function incorrectly recommends an action "A", but a search process subsequently corrects for this and deviates from "A", no experience for "A" will be generated, and the incorrect trained estimates of this action "A" will not be corrected.
2) In scenarios with extremely low search budgets and extremely high numbers of poor actions, a search algorithm may be unable to assign any of the visit count budget to high-quality actions, and then only continue recommending the poor actions that (by chance) happened to get visits assigned to them. 

The paper empirically compares the performance of SAVE to that of Q-Learning, UCT, and PUCT (the approach used by AlphaZero), on a variety of environments. This includes some environments specifically constructed to test for the situations described above (with high numbers of poor actions and low search budgets), as well as standard environments (like some Atari games). These experiments demonstrate superior performance for SAVE, in particular in the case of extremely low search budgets.

I would qualify SAVE as a relatively simple (which is good), incremental but convincing improvement over the state of the art -- at least in the case of situations with extremely low search budgets. I am not sure what to expect of its performance, relative to PUCT-like approaches, when the search budget is increased. For me, an important contribution of the paper is that it explicitly exposes the two situations, or "failure modes", of visit-count-based methods, and SAVE provides improved performance in those situations. Even if SAVE doesn't outperform PUCT with higher search budgets (I don't know if it would?), it could still provide useful intuition for future research that might lead to better performance more generally across wider ranges of search budgets.


Primary comments / questions:

1) Some parts of the paper need more precise language. The text above Eq. 5 discusses the loss in Eq. 5, but does not explicitly reference the equation. The equation just suddenly appears there in between two blocks of text, without any explicit mention of what it contains. After Eq. 6, the paper states that "L_Q may be any variant of Q-learning, such as TD(0) or TD(lambda)". L_Q is a loss function though, whereas Q-learning, TD(0) and TD(lambda) are algorithms, they're not loss functions. I also don't think it's correct to refer to TD(0) and TD(lambda) as "variants of Q-learning". Q-learning is one specific instead of an off-policy temporal difference learning algorithm, TD(lambda) is a family of on-policy temporal difference learning algorithms, and TD(0) is a specific instead of the TD(lambda) family.

2) Why don't the experiments in Figures 2(a-c) include a tabular Q-learner? Since SAVE is, informally, a mix of MCTS and Q-learning, it would be nice to not only compare to MCTS and another MCTS+learning combo, but also standalone Q-learning.

3) The discussion of Tabular Results in 4.1 mentions that the state-value function in PUCT was learned from Monte-Carlo returns. But I think the value function of SAVE was trained using a mix of the standard Q-learning loss and the new amortization loss proposed in the paper. Wouldn't it be more natural to then train PUCT's value function using Q-learning, rather than Monte-Carlo returns?

4) Appendix B.2 mentions that UCT was not required to visit all actions before descending down the tree. I take it this means it's allowed to assign a second visit to a child of the root node, even if some other child does not yet have any visits? What Q-value estimate is used by nodes that have 0 visits? Some of the different schemes I'm aware of would involve setting them to 0, setting them optimistically, setting them pessimistically, or setting them to the average value of the parent. All of these result in different behaviours, and these differences can be especially important in the high-branching-factor / low-search-budget situations considered in this paper.

5) Closely related to the previous point; how does UCT select the action it takes in the "real" environment after completing its search? The standard approach would be to maximise the visit count, but when the search budget is low (perhaps even lower than the branching factor), this can perform very poorly. For example, if every single visit in the search budget led to a poor outcome, it might be preferable to select an unvisited action with an optimistically-initialised Q-value.

6) In 4.2, in the discussion of the Results of Figure 3 (a-c), it is implied that the blue lines depict performance for something that performs search on top of Q-learning? But in the figure it is solely labelled as "Q-learning"? So is it actually something else, or is the discussion text confusing?

7) The discussion of Results in 4.3 mentions that, due to using search, SAVE effectively sees 10 times as many transitions as model-free approaches, and that experiments were conducted on this rather complex Marble Run domain where the model-free approaches were given 10 times as many training steps to correct for this difference. Were experiments in the simpler domains also re-run with such a correction? Would SAVE still outperform model-free approaches in the more simple domains if we corrected for the differences in experience that it gets to see?


Minor Comments (did not impact my score):
- Second paragraph of Introduction discusses "100s or 1000s of model evaluations per action during training, and even upwards of a million simulations per action at test time". Writing "per action" could potentially be misunderstood by readers to refer to the number of legal actions in the root state. Maybe something like "per time step" would have less potential for confusion?
- When I started reading the paper, I was kind of expecting it was going to involve multi-player (adversarial) domains. I think this was because some of the paper's primary motivations involve perceived shortcomings in the Expert Iteration approaches as described by Anthony et al. (2017) and Silver et al. (2018), which were all evaluated in adversarial two-player games. Maybe it would be good to signal at an early point in the paper to the reader that this paper is going to be evaluated on single-agent domains. 
- Figure 2 uses red and green, which is a difficult combination of colours for people with one of the most common variants of colour-blindness. It might be useful to use different colours (see https://usabilla.com/blog/how-to-design-for-color-blindness/ for guidelines, or use the "colorblind" palette in seaborn if you use seaborn for plots).
- The error bars in Figure 3 are completely opaque, and overlap a lot. Using transparant, shaded regions could be more easily readable.
- "... model-free approaches because is a combinatorial ..." in 4.2 does not read well.
- Appendix A.3 states that actions were sampled from pi = N / sum N in PUCT. It would be good to clarify whether this was only done when training, or also when evaluating.
review_title: Official Blind Review #4

final_score: rating: 6: Weak Accept
review_content: This paper proposes Search with Amortized Value Estimates (SAVE), which combines Q-learning and Monte-Carlo Tree Search (MCTS). SAVE makes use of the estimated Q-values obtained by MCTS at the root node (Q_MCTS), rather than using only the resulting action or counts to learn a policy. It trains the amortized value network Q_theta via the linear combination of Q-learning loss and the cross-entropy loss between the softmax(Q_MCTS) and softmax(Q_theta). Then, SAVE incorporates the learned Q-function into MCTS by using it for the initial estimate for Q at each node and for the leaf node evaluation by V(s) = max_a Q_theta(s,a). Experimental results show that SAVE outperforms the baseline algorithms when the search budget is limited.


- The idea of training Q-network using the result of MCTS planning is not new (e.g. UCTtoRegression in Guo et al 2014), but this paper takes further steps: the learned Q-network is again used for MCTS planning as Q initialization, the cross-entropy loss is used instead of L2-loss for the amortized value training, and the total loss combines Q-learning loss and the amortization loss.
- In Figure 1, it says that the final action is selected by epsilon-greedy. Since SAVE performs MCTS planning, UCB exploration seems to be a more natural choice than the epsilon-greedy exploration. Why does SAVE use a simple epsilon-greedy exploration? Did it perform better than UCB exploration or softmax exploration? Also, what if we do not perform exploration at all in the final action selection, i.e. just select argmax Q(s,a)? Since exploration is performed during planning, we may not need exploration for the final action selection?
- Can SAVE be extended to MCTS for continuous action space? SAVE trains Q-network, rather than a policy network that can sample actions, thus it seems to be more difficult to deal with continuous action space.
- In Eq. (5), we may introduce a temperature parameter that trade-offs the stochasticity of the policy to further improve the performance of SAVE.
- In Tightrope domain (sec 4.1), it says: "The MDP is exactly the same across episodes, with the same actions always having the same behavior.", but it also says: "In the sparse reward setting, we randomly selected one state in the chain to be the “final” state to form a curriculum over the length of the chain." It seems that those two sentences are contradictive.
- In the Tightrope experiment's tabular results (Figure 2), the performance of Q-learning is not reported. I want to see the performance of Q-learning here too.
- In Figure 2, the search budgets for training and testing are equal, which seems to be designed to benefit SAVE than PUCT. Why the search budget should be very small even during training? Even if the fixed and relatively large search budget (e.g. 50 or 100) is used during training and the various small search budgets are only used in the test phase, does SAVE still outperform PUCT?
- In Figure 2 (d), model-free Q-learning does not perform any planning, thus there will be much less interaction with the environment compared to SAVE or PUCT. Therefore, for a fair comparison, it seems that the x-axis in Figure 4-(d) should be the number of interactions with the environment (i.e. # queries to the simulator), rather than # Episodes. In this case, it seems that Q-Learning might be much more sample efficient than SAVE.
- In Figure 3, what is the meaning of the test budget for Q-Learning since Q-Learning does not have planning ability? If this denotes that  Q-network trained by Q-learning loss is used for MCTS, what is the difference between Q-Learning and SAVE w/o AL?
- In Figures 3, 4, 5, it seems that comparisons with PUCT are missing. In order to highlight the benefits of SAVE for efficient MCTS planning, the comparison with other strong MCTS baselines (e.g. PUCT that uses learned policy prior) should be necessary. A comparison only with a model-free baseline would not be sufficient.


-----
after rebuttal:

Thank the authors for clarifying my questions and concerns. I feel satisfied with the rebuttal and raise my score accordingly.
review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: This paper proposes SAVE that combines Q learning with MCTS. In particular, the estimated Q values are used as a prior in the selection and backup phase of MCTS, while the Q values estimated during MCTS are later used, together with the real experience, to train the Q function. The authors made several modifications to ‘standard’ setting in both Q learning and MCTS. Experimental results are provided to show that SAVE outperforms generic UCT, PUCT, and Q learning.

Overall the paper is easy to follow. The idea of the paper is interesting in the sense that it tries to leverage the computation spent during search as much as possible to help the learning. I am not an expert in the of hybrid approach, so I can not make confident judgement on the novelty of the paper.

 The only concern I have is that the significance of the result in the paper:
1. The proposed method, including the modifications to MCTS and Q learning (section 3.2 and 3.3), is still a bit ad-hoc. The paper has not really justified why the proposed modification is a better choice except a final experimental result. Some hypotheses are made to explain the experimental results. But the authors have not verified those hypotheses. Just to list a few here: (a). The argument made in section 2.2 about count based prior; (b). the statement of noisy Q_MCTS to support the worse performance of L2 loss in section 4.2; (c). In the last paragraph of section 4.3, why would a model free agent with more episodes results in worse performance?
2. The baselines used in this paper are only PUCT and a generic Q learning. What are the performances of other methods that are mentioned in section 2.1, like Gu 2016, Azizzadenesheli 2018, Bapst 2019? 

Other comments:
1. What is the performance of tabular Q-learning in Figure 2 (a-c)?

review_title: Official Blind Review #3

Meta-review: This paper proposes Search with Amortized Value Estimates (SAVE) that combines Q-learning and MCTS.  SAVE uses the estimated Q-values obtained by MCTS at the root node to update the value network, and uses the learned value function to guide MCTS.

The rebuttal addressed the reviewers’ concerns, and they are now all positive about the paper. I recommend acceptance.
Decision: Accept (Poster)