Venue: ICLR 2021 Conference

Reviews:

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

This paper extends the idea of momentum, commonly used in optimization literature, to Temporal Difference (TD) learning which is a widely used algorithm for policy evaluation in Reinforcement learning literature. The main challenge in this work is to account for the 'optimization bias' introduced by using momentum based updates. The authors propose to do this via a Taylor approximation to the TD update and empirically show the merits of this idea on some toy data sets as well as on an Atari game. 

Reason for score: 

The idea of using momentum for TD learning seems quite interesting. However, in my opinion, the paper seems to a somewhat incremental contribution, given the work of Sun et. al. 2020, which gives a theoretical analysis of momentum based updates for TD with linear function approximation. 

1) The bias correction via Taylor approximation of the gradients seems new to me. The authors claim that the bias doesn't play a significant role in supervised learning tasks. Can the authors provide some more citations to support this besides the 1-d regression task. For TD learning, the authors don't present results for bias corrections with second order terms. How do we know that we can safely ignore these for large networks? On the other hand, incorporating these terms poses a computational challenge. 

2) Prior work of Sun et. al. 2020, which proposes a momentum for a linear function approximation, uses projection to bound the iterates. Is the momentum update even stable for deep neural networks for large problems, without some additional tricks? The authors only test toy examples (the Atari example has some combination of Adam and momentum which makes it ).  

3) For the comparison on MsPacman, why is a combination with Adam required? The authors claim it is for speeding up learning. In this case, maybe the authors can have the MSE plot for just Adam updates for a better comparison? 

4) Many of the plots are truncated at a few thousand steps. What happens after that? It might be helpful to visualize the loss at limit points that different updates converge towards (roughly). Graphs with more steps might be more useful.

5) The authors claim their method improves sample complexity as compared to say the more widely used trick of freezing network. But Figure 17 shows that models with frozen targets eventually become more precise. This might be a reason why this idea may not perform well in the control setting, as Figure 17 suggests that there is probably a residual bias in all momentum based updates (when used with neural networks). 

Overall, I am unsure whether the contributions here are strong enough to justify a paper publication.

--------- Update after author response ---------

I thank the authors for their response. I have updated my score. I am slightly leaning toward acceptance though I think the paper might benefit from a revision based on some of the points raised by other reviewers, including comments about motivation for correcting the bias as well as the scalability (the proposed method requires storing n^2 additional values which is expensive for large networks). 
review_title: Correcting momentum in Temporal Difference learning

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper proposes a modification to momentum. Extra terms are added to account for the drift in parameters through the gradient updates that contribute to the momentum. The effect of this modification is studied on supervised learning and TD learning and on different representations. The conclusion is that while the original momentum is good enough for supervised learning, this modification matters when there is bootstrapping, especially on representations with high interference.

Overall, the empirical study highlights a direction for improving TD learning and the experiments are diverse and conclusive. Although the proposed approximations to the extra terms show limited improvement, experiments show that if the extra terms can be approximated more accurately, there will be a considerable gain. Computing the extra terms exactly is computationally expensive but it is possible that better approximations will be introduced later on. There are a few weaknesses that I describe below.

1. There is little discussion on why we would want to account for the drift in parameters in momentum. Would this somehow reduce variance or improve the rate of convergence?

2. Candidate step-sizes are too few and some differences could simply be due to the match between the chosen step-size and an algorithm. Consider sweeping over a finer grid.

3. Section 3.1 says "Note that this choice is purely illustrative and that our findings extend to similar simple functions." Is there evidence on other simple functions?

4. A discussion on different optimizers somewhere in the paper or the appendix is needed to see how the proposed updates compare to existing work.

Minor comments:
 
1. Section 1.1, problem formulation and definition of V and Q: In a standard RL setting reward is a function of state and action.

2. \theta and V_\theta are not defined. It is better to make it explicit that the function is parameterized by \theta and outputs V_\theta which estimates V^\pi.

---
Update: I have the other reviews and rebuttal. I am still leaning towards acceptance, although I do agree with the other reviews that there is little motivation for the idea. While the experiments show improvement, a discussion on convergence rates or variance could show why one should try this idea in the first place, and if \mu_* (rather than regular momentum) is indeed an ideal that the algorithm should approximate.
review_title: Interesting direction; limited improvement;

final_score: rating: 6: Marginally above acceptance threshold
review_content: #### Idea
The paper explains and studies an interesting issue with momentum in TD learning, which is its staleness while doing TD updates which is in contrary to the supervised learning. However, the paper could benefit from more investigations.

#### Comments
- In section 2.1: It is said that to compute the oracle update, one has to recompute the entire sum. This may take a while to compute and it would be good if they have had provided a computation-time or wall-time comparison will prior methods.
- In section 2.1: To handle the problem of long summation, "an effective horizon" is used. However, there's no explanations given behind this particular choice. Is it considered as a geometric distribution and thus this formula? Or if it's not, where does this formula come from?
- In section 3.2: When the proposed method is applied to the Atari games, the problem of scalability shows itself. As mentioned by the authors: "Since the architecture required to train ...", the scalability of this approach is under question. 
- In section 3.2: Regarding this paragraph: "Note that we do not use frozen targets ...". The most important question about this work is its scalability, whereas in a prior approaches like frozen targets there is not such an issue while dealing with staleness issue. As in experiments, authors have not used frozen targets, which seems to be misleading when it comes to the experiments and results. It would be useful to see a comparison between these two approaches since they try to solve a similar problem.

#### Minor issues
- In section 3.1: "We task a ..." needs to be changed to "We take a ..."

- In section 2.2: It would be better if you could give a more in depth explanation for eq 11: “Here the term multiplying ∆θ is not exactly the Hessian…”


review_title: Interesting idea but needs more investigation

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper studies the approach to 'correct the bias' of momentum in supervised learning and reinforcement learning (especially, in the temporal-difference algorithm). The proposed approach can maintain a moving average of the 'correct' gradient direction over past objective functions via extra updates. And the experiments show that it does speed up the convergence. (ps: I did not find the comparisons over the loss functions at the stationary points).

As we know TD learning uses a semi/partial/biased gradient with respect to the mean square Bellman error. Thus, the effect of applying momentum to training is an open question. I feel very glad to see such a paper studying it and adding a reasonable modification. The approach averages the TD update over different steps via a modified momentum update. Such an approach reduces the variance, which is usually very large in TD, but also uses additional computational power.

I found the motivation not very convincing for me. The paper seems to claim that a good momentum should carry the information of past objective function and calculate their gradients only with respect to the parameter in the current iterate. However, momentum terms do have the reason to use the gradient wrt previous parameters, as it can speed up the convergence in many situations, e.g. ravines. Another concern is that TD is not typically an online learning problem. The objective function in the early phase is not informative to the update in the later phases as the values of the next states are inaccurate. Therefore, I feel the theoretical reason for 'correcting' the 'bias', which is defined by this paper, is not warranted very well. 

I suggest the paper to rigorously discuss more on why such 'bias' has to be corrected. Alternatively, the proposed method is designed simply for the purpose of reducing the variance of the stochastic gradient for the case of minibatch update. But the paper needs to argue how it is better than using a larger batch or compare itself with other variance reduction approaches.
review_title: the motivation is not very convincing

Meta-review: This paper studies the role of momentum in temporal difference (TD) learning algorithms, and how this can be systematically exploited to accelerate the TD type algorithms. More specifically, the authors point out that the momentum term could be quite biased, and propose a scheme to remedy this issue. However, the reviewers point out the lack of motivation about bias correction; it is unclear why bias correction is crucial to achieve acceleration. 
Decision: Reject