Introspective Experience Replay: Look Back When Surprised
Authors: Ramnath Kumar
Dheeraj Mysore Nagaraj
Venue: Accepted by TMLR ()

Abstract: In reinforcement learning (RL), experience replay-based sampling techniques are crucial in promoting convergence by eliminating spurious correlations. However, widely used methods such as uniform experience replay (UER) and prioritized experience replay (PER) have been shown to have sub-optimal convergence and high seed sensitivity, respectively. To address these issues, we propose a novel approach called Introspective Experience Replay (IER) that selectively samples batches of data points prior to surprising events. Our method is inspired from the reverse experience replay (RER) technique, which has been shown to reduce bias in the output of Q-learning-type algorithms with linear function approximation. However, RER is not always practically reliable when using neural function approximation. Through empirical evaluations, we demonstrate that IER with neural function approximation yields reliable and superior performance compared to UER, PER, and hindsight experience replay (HER) across most tasks.

Published in Transactions on Machine Learning Research (01/2024)
Introspective Experience Replay: prised
Look
Back When Sur-
Ramnath Kumar Google Research
vemnathk@@google.com
Dhecraj Nagaraj Google Research
dheeruhhaggrrojlgggggg.cmm
Reviewed on OpenReview: https: // openreview. net/ per/form?? id= od=01120
Abstract
In reinforcement lcarning (RL), experience replay-based sampling techniques crucial in promoting convergence by eliminating spurious correlations. However, widely used methods such as uniform experience replay (UER) and prioritized experience replay (PER) have been shown to have sub-optimal convergence and high seed sensitivity, respectively. To address these issues, we propose a novel approach called Introspective Experience Replay (IER) that selectively samples batches of data points prior to surprising events. Our method inspired from the reverse experience replay (RER) technique, which has been shown to reduce bias in the output of Q-lcarning-type algorithms with linear function approximation. However, RER is not always practically reliable when using neural function approxination. Through empirical evaluations, we demonstrate that IER with neural function approximation yields reliable and superior performance compared to UER, PER, and hindsight experience replay (HER) across most tasks.
1 Introduction
Reinforcement learning (RL) involves learning with dependent data derived from trajectories of Markov processes. In this setting, the iterations of descent algorithms (like SGD) designed for i.i.d. data co-evolve with the trajectory at hand, leading to poor convergence' 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 Therefore, experience replay is usually deployed with popular algorithms like DQN, DDPG, and TD3 to achieve state-of-tho-an performance (Mnih al., 2013; Lillicrap al., 2015). It has been shown experimentally (Mnih al., 2015) and theoretically (Nagaraj al., 2020) that these learning algorithms for Markovian data show sub-par performance without experience replay.
The simplest and most widely used experience replay method is the uniform experience replay (UER), where the data points stored in the buffer are 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 prioritization" and introduced in 'Schaul et al. (2015)) was shown to have a high bias?. This leads to the a algorithm predominantly selecting rare data points and ignoring the rest, which are necessary to learn how to
The term here used from the lens of empirical study, where the learning curves do improve with further training, and the model said have converged.
We the 'bias" here used Schaul al. (2015), which means biased with respect the empirical distribution over the replay buffer

---

Published in Transactions on Machine Learning Research (01/2024)
reach the high reward states. Prioritized experience replay proposed to solve this issue (Schaul al., 2015) by using a sophisticated sampling approach. However, as shown in our experiments outside of the Atari environments, PER still suffers from a similar problem, and its performance can be highly sensitive to seed and typer-parameter The design of experience replay continues to be an active field of research. Several other experience replay techniques like Hindsight experience replay (HER) (Andrychowicz 2017), Reverse Experience Replay (RER) (Rotinov, 2019), and Topological Experience Replay (TER) (Hong et al., 2022) have been proposed. An overview of these methods is discussed in Section
al.,
Even though these methods widely deployed in practice, theoretical analyses have been very limited. Recent results on learning dynamical systems (Kowshik et al., 2021b;a) showed rigorously in a theoretical setting that RER is the sonceptually--groundeed algorithm when learning from Markovian data. Furthermore, this work was extended to the RL setting in Agarwal et al. (2021) to achieve efficient Q learning with linear function approximation. The RER technique achieves good performance 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 their TD error. It then returns batches of data formed by selecting the consccutive 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 This technique is an amalgamation of Reverse Experience Replay (RER) and Optimistic Experience Replay (OER), which only picks the points with the highest TD error.
Pivot
Plvol
Betch
Beich
Pivot
Pivot
Figure 1: An illustration of our proposed methodology when selecting k batches in the CartPole environment. The red color is used lo indicate the batches being sampled from the replay bulfer. The green samples are the un-sampled states from the buffer. The arrow explicitly points the pivots and the snapshot the surprising state encountered.
Our main findings are summarized below:
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).
Better Performance Against SOTA:
Conceptual Understanding: We consider simple toy examples understand the differences between UER, RER, OER and IER (Section 3.2, Section 4). This study justifies our algorithm design by showing a. why naive importance sampling, like in OER suffers from poor performance, often failing to learn any non-trivial policy and b) why techniques like UER and RER are slow to learn.
Forward vs. Reverse: We show that the temporal direction (forward/rever) /reeeeee) to consider after picking the pivot is non-trivial. We show empirically that. IER performs much better than its forward counterpart, IER (F) (see Figure 13). This gives evidence that causality plays a role in the success of IER.
Whole vs. Component Parts: Our method (IER) is obtained by combining RER. (which picks the samples in the reverse order received) and OFR (which greedily picks the samples with the largest. TD
2

---

Published in Transactions on Machine Learning Research (01/2024)
error). However, neither of these components perform well compared to their amalgamation, IER (see Figure 9).
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 on UER. However, we introduce two hyperparameters: a Hindsight flag, and the Uniform Mixing Fraction p. When the Hindsight parameter is set, then our samples combines with the HER, sampler leading to H-IER. The parameter is the fraction of batches picked as per UER instead of IER in given buffer (i.e, it allows mixing with UER, giving us U-IER). Note that most of our experiments use p 0.
Minimal hyperparameter tuning:
Table 1: IER performance in comparison to previous state-of-the-art baselines. These baselines inchude 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 11 different environments that cover a broad category of MDPs. These include a few Atari environments (previously used to support the efficacy of UER, PER), and many other classes of enviromments, 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
0
10
2 Related Works and Comparison
2.1 Experience Replay Techniques
Experience replay involves storing consecutive temporally dependent data in a (large) buffer in a FIFO order. Whenever a learning algorithm queries for batched data, the experience replay algorithm returns a sub-sample from this buffer such that this data does not hinder the learning algorithms due spurious correlations. The most basic form of experience replay is UER (Lin, 1992) which samples the data in the replay buffer uniformly at random. This approach has significantly improved the performance of off-policy RL. 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 a probability distribution which assigns higher probability to experiences with significant TD error and is shown to boost the convergence speed of the algorithm. This outperforms UER in most Atari environments. HER (Andrychowiez
al., 2017) works in the "what if' scenario, where even bad 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 a 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 can become highly selective to the point of completely ignoring certain data points, leading to poor performance. This is mitigated by sophisticated sampling procedure employed in PER. The theoretical analyses for these standard techniques have been explored but are limited (Szlak & Shamir, 2021).
2.2 Reverse Sweep Techniques
Reverse sweep or backward value itcration refers to methods that process the data as received in reverse order (see Section 4 for a justification of these methods). This has been studied in the context of planning tabular MDPs where transition probabilites are known (Dai & Hansen, 2007; Grzeš & Hoey, 2013) or have access to a simulator or fitted generative model (Florensa et al., 2017; Moore & Atkeson, 1993; Goyal et al., 2018; Schroecker et al., 2019). However, our work only seeks on-policy access to the MDP.
RER has been shown to work earlier Agarwal et al. (2021) in tabular settings where the state space is significantly small. However, RER has not been shown to scale to sottings with neural approximation Rotinov (2019) where most environments have very large state spaces. Therefore, the iterations of RER are 'mixed' with U.R. However, the experiments are limited and do not demonstrate that this method outperforms
3

---

// Randonly choose B indices from buffer Published in Transactions on Machine Learning Research (01/2024)
even UER. A similar procedure named Episodic Backward Update (EBU) is introduced in Lee et al. (2019). However, to ensure that the pure RER works well, the EBU method also seeks to change the target for Q learning instead of just changing the sampling scheme in the replay buffer. The reverse sweep was rediscovered as RER the context of streaming linear system identification in Kowshik et al. (2021b), where SGD with reverse experience replay was shown to achieve near-oplimal performance. In contrast, naive SGD was significantly sub-optimal due to the coupling between the Markovian data and the SGD itcrates. The follow-up work Agarwal 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.
3 Background and Proposed Methodology
We consider episodic reinforcement learning (Sutton & Barto, 2018), where at each time step an agent takes actions de in an uncertain enviromment with state 8t, and receives reward (8)))))). The enviromment then evolves into a new state $++1 whose law depends only on (st, at), Our goal is to (approximately) find the policy x² which maps the environmental state 8 to an action a such that when the agent takes the action ar = =+* (s;), the discounted reward I 1_ 7'rs] is maximized. To achieve this, we consider algorithms like DQN (Mnih et al. (2015)), and TD3 (Fujimoto et al. (2018)), which routinely use experience replay buffers. In this paper, we introduce new experience replay method, IER, and investigate the performance of the aforementioned RL algorithms with this modification. In this work, when say "return", mcan discounted episodic reward.
Algorithm 1: Our proposed Introspective Experience Replay (IER) for Reinforcement Learning
Input: Data collection mechanism T, Data buffer H. Batch size B, grad steps per Epoch G, number of episodes N, Importance function 7, learning procedure A, Uniform Mixing fraction p
4 while N do
n+1 H - T(H)
// Add new episode to the buffer // Compute importance of each data point in the buffer // Obtain index of top G elementa of I
I + I(H)
P + G)
g 0
while g < G do if g < G then D + H[P[g] - P[g]
// Load batch of previous examples from pivot P[g]
clsc
D + H[UnniormmH,, B)]
end
+ 9-1 (D)
// Run the learning algorithm with batch data D
end
end
3.1 Methodology
We now describe our main method in a general way where we assume that we have access to a data collection mechanism T which samples new data points. This then appends the sampled data points to a buffer H and discards some older data points. The goal to run an iterative learning algorithm A, which learns from batched data of batch size B in every iteration. We also consider an important metric associated with the problem. At each step, the data collection mechanism T collects episode and appends it to
4

---

Published in Transactions on Machine Learning Research (01/2024)
<- the buffer H. and discards some old data points, giving us the new buffer + T(H). We then sort the
entries of H based on the importance metric T and store the indices of the top G data points in an array P = [P[O]..... : PIG - I]]- Then for every index (i) in P, we run the learning algorithm A with the batch D = (H((P))).....
H[[p[]] - B + 1)). In some cases, we can 'mix'3 this with the standard UER sampling mechanism to reduce bias of the stochastic gradients with respect to the empirical distribution in the bufler, as shown below. Our experiments show that this amalgamation helps convergence in certain cases. 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 total of 1E6 data points, usually. We choose A to be an RL algorithm like TD3 or DQN. The importance function / is the magnitude of the TD error with respect to the current Q- estimate provided by the algorithm A (i.e. I = (Q(s. - R(s, a) - 7 o Qtarget (s',a))) When the data collection mechanism (T) is the same as UER, we will call this method IER. In optimistic experience replay (OER), we take T to be the same as in UER. However, we query top BG data points from the buffer HH and return G disjoint batches each of size B from these 'important" points. It 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.
3.2 Didactic Toy Example
In this section, we discuss the working of IER on a simple environment such as GridWorld-1D, and compare this with some of our basclines such as UER, OER, RER, and IER (F). In this environment, the agent lives on a discrete 1-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 is also a trap state (T; [3]), where the agents gets a reward of 22 The reward in every other state is O. For simplicity, we execute an offline exploratory policy where the agent moves left or right with probability of half and obtain a buffer of size 30000. The rewarding states occur very rarely in the buffer since it is hard to reach for this exploration policy. The episode ends upon meeting either of two conditions: the gool state, or (ii) the agent has exhausted the max-timestep condition and has not succeeded in reaching any terminal state. An overview of our toy environment is depicted in Figure 2(a). Other hyperparamoters crucial to replicating this experiment are described in Appendix B.
(i) the agent reaches the terminal state, which is
In this example, reaching the goal state as quickly 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 limes each state occurs in the bulfer. Furthermore, the remaining subplots of Figure 2 depict the Absolute Frequency of our off-policy algorithm trained in this environment. A state's "absolute frequency" 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 a 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 to the start state. We refer to the bottleneck in Figure 2(e) where some intermediate states are not sampled.
Advantage of IER: IER prioritizes sampling from the goal state and propagates the reward backward that the entire path leading to the reward is now aware of how to reach the reward. Therefore, combination
Mixing here denotes sampling with a given probability from one sampler A, and filling the remaining samples of batch with sampler
5

---

Published in Transactions on Machine Learning Research (01/2024)
of RER and OER, reduces the sampling bias in OER by preventing the bottlenecks seen in Figure 2(e). Bottleneck of IER (F): TER (F) has a more significant bottleneck when compared to RER and chooses to sample the non-rewarding middle states most often. IER (F) picks states in the future of the goal state, which might not contain information about reaching the goal.
This does not allow the algorithm to effectively learn the path which led to the goal state.
State Distribution in Buffer
Absalute Frequency
2030
1903
300
1299
200
790
599
100
(a) GridWorld-1D environment
(b) Buffer
(c) UER
Absalute Frequency
Absolute Frequency
Absolute Frequency
Absolute Frequency
400
400
400
400
350
300
200
200
200
200
150
100
100
(d) RER
(e) OER
(f) IER.
(8) IER (F)
Figure 2: Gridworld-1D environment is depicted in Figure 2(a). Distribution of states in the buffer (Figure 2(b)) and relative frequency of different experience replay samplers on the didactic example of GridWorld-1D enviromment (Figure 2(1)
The loy example above models several salient features 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.
(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").
4 Understanding Reverse Replay
This section highlights some conceptual motivations behind RER and IER. Works such as Agarwal et al. (2021); Kowshik et al. (2021b) have established rigorous theoretical guarantees for RER by utilizing super martingale structures. This structure is not present in forward replay techniques (i.e. the opposite of reverse replay) as shown in Kowshik et al. (2021a). We refer to Appendix D, where we show via an ablation study that going forward in time instead of reverse does not work very well. We give the following explanation ions for the success of IER, but note that further theoretical investigation is needed.
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
6

---

Published in Transactions on Machine Learning Research (01/2024)
Nerrakedd T0 Rror
Somatan K01
(a) UER
(b) RER
(c) IER
Figure 3: Relationship between absolute values of TD Error (Surprise factor) and Reward for the Ant environment.
further details) shows that in many environments IER picks pivots which are the states with large (positive negative) rewards, enabling effective learning.
More spread than OER: OER, which greedily chooses the examples with the largest TD error learn from, performs very poorly since it is overtly selective to the point of ignoring most of the states. To illustrate this phenomenon, we refer to the didactic example in Section 3.2. One possible way of viewing IER is that RER is used to reduce this affinity to picking a minimal subset of states OER. PER designed to achieve a similar outcome with a sophisticated and computationally expensive sampling scheme over the buffer. Causality: MDPs have a natural causal structure: actions and events the past influence the events the future. Therefore, whenever we see surprising or unexpected event, we can understand why how it happened by looking into the past.
We further illustrate the same by referring to the straightforward didactic example (Section 3.2), where we can see 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.
4.1 Results on Chain Environment
In this section, we discuss the working of IER on two simple Markov chain environments as proposed by Zhang& Yao (2019), where the environments were used for illustrating the inefficiency of mean-based decision-making. Similar to the didactic toy example (Section 3.2), we compare some our baselines, such as UER, OER, and RER to further show the efficacy and robustness of our proposed approach. Our setup of the environment is identical to the setup proposed in Figure of Zhang & Yao (2019) paper. Briefly, we experiment on two Markov Chain problems described below:
Chain 1 is a system with N non-terminal states and two available actions, UP and RIGHT. At the beginning of each episode, the agent starts at state 1. The UP action results in an immediate end to the episode with no reward, while the RIGHT action leads the next state with a reward sampled from a normal distribution with mcan of 0 and standard deviation of 1. When the agent reaches the terminal state G, the episode ends with reward of +10, and there no discounting. The optimal policy for this system is always moving right, but to learn this policy, the agent must first reach the G state. However, this is challenging for Q-learning because of two factors: the epsilon-greedy mechanism may randomly select UP, ending the episode, and before reaching G, the expected return of either RIGHT or UP at any state is O, making it impossible for the agent to differentiate between the two actions based on the mean criterion.
Chain 2 has the same state and action space as Chain 1, but the reward for RIGHT is now -0.1, except for reaching the G state, which gives reward of +10. The reward for UP sampled from normal distribution with mean of 0 and standard deviation of 0.2. There is discounting. When the standard deviation
7

---

Published in Transactions on Machine Learning Research (01/2024)
12
22
T2
7'2
Start
Goal
r1
T1
T1
T1
+10
Figure 4: An illustration the chain environment used in our below experiments. Markov chain 1, we set r1 NN 1), and r2 O. In Markov chain 2, we set r1 -0.1, and r2 (.2...2).
is small, the optimal policy remains moving right. However, before reaching the G state, the expected return of RIGHT for any non-terminal state is less than O, which mcans a Q-lcarming agent would prefer UP. This preference detrimental to Chain 2 as leads to an immediate episode ending, preventing further exploration.
Furthermore, make the problem harder (in comparison the works Zhang & Yao (2019)), we have increased the number of non-terminal stales (N) to 10. We train the agent with warmup of 1000 steps to populate the replay buffer similar to the setup in Section 3.2. Additional hyperparameters used for our agent are described in Table 5. We report the number of epochs required to reach the optimal policy averaged over 50 different seeds, with a maximum training epoch limit of 100. The lower the number of epochs taken for convergence, the better. As presented in the Table 2, our approach of utilizing IER outperforms other methods by effectively capturing the idea trap states and demonstrates superior learning capabilities.
Table 2: Number of epochs required to reach the optimal policy averaged over 50 different scods. From our experiments, we note that IER outperforms previous SOTA baselines both environments. The lower the number of epochs taken for convergence, the better.
Enviromment
UER
HER
RER
OER
IER
IER-F
Marhow Chain
49.52 a 1400 62:22 n
45.72 ma
7.36 1ar
4.22 1.
8.64 : 1.4
Markow Chain 2 96.98
98.76
97 06
844
6.72
16.82
5 Experimental Results
In this section, we briefly discuss our experimental setup as well the results of our experiments.
Environments: We evaluate approach diverse class of environments, such as (i) Environments with dinensnnsional state space (including classic control and Box-2D 2D environments). (ii) Multiple joint dynamic simulations environments (including Mujoco 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 et al. (2017), showed the efficacy of their approach on a subset of these classes. For instance, UER and PER was shown to work well on Atari games. Tn this work, we perform an extensive study to show the robustness and effectiveness of our model not just Atari environments but also in Mujoco, Box2D, and Classic Control enviromments. Due to computational limitations and the non-reproducibility of some baselines with UER, could not extend our experiments to some environments. We refer to Appendix A for 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 a standard sotting for all the different experience replay buffers. This classic setting is set so we can reproduce state-of-the-ee performance using UER on the respective environment. For most of our experiments, set the uniform mixing fraction (p) from Algorithm to be O. We use
8

---

Published in Transactions on Machine Learning Research (01/202))
100
30
-00
9xg
(a) CartPole-vO (DQN)
(b) Acrobot-vl (DQN)
(c) LamarLander-v2 (DQN)
4000
0
2003
0
201
7.00
(d) HalfChectah-r2 (TD3)
(c) Ant-v2 (TD3)
(f) Reacher-v2 (TD3)
Antrag heam
2000
1040
1.3
-101
(g) Walker-v2 (TD3)
(h) Hopper-v2 (TD3)
(i) InvertedDouhlaeendduuny (TD3)
500
-12
100
30g
120
(i) Pong-v0 (DQN)
(k) Enduro-v0 (DQN)
Figure 5: Learning curves of DQN/TTI TD3 agents on various environments using the Top-k metric. Here, the shaded area denotes the standard error.
non-zero p value only for a few environments to avoid becoming overtly selective while training, as described in Appendix B. For PER, we tune the a and / hyperparameters used in the Schaul et al. (2015) paper across all environments other than Atari. The default values of = 0.4 and B 0.6 are robust on Atari environments as shown by extensive hyperparameter search by Schaul et al. (2015). We detail the results from our grid search in Appendix C.2.
Metric: The metric for comparison between different algorithms is very important in RL since the learning curves are extremely noisy, seed sensitive and contain many outliers. Thus the empirical mean estimation method (where the empirical average of the return taken across the sceds) might not be able to compare the performance of the algorithms with a reasonable number of samples. To mitigate this drawback, we report our results with respect to two metrics (defined in the paragraphs below): The robust mean (the statistically principled approach) and the top-K seeds moving average return (heavily used in prior works). We demonstrate the robustness of the top-K metric and the robust mean metric from our study in Appendix C.1. Here the task is to infer the best algorithm based on a loy model of highly seed-sensitive learning curves. We show that both these methods allow us to efficiently infer the best algorithm. However, the usual empirical mean chooses the wrong answer almost 50% of the time. The top-K metric has boen criticized in the literature since this can empirically pick relatively sub-optimal algorithms which perform very well on rare seeds (Henderson et al., 2018). Thus, while we primarily consider the robust mean metric to compare the
9

---

Published in Transactions on Machine Learning Research (01/2024)
algorithms, we also report the top-K metric in order to facilitate comparison with prior works. We now describe the metrics used in detail below.
Robust Mean Metric: Practical data is known to suffer from heavy tailed phenomenon and outliers and thus estimating their means with the empirical mean estimator can be very sub-optimal. Thus, robust estimation has been widely studied in statistics, going back to the works of Huber (1964) and Tukey (1975). We refer to Lugosi & Mendelson (2019) for a detailed literature review on this topic. Thus we consider the median of means estimator (see refs in Lugosi & Mendelson (2019)) as the robust estimator for the mean. We consider = 25 seeds for each enviromment and each algorithm (n = 10 for the Atari environments due to resource constraints) and plot the moving average with a window size of 20 for CartPole and 50 for all others. We divide the moving average reward into 5 buckets of equal size and compute the mean inside each bucket. We then output the median across of these means. We construct the standard error of this estimator using the popular bootstrap method Efron & Tibshirani (1994).
The Top-K Seeds Metric: is common to use Top-1 and Top-K trials to be selected from among many trials in the reinforcement learning literature (see Schaul et al. (2015):Sarmad et al. (2019); et al. (2n17):Mnih et al. (2016)). In our work, 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 k = 10 seeds that gave the best performance out of a total of n = 25 trials. This measures the average performance of the top k/n quantile of the trajectories. This is robust despite the highly stochastic learning curves encountered in RI., where there is a non-zero probability that non-trivial policies are not learned after many steps. Moving average with a given window size is taken for learning curves (with a window size of 20 for CartPole 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 a 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.
Comparison with SOTA: Figure 5 and Figure 6 depicts our results in various environments upon using different SOTA replay sampler mechanisms (UER, PER and HER) on the Top-k and Robust Mean metric. Our proposed sampler outperforms all other baselines in most lasks and compares favorably in others. Our experiments on various environments across various classes, such as classic control, and Atari, amongst many others, show that our proposed methodology consistently outperforms all other basclines in most environments. Furthermore, our proposed methodology is robust across varions environments. (See Table 3) Forward vs. Reverse: The intuitive limitation to the "looking forward" approach is that in many RT. problems, the objective for the agent is to 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 lend to 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) picks states in the future of the goal state, which might not contain information about reaching the goal. Our studies on many enviromments (see Figure& 3 and Appendix E) show that the pivot points selected based on importance indeed have large (positive or negative) rewards.
Whole vs. Component Parts: Our approach is an amalgamation of OER and RER. Here we compare these individual parts with IER. Figure 9 describes the Top-K seeds Moving Average Return across various environments in this domain. As demonstrated, IER outperforms its component parts OER and RER. Furthermore, we also motivate each of our design choices such as the pivot point selection (sce Appendix C.5 where we compare our proposed approach with other variants of IER where the pivot points are randomly selected), and temporal structure (see Appendix C.6 where we compare our proposed approach with other variants of IER where the points are randomly sampled from the buffer instead of temporally looking backward after selecting a pivot point), and also buffer batch size sensitivity (see Appendix C.4).
6 Discussion
We sunmarize our results and discuss possible future steps. Speedup: IER shows a significant speedup in terms of time complexity over PER as depicted in Table 4. On average IER achieves a speedup improvement of 26.20% over PER across a large umbrella of environment classes. As the network becomes more extensive or complicated, our approach does have a higher overhead (especially computing TD error). Future work can investigate how to further reduce the computational
10

---

Published in Transactions on Machine Learning Research (01/2024)
Table 3: Average reward (via robust mean estimation) across various environments along with the standard error (computed via bootstrap). From our experiments, 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
170.98 a00
177.55 10:3
170. 16 6.
199.19 0.55
Acrobot
-347.31 = ta
-339.08 1..
-328.36 : mo
-256.62 20
LamarLander
1.62 1ox
-0.34 am
5.45
11.16 9-74
HalfCheetah
1047.669 19
404.09 245
10984.45 133.00
10179.05
114
Ant
3576.19 231
-2700.74 + n.3
3688.03 as
3697.42
2000
Reacher
-5.11 u.u
-5.58 2.43
-5.12
-5.09
Walker
4/00.33 Lokis0
1120.02 + u55.77
4/52..5 131.8
4705.08
196.41
Hopper
2886.62 106.07
11.14
100.33
2820.
041.27
3221.48
41.51
Inverted Double Pendulum
6876. = 917.11
7822.22
a: 002.04
7118.51
1806.44
7916.32
2 177.53
Pong
17.47 = 0.50
17.67 200
18.17 0.
18.44 2:37
Enduro
345.36 72.66
381.45 a 71.30
421.52 30.53
465.94
25.00
complexity of our method by computing the TD error fewer times at the cost of operating with an older TD error. We also notice a speedup of convergence toward a local-optimal policy of our proposed approach, as shown in a few environments. Furthermore, the lack of speedup some of the other experiments (even if they offer an overall performance improvement) could be since the 'surprised" pivot cannot be successfully utilized to teach the agent rapidly in the initial stages.
Issues with stability and consistency. Picking pivol points by looking at the TD error might cause us to sample rare events much more often and hence cause instability compared to UER as seen in some environments like HalfCheetah, LunarLander, and Ant, where there is a sudden drop in performance for some episodes (sce Figure 5, and Figure 6). We observe that our strategy IER corrects itself quickly, unlike RER, which cannot do this (see Figure 9h))). Increasing the number of pivol points per episode (the parameter G) and the uniform mixing probability p usually mitigates this. In this work, we do not focus on studying the exact effects of and G 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 4: Average Specdup terms of time complexity over PER across various environment classes.
Environment
Average Speedup
Classic Control
32.66%
Box-2D
54.32% f
Mujoco
18.09%
Atari
6.53% f
Why does IER outperform the traditional RER? The instability and unreliability 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 lincar approximation settings (Agarwal et al., 2021). Two explanations of this are i) The work on RER (Agarwal et al., 2021) considers the linear function approximation setting, where SGD type algorithms with i.i.d. have a bias-variance decomposition Jain et al. (2018): the distance from the initial point contracts exponentially in time (the bias term) and a remainder zero mean term (the variance term). With data from a Markov chain, the variance term can have non-zero mean in the Q learning setting. This problem is mitigated by the RER technique which makes sure the variance term is of zero mean, leading to fast convergence. In the case of non-conver loss functions, such as the square loss over a neural network, such bias variance decomposition cannot be achieved. Thus, we believe RER does not work well with non-convex loss functions and ii) The proof given in Agarwal et al. (2021) relics extensively on 'coverage' of the entire state-action space - that is, the entire stale-action space is visited enough number of times which might not hold, as shown in Section 3.2.
f.e., sudden drop in performance without recovery like catastrophic forgetting
11

---

Published in Transactions on Machine Learning Research (01/2024)
(a) CartPole-vO (DQN)
(b) Acrobot-vl (DQN)
(c) LunarLander-v2 (DQN)
1.5
(d) HalfCheetah-v2 (TDD3)
(e) Ant-v2 (TD33
(f) Reacher-v2 (TD3)
(g) Walker-v2 (TD3)
Hopper-v2 (TD3)
DnvertedDoublaPennnaaaa (TD3)
(j) Pong-vO (DQN)
(k) Enduro-vO (DQN)
Figure 6: Learning curves of DQN/TD3 agents on various environments using the Robust Mean metric. Here, the shaded area denotes the standard error computed via bootstrap method.
7 Conclusion
We propose novel experience replay sampler, Introspective Experience Replay (IER), which has significant promise solution for improving the convergence of RL algorithms. We have demonstrated through extensive experiments that IER. outperforms statc-of-the-art techniques such as uniform experience replay, prioritized experience replay, and hindsight experience replay on a wide range of tasks. One of the key strengths of our proposed approach is its ability to selectively sample batches data points prior to surprising events, which allows fast convergence without incurring the issues in methods such as PER and RER. While IER constructed based on the theoretically sound RER, is important note that IER does not necessarily inherit identical theoretical guarantees.
12

---

Published in Transactions on Machine Learning Research (01/2024)
Reproducibility Statement
In this paper, work with thirteen datasets, all of which are open-sourced in gym (https://githal) com/ openai/gym) More information about the environments is available in Appendix A. We predominantly use DQN, DDPG and TD3 algorithms 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 in Appendix B. All runs have been run using the A100-SXM4-40GB, TITAN RTX, and V100 GPUs, Our source code is made available for additional reference 6.
References
Naman Agarwal, Syomantak Chaudhuri, Pratock Jain, Dhocraj Nagaraj, and Pranceth Netrapalli. Online larget q-learning with reverse experience replay: Efficiently finding the optimal policy for linear mdps. arXiv preprint arxix:2100.00 110:::100008440,, 2021.
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojciech 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 Wojeiech Zaremba. Openai gym. arXiv preprint urXiu:1606: 540, 2016.
Peng Dai and Eric A Hansen. Prioritizing bellman backups without a priority queue. In ICAPS, pp. 113-119, 2007.
Bradley Efron and Robert J Tibshirani. An introduction to the bootstrop. CRC press, 1994.
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-guided hindsight experience replay. Advonces 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 on robol 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. PMTR, 2018.
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 preprinl arXi:: 1eee:1804.000 00379, 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 Pineau, Doina Precup, and David Meger. Deep reinforcement learning that matters. In Proceedings of the AAAI conference artificial intelligence, volume 32, 2018.
Zhang-War Wei Hong, Tao Chen, Yen-Chen Lin, Joni Pajarinen, and Pulkit Agrawal. Topological experience replay. arxiv preprint arXiv:2008.15845 2022.
httt:://gttuub..c////lrrrrrrr//e www.-aaaccc----reeeeeeeeeeeeeeee surprised
13

---

Published in Transactions on Machine Learning Research (01/2024)
Peter J Huber. Robust estimation of a location parameter. The Annals of Mathematical Statistics, pp. 73-101, 1964.
Prateek Jain, Sham M Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Parallelizing stochastic gradient descent for least squares regression: mini-batching, averaging, and model misspecification. Journal of machine learning reseorch, 18(223):1-42, 2018.
Suhas Kowshik, Dheeraj Nagaraj, Prateek Jain, and Praneeth Netrapalli. Near-optimal offline and streaming algorithms for learning non-linear dynamical systems. Advances in 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.
Su Young Lee, Choi Sungik, and Sac- YounY Chung. Sample-cfficient deep reinforcement learning via episodic backward update. Advances in Neural Information Processing Systems, 32, 2019.
Timothy P Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv:1509.02) 02971, 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:19022 0002288.000......0 2019.
Gábor Lugosi and Shahar Mendelson. Mean estimation and regression under heavy-tailed ionts::tiion:: A survey. Foundations of Computational Mathematics, 19(5):1145 1190, 2019.
Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXi::1812.5600 2013.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):529-533 2015.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukeuoglu. Asynchronous methods for deep reinforcement learning. In 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-18) 130, 1993.
Dheeraj Nagaraj, Xian Wu, Guy Bresler, Prateek Jain, and Praneeth Netrapalli. Least squares regression with markovian data: Fundamental limits and algorithms. Advances in neural information processing systems, 33:16666-16676, 2020.
Egor Rotinov. Reverse experience replay. Xrxiv preprint arXio: vrrXio:1910.00 1910.08780, 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 Computer Vision and Pattern Recognition, pp. 5898-5907, 2019.
Tom Schaul, John Quan, loannis Antonoglou, and David Silver. Prioritized experience replay. arXiv preprint arXiv:1511.05052 2015.
Yannick Schroecker, Mel Vocerik, and Jonathan Scholz. Generative predecessor models for sample-officient imitation learning. Xiv preprint ar Xiv: 1rXiv:1904.00 1904.01 1 139, 2019.
14

---

Published in Transactions on Machine Learning Research (01/2024)
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High-dimensional continuous control using generalized advantage estimation. orXiv preprint or 150::11:000000. 606602438, 2015.
Richard S Sutton. Generalization in reinforcement learning: Successful examples using sparse coarse coding.
Advances in neural information processing systems, 8, 1995.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Liran Szlak and Ohad Shamir. Convergence results for q-learning with experience replay. arXiv preprint arXiv:2112.04211 2021.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: physics engine for model-based control. In 2012 IEEE/RSJ international conference on intelligent robots and systems, pp. 5026 5033. IEEE, 2012.
John W Tukey. Mathematios and the picturing of data. In Proceedings of the International Congress of Muthematicians, Vancouver, 1975, volume 2, pp. 523 531, 1975.
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 cennecker-factoree approximation. Advances in neurol information processing systems, 30, 2017.
Shangtong Zhang and Hengshuai Yao. Quota: The quantile option architecture for reinforcement learning. Tn
Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 5797 5804, 2019.
15

---

Published in Transactions on Machine Learning Research (01/2024)
A Environments
For all OpenAl environments, data is summarized from https://github. https////ggggh......//////aaaaaa and more infor- mation is provided in the wiki https://githe: www htt///pnna/gyym/wlkk... Below we briefty describe some of the tasks we experimented on in this paper.
A.1 CartPole-vO
CartPole, as introduced in Barto et al. (1983), is a task of balancing 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 is 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 4-dimensional space describing the environment and respond by returning one of two values, pushing the cart either right or left.
A.2 Acrobot-v1
Acrobot, introduced in Sutton (1995), is 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 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 reward, and the episode length 500 timesteps.
A.3 LunarLander-v2
The LunarLandor environment introduced in Brockman al. (2016) is 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 maximum principle, is optimal to fire the engine at full throttle or 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.
it
A.4 HalfCheetah-v2
HallCheetah 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 the joints to make the chectah run forward (right) as fast as possible, with positive reward allocated based on 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 to the other six joints over the front and back thighs (comnecting to the torso), shins (connecting to the thighs), and feet (connecting to the shins). The reward obtained by the agent is calculated as follows:
= .i - 0.1 +|at
A.5 Ant-v2
Ant is an environment based on the work by Schulman et al. (2015) and adapted by Todorov et al. (2012). The ant is 3D robot with one torso, a free rotational body, and four legs. The task is to coordinate the four legs to move in the forward direction by applying torques on the eight hinges connecting the two links of each log 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 follows:
16

---

Published in Transactions on Machine Learning Research (01/2024)
Tr di. - -0.5 ||aell2 0.0005
|| contacc ++1
A.6 Reacher-v2
The Reacher environment, as introduced in Todorov et al. (2012), is a two-jointed robot arm. The goal is move the robot's end effector (called "fingertip") close 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.7 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 a 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 a 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 three-dimensional element vector. The state space consists of positional values for different body parts followed by the velocity states of individual parts.
A.8 Walker-v2
The Walker environment, as builds on top of the Hopper environment introducod in Todorov et al. (2012), by adding another set of legs making it possible for the robot walker forward instead of hop. The hopper is two-dimensional figure with two legs that consists of four main body part the torso at the top, two thighs in 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 a six-dimensional element vector. The state space consists of positional values for different body parts followed by the velocity states individual parts.
A.9 Inverted P2udul-Pendulum-22
Inverted Double-Pendulum as introduced in Todorov et al. (2012) is built upon the CartPole environment as introduced in Barto et al. (1983), with the infusion of Mujoco. This environment involves a cart that can be moved linearly, with a pole fixed and a second pole on the other end 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 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 one-dimensional contimuou action space in the range [-1,1], denoting the force applied to the cart and the sigu depicting the direction of the force. The state space consists of 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.
A.10 Pong-v0
Pong, also introduced in Mnih et al. (2013), is comparatively more accessible than other Atari games such as Enduro. Pong is a two-dimensional sports game that simulates table tennis. The player controls an in 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 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.
17

---

Published in Transactions on Machine Learning Research (01/2024)
A.11 Enduro-v0
Enduro, introduced in Mnih et al. (2013), is hard environment involving maneuvering race in the National Enduro, long-distance endurance race. The goal of the race is to pass certain nunber of cars each day. The agent must pass 200 cars on the first day and 300 cars 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 lactors 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 patch of fog may reduce visibility.
B Model and Hyperparameters
The hyperperparamelens used for our agents in the Tabular MDP setting with Markov chain environments is shown Table In this paper, we work with two classes of algorithms: DQN and TD3. The hyperparametens used for training our DQN algorithms in various environments are described in Table 6, Furthermore, the hyperparameters used for training TD3 described in Table 7.
Table 5: Hyperparameters used for training Tabular MDP on both Markov chain environments.
Description
Markov chains
argunent_
Discount
aiounttt
Batch size
batch pize
Number of epocls
100
n_epochs
Replay Bufler size
buffer size
Buller batch
batch,
Exploration factor
0.3
max_opsil lon
Learning rale
ir 0.1
Table Hyperparameters used for training DQN on various environments.
Description
Cari
Acrobot
LunarLander
Pong
Enduro
Genera Settinge
Discount
0.9
0.9
03.9
0.98
0.90
di diacount
512
batch aiza
Number of epochs
100
100
200
150
800
a_opochs
Suepe per epochs
etepe_per carpp_per__ppttee spoce
Number of train sleps
500
500
500
125
125
nux, train_ _ttepe
Turget update frequency
30
frrquency
Replay Buffer size
1ed
buffer _izeerr_ee
Algorsthm Settings
ONN Policy Channes
(32, 64)
(32, 64)
ean_chanzel
CNN Polley Kernels
(8.4,3)
(8,4,3)
can, kernel
Palic Strides
(4.2.1)
(4.2.
can,
Policy hidden sizes (MLP)
(8.5)
(8,5)
(8,5)
(512.)
(512.)
pol_bidden,
wwwdbhiddddeeeeee pizee
Buller size
64
batrcheiize
Bigiloation Seltings
upeilon
max_epeilon
Min epellon
0.01
0.1
0.1
0.01
0.01
nin, nin_epat eppllannno
rarão
0.4
0.4
0.12
0.1
0.1
decay ratio
Optimizer Settings
Learning rate
Sem+
5e
5e-8
16-4
Te-4
PER Specifie Settings
Pricritiaatonn Exponent
0.4
0.6
0.8
0.4
0.4
Annesling Parameter
0.6
IER Spocific Scttliga
Hindsight storing Miving, Pactor (p)
use hindsight
Additionally, we use Tabular MDPs for learning a policy our toy example. Since the environment is fairly simpler, and has very few states, function approximation is unnecessary. For all the agents trained on GridWorld, we use a common setting described in Table 8.
18

---

Published in Transactions on Machine Learning Research (01/2024)
Table 7: Hyperparameters used for training TD3 on various environments.
Description
Ant
Reacher
Walker
Doublo-Pendulun
HallCheetah
Hopper
argunent
General Settings
Disrount
0.99
0.99
0.99
0.901
diacount
Batch size
250
250
250
100
100
100
batch_eis
Number epochs
500
500
750
I_ apocce
Stepe per epochs
40
40
40
40
20
40
stegs per__prr____ eppch num, train_ataatte atapa
Number train steps
50
50
Replay Buller sioe
lef
1e
16
1ea
1
16
buffer_siie
Algorithon Settings
Policy hidden sizes (MLPP)
(256,
[256, 256)
(206,
(2066, 256)
(256, 216)
(256, 256)
pol w__hhidddnddd aizs
Policy noise clip
0.5
0.55
0.5
0.5
0.5
0.5
pol_noise__ clip
Policy noise
0.2
0.2
pol. poice tau batch batch_aiza ai2a
Target update tam
0,005
0.005
0.005
0.005
0.005
0.005
Beffer
100
100
100
100
100
Goussien noiar Expioration Settings
Max signa
0.1
0.1
0.1
0.1
0.1
0.1
_ sigas hin_sigaa
Min sigma
0.1
0.1
Optänularr Settings
Policy Learaing rate
1e
1e
Se
1e
3e
pol, 1r gf. 1r
QF Learning rate
le
le
le 8
le
PER Spocific Settinga
Priorisization Exponent
0.4
0.4
Bias Annealing Parameter
0.6
0.6
0.6
0.6
0.6
0.2
Spocific Settings
Use Hindsight. for storing states
hin_hindddppp ght
Mixing Factor (p)
0.4
0.3
0.8
Table 8: Hyperparametors used for training Tabular MDP on GridWorld-1D environment.
Description
GridWorld
argument__nae _ame
Discount
0.99
discount
Batch size
1
batch_size
Number of epochs
100
n_ opopshs
Replay Butfer size
3c4
buffer_aie _ize
Buffer batch
batch_size
Exploration factor
0.3
max_epsilon
Learning rate
0.1
1r
C Additional Results
C.1 Analysis of Fault Tolerance in Reinforcement Learning
Selecting an appropriate metric for comparison in RL is crucial due to the high variance in results attributed to the environment stochasticity and the stochasticity in the learning process. As such, using the average performance metric with small number of seeds can give statistically different distributions in results. This has been highlighted by the works of Henderson et al. (2018). Reliable reinforcement learning still remains an open problem. As such, using the average over all seeds might not give us a stable comparison of the algorithms considcred, unless we can increase our number of sceds to large numbers such as > 100. This is computationally very expensive and such high number of trials are seldom used in practice. Instead, other approaches use the maximum of N runs to report performance. This however is not ideal since it overestimates your performance by a large amount. We can see this with the PER hyper-parameter search where we deploy the best performing typer-parameter from the hyper-parameter grid search into an independent experiment with Top-K out of n metric. We notice that this under-perfone the grid search result. by a large margin. Thus, the top-1 1 metric is not desirable.
Instead, we propose the use of the Top-K performance metric, and the Robust Mean performance metric which we show below to be robust to noise and is closer to providing the right analysis in comparison to
19

---

Published in Transactions on Machine Learning Research (01/2024)
average metric approach. Similar work such Mnih et al. (2016) which used top-5/50 experiments, we use top-10/25 experiments to limit the overestimation of results further.
To explain our decision choice of Top-K metric and Robust Mean metrie, we consider a fault-based model for RL algorithm output and show via a simulation of this in a simple toy example why Top-K seeds or Robust Mean metric can give us a better way of inferring the best algorithm than the average, especially when the number of independent trials is low. RL algorithms usually perform well sometimes, and some other times they fail badly. This has been noted in the literature Henderson al. (2018) and can also be seen in our experiments. Since the deviations mean + gaussian noisc. To give better understanding, let us claborate with simplified scenario: Consider the following setting where we have 20 different enviromments. There are two algorithms: A and B. Algorithm A gives a moving average return of 0.9 50% of the time and a moving average return of 0 the remaining times (on all environments). Algorithm B, on the other hand, gives a moving average return of 50% of the time and a moving average return of the remaining times (on all 20 environments). In reality, Algorithm B performs better than Algorithm A in all 20 enviromments. We can conclude this with the empirical average if extend the number of experiments very large mumbers, such as 50 seeds per environment or larger. We further extend our above analysis by adding another Algorithm C that gives a moving average return of 0.8 50% of the time and moving average return of 0 the remaining times (on all 20 environments).
so large between seeds, this can be modeled
'fault' rather than
In this simplified model, we test how well the Top-K or Robust Mean metric and the average metric perform in recovering the ground truth (i.e, Algorithm B) via Monte- Carlo simulation with 500 trials. In each trial, we generate the return of each algorithm over each of the 20 environments from the model described above check the best algorithm with the average metric
with 25 different random seeds. For each environment, and the best algorithm with the Top-K metric and Robust Mean metric respectively. We compare this with the ground truth (i.e, algorithm B being the best in all 20 environments). Figure 7(a) depicts the comparison between the average metric, Top-K metric, and Robust Mean metric with respect to the ground truth. As illustrated, the Top-K metric, and Robust Mcan metric is more robust to faults and closer to the ground truth than the other metrics. We further add gaussian noise of mean 0, and standard deviation 0.2, keeping all other parameters constant. This noise added fault runs and standard ones. We note little difference in our results and depict the results averaged over 500 runs depicted in Figure 7(b) Therefore, our model suggests that the Top-K metric, and Robust Mean metric is more robust to faulty runs and can help facilitate the comparison of various learning algorithms with high volatility.
20
Proquron
Poqqanyy
10
Average
Top-k
Robnet
Ground Trath
Aserage
Top-k Mean Thuth
Algorithm
Algorithm B
Algunthi C
Alguriam A Algorithm B Algorithm C
(a) Without Gaussian Noise
(b) With Gaussian Noise (1r 0.2)
Figure 7: Analysis of Fault Tolerance Metrics.
C.2 Grid-Search for tuning PER hyperparameters
In this section we present the results from our grid search experiment for tuning the hyperparameters for PER. We tune the bias annealing parameter (3), and the prioritization exponent (a). We perform a robust. grid search across all environments we have experimented with with the range of the priortization exponent and beta J0.2, 0.4, 0.6, 0.8, 1.0). Figure 8 illustrates the performance of PER with varying hyperparameter
We briefly summarize the findings from grid-search experiment below:
20

---

Published in Transactions on Machine Learning Research (01/2024)
On environments such as CartPole, Reacher, we notice only marginal differences between default hyper parameters (a 0.4, 3 = 0.6) and the best hyper parameters tuned for the model.
For other environments such HalfCheetah, Aut, FetchReach, and Walker, notice significant gap between the performance of PER and IER even after a thorough tuning of PER hyperparameters. For instance, perforss PER by more that 8000 in lerms of average return on HallCheetah environment. Furthemore, IER. outperforms PER by almost 48 in terms of average return on FetchReach. Finally, IER outperforms PER by more than 6200 in terms of average return on Ant. On Walker, IER outperforms PER by almost 1500 in terms of average return. For these environments, we report the results with the default setting, L.e. a 0.4 and B = 0.6.
Some environments such as Acrobot, Pendulum, LunarLander, Hopper, and Nouble-Inverteds Pendulum did show significant improvements when tuned for the prioritization exponent, and bias annealing factor. We take the best hyperparametens from the grid-search experiment, and re-run the code to compute Top-K metrics (i.e, we pick top 10 out of 25 runs). However, from our experiments, we show that even the select hyperparameter is not robust across seeds, and overall performs worse than our proposed approach of IER across all environments: Acrobot, Pendulum, www.--nveerod-eedddlli
LunarLander, Hopper, and
For Atari environments such as Pong and Enduro, we use the default parameters recommended by Schaul et al. (2015), and do not perform a grid-search experiment.
130
130
2.6
2.4402
9.4
2-44
0.4
8.5
-10
0.0.0
-161 1.4 +10.0
1.2
-6.8
6.6
(a) CartPole-vO
(b) Acrobot-vl
(c) LanarTander-v2
200
500
-8.2..
9.
0.2 0.20
-9.2.0.
-0.00.
-0.01
0.6
m0.00.
(d) HalfCheetah-v2
(o) Ant-v2
(f) Reacher-v2
2500
1000
540
-1.2.4
0.8
-.2.0.2 -a ma2 6.6 -a2 -221 0.4
(8) Walker-v2
(h) Hopper-v2
InverteiDDaahhlPeenddmmmm
Figure Grid-Search of Prioritization exponent (a), and Bias Annealing parameter (3) respectively.
C.3 Whole vs. Component Parts
This section briefly presents the learning curves of our models on three different sampling schemes: IER, OER and R.R.R
21

---

Published in Transactions on Machine Learning Research (01/202))
200
300
-30
50
123
(a) CartPole-vo
(b) Acrobot-v1
(c) LunarLander-v2
1000
400
300
100
-13
-000
130
300
430
100
200
120
403
230
203
230
(d) HalfChoctah-v2
(c) Ant-v2
(l) Reacher-v2
3000
2000
5000
2000
1000
300
100
000
-00
(g) Walker-v2
(h) Hopper-v2
(i) InvertedDoublleedndunn-
500
-30
2xp
(i) Pong-vO
(kk Enduro-v0
Figure 9; Ablation study of OER, RER and IER.
C.4 Buffer Batch size sensitivity of IER
This section briefly presents the sensitivity to the buffer batch size hyperparameter for our proposed approach (TER). To analyze this, we run our experiments on the CartPole environment with varying batch size of the range 2-256.
Table and Figure 10 depict the buffer batch size sensitivity results from our proposed sampler.
C.5 How important is sampling pivots?
This section briefly presents the ablation study to analyze the importance of sampling "surprising" states pivots. As a baseline, we build experience replay where these pivots are randomly sampled from the buffer. The 'looking back" approach is used to create batches of data. For nomenclature, we refer to our proposed approach (IER) to use the "TD Metric" sampling of pivots, and the baseline that uses "Uniform" sampling of pivots. Table 10 and Figure 11 depict the buffer batch size sensitivity results from our proposed sampler.
C.6 How important is "looking back"?
This section briefly presents the ablation study to analyze the importance of "looking back" after sampling pivots. As baseline, we build a experience replay where we sample uniformly instead of looking back. For
22

---

Published in Transactions on Machine Learning Research (01/2024)
Table 9: Buffer Batch size sensitivity of IER on the CartPole environment.
Buffer Batch Size Average Reward
126.69 41.42
4
192.33 19.99
8
181.27
16
199.24
32
199.99 1: 0.001
199.83 + 0.31
128
193.23
10.08
256
179.95
18.04
200
Average Return
150
100
Step
20
40
60
80
256
16
128
32
64
Figure 10: Buffer batch size sensitivity of IER sampler the CartPole Environment
Table 10: Importance of sampling pivots our proposed approach (IER) on the CartPole environment.
Sampling Scheme
Average Reward
TD Metrie (IER)
199.83
Uniform (IER)
136.71
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 sampled.
Table 11 and Figure 12 depict the buffer batch size sensitivity results from our proposed sampler.
Table 11: Importance of looking back in our proposed approach (TER) on the CartPole environment.
Filling Scheme
Average Reward
Looking Back (IER)
199.83 2.
Uniform (TER)
182.5 4
23

---

Published in Transactions on Machine Learning Research (01/2024)
200
Average Return
150
100
50
Step
40
Uni forf Sampling
TD Metric Sampl ing
Figure 11: Ablation study of Importance Sampling of IER sampler on the CartPole Environment, Here "Uniform Sampling" denotes the uniformly random sampling of pivots, and "TD Metric Sampling" denotes our proposed approach (IER).
200
Average Return
150
100
Step
80 Uniform Filling Looking Back Filling
20
40
60
Figure 12: Ablation study of Filling Scheme of IER sampler on the CartPole Environment. Here "Uniform Filling" denotes the uniformly random sampling of states to fill after sampling the pivot state, and "Looking Back Filling" denotes our proposed approach (IER).
Ablation study of Temporal effects
This section studics the ablation effects of going temporally forward and backward once we choose a pivol hivo//surprise point. Furthermore, Figure 13 depicts the learning curves the two proposed methodologies. The forward sampling scheme is worse in most environments compared to the reverse sampling scheme.
E
Sparsity and Rewards of Surprising States
E.1 Surprising States Have Large Rewards
this section, we study the "learning from sparse reward" intuition provided in Section - iee. we want check the states corresponding large TD error correspond states with large (positive or 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
24

---

Published in Transactions on Machine Learning Research (01/2024)
200
380
50
43
330
123
(a) CartPole-vO
(b) Acrobot-v1
(c) LunarLander-v2
1000
1000
130
200
300
430
3
200
305
303
400
130
200
130
430
(d) HalfChectah-v2
(c) Ant-v2
(l) Reacher-v2
hdams
2000
1060
290
Foowwrrd
(g) Walker-v2
(h) Hopper-v2
InvertedDoubblleenduunn-
-10
Tomeruol
Beverre
Farword
(j) Pong-v0
(kk Enduro-v0
Figure 13: Ablation study of the effects of the temporal structure on the performance of the agent.
sampled buffers in the Ant environment. We see that high reward states (positive negative) also have higher TD errors. Therefore, our algorithm picks large reward states as endpoints to learn in such environments.
E.2 Surprising States Sparse and Isolated
Figure 14 and Figure 15 depict the distribution of "surprise" /TD error in sampled batch for CartPole and Ant environments respectively. These two figures help show that the states with a large "surprise" factor are few and that even though the pivot of buffer has a large TD error, the rest of the buffer typically does not.
Figure 14(d) and Figure 15(d) show a magnified view of Figure 14(c) and Figure 15(d) where the pivot point selected is dropped. This helps with a uniform comparison with the remaining timesteps within the sampled buffer. Again, we notice little correlation between the timesteps within the sampled buffer.
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 17. Furthermore, an overview of our implemented approach to RER is described briefty in Algorithm 2.
25

---

Published in Transactions on Machine Learning Research (01/2024)
Sparsty Arabyaa aump zuthar Ltn
Anatya sams buthera RBR
(a) UER
(b) RER
(c) IER
Normalue
(d) Magnified
Figure 14: Normalized TD Error ("Surprise factor") of each timestep over three different sampled buffers on the CartPole environment. Best viewed when zoomed.
Algorithm 2:
Reverse Experience Replay
Input: Data collection mechanism T, Data buffer H. Batch size B, grad steps per Epoch G, number of episodes N, learning procedure A.
n < N; P + len(H):
// Set index to last element of Buffer H.
while n N do
1;
H - T(H):
// Add episode to the buffer
+ 0;
while g < G do
if P B then
P - le)
// Set index to last element of Buffer H
else
P P P B:
end
D - H(P B,
// Load batch of previous B samples from index P
+ 1=
A(D);
// Run the learning algorithm with batch data D
end
end
26

---

Published in Transactions on Machine Learning Research (01/2024)
Berralied TD
Sarmaliee
Warmilzed TD
(a) UER
(b) RER
(c) IER
Arahys snnded sutton EX mad
(d) IER Magnified
Figure 15: Normalized TD Error ("Surprise factor") of each timestep over three different sampled buffers on the Ant environment. Best viewed when zoomed.
Temporally
Batch 2
Figure 16: An illustration of Reverse Experience Replay (RER) when selecting & batches from the Replay Buffer.
27

---

Published in Transactions on Machine Learning Research (01/2024)
Pivat
Plvot
Plvot
Pivot
Figure 17: An illustration of Optimistic Experience Replay (RER) when selecting pivots form batch from the Replay Buffer.
28


Reviews:
[{"review_id": "b9BE5jjgAN", "reviewer": "Reviewer_HEA6", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- This paper is well written with clarity and spent a good effort explaining and comparing with baseline methods in the literature. I find it very easy to follow despite that I am not familiar with the research in this field. \n- The proposed method is simple (in a good way), building upon reverse experience replay, and intuitive. The authors did a good job providing the intuition and investigating the benefit of the proposed method by case study in toy domains. \n\nWeaknesses:\n- The proposed method does not seem to outperform baselines by much. It might be desirable for the authors to identify properties of task scenarios that IER is best, while pointing out where IER does not affect the performance by much. e.g. does IER work better for tasks that have bottleneck states? \n- It seems HER was not used in the illustrations for understanding why it is not as good as IER. While HER is not a sampling method, it would still be useful to dig into why it would not perform as well as IER on the illustrative toy task.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a novel method for sampling data in the replay buffer for faster convergence of reinforcement learning algorithms. This paper provide detailed survey of existing methods and leverage simple examples to illustrate the benefit of the proposed method. Experiments in simulated domains also demonstrate the effectiveness of the proposed method and how it compares with baselines.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The authors should take a closer look and proof read the paper. E.g. section 4 first sentence is missing a verb.\n\nIt would be nice for the authors to group task by properties and discuss what kind of tasks would benefit the most from IER.\nMore extensive empirical evidence would be useful for evaluating the real impact of IER, since there isn't any theoretical analysis.", "broader_impact_concerns": "This work presents a technique for improving RL and does not raise any immediate ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ezMZpJpdFc", "reviewer": "Reviewer_iPCH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n* The writing is in general clear.\n* The proposed IER method is simple and easy to understand and implement.\n\nWeaknesses:\n* While IER builds upon the foundations of RER, it remains somewhat unclear how IER benefits from a comparable level of theoretical underpinning.\n* In the abstract, the authors state that IER is introduced to tackle issues related to \"sub-optimal convergence\" and \"high sensitivity to initial conditions.\" Nevertheless, there remains some ambiguity in how IER has specifically and effectively mitigated these two challenges. Furthermore, it's worth noting that the term \"convergence\" is typically employed within a theoretical context, yet the authors seem to apply it to describe empirical performance in this case.\n* The connection between high TD errors and large reward states is not surprising. I didn't quite get the point of highlighting it. Besides, the authors state that \"IER picks pivots which are the states with large (positive or negative) rewards, enabling effective learning.\". Nonetheless, it appears that this outcome isn't a distinctive characteristic of IER but rather an effect of the sampling strategy (focusing on states with high TD errors). It's worth noting that OER also employs a similar strategy.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents an innovative approach called Introspective Experience Replay (IER), which introduces a strategy for experience replay in machine learning. The IER method first selects a set of pivotal samples and then retrieves samples that precede these pivot points to construct a batch of data. Extensive experiments across diverse domains underscore not only the overall effectiveness of this method but also the contributions of its individual components.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* As IER is a combination of OER and RER, it would be better if the authors could include more detailed introductions about those two methods in the main text. For example, it might be a good idea to add figures like Fig.1 for OER and RER.\n* Section 4.1 appears somewhat perplexing. It would be beneficial if the authors could provide further elaboration on the specific intent and significance of this subsection.\n* On page 5, the authors mention that IER(F) might choose samples from the next episode. However, I think it is more of an implementation bug. We can easily restrict it within the same episode. Similarly, IER might also select samples from the previous episode. Please consider fixing it in the ablation experiments.\n* Page 12: how is the variant where the points are randomly sampled implemented? Are the points randomly sampled around pivots or over the entire buffer?\n* Table 4: could the authors give some comments on the reduced time efficacy in MuJoCo?\n* See Weaknesses for other changes.\n\nMinor changes:\n* There is no verb in the first sentence under Section 4.\n* Page 9: \"the task to infer\" -> \"the task is to infer\"", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "FsbOILv9HW", "reviewer": "Reviewer_TQ7y", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n1. The proposed algorithm is easy to follow and clearly presented.\n2. The comprehensive empirical results effectively highlight the resilience and versatility of the Introspective Experience Replay (IER) algorithm.\n3. The paper is well-structured and written, with many details provided to aid readers in understanding the principal contributions.\n\n### Weaknesses\n1. **Technical Issues**. This paper primarily employs a episodic reinforcement learning setting that is grounded in a non-stationary Markov Decision Process (MDP). Consequently, both the policy and the value function should inherently be time-dependent. However, it appears that the algorithmic constructs and notations in Section 3.1 do not align with these stipulated settings.\n\n2. **Lack of theoretical Insights**. The paper appears to underscore that one of the primary limitations of previous works, such as Prioritized Experience Replay (PER), stems from their limited theoretical results. Given that IER is essentially a combination of OER and RER, and both of which have been theoretically examined - it is unclear why a similar analysis for IER would present significant challenges. Considering the authors claims that \"further theoretical investigation is needed\" for IER, I believe this work remains incomplete without the inclusion of such theoretical results. I am assuming the authors possess a robust theoretical background in Reinforcement Learning (RL), particularly in experience replay-based sampling, and I am confident that they can accomplish it.\n\n3. **Concerns over Emprical Findings.** Based on the key findings of this paper (as illustrated in Figure 5), it appears that the training process was not fully completed in several environments. Specifically, the training curves for (b) Acrobot-v1, (g) Walker-v2, and (k) Enduro-v0 are still on an ascending trajectory and have yet to stabilize by the end of the training period. Additionally, I am curious why the Top-k results occasionally underperform compared to the Robust Mean results. This counterintuitive outcome merits further investigation to understand the underlying causes.\n\n4. **Novelty**. After reviewing the RER and OER algorithm, it seems the enhancements made by the proposed IER algorithm are relatively minor, particularly given the absence of theoretical foundation supporting the significance of this update, although my impression could be subjective and incomplete. I leave the decision to AC.\n\nMinor Concerns:\n\nAtari is a big benchmark and this paper only picks two (Pong and Enduro) out of 57 in total environments. I am wondering the reason behind this selection.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents an advanced algorithm known as the Introspective Experience Replay (IER), designed to enhance experience replay-based sampling in Reinforcement Learning (RL). The IER algorithm operates by selectively sampling batches of data points preceding unexpected events. The method identifies the top 'k' pivot points within a data buffer, ranking these points based on their Temporal Difference (TD) error. The algorithm subsequently generates data batches by selecting points that temporally precede these pivot points.\n\nThe findings of this research are primarily conveyed in a pragmatic and intuitive manner. This is achieved through substantial experimentation across various commonly studied RL environments. These encompass traditional control environments, Box-2D environments, Mujoco environments, and Atari environments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I am recommedning fixing the above issues, including:\n1) Rectify the inconsistent notation.\n2) Incorporate theoretical results.\n3) Address the incomplete experiments and thoroughly re-examine the outcomes to ensure accuracy and reliability.\n3) Include more empirical results if possible.", "broader_impact_concerns": "No significant broader impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All three reviewers' recommendation are "Leaning Accept". They had concerns about the novelty, the lack of theoretical guarantees, and whether the method has significantly outperformed the alternatives. These are not serious concerns in my opinion. For example, the paper's novelty is combining two other experience replay methods (Reverse Experience Replay and Optimistic Experience Replay). How novel this combination is can only be subjectively evaluated. Since novelty is not the main criteria for TMLR, I do not put much weight on it.


The authors have improved the paper during the discussion phase. In my own reading of the paper, I found several typos and other minor issues, which I enlist:

- P1: Extra space between footnote superscript 1 and the previous word.
- P1: What is the citation for OER?
- P3: The sentence "Since RER forms mini-batches ... can be unreliable Neural approximation" is not grammatical. Also please explain what is special about NN that prevents RER to be reliable?
- P4, Algorithm 1: What's the purpose of ';' in Algorithm 1? Also they are not adjusted.
- P4, Algorithm 1: "Randomly chose" --> "Randomly choose".
- P5, 1st line: What is index `i' in P[I]?
- P9, last line: The comment that IER (F) might select batches overflowing into the next episode is confusing. This can be avoided by proper data keeping. This is mentioned by one of the reviewers too.
- P10, Figure 5: Are these results for DQN or TD3, or a combination of both?
- P10, Figure 5: There are occasionally big drops in the performance of IER, for example, in (c). Any explanation for that?
- P10-11, Figures 5 and 6: What are the shaded area? Standard error?
- P12: The first paragraph has several typos: "OER not RER", "it's variant", no closing parenthesis.
- P12: No space in "classes.As the"
- P12: The explanation why RER is not working well for neural approximation is that the loss function is highly non-convex and this hinders the working on RER. Why is that? What specific aspect of non-convexity hinders RER? This level of explanation may not be very insightful.


I believe the paper does not need another round of reviewing, but it definitely requires another careful proofreading and some minor revisions. That is why I recommend acceptance with minor revision. I am looking forward to receive the authors' revised paper soon.
Decision: Accept (poster)