Look Back When Surprised: Stabilizing Reverse Experience Replay for Neural Approximation
Authors: Ramnath Kumar
Dheeraj Mysore Nagaraj
Venue: Submitted to ICLR 2023 (2023)
Keywords: Experience Replay
Reinforcement Learning

Abstract: Experience replay-based sampling techniques are essential to several reinforcement learning (RL) algorithms since they aid in convergence by breaking spurious correlations.  The most popular techniques, such as uniform experience replay(UER) and prioritized experience replay (PER), seem to suffer from sub-optimal convergence and significant bias error, respectively. To alleviate this, we introduce a new experience replay method for reinforcement learning, called IntrospectiveExperience Replay (IER). IER picks batches corresponding to data points consecutively before the ‘surprising’ points. Our proposed approach is based on the theoretically rigorous reverse experience replay (RER), which can be shown to remove bias in the linear approximation setting but can be sub-optimal with neural approximation. We show empirically that IER is stable with neural function approximation and has a superior performance compared to the state-of-the-art techniques like uniform experience replay (UER), prioritized experience replay(PER), and hindsight experience replay (HER) on the majority of tasks.

Under review as a conference paper at ICLR 2023
LOOK BACK WHEN SURPRISED: STABILIZING RE- VERSE EXPERIENCE REPLAY FOR NEURAL APPROXI- MATION
Anonymous authors Paper under double-blind review
ABSTRACT
Experience replay-based sampling techniques are essential to several reinforce- ment learning (RL) algorithms since they aid in convergence by breaking spurious correlations. The most popular techniques, such as uniform experience replay (UER) and prioritized experience replay (PER), seem to suffer from sub-optimal convergence and significant bias error, respectively. To alleviate this, we introduce a new experience replay method for reinforcement learning, called Introspective Experience Replay (IER). IER picks batches corresponding to data points secutively before the 'surprising' points. Our proposed approach based on the theoretically rigorous reverse experience replay (RER), which can be shown to remove bias in the linear approximation setting but can be sub-optimal with neu- ral approximation. We show empirically that IER is stable with neural function approximation and has a superior performance compared to the state-of-the-at techniques like uniform experience replay (UER), prioritized experience replay (PER), and hindsight experience replay (HER) on the majority of tasks.
INTRODUCTION
Reinforcement learning (RL) involves learning with dependent data, and algorithms designed for independent data might behave poorly coupled with the Markovian trajectories encountered in this setting. Experience replay (Lin, 1992) involves storing the received data points in a large buffer and producing a random sample from this buffer whenever the learning algorithm requires it. Therefore experience replay is usually deployed with popular algorithms like DQN, DDPG and TD3 achieve state-of-the-art performance (Mnih et al., 2015; Lillicrap et al., 2015). It has been shown experimentally (Mnih al., 2015) and theoretically (Nagaraj et al., 2020) that these learning algorithms for Markovian data behave sub-optimally without experience replay. Note that we use the term "sub-optimal" when consistently observing a sub-pat performance compared to the oracle. In contrast, the term "instability" refers to the setting where there is a high variance in our experiments, where only few seeds work well. We maintain this distinction throughout our paper.
The simplest and most widely used experience replay method is the uniform experience replay (UER), where the data points stored in the buffer sampled uniformly at random every time a data point is queried (Mnih et al., 2015). However, UER might pick uninformative data points most of the time, which may slow down the convergence. For this reason, optimistic experience replay (OER) and prioritized experience replay (PER) (Schaul et al., 2015) were introduced, where samples with higher TD error (i.e.. 'surprise") )) are sampled more often from the buffer. Optimistic experience replay (originally called "greedy TD-error prioritisation") was shown to have a high bias, and Prioritized experience replay was proposed to solve this issue (Schaul al., 2015). However, as shown in our experiments outside of the Atari environments, PER still suffers from the problem of high bias. Although this speeds up the learning process in many cases, there can be significant biases due to picking and choosing only specific data points, which can make this method sub-optimal. The design of experience replay continues to be an active field of research. Several other experience replay techniques like Hindsight experience replay (HER) (Andrychowicz et al., 2017), Reverse Experience Replay (RER) (Rotinov, 2019), and Topological Experience Replay (TER) (Hong et al., 2022) have been proposed. An overview of these methods in discussed in Section 2.

---

Under review as a conference paper at ICLR 2023
Even though these methods are widely deployed in practice, theoretical analyses have been very limited. Recent results on learning dynamical systems (Kowshik et al., 2021b;a) showed rigorously in theoretical setting that RER is the sanceptually-grounaae data. Furthermore, this work was extended to the RI. setting in Agarwal et al. (2021) to achieve efficient Q learning with linear function approximation. The RER technique achieves good perfor- mance since reverse order sampling of the data points prevents the build-up of spurious correlations in the learning algorithm. In this paper, we build on this line of work and introduce Introspective Experience Replay (IER). Roughly speaking, IER first picks top k: 'pivot' points from large buffer according to their TD error. then returns batches of data formed by selecting the consecutive points temporally before these pivot points. In essence, the algorithm looks back when surprised. The intuition behind our approach is linked to the fact that the agent should always associate outcomes to its past actions, just like in RER. The summary of our approach is shown in Figure 1. This technique an amalgamation of Reverse Experience Replay (RER), and Optimistic Experience Replay (OER), which only picks the points with the highest TD error
algorithm when learning from Markovian
Baich
Batch
Baach
Phot 1
2hxt2
Figure An illustration of our proposed methodology when selecting h batches in the CartPole environment. The red color is used to indicate the batches being sampled from the replay buffer. The green samples are the un-sampled states from the buffer. The pivots are explicitly pointed by the arrow and the snapshot of the surprising state encountered.
Our main findings are summarized below:
Better Performance Against SOTA: Our proposed methodology (IER) outperforms previous state- of-the-art baselines such as PER, UER and HER on most environments (see Table 1, Section 5).
Conceptual Understanding: We consider simple toy example where we understand the differences between UER, RER, OER and IER (Section 3.2). This study illustrates the better performance of our proposed method by showing why naive importance sampling, like in OER incurs significant bias and b) why techniques like UER and RER are slow to learn
Forward vs. Reverse: We show that the temporal direction (forward/reverse) to consider after picking the pivot is non-trivial. We show empirically that IER performs much better than its forward counterpart, IER (F) (see Table 3). This gives evidence towards causality playing a role in the success of IER.
Whole vs. Component Parts: Our method (IER) is obtained by combining two methods RER (which picks the samples in the reverse order as received) and OER (which greedily picks the samples with the largest TD error). We show that neither of these components performs well compared to their amalgamation, IER (Table 4).
Our proposed methodology uses minimal hyperparameter tuning. We use the same policy network architecture, learning rate, batch size, and all other parameters across all our runs for a given environment. These hyperparameters are selected based on the setting required to achieve SOTA performance UER. However, we have few options available, Hindsight flag, leading to the H-IER sampler, and the Uniform Mixing fraction leading to the U-IER sampler. Furthermore, for most of experiments,
Minimal hyperparameter tuning:
a mixing fraction of 0.
2

---

Under review as a conference paper at ICLR 2023
Table 1: IER outperforms previous state-of-the-art baselines. These baselines include samplers such as UER (Mnih et al., 2013), PER (Schaul et al., 2015), and HER (Andrychowicz et al., 2017) across many environments. Results are from 13 different environments that cover broad category of MDPs. These include a few Atari environments (previously used to support the efficacy of UER, PER), some Robotics environments (previously used to support the efficacy of HER), and many other classes of environments, including Classic Control, Box 2D, and Mujoco. More details about these experiments and their setup have been discussed in Section 5.
Experience Replay Method
UER
PER
HER
IER
Best Performance Frequency
0
RELATED WORKS AND COMPARISON
2.1 EXPERIENCE REPLAY TECHINIQES
Experience replay involves storing consecutive temporally dependent data in (large) buffer in FIFO order. Whenever a learning algorithm queries for batched data, the experience replay algorithm returns sub-sample from this buffer such that this data does not hinder the learning algorithms due to spurious correlations. The most basic form of experience replay is UER (Lin, 1992) which samples the data the replay buffer uniformly at random. This approach has significantly improved the performance of off-policy RI. algorithms like DQN (Mnih et al., 2015). Several other methods of sampling from the buffer have been proposed since; PER (Schaul et al., 2015) samples experiences from probability distribution which assigns higher probability to experiences with significant TD error and is shown to boost the convergence speed of the algorithm. This out-performs UER in most Atari environments. HER (Andrychowicz et al., 2017) works in the "what if" scenario, where even sub-optimal policy can lead the agent to learn what not to do and nudge the agent towards the correct action. There have also been other approaches such as Liu et al. (2019); Fang et al. (2018; 2019) have adapted HER in order to improve the overall performance with varying intuition. RER processes the data obtained in a buffer in the reverse temporal order. We refer to the following sub-section for detailed review of this and related techniques. We will also consider 'optimistic experience replay' (OER), the naive version of PER, where at each step, only top B elements in the buffer are returned when batched data is queried. This approach is known to suffer from high bias error mitigated by a sophisticated sampling procedure employed in PER. Other works such as Fujimoto et al. (2020); Pan et al. (2022) attempt to study PER and address some of its shortcomings and Lahire et al. (2021) introduces 'large batch experience replay' (LaBER) which reduces the stochastic noise in gradients, while keeping them unbiased.
2.2 REVERSE SWEEP TECHNIQUES
Reverse sweep backward value iteration refers to methods that process the data received in reverse order. This has been studied in the context of planning tabular MDPs (Dai & Hansen, 2007: Grzeš & Hoey, 2013). We refer to Section 4 for brief overview of why these methods are considered. However, this line of work assumes that the MDP and the transition functions are known. Inspired by the behavior of biological networks, Rotinov (2019) proposed reverse experience replay where the experience replay buffer is replayed in a LIFO order. Since RER forms mini- mini-batches with consecutive data points, it is unstable with Neural approximation (i.e, it does not learn consistently across different environments). Therefore, the iterations are stabilized by 'mixing' RER with UER. However, the experiments are limited and do not demonstrate that this method outperforms even UER. similar procedure called Episodic Backward Update (EBU) is introduced in Lee et al. (2019). However, to stabilize the pure RER, the EBU method seeks to also change the target for Q learning instead of just changing the sampling scheme in the replay buffer. The reverse sweep was independently rediscovered as RER in the context of streaming linear system identification Kowshik al. (2021b), where SGD with reverse experience replay was shown to achieve near-optimal performance. In contrast, naive SGD was significantly sub-optimal due to bias caused by Markovian data. The follow- up work Agarwal et al. (2021) analyzed off-policy Q learning with linear function approximation and reverse experience replay to provide near- optimal convergence guarantees using the unique super martingale structure endowed by reverse experience replay. Hong et al. (2022) considers topological experience replay, which executes reverse replay over a directed graph of observed transitions. Mixed with PER enables non-trivial learning in some challenging environments. Another line of work
3

---

