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": "z93CzEQa0S4", "reviewer": "Reviewer_4bps", "summary": "The paper presents a new experience sampling method by formulating the problem as regret minimization. They try to minimize the gap between the policy given all the data so far and the optimal policy. The paper provides a solution to such a regret minimization problem. Based on the solution, the paper claims that the optimal prioritization strategy indicates that we should pay more attention to experiences with higher hindsight TD error, better on-policiness, and more accurate Q value. Then the paper proposes methods to implement such sampling methods and present experiments in both continuous and discrete control domains to check their methods’ performances. \n\nStrength: \n1. The presentation is reasonably clear.\n2. The problem formulation is novel to me. \n3. The theory provides some insight into sampling experiences in RL.\n4. The experiments contain both challenging continuous and discrete control domains. ", "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": "Originality. It seems novel to me. \n\nClarity. The presentation is reasonably clear. \n\nSignificance. The topic itself is important. However, the result is not convincing, as I pointed out in the quality part below. \n\nQuality. See concerns below. \n\n1. Section 3.1. I would not consider PER and DisCor are two representative algorithms. In some sense, PER also leads to a more accurate Q value faster. Please see the missing citation later. In fact, one can definitely argue that a regular ER is also trying to learn more accurate Q values faster. Without ER, one may use a single experience to update the network/value function, which is definitely slower. \n\nFurther, L101-L104 is simply not justified. Using a target different from maximizing the expected return is common, from policy-based methods to value-based methods. L103, “for example, when the Bellman target is inaccurate, … ” For any stochastic optimization algorithm, there is no guarantee that each single updating step can lead to an improvement in the reduction of the loss function. Hence, such an example is meaningless. \n\nThe motivating example in Fig 1 is invalid because of both lack of details and the design itself.  \n\na. Why compare PER to uniform? The latter has access to all the states, and hence I guess it also has access to the model?  Does PER have access to all the states and the model? \nIf not, the comparison is unfair and pointless. First, PER does not have the same information as Uniform. Second, Uniform across state space is usually not doable in continuous domains. Are you trying to claim uniform sampling is what you want to design? \nIf yes, PER should learn really quickly, as it should learn s_0 to s_3’s values really quickly, and when at s_0, it would realize that the right action has a larger value. \nb. On such a simple domain, the learning rate should be finely swept rather than fixed as a constant 0.1. \nc. The domain should be more useful to demonstrate the exploration strategy. What is the exploration strategy used?  \n\n2. The theoretical result is not rigorous. \n\nFirst, the formulation of minimizing regret is problematic. According to objective (1),  the optimal Q_k should simply be B^\\ast Q_{k-1}, then the constraint is satisfied. Or do you mean it should not be a constraint; it should also be part of the objective? Furthermore, are there any constraints on the magnitude of the weights w_k? I would be surprised if there is no such constraint. \n\nHow can a theorem be informal? Would you please provide a clear answer? The assumption and important technical lemmas should be moved to the main body. \n\nFurther, I believe assumption 1 in the appendix is invalid. First, what is H? It is an undefined notation. How large could it be? Do you concern about the finite horizon setting? If so, it is different from the background section in the main body. \n\nAnd, such an assumption is counter-intuitive. It says once a state-action pair gets visited, the chance of going back to it is low. It seems contrary to the traditional ergodic/recurrency assumption. The paper also says, “the assumption is trivial in continuous spaces”; however, the theorem is designed for the tabular case. \n\nThe result of theorem 1 requires access to Q^\\ast. How can this be true?\n\n3. The proposed approach. The proposed approach to approximate the terms in Theorem 1 is not convincing. First, approximating |Q_k - Q^\\ast| is difficult. Does it require learning an environment model? Second, it is hard to believe an algorithm that needs so many approximations can work well. The algorithm should be very fragile. This can also be seen in the experiments as I discuss below. \n\n4. What are the relationships between ReMERT and ReMERN? Which one should be preferred in what cases? I cannot see a clear message from the paper. Is ReMERT the ultimate algorithm you propose? And ReMERN is just an intuitive baseline? \n\n5. The experiments. Why compare with SAC? Aren’t your methods generic to be used with many algorithms? (As indicated from L53-54: “Similar to PER, ReMERN, and ReMERT can be a plug-in module to all off-policy RL algorithms 54 with a replay buffer”) I expect the comparison should be DDPG-PER, DDPG-ReMERN, DDPG-REMERT, etc.… Anyway, PER should also be included. \n\nIn addition to PER, an intuitive baseline is to use PER with both long-term and short-term buffers, according to the paper’s theoretical result. \n\nThe variance is too high to distinguish different algorithms. It is not clear how the parameter sweep is done for all these algorithms. ReMERN/T should have many more parameters to tune. \n\n6. Important citation missing: Beyond Prioritized Replay: Sampling States in Model-Based Reinforcement Learning via Simulated Priorities. The work discusses PER in detail and points out its limitations and solutions. \n\nMinors: \n\n1. L26, “For example, minimizing TD error is different from the objective of RL, which is to maximize the expected return of the policy.” This statement is not accurate. First, Q learning does find the optimal policy in the tabular case. And the statement seems to reject all value-based methods. Second, RL has both policy evaluation and control problems. The former does not seek to maximize expected returns. It just evaluates a policy. \n\n2. The notations do not differentiate random variables and realized r.v. \n\n3. L72, the Bellman optimal operator is incorrect. It seems r(s, a) is an r.v., and it should be inside the expectation. The notation of function f can be replaced by Q. \n\n4. some references are messy. Editors are mixed with publication venue. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please see the review section. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "eHL6d-Gbjwr", "reviewer": "Reviewer_wsEk", "summary": "This paper proposes a method for prioritized sampling of a replay buffer to make it easy for temporal difference learning methods to learn faster. The paper builds on prior work, DisCor (Kumar et al. 2020), and derives a more inclusive prioritization estimator which includes accuracy of targets and more on-policyness. Empirical results indicate that the proposed method leads to improved performance on a number of tasks including MetaWorld, Atari and Gym tasks.   ", "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": "Overall the paper has interesting ideas. While on one end, it seems to heavily build on analysis and techniques from DisCor (i.e, the novelty is somewhat on the lower end), and the proposed ReMERN method only adds an additional on-policy correction to the prior method (DisCor), the practical method ReMERT does seem to be a bit better empirically since it uses a different estimator for accuracy of target values. However, since the main ideas seem heavily inspired by prior work, the amount of novelty is a bit low. The results on domains that are harder (e.g, Meta-World and Atari) do seem good, which makes this method empirically interesting.\n\nMy main concerns/questions are:\n\n1. What would the proposed method ReMERN do in the example in Figure 1(a)? Let's say the policy at the current instant takes all left actions. In this case, would the proposed method upweight transitions that also go left since it is a product of DisCor and importance weights, which would both suggest upweighting transitions that go left? So, is the proposed method failing in the same mode as DisCor in this example? \n\n2. Regarding the temporal property of TD error, I find it hard to assume that we can ignore the TD error. TD error in practice is never zero and infact grows during training and saturates. How can we make this optimization error 0? Moreover, no evidence of this is shown in the paper either (that this was indeed the case in the experiments)? Second, the distance to the end is a heuristic, especially on cyclic MDPs like the gym MDPs. So, why does ReMERT still work in these domains? \n\n3. Is there an ablation of TCE without the importance weights? Importance weights have been shown to add variance only, and prior methods have not found it to really help especially when off-policy replay buffers are used. An ablation to clearly disentangle TCE and importance weights is somewhat essential to verify this. This can also be thought of as a version of the DisCor idea instantiated differently, In my opinion, this is important to understand where the gains are coming from in the proposed method. \n\n4. What can be done to handle hindsight Bellman error? What happens if a PER estimator (historical Bellman error) is used for this term? \n\n5.  In RL we are typically interested in optimizing the cumulative regret, not the instantaneous regret. Then why is the regret minimization formulation complete and interesting? Maybe using this formulation in tasks with static datasets is more informative?  Is it possible to analyze this aspect on a gridworld, or does an experiment already do it?\n\nOverall, I am voting for weak acceptance. It would be good to add the ablations listed above and experiments to make sure the claims of the paper are empirically valid, and for more understanding to readers.  I would like to add that the novelty in the paper is relatively on the lower side, but the idea overall is interesting and empirically it seems promising.\n\nThe paper is clearly written and understanding the main ideas is easy from the writeup.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are not discussed. Maybe it is worth discussing more details of when the proposed method fails (e.g., when is the estimation of importance weights hard?)", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "eEvsNFTgz8N", "reviewer": "Reviewer_MNmG", "summary": "The authors derive the optimal prioritization strategy for maximizing return of the greedy policy. From this, the authors introduce two approximations of this optimal strategy as re-weighting strategies when learning the value function. The algorithms are evaluated on several MuJoCo tasks, meta-world and Atari.", "questions": "", "limitations": "", "rating": 4, "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": "My biggest concern is with the novelty of the proposed approach over DisCor. \n- DisCor is derived from a very similar formulation to eqn (1), it's not clear to me why the change from optimizing regret is necessarily better than optimizing value error ($|Q - Q^*|$). In fact, the relaxation in the proof also relies on minimizing this value error (Eqn (12) in the supplementary). So why is this the resulting weight (Eqn (2)) different from DisCor? I think the authors should (1) mention that the origin of Eqn (1) is from DisCor and (2) discuss the differences and/or show why these changes are desirable.\n- It's worth pointing out that Eqn (3) is identical to the solution of DisCor, where DisCor's $\\lambda$ is the density ratio. \n- Figure 1 is used to describe the issues with PER and DisCor. But the explanation doesn't really explain why DisCor is suboptimal. Focusing on the value estimate of the left action is not necessarily wrong (if for example, the left action is over-estimated, and the right action is correct, then we would need to focus on the left action). Furthermore, the authors should compare their proposed approach in this same setting to demonstrate that it solves this suboptimality. \n\nOne novel aspect of the paper is ReMERT which considers the estimation of value error by distance to the terminal state. However, this solution doesn't seem very general as its reliant on the horizon and the existence of terminal states. This approach appears to have some small benefits in MuJoCo but isn't even applicable in meta-world where these algorithms seem the most useful. \n\nClarity could be improved. \n- As mentioned, Section 3.1 could better describe the issues with DisCor. \n- I think small algorithm boxes which summarize the algorithms (i.e. steps 6/7 in Algo 1/2 in the supplementary) would improve the presentation of the algorithms. \n- Eqn (4) doesn't define $f^*$ and $f'$. \n\nGiven the paper claims to introduce a prioritization method, I do find it unusual that there are no baselines which actually use prioritized sampling anywhere in the paper. A quick glance at the PER paper suggests PER outperforms ReMERT on 4/5 of the Atari environments. Does ReMERT compare favorably against DisCor in this setting? The authors should also include ReMERN results. \n\nLack of code is disappointing for reproducibility. \n\nMinor Comments:\n- \"Our analysis gives a theoretical explanation for some prioritization methods, including PER, LFIW and DisCor\" (line 325). I don't think this statement is true at all based on the contents of the paper. \n\nOverall, I think the proposed approach is interesting, but the authors need to better distinguish the benefits of the approach over DisCor.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I'm not sure the authors have discussed limitations. For example, some discussion on the role of the approximations to the optimal strategy would improve the paper. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "Oqs9Dldl9a", "reviewer": "Reviewer_UE11", "summary": "The paper analyzes the desired sampling from an experience replay buffer and proposes two new methods for weighting the samples in the buffer.\nThe paper's contributions are:\n1. An detailed expression of the optimal weights.\n2. An algorithm ReMERN for finding the weights using a neural network.\n3. An algorithm ReMERT for finding the weights using a temporal property.", "questions": "", "limitations": "", "rating": 9, "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": "Originality: Are the tasks or methods new? Is the work a novel combination of well-known techniques? (This can be valuable!) Is it clear how this work differs from previous contributions? Is related work adequately cited?\n\nThe methods are novel. I especially liked Theorem 1 and how it explains the common intuition beyond previous methods. \n\nQuality: Is the submission technically sound? Are claims well supported (e.g., by theoretical analysis or experimental results)? Are the methods used appropriate? Is this a complete piece of work or work in progress? Are the authors careful and honest about evaluating both the strengths and weaknesses of their work?\n\nI am bothered by the results regarding ReMERT. In the example of Figure 1, as in any initial example of RL, it is quite obvious that it's better to update the value from the finish line backward. This result is not surprising and can explain the success of ReMERT in all experiments in the paper. Moving from Theorem 2 to Eq. (11) includes several approximations and bounds, so I get the feeling that not much of the theory propagates to the actual algorithm. Also, the claim that TCE is an approximation of |Qk - Q*| is problematic on its own since if this is the case why not just use it to calculate Q* - in which case there seem to be some kind of equivalence between TCE and reward shaping with distance to goal. To summarize, I think the ReMERT related results are technically sound but misleading to the reader as similar experimental results could have been reached with simple logic, and ReMERT is dedicated towards a specific set of problems with finite horizons.\n\nClarity: Is the submission clearly written? Is it well organized? (If not, please make constructive suggestions for improving its clarity.) Does it adequately inform the reader? (Note that a superbly written paper provides enough information for an expert reader to reproduce its results.)\n\nYes.\n\nFigure 1(b), (c) X-label is missing. \n\nSignificance: Are the results important? Are others (researchers or practitioners) likely to use the ideas or build on them? Does the submission address a difficult task in a better way than previous work? Does it advance the state of the art in a demonstrable way? Does it provide unique data, unique conclusions about existing data, or a unique theoretical or experimental approach?\n\nTheorem 1 is a very significant result I think other researchers are likely to build on. As with most algorithms that require training another neural network for a marginal improvement, it's unlikely ReMERN will be used in practice though I do think it's a significant result. ReMERT is but another example of how to use prior knowledge on the environment, though to the best of my knowledge using it in the experience replay buffer is novel (even though this is not how ReMERT was presented in the paper). \nOverall the paper provides a unique theoretical result with experimental consequences.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: We have a wide range of opinions for this paper. On the positive side, most reviewers agree that the problem addressed by the paper is important. But then, there are several concerns too:

- One of the main issues is the novelty, both theoretical and algorithmic, compared to DisCor (Kumar et al., "DisCor: Corrective Feedback in Reinforcement Learning via Distribution Correction," 2020). Some of the reviewers believe the theoretical novelty is not significant compared to DisCor, while others believe that the theoretical result, especially Theorem 1, is significant and insightful.
Since this is a point of contention, I suggest the authors to be more explicit in comparing their results with the prior work.

- The other issue is regarding the empirical studies, and whether the improvements are significant or not. The paper uses 3 or 4 random seeds in its experiments. The standard deviation of results is often large enough that we have a lot of overlap between curves in figures or the values in the table (for Atari).

- There is also a concern regarding Theorem 2.
The upper bound in Theorem 2 is "$\gamma R_\text{max} / (1 - \gamma) + ...$". This additive form makes the upper bound almost vacuous, as $R_\text{max}/(1 - \gamma)$ is equal to $Q_\text{max}$ and the quantity that is bounded is $|Q_k - Q^*|$, which is trivially smaller than 2 $Q_\text{max}$.
I should note that after bringing up this issue in the discussions, the authors provided another upper bound. That requires a careful verification by the reviewers.

- Some of the theoretical results are not presented precisely. For example, Theorem 1 provides a guarantee about a relaxation of an optimization problem in Eq. (1). But the relaxation is not specified in the main body. It appears to be Eqs. (12-13) in the appendix, which are presented as a part of the proof of an auxiliary lemma. This is simply too remote from where the result is stated.
It might be OK if the result is about a relaxed optimization problem instead of the original one, but the paper should be very clear and precise about it.

Overall, I think this paper might be interesting for the community, but it can benefit a lot from some major revisions. Given that two out of four reviewers are on the negative side, and that one of the positive reviewers is only recommending a weak accept, and all concerns mentioned above, unfortunately I cannot recommend the acceptance of this paper in its current form.
Decision: Accept (Poster)