Memory-Efficient Reinforcement Learning with Priority based on Surprise and On-policyness
Authors: Ryosuke Unno
Yoshimasa Tsuruoka
Venue: Submitted to ICLR 2023 (2023)
Keywords: replay buffer
reinforcement learning
memory efficiency

Abstract: In off-policy reinforcement learning, an agent collects transition data (a.k.a. experience tuples) from the environment and stores them in a replay buffer for the incoming parameter updates. Storing those tuples consumes a large amount of memory when the environment observations are given as images. Large memory consumption is especially problematic when reinforcement learning methods are applied in scenarios where the computational resources are limited. In this paper, we introduce a method to prune relatively unimportant experience tuples by a simple metric that estimates the importance of experiences and saves the overall memory consumption by the buffer. To measure the importance of experiences, we use $\textit{surprise}$ and $\textit{on-policyness}$. Surprise is quantified by the information gain the model can obtain from the experiences and on-policyness ensures that they are relevant to the current policy. In our experiments, we empirically show that our method can significantly reduce the memory consumption by the replay buffer without decreasing the performance in vision-based environments.

Under review as a conference paper at ICLR 2023
MEMORY-EFFICIENT REINFORCEMENT LEARNING WITH PRIORITY BASED ON SURPRISE AND ON-POLICYNESS
Anonymous authors Paper under double-blind review
ABSTRACT
In off-policyy reinforcement learning, an agent collects transition data (a.k.a. ex- perience tuples) from the environment and stores them in replay buffer for the incoming parameter updates. Storing those tuples consumes a large amount of memory when the environment observations are given as images. Large memory consumption is especially problematic when reinforcement learning methods are applied in scenarios where the computational resources are limited. this pa- per, introduce method to prune relatively unimportant experience tuples by a simple metric that estimates the importance of experiences and saves the overall memory consumption by the buffer. To measure the importance of experiences, we use surprise and on-policyness. Surprise is quantified by the information gain the model can obtain from the experiences and on-policyness ensures that they are relevant to the current policy. In our experiments, we empirically show that our method significantly reduce the memory consumption by the replay buffer without decreasing the performance in vision-based environments.
INTRODUCTION
Reinforcement learning (RL) has become a promising approach for learning complex and intelligent behavior from visual inputs (Mnih al.) 2016 Kalashnikov et al. (018). In particular, off off-policy RL algorithms (Mnih et al. 2015 Hessel et al. 2018 generally achieve better sample efficiency than on-policy algorithms by using experience replay (Lin 1992). In experience replay, the transitions observed in the environment In addition, the replay buffer has the role to remove the correlations between the samples in a mini- batch. However, these methods require significant number of experience tuples, which consume large amount memory when the observations are given as images.
stored experience tuples in replay buffer and used repeatedly.
Many prior studies replay buffers in RL consider how the experience tuples sampled from the buffer (Schaul et al., 2016 Zha et al., 2019) Fujimoto et al. 2020 Sun et al., 20200] Oh et al.) train agent in scenario where the available resources
limited, the play buffer needs to be reduced to an appropriate size. It is known that simply reducing the size of the replay buffer will lead unexpected performance degradation (Liu & Zou 2018 Fedus al., 2020). There is some prior work on how to select old experience tuples to overwrite when a new ex- perience tuple comes into a relatively small buffer (Pieters Wiering) 2016 de Bruin et al. 2016b] 2018). However, they do not consider a memory-efficient method for image observation where memory consumption large. We aim to reduce the size of the replay buffer without degrading the performance in visual domains.
2021]. If
Our intuition is that some experience tuples are important for gaining knowledge about the environ- ment and others are not. For example, the scenes in video game that do not accept any inputs from the player, such as the standby screen, occupy a considerable amount of time in the game, but they do not provide much information. In contrast, the frames that within a few frames of the scenes where the player earns or loses points are often important in the game. In particular, the scenes that related to the end of gameplay are important to keep the game going and to obtain high scores.
On the basis of this intuition, we propose to prioritize and keep experience tuples that are deemed important and discard the others. The overview of our approach is shown in Figure T In this paper,

---

Under review as a conference paper at ICLR 2023
Priority function
f(T)
(m) 0.63)
(72. 0.57)
Append
[73, 0.94)
new (&t, 0t Tt,, St-1)
DeW 0..55
New experience
Experience tuple
N.299
Discard
(7g. 0.43)
Relay butfer (C-5)
Figure 1:
Illustration of our proposed method. Priority of the experience tuples are calculated, and they are discarded based on the priority when a new experience tuple arrives. The capacity of the replay buffer in the figure is small for the sake of readability.
we propose a metric based on surprise (Itti & Baldi 2005) and on-policyness (Fedus et al., 2020 to estimate the importance of the experiences and to prune the unnecessary experience tuples stored in the replay buffer. We hypothesize that the importance of an experience tuple is determined by the degree of information that the model gains by obtaining the experience tuple and the strength of relevance to the current policy. Surprise is related to the uncertainty of an experience tuple and represents the novelty of the information. At the same time, however, the agent does not need to keep all the experience tuples that have high uncertainty, especially the ones that are likely to be outliers. The on-policyness metric is introduced to suppress the adverse effects of those outliers and keep the experience tuples close the actual transition the current agent takes. We demonstrate that our method can be implemented as simple modifications to the existing implementations for replay buffers. In addition, our approach sample experience tuples from the buffer.
be combined with the existing approaches that are used to
We show in the experiments that the proposed method of data pruning can save the memory sumption of the buffer and prevent performance decrease when the size of the buffer is limited.
RELATED WORK
Experience replay using replay buffers is a common method in off-policy RL algorithms to make the most of the experiences obtained by the behavior policy (Mnih et al., 2015 Haarnoja et al. 2018 Hessel et al.] 2018). Most of the research on replay buffers focuses on how the experience tuples are sampled from the buffer when creating mini-batch to accelerate the training process. The most well-known is the prioritized experience replay (PER) (Schaul et al., 2016). which prioritizes the sampling the experience tuples based on their training errors. There have been many studies in- vestigating other effective indicators for sampling the experience tuples to achieve efficient training. Some used fixed metrics to select experience tuples (Schaul et al.) [216)] Fujimoto et al.) 20200] Sinha al. 2022), while others constructed and trained models to select the tuples which maximize the improvement of the policy model after the parameter update (Zha et al. 2019) Oh et al.) (021)) There have also been some studies examining experience selection methods based on indicators such as reward (Pieters & Wiering 2016). surprise (de Bruin et al. 2018), and exploration (de Bruin al. 2016a 2018). and how they affect the performance of an RL agent in state-based environ- ments using relatively small buffer. Chen et al. (202T) proposed method that aims to construct a memory-efficient RL algorithm in vision-
domains. In this method, they freeze the parameters in the convolutional neural network (CNN) encoder at the early stage of the training and store the latent vector from the encoder, instead of storing raw images to save memory consumption. The major difference in our approach is that we choose the experiences to discard. Since the discarding of the experiences is done independently of the sampling process, the sampling methods used in the replay buffer can be combined with our method.
We introduce a method to select experience tuples in RL settings. Determining which tuples to keep can be seen in continual learning setting (Lopez-Paz & Ranzato 2017 Shin et al., 2017 Isele & Cosgun, 2018 Rolnick et al.) 2019). In these settings, the model is given a stream of data and the training done in an online manner. These settings suffer from catastrophic forget-
2

---

