We introduce "Search with Amortized Value Estimates" (SAVE), an approach for combining model-free Q-learning with model-based Monte-Carlo Tree Search (MCTS). In SAVE, a learned prior over state-action values is used to guide MCTS, which estimates an improved set of state-action values. The new Q-estimates are then used in combination with real experience to update the prior. This effectively amortizes the value computation performed by MCTS, resulting in a cooperative relationship between model-free learning and model-based search. SAVE can be implemented on top of any Q-learning agent with access to a model, which we demonstrate by incorporating it into agents that perform challenging physical reasoning tasks and Atari. SAVE consistently achieves higher rewards with fewer training steps, and-in contrast to typical model-based search approaches-yields strong performance with very small search budgets. By combining real experience with information computed during search, SAVE demonstrates that it is possible to improve on both the performance of model-free learning and the computational cost of planning.
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.