Under review as a conference paper at ICLR 2023
(Florensa et al., 2017: Moore & Atkeson, 1993; Goyal et al., 2018: Schroecker et al., 2019) considers reverse sweep with access to a simulator or using a fitted generative model. Our work on the other hand, only seeks on-policy access to the MDP.
BACKGROUND AND PROPOSED METHODOLOGY
We consider episodic reinforcement learning (Sutton & Barto, 2018), where at each time step agent takes actions a, in an uncertain environment with state st, and receives a reward fr. The environment then evolves into new state 81+11 whose law depends only 8t, dg. Our goal is to (approximately) find the policy n² which maps the environmental state to an action a such that when the agent takes the action dę π² (sx). the discounted reward E |Et y'ra] is maximized. To achieve this, we consider algorithms like DQN (Mnih et al. (2015)), DDPG (Lillicrap et al. (2015)) and TD3 (Fujimoto al. (2018)), which routinely use experience replay buffers. In this paper, introduce a new experience replay method, IER, and investigate the performance of the aforementioned RL algorithms with this modification. In this work, when we say "retum", we mean discounted episodic reward.
3.1 METHODOLOGY
We now describe our main method in a general way where we assume that we have access to data collection mechanism T which samples new data points. This then appends the sampled data points to buffer H and discards some older data points. The goal is to run an iterative learning algorithm A, which learns from batched data of batch size B in every iteration. We also consider important metric/ associated with the problem. At each step, the data collection mechanism collects a new episode and appends
the buffer H and discards some old data points, giving us the new buffer as H + T(H). We then sort the entries of H based on the importance metric I and store the indices WVG--1], 1]]. Then for every index in P, we run
of the top G data points in an array P = [P[O].... ..... P[G.... P the learning algorithm A with the batch D = (H(PI))).... H[[[i] B + 1)). In some cases, we can 'mix"' this with the standard UER sampling mechanism to reduce bias, shown below. This amalgamation help mitigate bias that could arise from our important metric sampling curriculum. We describe this procedure in Algorithm 1.
In the reinforcement learning setting, T runs an environment episode with the current policy and appends the transitions and corresponding rewards to the buffer H in the FIFO order, maintaining a total of 1E6 data points, usually. We choose A to be an RL algorithm like TD3 or DQN or DDPG. The importance function I is the magnitude of the TD error with respect to the current Q-value estimate provided by the algorithm & (i.e.. I IQ (s. a) R(s, a) 7 sup."' Qtarget (s', (,')), When the data collection mechanism (TT) is the same as UER, we will call this method IER. In optimistic experience replay (OER), points from the buffer H and return G disjoint batches each of size from these 'important' points. is clear that IER is a combination of OER and RER. Notice that we can also consider the data collection mechanism like that of HER, where examples are labeled with different goals, i.e. T has now been made different, keeping the sampling process exactly same as before. In this case, we will call our algorithm H-IER. Our experiment in Enduro and Acrobat depicts an example of this successful coalition. We also consider the RER method, which served as a motivation for our proposed approach. Under this sampling methodology, the batches are drawn from H in the temporally reverse direction. This approach is explored in the works mentioned in Section 2.2. We discuss this methodology in more detail in Appendix F.
take T to be the same as in UER. However, we query top BG data
3.2 DIDACTIC TOY EXAMPLE
In this section, we discuss the working of IER on simple environment such as GridWorld-1D, and compare this with some of our baselines such as UER, OER, RER, and IER (F). In this environment, the agent lives on a discrete I-dimensional grid of size 40 with a max-timestep of 1000 steps, and at each time step, the agent can either move left or right by one step. The agent starts from the starting state (S; [6), the goal of the agent is to reach goal state (G; [40) getting a reward of +1, and there
Mixing here denotes sampling with given probability from sampler A, and filling the remaining samples of batch with sampler B.
4

---

Under review as a conference paper at ICLR 2023
Algorithm 1: Our proposed Introspective Experience Replay (IER) for Reinforcement Learning
Input:
Data collection mechanism Data buffer H. Batch size B, grad steps per Epoch G, number of episodes N, Importance function I, learning procedure A, Uniform Mixing fraction p
<- 0: while n < N do
f 1;
H - T(H)
D Add a new episode to the buffer Compute importance of each data point in the buffer Obtain index of top C elements of
I I(H)
+ Gop(I:G)
9 + 0:
while < G do
if (1 p then
D H[ B, P[g]]
Load batch of previous B examples from pivot Pig]
else
- H(Uniform B)]
Randomly chose indices from buffer
end
0 g g+; A(D)
> Run the learning algorithm with batch data D
end
end
is also a trap state (T; (3], where the agents gets a reward of 22. The reward in every other state execute offline exploratory policy where the agent moves left or right
is O. For simplicity, with a probability of half and obtain a buffer of size 30000. The rewarding states occur very rarely in the buffer since it is hard reach for this exploration policy. The episode ends upon meeting either of two conditions: (i) the agent reaches the terminal state, which is the goal state, or (ii) the agent has exhausted the max- mex-timestep condition and has not succeeded in reaching any terminal state. An overview of our toy environment is depicted in Figure 2(a). Other hyperparameters crucial to replicating this experiment are described in Appendix B.
In this example, reaching the goal state as quickly as possible is vital to receive a positive reward and avoid the fail state. Therefore, it is essential to understand the paths which reach the goal state. Figure 2(b) depicts the number of times each state occurs in the buffer. Furthermore, the remaining subplots of Figure depict the Absolute Frequency of our off-policy algorithm trained in this environment. A state's ' "absolute frequency" is the number of times the replay technique samples a given state during the algorithm's run. The experiments on this simple didactic toy environment do highlight few interesting properties: Comparison of UER and IER: Since the goal state appears very rarely in buffer, UER and RER rarely sample the goal state and hence do not manage to learn effectively. While RER naturally propagates the information about the reward back in time to the states that led to the reward, it does not often sample the rewarding state.
Limitation of OER: While OER samples a lot from the states close to the goal state, the information about the reward does not propagate the start state. We refer to the bottleneck in Figure 2(c) where some intermediate states are not sampled.
Advantage of IER: IER prioritizes sampling from the goal state and propagates the reward backward so that the entire path leading to the reward is now aware of how to reach the reward. Therefore, combination RER and OER reduces the sampling bias in OER by preventing the bottlenecks seen in Figure 2(e).
Bottleneck of IER (F): IER (F) has a more significant bottleneck when compared to RER and chooses to sample the non-rewarding middle states most often. Also, note that whenever IER (F) chooses the goal state as the pivot, it selects the rest of the batch to overflow into the next episode, which begins at the starting state. This does not allow the algorithm to effectively learn the path which led to the goal state.
The toy example above models several salient features in more complicated RL environments.
(i) In the initial stages of learning, the exploratory policy is essentially random, and such a naive exploratory policy does not often lead to non-trivial rewards.
5

---

Under review as a conference paper at ICLR 2023
State Distribution
Absolite Frequency
Slar::
(a) GridWorld-ID enviromment
(b) Buffer
(c) UER
Absclute
Absolute
Absolute
Absolute
350
600
603
600
330
300
303
303
200
203
200
150
300
100
103
100
(d) RER
(e) OER
(I) IER
IER (F)
Figure 2: Gridworld-In 1D environment is depicted in Figure 2(a). Distribution of states in the buffer (Figure 2(b)) and relative frequeney different experience replay samplers the didactic example of GridWorld-1D environment (Figure 2(0:;2(();2(()22())22)))))
(ii) Large positive and negative reward states (the goal and trap states), and their neighbors provide the pivot state for IER and OER.
We show empirically that this holds in more complicated environments as well. Figure 3 depicts the surprise vs. reward for the Ant environment. Here we see a strong correlation between absolute reward and TD error ("Surprise factor")
(a)
(b) RER
Figure 3: Relationship between absolute values of TD Error (Surprise factor) and Reward for the Ant environment.
4 UNDERSTANDING REVERSE REPLAY
There are various conceptual ways we can look at RER and IER. This section outlines some of the motivations behind using this technique. Theoretical works such as Agarwal et al. (2021); Kowshik al. (2021b) have established rigorous theoretical guarantees for RER by utilizing super martingale structures. This structure not present in forward replay techniques (i.e., the opposite of reverse replay) shown in Kowshik al. (2021a). We refer to Appendix D where show via ablation study that going forward time instead reverse does not work very well. We give the following explanations for the success of IER.

---

Under review as a conference paper at ICLR 2023
Propogation of Sparse Rewards: In many RL problems, non-trivial rewards are sparse and only received at the goal states. Therefore, processing the data backward in time from such goal states helps the algorithm learn about the states that led to this non-trivial reward. Our study (see Figure 3 and Appendix E for further details) shows that in many environments IER picks pivots which are the states with large (positive negative) rewards, enabling effective learning-
Bias Reduction in OER: OER, which greedily chooses the examples with the largest TD error to learn from, performs very poorly due to bias. To illustrate this phenomenon, we refer the didactic example in Section 3.2. One possible way of viewing IER is that RER is used to reduce the bias in OER. Indeed, the theoretical analysis in Agarwal et al. (2021) shows that RER removes bias in Q-learning type algorithms, albeit in different sense. PER achieves similar bias reduction for OER with sophisticated and expensive sampling scheme over the buffer.
Causality: MDPs have a natural causal structure: actions and events in the past influence the events in the future. Therefore, whenever we see a surprising or an unexpected event, we can understand why or how it happened by looking into the past. Further theoretical work is needed to realize IER better.
We further illustrate the same by referring to the straightforward didactic example (Section 3.2) where can the effects of each of the experience replay methods. We also demonstrate superior performance on more complicated environments (Section 5) showcasing the robustness of our approach with minimal hyperparameter tuning.
5 EXPERIMENTAL RESULTS
In this section, we briefly discuss our experimental setup as well as the results from our experiments.
Environments: We evaluate our approach on a diverse class of environments, such as (i) Envi- romments with low-dimensional state space (including classic control and Box-2D environments), (ii) Multiple joint dynamic simulation and robotics environments (including Mujoco and Robotics environments), and (iii) Human-challenging environments (such as Atari environments). Note that previous seminal papers in the field of experience replay such as Mnih et al. (2013), Schaul et al. (2015), and Andrychowicz al. (2017) showed the efficacy of their approach on subset of these classes. For instance, UERand PER was shown to work well on Atari games. Furthermore, HER was effective in the Roboties environments such as FetchReach. In this work, we perform more ex- tensive study to show the robustness and effectiveness of our model not just in Atari and Robotics environments but also in Mujoco, Box2D, and Classic Control environments. Due to computational limitations and the non-reproducibility of some baselines, we could not extend our experiments to some Atari environments. We refer to Appendix A for a brief description of the environments used.
Hyperparameters: Refer to Appendix B for the exact hyperparameters used. Across all our experiments on various environments, we use standard setting for all the different experience replay buffers. This classic setting is set respective environment. For most of our experiments, we set the uniform mixing fraction (p) from Algorithm be O. We while training, as described in Appendix B. For PER, we use the same hyperparameters used in the Schaul et al. (2015) paper which had been proven robust across 50 different environments of Atari.
can reproduce state-of-the-ee -o-the--rt performance using UER on the
non-zero p value only for few environments overcome the bias
Metric: To compare the different models, we use the top-k seeds moving average return as the evaluation metric across all our runs. Top-k seeds here mean we take the average of seeds that gave the best performance. It is common to use top-k trials to be selected from among many trials in the reinforcement learning literature (see Schaul et al. (2015):Schaff et al. (armaa et al. (2019):Wr Wu et al. (2017);Mnis et al. (2016)). This factors in the seed sensitivity. Moving average with a given window size is taken for learning curves (with a window size of 20 for FetchReach and 50 for all others) to reduce the variation in return which is inherently present in each epoch. We argue that taking a moving average is essential since, usually, pure noise can be leveraged to pick a time instant where given method performs best (Henderson et al., 2018). Considering the top-k seed averaging of the last step performance of the moving average of the learning curves gives our metric- - the top-k seeds moving average return.
7

---

Under review as a conference paper at ICLR 2023
Comparison with SOTA: Table 2 depicts our results in various environments upon using different SOTA replay sampler mechanisms (UER, PER and HER). Our proposed sampler outperforms all other baselines in most tasks and compares favorably in others. Our experiments on various environments across various classes, such as classic control, Atari, etc., show that our proposed methodology consistently outperforms all other baselines in most environments, as summarized in Table I. Furthermore, our proposed methodology is robust across various environments, as highlighted in Table 2. The learning curves for our experiments have been depicted in the Appendix. (see Appendix C)
Table Top-k seeds Moving Average Return results across various environments. From our experi- ments, we note that IER outperforms previous SOTA baselines in most environments. Appendix B depicts the hyperparameters used for the experiment.
Dataset
UER
PER
HER
IER
CartPole
153.14
198.06
173.84
199,83
Acrobot
-257.93 a 1aam
-21..56 1
-389
a mm
-193.00 2m
Inverted Pendulum
-161.93 wus
-171.73 was
-69.44 112
-150.27 AM
LunarLander
-4.42
5,33
6.00
12.32
HollCheetah
10808.99 93 messe
99.75 1000
11072.54 2000
10544.80
2 1
Ant
3932.85 H24as
-2699.84 134
3803.17 17 MAN
4203.21
24.2
Mencher
2:0
-5.42
-5.30
-4.92
Walker
3507,03 a mose
1700.48 : s01se
889.82 a 14rtle
4349.29
Hopper
3072.65 42143
0.49 233
2685.72
122111
3205.05 40.35
Invented Double Pendulum
8489.54
7163:77
90002.05
9067.69
Fetch Reach
-1.84 est
499990 a10
-2.92 1.90
-1.74 0:44
Pong
19.15 L:3
17.02 3:2
18.70 1.4
19.10 120
Fanduro
01
514.32
586.32
The intuitive limitation to the "looking forward" approach is that in many RL problems, the objective for the agent is reach a final goal state, where the non-trivial reward is obtained. Since non-trivial rewards are only offered in this goal state, it is informative to look back from here to learn about the states that lead this. When the goals are sparse, the TD error is more likely to be large upon reaching the goal state. Our algorithm selects these as pivots, and IER (F) might select batches overflowing into the next episode. Our studies many environments (see Figure 3 and Appendix E) show that the pivot points selected based on importance indeed have large (positive negative) rewards. Our experiments depicted in Table show that IER outperforms IER (F) in most environments.
Forward vs. Reverse:
Table 3: Top-k seeds Moving Average Return results across various environments for Temporal Ablation study between IER (F) and IER (R; default). Note that we use the base setting of IER in this section to avoid spurious comparisons (i.e, with p = 0 and no hindsight).
Dataset
Forward
Rewers
CuiPPle
196.51 ext
pm
Acroboe
-433.15 =
-313,33 10u7
levened Pendulum
-582.13 : mm
Landeaander
213
HallCheetah
9369.30 30 a
10108.15
2963.71
4203.21
Reacher
1:00
Walker
2213.89 10000
2830.03
Hopper
293.64 s:s1
5U5.5W
2611
Double Pendulum
4009
FeschReuch
Pong
17.92 123
600.37 s:
$25.8
Our approach is an amalgamation of OER and RER. Here we compare these individual parts with IER. Table 4 describes the Top-k seeds Moving Average Return across various environments in this domain. As demonstrated, IER outperforms its component parts OER nor RER.
Whole vs. Component Parts:
8

---

Under review as a conference paper at ICLR 2023
Table 4: Top-k seeds Moving Average Return results across various environments for ablation study between RER, OER, and IER.
Dataset
RER
OER
IER
CortPole
163.93
162.36 s
199.83 4:
Acrohot
-320.70 stam
-472.63 am
-193,90
Invente Pendullmm
gams
-166.37 gn
-150.27 g0m
Lanarl Lander
9.84 1:
-16.08 20
12.32 mm
HalrCheetah
9449, gase
2237.91 momm
16544,88 s01
Ant
2168.47 gaanss
4203.21
Reacher
-5.91
-5.28
Walker
1578.33 1301
207.51 miw
4349.29
Hopper
206.23 koue
660.24
3205.05
46635
Inverted Double Pendulum
8953,44
7724.99
9067.69
Petch Reach
.49.44 kvvav
.47.2 kM
.1.74 k00
Pong
18.58 a/9
3.52 4333
19:10 1.
Enduro
483.98
361.21 4o0
S86.32
DISCUSSION AND CONCLUSIONS
We summarize our results and discuss possible future steps.
Speedup: TER shows a significant speedup in terms of time complexity over PER as depicted in Table 5. On average IER achieves a speedup improvement of 26.20% over PER across large umbrella of environment classes the network becomes more extensive, our approach does have a higher overhead (especially computing TD error). Future work can investigate how further reduce the computational complexity of our method by computing the TD error fewer times at the cost of operating with an older TD error. We also notice speedup of convergence towards an optimal policy of our proposed approach, as shown on few environments. Furthermore, the lack of speedup in some of the other experiments (even if they offer an overall performance improvement) could be due to the fact that the "surprised" pivot cannot be successfully utilized to teach the agent rapidly in the initial stages. We refer to Appendix C for the learning curves.
Issues with stability and consistency Picking pivot points by looking at the TD error might cause more biases and in- stability compared UER as seen some environments like HalfCheetah, LunarLander, and Ant, where there is sudden drop in performance for some episodes (see Appendix C). We observe that our strategy IER corrects itself quickly, unlike RER, which cannot do this (see Figure 5(e)). Increasing the number of pivot points per episode (the parameter G) and the uniform mixing probability p usually mitigates this. However, these steps might slow the initial convergence to locally op- timal policy. In this work, we do not focus on tuning these syper-parameters since our objective was to obtain methods that require minimal hyper-parameter tuning. However, future work can systematically investigate the significance of these parameters in various environments.
Table 5: Average Speedup in terms of time complexity over PER across various environment classes.
Environment
Average Speedup
Classic Control
32.66%
Box-2D
54.32%
Mujeco
18.09%
Roboties
55.56%
Atari
6.53%
Why does IER outperform the traditional RER? The instability of pure RER with neural approximation has been noted in various works (Rotinov, 2019; Lee et al., 2019), where RER is stabilized by mixing it with UER Hong et al. (2022) stabilizes reverse sweep by mixing it with PER. This is an interesting phenomenon since RER is near-optimal in the tabular and linear approximation settings (Agarwal et al., 2021). Two explanations of this are i) The loss function used to train the neural network is highly non-convex, which hinders the working of RER and ii) The proof given in Agarwal et al. (2021) relies extensively on 'coverage' of the entire state- aate-nction space that is, the entire state-action space is visited enough number of times which might not hold, as shown in the toy example in Section 3.2.

---

Under review as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
In this paper, we work with thirteen datasets, all of which are open-sourced in gym (https: //github. com/ www.oopengggiaee gym). More information about the environments available Ap- pendix A. We predominantly use DQN, DDPG and TD3 algorithms in our research, both of which have been adapted from their open-source code. We also experimented with seven different replay buffer methodologies, all of which have been adapted from their source code?. More details about the models and hyperparameters are described Appendix B. All runs have been run using the A A100-SXM440GGB, TITAN RTX, and V100 GPUs.
REFERENCES
Naman Agarwal, Syomantak Chaudhuri, Prateek Jain, Dheeraj Nagaraj. and Praneeth Netrapalli. Online target q-learning with reverse experience replay: Efficiently finding the optimal policy for linear mdps. arXiv preprint vrXiv:2110.08444/ 2021.
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience replay. Advances in neural information processing systems, 30, 2017.
Andrew G Barto, Richard S Sutton, and Charles W Anderson. Neuronlike adaptive elements that can solve difficult learning control problems. IEEE transactions on systems, man, and cybernetics, (5): 834- 846, 1983.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint arXiv: 2016.
Peng Dai and Eric A Hansen. Prioritizing bellman backups without priority queue. In ICAPS, pp. 113-119, 2007.
Meng Fang, Cheng Zhou, Bei Shi, Boqing Gong, Jia Xu, and Tong Zhang. Dher: Hindsight experience replay for dynamic goals. In International Conference on Learning Representations, 2018.
Meng Fang, Tianyi Zhou, Yali Du Lei Han, and Zhengyou Zhang. Curriculum-guider hindsight experience replay. Advances in neural information processing systems, 32, 2019.
Carlos Florensa, David Held, Markus Wulfmeier, Michael Zhang, and Pieter Abbeel. Reverse curriculum generation for reinforcement learning. In Conference robot learning, pp. 482-495. PMLR, 2017.
Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor- critic methods. In International conference on machine learning, pp. 1587-1596. PMLR, 2018.
Scott Fujimoto, David Meger, and Doina Precup. An equivalence between loss functions and non- uniform sampling in experience replay. Advances in neural information processing systems, 33: 14230, 2020.
Anirudh Goyal, Philemon Brakel, William Fedus, Soumye Singhal, Timothy Lillicrap, Sergey Levine, Hugo Larochelle, and Yoshua Bengio. Recall traces: Backtracking models for efficient reinforcement learning. arXiv preprint
2018.
Marek Grzeš and Jesse Hoey. On the convergence of techniques that improve value iteration. In The 2013 International Joint Conference on Neural Networks (IJCNN, pp. 1-8. IEEE, 2013.
Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pincau. Doina Precup, and David Meger. Deep reinforcement learning that matters. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
Zhang-Wer Wei Hong, Tao Chen, Yen-Chen Lin, Joni Pajarinen, and Pulkit Agrawal. Topological experience replay. arXiv preprint arXiv:2003. 15845, 2022.
Phttps://git wttptttt...oo////o/rrorrooeo garage
10

---

Under review as a conference paper at ICLR 2023
Suhas Kowshik, Dheeraj Nagaraj. Prateek Jain, and Praneeth Netrapalli. Near-optimal offline and streaming algorithms for learning non-linear dynamical systems. Advances Neural Information Processing Systems, 34, 2021a.
Suhas Kowshik, Dheeraj Nagaraj. Prateek Jain, and Praneeth Netrapalli. Streaming linear system identification with reverse experience replay. Advances in Neural Information Processing Systems, 34, 2021b.
Thibault Lahire, Matthieu Geist, and Emmanuel Rachelson. Large batch experience replay. arXiv preprint arXiv:2/1000111 2021.
Su Young Lee, Choi Sungik, and Sac- Young Chung. Sample-cfficient deep reinforcement learning via episodic backward update. Advances in Neural Information Processing Systems, 32, 2019.
Timothy Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Frez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint #rXiv:/509.0297/ 2015.
Long-Ji Lin. Self-improving reactive agents based on reinforcement learning, planning and teaching. Machine learning. 8(3):293-321) 1992.
Hao Liu, Alexander Trott, Richard Socher, and Caiming Xiong. Competitive experience replay. arXiv preprint arXiv: 2019.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):52-533,, 2015.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap. Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. International conference on machine learning, pp. 1928-1937. PMLR, 2016.
Andrew W Moore and Christopher G Atkeson. Prioritized sweeping: Reinforcement learning with less data and less time. Machine learning, 13(1):103-130 1993.
Dheeraj Nagaraj, Xian Wu, Guy Bresler, Prateek Jain, and Praneeth Netrapalli. Least squares regres- sion with markovian data: Fundamental limits and algorithms. Advances in neural information processing systems, 33: 16666-16666. 2020.
Yangchen Pan, Jincheng Mei,
Farahmand, Martha White, Hengshuai Yao, Mohsen Rohani, and Jun Luo. Understanding and mitigating the limitations of prioritized replay. In The 38th Conference on Uncertuinty in Artificial Intelligence, 2022.
Matthias Plappert, Marcin Andrychowiez, Alex Ray, Bob McGrew, Bowen Baker, Glenn Powell, Jonas Schneider, Josh Tobin, Maciek Chociej. Peter Welinder, et al. Multi reinforcement learn- ing: Challenging robotics environments and request for research. arXiv preprint 1xXx::8802.09644 2018.
Egor Rotinov, Reverse experience replay. arXiv preprint 191.v::910008780 2019.
Muhammad Sarmad, Hyunjoo Jenny Lee, and Young Min Kim. Rl-gan-net: A reinforcement learning agent controlled gan network for real-time point cloud shape completion. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp- 5898-5907, 2019.
Charles Schaff, David Yunis, Ayan Chakrabarti, and Matthew Walter. Jointly learning to construct and control agents using deep reinforcement learning. In 2019 International Conference Robotics and Automation (ICRA), pp. 9798-9805. IEEE, 2019.
Tom Schaul, John Quan, loannis Antonoglou, and David Silver. Prioritized experience replay. arXiv preprint arXiv: 1.05952, 2015.
11

---

Under review as a conference paper at ICLR 2023
Yannick Schroecker, Mel Vecerik, and Jonathan Scholz. Generative predecessor models for sample- efficient imitation learning. arXiv preprint arXiv:1904.011333 2019.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High-dimensional continuous control using generalized advantage estimation. arXiv preprint arXiv: 02438, 2015.
Richard S Sutton. Generalization in reinforcement learning: Successful examples using sparse coarse coding. Advances in neural information processing systems, 8, 1995.
Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ infernational conference intelligent robots and systems, pp. 5026-5033. IEEE, 2012.
Pawel Wawrzyúski. A cat-like robot real-time learning to run. In International Conference on Adaptive and Natural Computing Algorithms, pp. 380-390. Springer, 2009.
Yuhuai Wu, Elman Mansimov, Roger B Grosse, Shun Liao, and Jimmy Ba. Scalable trust-region method for deep reinforcement learning using kronecker-factored approximation. Advances in neural information processing systems, 30, 2017.
12

---

Under review as a conference paper at ICLR 2023
A ENVIRONMENTS
For all OpenAl environments, data is summarized from http://ppp//gghhh....ooo//////// and more information is provided in the wiki https: /ttp://gttttt//// com/ wwtom//ppaa/g//a/e Below briefly describe some of the tasks we experimented in this paper.
A.1 CARTPOLE-VO
CartPole, as introduced in Barto et al. (1983), is task of balancing a pole on top of the cart. The cart has access to position and velocity as its state vector. Furthermore, it can go either left or right for each action. The task is over when the agent achieves 200 timesteps without a positive reward (balancing the pole) which the goal state or has failed, either when (i) the cart goes out of boundaries (# 2.4 units off the center), or (ii) the pole falls over (less than + 12 deg). The agent is given continuous d-dimensional space describing the environment and can respond by returning one of two values, pushing the cart either right or left.
A.2 ACROBOT-VI
Acrobot, as introduced in Sutton (1995), is a task where the agent is given rewards for swinging double-jointed pendulum up from stationary position. The agent can actuate the second joint by one of three actions: left, right, or no torque. The agent is given a six-dimensional vector comprising the environment's s angles and velocities. The episode terminates when the end of the second pole is over the base. Each timestep that the agent does not reach this state gives a -1 reward, and the episode length 500 timesteps.
A.3 PENDULUM-VO
The inverted pendulum swingup problem, introduced in Lillicrap al. (2015) is based the classic problem in control theory. The system consists of a pendulum attached fixed at one end, and free the other end. The pendulum starts in random position and the goal is apply torque on the free end to swing it into an upright position, with its center of gravity right above the fixed point. The episode length 200 timesteps, and the maximum reward possible is O, when no torque being applied, and the object has O velocity remaining at an upright configuration.
A.4
The LunarLander environment introduced in Brockman et al. (2016) is a classic rocket trajectory optimization problem. The environment has four discrete actions do nothing. fire the left orientation engine, fire the right orientation engine, and fire the main engine. This scenario is per Pontryagin's 's maximum principle, as it is optimal to fire the engine at full throttle turn it off. The landing coordinates (goal) is always at (0, 0). The coordinates are the first two numbers in the state vector. There are a total of 8 features in the state vector. The episode terminates if (i) the lander crashes, (ii) the lander gets outside the window, or (iii) the lander does not move nor collide with any other body.
A.5 HALFCHEETAH-v2
HalfCheetah an environment based on the work by Wawrzyúski (2009) adapted by Todorov et al. (2012). The HalfCheetah is 2-dimensional robot with nine links and eight joints connecting them (including two paws). The goal is to apply torque on the joints to make the cheetah run forward (right) fast as possible, with positive reward allocated based the distance moved forward and negative reward is given for moving backward. The torso and head of the cheetah are fixed, and the torque can only be applied the other six joints over the front and back thighs (connecting the torso), shins (connecting to the thighs), and feet (connecting to the shins). The reward obtained by the agent is calculated as follows:
T1 =
0.1 ||
13

---

Under review as a conference paper at ICLR 2023
A.6 ANT-V2
Ant is environment based on the work by Schulman et al. (2015) and adapted by Todorov et al. (2012). The ant is a 3D robot with one torso, a free rotational body, and four legs. The task is to coordinate the four legs move in the forward direction by applying torques on the eight hinges connecting the two links of each leg and the torso. Observations consist of positional values of different body parts of the ant, followed by the velocities of those individual parts (their derivatives). with all the positions ordered before all the velocities, The reward obtained by the agent is calculated as follows:
T1 4i 0.5 * | 0.0005 * %t
contact
+1
A.7 REACHER-V2 V2
The Reacher environment, introduced in Todorov et al. (2012), is two-jointed robot arm. The goal to move the robot's end effector (called *fingertip*) close to a target that is spawned at a random positions. The action space is two-dimensional vector representing the torque to be applied at the two joints. The state space consists of angular positions (in terms of cosine and sine of the angle formed by the two moving arms), coordinates, and velocity states for different body parts followed by the distance from target for the whole object.
A.8 HOPPER-V2
The Hopper environment, as introduced in Todorov et al. (2012), sets out to increase the number of independent state and control variables compared to classic control environments. The hopper is two-dimensional figure with one leg that consists of four main body parts the torso at the top, the thigh in the middle, the leg at the bottom, and single foot on which the entire body rests. The goal of the environment is to make hops that move in the forward (right) direction by applying torques on the three hinges connecting the body parts. The action space is a three-dimensional element vector. The state space consists of positional values for different body parts followed by the velocity states of individual parts.
A.9 WALKER-V2
The Walker environment, as builds on top of the Hopper environment introduced in Todorov et al. (2012), by adding another set of legs making it possible for the robot to walker forward instead of hop. The hopper is a two-dimensional figure with two legs that consists of four main body parts the torso at the top, two thighs the middle, two legs at the bottom, and two feet on which the entire body rests. The goal of the environment is to coordinate both feel and move in the forward (right) direction by applying torques on the six hinges connecting the body parts. The action space is six-dimesiional element vector. The state space consists of positional values for different body parts followed by the velocity states of individual parts.
A. INVERTED
Inverted Double-Pendulum as introduced in Todorov et al. (2012) is built upon the CartPole environ- ment as introduced in Barto et al. (1983), with the infusion of Mujoco. This environment involves a cart that can be moved linearly, with pole fixed and second pole on the other end of the first one (leaving the second pole as the only one with one free end). The cart can be pushed either left or right. The goal is to balance the second pole on top of the first pole, which is on top of the cart, by applying continuous forces on the cart. The agent takes a one-dimensional continuous action space in the range [,,, denoting the force applied to the cart and the sign depicting the direction of the force. The state space consists positional values of different body parts of the pendulum system, followed by the velocities of those individual parts (their derivatives) with all the positions ordered before all the velocities. The goal is to balance the double-inverted pendulum on the cart while maximizing its height off the ground and having minimum disturbance in its velocity.
14

---

Under review as a conference paper at ICLR 2023
A.11 FETCHREACH-VL
The FetchReach environment introduced in Plappert et al. (2018) was released as part of OpenAl Gym and used the Mujoco physics engine for fast and accurate simulation. The goal 3-dimensional and describes the desired position of the object. Rewards in this environment are sparse and binary. The agent obtains a reward of 0 if the target location at the target location (within a tolerance of em) and -1 otherwise. Actions are four-dimensional, where specifies desired gripper movement, and the last dimension controls the opening and closing of the gripper. The FetchReach aims to move the gripper target position.
A.12 PONG-VO
Pong, also introduced in Mnih et al. (2013), is comparatively more accessible than other Atari games such as Enduro. Pong a two-dimensional sports game that simulates table tennis. The player controls an in-game paddle by moving vertically across the left and right sides of the screen. Players use this paddle to hit the ball back and forth. The goal is for each player to reach eleven points before the opponent, where the point is earned for each time the agent returns the ball and the opponent misses.
A.13 ENDURO-VO
Enduro, introduced in Mnih et (2013), is hard environment involving maneuvering race car in the National Enduro, long-distance endurance race. The goal of the race is to pass a certain number of cars each day. The agent must pass 200 cars on the first day and 300 cars on all subsequent days. Furthermore, as time passes, the visibility changes as well. At night in the game, the player can only see the oncoming cars' taillights. As the days' progress, cars will become more challenging to avoid. Weather and time of day are factors in how to play. During the day, the player may drive through an icy patch on the road, which would limit control of the vehicle, or a patch fog may reduce visibility.
B MODEL AND HYPERPARAMETERS
In this paper, work with two classes of algorithms: DQN, DDPG and TD3. The hyperparameters used for training our DQN algorithms in various environments are described in Table 6. The hyperparameters used for training our DDPG algorithms in various environments are described in Table 7. The hyperparameters used for training DDPG are described in Table 7. Furthermore, the hyperparameters used for training TD3 are described in Table 8.
Table 6: Hyperparameters used for training DQN on various environments.
Description
CartPole
Accobot
Lunael.ndder
Gearnal Sarings
Discoutt
0.9
0.0
0.9
0,55
0.99
discount
Ratch six
512
512
512
32
batch ud tiee
Number of spadis
100
100
200
150
900
nuepochir
Sugs per guads
10
30
10
20
20
ssspa_pws_eppoe
Number tain stess
300
300
300
125
125
nan crain steps
Target rpdir fropunccy
30
target update Erequency
Replay Buffer size
1.a
1.
16
1.
batfer_olae
Alguniiten Sontiur
CNN Channcs
CNN Policy Stides
(4,2. 1)
Policy hiiden sizee (MLP))
08.53
(8.5)
(8.5)
(312.)
(512.)
pol didee sieee batch ch. shie
Ruifer batch size
198
196
32
Asploratios Settingg
Mas spellon
1.0
1.0
1.0
1.0
1.0
max_mpsilon
Mis spilon
0.01
0.1
0.1
0,01
0.01
minLepsilon
Dociy ritio
044
0.13
0.1
0.1
decay ratio
Optimizar Seoings
Leaming rate
Sem4
5e-5
16-4
JER Sentivrr
Use Hindight for woring states
Mising Factor
15

---

Under review as a conference paper at ICLR 2023
Table 7: Hyperparameters used for training DDPG Pendulum environment.
Description
Pendulum
arqumert_name
General Settings
Discount
0.95
discourt
Batch size
256
batch_sizz
Number of epochs
30
n_epochs
Steps per epochs
50
steps_per_epoch
Number of train steps
40
num_train_steps
Target update Tau
0.01
La:get_ Trequenny
Replay Buffer size
le
baffer_sia
Algorithm Settings
Policy hidden sizes (MLP)
(400,300) 300)
pol ____iddee_siize of af_hidden_sizes batch_size
QF hidden sizes (MIP)
(400,300)
Buffer batch size
256
Exploration Settings
Exploration Policy Sigma
Ornstein Uhlenbeck Noise 0.2
exp_ hxp_policy sigma
Optimizer Settings
Policy Learning rale QF Learning rate
le
pol_rr qr_lr
le-a
IER Specific Sertings
Use Hindkight for storing states Mixing Factor (p)
use use_hindsing hindsight
Table 8: Hyperparameters used for training TD3 on various environments.
Description
Doable Penddlum
HalfChectah
FeichReach
aegurent__paree
General Settings
Discoust
0.50
01:00
11.99
0.86
discount
natch_aiie
spocts
epochs
50
Number
100
100
Replay Butle: size
1ea
1:4
Le
1c
10
buffez_aize
Algonttle Sentiggr
hidden (MLP))
(50)
(156,
(256, 200)
206)
(20)
golhidden hiddeddennnniee
0/2
022
Turgel update
6,065
0,305
0.006
0,005
0,005
0,005
0,01
tau
Harfer butch sine
100
100
100)
100
100
100
156
batch sime
Canoniaa nnier Equionstivn Sentinge
0.1
Min
0.1
011
0.1
0.1
Optiwizer Settings
Polccy Learning rate Leaming
3--
pol
Syecile
Use Hisdsial stxtngg stnce Mixcing Packer
hindsiin
04
83
08
Additionally, we use Tabular MDPs for learning policy in toy example. Since the environment fairly simpler, and has very few states, function approximation unnecessary. For all the agents trained on GridWorld,
common setting described in Table 9.
Table 9: Hyperparameters used for training Tabular MDP on GridWorld- ID environment.
Description
GridWorld
argument__nor name
Discount
0.99
discount
battch_st
Number of epochs
100
n_epochs
Replay Buffer size
3e
burfer_sil
Butler batch size
64
batch_ bize
Esploratoo factor
0.3
max_epsilon
Learning
16