Under review as a conference paper at ICLR 2023
ting (French) 1999; Goodfellow et al. 2013), where the model forgets the information observed in the early stage of the training. One method to prevent this issue is to keep some of the data in a buffer to remember the key components in each domain. In this approach, metries like the gradient of the samples (Lopez-Paz & Ranzato 2017] Aljundi et al. 2019), the feature vectors (Rebuffi et al.) 2017), or the learnability of the data (Sun et al. 2022) are used select the data keep. Tasks from different domains are given as the training proceeds in continual learning in RL (Isele & Cosgun 2018 Rolnick et al. 2019). The agents need to remember the previous task after being introduced to new tasks or have to adapt quickly using the knowledge from the previous tasks. In our setting, we only consider a single task domain and do not require adaptation a different task. Catastrophic forgetting is thus not as important as in these methods in our setting.
3 BACKGROUND
We consider Markov decision process (MDP), defined by (S, (S,A,T, AAA,,Po,, T), where S is a state space, a set of actions, T a state transition function, Po a distribution over the initial states, r S x A + R is a reward function, and E [0, 1) is discount factor. At each time step t, the agent observes the current state 8t of the environment, selects and takes an action at based on its policy x <aa (8.). The environment returns an immediate reward rr and the next state 8t+1- The goal of the agent is to learn a stationary policy that maximizes the expected discounted sum of reward R. ET cc 7 az)], where the expectation is calculated over the trajectories sampled from So ~ Pu, ag ~ (-1(s)), and 81+1 ~ Ts, ae) for 2 0. Tę is an experience tuple (s2, agy Tes 81+1) which contains elements observed within a single time step in the environment.
3.1 DEEP REINFORCEMENT LEARNING
The mainstream of off-policy RL algorithms derives from Q-learning (Watkins & Dayan 1992), which learns an -vlue function called a Q-function. The Q-function is defined a discounted sum of rewards, after taking an action on a state
Q" (s. a) E Σ ('r(snn =s 0g =
The Q-function is learned by minimizing the temporal difference (TD) error d(T) defined as:
8(T) (Q(st, at) Qtarget (+))
Qlarget (st, g a.) r(s,, ax) + max ())411
The deep Q-Network (DQN) algorithm (Mnih al. 2015) approximates Q-function with deep neural network. The Q-function has been expressed and learned in various forms, for example, combination of value function and advantage function (Wang al. 2016). tion returning the distribution of the Q-values (Bellemare et al. [217]] Dabney et al. 2018). In the represented discrete probability distribution pl p(Q), and com- monly the TD error is calculated as the KL-divergence between the current and the target Q-value distributions (Bellemare al. 2017):
func-
distributed settings, Q-values
((T) = (KL(p( target (st, ()))))((((((s
3.2 EXPERIENCE REPLAY
In an online setting, the collected experience tuples are discarded once they are used for updating the parameters. However, it is difficult for the model to learn from a single update loop. and thus discarding the experience tuples that can be rarely encountered can lead to insufficient training. Ex- perience replay (Lin 1992) is method that uses replay buffer to store experience tuples. A replay buffer is usually implemented with a ring buffer storing a fixed number of the latest experience tuples collected by the behavior policy. When the buffer is full, the oldest experience tuple is discarded and the new tuple is appended. By using the experience tuples repeatedly, experience replay improves the sample efficiency of the training algorithm. The simplest and the most common way of creating a batch a uniform sampling from the buffer. The replay buffer also plays a role in suppressing the temporal correlation of online samples and preventing catastrophic forgetting.
3

---

Under review as a conference paper at ICLR 2023
Algorithm Proposed method with Q-learning
1: Initialize action-value network Q with parameters 0
2: Initialize replay buffer 'D with capacity C'
3: for each time step do
4: Select and execute action ae +- arg max, Q0(
5: Receive reward r; and next state st+1
6: Calculate the pruning priority fTT)) of the experience tuple T
7: i C then
8:
(T f()"min)) & arg (t),),)))))))
9:
if f(rmm)) < f(T) then
D D D f()m()))
11:
Store the experience tuple (7t, (Tx)) into the replay buffer D
12:
end
13:
else
14:
Store the experience tuple (Te, f(T)) into the replay buffer
15:
end if
16:
Sample a batch from
Update with B
18:
Update the priority value in B and return it to D
end for
4 METHOD
In this section, we present our method for prioritizing the experience tuples by their importance and determining the tuples to be retained according to the calculated priority values. This is used to ensure that the number of tuples fits the capacity of the limited-sized replay buffer. Our method will save the memory required and important experience tuples will be sampled much more frequently, which can result acceleration the training. We define the priority calculation function f(r) for experience tuple as follows:
f(T)) w( ae QQ)((T)),
where 8(T) is value based on surprise and w(s,, ag Q) is weight based on the current agents policy calculated using the Q-function. The details the value and the weight will be described in the following sections.
4.1 SURPRISE
Surprise is a measure of how unexpected the experience tuples are for the model. Surprised-bare scores have been used for exploration in reinforcement learning to efficiently find states that are not fully known to the model (Schaul et al. 2016) Burda et al. 2019 Berseth et al. 2021). Prioritizing experience tuples that have high uncertainty and sampling on the weighted distribution have been shown to accelerate training in deep RL (Schaul et al. 2016 Hessel et al. 2018). TD-errors are usu- ally used as the uncertainty measure. The experience tuples with larger errors are more unexpected for the model and can have more room left to learn. In distributed Q-learning TD-errors can be viewed as an approximation of the information gain that can be obtained from the experience tuple
I(Q,T) = E, (Paa(((Q))))))N
~ E, DKL (p(QQupQQuarrre Larget [[p(())) E,]5(T)].
In the second line, we used the assumption that the distribution of the original Q-value given the experience tuple will become close to the target Q-value distribution. This is because the Q-function trained to minimize the difference between the target Q-function using the experience tuple Selecting tuples with a large TD-error will result in choosing tuples that have large information gain.
4

---

Under review as a conference paper at ICLR 2023
1.00
0.75
0.50
0.25
performance
-0.25
DOUD Douo
Bankraest
Doort
Aentsii
towelty
Breshoud
space spacaaliii rocllnoddr
"ers vergeeee
Uer bercek Meroccnaa
Timshial
Choppeccmmin
Boaing
folerra
Selentt
sunn Rubliaitit
Nome contleeoom
len
Koull
Cory Climbos
Rih egDD
ReadRury
End ro
Demonutttack
Bes
Figure 2: The best evaluation performance difference between the proposed method and the baseline method in settings where the replay buffer size is constrained to 10k. The results are normalized by the performance of the unconstrained baseline method.
4.2 ON-POLICYNESS WEIGHT
Selecting experience tuples only from those with large errors will result in unstable training. This because the tuples that are far from the state and action distribution of the current policy tend to have a large error since they are not seen frequently. To overcome this issue, we additionally introduce on-policyness (Fedus al.) 2020) the priority metric. Here, on-polieyness is defined as how much the experience tuple stored in the buffer reflects the current target policy.
The term of on-policyness is important in on-policy RL algorithms where the behavior policy and the target policy need to be the same. common way to satisfy this condition is to constrain the target policy to stay close to the behavior policy (Schulman et al.) 2015 2017). The on-policyness of an experience tuple is also important in off-policy training (Zhang & Sutton [017]] 2017]|auskee Hausknecht &
(toone, [2066] NNovati & Koumoutsakos 2019). To reflect the on-policyness of the experience tuples to the priority values, we propose a weight function in addition to the TD-error:
exp(Q((t, o4))
w( Oz (Q) Σa exp(((xt, a))
This weight function w(s, Q)) reflects how likely the model 8, and can be viewed as a soft Q-policy (Haarnoja et al.) 2017). The weight is always set to when the priority calculated for the first time ensure that every transition will be used least once.
take action o; certain state
At first, we considered using a hard policy for measuring the on-policyness. The weight function with a hard policy returns if the action taken in the experience tuple matches the action that maximizes the Q-value on the state s in the experience tuple, and returns small value for tuples containing other actions. This approach is similar the action probability distribution of an epsilon- greedy policy. However, using soft weights performed slightly better in the initial experiments, so we did not use the hard policy for evaluation.
4.3 OVERALL ALGORITHM
The overall algorithm is shown in Algorithm 1 In our algorithm, the priority of each experience tuple is calculated with the function explained above. A priority value f(Ti) for pruning experience tuples is calculated after the experience т, is sampled from the environments. We add the priority value to the tuple (Tr, ff)) stored in the buffer. The priority values of tuples are updated only when they sampled create minibatch.
5

---

Under review as a conference paper at ICLR 2023
BattleZone
CrazyClimber
100000
20000
80000
80000
15000
60000
reward
60000
10000
40000
40000
20000
5000
20000
1.0
0.4
1.0
1e6
1e6
1e6
Enduro
Qbert
RoadRunner
600
15000
20000
reward
10000
0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
steps
1e6
steps
1e6
steps
1e6
Baseline (1M)
SEER
Exploration+S (10k)
Baseline (10k)
Surprise+ (10k)
Ours (10k)
Comparison of the cumulative rewards in constrained memory settings. The solid line and shaded regions represent the mean and standard deviation, respectively, across five random seeds.
Figure 3:
The process of experience selection is executed when the buffer is full and experience tuple arrives. The tuple with the minimum priority value is discarded. These priority values are used and calculated independently of the ones used in PER. We also considered selecting tuples stochastically instead of selecting them deterministically but found it difficult to adjust the hyperparameters to provide appropriate weighting select the tuples.
EXPERIMENTAL RESULTS
5.1 EXPERIMENTAL SETTINGS
We conducted experiments on 52 Atari (Bellemare et al. 2013) games to investigate the efficacy of our method. Atari a set of commonly used benchmark environments for visual discrete control. contains 57 games in total. In our experiments, we used 52 out of 57 environments. We excluded five games from the evaluation because they only provide sparse rewards or require a significant amount of exploration. Those environments any constraint, and since our method does not promote exploration before the bascline algorithm receives initial reward signal from the environments, considered them not appropriate for comparison purpose.
challenging even for the baseline algorithm without
We trained agent using the Rainbow (Hessel al. 2018) algorithm for 1M training steps with the buffer size constrained to 10k. We ran experiments and compared our methods with the follow- ing experience selecting approaches. Baseline: discards the experience tuples in the First In First Out (FIFO) manner. Surprise+S (de Bruin et al. 2018): chooses the experience tuples stochas- tically using the same sampling method as PER. The sampling priority is based on the inverse of the TD-error 8(T). This sampling makes tuples with a small TD-error more likely to be discarded. Exploration+S (de Bruin et al. 2018): chooses the experience tuples with rare actions. The orig- inal implementation used action probabilities which cannot be directly used for Rainbow training. Instead, we used the sampling priority based on soft-policy metrics and sampled the tuples stochas- tically in the same way as PER. This sampling makes the tuples with rare actions stay longer in the buffer. In addition to these experience selection methods, we added results using SEER (Chen) et al. 2021), which is data compression method. We also experimented with the setting where no constraints are placed on the buffer size the baseline method to show the upper bound of the performance. The details of the model architecture and hyperparameters shown in Appendix

---

Under review as a conference paper at ICLR 2023
BattleZone
CrazyClimber
80000
80000
15000
reward
60000
60000
10000
40000
40000
20000
5000
20000
0.0
0.2
0.4
0.8
1.0
0.0
0.2
0.4
0.8
1.0
0.0
0.2
0.4
0.8
1.0
leb
Le6
1e6
Enduro
RoadRunner
600
10000
8000
400
20000
reward
6000
200
10000
4000
2000
0.0
0.2
0.4
0.8
1.0
0.0
0.2
0.4
0.8
1.0
0.0
0.2
0.4
0.8
1.0
le5
steps
1e6
1e6
Surprise + on po-plliccness
Surprise
On palicyness
Figure 4: Comparison of the cumulative rewards when each factor was removed from the priority calculation function in constrained- memoryy settings. The solid line and shaded regions represent the mean and standard deviation, respectively, across five random seeds. The dotted line shows the best mean score of the bascline method in the constrained setting.
We run experiments on five random seeds for each environment. The performance of the agent on each seed is evaluated by taking the mean cumulative reward of five evaluation episodes every 10k training steps.
5.2 RESULTS
We summarize the performance in each Atari environment in Figure We found that our experience selection method suppresses the degradation of the agent performance when the size of the replay buffer is limited. In 39 out of the 52 environments, from the baseline results. Figure3Jshows shows comparison with the other experience selection methods. The proposed method outperformed the prior experience selection methods and achieved compara- ble results to the unconstrained baseline in most of the environments. In some environments, such as RoadRunner, the proposed method even accelerated the training compared to the unconstrained baseline. The proposed method showed low performance in environments where the methods that put more weights on exploration had better scores. We provide all the learning curves and the best performance score of the baseline and the proposed method for the Atari environments in Appendix Fland Appendix H
proposed method has shown improvement
5.3
ABLATION STUDIES
5.3.1
COMPONENT ANALYSIS
We also experimented on six Atari environments with only one component the priority metrics, i.e. surprise on-policyness, to investigate the contribution of each factor. The results are shown Figure | indicating that both components contributed to the final performance. Overall, the performance decrease was larger when the on-policyness metric was removed from the priority function. For four out of the six environments, Atlantis, BattleZone, Defender, and RoadRunner, enough to obtain the final results. In Enduro, removing the
using the on-policyness metric surprise factor slowed down the learning speed, even though using the surprise alone showed a relatively small improvement in performance.

---

Under review as a conference paper at ICLR 2023
Beseine (1:0
25
50
(1M)
25
50
-25
-50
-50
Beseline (10K)
125
-100
Baseline
-50
-50
0.30
50
120K)
25
0.25
(10k)
0
-25
50 50
50
-50
0
50-50
50-50
200000 steps
500000 steps
1000000 steps
steps
500000 steps
1000000 steps
(a) BattleZone
(b) RoadRunner
Figure 5: Comparisons of latent state distributions of images stored in the replay buffer certain training steps visualized by t-SNE Van der Maaten & Hinton 2008). The color of the points is determined by the cumulative discounted reward the agent received within the transition.
5.3.2 STATE DISTRIBUTIONS
We plotted the distributions of the latent state representations with t-SNE (Van der Maaten & Hinton 2008), to analyze the state distributions of the experience tuples stored in the replay buffer. We also added the reward obtained during the transition in the experience tuple to the plot. We used the replay buffer from the unconstrained baseline, constrained baseline, and constrained proposed, which are the same as the ones shown in Section 5.2. The snapshots of the replay buffer were taken from every 100k training steps and all the transitions in the buffer were used for the constrained settings. As for the unconstrained settings, we used the states observed in between (100kxi + 90k) ~ (100k x 1)) (i = 0, 1, 99) training steps. We converted the image state observations into latent representations by using the CNN encoder module from the unconstrained baseline model after IM training steps. Thus, the latent representations of the observation from different experiment settings share the same latent space in the plotted results.
The results are shown in Figure 5 keeps tend to have larger returns during the transitions than the bascline methods. In Figure [a observed that the proposed method has a relatively higher coverage of state space compared to the baseline with buffer size of 10k throughout the training. The state distribution of the final training steps in Figure 5bb shows that the states are densely distributed in space where the baseline with constraint has relatively small amount of samples.
We can see that the state transitions that the proposed method
5.3.3 LONGER SETTING
We conducted experiments to examine whether our method would have an advantage in standard off-policy training. We examined this by using the experience selection metries on setting where the buffer size is set to 1M, which is a common size used for the replay buffer in off-policy train- ing (Mnih et al. 2015 Schaul et al. 2016 Hessel al. 2018). Since our experience selection is performed when there is space left in the buffer, we trained the agents for 10M in each environ- ment. We used six environments from Atari in total for this experiment. We select five environments where the proposed method performed well, and one environment where the proposed method did not show much improvement. These environments have a common property that a smaller buffer size reduces the performance of the agents.
We see a significant drop in performance for BattleZone and Qbert after around 1M steps of the training. This suggests potential negative effects of our method during a long training period. We will discuss this in detail in Section 6 The proposed method and the baseline performed almost equally well for CrazyClimber and RoadRunner. In Enduro and
The results are shown in Figure 6
8

---

Under review as a conference paper at ICLR 2023
BattleZone
CrazyClimber
Defender
30000
00000
80000
reward
20000
60000
6000
10000
40000
4000
20000
2000
0
0.0
0.2
0.4
0.8
1.0
0.0
0.2
0.4
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
le7
le7
le7
Enduro
Obert
RoadRunner
40000
1000
15000
30000
750
rewain
10000
500
20000
250
5000
10000
0
0.0
0.2
0.4
0.8
1.0
0.0
0.2
0.4
0.8
1.0
0.0
0.2
0.4
0.8
1,0
1e7
steps
1e7
1e7
Baseline (1M)
Ours (1M)
Figure 6: Comparison of the cumulative rewards with and without the proposed method when the buffer size is set to M.. The solid line and shaded regions represent the mean and standard deviation, respectively, across five random seeds. The curves are smoothed with moving average of 10 to improve readability.
Defender, the proposed method showed some positive effects. The former showed some accelcration in learning, while the latter showed smaller decline in performance.
6 LIMITATION AND DISCUSSION
In this paper, proposed method select experience tuples during training. The method suc- cessfully prevents the degradation of performance when the capacity of the replay buffer size is limited. The surprise promotes the buffer to store experience tuples that have large uncertainty and on-policyness ensures that the tuples are tied to the current policy of the agent.
One limitation of our work is the low performance of the agent in long-term training. Although using TD-errors as an indicator of learnability is reasonable to some extent, it can have negative effects when the agent trained for large number of time steps. For example, the training proceeds and the overall loss decreases, the influence of the states with large loss but with small novelty will increase. For example, the initial states of episodes can have high TD-errors because the return of an episode can vary depending on the trials. Although the on pe-polcccyess metric can reduce the effect of out-o--distribution experiences, the agent can easily fall into local optima when the diversity of the data is lost. As result, the combination of these two metrics has the vulnerability to make the state distribution converge to a small area in the state space. This makes the transition the replay buffer highly biased. A simple example of this case is shown in Appendix B One potential solution may be to ensure the diversity of states and actions stored the replay buffer to some extent.
CONCLUSION
We proposed a technique to save the memory consumption of a replay buffer by using estimated importance of the experiences. Our technique is based on the idea that the importance of experiences can be estimated using the TD-errors and the closeness to the decision made by the current target policy. Our experiments demonstrated that using our method of experience retention can reduce the negative effects of a limited-size buffer. We expect that our proposed method makes RL training more applicable to low-resource environments.

---

Under review as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
We provide detailed descriptions our experimental setups and implementations in Section 3.1 and Appendix A
We also provide the source code in the supplementary materials.
REFERENCES
Rahaf Aljundi, Min Lin, Baptiste Goujaud, and Yoshua Bengio. Gradient based sample selection for online continual learning. Advances in neural information processing systems, 32, 2019.
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.
Mare G Bellemare, Will Dabney, and Rémi Munos. distributional perspective reinforcement learning. In International Conference on Machine Learning, 449-458, PMLR, 2017.
Glen Berseth, Daniel Geng, Coline Manon Devin, Nicholas Rhinehart, Chelsea Finn, Dinesh Ja- yaraman, and Sergey Levine. SMiRL: Surprise minimizing reinforcement learning in unstable environments. In International Conference on Learning Representations, 2021.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. In International Conference on Learning Representations, 2019.
Lili Chen, Kimin Lee, Aravind Srinivas, and Picter Abbeel. Improving computational efficiency in visual reinforcement learning via stored embeddings, Advances in Neural Information Processing Systems, (44267799-2699) 2021.
Will Dabney, Mark Rowland, Mare Bellemare, and Rémi Munos. Distributional reinforcement learning with quantile regression. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 32, 2018
Tim de Bruin, Jens Kober, Karl Tuyls, and Robert Babuška. Off-policy experience retention for deep actor-critic learning. In Deep reinforcement learning workshop, NIPS, 2016a.
Tim de Bruin, Jens Kober, Karl Tuyls, and Robert Babuška. Improved deep reinforcement learning for robotics through distribution-bart based experience retention. In 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 3947-3952, 2016b. doi: 10.1109/
IROS.2011 2016.7755...
Tim de Bruin, Jens Kober, Karl Tuyls, and Robert Babuska. Experience selection in deep reinforce- ment learning for control. Journal of Machine Learning Research, 19, 2018.
William Fedus, Prajit Ramachandran, Rishabh Agarwal, Yoshua Bengio, Hugo Larochelle, Mark Rowland, and Will Dabney. Revisiting fundamentals of experience replay. In International Con- ference Machine Learning, pp. 3061-307 PMLR, 2020.
Robert M. French. Catastrophic forgetting in connectionist networks. Trends in Cognitive Sciences, 3(4):128-1355 1999. ISSN 1364-6613.
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.
Yasuhiro Fujita, Prabhat Nagarajan, Toshiki Kataoka, and Takahiro Ishikawa. Chainerrl: A deep reinforcement learning library. Journal of Machine Learning Research, 22(77):1-14, 2021.
Ian Goodfellow, Mehdi Mirza, Da Xiao, Aaron Courville, and Yoshua Bengio. An empiri- cal investigation of catastrophic forgetting in gradicnt- neural networks. arXiv preprins 112iv:1112.6211 2013.
Tuomas Haarojja, Haoran Tang. Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep energy-based policies. In International conference on machine learning, pp. 1352-1361. PMLR, 2017.
10

---

Under review as a conference paper at ICLR 2023
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International confer- on machine learning. pp. 1861-1870. PMLR, 2018.
Matthew Hausknecht and Peter Stone. On-policy vs. off- updates for deep reinforcement learning. In Deep Reinforcement Learning: Frontiers and Challenge. IJCAI, 2016.
Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. In Thirty-second AAAI conference on artificial intelligence, 2018.
David Isele and Akansel Cosgun. Selective experience replay for lifelong learning. In Proceedings of the AAAI Conference on Artificial Intelligence, 2018.
Laurent Itti and Pierre Baldi. Bayesian surprise attracts human attention. In Advances in Neural Information Processing Systems, volume 18. MIT Press, 2005.
Dmitry Kalashnikov, Alex Irpan, Peter Pastor, Julian Ibarz, Alexander Herzog, Eric Jang, Deirdre Quillen, Ethan Holly, Mrinal Kalakrishnan, Vincent Vanhoucke, et al. Scalable deep reinforce- ment learning for vision-based robotic manipulation. In Conference on Robot Learning, pp. 651- 673. PMLR, 2018.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In International Conference on Learning Representations, 2015.
Timothy P. Lillicrap. Jonathan Hunt, Alexander Pritzel, Nicolas Manfred Otto Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learn- ing. CoRR, abs/1509, 109.097,,, 2016.
Longxin Lin. Self-improving reactive agents based on reinforcement learning, planning and teach- ing. Machine Learning, 8:293-321, 1992.
Ruishan Liu and James Zou. The effects of memory replay in reinforcement learning. In 2018 56th annual allerton conference on communication, control, and computing (Allerton), pp- 478-488-85 485. IEEE, 2018.
David Lopez-Paz and Mare' Aurelio Ranzato. Gradient episodic memory for continual learning. Advances in neural information processing systems, 30, 2017.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Mare G. Belle- mare, Alex Graves, Martin A. Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wier- stra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518:529-533. 2015.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International conference machine learning, pp. 1928-1931 PMLR, 2016.
Guido Novati and Petros Koumoutsakos. Remember and forget for experience replay. Interna- tional Conference on Machine Learning, pp. 4851-4860. PMLR, 2019.
Youngmin Oh, Kimin Lee, Jinwoo Shin, Eunho Yang, and Sung Ju Hwang. Learning to sample with local and global contexts in experience replay buffer. In International Conference on Learning Representations, 2021.
Mathijs Pieters and Marco A Wiering. Q-learing with experience replay in dynamic environment. 2016 IEEE Symposium Series on Computational Intelligence (SSCI), pp. 1-8, 2016.
Sylvestre-AINe Alvise Rebuffi, Alexander Kolesnikov, Georg Sperl, and Christoph H Lampert. icarl: Incremental classifier and representation learning. In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pp. 2001-2010, 2017.

---

Under review as a conference paper at ICLR 2023
David Rolnick, Arun Ahuja, Jonathan Schwarz, Timothy Lillicrap, and Gregory Wayne. Experience replay for continual learning. Advances in Neural Information Processing Systems, 32, 2019.
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. In- ternational Conference on Learning Representations, 2016.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pp. 1889-1897. PMLR, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: (xXiv:777700347,, 2017.
Hanul Shin, Jung Kwon Lee, Jaehong Kim, and Jiwon Kim. Continual learning with deep generative replay. Advances in neural information processing systems, 30, 2017.
Samarth Sinha, Jiaming Song, Animesh Garg, and Stefano Ermon. Experience replay with likelihood-free importance weights. Proceedings of The 4th Annual Leurning for Dynamics and Control Conference, volume 168, pp. 110-123. PMLR, 2022.
Peiquan Sun, Wengang Zhou, and Houqiang Li. Attentive experience replay. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04):5900-559 59000005-977440 Apr. 2020.
Shengyang Sun, Daniele Calandriello, Huiyi Hu, Ang Li, and Michalis Titsias. Information- theoretic online memory selection for continual learning. International Conference on Learning Representations, 2022.
Saran Tunyasuvunakool, Alistair Muldal, Yotam Doron, Siqi Liu, Steven Bohez, Josh Merel, Tom Erez, Timothy Lillicrap, Nicolas Heess, and Yuval Tassa. dm_control: Software and tasks for continuous control. Software Impacts, 6: 100022, 2020. ISSN 2665-9638.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9111), 2008.
Ziyu Wang, Tom Schaul. Mattco Hessel, Hado Hasselt, Mare Lanctot, and Nando Freitas. Dueling network architectures for deep reinforcement learning. In International conference on machine learning, pp. 1995-2003, PMLR, 2016.
Christopher Watkins and Peter Dayan. Q-learning Machine Learning, 8:279-292, 1992.
Denis Yarats, Rob Fergus, Alessandro Lazarie, and Lerrel Pinto. Mastering visual continuous trol: Improved lugmened reinforcement learning. arXiv preprins arXiv:2107.09645 2021.
Daochen Zha, Kwei-Herng Lai, Kaixiong Zhou, and Xia Hu. Experience replay optimization. In- ternational Joint Conference on Artificial Intelligence, 2019.
Shangtong Zhang and Richard Sutton. deeper look at experience replay. arXiv preprint arXiv: 1712.01775 2017.
12

---

Under review as a conference paper at ICLR 2023
A TRAINING DETAILS
The model architecture we used based on the PFRL (Fujita et al. 2021) implementation of Rain- bow algorithm. The length of each episode is 108k frames maximum. The list of hyperparameters is shown in Table[]
Table 1: Parameters for Atari experiments
Parameter
Value
Batch size
32
Number of updates per training steps
1
Target update steps
2000
Replay start size
1000
Noisy net sigma
0.5
Observation size
(4, 84, 84)
Reward clipping
True, [-1.0, 1.0]
Discount rate
0.99
Action repetition
4
Learning rate
le-4
Optimizer
Adam (Kingma & Ba 2015
Max gradient norm
10
Multi-step length
5
For experiments using SEER (Chen et al. 2021), we froze the CNN encoder at 100k training steps. The initial size of the replay buffer 10k and the capacity is increased by factor of 2.25 after the CNN encoder is frozen and the observation states are stored as latent vectors. This is the exact gain that the replay buffer obtains when the 4x84x84 sized 8 bits int image observations are converted to 3136 length 32 bits float vectors.
B ANALYSIS OF FAILURE CASE IN MOUNTAIN CAR
We show some possible cases of failure using the proposed method in MountainCar-vo, In suc- cessful cases, the state action distribution of the tuples in the replay buffer will form cireular curves shown in Figure X The curve starts from the center and ends at the top-right which refers to the bottom of the valley and the top of the hill in Figure 7
We analyzed the state action distributions of tuples at the early and late stages of training from the failure cases using the surprise and the on-policyness metrics. At the early stage of training, surprise promoted the tuples to spread throughout the state space (Figure 9ap. However, after the models are trained to some extent, the tuples start to gather at the area which is the initial position of the cart in the episodes (Figure TOa). This is because, at certain point of training, the TD-errors from the novel states become smaller than the ones at the initial states where the variance of Q-values is relatively high throughout the training. We also found that the tuples selected by the on-policyness metrics can get biased, especially toward the tuples that selected the action "right" (Figure (b). This due to the fact that taking an action "right" on top the hill tends to have relatively high Q-values compared with other actions and makes the on-policyness weight large. This also resulted in the transitions taken near the goal seen the early stage remaining until the late stage of the training 10b). In addition, the tuples that were collected by the on-policyness metric had possibility to form cluster when the Q-value of a certain action became significantly high compared to other actions. As result, the combination of surprise and on- on-policyness result in convergence to small area in the state space and little action diversity making the policy collapse (Figure 10c).
13

---

Under review as a conference paper at ICLR 2023
Figure 7: Appearance of MountainCar-v0
Figure 8: State action distribution of tuples in the FIFO replay buffer
037
Mi
(a) Surprisc
(b) On-policyness
(c) Surprise On on-policssesss
Figure 9: State action distribution of tuples stored in the replay buffer at the early stage of training when using the specific pruning strategy in MountainCar-vO.
C APPLICATION TO DOMAINS WITH CONTINUOUS ACTION SPACE
The surprise term be used for most off-policy algorithms. On the other hand, the on-policyness metric which needs to calculate the softmax values across possible actions at a certain state cannot be directly used in domains with continuous action space. One possible approach would be to use the action probability that calculated Actor-Critic methods (Lillicrap et al. 2016 Haarnoja al. 2018) since the on-policyness metric resembles the soft Q-policy.
In such a case, assuming that the action probability distribution is given as a normal distribution, the on-policyness weight can be written
w(st, a,) [N(aaa
The a can be either the one used in the current target policy or fixed value. We observed that avoid- ing a small value for a when calculating the on-policyness would have slightly better performance. We set to throughout the training when calculating the on-policyness.
We evaluated this simple modification on Deepmind Control Suite (Tunyasuvunakool et al. 2020 We used DrQv2 Yarats et al. (02T)) as the RI. algorithm and constrained the replay buffer size to 2k, which the minimum size without changing the original exploration steps. The hyperparameters except for the replay buffer size were kept the same as in the original implementation. The results are shown Figure We saw improvements from baseline results on most of the domains we tested
14

---

Under review as a conference paper at ICLR 2023
601
080
600
4.3
-00
(a) Surprise
(h) On-policyness
(c) Surprise + On-policyness
Figure 10: State action distribution of tuples stored in the replay buffer at the late stage of training when using the specific pruning strategy in MountainCar-vO.
acrobot swingup
cartpole swingup
cartpole swingup sparse
cheetah run
1000
400
750
750
500
500
200
250
250
0-
0.00
0.25
0.50
0.75
1.00
cup catch
1o6
finger spin
166
finger turn easy
finger turn hard 06
1000
1000
750
500
500
500
500
250
0
0
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
hopper hop
le6
quadruped run
le6
quadruped walkles
reach duplo
1e6
800
200
200
600
500
100
100
0:
reacher easy
1e6
reacher hard
1e6
walker run
le8
walker walk
1e6
1000
800
1000
750-
600
750
500
500
400
500
250
200
0
0.00
0.25
0.50
0.75
1.00
1e6
1e6
lee
leo
Baseline
Figure 11: Comparison of the cumulative rewards with and without the proposed method when the buffer size is constrained to 2k. The solid line and shaded regions represent the mean and standard deviation, respectively, across five random seeds.
D DETERMINISTIC SELECTION VS STOCHASTIC SELECTION
Our proposed method deterministically selects the tuples to discard by selecting the tuple with the minimum priority value. However, this process be modified stochastic procedure by using the inverse of the priority value as the sampling priority. The results of the comparisons are shown in Figure [2] Applying stochastic sampling to the proposed method caused decrease in the perfor- mance in most of the environments. However, there were some environments where the stochastic sampling improved the performance. Those were the environments where the deterministic pro- posed method performed worse than the baseline. In addition, stochastic sampling had some effect on reducing the loss throughout the training.
15

---

Under review as a conference paper at ICLR 2023
Alien
Amidar
Mlannis
Banloteist
2000
10000
1000
1500
75000
reverd
400
1000
50000
200
25000
BettleZone
BeamRider
CrazyClimber
Defender
3000
20000
10000
75000
reword
15000
10000
50000
6000
5000
1000
25000
4000
0
2000
0.0
0.2
0.4
0.6
0.8
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
DemonsAttack
leb
Enduro
1e6
Frostbite
1e6
Krlll
1e6
2000
3000
400
rewara
2000
2000
200
1000
0.0
0.2
0.0
0.2
0.6
0.0
0.2
0.4
Phoenix
Obert
RoadRunner
Rebocank
15000
20000
r2ward
10000
2000
5000
10000
5
0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
1e5
1.6
1e6
1e6
Seaquest
Venture
Zaxzan
6000
600
1000
Worl
4000
14
400
500
200
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
0.8
steps
steps
Stegs
Beseline (1M)
Deseline (10k)
Ours
Ours+5 (10k)
Figure 12: Comparison between the performance of deterministic and stochastic selection of the tuples. The solid line and shaded regions represent the mean and standard deviation, respectively. across five random seeds.
TEMPERATURE TO SOFT-POLICY METRIC
We investigated the sensitivity of the on-policyness metric by changing the temperature parameter 3. Q-value is multiplied by the temperature parameter 3 before applying the softmax function when calculating the on-policyness. The results are shown in Figure [3 The setting with = the same as the setting where the priority value is calculated only from surprise. We saw a slight change in the performance for most the environments when the temperature parameter was scaled.
16

---

Under review as a conference paper at ICLR 2023
BattleZone
CrazyClimber
80000
80000
reward
60000
10000
40000
20000
5000
20000
0.0
0.2
0.4
0.8
1.0
0.0
0.2
0.4
0.8
1.0
0.0
0.2
0.4
0.8
1.0
le6
1c6
1c6
Enduro
RoadRunner
12500
600
10000
20000
reward
7500
200
10000
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
1c6
1c6
1c6
8 10.0
#=100
== 0.1
0.0
Figure 13: Cumulative rewards with various temperature values. The solid line and shaded regions represent the mean and standard deviation, respectively, across five random seeds.
F FULL RESULTS ON ATARI ENVIRONMENTS
The learning curves of the comparison between prior methods are shown in Figure 14 The learning curves of 52 environments we experimented on are shown in Figure
G SMALLER BUFFER SETTINGS
We also experimented Atari on settings where the size of the replay buffer is constrained to 1k, which is one-tenth the size of the original constrained setting. All the other hyperparameters except for the buffer size were kept the same as Section The results are shown Figure [6.
H BEST PERFORMANCE RESULTS
We show the mean best performance the results shown Apeendix and Appendix G in Table
17

---

Under review as a conference paper at ICLR 2023
Amidar
2000
100000
600
1500
75000
reward
400
50000
200
25000
500
8.0
0.0
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
leb
1e6
1e6
BankHeist
BattleZone
BeamRider
20000
1000
reward
15000
2000
500
10000
1000
5000
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
CrazyClimber
Defender
DemonAttack
10000
75000
3000
reward
7500
50000
5000
25000
1000
2500
0.0
0.2
0.4
0.8
1.0
0.0
0.2
0.4
0.8
1.0
0.0
0.2
0.4
0.8
1.0
Enduro
leb
Frostbite
1e6
Krull
1eb
3000
400
reward
2000
200
1000
0.2
0.2
0.2
le6
le6
le6
Phoenix
Qbert
RoadRunner
15000
4000
20000
10000
2000
10000
5000
0.0
0.2
0.4
0.8
1.0
0.0
0.2
0.4
0.8
1.0
0.0
0.2
0.8
1.0
1e6
1e6
1e6
Robotank
Seaquest
Venture
1000
600
reward
20
400
500
200
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Zaxxon
1c6
steps
1c6
steps
1c6
6000
rewaro
4000
Baseline (1M)
Surprise+S (10k)
Baseline (10k)
Exploration+5 (10k)
2000
SEER
Ours (10k)
0.0
0.2
0.4
0.6
0.8
1.0
stops
le5
Figure 14: Comparison the cumulative rewards in constrained-memory settings. The solid line and shaded regions represent the mean and standard deviation, respectively, across five random seeds.
18

---

Under review as a conference paper at ICLR 2023
Amidar
Asterix
Asteroids
17
2000
2503
1500
2003
1030
750
1000
905
Atlantis
BankHeeist
BettleZone
BeamRidde
Berzerk
3020
75030
5000
2020
50000
500
ocon
20000
Bowliig
Boxing
Breakout
Centipede
ChopperCommaand
00co
J503
1003
2020
CrazyClimber
Defender
DemonAttack
DoubleDunk
Enduro
20000
2000
aoo2
50030
2000
E002
4002
2000
FishingDebby
Freeway
Frostbite
Gopher
Gravitar
-40
3000
2000
10
J0p
-100
Hero
ketlockey
Jamesbond
Kangaroo
Krull
15000
0003
10000
200
5000
1000
2003
FuMasterr
MsPacman
NameTThssGan ThisGame
Phoenix
Pong
15000
10020
5000
2000
1800
2000
Obert
Riverraid
RoadRunner
Robotank
Seaquest
5000
4000
50000
5000
2000
1000
Solaris
Spaceinvaders
StarGunner
Tennis
TimePilot
6030
2000
1000
202
500
-20
2003
Tutankham
Downown
Venture
VideoPinbell
Wizerdo/Wor
1.50
2000
2000
BooDD
100
coo2
0003
4000
500
50
10000
2002
Revenge
160
5000
15000
Baseline (1M) Baseline (10k)
4000
10000
2000
(10k)
0.
03
2A
0.6
0.
3.0
54
02
04
0.
0.5
Figure 15: Comparison of the cumulative rewards with and without the proposed method when the buffer size is constrained 10k. The solid line and shaded regions represent the mean and standard deviation, respectively, across five random seeds.
19

---

Under review as a conference paper at ICLR 2023
Amidar
Asteroids
2503
1500
1:00
2002
1020
1000
1020
500
300
Atlantis
BankcHeiss
BettleZone
BeamRider
Berzerk
3000
1000
15900
2000
50000
500
0000
25000
5000
203
Bowling
Boxing
Breakout
Centipede
ChopperCommmand
50
2303
400D
2003
2010
CrazyClimber
Defender
DemonAttack
DoubleDunk
Enduro
L0000
13000
2000
-10
30030
5000
1000
DishingDerby
Freeway
Frostbite
Gopher
Gravitar
-70
3000
20
1000
-50
S00
1.00
Hero
keHlockey
Jamesbond
Kangaroo
Krull
1000
10000
0003
15000
10000
500
6003
5000
250
4000
2003
Kungf FuMaster
MsPacman
Name ThisGame
Phoenix
Pong
15000
30000
2000
3000
0030
2000
2000
Obert
Riverraid
RoadRunner
Robotank
Seaquest
40000
4000
Solaris
Spaceinvaders
StarGunner
Tennis
TimePilot
6030
1500
4030
602
1000
500
20
Tutankham
UpN Down
Venture
VideoFinbell
WizardofWor
1.3
2002
2000
500c0
4000
500
10000
1003
Revenge
160
35000
5000
Baseline (1M)
4000
Baseline
5000
(1k)
0.
03
24
0.6
0.8
3.0
54
02
04
0.
0.5
Figure 16: Comparison of the cumulative rewards with and without the proposed method when the buffer size is constrained to 1k. The solid line and shaded regions represent the mean and standard deviation, respectively, across five random seeds.
20

---

Under review as a conference paper at ICLR 2023
Table 2: Raw mean best scores of 52 games in Atari. results show the mean of five random
seeds, and the best results constrained settings are indicated bold.
Game
Baseline (IM)
Baseline (10k)
Baseline (1k)
Ours (10k)
Ours (Ik)
Alien
1530.0
1475.2
1275.6
1974.4
1620.0
Amidar
515.2
357.8
131.0
276.6
195.8
Assault
865.6
1108.3
959.9
1067.5
1399.0
Asterix
1680.0
1544.0
1062.0
1890.0
1330.0
Asteroids
1593.2
1097.6
918.4
1454.0
1450.4
Atlantis
75500.0
29328.0
41068.0
79336.0
40276.0
BankHeist
748.4
895.6
62.0
604.4
250.0
BattleZone
20720.0
13800.0
9480.0
19240.0
23080.0
BeamRider
3110.8
926.2
900.6
1545.4
1054.7
Berzerk
843.2
754.8
574.8
796.0
760.0
Bowling
72.0
70.0
65.8
69.1
79.8
Boxing
12.6
6.8
8.3
28.0
34.0
Breakout
60.4
63.5
21.4
62.8
42.8
Centipede
5951.4
5985.1
7608.5
6497.5
6724.8
ChopperCommand
1664.0
1676.0
1660.0
1876.0
1972.0
CrazyClimber
89072.0
49372.0
43988.0
92172.0
35508.0
Defender
10026.0
5946.0
5242.0
9864.0
6500.0
DemonAttack
2669.2
825.4
762.4
3523.8
1590.4
DoubleDunk
- -13.7
-8.1
-8.3
- -4..8
-10.7
Enduro
509.0
124.2
153.7
600.5
419.0
FishingDerby
63.3
-75.2
-77.0
- -3.33
-72.6
Freeway
33.1
31.9
31.0
31.3
30.3
Frostbite
3350.0
841.6
764.8
1456.4
922.8
Gopher
1662.4
1048.0
1303.2
2024.8
1059.2
Gravitar
826.0
556.0
560.0
620.0
424.0
Hero
17533.2
13727.4
10981.8
14478.2
5717.2
IceHockey
-1.5
-4.7
-3.7
-4.4
-1.8
Jamesbond
532.0
498.0
476.0
472.0
1006.0
Kangaroo
8296.0
4844.0
632.0
1920.0
4660.0
Krull
4850.7
4201.4
5451.6
6125.8
8266.0
KungFuMaster
14136.0
15920.0
15372.0
18940.0
13312.0
MsPacman
2555.6
2419.6
1898.4
2564.4
2205.6
Name TameThisGame
4356.4
3994.8
3872.8
5288.8
3582.0
Phoenix
4658.8
2234.0
2004.4
4184.0
2389.6
Pong
21.0
20.4
19.8
20.9
12.4
Qbert
15897.0
9170.0
4059.0
6143.0
3854.0
Riverraid
4700.0
3860.0
3716.0
3832.8
3364.8
RoadRunner
20636.0
9600.0
11036.0
26224.0
25396.0
Robotank
19.0
13.5
15.1
15.6
16.2
Seaquest
764.0
676.0
631.2
628.0
684.0
Solaris
7211.2
4392.0
4989.6
5923.2
4156.8
SpaceInvaders
698.8
646.2
503.4
659.4
544.6
StarGunner
1764.0
1228.0
968.0
2124.0
1556.0
Tennis
-0.6
-0.9
-3.8
-0.8
-3.5
TimePilot
6132.0
5120.0
4936.0
5700.0
4644.0
Tutankham
159.8
118.0
29.4
117.3
64.7
UpNDown
7832.8
5956.8
4489.2
6098.8
3862.8
Venture
1008.0
132.0
20.0
736.0
128.0
VideoPinball
21752.4
25910.8
22330.6
29800.7
14075.8
WizardOfWor
2740.0
1768.0
1504.0
3024.0
2348.0
RersRevenge
16454.1
16819.3
16543.5
17399.0
16692.9
Zaxxon
6412.0
3412.0
672.0
4864.0
3584.0
21


Reviews:
[{"review_id": "mhx30sY-Tc", "reviewer": "Reviewer_FE4B", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper aims to make off-policy RL algorithms more memory-efficient by reducing the size of the experience replay buffer. Specifically, the proposed algorithm keeps experience tuples with higher importance and discards unimportant ones. The importance of a tuple is measured by its \"surprise\" (TD error) and \"on-policyness\". Experimental results in Atari games show that the proposed algorithm achieves comparable performance with only 1% size of the original replay buffer, compared with the baseline method (Rainbow).", "summary_of_the_review": "Overall, this paper is well-motivated, focusing on an important problem. However, the performance drop of longer training limits the application of the proposed method. I believe this paper can be further improved with more analytical experiments in toy tasks.", "strength_and_weaknesses": "The paper is well-motivated and the writing is really good. The proposed method is indeed much more memory-efficient than Rainbow in Atari games when agents are trained with 1M steps.\n\nHowever, as also pointed out by the authors, when agents are trained longer (10M steps), the proposed algorithm actually performs much worse than the baseline in some tasks, even using a replay buffer with the same size as the one in baseline. The discussion of the limitation in Section 6 is not convincing or not supported by experiments. This paper can be much better if further experiments are conducted to show and analyze the limitation of instability with longer training. Moreover, a study of the affect of different buffer sizes (e.g., 1k, 10k, 100k, 1M) is necessary in order to see the whole picture.\n\nMinor issues and questions:\n- In Section 4.3, the function $f^{priority}$ is not defined.\n- In Figure 5(a), it seems that the state coverage of the proposed method (with 10K samples) is much better than the baseline (with 1M samples). How is it possible? Or maybe I interpret it incorrectly.\n- In Algorithm 1, will all priority scores in the replay buffer be recomputed after the Q function is updated? If so, will this slow down the training process? Can you show the wall-clock training time? If not, since the priority calculation function depends on the current Q value function, the pseudo-code hints that all priority scores in the replay buffer are recomputed, as shown in Line 8 & 11. It might be better to replace $f(\\tau)$ with some other symbol to show that the scores are not recomputed in Line 8 & 11.\n\nSuggestions\n- Instead of moving straight to Atari games, conducting experiments in toy environments might provide more insights. For example, no results are presented to support the claim that \"The surprise promotes the buffer to store experience tuples that cover the state space\" in Section 6. This claim can be better verified in low-dimensional tasks, such as Mountain Car.\n- My personal experience suggests that a less frequent update for Q function helps improve agent performance when the replay buffer is small.\n- In Figure 4, it seems that adding \"surprise\" is not that helpful and \"on-policyness\" is main reason for performance improvement. Did you try removing \"surprise\" (thus reduce negative effects as mentioned in Section 6) and redo the experiments in Figure 6?\n- Some methods listed in this [paper](http://arxiv.org/abs/1809.05922) might help to improve the performance of the proposed algorithm, such as reservoir sampling.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "dJ0jJeQsf_c", "reviewer": "Reviewer_HQEE", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper introduces a mechanism for selecting transitions to remove/replace from the replay buffer during training of an RL agent. The samples are selected based on a priority function that is a multiplication of surprise (TD-error) and a on-policy weight of the transition. Using this priority function, the paper claims that for shorter settings, their approach outperforms agents with comparably sized replays and is able to match agents with much larger replays on most Atari games. ", "summary_of_the_review": "This is a well written paper with good experiments supporting their methods ability enable learning of agents with small replay buffers at short timescales. I recommend acceptance.", "strength_and_weaknesses": "Strengths:\n- This paper is very well written, easy to follow, and well motivated. \n- The experiments are done on a wide range of the Atari games. For most of the games (although not all), this method does outperform the simple FIFO replacement strategy of a comparably sized buffer, and is able to close the performance gap with a larger sized buffer.\n- The ablation experiments show the contributions of each component in the priority weight, and show that both surprise and on-policyness do contribute to better performance.\n- This paper also tried running on longer timescales, with buffer size the same as what is typically used for Atari in the literature, and showed that their method actually does worse than traditional buffers on several environments on this longer timescale. While this is a limitation, it's good that the authors do talk about it, and it potentially highlights a future direction of work.\n\nLimitations/Questions:\n- How does your method work with n-step returns in Rainbow? If you remove a transition in the middle of a trajectory, does that invalidate several other transitions as well? If so, it might be worth exploring this relationship of the number of invalidated transitions and the horizon value in n-step, and see if a replacement strategy could be devised to work around that.\n- As mentioned above, the paper does mention limitations of the method when learning in longer timescales.\n\nEdit:\nAfter the discussion with other reviewers, I am lowering my score to marginal reject. I still think that this is an idea worth pursuing, but I think you need a few more experiments/analysis.\n- As other reviewers pointed out, using 10k is a bit arbitrary. You should do a sweep over different replay sizes to figure out the effect of replay size on different tasks. \n- If you are using Atari, you should show some runs with the full 50m steps.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "A5MebyxZu_", "reviewer": "Reviewer_f3A3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a method to make Rainbow more memory efficient. In particular, it proposes a way to only save data which seems more important using the combination of on-policyness and surprise metrics. Surprise metric is built based on TD-error and on-policyness measures how far behavioral policy is from target policy. One major difference between priority replay buffer and this method is priority replay buffer does not discard samples and saves all data until capacity allows; however, this method discards samples which are unimportant. To show the effectiveness of their method, this paper uses 52 games of Atari benchmark. ", "summary_of_the_review": "The main and critical concern about this paper is the experiments which are not conclusive considering the fact that this is an empirical paper. Another concern is this paper only studies pixel-based environments.  I don't understand why this paper can not be used with state-based environments like MuJoCo. I'd make my final recommendation after rebuttal as I'd like to hear the authors' rebuttal. That being said, this paper does not meet ICLR acceptance bar as it stands.", "strength_and_weaknesses": "While the idea of only saving high valued samples in the reply buffer and using smaller replay size is interesting and can be valuable, I have a couple of concerns with this paper:\n\n- Computational complexity: \nThe main motivation for this paper is to \"make RL training more applicable to low-resource environments''. Although this is the right problem to study,  the current method doesn't come for free and it increases computational complexity of a method as priority function requires to search through the replay buffer at each time step and estimate the score ( search can be more expensive here). The paper  doesn't analyze the complexity of the proposed method and does't provide insights about computation and memory trade-off.\n\n- Baseline methods:\nIn section 5.1, even though authors discuss various baseline methods, they compare their method with these baseline only on 6 environments. While I understand running Atari is expensive, since the contribution of this paper heavily relies on the results, the current results are not conclusive. I'd like to note that authors reported results with smaller replay buffers but the same rainbow method, these results are not as important as comparing with other baselines. Moreover, important baseline like \"Improving computational efficiency in visual reinforcement learning via stored embeddings.\" is missing in the experiments. Also, likelihood free ration and importance sampling weighting can be used as other baselines.  \n\n\n- Figure 2:\nIt is not clear to me what the baseline method in Figure 2? If it is 1K or 10K baseline, they are not appropriate baseline methods. It should be compared with methods which are discussed in the paper. \n\n- Validity of Results:\nComparing Baseline (1M) reported in Figure 8 with Dopamine ( https://google.github.io/dopamine/baselines/atari/plots.html), I notice a huge discrepancy between this paper's results and Dopamine which makes me anxious about validity of this results. Take Gopher as example, Dopmaine shows rainbow gets to average return of 10000 after 200M samples while this paper shows 1000. The same is true about other environments. \n\n- Writing:\nWhile the paper is written well in general, there are notable issues. Q-function is distribution but the equations treat it as not being a distribution. I think this should be fixed. Also, this paper discusses continual learning in the related work sections which I have a hard time to find any relationship with. Instead, this paper should have focused on related works which are relevant to this paper.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "3p12Qeii5I", "reviewer": "Reviewer_Lf8C", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a new method for being able to train high-quality policies on Atari benchmarks while having an experienced memory that is two orders of magnitude smaller. the motivation is that storing large amounts of data and experience memory, especially for image-based environments, can be very memory intensive. If you can reduce this demand for memory, we might be able to reduce the hardware requirements needed to run these algorithms. The method proposes combining types of experience replay methods for surprise and measuring on-policiness to instead remove tuples from the replay buffer that have the lowest combination of these two metrics. The method includes some analysis on the Atari environments that may indicate that performance is better or similar to prior methods that use significantly more memory stored in their experience replay buffer.", "summary_of_the_review": "The proposed method for reducing the memory requirement for training DQN is admerable. The analysis in the paper needs more data to understand better how the stability of the new algorithm. Also, the novelty of the method appears to be limited.", "strength_and_weaknesses": "pros\n- The method proposed in the paper is clean and very easy to understand and should be fairly easy to reproduce\n- Some of the motivations are also very clear. Being able to reduce the memory requirements for the algorithms we use these days can have many important impacts on making algorithms easier to use and more widely accessible to people.\n\ncons\n- One challenge with this method also has to do with the experimental analysis that it performs on the Atari environments. There are few examples where researchers are concerned with not having enough available memory to train in the Atari environments. Including additional environments for which these issues occur would help boost the paper's motivation. \n- The novelty of the method can also be seen as incremental in that it appears to be a combination of two prior well-understood methods for doing experience replay but instead is used for removing experience from the replay buffer instead of picking which ones to train the current policy.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject