Regret Minimization Experience Replay in Off-Policy Reinforcement Learning
Authors: Xu-Hui Liu
Zhenghai Xue
Jing-Cheng Pang
Shengyi Jiang
Feng Xu
Yang Yu
Venue: NeurIPS 2021 Poster (2021)
Keywords: reinforcement learning
experience replay

Abstract: In reinforcement learning, experience replay stores past samples for further reuse. Prioritized sampling is a promising technique to better utilize these samples. Previous criteria of prioritization include TD error, recentness and corrective feedback, which are mostly heuristically designed. In this work, we start from the regret minimization objective, and obtain an optimal prioritization strategy for Bellman update that can directly maximize the return of the policy. The theory suggests that data with higher hindsight TD error, better on-policiness and more accurate Q value should be assigned with higher weights during sampling. Thus most previous criteria only consider this strategy partially. We not only provide theoretical justifications for previous criteria, but also propose two new methods to compute the prioritization weight, namely ReMERN and ReMERT. ReMERN learns an error network, while ReMERT exploits the temporal ordering of states. Both methods outperform previous prioritized sampling algorithms in challenging RL benchmarks, including MuJoCo, Atari and Meta-World.

Regret Minimization Experience Replay in Off-Policy Reinforcement Learning
Xu-Hui Liu', Zhenghai Xue", Jing-Cheng Pang, Shengyi Jiang, Feng Xu, Yang Yu'
National Key Laboratory for Novel Software Technology
Nanjing University, Nanjing 210023, China
liuxh@lamda anw.laaaaaa......aa..........u ..j..nuuuuuuu edu. en, xuezh@smail.cm .nj.i........... edu.. {pangjc, jiangsy, xufeng aladaa.. www.nn..... edu. cn, yuyūnju. edu
Abstract
In reinforcement learning, experience replay stores past samples for further reuse. Prioritized sampling is a promising technique to better utilize these samples. Pre- vious criteria of prioritization include TD error, recentness and corrective feed- back, which are mostly heuristically designed. In this work, we start from the regret minimization objective, and obtain optimal prioritization strategy for Bellman update that can directly maximize the return of the policy. The theory suggests that data with higher hindsight TD error, better on-policiness and more accurate Q value should be assigned with higher weights during sampling. Thus most previous criteria only consider this strategy partially. We not only provide theoretical justifications for previous criteria, but also propose two new methods to compute the prioritization weight, namely ReMERN and ReMERT, ReMERN learns an error network, while ReMERT exploits the temporal ordering of states. Both methods outperform previous prioritized sampling algorithms in challenging RL benchmarks, including MuloCo, Atari and Meta-World.
Introduction
Reinforcement learning (RL) [1] has achieved great success in sequential decision making problems. Off-policy RL algorithms [2, 3, 4, 5, have the ability to learn from more general data distribution than on-policy counterparts, and often enjoy better sample efficiency. This is critical when the data collection process is expensive dangerous. Experience Replay [7] enables data reuse and has been widely used in off- off-po reinforcement learning. Previous work [8] points out that emphasizing on important samples in the replay buffer can benefit off off-policy RL algorithms. Prioritized Experience Replay (PER) [9] quantifies such importance by the magnitude of cumporal-differenee (TD) error. Based on PER, many sampling strategies [10, 11, 12] are proposed to perform prioritized sampling. They are either based on TD error [9, 10, 12] or focused on the existence of corrective feedback [1 1]. However, these are proxy objectives and different from the objective of RI, i.e., minimizing policy regret. They can be suboptimal in some cases due to this objective mismatch.
In this paper, first give examples illustrate the objective mismatch in previous prioritization strategies. Experiments show that lower TD error or more accurate Q function can not guarantee better policy performance. To tackle this issue, we first formulate an optimization problem that directly minimizes the regret of the current policy with respect to prioritization weights. We then make several approximations and solve this optimization problem. An optimal prioritization strategy is obtained and indicates that we should pay more attention to experiences with higher hindsight TD error, better on-pon no-policiness and more accurate Q value. To the best of our knowledge, this paper
Equal contribution Corresponding author
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

the first to optimize the sampling distribution of replay buffer theoretically from the perspective of regret minimization.
We then provide tractable approximations to the theoretical results. The on-policiness can be esti- mated by training classifier distinguish recent transitions, which generally more on-policy, from early ones, which are generally more off-policy. The oracle Q value is inaccessible during training, so we can not calculate the accuracy of Q value directly. Inspired by DisCor [11], we propose an algorithm named ReMERN which estimates the suboptimality of Q value with an error network updated by Approximate Dynamic Programming (ADP).
ReMERN outperforms previous methods in environments with high randomness, e.g. with stochas- tic target positions noisy rewards. However, the training of an extra neural network can be slow and unstable. We propose another estimation of Q accuracy based on a temporal viewpoint. With Bellman updates, the error in Q value accumulates from the next state the previous one all across the trajectory. The terminal state has no bootstrapping target and low Bellman error. Therefore, states fewer steps away from the terminal state will have lower error in the updated Q value because of the more accurate Bellman target. This intuition is verified both empirically and theoretically. We then propose Temporal Correctness Estimation (TCE) based on the distance of each state terminal state, and name the overall algorithm ReMERT.
Similar to PER, ReMERN and ReMERT can be plug-in module to all off-policy RL algorithms with a replay buffer, including but not limited to DQN [5] and SAC [2]. Experiments show that ReMERN and ReMERT substantially improve the performance of standard off-policy RI. methods in various benchmarks.
2 Background
2.1 Preliminaries
A Markov decision process (MDP) is denoted (,, where S is the state space, and A is the action space. T's'ss, a) and r(s, a) E [0, Rmax] are the transition and reward function. 7 E (0, 1) is the discounted factor and (o(s) is the distribution of the initial state. The target of reinforcement learning is to find a policy that maximizes the expected return: 17(x²) = Ex (220 7'((s,, at)]. where the expectation calculated from trajectories sampled from 8g ~ po. at x(-1se), and 81+1 ~
T(1st;, ae) for & 2 0.
For a fixed policy, an MDP becomes Markov chain, where the discounted stationary state dis- tribution is defined as (s). With a slight abuse of notation, the discounted stationary state- action distribution is defined as d= d= a) = d (s)ss( Then the expected return can be rewrit- ten as (TT) = I- (a (r(s, (a.)))((s,a)) a)). We assume there exists an optimal policy x such that ' arg max, ((T). We use the standard definition of the state-action value function, Q func- tion: Q= = Ex 7 (s) satisfies the Bellman equation (s,ssa) = (Q* a)). where B S + RSAA the Bell- man optimal operator: (B* f), == r(s. + max. P a²), where f f RSSA
7'r(si,
5,a0 a). Let Q* be the shorthand for Q=' Q"
The regret of policy æ is defined as Regret(Tr) = -y(x') - (T) It measures the expected loss in return by following policy instead of the optimal policy. Since 77( is constant, minimizing the regret is equivalent to maximizing the expected return, and thus it can be an alternative objective of reinforcement learning.
2.2 Related Work
Extensive researches have been conducted on experience replay and replay buffer. The most fre- quently considered aspect is the sampling strategy. Various techniques have achieved good perfor- mance by performing prioritized sampling on the replay buffer. In model-based planning, Prioritized Sweeping [13, 14, 15] selects the next state updates according to changes in value. Prioritized Ex- perience Replay (PER) [9] prioritizes samples with high TD error. Taking PER one step further, Prioritized Sequence Experience Replay (PSER) [10] considers information provided by transitions when estimating TD error. Emphasizing Recent Experience (ERE) [16] and Likelihood- Free Im- portance Weighting (LFIW) [12] prioritizes the correction of TD errors for frequently encountered

---

Suboprimaiity PER
Subsptimality
TD cour cnvrittthstt
604
400
100
+1
+1
+1
53
200
222
230
230
(a)
(b)
(c)
Figure 1: A simple MDP showing the objectives of PER and DisCor can slow down the training process. (a) A S-state MDP with initial state So and terminal state sr. Except for 83 and sy, there are two available actions, left and right. Turning left leads to the terminal state sy and +2 reward, while turning right leads to the next state and +1 reward. The optimal policy is to keep turning right until reaching $3, then reach sy. (b) Relationship between TD error (dashed line) and performance (solid line) of and VI+PER. (c) Relationship between Q error (dashed line) and performance (solid line) of VI and VI+DisCor.
states. Distribution Correction (DisCor) [11] assigns higher weights to samples with more accurate target Q value because these samples provide "corrective feedback". DisCor uses neural network to estimate the accuracy of target Q value. Inspired by DisCor, SUNRISE [17] proposes to use the surrogate for the accuracy of Q value. Adversarial Feature Matching [18] focuses on sampling uniformly among state-action pairs.
variance of ensembled functions
Instead of proposing new strategy of sampling, [19] proves that there exists relationship between sampling strategy and loss function, and weighted value loss can serve as a surrogate for prioritized sampling. Other works focus on buffer capacity [20, 21J. They point out that a proper buffer capacity can accelerate value estimation and lead to better learning efficiency and performance. In fact, this can be thought of as specific example of prioritization strategies, i.e., assigning zero weights to the samples exceeding the proper buffer capacity.
3 Optimal Prioritization Strategy via Regret Minimization
3.1 Revisiting Existing Prioritization Methods
PER and DisCor are two representative algorithms of prioritized sampling. PER prioritizes state- action pairs with high TD error, while DisCor prefers to perform Bellman update on state-action pairs that have more accurate Bellman targets. However, both criteria are different from the target of RL algorithms, which is to maximize the expected return of the policy. Such difference can slow down the training process in some cases. For example, when the Bellman target is inaccurate, minimizing TD error does not necessarily improve the optimality of Q value.
To illustrate the aforementioned problems, we provide an example MDP shown in the left part of Fig. I(a). This is five-state MDP with two actions: turning left and right. The optimal policy is to turn right in all states, receiving total reward of 5. Suppose the Q values for all (s, pairs are initialized to zero. The reward turning left higher than turning right action has higher TD error. As result, PER prefers states with the left action, which is not the fastest training process to achieve the optimal policy. Also, since there is no bootstrapping error for the terminal state sT, transitions with ST the next state have an accurate target Q value. Therefore, DisCor also focuses on aatecnaciion pairs with left action, which is again not optimal.
states, so the left
We perform Value Iteration (VD) on this MDP. To simulate function approximation in Deep RL and avoid convergence in few iterations, the learning rate set to 0.1. Prioritized sampling substituted by weighted Bellman update, as introduced in [19]. The results are shown in Fig. 1(b) and Fig. ((c). According to the results, PER indeed minimizes TD error more efficiently, and DisCor results in a more accurate estimation of Q value, as indicated by their objectives. However, they both need more iterations to converge than value iteration without prioritization. According to this MDP, the objective of previous prioritization methods can be inefficient in certain cases.
3

---

3.2 Problem Formulation of Regret Minimization
As shown in Section 3.1, an indirect objective can cause slower convergence of value iteration. In this section, we aim to find an optimal prioritization weight wi that can directly minimize the policy regret (7(=*) (TTT))) The weight multiplied to the Bellman error (Q B Qx=1)² and mg can be obtained from the updated Q function. To facilitate further derivations, we only consider the best Q function of the Bellman update, which calculated by the arg min operator. Therefore, the optimization problem with respect to wy can be written as:
min we
(()T) TTTT
s.t.
Qk = arg min En a) (Q - (B--"
QEO
Ey (s. = ax(s,a) 20,
where (s) Ln exp( (s,a)) is the policy corresponding to Qk- Q is the function space of Q functions and js is the data distribution of the replay buffer. Qx the estimate Q value after the Bellman update at iteration k.
(ep(Qa(s.a)
We then manage to solve this optimization problem. To get started, we introduce recurring proba- bility which serves as an upper bound of the error term in our solution.
Definition 1 (Recurring Probability). The recurring probability of a policy æ is defined as E sup,,a Et=r? 7'p" (8, t), where p is the probability of the agent starting from (8,0) a) and coming back to at time step t under policy x, i.e., p² (s,
Pr(so = 0g a, St 8, $1:1-11 * s; IT).
We then present the solution to the optimization problem in Thm. 1. The formal version of the theorem and detailed proof are in Appendix A.
Theorem (Informal). Under mild conditions, the solution we to a relaxation of the optimization problem I in MDPs with discrete action spaces is
w a) = Zi
(Fx(s. (x.((,))))
(2)
In MDPs with continuous action spaces, the solution is
WA (s, a) = 7
())( + +x,26,,,))
(3)
where
Ex(8,0)= d (s)
(2 ml(als)) exp (- 1Qx -Q1s
1'Qu-il (8,0)
((s
(c)
(d)
(a)
d (s,
Fk(x,a)=
exp ( 10-1Q==Q1l
Q*1 (s,
Qq Q0-ii
(18,a)
(c)
(d)
Zi, Z3 are normalization factors, cx (s, a) and cx,(ss, a) satisfy max {
((.a) (m.lssaa) (u(x,)) Fe(a,)
I Ex
With regard the error terms, there of coming back to the states that have been visited is small, or the number of steps an agent takes to come back the visited states is large. most tasks, either of these cases holds. We conduct exper- iments in several Atari games and show the verification results in Appendix D. The low probability leads to small cx. and implies the terms e (s, and 6x,2 (8, a) are negligible.
cases where 6r, is low by its definition: the probability
Therefore, Thm. 1 suggests that state-action tuples in the replay buffer should be assigned with higher importance if they have the following properties:
Higher hindsight Bellman error ( from IQ+ - B s'Qu=Il(s,0)) a)). Qx is the estimate of Q value after the Bellman update. This term describes the difference between the estimated hindsight Q value and the Bellman target. is similar to the prioritization criterion of PER [9], but PER concerns more about the historical Bellman error, i.c., 1Q--1 B" 3²Qx=2lss.d

---

More on-policiness ( from d= p(s,a)
). An efficient update of x requires wi to be on-policy, i.e., focusing on state-action pairs which are more likely to be visited by the current policy. Such prioritization strategy has been empirically illustrated in LFIW [12] and BCQ [22], while we obtain it directly from theorem.
Closer value estimation to oracle ( from (xp(-IQ: Q*1 (s, (s) This term indicates that state-action pairs with less accurate Q values after the Bellman update should be assigned with lower weights. Intuitively, state-action pairs that lead to suboptimal updates of the estimator of Q value should be down-weighted Such suboptimality may arise from incorrect target Q values or the error of function approximation in deep Q networks.
Smaller action likelihood (from 2 - T (a]s))). This term only exists in MDPs with a discrete action space. It offsets the effect of the on-policy term d some extent and similar to greedy strategy in exploration.
Our theoretical analysis indicates that existing prioritization strategies only consider the problem partially, neglecting other terms in minimizing the regret. For example, DisCor fails to consider the on-policiness and PER ignores the accuracy of Q value. In the remaining part of this section, we present practical approximations to each term in Eq. (2) and (3).
Term (a) is the importance weight between the current policy and the behavior policy. We can calculate this term using Likelihood-Fii Free Importance Weighting (LFIW, [12). LFTW divides the replay buffer into two parts, fast buffer Dj and slow buffer D.. It initializes neural network (5 a) and optimizes the network according to the following loss function:
(v) == ED, [ (S' (1, a))) ED, [J' (s,
where f' and f is the derivative and convex conjugate of function f. The updated Ky is the desired importance weight.
For term (b) and (d), since The and Qs are the policy and the estimate of Q value after the update, they cannot be calculated directly. Therefore, we approximate them by the upper and lower bounds. For term (b), S T& (a|s) s) S 2. For term (d), a viable approximation is to bound it between the minimum and maximum Bellman errors obtained at the previous iteration,
ming,a 1Qa-1 Q=Q and C2 = max,,a [Qk11 - Qx- As shown in DisCor, we can restrict the support of state-action pairs (s, a) used to compute 01 and e2 in the support of replay buffer, to ensure that both e1 and 0o are finite. With these approximation, we can derive a lower bound for wk. which will be detailed in Sec. 3.3 and Sec. 3.4.
In the next two subsections, we will provide two practical algorithms to estimate IQx - Q²
3.3 Regret Minimization Experience Replay Using Neural Network (ReMERN)
DisCor shows As can be a surrogate of IQu - Q"). which is defined as:
k II PT
1B-BBQu-il
(5)
4 1Q 13 B*Qu-il 7 PiA-1 AR-1
(6)
According to Eq. (6), {
1) (8, a) + 02 is an upper bound of [Qs Q*I. This is because
Ae is proven to be the upper bound of [Q, Q-1 [11] and is the upper bound of IQ+ BB 1-
Recall that 2 - (aaass) 2 and 1Q-11 3 2 CJ. and we can derive the final expression for this tractable approximation for ax) by simplifying all constants:
(s,
wx(8, a) x ((s.a) exp (-> (-> A (s)
This approximation applies to MDPs with discrete action space and MDPs with continuous action space. Using the lower bound of (s.a) may down-weight some transitions, but will never up- weight transition by mistake [11].
We use neural network to estimate Ag-1- As shown in Eq. (6), A can be calculated from bootstrapped target, which inspires use ADP algorithms update it. We name this method
5

---

ReMERN (Regret Minimization Experience Replay using Neural Network). The pseudo code for ReMERN presented in Appendix C. ReMERN applicable all value-based off- off-policy algo- rithms with replay buffer.
3.4 Regret Minimization Experience Replay Using Temporal Structure (ReMERT)
ReMERN uses neural network the estimator of [Qx Q*), However, training neural network is time consuming and suffers from large estimation error without adequate iterations. To mitigate this issue, we propose another estimation of IQx Q'1 from a different perspective.
3.4.1 The Temporal Property of Q Error
IQ -Q can be decomposed with the triangle inequality: 1Q--Q"1 S 1R-=BBQQ--++110 Q
@*1. The first term is the projection error depending on the function space Q. This error usually small thanks to the strong expressive power of neural networks. In the second term, Q is the estimate of target value, and Q-1 Q"1 is the distance from the target Q value to the ground-truth Q value. The target Q value at the terminal state consists of the reward only, so there no bootstrapping error and [ Q--1 Q'I 0. Moving backward through the trajectory, the accuracy of the Q value estimation decreases as the enror of Bellman update accumulates. These Q values are then utilized to compute the target Q value, leading to more erroneous Bellman updates and larger |B* -t Q*1. I. Such error can accumulate through the MDP. Consequently, states closer to the terminal state tend to have more accurate Bellman target. This motivates us to estimate the incorrectness of the estimated Q value using the temporal information of given state-action tuple (st, az).
To verify our intuition on the temporal property of Q er- ror, we use a gridworld MDP from [23] and visualize the mean error of the target Q value (i.e., 1 Q - Q"1) across different actions in Fig. We use DQN to update values. In this gridworld MDP, an agent starts at the red triangle on the top-left and terminates at the green rectan- gle on the top-right. The agent can't go through the wall, which plotted as gray grids. The darker a grid is, the higher error of Q function it has. This figure illustrates that states closer to the terminal state has lower Q error, corresponding to our intuition that [B Q+ Q*1 is re- lated to the position of (s, a) in the trajectory.
Q Suboptimalit
0//
0.6
05
0.4
02 The visualized error of target Q value in a GridWorld Environment. The error visualized by the color of the grid.
Figure 2:
To formalize this intuition, we first define Distance to End.
Definition 2 (Distance to End). Given a MDP M, t = {st, at YT is a trajectory generated by policy n in M. The distance to end of (st, at), denoted by hū (st, T in this trajectory.
Our intuition states that the value of Qx Q" has positive correlation with distance to end. Based on this intuition, we propose the following theorem.
Theorem 2 (Informal). Under mild conditions, with probability at least 1 8, we have
1Qx(s,a) - Q*
< <E. [(177 (s, (L +c) + 7 (())(t))) + g(ki,
(8)
where c = max,,a (x" g(ks 8) decreases exponentially as is increases.
a)), f(t) = 3-5 LQ = BB1QQ-1-B'Q--- B'Q and
The formal version of the theorem and its proof are in Appendix B. The theorem states that JQx Q"" is upper bounded by a function of distance to end and expected Bellman error with high probability.
3.4.2 A Practical Implementation
In Thm. we derive the upper bound of IQx - Q") which can serve as a surrogate to Q+ - Q*). Using upper bound as the surrogate may down-weight weight some transitions, but will never up-weight

---

transition that should not be up-weighted [11]. (TCE):
We call this Temporal Correctness
Estimation
((((,a) R E,,TCE,(s...
EE, f( 1s, ((s,a))(LQx-) + +c) + (0))))( +
(9)
Similar to the derivation of ReMERN, we can simplify the expression of wp (x, a) as:
d (8, a) a(s,a)
ug(ss,) a)
exp (- (-E,TCE,(ss,))
(10)
This approach of computing prioritization weights is named ReMERT (Regret Minimization Experience Replay using Temporal Structure). Its pseudo code is presented in Appendix C. In practice, record the distance to end of state-action pair when it is sampled by the policy and stored the replay buffer. The expectation with respect to T is computed based on the record and Monte-Carke estimation.
3.5 Comparison between ReMERN and ReMERT
ReMERT can estimate [Qx 19 Q- directly from the temporal ordering of states, which often provides more efficient and more accurate estimation than ReMERN. However, The expectation with respect to trajectory т in Eq. (10) induces statistical error. some environments, the distance to end of a certain state-action pair (s, a)) can vary widely across different trajectories, which is usually caused by the randomness of environments. For example, in environments with stochastic goal positions, the state may be near the goal in episode but far away from it in another. In such cases, pri- oritization weights provided by ReMERT have large variance and can be misleading. contrast, ReMERN need to train error but irrelevant to the distance end. Therefore, ReMERN suffers estimation error of neural network but is robust to the randomness of environments. We test their property in the following section.
4 Experiments
In this section, we conduct experiments to evaluate ReMERN and ReMERT*. We choose SAC and DQN as the baseline algorithms for continuous and discrete action space respectively and in- corporate ReMERN and ReMERT as the sampling strategy. We first compare the performance of ReMERN and ReMERT to prior sampling methods in continuous control benchmarks including Meta-Worid [24], MuJoCo [25] and Deepmind Control Suite (DMC) [26]. We also evaluate methods Arcade Learning Environments with discrete action spaces. Then, we dive into our algo- rithms and design several experiments, such Gridworld tasks and MuJoCo with reward noise, to demonstrate some key properties of ReMERN and ReMERT. detailed description of the environ- ments and experimental details are listed in Appendix D.
4.1 Performance on Continuous Control Environments
In MuJoCo and DMC tasks, ReMERT outperforms baseline methods on four of six tasks and achieves comparable performance in the rest tasks, i.e. HalfCheetah and Hopper, shown in Fig. 3. The marginal improvement of ReMERT in HalfCheetah mainly comes from the absence of strong correlation between Q-loss and time step. In HalfCheetah, there is specific terminal state, so the agent always reaches the max length of the trajectory, which gives a fake "distance to end" for every state. In Hopper, there sampled state-action pairs, as shown in Appendix D, so the state-action pairs are not sampled very unequally. Besides, Hopper is relatively easy task, in which prioritizing the samples have minor impact on the overall performance of the RL algorithm. The performance of ReMERN is better than DisCor, but is not as good ReMERT. This verifies our theory and the existence of large estimation error induced by updating neural network with ADP algorithms.
much difference of the IQx Q" term between all the
Codess available at http:://gitubb..oo/AA/tfeeeteeet
ReMERT.

---

Tish-swim
Ant-v2
Humanol6-v2
Discor
6000
9000
Reward
400
ReMERT
6000
4000
2000
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
1e6
1e6
1e6
Walker2d-v2
Hopper-v2
HairCheetah-v2
6000
1000
15000
Reward
4000
10000
2000
1000
5000
0.00
0.25
0.50 Timestep
0.75
1.00
0.00
0.25
0.50 Timestep
0.75
1.00
0.0
0.5
1.0 Timestep
1.5
2.0
186
105
Figure 3: Performance of ReMERT, ReMERN with SAC and DisCor baselines on continuous
control tasks.
The Meta-World benchmark [24] includes many robotic manipulation tasks. We select 8 tasks for evaluation, and plot the result in Fig. 4. The performance of PER can be found its paper [9]. Current state-of-the-art off policy RL algorithms such as SAC performs poorly on this benchmark because the goals of tasks have high randomness. Although DisCor [11] shows preferable perfor- mance in these tasks compared SAC and PER, ReMERN obtains significant improvement DisCor in the training speed and asymptotic performance. In this evaluation, we exclude ReMERT for comparison because the randomized target position in Meta-Wer World contradicts its assumption.
1e4
push
1e4
hammer
1e4
10.0 1e4
pick-place
SAC
7.5
ReMERN
15
5.0
5
2.5
0.0
-2.5
25
50
75
100 Le4
0
25
50
75
100
0
25
50
75
100
25
50
75
100
1e4
1o4
peo insert-side
stick: stick-push
1e4
stick-pull
1ed
faucet-close
Reward
10
2.5
0.0
Timestap
Lee4
Timestep
Ic4
Timestep
Timestep
led
Figure 4: Performance of ReMERN, standard SAC and DisCor in eight Meta- World tasks. From left to right: push, hammer, sweep, peg-inseen reg-insert-side, stick push, stick pull, faucet close.
4.2 Performance on Arcade Learning Environments
Atari games are suitable for verifying our theory for MDPs with discrete action space. The tested games have a relatively stable temporal ordering of states because the initial state and the terminal state have little randomness, so that the assumption of ReMERT is satisfied. As shown by Tab. 1, ReMERT outperforms DQN in the selected games. The results also suggest that ReMERT can be applied to environments with high dimensional state spaces. Results of more Atari games are listed in Appendix D. We do not include ReMERN for comparison because DisCor which is a composing part of ReMERN has no open-source code available for discrete action space.

---

Hopper
Ant
5000
6000
Reward
3000
4000
2000
1000
2000
2000
ReMERN
ReMERT
0.00
0.25
0.50 Timestep
1.00
0.00
0.25
0.50 Timestep
1.00
0.5
1.0
2.0
Timestep
Figure 5: reward noise.
Performance of ReMERN, ReMERT and SAC on three continuous control tasks with
4.3 Demonstration Key Properties of ReMERN and ReMERT
4.3.1 Influence of Environment Randomness
Fig. 3 and Fig. 4 show that ReMERN has better performance on Meta-Worid than on Mujoco tasks. We attribute this to the robustness our strategy environments with high randomness. For highly stochastic environment, the estimation of Q value is difficult. When the estimation of Q value is inaccurate, the target Q value is also inaccurate, leading to suboptimal update process in off- policy RL algorithms. Thanks to the closer value estimation to oracle principle, ReMERN estimates Q value more accurately than other methods. However, for less stochastic environments like MuloCo environments, the accuracy of error network might become the bottleneck of ReMERN.
To show this empirically, we add Gaussian noise the reward function MuJoCo environments. The details of the experimental setup are listed in Appendix D. Fig. 5 show that: (1) ReMERN and ReMERT perform better than SAC in stochastic environments, which verifies our analysis. (2) Though ReMERT suffers statistical error of temporal ordering, it is robust to the randomness of reward because the temporal property is not affected by the noise.
4.3.2 Analysis of TCE on Deterministic Tabular Environments
To analyze the effect the principle behind TCE, we evaluate the Q error in Gridworld with image input. We plot the 1x Q*I error of standard DQN, DQN with DisCor, DQN with TCE and DQN with oracle at time the training process in Fig. 6. TCE is combined
with DQN to estimate term (c) in Eq. (2). and the other terms are ignored to compute Wk. DQN with oracle uses the ground-truth error IQu Q*I calculate the prior- itization weight. The result shows that DQN with TCE achieves a more accurate Q value estimator than those of standard DQN and DQN with DisCor, while DQN with oracle 12 - Q-I achieves the most accurate value esti- mator. The lower efficiency of DQN with DisCor is due to the slower convergence speed of the error network. This proves the principle behind our theory effective, and TCE decent approximation of IQx Q'I.
Figure TCE and DisCor in Gridworld
Table DQN ReMERT Atari. DQN (Nature) is the performance the DQN paper [S].
DQN
(Baseline) is the performance of our baseline program [27].
Method
Enduro
KungFuMaster
Kangaroo
MsPacman
Qbert
DQN (Nature)
301+24.66
23270-1-955
2750
23114:525
10596++3244
DON (Baseline)
1185+ 100
29147+7280
1207
3318+647
13437+2537
ReMERT (Ours)
1303:2258
3554418432
1792
3481
14511

---

Conclusion and Future Work
In this work, we first revisit the existing methods of prioritized sampling and point out that the ob- jectives of these methods different from the objective of RL, which can lead to suboptimal training process. To solve this issue, we analyze the prioritization strategy from the perspective of regret minimization, which is equivalent return maximization in RL. Our analysis gives theoret- ical explanation for some prioritization methods, including PER, LFIW and DisCor. Based on our theoretical analysis, propose practical prioritization strategies, ReMERN and ReMERT, that directly aims to improve the policy. ReMERN is robust to the randomness of environments, while ReMERT more computational efficient and more accurate in environments with stable temporal ordering of states. Our approaches obtain superior results compared to previous prioritized sampling methods. Future work can be conducted in the following two directions. First, the framework ob- tain the optimal distribution in off- off-policy RL can be generalized to model-based RL and offinn RL. Second, the two proposed algorithms are suitable for different kinds of MDP, so finding a unified prioritization method for all MDPs can further improve the performance.
Acknowledgements and Disclosure of Funding
We thank Xintong Qi and Xiaolong Yin for helpful discussions. We would also like to thank two groups of anonymous reviewers for their valuable comments on our paper. This work is sup- ported by National Key Research and Development Program of China (2020AAA0107200) and NSFC(61876077).
References
[1] Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[2] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critie: Off- policy maximum entropy deep reinforcement learning with a stochastic actor. In Proceed- ings of the 35th International Conference Machine Learning (ICML'18), pages 1856-1865. Stockholmsmässan. Sweden, 2018.
[3] Scott Fujimoto, Herke van Hoof, and David Meger. Addressing function approximation er- in actor-critic methods. In Proceedings of the 35th International Conference Machine Learning (ICML' (8)), pages 1582-1591, Stockholmsmässan, Sweden, 2018.
[4] Matteo Hessel, Joseph Modayil, Hado van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Gheshlaghi Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. In Proceedings of the 32nd Conference on Artificial Intelligence 18), pages 3215-3222, New Orleans, LA, 2018
[5] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin A. Riedmiller, Andreas Fidjeland, Georg Ostrovski, Stig Pe- tersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep rein- forcement learning. Nature, 518(755)))52995535 2015.
[6] Mare Bellemare, Will Dabney, and Rémi Munos. A distributional perspective on reinforce- ment learning. In Proceedings of the 34th International Conference on Machine Learning (ICML'I7), pages 449 458. Sydney, Australia, 2017.
[7] Long Lin. Self-improving reactive agents based on reinforcement learning, planning and teaching. Journal of Machine Leurning Research, 8:293-321, 1992.
[8] Angelos Katharopoulos and François Fleuret. Not all samples are created equal: Deep learning with importance sampling. In Proceedings of the 35th International Conference on Machine Learning (ICML'I8) 18)), pages 2530-2539, Stockholmsmässan Sweden, 2018.
10

---

[9] Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. In Proceedings of the 4th International Conference on Learning Representations (ICLR' 16), San Juan, Puerto Rico, 2016.
[10] Mare Brittain, Joshua Bertram, Xuxi Yang, and Peng Wei. Prioritized sequence experience replay. CoRR, abs//905. 12726, 2019.
[11] Aviral Kumar, Abhishek Gupta, and Sergey Levine. Discor: Corrective feedback in reinforce- ment learning via distribution correction. In Proceedings of 33rd conference on Neural Infor- mation Processing Systems (NewrIPS 20),, virtual event, 2020.
[12] Samarth Sinha, Jiaming Song. Animesh Garg, and Stefano Ermon. Experience replay with likelihood-free importance weights. CoRR, abs/2006. 13169, 2020.
[13] David Andre, Nir Friedman, and Ronald Parr. Generalized prioritized sweeping. In proceed- ings of the 10th conference on Neural Information Processing Systems (NeurIPS pages 1001-1007, Denver, CO, 1997.
[14] Andrew W. Moore and Christopher G. Atkeson. Prioritized sweeping: Reinforcement learning with less data and less time. Journal of Machine Learning Research, 13:103-130, 1993.
[15] Harm van Seijen and Richard Sutton. Planning by prioritized sweeping with small backups. In Proceedings of the 30th International Conference on Machine Learning (ICML'13) pages 361-369, 2013.
[16] Che Wang, Yanqiu Wu, Quan Vuong, and Keith Ross. Striving for simplicity and performance in off off-policy DRL: output normalization and non-uniform sampling. In Proceedings of the 37th International Conference on Machine Learning (ICML'20), pages 10070-10080, virtual event, 2020.
[17] Kimin Lee, Michael Laskin, Aravind Srinivas, and Pieter Abbeel. SUNRISE: A simple unified framework for ensemble learning in deep reinforcement learning. In Proceedings of the 38th International Conference on Machine Learning (ICML'21), pages 6131-6141, virtual event, 2021.
[18] Justin Fu, Aviral Kumar, Matthew Soh, and Sergey Levine. Diagnosing bottlenecks in deep q learning algorithms. In Proceedings of the 36th International Conference on Machine Learning (ICML'I9) pages 2021-2030, Long Beach, CA, 2019.
[19] Scott Fujimoto, David Meger, and Doina Precup. An equivalence between loss functions and non-uniform sampling in experience replay. In Proceedings of the 33rd Annual Conference Neural Information Processing Systems (NeurIPS 20), 2020.
[20] Shangtong Zhang and Richard S. Sutton. abs/1712.011255, 2017.
A deeper look at experience replay. CoRR,
[21] William Fedus, Prajit Ramachandran, Rishabh Agarwal, Yoshua Bengio, Hugo Larochelle, Mark Rowland, and Will Dabney. Revisiting fundamentals of experience replay. In Proceed- ings of the 37th International Conference on Machine Learning (ICML'20), pages 3061-3071, virtual event, 2020.
[22] Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. In Proceedings of the 36th International Conference on Machine Learning (ICMI.'9)) 19), pages 2052-2062, Long Beach, CA, 2019.
[23] Maxime Chevalier-Boisvers Lucas Willems, and Suman Pal. Minimalistic gridworld environ- ment for openai gym. https://gitub..ommmxximeeb/ minigrid, 2018.
[24] Tianhe Yu, Deirdre Quillen, Zhanpeng He, Ryan Julian, Karol Hausman, Chelsea Finn, and Sergey Levine. Meta-world: A benchmark and evaluation for multi-task and meta reinforce- ment learning. Proceedings of the 3rd Conference on Robot Learning (CoRL. Osaka, Japan, 2019.
11

---

[25] Emanuel Todorov. Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In Proceedings of 24th International Conference on Intelligent Robots and Systems (IROS' 12), pages 5026-5033, Vilamoura, Portugal, 2012.
[26] Yuval Tassa, Saran Tunyasuvunakool, Alistair Muldal, Yotam Doron, Siqi Liu, Steven Bohez, Josh Merel, Tom Erez, Timothy Lillicrap, and Nicolas Heess. dm-control: Software and tasks for continuous control, 2020.
[27] Jiayi Weng, Huayu Chen, Alexis Dubureq, Kaichao You, Minghao Zhang, Dong Yan, Hang Su, and Jun Zhu. Tianshou. https//ggitubb.co//mmmmmmiiiiii 2020.
12


Reviews:
[{"review_id": "wFiu6qUcJUW", "reviewer": "Reviewer_okGN", "summary": "This paper proposes an approach to prioritizing experience replay, specifically it advocates for prioritizing experiences that, when sampled and used for Bellman error minimization, result in lower regret (or really higher reward objective).\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The approach taken here to prioritize experience is certainly interesting, as it actually connects the prioritization problem to the reward maximization problem, which is the ultimate goal of RL. As such, the prioritization approach could be thought of as objective-aware. This stands in contrast to previous work in the space that defines a good prioritization scheme as one that, for example, reduces the TD error rapidly (PER).\n\nThe paper nicely demonstrates that heuristics, such as the one used by PER, may not necessarily manifest themselves into higher rewards, and so it nicely motivates why we need to reformulate the prioritization problem.\n\nThe solution to the reformulated problem highlights key factors when determining which sample to use:\n1- high hindsight Bellman error\n2- low importance sampling (between behavior and target policies)\n3- accuracy of the resultant Q*\n4- focusing on actions behind which the policy assigns more probability.\n\nThoughts regarding the proof of Theorem 1: assumption 1 sounds highly arbitrary and self-serving. Is it correct to say that the theory won't apply to MDPs in which a transition to a same state is likely? It seems like the assumption is only used to approximate the gradient in the follow up derivation. Is it not possible to remove the assumption and bound the error instead?\n\nI didn't get why we used Jensen's inequality in (14). Why can't we directly optimize for 12? In (16), why can't a p_k be strictly zero? In step 4, second equality, should a s be a'? In general, i think the proof needs to get polished and assumption better justified before this result is ready for publication.\n\nThe temporal property of Q error seems kind of hacky. a) it depends on the current policy, so it needs to be re-estimated with every change, and b) it is not obvious how to think about it in non-episodic domains and/or domains with frequent self-transitioning states. Can you clarify?\n\nCan you also include the computation time required for REMERN and REMERT? In particular, i am interested to know its comparison with DQN and PER. Is the computation of w the bottleneck of the algorithm, or that it does not affect the overall computation time significantly. Also, I'd move the PER result from the Appendix to the main text, as PER would be the most important baseline to assess the competency of the proposed algorithms.\n\nIn general, this paper is identifying a weakness of the previous work pertaining to experience prioritization, which is really nice, but i have my own doubts regarding the proposed way of computing the weight. Overall, I lean towards acceptance at this point.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "qeaOwGaPvwX", "reviewer": "Reviewer_hPUt", "summary": "This paper attempts to provide a theoretical approach to the prioritization of the experience reply to minimize regret. \nThe main result of the paper shows that to minimize the regret, one should minimize a weighted mean squared Bellman error, where the weights $\\omega(s, a)$ depend on four terms\n\n1. the magnitude of the Bellman error for the state-action pair $s,a$\n2. the degree of \"policiness\" of the sample $s, a$ (seen as the probability of sampling from the experience replay v.s. the discounted state distribution)\n3. the magnitude of the error $|Q_k - Q^*|(s, a)$, which tells us how \"wrong\" is $Q_k(s, a)$\n4. the probability of sampling $a$ given $s$ according to the current policy.\n\nThe authors develop some heuristics to estimate these four components, and to weigh the replay memory accordingly.\n\n", "questions": "", "limitations": "", "rating": 3, "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": "The idea to find a principled way to prioritize the replay buffer is nice. \nTheorem 1 (if correct) is an important contribution, as it allows to use the experience replay in a smarter way.\n\nI have, however, a few fundamental concerns. The first one is about why the authors focus on the regret. In their setup, the maximization of the return should be enough, and I find the terminology \"regret\", confusing, as it is used usually in a different context.\nAnother concern is that the paper looks like more a draft stage rather than a finished work. There are a few imprecisions, as well as many details missing. I list them later, but to give an idea, many mathematical symbols are not defined, and some of the reasonings made do not make perfect sense to me. \nMy last concern regards the amount of approximations introduced. It is not easy (at least for me) to understand the logic behind the approximations. Unfortunately, the language used in the paper does not help to clarify them.\n\n\n\nThe authors evaluate their methods (ReMERN and ReMERT) on different settings. I think that the empirical section is well constructed (even though I would advocate the comparison with the classic Prioritized Experience Replay); however, I do not find the results to be particularly significant, especially when taking in account that the method proposed is strongly empirical (I usually tend to weight less the importance of the experimental section when the theoretical section is stronger).\n\n\n__Questions__\n\n1. In lines $\\texttt{141-144}$ you state that \"an efficient update requires $\\omega_k$ to be on-policy\". I do not understand this sentence. If I understand Theorem~1 correctly, when $d^{\\pi, k}(s, a)$ is low and $\\mu(s, a)$ is high, then $\\omega_k(s, a)$ will be low, while when $d^{\\pi, k}(s, a)$ is high and $\\mu(s, a)$ is low, $\\omega_k(s, a)$ will be high. How is this related to on-policy/off-policy? It seems that in the two cases that I mention, clearly both off-policy, we have two different asymptotic $\\omega_k(s, a)$.\n\n2. I do not understand Equation 4. I do not know what is a slow replay buffer and a fast one, and I do not know the meaning of $f^*$ and $f'$\n\n3. How do you train $\\Delta_k$? From the formula seems that you need to store all the previous policies $\\pi_k$ (small detail: you usually do not have $P^{k-1}$ or $\\mathcal{B}^*$, I guess that you are fitting a _sample estimate_).\n\n4. Is Equation~  an upperbound, a lower bound, or ... ? It is hard for me to relate it to Equations 2 and 3. (As I discuss later, I am convinced that using $\\propto$ is wrong in Eq. 7).\n\n5. $\\texttt{247}$ what does it mean \"the term $h^\\pi_\\tau(s, a)$ is relatively fixed\"? Means that it has low variance? And what is the _temporal ordering_ of the estates (or a _stable temporary order of states_)?\n\n\n__\"Minor\" Questions__\n\n1. I fail to understand the need of minimizing $\\eta(\\pi*) - \\eta(\\pi_k)$, since it is equivalent to $\\max \\eta(\\pi_k)$ (up to an additive constant factor).\n\n2. I fail to understand what $|Q_k - Q^*|(s, a)$ means. Is it a shorthand for $|Q_k(s, a) - Q^*(s, a)|$?\n\n3. The policy is defined as $\\pi(s) = \\mathrm{arg}\\max_a Q_k(s, a)$ (line $\\texttt{126}$). What is $\\pi_k(a|s)$ in Theorem~1? (remember, the paper should be self contained, I should not go to investigate that in the Appendix.)\n\n4. What are $f'$ and $f^*$ in Equation 4?\n\n5. What does it mean in Theorem 2 \"Ignoring some terms\", \"holds with high probability\"? I know you are referring to the Appendix, but the paper should be self contained. Including a \"Theorem\" in such unclear way, is completely useless. \n\n\n__Side notes__\n\n\n1. You define $\\eta(\\pi)  = \\mathbb{E}\\left[\\sum_{t>0}\\gamma^t r(s_t, a_t)\\right]$  on line $\\texttt{62}$, but then you define it as $\\eta(\\pi) = \\mathbb{E}_{d^\\pi(s, a)}[r(s,a)]$., where $d^\\pi$ is the _discounted stationary state distribution_. \nThe two definitions are not equivalent as, \n\n$$ (1-\\gamma)\\mathbb{E}\\left[\\sum_{t>0}\\gamma^t r(s_t, a_t)\\right] = \\mathbb{E}_{d^\\pi(s, a)}[r(s,a)]$$\n\n2. Eq two should be modified in the following way:\n\n$$\\text{s.t.} \\quad Q_k  = \\mathrm{arg}\\min_Q E_\\mu \\left[\\omega_k(s, a)  \\cdot (Q-\\mathcal{B}^*Q_{k-1})(s, a)\\right].$$\n\n3. Equation 7 is an approximation of Equation 3; you should not use the same symbol both for the \"correct\" value and for its approximation.\n\n4. I think at line $\\texttt{233}$ $Q$ should be substituted with $Q_{k-1}$.\n\n5. In the Appendix you define $d^\\pi$. I find the definition wrong, or at least unclear. Why don't you use the definition from Sutton et al., NIPS 1999? \n\n6. $\\texttt{192}$, The first term is the _projection error_. \n\n7. Line $\\texttt{233}$. How do you update $Q_k = (1-\\alpha)Q_{k-1} + \\alpha Q_{k-1}$? Is $Q$ tabular? What it is done usually, it is to update the parameters of $Q_k$ with a soft-update rule. \n\n8. Line $\\texttt{236}$. How do you ensure that a small change in the Q-function results in a small change in the policy? \n\n\nUPDATE\n=======\n\nI thank the authors for their answers to my questions. \nUnfortunately, after carefully considering the author's response and other reviewer's responses, I am willing to keep my score as it is. \n\nThe paper analyzes an interesting problem and proposes a theoretical approach to minimize the regret in weighting the samples coming from the replay memory. The algorithmic solution, however, relies heavily on approximations (like the result in Equation 7, and the need to approximate the Bellman error with a neural network) and heuristics, as I also remarked in my review. \nI usually expect strong empirical evidence supporting empirical works. However, in my perspective, the results are not so strong. \nIn Figure 4, the learning curve is clearly unstable both in push and sweep. In stick-pull, hammer, and peg-insert-side, the variance is considerably high, making me doubtful of the statistical significance of the results. The same issue of high variance seems to be present also in most of the tasks in Figure 3 and Table 1. \n\nAs I remarked in the review, I also detected several imprecisions (mathematical notation and language), which make me think that the paper should be polished. \n\nSide remark. The policy is greedy w.r.t. the Q-function, meaning that small changes in the Q-function many still cause large changes in the policy, i.e. consider $Q(s_1, a_1) = 100$ and $Q(s_1, a_2) = 99.99$, which leads a policy $\\pi(a_1| s_1) = 1; \\pi(a_2|s_1) = 0$, but after an update, we suppose that $Q(s_1, a_1) =100$ and $Q(s_1, a_2) = 100.1$. This will lead the policy to have a big \"jump\", since now the greedy policy will be $\\pi(a_1| s_1) = 0; \\pi(a_2|s_1) = 1$.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Although the author claimed that they discussed the limitations of their work, I do not find the discussion in the paper. \nI suggest that the discussion should be made more clear in the Conclusion.\n\nThere is no societal impact to be discussed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "p5ZqxeujGDJ", "reviewer": "Reviewer_8h92", "summary": "This paper proposes a method to improve the data selection strategy of experience replay, which is one of the standard techniques in deep reinforcement learning. As opposed to the previous method (PER), the authors provide a theoretical study to design an optimal prioritization weight by minimizing the policy regret. Some theoretical parts are partially based on the previous study (DisCor). The major contribution is that the prioritization weight is decomposed into four components. The most difficult part is to estimate $|Q_k – Q^*|$. The authors propose two practical algorithms. ReMERN estimates the upper bound of $|Q_k – Q^*| while ReMERT exploits the distance to the terminal state. The proposed method is evaluated on several benchmark tasks, including MuJoCo, MetaWorld, and Atari, and the experimental results show the proposed methods improve sample efficiency in many cases.", "questions": "", "limitations": "", "rating": 8, "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": "Major comments\n1. In Section 3.4.1, the authors mention that the terminal state consists of the reward only. It is correct, but some tasks do not have a terminal state. Is it possible to apply ReMERT to the non-episodic or continuing task? In fact, the performance of the proposed method is almost the same as DisCor in the HalfCheetah task. \n\n2. I do not fully understand the TCE algorithm. For example, how do you compute $\\mathbb{E}[|Q_{k-1} - \\mathcal{B}^* Q_{k-2}|]$ in practice? In the simplified version (11), do you compute the expectation? In addition, it would be better to explain the difference between c of Eq.(8) and c of Eq.(9). In (8), $c$ is given by $\\max_{s, a} (Q^* (s, a^*) – Q^*(s, a))$, but $c$ of Eq.(9) is the hyperparameter. \n\n3. The authors use Likelihood-Free Importance Weights (LFIW) to estimate the density ratio $d^{\\pi_k}(s, a)/\\mu(s, a)$. However, I do not fully understand LFIW can estimate it in practice. LFIW assumes that the slow replay buffer contains samples from $\\mu(s, a)$ while the fast replay buffer contains samples from $d^{\\pi_k}$. Does the assumption hold in practice?  \n\nMinor comment\n\n4. In Appendix C, the authors show the pseudo-codes of ReMERN and ReMERT that are integrated with DQN. Would you show the pseudo-codes for the continuous version? In particular, SAC maintains two state-action value functions to avoid the overestimation problem. Did you use the same weight for the loss functions? It would be better to show the update rules to clarify the algorithm. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In Section 5, the authors claimed that ReMERN is robust to the randomness of environments. However, Figure 6 shows that ReMERT is more robust than ReMERN in Walker2d and Ant with noise. So, it is not clear why the two proposed algorithms are suitable for different kinds of MDP. It would be better to discuss this point in more detail. ", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical concerns. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8 hours"}, "extra_text": {}}, {"review_id": "WQtpXw0M7Lu", "reviewer": "Reviewer_Giki", "summary": "Regret\nThis paper explores a theoretical understanding of a current very prevalent method of training deep RL agents: experience replay. It brings an optimization perspective and formulate return maximization using an importance weighting to samples in buffer. The most important contribution of this paper is coming with a solution of weight that is almost analytical, which explains quite a few interesting myth/questions regarding experience replay. (Detailed below). \n", "questions": "", "limitations": "", "rating": 9, "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": "\nFigure 1: the x axis is iteration? What’s the explanation that PER and Discor performing worse than uniform? Any influence from experiment parameters? How many runs are here? Step-size? Number of samples? What are the features? Initialization? What is the particularity of this problem that makes the two methods slower? It is foreseeable that these setup can influence the performance on such a simple example and such a short time of training. I see you have some explanations from line 99, but still it’s not very convincing. Looks like more like an argument than a solid explanation. \n\nThis doesn’t seem a good example (at least it is not well presented: not convincing; no maths or understanding why the two methods are slower than uniform sampling). \n\nEquation 1: this formulation is interesting. Just the dependence of the policy isn’t explicitly dependent on w_k, which is flawed. Perhaps you should define \\pi_k from Q_k. \n\nI assume all w_k>=0? Then shouldn’t it be constrained? It could also be in the form of exp^w. In the paper, w is directly learn for each sample. In practice, there are millions to billions of samples,  generalization between samples is important. Thus considering parameterizing w_k will be interesting. \n\nThat being said, the experiments missed a study of the weights. Are they negative or positive? Any insights into the signs of w on the performance and behavior of the algorithm?\n\nIt looks like an adaptive importance sampling strategy, especially eq 2. In Th 1. Has an importance sampling ratio. I think this is not accidental. I like the “on”-policiness, it is a very interesting understanding of the off-policy samples. The downside is that the learning of w will have a high variance. \n\nNote if Q_k converges to Q at a linear rate (for value iteration, a gamma rate, seems in your eq. 7 it is something like this), then the weights will be exponentially increasing. This will the sampling focus on those samples that will drive Q_k close to Q*. This will be very interesting to show for some generalization case to illustrate this perspective. \n\nThe hindsight Bellman Error is interesting too. That it explains hindsight experience replay is most interesting I think. \n\nAction selection perspective: If a_k is selected with a high probability, then the weight for s, a_k is small. Sampling this state action pair will be small in experience replay. So the weighting will prefer those rarely taken actions, correct? If this is correct, I think the last item of your understanding from Th 1, “a_k is less likely to be selected by the policy“, should be stated more precise like, “samples of rarely taken actions will be replayed more”. That “a_k is less likely to be selected by the policy“ is not necessarily true: it may be influenced by features and many other things. \n\nCould you double check the “2-\\pi_k” and why it’s not “1-\\pi_k”?\n\nBy “informal” you mean a relaxation?\n\nExperiments were performed on Mujoco continuous action tasks, and outperforms Discor, and SAC on four tasks (with a closer gap in Walker2d), which is not bad. \n\nAlso on Meta-World benchmark (8 tasks were selected). The results are more promising than Mujoco, with larger winning gaps. \n\nThe valuation is also done for discrete-action tasks on Atari games. On 5 selected games the algorithm outperforms DQN by a large margin. However, the baseline DQN is weak; you probably needs to include more baselines especially those experience replay,  some model-based methods as well as exploration method (since your weighting relates to action selection perspective). \n\nrelated: experience replay and Atari baselines\n\nRecurrent Experience Replay in Distributed Reinforcement Learning \nhttps://openreview.net/forum?id=r1lyTjAqYX\n\nDistributional Reinforcement Learning for Efficient Exploration\nhttps://arxiv.org/abs/1905.06125\n\n\n\n\n\n\n\n\n\n\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "n/a", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "1.2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a new method for prioritized experience replay by casting the problem of finding optimal prioritization weights as an optimization problem and then approximating its solution. The review team has significant divergence in their opinions about the paper. Multiple reviewers find the optimization-based formulation of prioritized experience replay refreshing and insightful, and are willing to accept the paper based on its novel perspective. However, as reviewers okGN and hPUt have pointed out, the theoretical derivation of the paper has the caveat that the original objective cannot be directly solved, and a fair number of relaxations and approximations need to be employed. No discussion about how those approximations affect the algorithm's ability to optimize the original objective (e.g., can you somehow quantify the approximations involved? consider questions like: do you get an additive approximation, a multiplicative one, and if so, how large are the approximation errors). While we fully acknowledge the authors' argument that it may be simply difficult to optimize the original objective and the approximations may be reasonable and necessary, this caveat still shows that the rather heuristic nature of the method (*), and in light of this, reviewer hPUt argues that the paper should be evaluated mainly on its empirical results which are not sufficiently strong (curves overlap, or the error bars are too large to tell). Given all these considerations, the AC's recommendation still leans towards acceptance, as the lack of a comprehensive theory is not a fatal issue and the rest of the paper is reasonably executed. 

(*) Along this line, the AC strongly urges the authors not to call Theorem 1 a "theorem"; the statement is simply vacuous if read as a theorem, and needs to be called something less formal. The main approximation steps also need to be included for the main text to be self-contained. 
Decision: Accept (Poster)