---

Under review as a conference paper at ICLR 2023
C ADDITIONAL RESULTS
C.I PERFORMANCE OF IER WITH LOW-DIMENSIONAL. STATE SPACE
This section briefly discusses results environments with a low-dimensional state space, such as classic control environments (CartPole, Acrobot, and Pendulum) and Box-2D environments (LunarLander). Figure depicts the learning curves of our DQN/DDPG agents in these environments.
-100
400
300
400
Stap
Step
20
HER
PPER
IER
(a) CartPole-vO
(b) Acrobot-vi
Anerage Retum
-1000
-100
Stop
(c) Pendulum-vO
(d) LunarLander-v2
Figure 4: Learning curves of DQN/DDPG agents Classic Control and Box-2D environments.
We note that proposed methodology significantly outperform other baselines for the classic control algorithms. Furthermore, Figure 4(a) shows excellent promise as we achieve a near-perfeed score across all seeds in one-tenth of the time it took to train PER.
C.2 PERFORMANCE IN MULTIPLE JOINT DYNAMICS SIMULATION AND ROBOTICS ENVIRONMENTS
Multiple joint dynamic simulation environments (mujoco physics environments) and robotics environ- such HalfCheetah, Ant, Inverted Double-Pendulum. and FetchReach (Todorov al. (2012); Plappert et al. (2018)) are more complex and enable us to study whether the agent can understand the physical phenomenon of real-world environments. Figure 5 depicts the learning curves of our TD3 agents in these environments. Again, our proposed methodology outperforms all other baselines significantly in most of the environments studied this section. Additionally, it is essential to point out that our proposed method shows an impressive speedup of convergence in Inverted Double Pendulum and convergence to much better policy in Ant.
C.3 PERFORMANCE IER IN HUMAN CHALLENGING ENVIRONMENTS
This section briefly discusses our results on human-challenging environments such as Atari envi- ronments (Pong and Enduro). These environments are highly complex, and our algorithms take millions of steps to converge to a locally optimal policy. Figure 6 depicts the learning curves of our DQN agents in these environments. We note that proposed methodology can perform favorably when compared to other baselines for the Atari environments and can reach large reward policies significantly faster than UER.
17

---

Under review as a conference paper at ICLR 2023
Aetrgng Retuum
8000
4000
2003
HalfChcetah-v2
(b) Ant-v2
Rotum
4020
2020
1030
-10
UER
IUR
-EER
PER
(c) Reacher-v2
(d) Walker-v2
3000
Auarage
6030
4020
1000
500
St39
Stop
100
200
400
500
200
420
UER
HER
-EER
IER
.LER
TER
HER
FER
(e) Hopper-v2
(f InveredDDuhhePendulumgg
-10
-00
-00
Step
20
60
50
CER
HER
-PER
UER
(g) FetchReach-vi
Figure 5: Learning curves of TD3 agents on Mujoco and Robotics environments.
C.4 WHOLE COMPONENT PARTS
This section briefly presents the learning curves of our models on three different sampling schemes: IER, OER and RER.
C.5 BUFFER BATCH SIZE SENSITIVITY OF IER
This section briefly presents the sensitivity to the buffer batch size hyperparameter for our proposed approach (IER). To analyze this, batch size of the range 2-256. Table 10 and Figure 8 depict the buffer batch size sensitivity results from proposed sampler.
experiments the CartPole environment with varying
18

---

Under review as a conference paper at ICLR 2023
10
(a) Pong-v0
(b) Enduro-vO
Figure 6: Learning curves of DQN agents Atari environments.
-00
-20
380
201
(a) CartPole-vO
(b) Acrobot-vl
(c) Pendulum v0
(d) LunarLander-v2
(e) HalfCheetah-v2
(f) Ant-v2
180
(g) Reacher-v2
(h) Walker-v2
(i) Hopper-v2
300
ii) InvertelDDuhleeendduun-Z
(k) FetchReach-vl
(I) Pong-vO
340
(m) Enduro-v0
Figure 7: Ablation study of OER, RER and IER.
19

---

Under review as a conference paper at ICLR 2023
Table 10: Buffer Batch size sensitivity of IER the CartPole environment.
Buffer Batch Size
Average Reward
2
126.69
4
192.33 1329
8
181.27 #2313
16
199.24 # 1.32
32
199.99 0001
64
199.83
128
193.23 393.33 10.08
256
179.95 1894
200
Average Return
150
100
Step
0
0
20
40
60
80
8
4
256
16
128
32
64
Figure 8: Buffer batch size sensitivity of IER sampler on the CartPole Environment
C.6 HOW IMPORTANT SAMPLING PIVOTS?
This section briefly presents the ablation study analyze the importance of sampling "surprising" states as pivots. As a baseline, we build a experience replay where these pivots are randomly sampled from the buffer. The "looking back" approach is used to create batches of data. For nomenclature, refer to our proposed approach (IER) to use the "TD Metric" sampling of pivots, and the baseline that uses "Uniform" sampling of pivots. Table 11 and Figure 9 depict the buffer batch size sensitivity results from our proposed sampler.
Table 11: Importance of sampling pivots in our proposed approach (IER) on the CartPole environment.
Sampling Scheme
Average Reward
TD Metric (IER)
199.83 031
Uniform (TER)
136.71 1959
C.7 How IMPORTANT IS "LOOKKIN BACK"?
This section briefly presents the ablation study to analyze the importance of "looking back" after sampling pivots. As baseline, we build experience replay where sample uniformly instead of looking back. For nomenclature, we refer to our proposed approach (IER) to use the "Looking Back" approach (similar to IER), and the baseline that uses "Uniform" approach. We refer to these two approaches as possible filling schemes, i.e. fill the buffer with states once the pivot state is sampled.
Table 12 and Figure 10 depict the buffer batch size sensitivity results from proposed sampler.
20

---

Under review as a conference paper at ICLR 2023
200
Average Return
150
100
Step
0
0
20
40
60
80
Uniform Sampling
TD Metric Sampling
Figure 9: Ablation study Importance Sampling of IER sampler on the CartPole Environment. Here "Uniform Sampling" denotes the unbiased and random sampling of pivots, and "TD Metric Sampling" denotes our proposed approach (IER).
Table 12: Importance of looking back in our proposed approach (IER) on the CartPole environment.
Filling Scheme
Average Reward
Looking Back (IER)
199.83 0:31
Uniform (IER)
182.5 2349
200
Average Return
150
100
Step
0
0
80 Uniform Filling Looking Back Filling
20
40
60
Figure 10: Ablation study of Filling Scheme IER sampler on the CartPole Environment. Here "Uniform Filling" denotes the unbiased and random sampling of states to fill after sampling the pivot state, and "Looking Back Filling" denotes our proposed approach (IER).
D ABLATION STUDY OF TEMPORAL EFFECTS
This section studies the ablation effects of going temporally forward and backward once we choose a pivot/surprise point. Furthermore, Figure depicts the learning curves of the two proposed methodologies. We notice that against theoretical intuition, the unbiased forward sampling scheme is worse in most environments compared to the reverse sampling scheme.
E SPARSITY AND REWARDS OF SURPRISING STATES
E. SURPRISING STATES HAVE LARGE REWARDS
In this section, we study the "learning from sparse reward" intuition provided in Section 4 i.c., we check if the states corresponding to large TD error correspond to states with large (positive
21

---

Under review as a conference paper at ICLR 2023
1000
40
(a) CartPole-vO
(b) Acrobot-v1
(c) Pendulum-vO
Fiverss Forvard
Spvertaa Schaard
Foroard
(d) LunarLander--2
(e) HallCheetah-v2
(f) Ant-v2
(g) Reacher-v2
(h) Walker-v2
(i) Hopper-v2
(i) InverteiDDuhhePenndtum--2
(k) FetchReach-vl
()) Pong-vO
(m) Enduro-vO
Figure 11: Ablation study of the effects of the temporal structure the performance of the agent.
negative) rewards. To test the hypothesis, we consider a sampled buffer and plot the TD error of these points in the buffer against the respective reward. Figure shows the distribution of TD error against reward for the sampled buffers in the Ant environment. We that high reward states (positive or negative) also have higher TD errors. Therefore, our algorithm picks large reward states as endpoints to learn in such environments.
E.2 SURPRISING STATES ARE SPARSE AND ISOLATED
Figure 12 and Figure 13 depict the distribution of "surprise" //D emror in a sampled batch for CartPole and Ant environments respectively. These two figures help show that the states with large "surprise" factor are few and that even though the pivot of a buffer has a large TD error, the rest of the buffer typically does not.
Figure 12(d) and Figure 13(d) show magnified view of Figure 12(c) and Figure 13(d) where the pivot point selected is dropped. This helps with uniform comparison with the remaining timesteps within
22

---

Under review as a conference paper at ICLR 2023
the sampled buffer. Again, we notice little correlation between the timesteps within the sampled buffer.
Spantyy AwIVE DVC pethers DErUER
Spartyy AWW/E PORT MAPO oether
Tarmatee Brier (a) UER
Sarmaiio tow (b) RER
(c) IER
Searity Amstlatt over 3 pemmleed fufferr magetted
(d) IER Magnified
Figure 12: Normalized TD Error ("Surprise factor") of each timestep over three different sampled buffers on the CartPole environment. Best viewed when zoomed.
F REVERSE EXPERIENCE REPLAY (RER)
This section discusses our implementation of Reverse Experience Replay (RER), which served as motivation for our proposed approach. The summary of the RER approach is shown in Figure 14. Furthermore, an overview of our implemented approach RER is described briefly in Algorithm
23

---

Under review as a conference paper at ICLR 2023
amoedd
(a) UER
(b) RER
(c) IER
(d) IER Magnified
Figure 13: Normalized TD Error ("Surprise factor") of each timestep over three different sampled buffers the Ant environment, Best viewed when zoomed.
Temperely
Bassh
Butch
Figure 14: An illustration of Reverse Experience Replay (RER) when selecting & batches from the Replay Buffer.
24

---

// Load batch of previous B samples from Under review as a conference paper at ICLR 2023
Algorithm 2: Reverse Experience Replay
Input: Data collection mechanism Data buffer H., Batch size B, grad steps per Epoch G, number of episodes N, learning procedure A
f- N;
P < len(H):
// Set index to last element of Buffer H
while n N do
4- n 1;
H + T(H);
// Add a new episode to the buffer
g 0:
while < G do
if P B 0 then
P + l
// Set index to last element of Buffer H
else
P + P B:
end
+ H(P- - B, P];
index P
9 g +1
A(D);
// Run the learning algorithm with batch data D
end
end
25


Reviews:
[{"review_id": "fP0vENMk4W", "reviewer": "Reviewer_HzYs", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. \n", "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. ", "strength_and_weaknesses": "Strength: \n\n1. The topic of ER mechanism is interesting and important; \n2. The paper presents its mean idea very clear;\n3. The proposed sampling method seems to be novel;\n4. The paper conduct extensive experiments on a variety of domains. \n\nWeaknesses: \n\n---------------------------\nAlgorithm 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. \n\nFigure 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? \n\n---------------------------\nConcerns about experiments. The empirical results are extensive but not persuasive. \n\n1. 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. \n\n2. Missing at least two intuitive baselines to make the proposed method more persuasive:\n1). 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.\"\n2). 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\n\n3. 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? \n\n4. 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. \n\n\n---------------------------\nMissing 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: \n[1] An equivalence between loss functions and non-uniform sampling in experience replay by Scott Fujimoto et al. \n[2] Remember and forget for experience replay by Guido Novati et al.\n[3] Understanding and mitigating the limitations of PER by Yangchen Pan et al.\n[4] regret minimization ER in off-policy RL et al. \n\nAll 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. \n\n----------------------\nPresentation 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.\nFurthermore, 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. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "dKUg2GGJc-I", "reviewer": "Reviewer_j7Bo", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. ", "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.", "strength_and_weaknesses": "**Strengths:**\n- 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.\n-  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.\n- The authors report that empirically their approach requires minimal hyperparameter tuning.\n- The paper is very well-written.\n\n**Weaknesses:**\n\nI did not find any major weaknesses that would justify rejection. Some details are unclear:\n- 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? \n- Does the results in Section 3.2 change if the environment is stochastic? \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "UXwnHSrhYxh", "reviewer": "Reviewer_FAX4", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.", "strength_and_weaknesses": "### Strengths \n\nThe paper tries to capture the idea that rewards should be propagated backwards, starting from states which have the largest TD error.\n\n### Weaknesses \n\nThe 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.  \nAdditionally, 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.   \nOverall, there are no strong arguments for the presented method (neither formal nor empirical).\n\n### Algorithmic contribution\n\nThe contribution is minor and not really supported by anything else than claims and vague intuitions.  \nIt 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).   \nGruslys, 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.  \nZhang, S. and Sutton, R. S. A deeper look at experience replay. In NeurIPS 2017 Deep Reinforcement Learning Symposium, 2017.\n\nThe algorithm itself is unclear and not really discussed.  \nIn 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.  \nHow do you guarantee all states will eventually be updated?  \nHow does function approximation come into play?  \nWhat is the exploration strategy?  \n\n### Theoretical soundness\n\nEverything 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.  \nBesides 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.   \nAdditionally, besides the claims that theoretical results are in previous papers, there is no new formal result in this paper.\n\nAll the arguments are rather vague and seemingly intuitive.  \n\nLots 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).  \n\n### Literature coverage\n\nI'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).\n\nThis 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.\n\nI 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.\n\nMost 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.  \nLahire, T., Geist, M., & Rachelson, E. (2022). Large Batch Experience Replay. International Conference on Machine Learning.\n\n### Empirical evaluation\n\nThe 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?  \nI 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.\n\nThe \"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?  \nThe 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.  \nI 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?\n\nOverall the experimental validation is unconvincing.\n\n### Paper organization.\n\nVery bad organization and writing overall: \n- 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).\n- 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).\n- Excessive use of superlatives for unsupported claims (minimal tuning, important metric...).\n- 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\").\n- Lots of typos (e.g. \"important\" instead of \"importance\", \"staring\" instead of \"starting\")\n- Misinterpretation of the assignment operator \"$\\leftarrow$\".\n- Poor English.\n- Repetitions about what is in the appendix and too little discussion in the main text.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "1MTr8EYT4O", "reviewer": "Reviewer_nF51", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. \n\nThe intuition of the paper is that an agent should select transitions that associate with outcomes. \n\nIn 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.\n", "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. ", "strength_and_weaknesses": "> Strength\n\nThe problem is important and very interesting. \n\nConsidering the pivot points and selecting transitions before outcomes seems to be new for experience replay.\n\nThe experiments show the proposed method works better than others.\n\n>Weaknesses\n\nThe paper argues that the previous methods have bias. Does the proposed have bias too? The paper needs to provide an analysis about it.  \n\nThe 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?\n\nRelated 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. \n\nFor 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.\n\nIt is better to improve the writing of the paper. For example, in Figure 1, the paper uses colors but does not provide explanation. \n\nIn Table 2, why does not  IER work better in Pong?\n\nIn Table 2 and Table 3, why do IER and Reverse have different results?\n\nThe 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. \n\nWhy does not the paper provide learning curves for comparing different methods? Using curves is common to present results. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject