Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 1: strong reject
review_content: summary_of_the_paper: This paper proposes to sample experience from a replay buffer by keeping a memory of trajectories, and picking sequences of B consecutive samples as minibatches. The sequence is the one whose last state features the largest TD error. Each sequence can be mixed with samples drawn uniformly from the replay buffer.
strength_and_weaknesses: ### Strengths 

The paper tries to capture the idea that rewards should be propagated backwards, starting from states which have the largest TD error.

### Weaknesses 

The idea that rewards should be propagated backwards in time is the key idea behind asynchronous DP and prioritized sweeping (Moore & Atkeson, 1993) so it is nothing new.  
Additionally, the authors miss the fact that Deep RL is about using NNs to solve the Bellman equation, which in turn is a series of empirical risk minimization (approximate dynamic programming) problems over a replay buffer. And ERM suffers from arbitrary sampling schemes.   
Overall, there are no strong arguments for the presented method (neither formal nor empirical).

### Algorithmic contribution

The contribution is minor and not really supported by anything else than claims and vague intuitions.  
It is not connected to the relevant literature on ER. Especially, there could be connections to well grounded approaches like (Gruslys et al, 2018) or (Zhang & Sutton, 2017).   
Gruslys, A., Dabney, W., Azar, M. G., Piot, B., Bellemare, M., and Munos, R. The reactor: A fast and sample-efficient actor-critic agent for reinforcement learning. In International Conference on Learning Representations, 2018.  
Zhang, S. and Sutton, R. S. A deeper look at experience replay. In NeurIPS 2017 Deep Reinforcement Learning Symposium, 2017.

The algorithm itself is unclear and not really discussed.  
In particular, the way the "importances" are computed is never mentioned. Do you cycle through all the replay buffer at every gradient step to assess these priorities? That sounds very costly.  
How do you guarantee all states will eventually be updated?  
How does function approximation come into play?  
What is the exploration strategy?  

### Theoretical soundness

Everything relies on the claim made in Kowshik et al. (2021a and b), which are not recalled. So the soundness of the algorithm is not really backed by prior work.  
Besides this, training a neural network remains an empirical risk minimization process, which requires iid samples. The distribution of samples itself can be altered via importance sampling. But making the sampling distribution deterministic is a strange (very doubtable) practice here. Mixing with a uniform distribution might be relevant but is not defended by any sort of analysis.   
Additionally, besides the claims that theoretical results are in previous papers, there is no new formal result in this paper.

All the arguments are rather vague and seemingly intuitive.  

Lots of repetition about the bias introduced by Markovian data. But Markovian data is never defined. And why it causes bias is never explained (not even intuitively).  

### Literature coverage

I'd like to encourage the authors to escape their comfort zone. This work builds upon the contributions by Kowshik et al. (2021a and b) and to some extent Agarwal et al. (2021) which is essentially the same authors on very close topics. Additionally, OER (Optimistic ER) is presented by the authors as introduced in the PER paper, where it is nowhere to be found (and the search in a web browser about optimistic ER returns no relevant link).

This whole work is based on RER, which is introduced in a preprint from 2019 which never received peer-reviewing. RER relies on keeping trajectories in memory and replaying them backwards for updates. I will add, to the best of my ability to check facts, RER was never validated, even experimentally. While keeping the structure of trajectories within the replay buffer might be relevant, there are works out there which go way beyond that.

I fail to understand how one can introduce a comparison with HER. Despite the name, HER is not a non-uniform sampling method for experience replay. It is an intrinsic motivation method for designing goal-based policies. So the point of the comparison evades me.

Most of the abundant literature on ER is missing in this paper. To the best of my knowledge, the most recent paper on the topic is by Lahire et al. (2022), which contains a quite extensive literature survey about other recent work in ER. This same paper establishes a link between selecting specific samples in a replay buffer for SGD-based Bellman updates, and importance sampling to reduce the variance of SGD's gradient estimate. I encourage the authors to check this work and the corresponding body of literature.  
Lahire, T., Geist, M., & Rachelson, E. (2022). Large Batch Experience Replay. International Conference on Machine Learning.

### Empirical evaluation

The toy example is very incomplete. Is there a function approximator in the form of a NN? If yes, what is the NN's input? The state index? Is there a learning rate decrease schedule?  
I think this toy example is very biased and the only thing it actually shows (in a vague fashion) is that *maybe*, in *some* function approximation cases, asynchronous DP updates may possibly lead to an optimal value function regardless of the samples distribution for SGD updates.

