Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary: The authors of this paper make a connection between the TD-error from a single unit of experience and various metrics of improvement for agents trained with prioritized experience replay and Q-learning or soft Q-learning. They show that priorities based on TD-error are indeed sensible, and show that a small adjustment to TD-error-as-priority for soft Q-learning agents is both theoretically sound and can yield improved performance. 

The set-up and motivation of the paper is relatively clear and well-explained. One reason I like the paper is that the process is quite straightforward: 1) Strive to better understand a commonly-used algorithm, 2) Derive theory with reasonably good intuition behind it, 3) show that it empirically holds true on simple environments, and 4) the better understood result also yields modest improvements on a test suite. 

There are a few areas I would consider rewriting or rewording for added clarity.

For instance, the thesis of the paper relies on a sensible definition of "value of experience", and this isn't made concrete until later, though perhaps this is hard to do in the introduction. As a small nit, I think the extra use of the word surprise was at first a bit unclear, especially as it aliases TD-error (unless I missed something). 

I think an extra paragraph about why we should use surprise as the correct metric for prioritization would be helpful. Notably, that when we know it upper bounds the three metrics, we want to continue prioritizing sampling experiences when training our agent, because this will yield faster learning, since we will have larger improvements to our agent. 

However, this dovetails into an additional few questions that could be followed up here: Is there a correct temperature with which we sample experiences from our prioritized replay that is ideal? Should we not be sampling experiences, and simply sorting the experiences by priority and training our agent on experiences in descending order of priority? Why shouldn't we do this? How much worse is this than using uniform sampling? I understand that some of these questions are hard to answer with limited compute, but some mention of this would give the paper more depth.

Additionally, there are a number of small issues in the writing, notably towards the end. A careful read of the paper for proper grammar, making sure the right propositions are used and that there are no missing words in sentences would help the flow and readability of the paper greatly. 

While the overall result is a nice one, I believe the paper has somewhat limited scope. It doesn't fundamentally change how we should approach training our agents with a replay buffer. In fact, I suspect that TD-error was used by the original authors because they knew of a link like this, or had strong suspicions of it. I think what this paper should do is explore or at least pose a gamut of interesting follow-up questions about the role of replay and how best to use it. Is it possible that there is instead a lower bound we can derive; can we learn a sampling/prioritization scheme by gradient descent that somehow does better? Are there prioritizations completely disjoint from TD-error that we should consider using? In addition, while limited resources might make more empirical investigations challenging, it's also worth understanding how other commonly used algorithmic mechanisms in deep RL interact with prioritization, such as stepping environments in batches, or the preprocessing done to observations, or things like reward or advantage clipping. 

I think that if the paper showed more evidence of zooming out and thinking deeply about the core problem, this would be an excellent paper. 
review_title: Dissecting the validity of using TD-error for prioritized experience replay

final_score: rating: 3: Clear rejection
review_content: This paper tries to interpret PER from the lens of replaying experience that has the most "surprise" and shows how it connects to some notions of value such as the expected value of the backup and policy improvement value and evaluation improvement value and argue. The authors also derive a max-ent version of this and show that this can improve performance on some Atari games (though this is not that convincing).

My score for this paper is based on these points:

 Motivation: I do not see the motivation for introducing these metrics and why that explains PER in the first place. Agreed that PER is a reasonable choice, and it can upper bound the EIB and EVB metrics (i have issues with this too, more on this next), it just seems to me that the paper doesn't make any convincing claim for why this helps us understand why PER works. If the focus of the paper is on understanding PER, then the paper does not do a good job of it. If it is to introduce these prioritization based on these metrics -- and the paper focuses entirely on them -- then I then have several concerns next.

- Definition of the value metrics: The cited definition of these metrics requires using the true Q-function or the true value function of the resulting policy. If we end up approximating this using the learned model, what is the guarantee that these metrics are indeed useful? Also theorem 1 should be restated to say that they care about the "empirical" EIB and EVB, that is computed using the learned Q-function, else it doesn't make sense to me. Moreover, if the TD error is a bound (which I think isn't with neural networks as I discuss in the next point) on the empirical EVB, can't I just drastically overestimate Q-values and get a larger empirical EVB value to be super high and prioritize on those examples? Why is that good? Why won't that promote overestimation? 

