Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper proposes a method to improve the data selection strategy of experience replay, which is one of the standard techniques in deep reinforcement learning. As opposed to the previous method (PER), the authors provide a theoretical study to design an optimal prioritization weight by minimizing the policy regret. Some theoretical parts are partially based on the previous study (DisCor). The major contribution is that the prioritization weight is decomposed into four components. The most difficult part is to estimate $|Q_k – Q^*|$. The authors propose two practical algorithms. ReMERN estimates the upper bound of $|Q_k – Q^*| while ReMERT exploits the distance to the terminal state. The proposed method is evaluated on several benchmark tasks, including MuJoCo, MetaWorld, and Atari, and the experimental results show the proposed methods improve sample efficiency in many cases.
main_review: Major comments
1. In Section 3.4.1, the authors mention that the terminal state consists of the reward only. It is correct, but some tasks do not have a terminal state. Is it possible to apply ReMERT to the non-episodic or continuing task? In fact, the performance of the proposed method is almost the same as DisCor in the HalfCheetah task. 

2. I do not fully understand the TCE algorithm. For example, how do you compute $\mathbb{E}[|Q_{k-1} - \mathcal{B}^* Q_{k-2}|]$ in practice? In the simplified version (11), do you compute the expectation? In addition, it would be better to explain the difference between c of Eq.(8) and c of Eq.(9). In (8), $c$ is given by $\max_{s, a} (Q^* (s, a^*) – Q^*(s, a))$, but $c$ of Eq.(9) is the hyperparameter. 

3. The authors use Likelihood-Free Importance Weights (LFIW) to estimate the density ratio $d^{\pi_k}(s, a)/\mu(s, a)$. However, I do not fully understand LFIW can estimate it in practice. LFIW assumes that the slow replay buffer contains samples from $\mu(s, a)$ while the fast replay buffer contains samples from $d^{\pi_k}$. Does the assumption hold in practice?  

Minor comment

4. In Appendix C, the authors show the pseudo-codes of ReMERN and ReMERT that are integrated with DQN. Would you show the pseudo-codes for the continuous version? In particular, SAC maintains two state-action value functions to avoid the overestimation problem. Did you use the same weight for the loss functions? It would be better to show the update rules to clarify the algorithm. 

limitations_and_societal_impact: In Section 5, the authors claimed that ReMERN is robust to the randomness of environments. However, Figure 6 shows that ReMERT is more robust than ReMERN in Walker2d and Ant with noise. So, it is not clear why the two proposed algorithms are suitable for different kinds of MDP. It would be better to discuss this point in more detail.
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: Regret
This paper explores a theoretical understanding of a current very prevalent method of training deep RL agents: experience replay. It brings an optimization perspective and formulate return maximization using an importance weighting to samples in buffer. The most important contribution of this paper is coming with a solution of weight that is almost analytical, which explains quite a few interesting myth/questions regarding experience replay. (Detailed below). 

main_review: 
Figure 1: the x axis is iteration? What’s the explanation that PER and Discor performing worse than uniform? Any influence from experiment parameters? How many runs are here? Step-size? Number of samples? What are the features? Initialization? What is the particularity of this problem that makes the two methods slower? It is foreseeable that these setup can influence the performance on such a simple example and such a short time of training. I see you have some explanations from line 99, but still it’s not very convincing. Looks like more like an argument than a solid explanation. 

This doesn’t seem a good example (at least it is not well presented: not convincing; no maths or understanding why the two methods are slower than uniform sampling). 

Equation 1: this formulation is interesting. Just the dependence of the policy isn’t explicitly dependent on w_k, which is flawed. Perhaps you should define \pi_k from Q_k. 

I assume all w_k>=0? Then shouldn’t it be constrained? It could also be in the form of exp^w. In the paper, w is directly learn for each sample. In practice, there are millions to billions of samples,  generalization between samples is important. Thus considering parameterizing w_k will be interesting. 

That being said, the experiments missed a study of the weights. Are they negative or positive? Any insights into the signs of w on the performance and behavior of the algorithm?

It looks like an adaptive importance sampling strategy, especially eq 2. In Th 1. Has an importance sampling ratio. I think this is not accidental. I like the “on”-policiness, it is a very interesting understanding of the off-policy samples. The downside is that the learning of w will have a high variance. 

Note if Q_k converges to Q at a linear rate (for value iteration, a gamma rate, seems in your eq. 7 it is something like this), then the weights will be exponentially increasing. This will the sampling focus on those samples that will drive Q_k close to Q*. This will be very interesting to show for some generalization case to illustrate this perspective. 

The hindsight Bellman Error is interesting too. That it explains hindsight experience replay is most interesting I think. 

Action selection perspective: If a_k is selected with a high probability, then the weight for s, a_k is small. Sampling this state action pair will be small in experience replay. So the weighting will prefer those rarely taken actions, correct? If this is correct, I think the last item of your understanding from Th 1, “a_k is less likely to be selected by the policy“, should be stated more precise like, “samples of rarely taken actions will be replayed more”. That “a_k is less likely to be selected by the policy“ is not necessarily true: it may be influenced by features and many other things. 

Could you double check the “2-\pi_k” and why it’s not “1-\pi_k”?

By “informal” you mean a relaxation?

Experiments were performed on Mujoco continuous action tasks, and outperforms Discor, and SAC on four tasks (with a closer gap in Walker2d), which is not bad. 

Also on Meta-World benchmark (8 tasks were selected). The results are more promising than Mujoco, with larger winning gaps. 

The valuation is also done for discrete-action tasks on Atari games. On 5 selected games the algorithm outperforms DQN by a large margin. However, the baseline DQN is weak; you probably needs to include more baselines especially those experience replay,  some model-based methods as well as exploration method (since your weighting relates to action selection perspective). 

related: experience replay and Atari baselines

Recurrent Experience Replay in Distributed Reinforcement Learning 
https://openreview.net/forum?id=r1lyTjAqYX

Distributional Reinforcement Learning for Efficient Exploration
https://arxiv.org/abs/1905.06125














limitations_and_societal_impact: n/a
review_title: null

final_score: rating: 3: Clear rejection
review_content: summary: This paper attempts to provide a theoretical approach to the prioritization of the experience reply to minimize regret. 
The main result of the paper shows that to minimize the regret, one should minimize a weighted mean squared Bellman error, where the weights $\omega(s, a)$ depend on four terms

1. the magnitude of the Bellman error for the state-action pair $s,a$
2. the degree of "policiness" of the sample $s, a$ (seen as the probability of sampling from the experience replay v.s. the discounted state distribution)
3. the magnitude of the error $|Q_k - Q^*|(s, a)$, which tells us how "wrong" is $Q_k(s, a)$
4. the probability of sampling $a$ given $s$ according to the current policy.

The authors develop some heuristics to estimate these four components, and to weigh the replay memory accordingly.


main_review: The idea to find a principled way to prioritize the replay buffer is nice. 
Theorem 1 (if correct) is an important contribution, as it allows to use the experience replay in a smarter way.

I have, however, a few fundamental concerns. The first one is about why the authors focus on the regret. In their setup, the maximization of the return should be enough, and I find the terminology "regret", confusing, as it is used usually in a different context.
Another concern is that the paper looks like more a draft stage rather than a finished work. There are a few imprecisions, as well as many details missing. I list them later, but to give an idea, many mathematical symbols are not defined, and some of the reasonings made do not make perfect sense to me. 
My last concern regards the amount of approximations introduced. It is not easy (at least for me) to understand the logic behind the approximations. Unfortunately, the language used in the paper does not help to clarify them.



The authors evaluate their methods (ReMERN and ReMERT) on different settings. I think that the empirical section is well constructed (even though I would advocate the comparison with the classic Prioritized Experience Replay); however, I do not find the results to be particularly significant, especially when taking in account that the method proposed is strongly empirical (I usually tend to weight less the importance of the experimental section when the theoretical section is stronger).


__Questions__

1. In lines $\texttt{141-144}$ you state that "an efficient update requires $\omega_k$ to be on-policy". I do not understand this sentence. If I understand Theorem~1 correctly, when $d^{\pi, k}(s, a)$ is low and $\mu(s, a)$ is high, then $\omega_k(s, a)$ will be low, while when $d^{\pi, k}(s, a)$ is high and $\mu(s, a)$ is low, $\omega_k(s, a)$ will be high. How is this related to on-policy/off-policy? It seems that in the two cases that I mention, clearly both off-policy, we have two different asymptotic $\omega_k(s, a)$.

2. I do not understand Equation 4. I do not know what is a slow replay buffer and a fast one, and I do not know the meaning of $f^*$ and $f'$

3. How do you train $\Delta_k$? From the formula seems that you need to store all the previous policies $\pi_k$ (small detail: you usually do not have $P^{k-1}$ or $\mathcal{B}^*$, I guess that you are fitting a _sample estimate_).

4. Is Equation~  an upperbound, a lower bound, or ... ? It is hard for me to relate it to Equations 2 and 3. (As I discuss later, I am convinced that using $\propto$ is wrong in Eq. 7).

5. $\texttt{247}$ what does it mean "the term $h^\pi_\tau(s, a)$ is relatively fixed"? Means that it has low variance? And what is the _temporal ordering_ of the estates (or a _stable temporary order of states_)?


__"Minor" Questions__

1. I fail to understand the need of minimizing $\eta(\pi*) - \eta(\pi_k)$, since it is equivalent to $\max \eta(\pi_k)$ (up to an additive constant factor).

2. I fail to understand what $|Q_k - Q^*|(s, a)$ means. Is it a shorthand for $|Q_k(s, a) - Q^*(s, a)|$?

3. The policy is defined as $\pi(s) = \mathrm{arg}\max_a Q_k(s, a)$ (line $\texttt{126}$). What is $\pi_k(a|s)$ in Theorem~1? (remember, the paper should be self contained, I should not go to investigate that in the Appendix.)

4. What are $f'$ and $f^*$ in Equation 4?

5. What does it mean in Theorem 2 "Ignoring some terms", "holds with high probability"? I know you are referring to the Appendix, but the paper should be self contained. Including a "Theorem" in such unclear way, is completely useless. 


__Side notes__


1. You define $\eta(\pi)  = \mathbb{E}\left[\sum_{t>0}\gamma^t r(s_t, a_t)\right]$  on line $\texttt{62}$, but then you define it as $\eta(\pi) = \mathbb{E}_{d^\pi(s, a)}[r(s,a)]$., where $d^\pi$ is the _discounted stationary state distribution_. 
The two definitions are not equivalent as, 

$$ (1-\gamma)\mathbb{E}\left[\sum_{t>0}\gamma^t r(s_t, a_t)\right] = \mathbb{E}_{d^\pi(s, a)}[r(s,a)]$$

2. Eq two should be modified in the following way:

$$\text{s.t.} \quad Q_k  = \mathrm{arg}\min_Q E_\mu \left[\omega_k(s, a)  \cdot (Q-\mathcal{B}^*Q_{k-1})(s, a)\right].$$

3. Equation 7 is an approximation of Equation 3; you should not use the same symbol both for the "correct" value and for its approximation.

4. I think at line $\texttt{233}$ $Q$ should be substituted with $Q_{k-1}$.

5. In the Appendix you define $d^\pi$. I find the definition wrong, or at least unclear. Why don't you use the definition from Sutton et al., NIPS 1999? 

6. $\texttt{192}$, The first term is the _projection error_. 

7. Line $\texttt{233}$. How do you update $Q_k = (1-\alpha)Q_{k-1} + \alpha Q_{k-1}$? Is $Q$ tabular? What it is done usually, it is to update the parameters of $Q_k$ with a soft-update rule. 

8. Line $\texttt{236}$. How do you ensure that a small change in the Q-function results in a small change in the policy? 


UPDATE
=======

I thank the authors for their answers to my questions. 
Unfortunately, after carefully considering the author's response and other reviewer's responses, I am willing to keep my score as it is. 

The paper analyzes an interesting problem and proposes a theoretical approach to minimize the regret in weighting the samples coming from the replay memory. The algorithmic solution, however, relies heavily on approximations (like the result in Equation 7, and the need to approximate the Bellman error with a neural network) and heuristics, as I also remarked in my review. 
I usually expect strong empirical evidence supporting empirical works. However, in my perspective, the results are not so strong. 
In Figure 4, the learning curve is clearly unstable both in push and sweep. In stick-pull, hammer, and peg-insert-side, the variance is considerably high, making me doubtful of the statistical significance of the results. The same issue of high variance seems to be present also in most of the tasks in Figure 3 and Table 1. 

As I remarked in the review, I also detected several imprecisions (mathematical notation and language), which make me think that the paper should be polished. 

Side remark. The policy is greedy w.r.t. the Q-function, meaning that small changes in the Q-function many still cause large changes in the policy, i.e. consider $Q(s_1, a_1) = 100$ and $Q(s_1, a_2) = 99.99$, which leads a policy $\pi(a_1| s_1) = 1; \pi(a_2|s_1) = 0$, but after an update, we suppose that $Q(s_1, a_1) =100$ and $Q(s_1, a_2) = 100.1$. This will lead the policy to have a big "jump", since now the greedy policy will be $\pi(a_1| s_1) = 0; \pi(a_2|s_1) = 1$.



limitations_and_societal_impact: Although the author claimed that they discussed the limitations of their work, I do not find the discussion in the paper. 
I suggest that the discussion should be made more clear in the Conclusion.

There is no societal impact to be discussed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes an approach to prioritizing experience replay, specifically it advocates for prioritizing experiences that, when sampled and used for Bellman error minimization, result in lower regret (or really higher reward objective).


main_review: The approach taken here to prioritize experience is certainly interesting, as it actually connects the prioritization problem to the reward maximization problem, which is the ultimate goal of RL. As such, the prioritization approach could be thought of as objective-aware. This stands in contrast to previous work in the space that defines a good prioritization scheme as one that, for example, reduces the TD error rapidly (PER).

The paper nicely demonstrates that heuristics, such as the one used by PER, may not necessarily manifest themselves into higher rewards, and so it nicely motivates why we need to reformulate the prioritization problem.

The solution to the reformulated problem highlights key factors when determining which sample to use:
1- high hindsight Bellman error
2- low importance sampling (between behavior and target policies)
3- accuracy of the resultant Q*
4- focusing on actions behind which the policy assigns more probability.

Thoughts regarding the proof of Theorem 1: assumption 1 sounds highly arbitrary and self-serving. Is it correct to say that the theory won't apply to MDPs in which a transition to a same state is likely? It seems like the assumption is only used to approximate the gradient in the follow up derivation. Is it not possible to remove the assumption and bound the error instead?

I didn't get why we used Jensen's inequality in (14). Why can't we directly optimize for 12? In (16), why can't a p_k be strictly zero? In step 4, second equality, should a s be a'? In general, i think the proof needs to get polished and assumption better justified before this result is ready for publication.

The temporal property of Q error seems kind of hacky. a) it depends on the current policy, so it needs to be re-estimated with every change, and b) it is not obvious how to think about it in non-episodic domains and/or domains with frequent self-transitioning states. Can you clarify?

Can you also include the computation time required for REMERN and REMERT? In particular, i am interested to know its comparison with DQN and PER. Is the computation of w the bottleneck of the algorithm, or that it does not affect the overall computation time significantly. Also, I'd move the PER result from the Appendix to the main text, as PER would be the most important baseline to assess the competency of the proposed algorithms.

In general, this paper is identifying a weakness of the previous work pertaining to experience prioritization, which is really nice, but i have my own doubts regarding the proposed way of computing the weight. Overall, I lean towards acceptance at this point.
limitations_and_societal_impact: Yes
review_title: null

Meta-review: The paper proposes a new method for prioritized experience replay by casting the problem of finding optimal prioritization weights as an optimization problem and then approximating its solution. The review team has significant divergence in their opinions about the paper. Multiple reviewers find the optimization-based formulation of prioritized experience replay refreshing and insightful, and are willing to accept the paper based on its novel perspective. However, as reviewers okGN and hPUt have pointed out, the theoretical derivation of the paper has the caveat that the original objective cannot be directly solved, and a fair number of relaxations and approximations need to be employed. No discussion about how those approximations affect the algorithm's ability to optimize the original objective (e.g., can you somehow quantify the approximations involved? consider questions like: do you get an additive approximation, a multiplicative one, and if so, how large are the approximation errors). While we fully acknowledge the authors' argument that it may be simply difficult to optimize the original objective and the approximations may be reasonable and necessary, this caveat still shows that the rather heuristic nature of the method (*), and in light of this, reviewer hPUt argues that the paper should be evaluated mainly on its empirical results which are not sufficiently strong (curves overlap, or the error bars are too large to tell). Given all these considerations, the AC's recommendation still leans towards acceptance, as the lack of a comprehensive theory is not a fatal issue and the rest of the paper is reasonably executed. 

(*) Along this line, the AC strongly urges the authors not to call Theorem 1 a "theorem"; the statement is simply vacuous if read as a theorem, and needs to be called something less formal. The main approximation steps also need to be included for the main text to be self-contained. 
Decision: Accept (Poster)