The "broad category of environments" claimed is actually a set of 10 environments, including some very simple ones (cartpole) and only 2 ALE environments (Pong and Enduro, why only these two?). This seems very light. Why this choice?  
The top-k seeds is a very questionable choice of performance metric. Please avoid doing this. It uselessly biases results. We don't need RL agents that perform well once in a while.  
I strongly doubt some claims, such as the speedup. With only a partially defined algorithm, how can I evaluate this? What is the baseline for comparison? what are the actual figures, rather than just reporting percentages of improvement?

Overall the experimental validation is unconvincing.

### Paper organization.

Very bad organization and writing overall: 
- Constant forward references, to section 4 from section 2, to section 5 from table 1 (which should actually be in section 5, not at the beginning of the paper).
- Lots of references to the appendix, for important results, backing claims from the main text (and nothing in the main text about the same claims).
- Excessive use of superlatives for unsupported claims (minimal tuning, important metric...).
- Blur, unsupported statements ("a broad category of environments" with no details, "a few Atari environments",... "many other classes of environments", "a total of 1e6 data points usually").
- Lots of typos (e.g. "important" instead of "importance", "staring" instead of "starting")
- Misinterpretation of the assignment operator "$\leftarrow$".
- Poor English.
- Repetitions about what is in the appendix and too little discussion in the main text.
clarity,_quality,_novelty_and_reproducibility: Clarity, quality: bad. Please see "paper organization" above.

Novelty: minor. Prioritizing on TD errors has been extensively studied. Including recent samples too. The novelty would be in the combination of the two, but the one proposed is not sound.

Reproducibility: the description of the benchmarks is only partial but the code is provided (I skimmed through it quickly but did not check in detail nor run it).
summary_of_the_review: This paper proposes a sampling scheme for emphasizing states with large TD error and their B predecessors along trajectories, when computing gradients for SGD updates in approximate value iteration algorithms. The algorithm's presentation is very incomplete, the ideas are poorly motivated, the empirical evaluation does not permit drawing conclusions and the paper's organization can be much improved. I recommend rejection.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies experience replay in reinforcement learning, which is helpful in handling spurious correlations caused by the Markovian data collection process. Prior methods such as uniform and prioritized experience replay can introduce bias and suffer from suboptimal convergence rates. Motivated by recent theoretical advances in experience replay, such as reverse experience replay (RER) (which provably removes bias in the linear setting but is still suboptimal in neural network function approximation), the authors propose introspective experience replay (IER). The IER approach combines ideas from RER, which samples data points in the reverse order, and optimistic experience replay, which samples data greedily according to their corresponding TD error. In summary, the IER approach picks consecutive batches of data before certain "surprising" pivot points, with the highest TD errors. The authors conduct an empirical evaluation of IER on several environments such as classic control, robotics, and Atari, and show that IER outperforms other experience replay methods in most cases. 
strength_and_weaknesses: **Strengths:**
- This paper is well-motivated and a solid contribution to reinforcement learning. The proposed approach is simple and intuitive, and is inspired by recent theoretical groundings of reverse experience replay and combines it with optimistic experience replay.
-  The authors explain the majority of their design choices in detail, compare them with alternative methods, and provide many insights. The example in Section 3.2 and discussion in Section 4 are particularly nice to get a good understanding of different methods. The authors also discuss forward vs. reverse experience replay by noting the prior work of Kowshik et al. 2021 and providing an empirical comparison of the two options.
- The authors report that empirically their approach requires minimal hyperparameter tuning.
- The paper is very well-written.

**Weaknesses:**

I did not find any major weaknesses that would justify rejection. Some details are unclear:
- While the reverse sampling approach is well-justified, the use of TD error for prioritization is not very clear. Why is TD error a good proxy for the surprise pivot? Although Figure 3 shows correlations to rewards, it would be helpful if the authors elaborate more on this. Is prioritizing high TD helpful in breaking the correlations caused by Markovian data collection, and if yes, how? Is it possible that prioritizing high TD samples actually biases the approach to more stochastic transitions, which might not necessarily be a good idea? 
- Does the results in Section 3.2 change if the environment is stochastic? 

clarity,_quality,_novelty_and_reproducibility: The paper is written clearly and the quality is good. Algorithmic novelty is limited but many insights on experience replay are provided. Code is included in the supplementary material.
summary_of_the_review: I found this paper to be a solid contribution to RL. The paper not only introduces a new experience replay algorithm that outperforms prior methods but also provides insight into the limitations of prior methods.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes an experience replay method for reinforcement learning. The paper argued that previous methods are sub-optimal and have bias. The proposed method picks some pivot points at first. Then it selects transitions before these pivot points. 

The intuition of the paper is that an agent should select transitions that associate with outcomes. 

In the experiments, the proposed method compares UER, PER, HER with multiple environments. The paper uses the top-k seeds moving average return as the evaluation metric and 3 seeds. The paper also compares IER forward and IER reverse. The results show that the proposed method works better for the most of the dataset.

strength_and_weaknesses: > Strength

The problem is important and very interesting. 

Considering the pivot points and selecting transitions before outcomes seems to be new for experience replay.

The experiments show the proposed method works better than others.

>Weaknesses

The paper argues that the previous methods have bias. Does the proposed have bias too? The paper needs to provide an analysis about it.  

The surprised pivots are one of key components of the method. How to pick pivots seems to be not new. The paper uses TD error for selecting pivots. What is the difference between the proposed method and PER about the idea?

Related works are not enough. For example, for the experience replay, the paper does not mention CER (Competitive experience replay), CHER (DHER: Hindsight experience replay for dynamic goals), DHER (Curriculum-guided hindsight experience replay), and so on. 

For the important function, it uses the magnitude of the TD error, what does magnitude mean? What exactly is the important function? It is not clear.

It is better to improve the writing of the paper. For example, in Figure 1, the paper uses colors but does not provide explanation. 

In Table 2, why does not  IER work better in Pong?

In Table 2 and Table 3, why do IER and Reverse have different results?

The baselines used in the paper are a little confusing. What is OER? Why does it not appear in Table 2? It is better to provide more details. 

Why does not the paper provide learning curves for comparing different methods? Using curves is common to present results. 

clarity,_quality,_novelty_and_reproducibility: The quality and clarity are good. The paper also proposes a new method.
summary_of_the_review: The paper argues the previous methods have bias. However, the paper does not provide enough support to show their method does not have bias. The proposed method uses TD for selecting pivots. It might be similar to previous works. The paper also needs to provide more details about related works and techniques.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies experience replay mechanisms in a deep reinforcement learning (DRL) setting. Notably, it proposes a modification to the existing reverse experience replay method. The paper claims that purely prioritizing experiences according to TD errors and a naive (uniform) ER method may suffer from sub-optimal convergence and potentially large bias, respectively. Then the paper proposes the following method. First, the algorithm picks up k “pivot points” from a large buffer according to the TD error-based sampling distribution. Second, get the corresponding k batches of data where each batch ends with a pivot point sampled in the previous step. Then those mini-batches are used to update the training parameters. Extensive experiments on simple discrete domains, mujoco domains, and Atari games are conducted to show the effectiveness of the algorithms. 

strength_and_weaknesses: Strength: 

1. The topic of ER mechanism is interesting and important; 
2. The paper presents its mean idea very clear;
3. The proposed sampling method seems to be novel;
4. The paper conduct extensive experiments on a variety of domains. 

Weaknesses: 

---------------------------
Algorithm design. The presented algorithm 1 has to collect data episode by episode. This turns the algorithm into an offline algorithm, restricting its utility. But it seems the sampling method can be done in an online manner, why not propose that? This is important because 1) an online method is a closer competitor to PER which runs online (update parameters at each environment time step) and 2) it is clearer how the two algorithms are compared. 

Figure 3 is not persuasive. The TD errors can change as the parameters get updated. I do not see a clear correlation between reward magnitude and TD error magnitude. Also, if this correlation is true and is beneficial, shouldn't PER perform very well in the sparse reward setting? 

---------------------------
Concerns about experiments. The empirical results are extensive but not persuasive. 

1. Many figures (Fig 4-6) in the experiments section include learning curves with very large variances/standard errors, where one cannot really identify the proposed method to be better than others. Furthermore, it is better to study the hyper-parameter sensitivity of the proposed algorithm. The algorithm seems to have a large reliance on the size of the ER buffer. 

2. Missing at least two intuitive baselines to make the proposed method more persuasive:
1). Uniformly sample the pivot points, and the rest is the same as the proposed method: this can verify the usefulness of the claimed "reverse replay."
2). Prioritized sampling of the pivot points and then uniform sampling of the rest of datapoints in each batch: this can further validate the reverse sampling is important

3. One critical question about the experiments. The PER/UER can update parameters at each time step, while RER++ needs to wait until the end of an episode. How do you conduct the comparison? Do you use the same amount of real environment data or the same computation power for all algorithms? 

4. Missing details of the PER. PER has a mechanism to anneal the sampling bias. Since I see the proposed method used a "mixed replay" method to mitigate bias, it is important to report if there any effort (tuning the hyper-parameter) of the PER baseline has been made to anneal the bias. 


---------------------------
Missing related work. The paper belongs to the broad subarea of the sampling distribution of experiences, and there are many more papers in this category that should be discussed. I name a few highly relevant works here: 
[1] An equivalence between loss functions and non-uniform sampling in experience replay by Scott Fujimoto et al. 
[2] Remember and forget for experience replay by Guido Novati et al.
[3] Understanding and mitigating the limitations of PER by Yangchen Pan et al.
[4] regret minimization ER in off-policy RL et al. 

All these papers discuss the pros and cons of PER/ER methods, and some of them shed light on the theoretical mechanisms behind why a sampling method should be beneficial or what a good sampling distribution should be. 

----------------------
Presentation issue (I consider this not critical, but it can be significantly improved). The proposed sampling approach is not well-motivated. In the abstract, it says PER and UER may suffer from large bias and sub-optimal convergence, respectively. However, there is no evidence in the paper showing the proposed IER method is optimal or has a small bias. In fact, PER does address the biased sampling issue by using an important ratio, as introduced in the original paper (section 3.4). In contrast, the proposed method does not even have a sound method to anneal the sampling bias.
Furthermore, the paper attempts to use RER to motivate their approach too. However, the RER theory (from a system identification setting or linear MDP setting) cited by the authors does not really apply to general RL settings. I do not mean the authors need to provide a new/strong theory to motivate their method. Still, it would be a plus if the authors specify which theorems from existing work motivate their algorithmic design. 

clarity,_quality,_novelty_and_reproducibility: I comment on each of these in the above section. 
summary_of_the_review: The paper studies an important topic and presents a new ER method with extensive empirical results. However, I think the drawbacks of the algorithmic and experimental design currently outweigh the advantages. I will adjust my score based on reading the author's response and other reviewers' opinions.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper describes a novel experience replay method. Briefly, the TD error defines pivot points in the experience replay buffer. The method then uses those pivot points and select samples by moving backwards from them. This part is like reverse experience replay. Intuitively, the suggested method looks back when surprised.

The method does not theoretically analyze its properties. The justifications are based on empirical studies, on both a toy problem as well as many standard benchmarks.

Most reviewers believe that the idea is novel, the design choices are described well, and the empirical results show the superiority of the method.

On the negative side, the paper is a bit imprecise. For example, the paper mentions that previous methods have bias as one of their main weaknesses but does not actually show that their method is unbiased. In fact, the method leads to a biased sampling of the state space (this is mentioned in Discussion (Section 6) by saying that "Picking pivot points by looking at the TD error might cause more biases"). The fact that the method performs well on some benchmarks is not an indication of its unbiasedness.

Similarly problematic is the use of the terms optimal or sub-optimal, which are defined and used in non-standard ways.

I believe these can be fixed by a major revision in the paper.

Another major issue with the paper is the use of top-k seeds as the performance metric with the choice of k = 3 (this is mentioned by Reviewer FAX4), which is selected from the total number of seeds n = 5 (not specified in the paper but clarified by the authors during the discussion period).

First, computing the average performance based on 3 results leads to inaccurate estimates of the performance.

Moreover, the top-k seeds, even though used previously by some papers, is a problematic metric. To see why, consider random variables $X_1, X_2, ..., X_n$ all distributed according to a Gaussian distribution. Suppose $X_i$ is the performance of one of the seeds. The expected value of $\max_i X_i$, which corresponds to the choice of top-1, is going to behave as $O(\sqrt{\log(n)})$. That is, as you increase n, the top-1 seed performance increases in an unbounded way. So if one chooses n to be a large number, but just report the top-3, the performance could be overestimated greatly.
This is not limited to a Gaussian distribution though. The top k out of n for any distribution is biased upwards. How much bias depends on the distribution and the choice of k and n.

The unsuitability of top-k seeds metric is discussed in Henderson et al., "Deep reinforcement learning that matters," AAAI, 2018, which is already cited by the paper, as well as Agarwal et al., "Deep Reinforcement Learning at the Edge of the Statistical Precipice," NeurIPS, 2021, which is not cited. Look at Section "Random Seeds and Trials" of the former and Appendix A.4 of the latter.

I strongly suggest that the authors re-run their experiments with much larger number of seeds/runs (perhaps in the order of 20-30 for most experiments, perhaps except for Atari ones) and report the average and standard error. If the authors insist on reporting the top-k performance as well, that is OK, but they need to explain what it is measuring. It is not measuring the average performance of the algorithm. Perhaps it is an estimate for the k/n-th quantile. This should be clarified.

Overall, I believe this paper has some room for improvement, both in the quality of reported empirical results and the clarify and preciseness of its writing. Therefore, unfortunately I cannot recommend its acceptance.
justification_for_why_not_higher_score: The empirical results are questionable. The writing is imprecise.
Decision: Reject