- Why is the update on the Q-value assumed to be tabular if the experiments are with a deep network on Atari? In a non-tabular setting Theorem 1 does not hold so either that should be rederived for the case of DQN or the experiments should be adjusted to do it on tabular settings.   In any case, now it is not clear to me why the method works with DQN, since the update in this setting isn't equal to $Q(s, a) \leftarrow Q(s, a) + \alpha TD(s, a)$. In general, the solution isn't known with neural networks, so the upper bound story doesn't hold there. With the NTK (Jacot et al.) assumption, I can obtain a somewhat similar update but pre-conditioned with the kernel Gram matrix (see Achiam et al. Towards characterizing divergence in deep Q-learning). However, Theorem 1 doesn't hold anymore now. So, it is unclear why the method works.

- Even if I were to look at the experiments only, the results are not that impressive. The method is generally close to PER, and maybe a little better, but no comparison is made on a more efficient method such as Rainbow, and there are only 9 Atari games, which is too little. So, that is not super convincing yet.

I would suggest the authors make some of the changes above.
review_title: Not convinced about motivation, method or results

final_score: rating: 5: Marginally below acceptance threshold
review_content: This work aimed to understand the prioritized experience replay, a widely used technique to improve learning efficiently for RL agents. The authors proposed three different value metrics to quantify the experience, and showed that they are upper bounded by the TD error (up to a constant). The extension to soft Q-learning was also presented. Finally, the authors showed in experiments that derived upper bounds hold in Maze and CartPole. They also demonstrated that a new variant based on the upper bound achieved better performance on a subset of Atari games.

The authors tried to achieve a deep understanding of the prioritized experience replay, which I believe to be an important task. However, after reading through the paper, I am afraid that the question why prioritized experience replay works so well in practice is not well addressed. The authors provided the three metrics, and provided their upper bounds. Unfortunately, they are not sufficient to help the understanding, as the upper bound derived is just the TD error used in the prioritized experience replay. I also do not see enough depth for these theoretical results, and the presentation could be improved as well. The experiments indeed showed some practical benefits, but descriptions are confusing sometimes. My detailed comments and questions are as follows.

1. When defining EVB, PIV, EIV in Eq. (3)- Eq. (5), "s_k" is used. However, in the derivation of Theorem 3.1, why is "s" used? They should be the same if both are from "e_k".
2. The introduction of function approximators in the last paragraph in Section 2 is confusing: How are they used in the following sections? Also, why does the assumption "...as if the parameterized Q-function converges to its target value" hold?
3. For Theorem 3.1, it looks to me that a tighter upper bound according to the derivations should be \alpha |TD|. Why did you omit \alpha?
4. In the derivation for Eq. (7), the authors claimed that "the third line is because the increase in Q-function resulted from greedy
policy improvement will not exceeds the surprise (times the learning step-size)". Could you elaborate more on why this is the case?
5. For VER in Section 5.3, which upper bound does it use? I guess it may come from Theorem 4.1, but need more clarification. Also, what are the exact differences between VER and PER?
review_title: Review

final_score: rating: 4: Ok but not good enough - rejection
review_content: Summary: the idea of prioritized experience replay is revisited, but from a new perspective with new theoretical results. Here, the authors propose the expected value of backup (EVB) as a metric to assess the quality of a sample and its potential improvement on the policy and on the value function. The authors decompose this metric into the benefit attributed to the policy and benefit to the value function. The authors have two theorems. The first theorem shows that the surprise (aka the temporal difference error) is an upper bound of the EVB in the Q-learning setting. The second theorem shows that the surprise, multiplied by a constant that depends on the policy, is an upper bound to EVB in the soft RL setting. The authors demonstrate that the proposed tighter bound on the EVB *could* yield improvements in the soft RL setting. 

Pros of this work:
- the work tries to tackle an important and still not fully answered question, which is why prioritized replay works well in the DQN setting but not in the soft RL settings, making very nice connections to the existing empirical literature on the topic, and a suggestion of how to improve PER
- the paper is very clearly written and the motivation of addressing PER from a rigorous perspective is clear.
- overall, a rigorous study of the "quality" of samples and experience seems like a very promising direction if the goal is to develop more intelligent agents that can make better use of the information available to them
- the authors try to demonstrate why the approach leads to tighter bounds than standard PER with some visualization (although I point out some issues below)

Cons:
- lack of motivation regarding the choice of EVB
- more thorough experimentation
- lack of evidence suggesting a tight upper bound (e.g. modest improvement in soft RL, maze example does not suggest a tight bound in Q-learning)

