Revisiting Prioritized Experience Replay: A Value Perspective
Authors: Ang A. Li
Zongqing Lu
Chenglin Miao
Venue:  (2021)

Abstract: Reinforcement learning (RL) agents need to learn from past experiences. Prioritized experience replay that weighs experiences by their surprise (the magnitude of the temporal-difference error) significantly improves the learning efficiency for RL algorithms. Intuitively, surprise quantifies the unexpectedness of an experience to the learning agent. But how surprise is related to the importance of experience is not well understood. To address this problem, we derive three value metrics to quantify the importance of experience, which consider the extra reward would be earned by accessing the experience. We theoretically show these value metrics are upper-bounded by surprise for Q-learning. Furthermore, we successfully extend our theoretical framework to maximum-entropy RL by deriving the lower and upper bounds of these value metrics for soft Q-learning, which is also related to surprise. Our framework links two important quantities in RL, i.e., surprise and value of experience, and provides a theoretical basis to estimate the value of experience by surprise. We empirically show that the upper bounds hold in practice, and experience replay using the upper bound as priority improves maximum-entropy RL in Atari games. 

Under review as a conference paper at ICLR 2021
REVISITING PRIORITIZED EXPERIENCE REPLAY: A VALUE PERSPECTIVE
Anonymous authors Paper under double-blind review
ABSTRACT
Reinforcement learning (RL) agents need to learn from past experiences. Priori- tized experience replay that weighs experiences by their surprise (the magnitude of the lemporal-difference error) significantly improves the learning efficiency for RL algorithms. Intuitively, surprise quantifies the unexpectedness of an expe- rience to the learning agent. But how surprise is related to the importance of experience is not well understood. To address this problem, we derive three value metrics quantify the importance of experience, which consider the extra reward would earned by accessing the experience. We theoretically show these value metrics
roper-bounded by surprise for Q-learning. Furthermore, fully extend our theoretical framework to maximum-entropp RL by deriving the lower and upper bounds of these value metries for soft Q-learning, which turn out to be the product of surprise and "on-policyness" of the experiences. Our frame- work links two important quantities in RI., i.e., surprise and value of experience, and provides theoretical basis to estimate the value of experience by surprise. We empirically show that the bounds hold practice, and experience replay using the upper bound as priority improves maximum-entropp RL in Atari games.
success-
INTRODUCTION
Learning from important experiences prevails in nature. In rodent hippocampus, memories with higher importance, such as those associated with rewarding locations or large reward-predicte errors, are replayed more frequently (Michon et al., 2019; Roscow et al., 2019; Salvetti et al., 2014). People who have more frequent replay of high-reward associated memories show better performance in memory tasks (Gruber et al., 2016; Schapiro et al., 2018). normative theory suggests that prioritized memory access according to the utility of memory explains hippocampal replay across different memory tasks (Mattar Daw, 2018). As accumulating new experiences is costly, utilizing valuable past experiences is a key for efficient learning (Ólafsdóttir et al., 2018).
Differentiating important experiences from unimportant (RL) algorithms (Katharopoulos Fleuret, 2018). Prioritized experience replay (PER) (Schaul al., 2016) is experience replay technique built on deep Q-network (DQN) (Mnih al., 2015), which weighs the importance of samples by their surprise, the magnitude of the temporal-differee (TD) error. As a result, experiences with larger surprise are sampled more frequently. PER signif- icantly improves the learning efficiency of DQN, and has been adopted (Hessel et al., 2018; Hor- gan et al., 2018; Kapturowski al., 2019) and extended (Daley & Amato, 2019; Pan et al., 2018: Schlegel et al., 2019) by various deep RL algorithms. Surprise quantifies the unexpectedness of learning agent, and biologically corresponds to the signal of reward prediction emor in dopamine system (Schultz et al., 1997; Glimcher, 201 1), which directly shapes the memory of animal and human (Lisman & Grace, 2005; McNamara al., 2014). However, how surprise related to the importance of experience in the context of RL is not well understood.
also benefits reinforcement learning
an experience
We address this problem from an economic perspective, by linking surprise to value of experience in RL. The goal of RL agent is to maximize the expected cumulative reward, which is achieved through learning from experiences. For Q-learning, an update on an experience will lead to a more accurate prediction of the action-value agent may get. We define the value of experience as the increase in the expected cumulative reward resulted from updating on the experience (Mattar & Daw, 2018). The value of experience quantifies
better policy, which increases the expected cumulative reward the

---

Under review as a conference paper at ICLR 2021
the importance of experience from first principles: assuming that the agent is economically rational and has full information about the value of experience, it will choose the most valuable experience to update, which will yield the highest utility. As supplements, derive two more value metrics, which corresponds to the evaluation improvement value and policy improvement value due to update on an experience.
In this work, we mathematically show that these value metrics are upper-bounded by surprise for Q-learning. Therefore, surprise implicitly tracks the value of experience, and accounts for the impor- tance of experience. We further extend our framework to maximum-entropy RL, which augments the reward with an entropy term encourage exploration (Haamojj et al., 2017). We derive the lower and upper bounds of these value metrics for soft Q-lcarning, which are related to surprise and con-policyness" of the experience. Experiments in Maze and CartPole support our theoretical results for both tabular and function approximation RI. methods, showing that the derived bounds hold in practice. Moreover, we also show that experience replay using the upper bound as priority improves maximum-entropy RL (i.c., soft DQN) in Atari games.
MOTIVATION
2.1 Q-LEARNING AND EXPERIENCE REPLAY
We consider Markov Decision Process (MDP) defined by a tuple (S, 7) where S is finite set of states, A is a finite set of actions, P is the transition function, R the reward function, and Y [0, 1] is the discount factor. A policy π of agent assigns probability T(a)s) to each action a E AA given state s S. The goal is to learn an optimal policy that maximizes the expected discounted return starting from time step f, G, rt + TT++1 72 +
Zi=o 7're+s, where rs is the reward the agent receives at time step t. Value function Ux is defined as the expected return starting from state s following policy æ, and Q-function gr (s, a) is the expected return on performing action a in state s and subsequently following policy π.
According to Q-learning (Watkins & Dayan, 1992), the optimal policy can be learned through policy iteration: performing policy evaluation and policy improvement interactively and iteratively. For each policy evaluation, we update Q(s, a). an estimate of gr (s,a).. by
Qnew (s, a) Qoua a) + aTD(s,a,r,'))
where the TD error TD(s, s') r + max,' Quta(s' a') Quaa(s, a) and a is the step-size parameter. Qnew and Quld denote the estimated Q-function before and after the update respectively. And for each policy improvement, we update the policy from Vold neww according the newly estimated Q-function,
Tnew = arg max Qnew (s, a).
Standard Q-learning only uses each experience once before disregarded, which sample inefficient and can be improved by experience replay technique (Lin, 1992). We denote the experience that the agent collected at time & by a 4-tuple eg = {sk; aj Tk, s According to experience replay, the experience ex is stored into the replay buffer and can be accessed multiple times during learning.
2.2 VALUE METRICS OF EXPERIENCE
To quantify the importance of experience, we derive three value metrics of experience. The utility of update on experience eş is defined as the value added to the cumulative discounted rewards starting from state Sk. after updating will yield the highest utility to the agent. We denote such utility as the expected value of backup EVB(cL) (Mattar & Daw, 2018),
εx- Intuitively, choosing the most valuable experience for update
EVB(E)) U Usae (5k) Usraa (5k)
Σ Tnew (a) 88 m (Sk, a)
Σ Total Totaa (m)s (Sk, a)
(1)
where Tolds Vrai and qn are respectively the policy, value function and Q-function before the up- date, and Tnews Unew and qow. those after. As the update experience eg consists of policy
2

---

Under review as a conference paper at ICLR 2021
Linear GridWorld
random
b
Prioritize by surprise
Replay needed
Time
c
Prioritize by EVB
Value
Time
Figure I: a. Illustration of the "Linear GridWorld" example: there are grids and 4 actions (north, south, cast, west). Reward for entering the goal state (cheese) is 1; reward is 0 elsewhere. b-c. Examples of prioritized experience replay by surprise and value of experience (EVB). The main difference that EVB only prioritizes the experiences that are associated with the optimal policy; while surprise is sensitive to changes in value function and will prioritize non-optimal experiences, such as those associated with north or south. Here squares represent states, triangles represent actions, and experiences associated with the highest priority are highlighted. d. Expected number of replays needed to learn optimal policy, as the number of grids changes: uniform replay (blue), prioritized by surprise (orange), and EVB (green).
evaluation and policy improvement, the value of experience further be separated to evaluation improvement value EIV(ex) and policy improvement value PIV(e:) by rewriting (1):
EVB(EN) = Σ Teew (alss) Tosa (a su Moaz (Sk; a) Σ (ata su) Ma (sx, a) In (Sk, a)],
((V()))
HIV(e>)
where PIV(e;) measures the value improvements due to the change of the policy, and EIV(ex) cap- tures those due the change of evaluation. Thus, we have three metrics for the value of experience: EVB, PIV and EIV.
2.3 VALUE METRICS OF EXPERIENCE IN Q-LEARNING
For Q-learning, we use Q-function to estimate the true action-value function. A backup over an experience eş consists of policy evaluation with Bellman operator and greedy policy improvement. As the policy improvement greedy, we can rewrite value metrics of experience to simpler forms. EVB can be written as follows from (1),
EVB(cx) = max Qnew max (ska a).
Note that EVB here is different from that in Mattar & Daw (2018): in our case, EVB is derived from Q-learning; while in their case, EVB is derived from Dyna, a model-based RL algorithm (Sutton, 1990). Similarly, from (2), PIV can be written as
(IV(ex) max Qnew a) Qnew dota);
(4)
where Oold arg max, (Sk, a), and EIV can be written as
(IV( Quew (Sk, Guta) Qota Gola).
(5)
2.4 A MOTIVATING EXAMPLE
We illustrate the potential gain of value of experience in a "Linear GridWorld" environment (Fig- la). This environment contains N linearly-aligned grids and actions (north, south, east, west).
3

---

Under review as a conference paper at ICLR 2021
The rewards are rare: 1 for entering the goal state and 0 elsewhere. The solution for this environment is always choosing east.
We use this example to highlight the difference between prioritization strategies. Three agents per- form Q-learning updates on the experiences drawn from the same replay buffer, which contains all the (4N) experiences and associated rewards. The first agent replays the experiences uniformly at random, while the other two agents invoke the oracle to prioritize the experiences, which greedily select the experience with the highest surprise EVB respectively. In order to learn the optimal policy, agents need to replay the experiences associated with action east in a reverse order.
For the agent with random replay, the expected number of replays required is 4 (Figure 1d). For the other two agents, prioritization significantly reduces the number of replays required: prioriti- zation with surprise requires 4. replays, and prioritization with EVB only uses N replays, which is optimal (Figure Id). The main difference is that EVB only prioritizes the experiences that are associated with the optimal policy (Figure Ic), while the surprise sensitive changes in the value function and will prioritize non-optimal experiences: for example, the agent may choose the experi- ences associated with south or north in the second update, which are not optimal but have the same surprise as the experience associated with east (Figure lb). Thus, EVB that directily quantifies the value experience can serve as an optimal priority.
UPPER BOUNDS OF VALUE METRICS OF EXPERIENCE IN Q-LEARNING
PER (Schaul et al., 2016) greatly improves the learning efficiency of DQN. However, the underlying rationale is not well understood. Here, we prove that surprise is the upper bound of the value metrics Q-learning.
Theorem 3.1. The three value metrics of experience es in Q-learning ((EV)), |PIV| and (EVV)) are bounded by a TDDD(s (kk ags Tk, sk)), where is step-size parameter.
Proof. See Appendix A.I.
In Theorem 3.1, we prove that [EVB]. |PIV) and |BIV] are upper-bounded by the surprise (scaled by the learning step-size) in Q-learning. As surprise intrinsically tracks the evaluation and policy improvements, it can serve as an appropriate importance metric for past experiences. We will further study these relationship in experiments.
4 EXTENSION TO MAXIMUM-ENTROPY RL
In this section, we extend our framework to study the relationship between surprise and value of experience maximum-entropy RI., particularly, soft Q-learning.
4.1 SOFT Q-LEARNING
Unlike regular RL algorithms, maximum-entropp RL augments the reward with an entropy term: R = (H(-ss))) where H(-) the entropy, and / an optional temperature parameter that determines the relative importance of entropy and reward. The goal is to maximize the expected cumulative autropy-augmented rewards. Maximum-entropy RL algorithms have advantages at cap- turing multiple modes of near optimal policies, better exploration, and better transfer between tasks.
Soft Q-learning is an off-policy value-based algorithm built on maximum--nttrop RL principles (Haarnoja et al., 2017; Schulman et al., 2017). Different from Q-learning, the target policy of soft Q- learning is stochastic. During policy iteration, Q-function updated through soft Bellman operator ssoft and the policy is updated to maximum-entroopy policy:
Policy Evaluation: Qualll (s, a) = _1000 Quill (s, = + + Vooall (s')
1
Policy Improvement: Tawn (a|s) softmax,
Quett a));
4

---

Under review as a conference paper at ICLR 2021
where softmaxx (z) exp(zi)/ E, exp(x;; is the softmax function, and the soft value function (s))((s) (s) is defined as,
s (8) En ( (8, a) - log()(a|s))) = 3 log Σ exp Q (8,
Similar as in Q-learning, the TD-error soft Q-learning (soft TD error) is given by: TD a, r, = + /Vola (s') Vold (8, a).
4.2 VALUE METRICS OF EXPERIENCE IN MAXIMUM-ENTREN RL
Here, we extend the value metrics of experience to soft Q-learning. Similar as (1), EVB for
maximum-entropy RL is defined as,
EVBBal (ex)
ueell (8k) old (8k)
Σ new (al S/ { (nnw soft
(kk a) 3 (log(TTew
(new (a)
(s)))))
Tota (a) (
saft (sk, a) - 3 (ag(=ou(a|sk)))
(6)
EVB soft can be separated into PIVsoft and Elv which respectively quantify the value of policy and evaluation improvement in soft Q-learning.
Plysoft Σ
new (a|sa (k) (oow (8k, a) 3 log Tnew [s]s
Σ Tata (ynow (sk, a)
Σ
Tne (a(sk) - Tota (ata(a) (a)8k) } Inow (Sk, a) (TTe (-1s)) - H (mTaa(-|8Kk) (7)
EIVsoft
Σ
Tota (a) |&k [yro (sk; a)
soft (sk: a)).
Value metrics of experience in maximum-entropy RL have similar forms in regular RL except for the entropy term, because changes in policy leads to changes in the policy entropy and affects the entropy-augmented rewards.
4.3 LOWER AND UPPER BOUNDS OF VALUE METRICS OF EXPERIENCE IN SOFT Q-LEARNING
We theoretically derive the lower and upper bounds of the value metrics of experience in soft Q- learning.
Theorem 4.1. The three value metrics of experience et soft Q-learning (EVBBBf), |PIV and [ETV are upper bounded by pm |TDoft), where p moxx(moid(a) sk), Tnew (ax [sk)] is policy related term.
Proof. See Appendix A.2.
Theorem 4.2. For soft Q-learning, |EVB and [ETVoOR] (but not [P]Voo|) are lower bounded by 1TTh | where prl = min Taua (ap (8k), Tnow (ar(sk)} is policy related term.
Proof. See Appendix A.3.
The lower and upper bounds soft Q-learning include a policy term with the surprise (the magni- tude of the soft TD error). The policy related term Px quantifies the "on-policyness" of the experi- enced action. And the bounds become tighter as the difference between (a (sx) and Thew (ax [8)) becomes smaller. Surprisingly, the coefficient of the entropy term 3 impacts the bound only through
5

---

Under review as a conference paper at ICLR 2021
the policy term, which makes it an excellent priority even & changes during learning (Haarnoja et al., 2018). As 0 I p < 1, the value metries are also upper bounded by surprise (TDD=))) alone, which is similar as in Q-earniing However, as ((ag(s)) is usually less than 1, surprise is looser upper bound in soft Q-learning. This supports previous study, which empirically shows that directly applying PER using surprise alone in soft Q-learnigg does not significantly improve the sample efficiency (Wang & Ross, 2019). We will further study these relationship in experiments.
EXPERIMENTS
Our experiments aim to answer following questions: (i) Do the theoretical bounds of value metrics of experience hold true in practice? (ii) If the bounds hold, are they tight? (iii) Do the bounds derived RL help to improve performance? First, we implement tabular versions of Q- learning and soft Q-learning in Maze to verify the bounds in tabular methods. Second, by slightly modifying the definition of the value metrics of experience, we extend our framework to function approximation methods, which is far more powerful than the tabular methods (see Appendix A.4). We implement DQN and soft DQN in CartPole to examine the bounds in function approximation methods. Finally, we implement PER with the theoretical upper bound as priority for soft DQN and evaluate its effectiveness.
for maximum-entie
Throughout the experiments, the value metries of experience (EVB, PIV and EIV) for Q-learning are calculated using (3), (4), and (5), and those for soft Q-learnig are calculated using (6), (7), and (8). For soft Q-learning, we do not model the actor explicitly: the policy calculated as the softmax of the soft Q-function (see Section 4.... The upper bound for value metrics in Q-learning surprise (Theorem 3.1), while the lower and upper bounds for soft Q-learning are calculated according Theorem 4.1 and 4.2, which include a policy term and surprise. The experimental details are described in Appendix A.5 and all the codes are available at: https: //ttt::///ithbb. com/ hwm//Rfoolife//e/
5.1 MAZE
The first set of experiments are conducted in a maze environment of a 5 x 5 square with walls. The agent needs reach the goal zone by moving one square in any of the four directions (north, south, east, west) each time. We implement tabular versions of Q-learning and soft Q-learning to solve this problem.
For each algorithm, the value metrics of experience as well as the theoretical bounds are illustrated in Figure 2. As we can see from upper panel, all three value metrics of experience are bounded by the surprise for Q-learning. As our theory predicts, the absolute values of EIV are either equal to the surprise (if the action of the experience is the best action before update) or 0. For soft Q-learning, the three value metrics of experience are bounded by the theoretical upper bound, and EVB and EIV are bounded by the theoretical lower bound, supporting our theory (Theorem 4.1 and 4.2). There is a large proportion of EVBs lies on the identity line, indicating the bounds are tight. The proportion of non-zero values experiences is higher in soft Q-learning than in Q-learning, because all value metrics of experiences affected by the "on-policyness" of the experienced actions. Q- learning learns a deterministic policy that makes most actions of experiences off-policy, while soft Q-learning learns stochastic policy that results in less sparse values of experiences. In summary, the experimental results in the maze environment support the theoretical bounds of value metrics of experience in Q-learning and soft Q-learning.
5.2 CARTPOLE
CartPole is pendulum with center of gravity above its pivot point. The goal is to keep the pole balanced by moving the cart forward and backward. We implement DQN and soft DQN (DQN with soft-update) in this environment. For DQN, we replace the Q-network in Mnih et al. (2015) with two-layer MLP. For Soft-DQN, all the settings are the same with DQN, except for two modifications: during policy evaluation, the (soft) Q-network is updated according the soft TD error; during policy improvement, the policy is updated following a maximum maximum-entropy the values (see Section 4.1.
-ntrropy policy, as the softmax of

---

Under review as a conference paper at ICLR 2021
Q-learning
[P]
[T]
[D]
Soft Q-leaming (upper)
14-
[EM]]
[P0]]
the max (TD]
ro max [TD]
tho max (TD)
Soft Q-learning (lower)
(B4]
mm
(TD)
rho_min
[TD]
[TD]
Figure 2: Results of Q-learning and soft Q-lcarning in Maze. a-c. surprise (the magnitude of TD error) absolute value of EVB (left), EIV (middle) and PIV (right) in Q-learning. d-f. Theoretical upper bound and g-i. lower bound v.s. absolute value of EVB, EIV and PIV in soft Q-learning. The red line is the identity line.
By slightly modifying the definition of value metrics of experience, we can extend our framework to function approximation methods (see Appendix A.4). The value metrics of experience as well as the theoretical bounds are illustrated in Figure 3. All value metrics of experience in DQN (Figure 3a- c) and soft DQN (Figure 3d-f) are bounded by the theoretical upper bounds. For DQN, absolute EVBs and PIVs uniformly distributed in the bounded area, while absolute EIV' equal the surprise or O. Results are different in soft DQN, where absolute EVBs and EIVs are distributed more closely towards the theoretical upper bounds, suggesting the upper bound in soft Q-learning is tighter. Moreover, (Figure 3g-h) shows the EVBs and EIVs lower bounded by p TD while PIV' are not The experimental results confirm the bounds of value metrics in function approximation methods.
5.3 ATARI GAMES
In this set of experiments, investigate whether the theoretical upper bound of value metries of experience, which balances the surprise and "on- "on--ooioyee poliecyolss"" of the experience (Figure 6), can serve appropriate priority for experience replay in soft Q-learning More specifically, the performance of soft DQN with different prioritization strategies: uniform replay, prioritization with surprise or the theoretical upper bound (pTT * (DD ), which are denoted by soft DQN, PER and VER (valuable experience replay) respectively. This set of experiments consists of nine games from Atari 2600 games, whose goal is learning to play each of the games with the screen pixels the only input. We closely follow the experimental setting and network architecture outlined by
compare

---

Under review as a conference paper at ICLR 2021
DQN
[TD]
[T0)
110
Soft DQN (upper)
11000
tho
rho_max
max
Soft DQN (lower)
[TD]
[TD]
Figure 3: Results of DQN and soft DQN in CartPole. a-c. surprise (the magnitude of the TD error) vs. absolute value of EVB (left), EIV (middle) and PIV (right) in DQN. d-f. Theoretical upper bound and g-i. lower bound v.s. absolute value of EVB, EIV and PIV in soft DQN. The red line is the identity line.
Mnih et al. (2015). For each game, the network is trained on single GPU for 40M frames, or approximately days.
Figure 4 shows that soft DQN prioritized by surprise or the theoretical upper bound significantly outperforms uniform replay in most of the games. On average. soft DQN with PER or VER outper- form vanilla soft DQN by 1.8% or 18.0% respectively. Moreover, VER shows higher convergence speed and outperforms PER in most the games (8.47% on average), which suggest that tighter upper bound on value metrics improves the performance of experience replay. These results suggest that the thcoretical upper bound can serve as an appropriate priority for experience replay in soft Q-learning.
DISCUSSION
In this work, we formulate a framework to study relationship between the importance of experience and surprise (the magnitude of the TD error). To quantify the importance of experience, we derive three value metries of experience: expected value of backup, policy evaluation value, and policy improvement value. For Q-learning, we theoretically show these value metrics are upper bounded by surprise. Our claims supported by the experiments of tabular Q-learning and DQN. Thus, surprise implicitly tracks the value of the experience, which leads to high sample efficiency of PER. Furthermore, extend framework maximum-entropy RI., by showing that these value
8

---

Under review as a conference paper at ICLR 2021
A
BattleZone
Bexing
Seft DON
Seft DON
Sont DON
PCR
130
Score
Score
2011
Epoch
Epoch
Epoch MsPacman
Beomkidder
DemonAttack
3000
4000
Score
Score
2009
Epoch
Esoch
Epoch
Obert
Seaquest
Space invaders
Soft DON
PER VES
FFR VOR
V2h
Score
Score
Score
2004
Epoch
Epoch
Epoch
Figure 4: Learning curve of soft DQN (blue lines), and soft DQN with prioritized experience replay in term of soft TD error (PER, orange lines) and the theoretical upper bound of value metrics of experience (VER, green lines) nine Atari games.
metrics are lower and upper bounded by the product of a policy term and surprise. The results in soft Q-learning and soft DQN supports our theory. Moreover, we employ the upper bound as the priority for experience relay, termed as VER, in soft DQN. And we empirically show that VER outperforms PER and significantly improves the sample efficiency of soft DQN.
By linking surprise and value of experience, two important quantities in learning, our study has the following implications. First, from a machine learning perspective, our study provide a framework to derive appropriate priorities of experience for different algorithms, with possible extension to batch RL (Fu et al., 2020) and sequence experience replay Brittain et al. (2019). Second, for neuroscience, our work provides insight on how brain might encode the importance of experience. Since surprise biologically corresponds to the reward prediction-error signal in the dopaminergic system (Schultz et al., 1997; Glimcher, 2011) and implicitly tracks the value of the experience, the brain may account on it to differentiate important experiences.
REFERENCES
Mare Brittain, Josh Bertram, Xuxi Yang, and Peng Wei. Prioritized sequence experience replay. arXiv preprint arXiv: 1905. 12726, 2019.
9

---

Under review as a conference paper at ICLR 2021
Brett Daley and Christopher Amato. Reconciling X-returns with experience replay. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Laurent El Ghaoui. Optimization models and applications,
com/
keeppies/cse wtt.leeesccaa888e222222
2018. Livebook visited Spring 2018.
Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine. D4rl: Datasets for deep
data-driven reinforcement learning. arXiv preprint arXiv:2004.072199 2020.
Paul W Glimcher.
Understanding dopamine and reinforcement learning: the dopamine reward pre- diction error hypothesis. Proceedings of the National Academy of Sciences, 108(Supplement 3): 15647-15654, 2011.
Matthias J. Gruber, Maureen Ritchey, Shao-fang Wang, Manoj K. Doss, and Charan Ranganath. Post-learning Hippocampal Dynamics Promote Preferential Retention of Rewarding Events. Neu- ron, 1000:1110-11201 2016.
Tuomas Haarnoja, Haoran Tang. Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep energy-based policies. In International Conference on Machine Learning (ICML), 2017.
Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, et al. Soft actor-critic algorithms and appli- cations. arXiv preprint
2018.
Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bital Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. In AAAI Conference Artificial Intelligence (AAAT), 2018.
Dan Horgan, John Quan, David Budden, Gabriel Barth-Maron, Matteo Hessel, Hado Van Has- selt, and David Silver. Distributed prioritized experience replay. International Conference on Learning Representations (ICLR), 2018.
Steven Kapturowski, Georg Ostrovski, John Quan, Remi Munos, and Will Dabney. Recurrent perience replay in distributed reinforcement learning. In International Conference on Learning Representations (ICLR), 2019.
Angelos Katharopoulos and François Fleuret. Not all samples are created equal: Deep learning with importance sampling, arXiv preprint 1rXiiv180330094: 2018.
Long-Ji Lin. Self-improving reactive agents based on reinforcement learning, planning and teaching. Machine learning, 8(3-4):293-321, 1992.
John E Lisman and Anthony A Grace. The hippocampal-vir loop: controlling the entry of informa- tion into long-term memory. Neuron, 46(5):703-713 2005.
Marcelo G. Mattar and Nathaniel D. Daw. Prioritized memory access explains planning and hip- pocampal replay. Nature Neuroscience, 21911):1609-1117, 2018
Colin G McNamara, Álvaro Tejero-Cantero, Stéphanie Trouche, Natalia Campo-Urriza, and David Dupret. Dopaminergic neurons promote hippocampal reactivation and spatial memory persis- tence. Nature neuroscience, 17112)11588-1660 2014.
Frédéric Michon, Jyh-Jang Sun, Chae Young Kim, Davide Ciliberti, and Fabian Kloosterman. Post- learning hippocampal replay selectively reinforces spatial memory for highly rewarded locations. Current Biology, 1369)11434 2019.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Belle- mare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wier- stra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7540):529-533 2015.
H Freyja Ólafsdöttir, Daniel Bush, and Caswell Barry. The role of hippocampal replay in memory and planning. Current Biology, 28())R377R50. 2018.
10

---

Under review as a conference paper at ICLR 2021
Yangchen Pan, Muhammad Zaheer, Adam White, Andrew Patterson, and Martha White. Organizing experience: a deeper look at replay mechanisms for sample-based planning in continuous state domains, arXiv preprint arXiv:18066.o 04624, 2018.
Emma L Roscow, Matthew W Jones, and Nathan F Lepora. Behavioural and computational evidence for memory consolidation biased by reward-prediction errors. bioRxiv, pp. 716290, 2019.
Beatrice Salvetti, Richard GM Morris, and Szu-Han Wang- The role of rewarding and novel events in facilitating memory persistence in separate spatial memory task. Learning & memory, 21(2): 61-72, 2014.
Anna C Schapiro, Elizabeth A McDevitt, Timothy T Rogers, Sara C Mednick, and Kenneth A Nor- man. Human hippocampal replay during rest prioritizes weakly learned information and predicts memory performance. Nature communications, 9(1): 1-1, 2018.
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. In International Conference on Learning Representations (ICLR), 2016.
Matthew Schlegel, Wesley Chung, Daniel Graves, Jian Qian, and Martha White. Importance resam- pling for oof-pol prediction. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
John Schulman, Xi Chen, and Pieter Abbeel. Equivalence between policy gradients and soft q- learning. arXiv preprint (:XKv:/704.00444 2017.
Wolfram Schultz, Peter Dayan, and P Read Montague. A neural substrate of prediction and reward. Science, 275(5306):1993-1599 1997.
Richard S Sutton. Integrated architectures for learning, planning, and reacting based on approxi- mating dynamic programming. In Machine learning proceedings 1990, pp. 216-224. Elsevier, 1990.
Che Wang and Keith Ross. Boosting soft actor-critic: Emphasizing recent experience without for- getting the past. arXiv preprint arXiv:1906. 04009, 2019.
Christopher J. C. H. Watkins and Peter Dayan. Q-learning. Machine Learning, 833-4)277--99,, 1992.
A APPENDIX
A. PROOF OF THEOREM 3.1
In this section, derive upper bounds of value metrics of experience in Q-learning The absolute EVB can written as
EVB(ex)) = max Qnew (sk, a) - max a)]
S max Qnew (sk: a) (ola(kk a)]
S <T]TD(sk ak, Tk, *k));
(9)
where the second line is from the contraction of max operator.
The absolute PIV can be written as [eIV())) max Qnew a) Qnew (5k, arg max Qoua
max Quew (Sk, a) Qnew arg max Qota (82, a))
max Qnew (8k, max Qola(Sk, a) lam=a, a TT (sk, ak. ak. Tk, s(
(10)
where the second line is from that the change in Q-function following greedy policy improvement is greater or equal to O, and the third line is from the update of Q-function. For TD(sk, ak, Tk, s).) 2 0, have
< max Qnew (sk. a) max Qoia (5k, a) S TTD(Ek Ok Tki 16))
11

---

Under review as a conference paper at ICLR 2021
And for (s(sk, e ab, Pk: 5%.) S O, have
max Qnew (5k, a) max (ola S
Bring above inequalities to 10, have
PIV(())] & a ( on, Tx, sk)l
(11)
Similarly, the absolute EIV can be written as follows,
[eV(())) = neww (8k, Gold) - (sk: Gold)
A a (D 8k 0gg Pky $6)]
S < (k: Th; s1
(12)
For equations (9) and (11), the equality is reached if the experienced action is the same as the best action before and after the update. For (12), the equality is met if the experienced action the best action before update.
A.2 PROOF OF THEOREM 4.1
In this section, we derive upper bounds of value metrics of experience in soft Q-learning. For soft-Q learning, |EVB can be written
EVB (cx)) I = 18g Σ expl Quen (sk, a)) - -Blog] Σ
exp( Qaid (sk, (sk, a))l
a
1 log
Σ exp { (0a0 (sk, a) la=a, TD log Σ exp
1 Qua (sk, a)}-
3
Let us define the LogSumExp function F( = 3 log E, exp (3) The LogSumExp function F())
convex, and strictly and monotonically increasing everywhere in its domain (El Ghaoui, 2018).
The partial derivative of F(ž) is softmax function
(F = softmax o) 2 0.
Oz;
which takes the same form as the policy of soft Q-learning. For < O, we have:
0F (F
< F(I + c...) FII,,.,,,
dx,
Similarly, for e 2 0, we have,
OF c....
0 < F(z (Z., E...)
Oz;
By substituting F, by Qualt (sk, ag) and e by TD and rewriting partial derivative of F(ū) into policy form, we have following inequalities. For TD <
(asa TD < log Σ
Eexpl -
1 Quati (sk, a)) 3 log Σ exp(
1 Qual (sk, a)) S 0
3
Similarly, for TD soft O, we have
0 < log Σ expl
gaatt (sk, a)) log Σ expl 1 Quaf( (Sk, a)) Tnow (sx) TDD
(
Thus, we have the upper bounds of JEV
EEV (ex) & max max(mma(qelssc). Nnew (ax(sx)) |TD
12

---

Under review as a conference paper at ICLR 2021
For [P[V we have,
(exx))(ex)) - Σ Nnew ( new (sk, a) 33 (new (a) [)]s
Σ Tota Taaa ( (sk, a) - (og((T
now (al s) men ($k, Iog (a|s)))
Σ
Told (old(als) { (sk a)
log (ot())) Told (a (4|s)) TD)
Quen (Sk. a)
Qoid (sk, a)
B log
exp
3 log Σ exp
Total (ax |s TD
B
where the second line because the policy improvement value always greater than or equal to 0, and the third line is by reordering the equation.
For TD soft
0, we have:
Quei (sk. a)
Quat (kk: a)
0 S B log
exp
- log
exp
Told (ax (TD S Nnow ( TDD
B
For TD
0, we have:
Quali (sk. a)
Quai (sk, a)
0 S Blog
exp
B log
exp
Told (ooa(axss)TD') S Tosa ((xlx)) TDyoff
B
Thus, we have the upper bounds of |PIV
Pivsof < max Maax((Taa(aa (sx), knew (aclss)} * [TD
Also, for |IV we have:
of (ex)== Σ
Total (a) ( (sk, a) Quaa (sk: a)ll
(als) * TD
< max Tatal (a ssk), nnow (ak/sk)) |DDsoft
There is no lower bound of the similar form for |PIV
A.3 PROOF OF THEBREM 4.2
In this section, we derive lower bounds of value metrics of experience soft Q-learning. Similar as deriving upper bounds in Appendix A.2, we derive the lower bounds for [EVB] using the the LogSumExp function F(T)= = 3 log E, exp (3) For < 0, we have:
OF ..., FG + C.... 5.
F(z F; + c....) F F(I
dr,
Similarly, for e 2 0, we have,
0F OF (I Lis 2
F(o1,.., e....) (211,.., 2
Or, By substituting v, by Quell (5R, ax) and by TD and rewriting partial derivative of F(ž) into policy form, we have following inequalities. For sof <
3 log Σ expl Qaaf (SM, a)) - 3 log Σ exp
soft (Sk, a)) < Tnew (aulsk) TD <0
13

---

Under review as a conference paper at ICLR 2021
Similarly, for TD O, we have:
3 log Σ exp( (sk (sk: a)) - 1og Σ exp( Rold (sk, (sk; 2 Taia(ak (sk
) IDD 2
Thus, we have the lower bounds of [EVB*nn
EVB"""(e)) 2 min Tau (xx/s)))))))))))))))))))(())(( (sk), Tnow Noo (aklsk)) TD
For |EIVsoft, we have:
ElVsol (e+)
Σ Tosal (Q]s) (sk: a) Quail (#k, a)ll
(als) |DDsott
min Mana(as (kk); Tnew (ax [sx)}
TDDoa
A.4 EXTENSION TO FUNCTION APPROXIMATION METHOD
In function approximation methods, we learn a parameterized Q-function Q az 0c). The parameter updated on experience 6₁ through gradient- based method,
0++1 = 02 + a( (arrgee (8k, a&) (+ ax; 0,)) Vo. Q(*,, <x; 0z)), where a is the learning rate and Quarger is the target value, defined
targe (k: ax) = rk + y max Qs d': 0t).
And the TD-error is defined as:
TD Qurger (8k, 0x) (sk, 4 0z)
As a in function approximation Q-learning usually very small, for each update, the parameterized function moves to its target value only by small amount.
Our framework can be extended function approximation method by slightly modifying the defi- nition of the value metrics of experience: replacing the Q-function after the update (Q(s, a; 0++1)) by the target Q value (Qurge (s. a)) in the value metries of experience (1-5 and 6-8). The intuition behind this modification is simple: the value is defined by the cause of the update (target Q-value), but not the result of the update through gradient-bases update. With this modification our theory is applicable to all function approximation methods, regardless the specific forms of the function approximator (linear function or neural networks). For Q-learning the value metrics can be written as:
EVB(ex) = max Qtarger (sk, a) - max ((sk, a; 0z)
PIV(ex) =
max Qurrer (8k, a) Qtarger (8k, Gola) (IV()x) = Qtarger (sk, dota) - Q(K,, Gold: 02).
And for soft Q-learning, the value metrics can be written as:
EVB (ex) = 3 log Σ expl Quaner (Sk, a)) B log
Σ expl 1 expl= Quan Q a;);))
Quoft target (8k. a)
Qroft (sk, 0t) Todd (oud (axls) (ax
PIvsof((ex)
log
exp
3 log Σ exp 3
EIv (ex) Σ
(ata(a (Sk, a) Qroft (sk, (sn,00 0,)].
After the modifications, the value metrics of experience have similar form as the tabular case, and all Theorems derived in the tabular case can be applied to function approximation methods.
14

---

Under review as a conference paper at ICLR 2021
Q-learning
soft Q-learning
spisndes
apisodes
Figure 5: Maze environment and learning curves.
A.5 EXPERIMENTAL DETAILS
A.5.1 MAZE
For the maze experiments in section 5.1, we use as depicted in Figure 5a. The agent needs to reach the goal zone in the bottom-right corner. At each time step, the agent can choose to west). If the move is blocked by a wall or the border of the maze, the agent stays in place. Every time step, the agent gets reward of -0.004 or 1 if it enters the goal zone and the episode ends. The discount factor is 0.99 throughout the experiments. For these experiments, we use tabular setting for Q-learning and soft Q-learning according section 2.1 and 4.1. For Q-learning, the behavior policy is e-greedy, where decays exponentially from 1 to 0.001 during training. And we set learning step size = For soft Q-learning. the temperature parameter / is set to 100. Total trial number is 50 for each algorithm. During training, both algorithms successfully solve the maze game, see Figure 5b-c for the learning curves.
environment of a 5 x 5 square with walls,
one square in any of the four directions (north, south, east,
A.5.2 CARTPOLE
For CartPole, the goal to keep the pole balanced by moving the cart forward and backward for 200 steps. We test our theoretical prediction on DQN and soft-DQN (DQN with soft-update). For DQN, we implement the model according to Mnih et al. (2015), where we replace the original Q- network with a two-layer MLP, with 256 Relu neurons for each layer. The in e-greedy policy decays exponentially from 1 to 0.01 for the first 10, 000 steps, and remains 0.01 afterwards. For soft-DQN, all settings are the same with DQN, except for two modifications: for policy evaluation, the (soft) Q-network is updated according to the soft TD error; the policy follows manximum-entrrppe policy, calculated the softmax of the soft Q values (sce section 4.1). The temperature parameter is set to 0.5. For both algorithms, the discount factor is 0.99, the learning rate is 0.005, experience buffer size is 1000, the batch size is 16 and total environment interaction is 50, 000.
A.5.3 ATARI GAMES
For this set of experiments, we compare the performance of vanilla soft DQN and soft DQN with PER, where we use surprise and the theoretical upper bound as priorities (Schaul et al., 2016), respectively denoted as PER and VER (valuable experience replay). We select 9 Atari games for the experiments: Alien, BattleZone, Boxing, BeamRider, DemonAttack, MsPacman, Qbert, Seaquest and SpaceInvaders. The vanilla soft DQN is similar that described in the above section, but the Q-network the same with Mnih et al. (2015). We implement PER on soft-DQN according to Schaul al. (2016). For all algorithms, the temperature parameter 3 0.05, the discount factor 0.99, the learning rate is le-4, experience buffer size is 1M, the batch size is 32, total environment interaction 50, 000. For PER or VER, the parameters for importance sampling are ais 0.4 and Bis 0.6. For each game, the network is trained on single GPU for 40M frames, or approximately 2 days.
15

---

Under review as a conference paper at ICLR 2021
Maze
0.2
0.4
0.6
0.00
0.25
0.50
0.75
0.0
0.5
1.0
Upper Bound
[TD]
rho_max
CartPole
Upper Bound
[TD]
rho
max rho_max
Figure 6: Illustration on the difference between VER and PER in soft Q-learning. VER uses the theo- retical upper bound as priority (p (TD* which balances the TD error and the "on-pot policyness" of the experience. Depicted are the theoretical upper bound (left), [TD] (middle), and the policy term (right) of 50 experiences from the replay buffer in the maze (upper panel) and CartPole (lower panel), ordered by the theoretical upper bound.
16


Reviews:
[{"review_id": "ybQrU_KUh9", "reviewer": "AnonReviewer4", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: the idea of prioritized experience replay is revisited, but from a new perspective with new theoretical results. Here, the authors propose the expected value of backup (EVB) as a metric to assess the quality of a sample and its potential improvement on the policy and on the value function. The authors decompose this metric into the benefit attributed to the policy and benefit to the value function. The authors have two theorems. The first theorem shows that the surprise (aka the temporal difference error) is an upper bound of the EVB in the Q-learning setting. The second theorem shows that the surprise, multiplied by a constant that depends on the policy, is an upper bound to EVB in the soft RL setting. The authors demonstrate that the proposed tighter bound on the EVB *could* yield improvements in the soft RL setting. \n\nPros of this work:\n- the work tries to tackle an important and still not fully answered question, which is why prioritized replay works well in the DQN setting but not in the soft RL settings, making very nice connections to the existing empirical literature on the topic, and a suggestion of how to improve PER\n- the paper is very clearly written and the motivation of addressing PER from a rigorous perspective is clear.\n- overall, a rigorous study of the \"quality\" of samples and experience seems like a very promising direction if the goal is to develop more intelligent agents that can make better use of the information available to them\n- the authors try to demonstrate why the approach leads to tighter bounds than standard PER with some visualization (although I point out some issues below)\n\nCons:\n- lack of motivation regarding the choice of EVB\n- more thorough experimentation\n- lack of evidence suggesting a tight upper bound (e.g. modest improvement in soft RL, maze example does not suggest a tight bound in Q-learning)\n\nDetails:\n- lack of motivation regarding the choice of EVB: while the EVB seems like an intuitive starting point for investigation, its motivation and a-priori connection to prioritized replay is not fully clear. one of the problems with EVB is that it seems to be a largely myopic measure of quality that is linked to only the current sample, e.g. (s,a,r,s'), while ignoring the effect of the sample on further backups in the rollout. Recent work on the topic [1] (PSER) suggest that a myopic approach can be significantly improved by up-weighting earlier transitions that lead to good transitions in the future. This would seem to suggest that a non-myopic metric could lead to more significant improvements than working with a myopic setting which could be fundamentally flawed. While I do agree that EVB is a good starting point for analysis, I am not convinced the results are fully conclusive, particularly given the need for stronger motivation on EVB and more conclusive experiments (see below) . I would encourage the authors to think about how to better motivate the use of EVB in the papers introduction more clearly if existing literature suggests so (I am somewhat aware of [2], although the authors there do highlight the shortcomings of EVB). Could sequential replay be the result of using an underlying metric that is less myopic than EVB, which seems to shows better promise over PER? If not, why is EVB truly the only right approach for analyzing PER?\n- more thorough experimentation: while I concur that the current paper addresses an important theoretical question, and while the result appears trivial to implement (not more difficult than PER), the bound should also be justified experimentally if it is to have significant value in practice. I think one key detail that is missing and could greatly benefit the paper is a more careful analysis and visualization of what the modified tighter bound is actually doing in the soft-Q setting. For example, how does the ranking of experience change when using the \"tighter\" bound? How often does this bound lead to a revision or re-evaluation of experience v.s. PER? Is there a fundamental reason why PER could not be as effective for soft RL in general that cannot be explained by better myopic estimates of the value of each transition? \n- lack of evidence suggesting a tight upper bound - Q: while the authors argue at several points in the paper that the |TD| could be a tight upper bound, this bound is only attained in some special cases. However, this does not really mean that the upper bound is tight for Q-learning, since there could be other upper bounds based on |TD| that incorporate additional value or policy information that could be tighter (same also applies for soft RL). The Figure 1 also seems to suggest that the values are scattered quite randomly and do not attain the upper bound as claimed for Q-learning. This does not suggest that |TD| is tight in any way. Can a gap be proved that effectively provides a lower bound on EVB? \n- lack of empirical evidence supporting the tighter bounds - soft RL: The experiments on Atari also suggest that the improvements of VER are quite mild, only improving on PER with statistical confidence on two of the experiments (interestingly, these two experiments also show mild improvement by PSER, whereas PSER shows considerable improvements on other games evaluated here).  This seems to be at odds with the claims that VER is a significant improvement of PER in soft RL. In the games where VER does not improve upon PER significantly, I would encourage the authors to comment on why the results are so similar to PER. I think the current benchmark problems are fairly sufficient and complex, and would not require more evaluation, unless the authors believe this would lead to a different conclusion or if the games selected are not representative of where VER can be beneficial. \n\nOther points:\n- while I agree with the authors that when the learning rate is held constant, |TD| is an \"upper bound\" to EVB in the Q-learning case. However, in practice we often use state-dependent learning rates that can be annealed over time with visitation counts, which can often yield improvements (as long as the usual stochastic convergence conditions are satisfied, of course). In this case, wouldn't the learning rate play a role in the bound?\n\nI think the work is very interesting and addresses a central issue, and I hope that the above comments can be useful to improve the paper. Overall, I think it is necessary to think more carefully about the connection between PER and quantifying the value of an experience (e.g. why EVB? how to reconcile moderate empirical evidence of the new bounds?). I am looking forward to the authors' response on these issues above.\n\nReferences:\n[1] Brittain, Marc, et al. \"Prioritized Sequence Experience Replay.\" arXiv preprint arXiv:1905.12726 (2019).\n[2] Mattar, Marcelo G., and Nathaniel D. Daw. \"Prioritized memory access explains planning and hippocampal replay.\" Nature neuroscience 21.11 (2018): 1609-1617.", "extra_scores": {}, "extra_text": {}}, {"review_id": "QxkRd5ozRRy", "reviewer": "AnonReviewer1", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper tries to interpret PER from the lens of replaying experience that has the most \"surprise\" and shows how it connects to some notions of value such as the expected value of the backup and policy improvement value and evaluation improvement value and argue. The authors also derive a max-ent version of this and show that this can improve performance on some Atari games (though this is not that convincing).\n\nMy score for this paper is based on these points:\n\n Motivation: I do not see the motivation for introducing these metrics and why that explains PER in the first place. Agreed that PER is a reasonable choice, and it can upper bound the EIB and EVB metrics (i have issues with this too, more on this next), it just seems to me that the paper doesn't make any convincing claim for why this helps us understand why PER works. If the focus of the paper is on understanding PER, then the paper does not do a good job of it. If it is to introduce these prioritization based on these metrics -- and the paper focuses entirely on them -- then I then have several concerns next.\n\n- Definition of the value metrics: The cited definition of these metrics requires using the true Q-function or the true value function of the resulting policy. If we end up approximating this using the learned model, what is the guarantee that these metrics are indeed useful? Also theorem 1 should be restated to say that they care about the \"empirical\" EIB and EVB, that is computed using the learned Q-function, else it doesn't make sense to me. Moreover, if the TD error is a bound (which I think isn't with neural networks as I discuss in the next point) on the empirical EVB, can't I just drastically overestimate Q-values and get a larger empirical EVB value to be super high and prioritize on those examples? Why is that good? Why won't that promote overestimation? \n\n- Why is the update on the Q-value assumed to be tabular if the experiments are with a deep network on Atari? In a non-tabular setting Theorem 1 does not hold so either that should be rederived for the case of DQN or the experiments should be adjusted to do it on tabular settings.   In any case, now it is not clear to me why the method works with DQN, since the update in this setting isn't equal to $Q(s, a) \\leftarrow Q(s, a) + \\alpha TD(s, a)$. In general, the solution isn't known with neural networks, so the upper bound story doesn't hold there. With the NTK (Jacot et al.) assumption, I can obtain a somewhat similar update but pre-conditioned with the kernel Gram matrix (see Achiam et al. Towards characterizing divergence in deep Q-learning). However, Theorem 1 doesn't hold anymore now. So, it is unclear why the method works.\n\n- Even if I were to look at the experiments only, the results are not that impressive. The method is generally close to PER, and maybe a little better, but no comparison is made on a more efficient method such as Rainbow, and there are only 9 Atari games, which is too little. So, that is not super convincing yet.\n\nI would suggest the authors make some of the changes above.", "extra_scores": {}, "extra_text": {}}, {"review_id": "LzGCgEsfVk", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work aimed to understand the prioritized experience replay, a widely used technique to improve learning efficiently for RL agents. The authors proposed three different value metrics to quantify the experience, and showed that they are upper bounded by the TD error (up to a constant). The extension to soft Q-learning was also presented. Finally, the authors showed in experiments that derived upper bounds hold in Maze and CartPole. They also demonstrated that a new variant based on the upper bound achieved better performance on a subset of Atari games.\n\nThe authors tried to achieve a deep understanding of the prioritized experience replay, which I believe to be an important task. However, after reading through the paper, I am afraid that the question why prioritized experience replay works so well in practice is not well addressed. The authors provided the three metrics, and provided their upper bounds. Unfortunately, they are not sufficient to help the understanding, as the upper bound derived is just the TD error used in the prioritized experience replay. I also do not see enough depth for these theoretical results, and the presentation could be improved as well. The experiments indeed showed some practical benefits, but descriptions are confusing sometimes. My detailed comments and questions are as follows.\n\n1. When defining EVB, PIV, EIV in Eq. (3)- Eq. (5), \"s_k\" is used. However, in the derivation of Theorem 3.1, why is \"s\" used? They should be the same if both are from \"e_k\".\n2. The introduction of function approximators in the last paragraph in Section 2 is confusing: How are they used in the following sections? Also, why does the assumption \"...as if the parameterized Q-function converges to its target value\" hold?\n3. For Theorem 3.1, it looks to me that a tighter upper bound according to the derivations should be \\alpha |TD|. Why did you omit \\alpha?\n4. In the derivation for Eq. (7), the authors claimed that \"the third line is because the increase in Q-function resulted from greedy\npolicy improvement will not exceeds the surprise (times the learning step-size)\". Could you elaborate more on why this is the case?\n5. For VER in Section 5.3, which upper bound does it use? I guess it may come from Theorem 4.1, but need more clarification. Also, what are the exact differences between VER and PER?", "extra_scores": {}, "extra_text": {}}, {"review_id": "DB3Atcpj9_", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: The authors of this paper make a connection between the TD-error from a single unit of experience and various metrics of improvement for agents trained with prioritized experience replay and Q-learning or soft Q-learning. They show that priorities based on TD-error are indeed sensible, and show that a small adjustment to TD-error-as-priority for soft Q-learning agents is both theoretically sound and can yield improved performance. \n\nThe set-up and motivation of the paper is relatively clear and well-explained. One reason I like the paper is that the process is quite straightforward: 1) Strive to better understand a commonly-used algorithm, 2) Derive theory with reasonably good intuition behind it, 3) show that it empirically holds true on simple environments, and 4) the better understood result also yields modest improvements on a test suite. \n\nThere are a few areas I would consider rewriting or rewording for added clarity.\n\nFor instance, the thesis of the paper relies on a sensible definition of \"value of experience\", and this isn't made concrete until later, though perhaps this is hard to do in the introduction. As a small nit, I think the extra use of the word surprise was at first a bit unclear, especially as it aliases TD-error (unless I missed something). \n\nI think an extra paragraph about why we should use surprise as the correct metric for prioritization would be helpful. Notably, that when we know it upper bounds the three metrics, we want to continue prioritizing sampling experiences when training our agent, because this will yield faster learning, since we will have larger improvements to our agent. \n\nHowever, this dovetails into an additional few questions that could be followed up here: Is there a correct temperature with which we sample experiences from our prioritized replay that is ideal? Should we not be sampling experiences, and simply sorting the experiences by priority and training our agent on experiences in descending order of priority? Why shouldn't we do this? How much worse is this than using uniform sampling? I understand that some of these questions are hard to answer with limited compute, but some mention of this would give the paper more depth.\n\nAdditionally, there are a number of small issues in the writing, notably towards the end. A careful read of the paper for proper grammar, making sure the right propositions are used and that there are no missing words in sentences would help the flow and readability of the paper greatly. \n\nWhile the overall result is a nice one, I believe the paper has somewhat limited scope. It doesn't fundamentally change how we should approach training our agents with a replay buffer. In fact, I suspect that TD-error was used by the original authors because they knew of a link like this, or had strong suspicions of it. I think what this paper should do is explore or at least pose a gamut of interesting follow-up questions about the role of replay and how best to use it. Is it possible that there is instead a lower bound we can derive; can we learn a sampling/prioritization scheme by gradient descent that somehow does better? Are there prioritizations completely disjoint from TD-error that we should consider using? In addition, while limited resources might make more empirical investigations challenging, it's also worth understanding how other commonly used algorithmic mechanisms in deep RL interact with prioritization, such as stepping environments in batches, or the preprocessing done to observations, or things like reward or advantage clipping. \n\nI think that if the paper showed more evidence of zooming out and thinking deeply about the core problem, this would be an excellent paper. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is certainly on the way to be a solid contribution: it's an interesting research question, and we need more understanding papers (rather than yet another algorithmic trick paper).

The reviewers thought the paper was not yet ready. The reviewers suggested: (1) more motivation of why the proposed metrics were of interest, (2) clearer discussion and evidence of how the analysis better articulates the performance of PER, (3) missing empirical details like methodology for setting hyper-parameters, why these 9 Atari games, undefined errorbars, unspecified number of runs, and (4) conclusions not supported by evidence in Atari: with missing experiment details, likely too few runs, and overlapping errorbars in most games few scientific conclusions can be drawn.

The work might be strengthen by developing the first part of the paper (and focussing on the reviewer's suggestions) and deemphasizing the novel algorithmic contribution part.
Decision: Reject