Prioritizing Samples in Reinforcement Learning with Reducible Loss
Authors: Shiva Kanth Sujit
Somjit Nath
Pedro Braga
Samira Ebrahimi Kahou
Venue: NeurIPS 2023 poster (2023)
Keywords: reinforcement learning
sample efficiency
experience replay
TL;DR: We propose a prioritization scheme based on the loss reduction potential instead of just the magnitude of the loss

Abstract: Most reinforcement learning algorithms take advantage of an experience replay buffer to repeatedly train on samples the agent has observed in the past. Not all samples carry the same amount of significance and simply assigning equal importance to each of the samples is a naïve strategy. In this paper, we propose a method to prioritize samples based on how much we can learn from a sample. We define the learn-ability of a sample as the steady decrease of the training loss associated with this sample over time. We develop an algorithm to prioritize samples with high learn-ability, while assigning lower priority to those that are hard-to-learn, typically caused by noise or stochasticity. We empirically show that across multiple domains our method is more robust than random sampling and also better than just prioritizing with respect to the training loss, i.e. the temporal difference loss, which is used in prioritized experience replay.

Prioritizing Samples in Reinforcement Learning with Reducible Loss
Shivakanth Sujit
Somjit Nath
Mila, Quebec AI Institute, ÉTS Montréal shivakanth. suj sesjit@gmail.com com
Mila, Quebec AI Institute, ÉTS Montréal somj conjitnath@@mail.. com
Pedro H.M. Braga
Mila, Quebec Al Institute, ÉTS Montréal, Universidade Federal de Pernambuco pedromagalhaes hw@hhabll..........mm....m..mm.m com
Samira Ebrahimi Kahou
Mila, Quebec Al Institute, ÉTS Montréal, CIFAR Al Chair samira. ebrahimi kahou@gmail.com
Abstract
Most reinforcement learning algorithms take advantage an experience replay buffer to repeatedly train samples the agent has observed in the past. Not all samples carry the same amount of significance and simply assigning equal importance to each of the samples is naive strategy. In this paper, we propose a method to prioritize samples based on how much we can learn from a sample. We define the learn-ability of sample loss associated with this sample over time. We develop an algorithm to prioritize samples with high learn-ability, while assigning lower priority to those that are hard-to-learn, typically caused by noise or stochasticity. We empirically show that across multiple domains method is more robust than random sampling and also better than just prioritizing with respect to the training loss, i.c. the temporal difference loss, which is used in prioritized experience replay. The code to reproduce our experiments can be found here
the steady decrease of the training
Introduction
Deep reinforcement learning has shown great promise in recent years, particularly with its ability to solve difficult games such as Go [Silver et al. 2016). chess [Silver et al.. 2018). and Atari [Mmih] et al. 2015). However, online Reinforcement Learning (RL) suffers from sample inefficiency because updates to network parameters take place at every time-step with the data being discarded immediately. One of the landmarks the space of online RI. learning has been Deep Q Networks (DQN) [Mnih] et al. 2015), where the agent learns to achieve human-level performance in Atari 2600 games. A key feature of that algorithm was the use of batched data for online learning. Observed transitions stored in buffer called the experience replay Lin 2004), from which one randomly samples batches of transitions for updating the RL agent.
Instead of randomly sampling from the experience replay, we propose to sample based on the learn- ability of the samples. We consider a sample to learnable if there is potential for reducing the agent's 's loss with respect to that sample. We term the amount by which we can reduce the loss of sample to reducible loss (ReL.).. This different from vanilla prioritization Schaul et al.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

[016] which just assigns high priority to samples with high loss, which can potentially lead to repeated sampling of data points which can not learned from due to noise.
In our paper, we first briefty describe the current methods for prioritization while sampling from the buffer, followed by an intuition for reducible loss in reinforcement learning. We demonstrate the performance of our approach empirically on the DeepMind Control Suite [Tassa et al.) 2018 DI)). OpenAl Gym, MinAtar [Young and Tian 2019] and Arcade Learning Environment [Bellemare et al. 2013) benchmarks. These experiments show how prioritizing based on the reducible loss IS a more
robust approach compared just the loss term (Schaul et al. 2016 used in Hessel al. 2017 and that it can be integrated without adding any additional computational complexity.
2 Background and Related Work
In Reinforcement Learning (RL), an agent is tasked with maximizing the expected total reward it receives from an environment interaction with it. This problem formulated using Markov Decision Process (MDP) [Bellman 1957] that is described by < S, .. R, P >, where S, A, R and P represent the state space, the action space, the reward function, and the transition function of the environment, respectively. The objective of RL. is to learn an optimal policy x², which is mapping from states to actions that maximizes the expected discounted sum of rewards it receives from the environment, that is
π = argmax E
- = s,
where y E [0, 1] is the discount factor. Action value methods obtain policy by learning the action value (Q"(s,, as) )) of a policy which is the expected return by taking action a₂ in state 8ı and then following the policy π to choose further actions. This is done using the Bellman equation, which defines a recursive relationship in terms of the Q value function, as follows
(st, a.) = Te + max Q" ($1+1.4)
The difference between the left and right sides of Eq. 2 is called the temporal difference error (TD error), and Q value methods minimize the TD error of the learned Q function Q" (implemented as a neural network) using stochastic gradient descent. That is, the loss for the Q network is
Lg (Q" a.) (rx + y max ((())11))))
We can then use the Q value to implicitly represent a policy by choosing actions with high Q values. While this is easy in discrete control tasks which have small action space, it can be difficult in continuous action spaces because finding the action that maximizes the Q value can be an optimization problem in itself. This can be computationally expensive to do at every instant, so recent methods alleviate this problem through an actor network μg that learns the action that produces the maximum Q value through stochastic gradient ascent, that is
No argmax (Ss,,Ho(ss))
The loss for the network in Eq. is then modified so that the argmax is evaluated using the actor network,
Lg = (Q" (s,, a.) - (ra + (o(s))))))
(5)
2.1 Experience Replay
Online RL algorithms perform updates immediately after observing a transition. However, these not only make learning inefficient but can cause issues in training due to high correlation between recent transitions. To eliminate this problem, Lin (2004) introduced experience replay, which stores the observed transitions and provides an interface to sample batches of transitions. This has been successfully used in DQN [Mnih et al. 2015) to play Atari 2600 games. Since Eqs. 3 5 not require that the states and actions are generated from the current policy, algorithms trained this way are called off-policy RL algorithms. During training, data is collected from the environment and are sampled to be trained on.
stored in a replay buffer from which

---

A naive method of sampling is to uniformly sample all data in the buffer, however, this is inefficient because not all data necessarily equally important. [Schaul et al. [2016] proposes Prioritized Experience Replay (PER), that samples points with probabilities proportional to their TD error which has been shown to have a positive effect on performance by efficiently replaying samples that the model has not yet learned, i.e., data points with high TD error. Each transition in the replay buffer assigned a priority p., and the transitions are sampled based on this priority. To ensure that data points, even with low TD error, are sampled sometimes by the agent, instead of greedy sampling based on TD error, the replay buffer in PER stochastically samples points with probability P.
P Σn
P.
(6)
where a E [0, 1) is a hyper-parameter introduced smoothen out very high TD errors. Setting a to makes it equivalent to uniform sampling. Since sampling points non-uniformly changes the expected gradient of a mini-batch, PER corrects for this by using importance sampling (IS) weights w
Punifoem P.
Wi =
(7)
where E [0, 1] controls the amount by which the change in gradient should be corrected and + where N is the number of samples in the replay buffer. The loss attributed to each Puniform NV
sample is weighed by the corresponding w, before the gradient is computed. In practice, 33 is either to 0.5 linearly annealed from 0.4 to during training.
2.2 Target Networks
In Eqs. 3 and 5 the target action value depends not only on the rewards but also on the value of the
next state, which not known. So, the value of the next state approximated by feeding the next
state to the same network used for generating the current Q values. As mentioned in DQN [Mnih
al. 2015), this leads to very unstable target for learning due to the frequent updates of the Q network. To alleviate this issue, MMih et al. [2015] introduce target networks, where the target Q value is obtained from a lagging copy of the Q network used to generate the current Q value. This
prevents the target from changing rapidly and makes learning much more stable. So Eq. 3 can be suitably modified to
Lo - (+), - (rx + max (((+),)a)))
(8)
respectively, where 0 are the parameters of the target network, which are updated at low frequency. Mnih et al. (2015) copies the entire training network 0 to the target network, whereas Haarnoja et al.) [2018] performs a soft update, where the new target network parameters are exponential moving average (with a parameter T) of the old target network parameters and the online network parameters.
2.3 Reducible Loss
The work of Mindermann al. [022] proposes prioritized training for supervised learning tasks based on focusing on data points that reduce the model's generalization loss the most. Prioritized training keeps a held-out subset of the training data train a small capacity model, Ono at the beginning of training. During training, this hold-out model is used to provide measure of whether a data point could be learned without training it. Given training data (I;, E D. the loss of the hold-out model's 's prediction, Viko on data point I; could be considered an estimate of the remaining loss after training on datapoints other than (.z, Vs). termed the irreducible loss. This estimate becomes more accurate as one increases the size of the held-out dataset. The difference between the losses of the main model, 6, and the hold-out model on the actual training data is called the reducible loss, L,p which is used for prioritizing training data in mini-batch sampling. T,, can be thought of as a measure of information gain by also training on data point (xr y).
L, = Loss(ū xz, 0) Loss(ğ 2, Oho)
(9)
3

---

2.4 Prioritization Schemes
Altemate prioritization strategies have been proposed for improvements in sample efficiency, [Sinha et al. [2000 proposes an approach that re-weights experiences based on their likelihood under the stationary distribution of the current policy in order to ensure small approximation errors on the value function of recurring seen states. Lahire et al. [2021] introduces the Large Batch Experience Replay (LaBER) to overcome the issue of the outdated priorities of PER and its hyperparameter sensitivity by employing an importance sampling view for estimating gradients. LaBER first samples a large batch from the replay buffer then computes the gradient norms and finally down-samples to a mini-batch of smaller size according to a priority. Kumar et al. [020] presents Distribution Correction (DisCor), a form of corrective feedback to make learning dynamics more steady. DisCor computes the optimal distribution and performs a weighted Bellman update to re-weight data distribution in the replay buffer. Inspired by DisCor, Regret Minimization Experience Replay (ReMERN) [Liu et al. 2021] estimates the suboptimality of the Q value with an error network. Yet. Hong et al. [2022] uses Topological Experience Replay (TER) to organize the experience of agents into a graph that tracks the dependency between Q-value of states.
3 Reducible Loss for Reinforcement Learning
While PER helps the agent to prioritize points that the model has not yet learned based on high TD error, we argue that there some trawb Data points could have high TD error because they noisy or not learnable by the model. It might not be the case that a data point with high TD error is also sample that the model can actually learn get useful signal from. In supervised learning, known failure condition of loss based prioritization schemes is when there are noisy points which can have high loss but are not useful for repeated training (Hu et al. 202I]. Instead of prioritization based on the TD error, we propose that the agent should focus on samples that have higher reducible TD error. This means that instead of the TD error, we should use a measure of how much the TD error can be potentially decreased, as the priority p; term in Eq. 6 it means that the algorithm can avoid repeatedly sampling points that the agent has been unable to Iearn from and can focus on minimizing error on points that are learnable, thereby improving sample efficiency. Motivated by prioritized training in supervised learning, we propose a scheme of prioritization tailored to the RI. problem.
We contend that this is better because
In the context of supervised learning, leam-ability and reducible loss for sample well-defined as one has access to the true target. However, in RL, the true target is approximated by a bootstrapped target (TD methods) the return obtained from that state (Monte Carlo). For policy evaluation with a fixed policy, the true value function can be obtained, however, since we are interested in control, it will be computationally intensive to capture the true value function with every change in policy as in policy iteration. Thus, to determine the Iearn-ability of sample, we need access to how the targets of the sample behave and how it changes across time. Since the concepts of a hold-out dataset or model are ill-defined in the paradigm of RL, we replace them with a moving estimate of the targets. Unlike supervised learning, where we draw i.i.d. batches from a fixed training set, the training data in RL are not i.i.d since they are generated by changing policy. So the holdout model would need to be updated from time time. Thus, in Q learning- based RL methods, a good proxy for the hold-out model is the target network used in the Bellman update in Eq. 8 Since the target network is only periodically updated with the online model parameters, it retains the performance of the agent on older data which are trained with outdated policies. |Schaul et al. (202 demonstrates how the policies keep changing with more training even when the agent receives close to optimal rewards. Thus, the target network can be easily used an approximation of the hold out model that was not trained on the new samples. Therefore, we define the Reducible Loss (ReLo) for RL as the difference between the loss of the data point with respect to the online network (with parameters 0) and with respect to the target network (with parameters 0). So the Reducible Loss (ReLo) can be computed as
ReLo
Lo Lg
(10)
There are similarities between ReLo as prioritization scheme in the sampling behavior of low priority points when compared to PER. Data points that were not important under PER, i.e. they have low Lg. will also remain unimportant in ReLo. This is because if Lo is low, then as per Eq. 10 ReLo will also be low. This ensures that we retain the desirable behavior of PER, which is to not repeatedly sample points that have already been learned.
4

---

However, there is a difference in sampling points that have high TD enror. PER would assign high priority data points with high TD error, regardless of whether or not those data points are noisy or unlearnable. For example, data point can have high TD error which continues to remain high even after being sampled several times due to the inherent noise of the transition itself, but it would continue to have high priority with PER. Thus, PER would continue to sample it, leading to inefficient learning. But, its priority should be reduced since there might be other data points that are worth sampling more because they have useful information which would enable faster learning, The ReLo of such a point would be low because both Lg and Lg would be high. In case a data point is forgotten, then the Le would be higher than Lg. and the ReLo would ensure that these points are revisited. Thus ReLo can also help to overcome forgetting.
3.1 Implementation
The probability of sampling data point is related to the priority through Eq. c and requires the priority to be non-negative. Since Q value methods use the mean-squared error (MSE) loss, the priority is guaranteed to be non-negative. However, ReLo computes the difference between the MSE losses and it does not have the same property. This value can go to zero when the target network is updated with the main network using hard updates. However, it quickly becomes non-zero after one update. So, we should create a mapping Smap for the Rel.o error that is monotonically increasing and non-negative for all values. In practice, we found that clipping the negative values to zero, followed by adding a small e to ensure samples had some minimum probability, worked well. That is. P; = max [ReLo, 0) + E. This is not the only way we can map the negative values and we have studied one other mapping in the supplementary material. Note also that during initial training when the agent sees most of the points for the first time, it would assign low priority to all depending on the value of ReLo and the sampling would be close to random. However, the priority will never go to zero because c, so we will always have a non-zero probability of drawing the sample. Once is sampled and the loss goes down, then the priority would again increase per ReLo and it would prioritize such points until the ReL. becomes low again. Thus, kind of achieves the best both worlds, where initially with less information we sample uniformly, but once ReL.o increases we sample points more frequently.
ReLo is not computationally expensive since it does not require any additional training. It only involves one additional forward pass of the states through the target network. This is because the Bellman backup (i.e., the right hand side of Eq. 2 is the same for Lg and Lg. The only additional term that needs to be computed for ReLo is Qigt St: ae) to compute Lg-
Algorithm 1 Computing ReLo for prioritization
Given off- off-policy algorithm A with loss function Lalg online Q network parameters f target Q network parameters replay buffer B, max priority Pmax, ReLo mapping fmap. epsilon priority c, training timesteps T. gradient steps per timestep T grad. batch size b. T for t in 3. do
Get current state from the environment Compute action a from the agent
Store the transition St. dt, Lt, S1+1 > in the replay buffer B with priority Pman- for steps in 1, 2, ....... do
Sample minibatch of size b from replay buffer
Compute the loss T.gls and update the agent parameters 0
Compute Loig and calculate ReLo as per Eq. 10
Update priorities of samples in mini-batch with the new ReLo values as Smap (Rel.o;) + end for
Update target network following the original RL algorithm A end for
In our implementation, we saw a negligible change in the computational time between PER and ReLo, ReLo also does not introduce any additional pyrre-earameters that need to be tuned and works well with the default hyper-pare paremmerreeters of a and 3 in PER. An important point to note is that ReLo does not necessarily depend on the exact loss formulation given in Eq. 8 and can be used with the loss function Lgg alg of any off off-policy Q value learning algorithm. In order to use ReLo, only have to additionally
5

---

IQM
Optimality Gap
LaBER.
IQM
Optimality Gap
Daseline-
Baseline-
PER-
PER
ReLo:
0.7
Max Normalized Score
Max Normalized Score
(a) Deed Control Suite
(b) OpenAl Gym
IQM
Optimality Gap
LaBER
Baseline
Optmallty Gap
PER
RelLo
Rainbow
Human Nomalized Score
Normalized
(c) MinAtar
(d) Atari
Figure 1: Metrics aggregated across each benchmark based on proposed metrics from Agarwal et al. 2021
10 seeds per environment-algorithn pair.
compute Ladg with respect the target network parameters 0. If the loss is just the mean square erro, then ReLo can be simplified and can be represented by the difference between Qo and Qg. But other extensions off policy learning methods modify this objective, for example distributional learning [Bellemare et al. [017] minimizes the KL divergence and the difference between two KL divergences can be simplified the same way. To make ReLo a general technique that can be used across these methods, we define it in terms of Lo and L.g. Our experiments also show that ReLo is robust the target network update mechanism, whether is a hard copy of online parameters at fixed frequency (as in DQN [Mnih et al. [013), and Rainbow [Hessel et al. 2017]) or if the target network an exponential moving average of the online parameters (as Soft Actor Critic [Haarnoja al. 2018)
Experimental Results
4.1 GridWorld Experiments
The major goal these Gridworld studies is to draw attention to two PER issues: subpar performance when faced with stochasticity and forgetting when faced with many tasks. We also highlight how ReLo can potentially solve both issues.
4.1.1 Pitfalls of TD Error Prioritization
To illustrate the potential downsides of using PER with TD error prioritization, we created a x empty gridworld with single goal. The agent always spawns at the top left corner and it has reach the goal at the bottom right for reward of +2. The reward zero everywhere else except, near center of the grid, where there is another state with a reward sampled uniformly from [-0.5, 0.5
The presence of this critical point would mean that during the initial phase of training, PER would keep prioritizing transitions to that state due to the unpredictable reward and the corresponding high TD error, and fail to learn about the true goal. Given a sufficient number of samples, all algorithms would ultimately converge the optimal policy. The ReLo criterion, however, does not prioritize unlearnable points and prioritizes other points where it can receive larger reward. Fig. 2 shows that PER samples this unlearnable point very often and with limited experience is unable to solve the task. In contrast, both uniform experience replay and ReLo do not over-sample this transition and thus can perform better in this scenario. This is further affirmed by the number of updates each algorithm makes in the neighborhood of the unlearnable point as visualized in Fig. 2 Prioritization using ReLo enables the agent sample more from the transitions leading the marn reward which explains its better performance.
'A detailed description of the environment given in the supplementary material.

---

Ordwerd www.sstteeeeo0000
145
1.0
Numbor
0.0
Saxeine
PiN
Figure 2: Left: The rewards obtained after 50K episodes across 50 runs in the gridworld domain with an unlearnable point. Right: Number of times a transition containing the unlearnable state and its neighbors were sampled.
4.1.2 Mitigating forgetting with Rel.o
To study how ReLo can help reduce forgetting in RL, design multi task version of the gridworld. We create a 6 x 6 gridworld consisting of two rooms A and B and goal state in each room. Task A is defined starting in Room A and reaching the goal state in Room A, and Task B is defined similarly for Room B. There a single gap in between the rooms, allowing the agent to explore both rooms but time limit is introduced so that the agent can not reach both goals in one episode. During training, for the first 100k steps, the agent starts in Room with access to Room B blocked. So during this stage, the agent observes only Task A. After 100K steps, the agent starts only in Room B, thereby no longer collecting data about Task A and must retain its ability on the task by replaying relevant transitions from the buffer. We train three agents, a baseline DQN agent, PER agent and a ReLo agent and monitor performance on both tasks during training. We provide average success rates over 60 seeds after 1M steps in Table [ad Appendix It shows how ReLo exhibits the least degradation in performance on Task A compared to the other baselines. From the training curves, we can see that there is a clear drop off in performance on Task A after 100K steps when the agent can no longer actively collect data on the task. However the ReLo agent exhibits least degradation in Task A while also outperforming the baseline and PER agent on Task This experiment clearly shows how ReLo helps the agent replaying relevant data points that could have been forgotten.
Table 1: Performance on Forgetting Task. Confidence intervals in brackets.
ALGORITHM
TASK A
TASK B
UNIFORM
0.43 (0.32, 0.54)
0.40 (0.29, 0.51) 0.26 (6.16, 0.36) 0.74 (0.65, 0.84)
PER
0.29 (0. 19, 0.39)
RELO
0.63 (0.52, 0.74)
4.2 Comparison of PER and ReLo
We study the effectiveness ReLo on several continuous and discrete control tasks. For continuous control, we evaluate on 9 environments from the DeepMind Control (DMC) benchmark [Tassa et al.) 2018) as they present variety of challenging robotic control tasks with high dimensional state and action spaces. We also include 3 environments from the OpenAl Gym benchmark for continuous control. For discrete control, we use the MinAtar suite (Young and Tian 2019 which consists of visually simpler versions of games from the Arcade Learning Environment (ALE) [Bellemare et al. 2013). The goal of MinAtar is to provide a benchmark that does not require the vast amounts of compute needed for the full ALE evaluation protocol, which usually involves training for 200M frames across 10 runs per game. This can be prohibitively expensive for researchers and thereby the MinAtar benchmark reduces the barriers present in studying deep RL research. We include scores 24 games from the ALE benchmark for a reduced number of steps to observe if there are signs of improvement when using ReLo over PER. We provide full training curves for each environment in the supplementary material. We compare ReLo with LaBER [Lahire et al. [222]] on the DeepMind Control Suite and MinAtar benchmarks using the codebase released by the authors.
In addition to the per environment scores, we report metries aggregated across environments based on recommendations from Agarwal et al. [222 in Fig. We can see that across diverse set of
7

---

tasks and domains, ReLo outperforms PER as a prioritization scheme, with higher IQM and lower optimality gap scores. This highlights the generality of ReLo.
4.2.1 DMC
In the continuous control tasks, Soft Actor Critic (SAC) [Haarnoja et al. 2018 is used as the base off- off-policy algorithm which we add ReLo. SAC has online and exponential moving average target Q network which we use to generate the ReLo priority term as given in Eq. [0 For comparison, also include SAC with PER to showcase the differences in performance characteristics of PER and ReLoo The results are given in Figs. Tal On of the 9 environments, ReLo outperforms the baseline SAC well SAC with PER. This trend in performance is visible in the aggregated scores in Fig. Ta where ReLo has a higher IQM score along with a lower optimality gap when compared to SAC, SAC with PER and LaBER.
Additionally, to study the effect of stochastic dynamics in a non-gridworld setting, we conducted an experiment stochastic versions of DMC environments. Specifically, added noise sampled from (0, o²) to the environment rewards during training. During evaluation episodes, no noise is added to the reward. This is similar to the stochastic environments used by [Kmarr et al. 2020]. For Quadruped Run, Quadruped Walk, Walker Run we used a 0.1, and for Walker Walk we used a higher level of noise (a 1) since there wasn't 't much change in the performance when using o 0.1 compared to deterministic version. The results are presented in Fig. Fig-BJand and Table 2 These experiments highlight how ReLo outperforms uniform sampling and PER in stochastic dynamics while also attaining lower TD error and reinforce our claim that ReLo can effectively handle stochasticity in environments.
Quadrased Run (a-n 0.3)
Quidhipod Walk: (pm
Welker Rum1
Welkor Walk (a-
65-
200
04
3.8
14
6.5
00
0.2
0.5
3.5
Figure 3: Performance on Stochastic DMC. Performance aggregated over 5 seeds.
Table 2: Validation TD Error on Stochastic DMC. Performance aggregated over 5 seeds.
QUADRUPED RUN
QUADRUPED WALK
WALKER RUN
WALKER WALK
UNIFORM
0.5 (0.34, 0.66)
1.27 (1.07, 1.47)
0.04 (0.04, 0.04)
1.98 (1.96, 2.0)
PER
5.22 (3.39, 7.05)
0.53 (0.47, 0.59)
0.06 (0.05, 0.07)
3.62 3.78))
RELO
0.19 (0.17, 0.2)
0.12 (0.11, 0.12)
0.03 (0.02, 0.03)
1.94 (1.92, 1.96)
4.2.2 OpenAl Gym Environments
In addition to the DeepMind Control Suite, we also evaluate ReLo on environments from the OpenAl Gym suite, namely HalfCheetah-v2, Walker2d-v2 and Hopper-v2 and the results available in Fig. 1b There is a general trend where PER leads to worse performance when compared to the baseline algorithm, in line with previous work by Wang and Ross [2019] that shows that the addition of PER to SAC hurts performance. However, this is not the case when using ReLo as prioritization scheme. It is very clear how the PER degrades performance while ReLo does not adversely affect the learning ability of the agent and in fact leads to higher scores in each of the tested environments. We believe that the degraded performance of PER in the Gym environments is due to instability in training caused by rapidly varying value estimates. We provide experiments to back up this claim Appendix L We should that early terminations in the OpenAl Gym environments cause the PER agent to have the highest variance in the estimate of the fail state distribution. These results are presented in Table 3 When we disable early terminations, the PER agent is able learn these environments, though it is still worse than the ReLo agent.
8

---

Table 3: Variance in Value Estimate of Fail State Distribution.
МETHOD
MEAN (CIS)
MIN
MAX
BASELINE
29.055 (-62.551, 120.662)
-87.8392 -115.291
258.484
PER
149.982 (-76.382. 376.3474634 376.346)
793.237
RELO
18.225 (-0.307, 756)
-14.4796
49.37
Cheetah Run
Quadruped Run
Allen
Amidar
T0Enrr
ToEnor
92
de
0.5 jamesbond
Quadruped Walk
Walker Run
Bank Heist
3-
TEEmor
0.50
0.00
0-
0.0
0.2
0.4
0.6
08
0.0
02
0.4
0.6
02
1.0
0.0
0.5
1.0
15
2.0
0.0
0.5
1.0
15
20
S0000
led
Stops
145
Stope
1e6
Sto05
1e5
FER
Reto
Boseline
Rainbow
Ranbow-Reia
(a) DMC
(b) Atari
Figure 4: Comparison of training TD error for PER and ReLo based sampling in DMC and b) Atari benchmarks. Calculated over 5 seeds.
4.2.3 MinAtar
the MinAtar benchmark, we use DQN (Miih et al. 2015) as baseline algorithm and compare its performance with PER and ReLo the 5 environments in the benchmark. DQN does not have moving average target Q network and instead performs a hard copy of the online network parameters to the target network at fixed interval. Similar to the implementation of ReLo in SAC, we the online and target Q network in the ReLo equation for calculating priorities. The results on the benchmark given in Fig. Tc PER performs poorly Seaquest and SpaceInvaders, with scores lower than the baseline DQN. These results are consistent with observations by Obando- Oobondo-Ceron and Castro 2021) which analyzed the effect of the components of Rainbow in the MinAtar environment. In contrast, ReLo consistently outperforms PER and is comparable to or better than the baseline. Our previous observation that ReLo tends help improve performance in situations where PER hurts performance also true here.
4.2.4 ALE
As an additional test, we modificd the Rainbow [Hessel et al.) 2017] algorithm, which uses PER by default, to instead use ReLo as the prioritization scheme and compared it against Rainbow with PER on 24 environments from the ALE benchmark. Instead the usual 200M frames evaluation, we trained each agent for 2M frames study if there are gains that be observed in this compute- constrained setting. As shown in Fig. [d we see that Rainbow with ReLo achieves better performance than Rainbow with PER. These experiments show the versatility of ReLo prioritization scheme.
4.3 Analysis of TD Loss Minimization
To verify if using ReLo as prioritization scheme leads to lower loss values during training, we logged the TD error of each agent over the course of training and these loss curves are presented in Fig. 4 As we can see, ReLo does indeed lead to lower TD errors, empirically validating our claims that using ReLo helps the algorithm focus on samples where the loss can be reduced. Another interesting point is that in Fig. 4a SAC with PER has the highest reported TD emror throughout training. This due to PER prioritizing data points with high TD error which might not necessarily learnable. Data points with higher TD error repeatedly sampled and thus making the overall

---

losses during training higher. In contrast, ReLo addresses this problem by sampling data points that learnable and leads to the lowest TD errors during training.
Table 4: Comparison of validation TD Errors on DM Control Suite
BASELINE
PER
RELO
CHEETAHRUN
0.02 + 0.002
0.03 = 0.000
0.12 + 0.033
QUADRUPEDRUN
0.62 0.05
2.24 0.122
0.35 0.067
QUADRUPEDWALK
3.17 0.2552
2.11 0.189
1.07
WALKERRUN
0.08 4 0.015
0.15 0.018
0.06 0.008
Table 5: Comparison of validation TD Errors on Atari
RAINBOW
RAINBOW+RELO
ALIEN
2.329 0.400
2.331 0.2551
AMIDAR
2.157 0.120
2.055
= 0.144
BANK HEIST
2.044 0.222
2.018 0.261
JAMESBOND
1,653 0.819
1.142 = 0.174
Validation TD Error: We also compared the validation TD errors of each method after training in
Tables 2 4 5 This was done by collecting 10 frames from the environment and computing the mean TD errors of these transitions. These results show that the validation TD errors (Li et al.) 2023] obtained at the evaluation phase are actually lower for ReLo. This analysis is very similar to observations in [Li al. 2023] where the authors find that lower validation TD error is a reliable indicator of good sample efficiency for off off-policy RL algorithms. ReLo achieves lower validation TD error compared uniform sampling and PER on DM Control Suite and Atari. When we study the correlation between validation TD error and performance in Appendix [ and observe a strong correlation between the two metrics, confirming the findings of [i al. [2023). These results highlight another crucial reason for the robustness and good performance of ReLo across multiple domains.
Conclusion
In this paper, we have proposed new prioritization scheme for experience replay, Reducible Loss (ReLo), which is based on the principle of frequently sampling data points that have the potential for loss reduction. We obtain measure of the reducible loss through the difference in loss of the online model and a hold-out model on a data point. In practice, we use the target network in Q value methods proxy for hold-out model.
ReLo avoids the pitfalls that come with naively sampling points based only on the magnitude of the loss since having high loss does not imply that the data point is actually learnable. While alleviating this issue, ReLo retains the positive aspects of PER, thereby improving the performance deep RL algorithms. It is very simple to implement, requiring just the addition of few lines of code to PER, and similar to PER it can be applied to any off-policy algorithm. Since it requires only one additional forward pass through the target network, the computational cost of ReLo is minimal, and there is very little overhead in integrating it into an algorithm.
While the reducible loss can be intuitively reasoned about and tested empirically, future work should theoretically analyze the sampling differences between ReLo and PER about the kind of samples that they tend to prioritize or ignore. This deeper insight would allow to find flaws in how approach non-uniform sampling in deep RL algorithms similar to work done in Fujimoto et al. [2020]. It would provide analysis of the change in learning dynamics induced by PER and ReLo.
10

---

Acknowledgments and Disclosure of Funding
The authors would like to thank the Digital Research Alliance Canada for compute resources, NSERC, Google and CIFAR for research funding. We would like to thank Nathan Rahn and Pierluca D'Oro for their feedback and comments. We also thank Nanda Krishna, Jithendaraa Subramanian, Vincent Michalski, Soma Karthik and Kargil Mishra for reviewing early versions of this paper.
References
Rishabh Agarwal, Max Schwarzer, Pablo Samuel Castro, Aaron Courville, and Mare G Bellemare. Deep reinforcement learning the edge of the statistical precipice. Advances in Neural Information Processing Systems, 2021.
Mare G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environ- ment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47: 253-279, 2013.
Marc G Bellemare, Will Dabney, and Rémi Munos. A distributional perspective reinforcement learning. International Conference on Machine Learning, pages 449-458, PMLR, 2017.
Richard Bellman. A markovian decision process. Journal of Mathematics and Mechanics, 6(5):
679-684, 1957. URL http::t///www.... jstor.
24900506
Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Matteo Hessel, Ian Osband, Alex Graves, Volodymyr Mnih, Rémi Munos, Demis Hassabis, Olivier Pietquin, Charles Blundell, and Shane Legg. Noisy networks for exploration. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL httptst:/
net/ www.:neeeeooonnimee htt
Scott Fujimoto, Herke van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1587-1596. PMLR, 10-15 Jul 2018. URL /ttp:htts///prreeddngg mlr press/ 180/fujamotoo8..co wa..ooooo1aahh.... html
Scott Fujimoto, David Meger, and Doina Precup. An equivalence between loss functions and non- uniform sampling in experience replay. Advances in neural information processing systems, 33: 14219-14230, 2020.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforeement learning with stochastic actor. Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICMI. 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 1856-1865. PMLR, 2018. URL htw.hhttp:/// http:::/proceeddigg//
mlr. www.preesseeeee vv00 hat/8//aaanojaj.. www.nooaaaii...... hhml
Matteo Hessel, Joseph Modayil, Hado van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Daniel Horgan, Bilal Piot, Mohammad Gheshlaghi Azar, and David Silver. Rainbow: Combining
improvements in deep reinforcement learning. CoRR, abs/1710.02298,, 2017. URL http://
arriv.org//bb... /1tp. 1111/021100009888
Zhang-Wei Hong. Tao Chen, Yen-Chen Lin, Pajarinen, and Pulkit Agrawal. Topological experience replay. ICLR, 2022. doi: 10.48550/arXiv:2203..1
Yuenan Hou, Lifeng Liu, Qing Wei, Xudong Xu, and Chunlin Chen. A novel ddpg method with prioritized experience replay. In Systems, Man, and Cybernetics (SMC), 2017 IEEE International Conference on, pages 316-321. IEEE, 2017.
Niel Teng Hu, Xinyu Hu, Rosanne Liu, Sara Hooker, and Jason Yosinski. When does loss-based prioritization fail? arXiv preprint arXiv: 2rxiv-2107.07741, 2021.

---

Aviral Kumar, Abhishek Gupta, and Sergey Levine. Discor: Corrective feedback in reinforcement learning via distribution correction. Advances in Neural Information Processing Systems, 33: 18560-18572, 2020.
Thibault Lahire, M. Geist, and E. Rachelson. Large batch experience replay. ICML, 2021.
Qiyang Li, Aviral Kumar, Ilya Kostrikov, and Sergey Levine. Efficient deep reinforcement learning requires regulating overfitting. 2023.
Timothy P. Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Hrez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning, In Yoshua Bengio and Yann LeCun, editors, 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016. URL http:://axxvv.orgg/a/// httpg//bs/1100..000 1tt.11109900977
Longxin Lin. Self-improving reactive agents based on reinforcement learning, planning and teaching. Machine Learning, 8:293-321, 2004.
Xu-Hui Liu, Zhenghai Xue, Jing-Cheng Pang. Shengyi Jiang, Feng Xu. and Yang Yu. Regret minimization experience replay in off- off-policy reinforcement learning. NEURIPS, 2021.
Sören Mindermann, Jan M Brauner, Muhammed T Razzak, Mrinank Sharma, Andreas Kirsch, Winnie Xu, Benedikt Höltgen, Aidan N Gomez, Adrien Morisot, Sebastian Farquhar, and Yarin Gal. Prioritized training points that are learnable, worth learning, and not yet learnt. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 15630-15649, PMLR, 17-23 Jul 2022. URL https://proceeednng. mlr. wttpss//112//mmdermmmanntt
Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Andrei A. Rusu, Joel Veness, Mare G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Pe- tersen, Charles Beattie, Amir Sadik, Joannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep rein- forcement learning. Nature, 518(7540):529-533 February 2015. ISSN 00280836. URL http::/dx.do1: org.10..111... 1038/ 2038//aatue11238
Johan Samir Obando- Ceron and Pablo Samuel Castro. Revisiting rainbow: Promoting more insightful and inclusive deep reinforcement learning research. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 1373-1383. PMLR, 2021. URL httpttt/tt/oceeediiiiie
mlr. (reesa/v13//eero//// html
Youngmin Oh, Jinwoo Shin, Eunho Yang, and Sung Ju Hwang. Model-augmented prioritized experience replay. In International Conference on Learning Representations, 2022. URL https net
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. In
Yoshua Bengio and Yann LeCun, editors, 4th International Conference Learning Representa- tions, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016. URL httt::///axivv wargg/bbs/11110 05952
Tom Schaul, André Barreto, John Quan, and Georg Ostrovski. The phenomenon of policy churn, 2022. httt/tttt:::/artttt
htrg/abs/2206.. 00730
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: Arxiv-1707.cm 06347, 2017.
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Mare Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484448) January 2016. doi: 10. 1 1.911. URL attps:://o/ org/ 10. 1038/ ntt.0//e//aueeee6111111
12

---

David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai. Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap. Karen Simonyan, and Demis Hassabis. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 36206419::1100-11 144, 2018. doi: 10.1126/science. aar6404.
wwtt::///wwwsscccceeeeccceme science org/ /ww./bb//////oo 10. 1126/ science. a4r6404
Samarth Sinha, Jiaming Song, Animesh Garg, and S. Ermon. Experience replay with Ikelihood-free importance weights. L4DC, 2020.
Yuval Tassa, Yotam Doron, Alistair Muldal, Tom Erez, Yazhe Li, Diego de Las Casas, David Budden, Abbas Abdolmaleki, Josh Merel, Andrew Lefrancq, Timothy Lillicrap, and Martin Riedmiller. Deepmind control suite. arXiv preprini arXiv: Arxiv-1801.0060 2018.
Hado van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double learning. Dale Schuurmans and Michael P. Wellman, editors, Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA, pages 2094-2100. AAAI Press, 2016.
aaai wrg. wwwp//c//nnnineeeeeeeeeeeeeeeeee wttpiiiwwwpp.......eeee /
haper/view/12389
Che Wang and Keith Ross. Boosting soft actor-critic: Emphasizing recent experience without forgetting the past. arXiv preprint arXiv: Arxiv-1906.04000 2019.
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado van Hasselt, Mare Lanctot, and Nando de Freitas. Dueling network architectures for deep reinforcement learning. In Maria-Florina Balcan and Kilian Q Weinberger, editors, Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pages 1995-2003. 1995-2003JMMRR.oog 2016. URL httl:httt:///oeee/ee//
mlr. wwwps/////e/aee http/////aanff..ht...
Denis Yarats and llya Kostrikov. Soft actor-critic (sac) implementation in pytorch. https://gitan http//gittt foom///nissyaratsyyttrr.r.
2020.
Kenny Young and Tian Tian. Minatar: An atari-inspired testbed for thorough and reproducible reinforcement learning experiments. arXiv preprint arXiv:1903.03177 2019.
Brian Ziebart, Andrew L Maas, J Andrew Bagnell, Anind K Dey, et al. Maximum entropy inverse reinforcement learning. In Aaai, volume 8, pages 4338-148. Chicago, II, USA, 2008
13

---

A Implementation Details
We build our experiments on top of existing implementations of SAC, DQN and Rainbow. For the DeepMind Control Suite experiments, we modify Yarats and Kostrikov 2020), adding prioritized replay buffer and the ReLo version. We use an open source implementation of Rainbow for the Arcade Learning Environment and the DQN implementation from the MinAtar authors) Young and Tian [209]. Aside from the collected frames and number seeds, we have not modified any of hyper-parametens from these original implementations. The hyper--aaaamteess as well as hardware and software used are given in Table 6
Table 6: Hyper- Param-Parsaeters of all experiments
Environments
Algorithm
Algorithm Parameters
Hardware & Software
Hardware-
CPU: Intel Gold 6148 Skylake
Frames = 2 10 seeds 5
GPU: 1 NVidia V100
RAM: 32 GB
ALE
Rainbow
Remaining haper-parameters same as Hessel ct al. 2017
Software-
Pytorch: 1.10.0
Python: 3.8
Hardware-
CPU: Intel Gold 6148 Skylake
Frames 10 seeds 5
GPU: NVidia V100
RAM: 32 GB
DeepMind Control Suite
SAC
Remaining hyper-paramelers same as Haarnoja et al. 2018
Software-
Pytorch: 1.10.0
Python: 3.8
Hardware-
CPU: 6 Intel Gold 6148 Skylake
Frames = 5 x 10t seeds 5
GPU: 1 NVidia V100
RAM: 32 GB
MinAtar
DQN
Remaining hyper-parament same as Mnih ct al. 2015
Software-
Pytorch: 1.10.
Python:
Figure 5: Visualization a few environments from each benchmark. Left to right: DeepMind Control Suite, MinAtar, Arcade Learning Environment
B Mapping Functions for ReLo
Prioritized experience replay buffers expect the priorities assigned data points be non-negative. While the MSE version of the TD error used PER satisfies this constraint, Rel.o does not. Therefore, there must be non-negative, monotonically increasing mapping from ReLo to p:. In our main experiments, we clipped negative ReLo values to zero. Another mapping we tried was to set p: ReLo in which case the probability of sampling data point P., from Eq. 6, corresponds the softmax over ReLo scores. However, for this choice the priority would explode if the ReLo crossed
hutps//gitthb.coo//iiixin//nnnn
14

---

Quadruppe Run
Quedruped Wal
750
750
250
253
Walk
800
1993
750
600-
0.0 32
6,1
0.6 0.
0.
32
64
08
Stags
Explneu
Figure 6: Comparison of different mapping functions from ReLo ps on a subset of environments from the DMC benchmark. Performance is evaluated over 3 seeds.
Method PER
Method RoLo
Mothod - PER
Nethod RcLo
Date
2
Deta
2.4
0.4
3.5
044
0.5
0.6
0.5
0.6
0.5
0.6
(a) DMC
(b) OpenAl Gym
Figure 7: Sensitivity of ReLo and PER to a and [.
values above which happened occasionally during the initial stages of learning in Rainbow. The second mapping function candidate was exponential when ReLo is negative and linear otherwise, that is,
ReLo
ReLo < 0
J EEpLLinear
+
otherwise
The linear part is shifted so that the mapping smooth around ReLo 0. As shown in Fig. 6 /Espplinear performs worse compared to just clipping negative ReLo values to zero. When the Rel.o values during training are analysed, we observe that the average of ReL.o values (before the mapping) tends to be positive, so clipping does not lead to large loss in information.
C Hyperparameter Sensitivity
We used the default hyperparameters that were given by Schaul al. [0066], i. a 0.5, f 0.4 for all benchmarks for PER and ReLo. Rainbow (Hessel et al. 2017 used these values for the ALE benchmark after extensive grid search. [Obando-Ceron and Castro (027], which studied DQN and Rainbow on the MinAtar benchmark, used the same values for and / after hyperparameter tuning, hence we reused these values in our experiments. These values transferred well to the DMC domain and so we used them for all continuous control experiments too. We performed hyperparameter sweep over a and /3 for DMC and OpenAl gym and results can be found Fig 7 ReLo consistently outperforms PER in these sweeps highlighting the robustness of ReLo across benchmarks. These sweeps also show that the performance of ReLo varied with changing the value of a which implies that the priorities assigned by ReLo not close to zero and hence the sampling behavior of ReLo not uniform. If the priorities were close to zero, then performance would not change when vary the value of since Eq. 6 would then reduce fori regardless of the value a.
D Extended Related Work
D.1 Prioritization Schemes
Prioritization strategies have been leading important improvements in sample efficiency. (Sinha et al. 2020 proposes an approach that re-weights experiences based on their likelihood under the
15

---

stationary distribution of the current policy in order to ensure small approximation errors on the value function of recurring seen states. Lahire et al. [202T] introduces the Large Batch Experience Replay (LaBER) to overcome the issue of the outdated priorities of PER and its hyperparameter sensitivity by employing an importance sampling view for estimating gradients. LaBER first samples a large batch from the replay buffer then computes the gradient norms and finally down-samples it to mini-batch of smaller size according to priority.
Kumar et al. 2020] presents Distribution Correction (DisCor), a form of corrective feedback to make learning dynamics more steady. DisCor computes the optimal distribution and performs a weighted Bellman update to re-weight data distribution in the replay buffer. Inspired by DisCor, Regret Minimization Experience Replay (ReMERN) [iu et al. [2021] estimates the suboptimality of the Q value with an error network. Yet, [Hong et al. [2022] uses Topological Experience Replay (TER) to organize the experience of agents into graph that tracks the dependency between Q-value of states.
While PER was initially proposed as an addition to DQN-style agents, Hou et [2017] have shown
that PER can be a useful strategy for improving performance in Deep Deterministic Policy Gradients
(DDPG) Lilicraap al. (016]] Another recent strategy to improve sample efficiency was introduce losses from the transition dynamics along with the TD error as the priority Oh et al. [2022). Although this has shown improvements, it involves additional computational complexity since also requires learning a reward predictor and transition predictor for the environment. Our proposal does not require training additional networks and hence is similar in computational complexity to PER. This makes it very simple to integrate into any existing algorithm. Wang and Ross (2019) propose an algorithm to dynamically reduce the replay buffer size during training of SAC so that the agent prioritizes recent experience while also ensuring that updates performed using newer data are not overwritten by updates from older data. However, they do not distinguish between points based on lear-ability and only assume that newer data is more useful for the agent to learn.
D.2 Off-Policy Algorithms
Off-policy algorithms are those that can learn a policy by learning from data not generated from the current policy. This improves sample efficiency by reusing data collected by old versions of the policy. This is in contrast to on-policy algorithms such as PPO Schulmann et al. [017)). which after collecting a batch of data and training on it, discard those samples and start data collection from scratch. Recent state-of ftate-of-the-art off- off-policy algorithms for continuous control include Soft Actor Critic (SAC) Haarnoja et al. (2018) and Twin Delayed DDPG (TD3) Fujimoto al. [2018] SAC learns two Q networks together and uses the minimum of the Q values generated by these networks for the Bellman update equation to avoid over estimation bias. The Q target update also includes a term to maximize the entropy of the policy to encourage exploration, a formulation that comes from Maximum Entropy RL Ziebart et al. [0088. TD3 successor to DDPG Lillicrap et al. (016) which addresses the overestimation bias present in DDPG in a similar fashion to SAC, by learning two Q networks in parallel, which explains the "twin" " in the name. learns an actor network ja following Eq. 4 to compute the maximum over Q values. TD3 proposes that the actor networks be updated at less frequent interval than the Q networks, which gives rise to the "delayed" name. In discrete control, Rainbow Hessel et al. [2017] combines several previous improvements over DQN, such as Double DQN van Hasselt et al. (016], PER Schaul et al. [2016), Ducling DQN Wang et al. 2016,, Distributional RL Bellemare al. 2017 and Noisy Nets Fortunato et al. 2018
E DeepMind Control Suite
We choose 9 environments from the DeepMind Control Suite Tassa et al. 2018 for testing the performance of ReLo on continuous control tasks. Each agent was trained on proprioceptive inputs from the environment for 1M frames with an action repeat of 1. The training curves for the baselines and ReLo are given in Fig, g
16

---

Table 7: Comparison of PER and ReLo the DMC benchmark
BASELINE
PER
LABER
RELO
CHEETAH RUN
761.89 = 112.38
831,87 = 38.90
579.80 + 60.61
660.29 + 141.22
FINGER SPIN
966.68 + 29.40
975.40 6.75
884.46 + 20.23
978.78 + 14.46
HOPPER HOP
264.75 + 37.90
217.35 +: 113.79
90.85 =
247.81 51.01
QUADRUPED RUN
612.67
143.90
496.42 216.01
344.80+41.13
833.92 81.05
QUADRUPED WALK
831.92 74.34
766.30
942.64
REACHER EASY
983.06 + 2.70
981.58 6.33
947.20 + 14.46
979.08 = 11.02
REACHER HARD
955.08 = 38.52
935.08 = 47.94
951.08 6.70
WALKER RUN
759.13 + 23.91
755.49 64.35
551.81 + 58.41
WALKER WALK
943.67 + 30.28
957.38 + 8.24
863.89 + 112.60
963.28 5.03
Cheetah Run
Finger Spin
Happer Hop
1000
1000
750
750
Reward
200
500
500
250
250
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.0
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Walk
1000
750
750
5.0
5.00
250
250
0.0
0.4
5.8
1.0
0.2
0.6
1.0
Reacher Hard
Walker Run
Walker Walk
800
1000
750
Roaddd
500
250
0.4
9.8
0.2
0.6
1.0
105
1c5
105
Danalime
Relo
LaBER
Figure 8: Training curves of environments from the DeepMind Control Suite. evaluated for 10 episodes over 5 random seeds.
Performance is
F OpenAI Gym Environments
We evaluate agents for 1M timesteps on each environment and similar to DM Control, they are trained using proprioceptive inputs from the environment. The hyperparameters for this benchmark are shared with those used for the DM Control Suite experiments.
Table 8: Comparison of PER and ReLo on OpenAl Gym environments
BASELINE
PER
RELo
GYM HALFCHEETAI
9579.60 +: 1331.00
9549.42 4 917.92
11590.63 +: 670.36
GYM HOPPER
2795.18 + 659.19
2175.09 + 456.11
2527.93 + 648.61
GYM WALKER
2854.20 + 623.69
735.16 + 474.89
3514.39
676.80
G MinAtar
We evaluate the baselines against 5 environments the MinAtar suite Young and Tian (209).
A visualization of few environments from the suite is presented in Fig. 5 Each agent receives
17

---

Haircheatah
Gym
4.00
4000
Rewaard
5000
5003
2000
2000
1000
1.0
100
Stess
Steas
Figure 9: Training curves of environments from the OpenAl Gym benchmark. Performance is evaluated for 10 episodes over 5 random seeds.
the visual observations from the environment and is trained for 5M frames following the evaluation methodology outlined in Young and Tian 2019). The training curves are given in Fig. 10
Asterix
Breakout
Freeway
60
Rowbod
20
Seaquest
Invaders
20-
Rowor5
20-
106
105
Daselime
ReLo
Figure 10: Training curves of environments from the MinAtar benchmark. Performance is evaluated using a running average over the last 1000 episodes over 5 random seeds.
Table 9: Comparison of PER and ReLo on the MinAtar benchmark
BASELINE
PER
LABER
RELo
ASTERIX
12.54 + 1.08
16.16 1.02
15.51 = 1.11
15.68 + 0.89
BREAKOUT
9.36 + 0.29
8.88
0.72
8.81 + 0.61
8.98 + 0.75
FREEWAY
52.80 0.35
52.75 0.22
41.98 1 20.99 20.99
53.25 1 0.37
SEAQUEST
16.13 1
6.02 1.92
14.63 2.98
18.13 1 1.25
SPACE INVADERS
45.36 1 1.65
37.36
43.67 3.17
38.54 1 2.60
H Arcade Learning Environment
We evaluate agents on compute-constrained version of the Arcade Learning Environment Bellemare al. 2203), training each agent for 2M frames. We chose the standard 24 environments from the suite for our evaluation. ReLo is competitive with PER Schaul et al. (2016) in the tested environments. The training curves for the Temporal Difference Error and the rewards are given in Fig. IT Fig. 12 respectively.
I Gridworld
implement a simple GridWorld for the experiments that highlights the drawbacks of PER with TD loss prioritization in Section 5.6. It consists of a x 7 grid. A visualization of the grid is given in Fig. [3 The start state the agent, represented by the blue point, the top left and the goal state the bottom right, represented by the green point. The agent is represented by the black point. The
18

---

A/W
NEAXX
Barkeett
kodin
Eroatert
Oxoce
1.5
04
10
16
21
15
14
15
20
10
04 14
30
2704
2005
Figure Temporal difference loss curves for Rainbow (with PER) and Rainbow with ReL.o. Rainbow with ReLo achieves lower loss compared to PER, showing that ReLo is able to prioritize samples with reducible loss. The dark line represents the mean and the shaded region is the standard deviation over seeds.
Bootg
Vile
1008
15
10
18
24
25
11
1000
300
4000
2000
1000
15
1.
2.0
25
25
10.
2000
1860
15
1.0
1180
180
2003
Figure 12: Training curves of 24 environments from the ALE benchmark. Performance evaluated for 10 episodes over 5 random seeds.
agent gets a reward +2 when it reaches the goal state, but does receive reward anywhere else other than the stochastic point. The red point marks the state with corresponding reward uniformly sampled from [-0.5, 0.5]. The locations of these points is fixed and does not change during training or evaluation. The state that the agent receives is (x, y) where and y are the coordinates of the agent's location, x, [-3,3] and x, y E Z. The agent has actions, to move up, down, left or right which will deterministically move the agent in that direction by 1 unit. If the agent is at the edge of the grid and takes an action that will move it out the 7 grid, then it remains the same location.
19

---

Table 10: Comparison of Rainbow with PER and Rainbow with ReLo on the ALE benchmark
RAINBOW
RAINBOW W/ RELO
ALIEN
1278.70 223.14
1352.90 535.70
AMIDAR
376.20 81.07
410.10 + 85.63
ASSAULT
2241.78 + 648.17
2617.37 + 555.97
ASTERIX
3214.50 323.70
3352.00 + 431.98
BANKHEIST
526.80 277.83
641.80 284.67
BOXING
76.65 14.58
76.21 11.59
BREAKOUT
82.03 = 46.10
68.36 + 45.39
CHOPPERCOMMAND
2794.00 + 732.87
4974.00 + 2801.93
DEMONATTACK
25500.50 1631
29294.30 15905.25
FREEWAY
32.58 0.31
32.35 0.25
FROSTBITE
2850.60 = 1553.34
3532.30 1270.73
GOPHER
5336.60 = 1023.75
5679.80 + 1199.68
HERO
9907.15 2108.71
8830.30 + 1894.51
JAMESBOND
810.00 = 412.00
902.00 469.40
KANGAROO
8904.00 3879.97
8091.00 3618.47
KRULL
6553.18 803.15
6718.67 + 799.47
KUNGFUMASTER
29371.00 8525.69
23654.00 + 12360.40
MSPACMAN
2094.70 614.58
1755,80 + 374.32
PONG
3.18 = 9.02
5.96 6.45
PRIVATEEYE
100.00 0.00
100.00 = 0.00
QBERT
8382.00 = 2935.16
10900.25 + 2704.23
ROADRUNNER
29333.00 9465.78
29222.00 = 8696.91
SEAQUEST
1377.20 20 362.57
1848.80 788.85
UPNDOWN
17065.40 7637.25
21241.50
8599.97
Figure 13: A top down view the GridWorld. The agent is the black point. starts at the blue point and the goal state is the green point. The red point represents the location of the stochastic reward.
Forgetting Experiment
visualize the gridworld used for forgetting experiment in Fig. 14 The training curves are given in Fig. 15
K
Correlation between Validation TD Error and Policy Performance
We study the correlation between validation TD error and the performance the policy and are able to reproduce the findings of Li et al. [2023] showing that there is indeed high correlation between the validation TD error and the performance. The results are Table We performed paired t-test and bold entries where the results significant.
20

---

Figure 14; Visualization of Grid Room. Cyan is goal state in Room A, green is goal state in Room B. Goal A gives reward of +1 and Goal B gives +5.
Task A
Task
1.00
Success Rate
0.75
0.50
0.25
0.00
Step
1c6
Step
1c6
PER Uniform
ReLo
Figure 15: Performance curves of Uniform sampling, PER and ReLo on the forgetting task. Success rates are averaged over 60 seeds and shaded regions indicate standard deviation. Once the agent is no longer able to collect data about Task A (>100K steps), performance the Task A decreases, but ReLo exhibits the least degradation in performance on Task A while still learning to solve Task B.
Table 11: Validation TD Error and Policy Performance on the DMC benchmark
METHOD
TD ERRORBiST
RETURNBESI
CHEETAHRUN
PER
PER
SINGERSPIN
RELO
RELO
HOPPERHOP
RELO
BASELINE
QUADRUPEDRUN
RELO
RELO
QUADRUPEDWALK
LABER
RELO
REACHEREASY
RELO
BASELINE
REACHERHARD
BASELINE
RELO
WALKERRUN
RELo
RELO
WALKERWALK
RELo
RELO
L Instability of PER in Mujoco Environments
We believe that degraded performance of the PER agent in Mujoco is because of instability in learning caused by rapidly varying value estimates. To test this hypothesis we studied the Walker2d environment, where PER obtains mean reward of 700, compared to the bascline (uniform sampling) which obtains a mean reward of 2800. This is surprising since PER does learn to perform well in WalkerWalk, which is the DMC equivalent of Walker2d (they have similar agent morphologies).
An important difference the two environments that Walker2d has early termination (episode ends when the walker falls down) while WalkerWalk does not. This meant that the early terminations could make predicting the value of the fail state distribution difficult as the walker falls different ways. There could be lot of noise in the reward at that stage which can make the TD estimate noisy too.
21

---

We hypothesize that since PER only samples datapoints proportional to the TD error, these states would be repeatedly sampled as the noisy estimate would make the TD error high. This means would be less likely to prioritize the samples corresooniigg good behavior which could have lower TD error than the noisy fail states. We looked the value estimate of the fail state in the baseline, PER and ReLo agent and observed this was the case. This is presented in Table T2 and estimates are calculated over 40 episodes.
Table 12: Variance in Value Estimate of Fail State Distribution.
METHOD
MEAN (CIs)
MIN
MAX
BASELINE
29.055 (-62.551, 120.662)
-87.8392
258.484
PER
149.982 (-76.382, 376.346)
-115.291
793.237
RELO
18.225 (-0.307, 36. 356)
-14.4796
49.37
There is high variance in the predicted value of the fail state for PER, meaning that invariably the TD eπrоr for these points would be high. But further training on noisy points does not help and instead makes the problem worse, causing the value estimate diverge. This can cause instabilities in training and potentially derail learning.
Finally created modified version of Walker2d without early terminations and PER acheives much better performance (Mean score of 1943.65 compared to 700.5 in the original Walker2d) in this environment, validating environment and the hyperparameters of the PER agent were the same in both experiments. We also looked at the value of the initial states (the environment is randomly initialized there is initial state distribution) in Table 13 and PER has higher variance in the predicted value even here.
hypothesis. Besides removing early termination, other parameters of the
Table 13: Variance in Value Estimate of Fail State Distribution.
METHOD
MEAN
MIN
MAX
BASELINE
227.916 (215.415, 240.417)
215.929
252.337
249.379 (177.265, 321.494)
177.968
337.663
RELO
203.893 (195.357, 212.428)
193.014
214.811
This analysis adds credence to our hypothesis that PER suffers from high variance in value estimates which hurt learning. Additionally, the experiments also show that ReLo has the least variance in the predicted value of the state (initial or fail state), highlighting how ReLo is a more stable prioritization scheme.
22


Reviews:
[{"review_id": "x6peJNM4II", "reviewer": "Reviewer_hZPB", "summary": "The author proposes a simple modification on prioritized experience replay, preventing unlearnable samples from being prioritized. Prioritized experience replay (PER) prioritizes samples with high TD errors, but some samples that have irreducible TD errors due to stochasticity may also be prioritized. This will hurt learning since these samples are unlearnable. Thus, the author proposes to prioritize only learnable samples by using reducible losses as priorities. The reducible losses are measured by the difference of TD errors with respect to the online Q-network and target Q-network. The experimental results show that the proposed method demonstrates consistent improvements over PER and uniform sampling in various common benchmarks.", "questions": "- Why PER degrades in mujoco (openai gym) but not in deepmind control suite?\n- In Table 1, ReLO doesn't have lower validation TD errors than PER and baselines in CheetahRun. Can the author comment on why?", "limitations": "Not mentioned in the paper. I suggest the author think of limitations when the target network is not a good held-out set and how to construct a better held-out set. Also, it's good to provide some theoretical analysis to show why the chosen priority will improve the convergence rate to the correct Q-function or similar analysis made in LaBER.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The idea of prioritizing reducible is a critical insight on prioritizing experience replay.\n- The method is easy to implement\n- The performance improvement seems to be consistent, while I have a few concerns on experimentation details.", "weaknesses": "- Lack of justification on why the difference between online and target networks can be a good estimate of reducible loss. A low online network loss may not indicate the Q-function learns the right Q-values since online networks may be changing too fast and cannot provide stable value targets.\n- Experiments in Atari need more justification. Since not every Atari game is tested, it is required to show the reason of choosing these games. Do these games cover all types of games? Are they particularly challenging for PER? Also, the reason of training only 2M frames makes the experiments weak. It's understandable that training 200M frames is not attainable for most people. But I think it's good to think of why training 2M frames would be sufficient to tell the difference between PER (Rainbow) and ReLO. It seems that the performance of ReLO and PER in Atari is pretty close. For now, the results in Atari is a bit inconclusive. It's possible that in these compute-restricted settings, ReLO and PER won't have significant differences.\n\nOverall, I think the insight made in this paper is important. However, the current experimental results do not clearly demonstrate why this insight matters since the performance is not significantly improved. In Atari, it's quite close to Rainbow (which is PER). In other domains, ReLO is doing better than PER but quite close to baselines (uniform sampling). To strengthen this paper, I suggest the author looking for tasks that significantly show the performance gain of ReLO to other tasks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the useful suggestions and comments to help improve this paper. We have incorporated the recommendations into the paper and discuss them below.\n\n### Motivation of ReLo in RL and target networks\nIn Mindermann et al. (2022) the hold out model is trained on a validation dataset which is drawn from the same distribution as the training dataset. Infact, the implementation uses a subset of the training set to train the validation model. However in RL we deal with non stationarity data distributions so it is not possible to train a hold-out model. However, the problem of learnability of a sample still exists in RL. If we observe that the TD error has been high for a long time, then it might be the case that at those points there is inherent noise (e.g. receives random reward every time), making such points highly unlearnable. PER would emphasize such points, whereas ReLo will not. Thus, a lagging version of the online model (target network) can be used to capture such points.\n\nWe believe target networks can be a good approximation for hold out model for two reasons:\n- Even though both models are trained on the same transitions, as explained earlier, there can be significant change in the data distribution that the online model sees that the target model does not till the next time the parameters are copied. As the policies approach close to optimal behavior, the difference in policy behavior between the online and the target network might reduce. However, as Schaul et al. (2022) mentions, the policies keep changing even when close to convergence, which means at no point are the distributions for training the online and target model same. \n- This is just an approximation for the holdout model, and we just use it as a prioritization scheme. So even the points that have low priority are still sampled. Thus in cases that the approximation may not hold good, it won’t affect the training in a major way as those points will still be sampled.\n\n\n### Atari Experiments\nWe have addressed your concerns in the Consolidated Author Response.\n\n### Additional examples of the benefits of ReLo\nWe have added another example to show how ReLo can prevent forgetting when switching to a new task. In addition, in our experiments in the paper, we show that ReLo is more robust and can be widely applied to many domains whereas PER only has limited benefits in particular environments.\n\n### Poor Performance of PER in DMC\n\nFrom our inspection of the training process, we believe this could be due to instabilities in training caused by high TD errors. During training of the PER agent the TD error would sometimes explode and not recover.\n\n### Higher Validation TD Error on CheetahRun\n\nReLo does not outperform in the baselines in this particular task. It could be that prioritizing the TD error works really well in this environment which is why PER is the best performing algorithm.\n\n### Limitations \nWe will add a separate limitations paragraph in the Conclusions section in the revised version of the paper.\n* Separate held out Set instead of using Target Networks: One approach would be to collect a subset of trajectories from the environment during the training process to create an evolving held out dataset. These trajectories would be only in the held out buffer and not the training buffer. The main RL agent would learn from the training buffer, and in parallel, we could learn a new Q network on only the held-out buffer. However this process would consume additional computational resources. In general, since the samples collected are non i.i.d, target networks can be a good approximation for this held out model.\n\n*    Theoretical Analysis: We agree it would be interesting to perform a theoretical analysis of the change in training dynamics and convergence rate introduced by sampling with ReLo. We have mentioned this as an avenue for future work in the conclusion of the paper."}, {"review_id": "cUMWnAwBDd", "reviewer": "Reviewer_DXpG", "summary": "This work introduces a novel experience replay sampling technique (ReLo-based sampling) that prioritizes sampling experience that has the greatest potential for reducing the agent’s loss. Empirically, ReLo-based sampling yield better performance than uniform random sampling and prioritized experience replay (PER).", "questions": "1. Can the authors include the returns for the tasks shown in Figure 2? Does large TD-error correspond to poor performance for these tasks? Since LaBER addresses issues with PER, It would be informative to see the TD-error for LaBER in Figure 2 as well.", "limitations": "See Weaknesses.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The work tackles a known issue with PER,\n2. The writing is generally very clear, and the authors consider a diverse set of benchmark tasks (discrete/continuous control, visual vs state-based observations).", "weaknesses": "1. The authors discuss how ReLo-based sampling can help in tasks with stochastic dynamics and/or rewards and help prevent forgetting, though it seems like the chosen benchmark tasks don't illustrate all of these benefits.\n    * DMC and OpenAI Gym environments have deterministic dynamics and rewards.\n    * MinAtar has stochastic dynamics (sticky actions with probability 0.1), but this stochasticity is completely independent of the agent’s state and chosen action. Thus, this stochasticity makes every state “equally unlearnable” in a sense. \n    * In contrast, I do see how ReLo is helpful if a subset of states have stochastic dynamics/rewards as in the toy example in section 4.6.\n\nDoes this mean the observed benefits of ReLo can then be attributed to how it prevents forgetting?\n\n2. I would like to see further discussion on how ReLo helps prevent forgetting, especially if the reasoning in my first comment is valid. Currently, there is one sentence mentioning this benefit. If the authors can provide a toy example similar to the gridworld example in section 4.6, that would more clearly illustrate why ReLo is important. Something that comes to mind: Consider an agent that must simultaneously learn 2 different tasks (e.g. navigate to point A and point B in a gridworld task). The first half of training, the agent sees task 1. The second half, it sees task 2. Presumably, ReLo would prevent the agent from forgetting task 2 while learning task 1?\n\n3. I believe section 4.6 should be moved just before ReLo-based sampling is introduced; it concretely illustrates a problem with PER and demonstrates how ReLo-based sampling addresses it.\n\n4. Related to my two previous comments: I feel ReLo needs more motivation. Section 4.6 does a good job of motivating one aspect of ReLo, though I would really like to see motivation for the other aspects (forgetting, stochastic rewards).\n\nI am willing to raise my score if the authors can (1) clarify which benefits of ReLo the experiments highlight, (2) better motivate ReLo e.g. through the use of additional tasks that highlight each potential benefit of ReLo.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable comments and suggestions to improve the paper. We strongly believe that these suggestions would make the paper better. We address all the concerns and questions below.\n\n### How ReLo can help even without stochasticity in rewards or dynamics\nYes, this can be attributed to how it prevents forgetting. We provide ReLo's motivation by illustrating how prioritising the TD error might be problematic when the reward or dynamics are stochastic (Section 4.6). However, ReLo can also help in preventing forgetting. In the function approximation setting, it is generally quite difficult to obtain the correct values of every state accurately because a change in the network affects the values of the entire state space. When an agent enters a region of the state space that it has not explored before, it is bound to get a spike in the TD error for all these new samples and PER will repeatedly sample these states. This might make the slightly older states non-consistent because we are in a function approximation setting. ReLo would prevent this by allowing the agent to still sample based on the reducible loss, so it would only prioritize learnable samples. \n\n### How ReLo can prevent forgetting\nWe thank you for this suggestion and we performed a similar experiment where we indeed confirmed that ReLo can actually prevent forgetting. We elaborate on this and share intereseting insights in the Common Author Response.\n\n### Section 4.6\nWe shall move this section in the revised version of the paper.\n\n### Benefits of ReLo\nIn this paper we study the effect of the ReLo criterion on\n- handling noisy/stochastic points (Section 4.6) \n- mitigating forgetting of previous tasks (Forgetting experiment in the common response)\n\nWe also highlight its\n- generality and robustness to mechanism and frequency of target network updates (EMA/Hard-copy target update)\n- applicability to varied tasks with discrete or continuous control, with pixel or proprioceptive inputs.\n\n### Returns for experiments in Figure 2\nThe returns are given in Table 2 in the supplementary material.\n\n### Relationship between validation TD Error and Policy Performance\nWe have addressed this in the Common Author Response. To summarize, there is indeed a correlation between the validation TD error and the policy performance in the trained off policy agents.\n\n### TD Errors for LaBER\nWe included the validation TD Error for LaBER in the Common Author Response. We will add the traning TD Error in the revised version of the paper."}, {"review_id": "FBT06xurOW", "reviewer": "Reviewer_Mxrp", "summary": "The authors propose a novel form of prioritized experience replay based on the “learn-ability” of the sample, or how much the training loss on a sample can be reduced.  \nThey point out that previous methods that prioritize data with high TD error are not optimal if the high TD error is irreducible error, which can be caused by a noisy environment.  Instead the authors prioritize high reducible TD error using a new metric that is the difference in TD error between the current Q function and a delayed, target Q function.  This is a simple and computationally cheap method that can be applied to many off-policy RL algorithms.\nThey demonstrate across a range of continuous and discrete control benchmarks that this sampling metric outperforms uniform and PER sampling and demonstrate that their method achieves lower TD error.", "questions": "- Section 3 makes a nice connection between the hold-out model in supervised and the target Q network in RL.  Why isn’t the same reasoning applied to the hold-out data?  If the ReLo is computed on data that has been used to train the target network already, isn’t this no longer the reducible loss?\n\n- Section 3.1: How are the priority values updated across the replay buffer as training progresses?  If the priority values are only updated per training mini-batch, is it possible that there are a large proportion of out-of-date priority values, especially if ReLo was low to begin with but increases later like in the forgetting case that was mentioned.\n\n- Why is PER in most cases, worse than the baseline method?  \n\n- Section 4.6:  This is a nice toy analysis and may also be useful to mention earlier on in the paper to support the hypothesis that PER is limited due to unlearnable samples.  The issue is the learning curves for this task aren’t very convincing because of the high variance and that average performance never really goes above 0.5 for any methods.\n\n- Why did you use LaBER as another comparison and why were the other prioritized replay methods not relevant to compare against?", "limitations": "No limitations addressed", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Authors identify a valid limitation of prior methods: that it might over-emphasize samples with high reducible error leading to wasted training effort.  \n- Reasonable application of supervised learning techniques to RL to address this limitation in a relatively simple and straightforward algorithm.  Method also inherits generality of other prioritized experience replay algorithms.\n- Authors demonstrate strong experimental results across a wide range of tasks and using multiple base RL algorithms.", "weaknesses": "- Clarity in writing.  Background and related work section can be more concise.  In section 3.1, the introduction of $f_{map}$ with PER priority is not very intuitive.  Some terms like \"significance\" and \"importance\" of data are not well defined, and \"learn-ability\" and reducible loss seem to be the same.\n\n- In general, the experimental results are missing learning curves, especially since sample efficiency would be one of the main benefits of prioritized replay.  It’s also not clear how the final performance figures are determined (Are all methods trained until convergence?  How are the policies evaluated?).\n\n- Section 4.5 TD Error Analysis.  The interpretation of the TD errors seems a bit stretched.  Many factors could affect TD error that does not necessarily relate to policy performance.  For example, that PER actually prioritizes high TD error samples like the authors mention.  Were the validation data gathered by the specific policy trained in each algorithm?  Were these policies trained until convergence?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable insights and suggestions to improve the clarity of the paper. First, we would like to apologize for the lack of explanation and coherence in the paper. We have fixed all the points raised in the review. We will address them sequentially.\n\n### Notation Clarification\n$f_{map}$ is used to denote the mapping from the raw ReLo values to a priority that can be used for sampling in the Priority Queue implementation of the PER buffer. We shall add clarifications in the revised version of the paper to highlight this.\n\n### Significance, Importance and Learnability\nThese are qualitative terms that we use to describe the phenonmenon that all data samples are not equally important for the learning process. We use learnability as a  the qualitative measure of how useful a sample is for the learning process. The reducible loss is a quantitative metric that can be used to measure the learnability of a sample.\n\n### How final performance is determined\nWe follow the recommendations of Agarwal et al. (2021) for aggregating results across a benchmark. They propose treating the performance of a given training run as a random variable and suggest that authors report statistical measures on these random variables. The interquartile mean (IQM) computes the mean of the middle 50% of runs while the optimality gap is a measure of how far an algorithm is from optimal performance aggregated across environments. For computing these measures, each environment score first needs to be normalized. In the DMC benchmark, the optimal score for each environment is 1000, while we use the highest reported scores for each environment from the MinAtar paper and the OpenAI Gym environments for calculating the optimality gap for those benchmarks. The environment scores are normalized with respect to this max score. For the ALE benchmark, we normalize the scores of each game with respect to reported random and human level scores.\n\n### Learning Curves\n\nThe learning curves for the experiments are given in the supplementary material.\n\n\n\n### Relationship between validation TD Error and Policy Performance\nWe have addressed this in the Common Author Response. To summarize, there is indeed a correlation between the validation TD error and the policy performance in the trained off policy agents.\n\n### Calculation of Validation TD Error\nYes, the validation data was collected by the same policy after training was completed. The policies are trained for 1M steps (for DMC and Mujoco, which is standard for these benchmarks) or 2M steps (Atari). \n\n### Separate Hold-out Data\nOne approach would be to collect a subset of trajectories from the environment during the training process to create an evolving held out dataset. These trajectories would be only in the held out buffer and not the training buffer. The main RL agent would learn from the training buffer, and parallely we could learn a new Q network on only the held-out buffer to mimic the held out model. However this process would consume additional computational resources. In general, since the samples collected are non i.i.d, target networks can be a good approximation for this held out model.\n \n### Updating Priority Values\nThe priorities are updated for the batch of samples that are trained on. So the priorities in the buffer are the last encountered priorities of the sample. This is based on the implementation used by PER since it can be very expensive to recalculate the priorities of all samples in the buffer after every update. The addition of $\\epsilon$ to the probabilities ensures that all samples are replayed and if there is an erroneous priority it would be corrected the next time the data point is sampled. \n\n### Why PER does worse than uniform in certain environments?\nIn a function approximation setting, it is generally quite difficult to obtain the correct values of every state accurately. When an agent enters a region of the state space that it has not thoroughly explored before, it is bound to get a spike in the TD Error for all these samples and PER will repeatedly sample these new states. This might make the slightly older states non-consistent because we are in the function approximation setting and thus this can lead to forgetting. ReLo prevents this by sampling states based on the reducible loss and thus prevents forgetting.\n\n\n### Learning curves in Section 4.6\nSection 4.6 motivates why PER is not a good prioritization scheme and how ReLo would be able to handle these cases. We did not train those agents for longer because we are more interested in the sampling strategies of the baselines and how they handle stochasticity in environments.\n\n### Why LaBER was used as a baseline?\nLaBER did not require training any additional networks to obtain better prioritization schemes and required similar compututational resources to Prioritized Experience Replay. That is why, we think LaBER and PER would be fair baselines since ReLo also does not involve training any additional networks which can be expensive."}, {"review_id": "jBLAVkMH8o", "reviewer": "Reviewer_ax9T", "summary": "This paper proposes an experience replay priority scheme based on the notion of reducible loss (ReLo), estimated as the difference in Q-loss between using the online Q-network and the target Q-network, and show in experiments in DM Control Suite, Mujoco tasks, and Atari environments that it improves upon prioritized experience replay (PER) (TD-error based) and uniform replay. They also demonstrate through a toy example that their method is able to avoid the common pitfall of stochasticity that prioritized experience replay struggles with often.", "questions": "As mentioned in the weaknesses section, for the MinAtar and Atari experiments, did you enable sticky-actions? If yes, what was the sticky probability?\n\nBecause ReLo uses the target network to compute priorities, it is currently tied to the hyperparameters of the target network. Have you considered using a second target network to disentangle this? Could there be cases where for the RL, you would want a very fast updating target network, but for ReLo you would want a much slower updating target network?\n", "limitations": "This is related to the question about having a second target network. ReLo currently cannot easily change the hyperparameters for the target network, as it may have a great impact on the RL optimization. It may end up being the case that ReLo would prefer a much slower (or much faster) updating target network. This seems like a possible future direction to explore. Perhaps there should be a brief mention of this in the paper.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The strength of this paper is in its simplicity and clarity. The idea and implementation is very simple and straightforward, requiring no new changes to existing algorithms and networks, and takes advantage of the target network that is already present. The priority is very simple to compute, as it just requires computing the Q-loss one more time. The experiments are quite clear, and demonstrate how ReLo can outperform uniform sampling and PER across control/robotic tasks and MinAtar tasks. This all makes this idea very easy to adopt and further experiment with for follow-ups.", "weaknesses": "The main weakness is in the experiments. One weakness is in the ALE experiments, which do not run Rainbow for very long (only 2M). While these preliminary results are promising, they are ultimately too early in training to be relied upon. Nevertheless they are still useful to see than not to have. Another weakness is the lack of more stochastic domains, as control/mujoco and Atari are all very close to deterministic. Was sticky-actions enabled for Atari or MinAtar tasks? If not, then that would be something very good to include that would not require running on a new domain.\n\n---- After Author Rebuttals ----\n\nAfter reading other reviews and author rebuttals, I do agree that the experiments are a little lacking. There should be a clear (non-gridworld) stochastic domain that can highlight the difference between uniform, PER, and ReLo. The addition of noisy DMC results would fill this gap, and as the authors will include it in the final paper. I maintain my score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's constructive criticism and recommendations for making this paper better. We discuss the points below.\n\n### Sticky Actions\nYes we used sticky actions in Atari and MinAtar, utilizing the default values of 0.25 and 0.1 respectively. \n\n### Decoupling Target Network and Held Our Model\nWe thank the reviewer for pointing this out. We agree it would be an interesting question to see if ReLo could be implemented with a separate target network. For our experiments we wanted to highlight the robustness and generality of ReLo by studying it with different target update mechanisms and target update frequencies and hence we did not use an additional target network.\n\nBut we agree this would indeed be an interesting proposition. We performed some preliminary experiments with separate target networks and the performance was similar. However we are running some ablation experiments with faster and slower update frequencies.\n\n### Additional experiments\nTo highlight the ability of ReLo to mitigate forgetting, we created an experiment where an agent is given access to a sequence of tasks. This is explained in detail in the consolidated response. The experiment shows how the ReLo agent suffers the least degradation in performance on prior tasks while still learning on the new task. This is in contrast to the PER agent which forgets how to solve the previous task and also takes longer to learn the new task."}]

Author rebuttal:
Thank you for taking the time to review our work. We greatly appreciate your valuable feedback and comments and we will incorporate the suggestions into the revised version of the paper. We would like to clarify a few points that multiple reviewers mentioned before addressing each comment individually. 

### ReLo can help prevent forgetting
We created a 6x6 gridworld consisting of two rooms and a goal state in each room. The left room is called Room A and the right is Room B. We define Task A as the agent starting in the Room A and reaching the goal state in Room A, and similarly define Task B as the agent starting in Room B and reaching the goal in Room B. There is a single gap in the wall allowing the agent to explore both rooms, but a timelimit is implemented such that the agent can not reach both goals in one episode. For the first 100k environment steps, the agent begins in Room A and we block access to Room B. So during this stage, the agent only learns about Task A. 

After 100K steps, the agent starts in Room B, allowing it to learn Task B. The agent no longer starts at Room A, thereby no longer collecting data about Task A and must retain its ability by replaying the relevant transitions from the buffer. We train three agents, a baseline DQN agent, a PER DQN agent and a ReLo DQN agent and monitor their performance on both tasks during training. We evaluate performance over 50 seeds, providing the average success rates at the end of training in the table below. The training curves and a visualization of the environment are included the PDF included in the general response.

| Task A       | Task B       |
| -----------  | -----------  |
|PER: 0.40     |PER: 0.64     |
|Uniform: 0.32 |Uniform: 0.72 |
|ReLo: 0.80    |ReLo: 1.00    |


From the training curves, we can see that there is a clear drop off in performance on Task A after 100K steps when the agent can no longer actively collect data on the task. However the ReLo agent exhibits least degradation in Task A while also outperforming the baseline and PER agent on Task B. This experiment clearly shows how ReLo helps the agent replaying relevant data points that could have been forgotten. 

### Relationship between Validation TD Error and Performance (DXpG, Mxrp)
We analyzed the validation TD error and the return for environments in the DMC suite and observed that there is indeed a correlation between the two metrics. Of the 9 games tested, in 5 games the method with the best (lowest) validation TD error is also the method with the best (highest) policy performance. There is a similar correlation between the worst validation TD error and the worst performing policy. 

### Atari Experiments (ax9T, hZPB, DXpG)
The subset of games were chosen from the games used in the Atari100K benchmark. This is a benchmark used for evaluating sample efficiency in Atari, where agents are provided with a budget of only 100K interactions with the environment. The suite was chosen to cover a range of games where non random performance can be obtained in 100K data regime. Hence we believe this subset would be a good suite of games to validate our hypothesis that ReLo improves sample complexity.

Meta-review: This paper identified an issue of prioritized experience replay (PER), i.e., large TD error could be a result of irreducible noise, which makes PER problematic in stochastic transition and reward settings. The authors proposed to used a reducible loss based on target networks to do prioritization.

The idea of prioritizing reducible is appreciated by all reviewers and is a valid issue of PER. Reviewers also like the simple and direct proposed method, using target network to approximate reducible losses.

There are concerns regarding the experiments were conducted on nearly deterministic environments of DMC and OpenAI Gym, and the authors used a noisy DMC environment to provide additional evidences, which convinced reviewers.

Discussions and suggestions from reviewers, including forgetting experiments and improving writing should be taken into subsequent versions.
Decision: Accept (poster)