Details:
- lack of motivation regarding the choice of EVB: while the EVB seems like an intuitive starting point for investigation, its motivation and a-priori connection to prioritized replay is not fully clear. one of the problems with EVB is that it seems to be a largely myopic measure of quality that is linked to only the current sample, e.g. (s,a,r,s'), while ignoring the effect of the sample on further backups in the rollout. Recent work on the topic [1] (PSER) suggest that a myopic approach can be significantly improved by up-weighting earlier transitions that lead to good transitions in the future. This would seem to suggest that a non-myopic metric could lead to more significant improvements than working with a myopic setting which could be fundamentally flawed. While I do agree that EVB is a good starting point for analysis, I am not convinced the results are fully conclusive, particularly given the need for stronger motivation on EVB and more conclusive experiments (see below) . I would encourage the authors to think about how to better motivate the use of EVB in the papers introduction more clearly if existing literature suggests so (I am somewhat aware of [2], although the authors there do highlight the shortcomings of EVB). Could sequential replay be the result of using an underlying metric that is less myopic than EVB, which seems to shows better promise over PER? If not, why is EVB truly the only right approach for analyzing PER?
- more thorough experimentation: while I concur that the current paper addresses an important theoretical question, and while the result appears trivial to implement (not more difficult than PER), the bound should also be justified experimentally if it is to have significant value in practice. I think one key detail that is missing and could greatly benefit the paper is a more careful analysis and visualization of what the modified tighter bound is actually doing in the soft-Q setting. For example, how does the ranking of experience change when using the "tighter" bound? How often does this bound lead to a revision or re-evaluation of experience v.s. PER? Is there a fundamental reason why PER could not be as effective for soft RL in general that cannot be explained by better myopic estimates of the value of each transition? 
- lack of evidence suggesting a tight upper bound - Q: while the authors argue at several points in the paper that the |TD| could be a tight upper bound, this bound is only attained in some special cases. However, this does not really mean that the upper bound is tight for Q-learning, since there could be other upper bounds based on |TD| that incorporate additional value or policy information that could be tighter (same also applies for soft RL). The Figure 1 also seems to suggest that the values are scattered quite randomly and do not attain the upper bound as claimed for Q-learning. This does not suggest that |TD| is tight in any way. Can a gap be proved that effectively provides a lower bound on EVB? 
- lack of empirical evidence supporting the tighter bounds - soft RL: The experiments on Atari also suggest that the improvements of VER are quite mild, only improving on PER with statistical confidence on two of the experiments (interestingly, these two experiments also show mild improvement by PSER, whereas PSER shows considerable improvements on other games evaluated here).  This seems to be at odds with the claims that VER is a significant improvement of PER in soft RL. In the games where VER does not improve upon PER significantly, I would encourage the authors to comment on why the results are so similar to PER. I think the current benchmark problems are fairly sufficient and complex, and would not require more evaluation, unless the authors believe this would lead to a different conclusion or if the games selected are not representative of where VER can be beneficial. 

Other points:
- while I agree with the authors that when the learning rate is held constant, |TD| is an "upper bound" to EVB in the Q-learning case. However, in practice we often use state-dependent learning rates that can be annealed over time with visitation counts, which can often yield improvements (as long as the usual stochastic convergence conditions are satisfied, of course). In this case, wouldn't the learning rate play a role in the bound?

I think the work is very interesting and addresses a central issue, and I hope that the above comments can be useful to improve the paper. Overall, I think it is necessary to think more carefully about the connection between PER and quantifying the value of an experience (e.g. why EVB? how to reconcile moderate empirical evidence of the new bounds?). I am looking forward to the authors' response on these issues above.

References:
[1] Brittain, Marc, et al. "Prioritized Sequence Experience Replay." arXiv preprint arXiv:1905.12726 (2019).
[2] Mattar, Marcelo G., and Nathaniel D. Daw. "Prioritized memory access explains planning and hippocampal replay." Nature neuroscience 21.11 (2018): 1609-1617.
review_title: Very interesting work with great potential, but the choice of EVB needs clearer motivation, and experimental is inconclusive

Meta-review: This paper is certainly on the way to be a solid contribution: it's an interesting research question, and we need more understanding papers (rather than yet another algorithmic trick paper).

The reviewers thought the paper was not yet ready. The reviewers suggested: (1) more motivation of why the proposed metrics were of interest, (2) clearer discussion and evidence of how the analysis better articulates the performance of PER, (3) missing empirical details like methodology for setting hyper-parameters, why these 9 Atari games, undefined errorbars, unspecified number of runs, and (4) conclusions not supported by evidence in Atari: with missing experiment details, likely too few runs, and overlapping errorbars in most games few scientific conclusions can be drawn.

The work might be strengthen by developing the first part of the paper (and focussing on the reviewer's suggestions) and deemphasizing the novel algorithmic contribution part.
Decision: Reject