Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work investigates the problem of improving pretrained agents on discrete RL problems by using tree search. Using a ground-truth environment model, it finds that naively implemented tree search sometimes results in worse performance than no tree search at all. The authors provide analysis of this phenomenon in a simplified setting which shows that performing search on noisy Q estimates, especially with greater noise for states outside the span of the policy, results in taking incorrect actions. They introduce a correction term for tree search and show that it provides superior performance. The paper also includes a discussion of using batching to make tree search faster on accelerators, including using it to train agents.
main_review: This work has some interesting elements, but is currently a bit unpolished and is not ready for publication. The paper would benefit from increased focus on the discussion of overestimation and its correction, the most interesting and novel components. The section on batching forward passes during search for efficiency is described as novel but is routine in the model-based RL community. The discussion of training with tree search distracts from the central topic of the paper as it does not involve the problems of overestimation and distribution shift. 

### Structure and text
The basic setting, using a learned agent at test time with a greater degree of tree search than was used at training time, is straightforward and fairly common in model-based RL; see for example the appendix of [5]. The introduction would be stronger if it did not re-introduce this idea before discussing the contribution of this work specifically.

Figure 2 is nice and would be helpful if moved into the introduction to help set the scene for the reader.

In Figure 1, I believe the Q-values shown are the estimates (i.e. $\hat Q$). It would be helpful if the \hats were applied more consistently throughout the work.

Lemmas 3.1 and 3.2 are extremely unhelpful as written since they consist entirely of terms defined in the appendix. It would be much better if they were at least stated in a self-contained way, though of course the proofs can be deferred to the appendix. Even replacing them with easy-to-understand bounds would be more illuminating, especially given that we have already made some strong assumptions so the precise details are not so important.

`\widehat` would be helpful for defining the variance in Proposition 3.6.

While the top-line numbers for BCTS are good, this work would be much more compelling with additional investigative experiments. Is overestimation on little-visited states happening in practice during tree search? How much of the time? Does that over-estimation decay as predictions are further in the future, or does performance improve with increasing $d$ due to the $\gamma$ decay alone? (This would be surprising since $\gamma$ is usually very near 1.) Does the overestimation scale as predicted by your theory? Overall the theory is fine, but the assumptions are such that it should only be thought of as something to build intuition; I want to know if that's _really_ what's going on with a learned agent.


### Technical questions
In equation (1), I believe the max should be applied to both terms, i.e. the max over actions of (accumulated reward + bootstrap Q value)?

Assumption 1 deals with state and action trajectories, and defines one variance if the first action matches the policy and a different one otherwise. What about the rest of the actions? That is, as the assumption is written now, the variance of $\hat Q$ would be low even if every action other than the first was different than the one $\pi_o$ would take. Similarly in Assumption 2. Is this intended, and necessary to simplify the analysis?

Theorem 3.3 is maybe not quite what one would want to prove — the expected value of the estimator might be correct even while it produces incorrect actions much of the time. Indeed, by the assumptions we already have that $\hat Q$ is unbiased, and yet optimizing against it has bad outcomes. It might be difficult to prove, but a more compelling result would be about exactly how often this algorithm takes the optimal action with respect to the true $Q_d^{\pi_0}$.

Do you use sticky actions, as described by [4]? This makes the environments substantially less deterministic.

The results shown in Table 1 on training with tree search are striking, but the comparisons are not necessarily the most meaningful. Training with tree search is a question of policy optimization against a  _known model_, whereas the full reinforcement learning setting (which the baselines are operating in) involves no prior knowledge about the environment. I'm not too bothered with this though since I would recommend removing this section entirely.


### Novelty
This examination of overestimation and distribution shift is interesting, but not compellingly novel. I have seen related ideas in the literature though probably not constructed in exactly this way.

This paper touches on an interesting fundamental question that is fundamental in off-policy and offline reinforcement learning: how well does a Q function generalize, and how can we mitigate its variance for policy optimization? In the off-policy literature, there might be useful connections to draw to [2] and [3]. For offline RL, [1] might make a good starting point in the literature.

### References
1. Regularized Behavior Value Estimation, Gulcehre 2021
2. Double Q-learning, van Hasselt 2010
3. Addressing Function Approximation Error in Actor-Critic Methods, Fujimoto 2018
4. Revisiting the Arcade Learning Environment: Evaluation Protocols and Open Problems for General Agents, Machado 2017
5. Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model, Schrittwieser 2019
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In the setting where a pretrained value function is used in combination with MCTS, the authors show that because of the distribution shift problem, using the pretrained value function as the evaluation function in MCTS results in a performance worse than directly using the value function. Then, a correction term that in the end is based on the bellman error is proposed to resolve this issue. Experiments show that this correction term is effective. 

The second part of this paper proposes a more GPU compatible search method that seems to scale well when a GPU simulator is available. 
main_review: Clarity:
- the clarity of Section 3 can be greatly improeved. Can some of the lemmas be moved to the appendix? 
- also, I think more intuitive explaination of the correction term can help readers better understand the main idea. I am feeling that it is an intuitive method in the end that has been overcomplicated. 

Originality:
- the presented methods are new as I far as I know.

Quality:
- overall this submission seems technically sound.
- what are the limitations of your methods?
- does assumption 1 really holds in practice? 

Significance:
- this submission presents a nice solution to an interesting problem, which is the distribution shift problem when using pretrained value function in MCTS. 
limitations_and_societal_impact: My main suggestion is to improve the presentation of this submission, especially Section 3.

Second, I think more experimental results on other domains will also make the submission stronger. I am also interested to see search time constrained evaluation to understand to what extend the correction term can allow the performance of MCTS to be improeved with a pretrained value function. 

Minor:
- is there link to be made to [1]?


[1] Jiang, Nan, et al. "The dependence of effective planning horizon on model accuracy." Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems. 2015.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper is about combinations of Tree Search (TS) and trained value functions, where the value functions may already have been trained without involving any TS during training, in RL problems such as Atari games. Claimed contributions:

1) Identification and analysis of a distribution-shift phenomenon, where, if a value function was trained standalone (without TS), adding TS on top of it at evaluation time can actually reduce an agent's performance (relative to, say, a plain agent that is greedy w.r.t. the trained value function). The basic intuition for why this happens is as follows: during training, states that are more likely to be visited under the greedy policy (w.r.t. value function) show up more frequently in collected experience, and hence also get a more accurately-trained value function. A tree search (especially an exhaustive one) will run the value function significantly more often to also evaluate states that the greedy policy would rarely/never reach, and in these states the value function will have larger errors (which may be overestimating or underestimating errors). Because there are usually more paths through the tree that the greedy policy would not visit than there are paths that the greedy policy would visit, the number of branches with large errors are likely to outnumber the branches with smaller errors. This outnumbering leads to a maximisation bias, where, when there are multiple such branches with large errors, likely at least one of them will be overestimating, causing the tree search to prioritise that branch over one with a more accurately-trained value function.

2) A correction term that allows a new "BCTS" tree search algorithm to function well with a pre-trained value function.

3) An approach named Batch-BFS to efficiently, on a GPU, run a breadth-first-style tree search with trained value function (assumes, I think, that the forward model of the environment, like an Atari game, itself can also be implemented to run on the GPU).

The resulting Batch-BFS approach outperforms DQN and Rainbow on several Atari games.
main_review: Overall I think the paper is solid in all the core aspects (originality, quality, clarity, and significance). I do have several more detailed comments below, but do not think any of them should be a major issue to address:

1) First two paragraphs of Introduction discuss how the paradigm of MCTS would be less suitable for continuous/large state spaces or image-based domains, and how the more simple "breadth-first-style" TS used in this paper would be more suitable without requiring any memorization, but I don't see why this is true. MCTS has no more problems with continous or large state spaces than a BFS would. With an extremely large or continuous state space, MCTS would likely struggle to grow a sufficiently large tree to fully cover that space... but that holds for any other tree search too. I wonder, with the references to image-based domains and memorization, are the authors actually thinking of problems with a large state **representation** (rather than state space), i.e. problems where a single state requires a large amount of memory to store? Again, I'm not sure that I agree that this is necessarily that much of a problem for MCTS. If it takes too much memory to stores states in nodes, it is also possible to implement MCTS by only storing actions along the edges, and use those actions to recreate the state as the algorithm traverses the tree.

2) Section 4 states that Batch-BFS is proposed "to solve this issue" [= the issue that the number of nodes to evaluate scales exponentially with search depth d]. I think that "solve" may be too strong a word here. I'll happily believe that GPUs allow for significantly more parallelisation than CPUs, and can meaningfully increase the search depth that can feasibly be reached... but I don't see that as really **solving** the issue of exponential growth. There is still exponential growth, and exponential growth will at some point catch up again and even make a GPU struggle. Maybe just something like "mitigate" or "address" would be more fair. On a related note, it would be interesting to see what kinds of search depths match the numbers of leaves reported on the x-axes of Figure 3.

3) In *"Revisiting the Arcade Learning Environment: Evaluation Protocols and Open Problems for General Agents"*, Machado et al. (2018) investigated how, due to the determinisim in ALE, many approaches turn out to be able to perform well in these environments simply by memorising strong action sequences, and propose using *sticky actions* (in training as well as evaluation) to disincentivise such solutions (as opposed to ones that actually learn to make informed decisions based on the state and generalise to new circumstances). Were sticky actions used in any of the trainings or evaluations in this paper? I think this is a particularly interesting question in the context of this paper, because the use of sticky actions during training would force a bit more exploration and force the value function to be applicable to a more diverse set of states than in a (close to) deterministic environment. To what extent would such a training practice mitigate the bias and maybe reduce or eliminate the need for a correction?

---

Minor comments:
- Quotes on left-hand side of words "Left" and "Right" on bottom of page 3 should "point" the other way (opening instead of closing quotes)
- Footnote 1 states the Atari environments used are "close to deterministic". Is it possible to elaborate on in what way(s) they are *not* deterministic?
- Line 123: evidence support --> evidence supports
- Line 154: Technically, I guess it does not necessarily hold exactly that the expectation of Q-hat equals Q when trained using Rainbow? There may be errors due to imperfect function approximation, probably a bias from Prioritized Experience Replay since it's customary to only partially correct for its non-uniform sampling with importance sampling, and if I recall correctly also only partial or no correcting for biases due to multi-step off-policy update steps in Rainbow. Maybe all of this is not too relevant to this paper though.
- In Figure 2, is it correct to state that the red states were "not visited/observed during training"? I get that they are likely visited *less frequently*, but not entirely unvisited, right?
- Caption Figure 4: "a deeper tree often degrades the performance of vanilla TS" --> is it really fair to say "often" here? I see this primarily being the case just in Frostbite, plus in most of the other games specifically when going from depth 0 --> 1, but not anymore when increasing depth beyond 1.
limitations_and_societal_impact: Limitations are adequately addressed in the paper, except possibly somewhat of a limitation in the experiments, see point 3) in the main review above.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors introduce a new tree search technique that can be used to improve the score of trained RL agents online. They propose an analysis of the counter-intuitive phenomenon that applying standard MCTS with a pre-trained value function is less performant than using directly the value function in spite having access to more information. 

The first contribution is an analysis of TS and the introduction of an off-policy correction term based on the analysis. The second contribution is a GPU adaptation of TS making it fast at inference time but also possible to train tree based agents in a scalable way.

The paper is well written and addresses an interesting problem and the proposed method could be used in many RL algorithms and applications. The GPU implementation seems somewhat disconnected to the rest of the paper. 

main_review: The authors attribute the performance loss of standard tree search to a distribution shift. When using the estimated value function to guide the tree search, it is evaluated in states poorly explored during training, with inaccurate value estimate and hence downgrade the performance of the whole tree search. 

Empirical analysis of the degradation caused by TS:

They provide empirical proof and a further theoretical analysis. I think the empirical proof lack of details, fortunately I had observed this phenomena in my own experiments and was not to be convinced.
-	“We also measure the off-policy distribution shift between \pi_0 and the TS policy by counting disagreements “ In this above sentence, do the author use pi_0 in the TS as well?
-	This section on empirical proof of the discrepancy between TS and pi_0 lacks a bit of precision. The author should provide more details at least in appendix. Does the computation budget of the tree search affect these results? Did they use any exploration policy (e.g. UCB) in the tree search?

Regarding the theoretical analysis: 

The author assume that the value estimate follows a normal distribution with two different deviations depending on whether the action follows the original policy or not. Although simplistic this assumption seems reasonable enough to provide a first analysis of the problem and is well justified by the authors.

In assumption 2: shouldn’t the value function be Q_d^{\pi_0} instead of Q^{\pi_0}? The justification for assumption 2 is not as clear.
Throughout the analysis the author separate the cases where the action follows the original policy or other branches of the tree. The dichotomy is used in all the subsequent proofs. It results in two different biases for the “pi-0 following branch” and the other branch. 

The two biases are used to provide a correction term in the action selection procedure of the tree. With another approximation, the authors derive a very simple formula for approximating the correction term as a function of: the size of the action space, the depth of the tree, sigma_e, sigma_o. The two standard deviations are introduced in assumption 1. 

The rest of the analysis shows that the probability of selecting a suboptimal action is bounded.

The overall analysis strongly rely on assumption 1 but seems sound and correct overall, leading to a practical correction term with two parameters to estimate. The remaining of the section provide guidance in how to estimate sigma_o and sigma_e. The author should provide an algorithm, or an intuitive explanation on how to practically estimate those two parameters, I think proposition 3.6 provides a theoretical justification but it is unclear how to practically implement it.

Scalability:

This part addresses a completely different problem of TS: scalability. TS is usually expensive to run as it requires many online simulations growing exponentially with the depth. The authors rely on GPUs to address the scalability issue. This contribution is not theoretical but practical.

The author provide a pseudo-code of the solution but no explanation is given. The diagram in the appendix is helpful and should in my opinion replace the provided pseudo-code.

Without surprise, the parallel implementation outperforms standard TS for a large number of leaves in terms of runtime. The batch BFS implementation consists in evaluating each level of the tree at the same time in a “batch”. It is unclear how this method can be used with TS techniques using pruning or UCB type branching. 

Inference Experiments:

The experiments support the claim, BCTS provides consistent improvement over rainbow and standard TS. 
“As for BCTS, we found that multiplying its correction term (see (6)) by a constant that we sweep over can improve performance; we applied this method for the experiments here.” 
This constant is not mentioned in the analysis and should be further discussed. If sweeping of a constant is being used, one wonders if estimating delta_e and delta_o is really useful or if we could just do parameter sweeping as well. 

Training experiments:

The author don’t use the BCTS algorithm but the batch-BFS only for this set of experiments. However the author mention that they use another corrected update? Clarification needed.
The results in table 1 should also include the pre-trained rainbow + BCTS for a full comparison of the proposed methods.

limitations_and_societal_impact: This work requires models or simulators for tree search to be applied but overall it can touch a broad range of applications beyond games.
review_title: null

Meta-review: This is a solid paper and set of contributions. There are certainly areas where it could be improved; to me these are primarily around the structure of the paper and writing (not that these are poor, but there are these two essentially distinct contributions that some reviewers get tripped up on). z7iw points out that related ideas can be found in the literature and that this negatively impacts novelty, and I agree that this overlap exists but would argue that whatever minor hit novelty takes it is made up for by how this can unify understanding of where these challenges arise. There are several concrete suggestions (or areas for clarification) that the reviewers have brought up, and the authors are encouraged to include them in the final version of the paper.
Decision: Accept (Poster)