Reliability-Adjusted Prioritized Experience Replay
Authors: Leonard S. Pleiss
Tobias Sutter
Maximilian Schiffer
Venue: ICLR 2026 Poster (2026)
Keywords: Deep Reinforcement Learning
Temporal Difference Learning
Experience Replay
Primary area: reinforcement learning
TL;DR: We present Reliability-adjusted Prioritized Experience Replay, which boosts data efficiency over Prioritized Experience Replay by weighting samples with a novel TD-error reliability measure, achieving superior results on control tasks and Atari.

Abstract: Experience replay enables data-efficient learning from past experiences in online reinforcement learning agents. Traditionally, experiences were sampled uniformly from a replay buffer, regardless of differences in experience-specific learning potential. In an effort to sample more efficiently, researchers introduced Prioritized Experience Replay (PER). In this paper, we propose an extension to PER by introducing a novel measure of temporal difference error reliability. We theoretically show that the resulting transition selection algorithm, Reliability-adjusted Prioritized Experience Replay (ReaPER), enables more efficient learning than PER. We further present empirical results showing
that ReaPER outperforms both uniform experience replay and PER across a diverse set of traditional environments including several classic control environments and the Atari-10 benchmark, which approximates the median score across the Atari-57 benchmark within one percent of variance.

Published as a conference paper at ICLR 2026
RELIABILIT--DDUSTED PRIORITIZED EXPERIENCE REPLAY* *
Leonard S. Pleiss
Tobias Sutter University St. Gallen St. Gallen, 9000 tobias. . wwt.laasssuteeruuigg..co
Technical University Munich Munich, 80331 leonard. www..pppp.... plet wwsstmmmumm.mm de
Maximilian Schiffer
Technical University Munich
Munich, 80331 schiffere tum.
ABSTRACT
Experience replay enables data-efficient learning from past experiences in online reinforcement learning agents. Traditionally, experiences were sampled uniformly from replay buffer, regardless of differences in experience-specife learning po- tential. In an effort to sample more efficiently, researchers introduced Prioritized Experience Replay (PER) In this paper. we propose an extension to PER by intro- ducing a novel measure of temporal difference error reliability. We theoretically show that the resulting transition selection algorithm, [Reliability-ajjuseed Prior- itized Experience Replay (ReaPHR) enables more efficient learning than PER We further present empirical results showing that ReaPER outperforms both uni- form experience replay and PER across a diverse set of traditional environments including several classic control environments and the Atari-10 benchmark, which approximates the median score across the Atari-57 benchmark within one percent of variance.
INTRODUCTION
Reinforcement Learning (RL. agents improve by learning from past interactions with their envi- ronment. common strategy to stabilize learning and improve sample efficiency is to store these interactions called transitions in replay buffer and reuse them through experience replay to increase sample-efficienge When using experience replay, the agent obtains mini-batchi for training by sampling transitions from the replay buffer. bani-batches are traditionally obtained using random sampling. However, prioritization schemes can help to select more informative transitions, improv- ing convergence speed and, ultimately, agent performance significantly (Schaul et al.) (2015)). As such, the sampling scheme constitutes a performance-critical component for modern reinforcement learning agents leveraging experience replay (Hessel al. 2017).
Among proposed prioritized sampling schemes, PER remains the most widely used (see Appendix C
PER was introduced in Schaul al. (2015). It samples transitions in proportion their absolute
Temporal Difference Error (TDE), which measures the distance between predicted and target Q- values. Accordingly,..... PER]foloows (ecooddngyy|PEERRolllooooo the rationale that transitions with higher absolute TDES bear higher learning potential. While this rationale is intuitive, the TDF is biased proxy as both the predicted and the target Q-value are approximations. Hence, prioritizing transition selection based on absolute TDEs can misdirect learning, potentially leading degrading value estimates, if the target Q-value is itself inaccurate (Panahi et al.) 2024) Carrasco-Dava -aviss et al. 2025). Such inaccurate targets may dampen convergence in the worst deteriorate final policy performance.
To address the bias while retaining the efficient transition selection, we propose ReaPER an enhanced experience replay strategy that extends PER weighting the TDE with measure of target Q-value reliability. This design is motivated by the observation that, when the agent's 's estimation of future states is inaccurate, the corresponding target Q-values become unreliable. In such cases, the TDE

---

Published as a conference paper at ICLR 2026
ceases to be dependable indicator of transition's learning potential, leading to ineffective detrimental updates. By explicitly accounting for reliability, [ReaPER]pree preserves the advantages of PER over uniform experience replay while mitigating the negative impact of misleading priorities, resulting in consistent performance improvements.
Intuition The rationale behind our reliability estimate becomes particularly intuitive in game environments such as Go, Chess, or Tic Tac Toe. Consider player assessing the current board position: if they lack reliable understanding of how the game might unfold, their evaluation of the current state's s value is likely inaccurate. As shown in Figure D states closer to terminal outcomes (i.e., near the end of the game) involve fewer remaining moves, making easier for the agent to
Boand daice, imndep
Boand ancca imeddpttt
Board saiz lincuep
X
X
O
X
O
X
X
X
Figure 1: Subsequent states from Tic Tae Toe game from the perspective of the agent placing circles. Board state + 2 is terminal. States i and ++1 are losing under optimal play. For an inexperienced player, recognizing that + is a losing state generally easier than recognizing as such. However, once t + 1 is understood as losing, identifying as lost becomes more straightforward. In general, accurately assessing + 1 is prerequisite for reliably assessing t -sspccilll when learning the game without explicit knowledge of rules or win conditions. As long as the agent's assessment of t + is flawed, its evaluation t remains unreliable.
accurately estimate their values. Early-game states, in contrast, rely on longer and more uncertain rollouts. Thus, value estimates tend to be more reliable as one moves closer to the end of an episode. This observation implies a hierarchical dependency the learning of transitions within a trajectory, wherein the accurate estimation of earlier state-action values is conditioned on the agent's ability to infer and propagate information from later transitions. Consequently, we suggest that the reliability of target values and by extension, of TDES should factor into experience replay prioritization.
State of the Art Experience replay has been an active field of research for decades. After its first conceptualization by Lin (1992), various extensions, analyses and refinements have been proposed
(e.g., Andrychowicz et al. (2017) Zhang & Sutton (2017); Isele & Cosgun (2018); ; Rolnick et al.
(2018)
Rostami
(2019 Fedus et (2020); Lu et (023)).
Central to our work is an active stream of research exploring optimized selection of experiences from the replay buffer. The most notable contribution this stream so far was PER (Schaul et al.. 2013 Panahi et al.] [022].. In essence, PER proposes to use the absolute TDE as a sampling weight, which allows to select transitions with high learning potential more frequently compared to a uniform sampling strategy. Various papers built upon the idea of using transition information
transition selection criterion: Ramicic & Bonarini (2017) explored an entropy baased selection criterion. Gao
et al. (202)) 1) proposed using experience rewards for sample prioritization. Britttin al. (2019)
introduced Prioritized Sequence Experience Replay, which extends PER by propagating absolute TDEs backwards throughout the episode before using them sampling criterion. /Zha al. (2019)
On et al. (2021) proposed dynamic, learning-baa based transition selection mechanisms. Yet, the proposed approaches have not replaced PER remains the only prioritized sampling strategy
that is widely adopted by state-of-the-ard RL algorithms. For a comprehensive review of the relevant literature and a systematic breakdown this claim, we refer Appendix C
Contribution We propose ReaPER, a novel experience replay sampling scheme that improves upon PER by reducing the influence of unreliable TD targets, ultimately leading to more stable learning and better policy performance. Specifically, our contribution is threefold: first, we propose the concept of target Q-value and reliabbiiiy and introduce a reliability score based on the absolute TDEs in subsequent states of the same trajectory. Second, of the sitiabiiityadjustte absolute TDE as a transition selection criterion. Third, we leverage the theoretical insights and the novel reliability score to propose ReaPER sampling scheme facilitating
present formal results proving the effectiveness
2

---

Published as a conference paper at ICLR 2026
more effective experience replay. The proposed method is algorithm-agnostic and can be used within any off-policy RL algorithm.
To substantiate our theoretical findings, perform numerical experiments comparing RcaPER to PER across various traditional RD environments, namely CARTPOLE, ACROBOT, LUNARLANDER
and the ATARI-10 benchmark, which recovers 99. 2% of variance within the median score estimate of the full Atari-57 benchmark (Aitchison et al. 2022). We show that both prioritized sampling strategies outperform uniform experience replay, and further show that ReaPER consistently outperforms PER Specifically, in environments of lower complexity like CARTPOL
ACROBOT and LUNARLANDER, CeaaER]reaches the maximum score between 16.6% and 32.6% faster than PER In environments of higher complexity, exemplified by the ATARI- 10 benchmark, Benccmark,ReaPRRPppee achieves a 22.97 22.97% higher median peak performance. In partially observable variant of the ATARI-10 benchmark, the performance gap widens, with [ReaPER]achievingg achieving a 34.98% median improvement.
PROBLEM STATEMENT
We consider a standard Markov decision process (MDP) as usually studied in an RL SettinggSutton & Barto 1998). We characterize this MDP as tuple (S, A, P.r,y.)), P))
where is a finite state space, A is a finite action space, P: x A + ( is a stochastic kernel, r S x - R is a reward function, denoting the distribution of the initial state, S ~ p. At time step I, the system is in state S. = 8 E S. We denote by S, and A, the random variables representing the state and action time and by E S and E AA their respective realizations. If an agent takes action A a E A, it receives corresponding reward r(s, a), and the system transitions to the next state S P(-|s, a). We define the random reward at time t as R₂ = r(: A.). The agent selects actions based on policy + via A, = (S.).
(0, 1) is discount factor, and p A(S) denotes probability mass function
Let (-) = Prob(- S1 ~ p) denote the probability of an event when following a policy म, starting from an initial state S₁ p. and let 1571 denote the corresponding expectation operator. We consider problems with finite episodes, where n expresses the number of transitions within the episode. Let G2 denote the discounted return at time t, G. Ei=e T-RR; We define the Q-function (or action-value function) for policy ı as
1
(²(s.a)= = E | St s, A
i R4 St S,
(I)
The ultimate goal of RL. is to learn policy that maximizes the Q-function, leading to max, Q3 (s,a). The policy gradually improved by repeatedly interacting with the environ- ment and learning from previously experienced transitions. A transition C₁ is 5-tuple, C,
=
(Se, Re, S,+1,de), de), where de is a binary episode termination indicator, de 1r=n One popular
approach to learn Q" is via Watkins' Q-learning (Watkins 1989; Watkins & Dayan 1992. where Q-values are gradually updated via
(2) in which n E (0, 1] is the learning rate and 8, the TDE 8, Q Qugger (Si) Q(S; At) with Q Quarges (S. Ret1 + (1 de+1) 7 max, QS+++1 a). For brevity of notation, we refer to the absolute TDE as 6t =1,/].
Q(S, A.) + Q(S, + + n
In practical RI. deployments, when the Q-function is approximated with a neural network, this framework has been augmented with several influential extensions, including DDoble Deep Q Network (DDQN) target networks, and experience replay (see Appendix B). Experience replay is commonly employed to stabilize and accelerate learning. Transitions collected through agent- environment interaction are stored in finite buffer H = [C from which mini-batches X C H of fixed size | = are sampled to update the Q-function. The sampling distribution over the buffer, denoted by μ (HH), determines the likelihood μu( (C))) of selecting transition C₁ E 76 when constructing X', In uniform experience replay, μ is the uniform distribution, whereas in PER Schaul
3

---

Published as a conference paper at ICLR 2026
et al. 2015), transitions are sampled according to scalar priority values, derived from the absolute TDE
Empirical evidence suggests that the effectiveness of the learning process is sensitive to the choice of μ. i.c. sampling transitions with high learning potential can improve convergence speed and final performance. However, designing
optimal or near-optimal sampling distribution remains an open problem. With this work, we aim to contribute to closing this gap by defining and efficiently approximating a sampling distribution j² that maximizes learning progress using experience replay.
METHODOL.OGY
In the following, we provide the methodological foundation for ReaPER We first introduce reliability score for absolute TDEs, which we use to derive TDE based aeliablity-adfjutee transition sampling method. We then provide theoretical evidence for its efficacy.
3.1 RELIABILITY SCORE
In bootstrapped value estimation, as in Q-learning, the target value
Quager (S:) = Re+1 + (1-d(+1) max Q(S((1,
(3)
relies on the current estimate of future values. Consequently, the quality of an update to Q(S, As) depends not only on the magnitude of the absolute TDE ot. but also on the reliability of the target value Quargen(S)) (St).
We define the reliability of a target Q-value as a measure of how well it approximates the true future return from given state-action pair. Intuitively, target value is reliable if it decreases the distance between Q" (St,A) and Q(S,, At). Conversely, a target is unreliable if training on it increases the distance between Q" (St, As) and Q(S,,
To motivate this concept and formalize its operational consequences, we consider a single episode consisting of transitions (CI...., C,), from initial state S₁ to terminal state S,+1. We highlight three key observations that explain how reliability varies along the trajectory and how it can be used to improve sampling:
Observation 3.1 (Unreliable targets can degrade learning). (S) depends on the estimate
for t Q(S++1,)) (I...., 1}, which may be inaccurate. If an update is based on a poor target value, the resulting Q(S;, As) may diverge from Q" (St, At), thereby degrading the estimate.
Observation 3.2 (Terminal transitions induce reliable updates). For terminal transitions, the target Rm, This target is exact, implying that the
is given directly by the environment, i.e., Qtarger corresponding TDE accurately reflects the deviation from the ground truth Q-value, Thus, updates based terminal transitions are guaranteed to shift Q(S,, An) towards Q" (Sn,A,) if 5 O.
Observation 3.3 (Reliability propagates backward). An accurate update to QSS, At) improves the accuracy of Barger(S,-11 and earlier targets, which recursively depend on it. Therefore, updating transitions near the end of the episode helps improving the reliability of Qurget for earlier transitions.
These observations highlight a temporal hierarchy in transition learning: Learning later transitions before learning earlier transitions appears advantageous. On the one hand, later targets rely on fewer estimated quantities and are therefore more reliable. On the other hand, learning later transitions positively impacts the target reliability for earlier transitions. Furthermore, high TDE indicates misunderstanding of game dynamics for a given transition, thus rendering the value estimation in predecessor transitions which rely on the understanding of the value dynamics in the subsequent rollout - less reliable. We therefore aim to resolve TDEs back- to- fo-front. This motivates defining the reliability of Qrarga(()) (S.) inversely related to the sum of future absolute TDEs
R2 = Σ 8+
(4)
En1 85
Using this definition, we propose the reliability-udjuaa
TDE
V, .5.
(5)
4

---

Published as a conference paper at ICLR 2026
sampling criterion for selecting transitions during experience replay. High values of v corre- spond to transitions that promise large updates and have reliable target values. Sampling weights can be obtained by normalizing the sampling criterion with the sum of vp over all transitions.
3.2 FORMAL ANALYSIS
We consider a set of transitions that constitutes a single complete trajectory of length n, D = {Ci) where C, (St, A,, R,, Se+1 1. de).
Updates are based on the TDE by = ((,,, - Qaaree (S,), using the standard bootstrapped target Qurrer (St) R2 7(1 de) max Q(5++1,
(6)
Convergence A critical factor to ensure convergence in Q-learning is the alignment between the TDE and the true value estimation error (S,, A,) Q* A²). When the bootstrapped target biased, meaning Qunger((s) & (S,,,, the update direction may become misaligned, potentially worsening the value estimate.
We defer the formal misalignment analysis to Lemma and Lemma D.2 in Appendix D.1 In essence, the expected change in squared true value estimation error due to an update of the value function approximator under sampling strategy μ can be decomposed into three components, the TDE variance, the true squared error, and the bias-error interaction
[IQ(S, A.) (S, A.)
E
2n
2n) > Elere),
TBC
variance
True squared crvor
Blas-crroo-imeeration
where e denotes the true value error, and E, denotes the target bias,
e Q(s,, - (S,,,
= (s,) (S,,
(8)
By focusing on large TDEs PER aims to sample transitions with higher true squared error more frequently, thus resolving errors faster and improving efficiency over uniform sampling. In the following, we show that our ReaPER sampling scheme additionally controls the target bias, thereby minimizing the bias-error interaction, while also preserving the advantages of PER This allows ReaPER]to to increase -ampling-efficiency over PER. To do so, we base the following formal analyses on a key assumption relating target bias to absolute downstream TDEs
Assumption 3.4 (Target Bias via Downstream TDEs
Along an optimal trajectory, the target bias Et
for each transition C2 satisfies
leal <
Σ 5..
for some I 1, where 5,- = 16,). This assumption formalizes the intuition that bootstrapped targets primarily inherit bias from inaccuracies in future predictions. It reflects standard TD-learning dynamics under sufficient exploration and function approximation stability. While - similar to the assumptions made in standard convergence proofs [o] this assumption may theoretically be violated during the early phases of training, it tends to hold in practice, especially once value estimates stabilize, as we show in Appendix E In nutshell, Assumption 3.4 captures the intuition that target bias predominantly arises from unresolved downstream TDEs reflecting a local perspective on TD-learning dynamics. Unlike classical convergence proofs that require global exploration and decaying learning rates, our assumption focuses on bounding the bias along observed trajectories during finite-sample learning, making it more applicable to practical deep RL We refer the interested for a detailed discussion.
reader to Appendix D.2
Under Assumption 3.4 the reliability score R, reppresenting the fraction of downstream TDE within
given trajectory bounds the normalized target bias. This is captured in the following lemma.
Lemma 3.5 (Reliability Bounds Target Bias). Under Assumption 3.4
| & A(1 R₂) Σ 5t
(10)
5

---

Published as a conference paper at ICLR 2026
For the proof of Lemma 3.5
refer to Appendix D.3 Lemma 3.5
expresses that transitions with
higher reliability scores exhibit lower target bias and thus yield more trustworthy (DES This finding
motivates selecting training transitions not just by TDE magnitude, but by combination of TDE magnitude and reliability - as implemented in ReaPER
Building the established relationship between reliability and target bias, derive the following convergence hierarchy.
Proposition 3.6 (Convergence Hierarchy of Sampling Strategies). Under Assumption 3.4 and given fixed learning rate n, RReaPER (14 x RTō," yields lower expected Q-value ervor than standard (e 5,") ), which in turn outperforms uniform sampling,
PER
FIll (niffrr)) - Q*11²1= 2 RI (PER) Q- F(II ReaPER)
Q²113),
(11)
where E denotes the expectation across training runs.
The corresponding proof, detailed in Appendix D.4 formally compares the expected error decrease
terms under different sampling distributions, using Lemma 3.5 to bound the ttas-error-interae While we limit Proposition 3,6 optimal policies for brevity of notation, we can straightforwardly extend to suboptimal policies.
Remark 3.7 (Extension to suboptimal policies), the agent follows fixed but suboptimal policy, Assumption 3.4 can be relaxed to include an additive policy-induce bias term Ç 2 0, yielding
leal S
c.
(12)
i=++
In this case, ReaPER still improves sampling efficiency in expectation, although the achievable Q-value accuracy hower-bbunded by the policy suboptimality Ç. For further details, we refer the interested reader Appendix D.5
Together, these results provide the theoretical foundation for ReaPER|s design: By prioritizing transitions with high absolute TDE and high reliability, ReaPER selects relevant transitions while improving alignment with the true value error, leading to faster and more stable learning.
Variance reduction In the following, we show that the proposed sampling scheme,, based on reliability-adjusted TDES reduces the variance of the Q-function updates. As first step towards this result, we analyze the theoretically optimal distribution sample from in order to minimize the variance of the Q-function update step. Recall that Q- valuue are updated according to (2). where the TDE corresponding At)
transition C, from the finite replay buffer H reads d; Q uarger (St)
We assume fixed episode and treat the current Q-values as constants, focusing on analyzing the update variance induced by the sampling distribution μ over H. The update variance can then be expressed as
Σ pe Var
Σ pr Var(a (S.))
Σ moo
(13)
where the first equality follows from the definition the TDE and the assumption that the current Q-values are constant. The second equality simply defines of := Var var[QungerSA (S,)) as the variance of the bootstrapped target for brevity.
Proposition 3.8 (Variance reduction via reliability aware sampling). The distribution μ² minimizing the update variance (13) is given by
th x 8+ for all t (1,...,N)
(14)
of
For the proof of Proposition 3.8
refer to Appendix D.6
As direct consequence of Proposition 3.8 we find that our proposed ReaPER sampling scheme is variance reducing if the reliability R is proportional to the inverse variance of the bootstrapped target.

---

Published as a conference paper at ICLR 2026
As the true target Q" remains constant, significant proportion of variance across runs for given state can be attributed to the target bias. As such, there exists a direct relationship between e and of. Hence, under Assumption 3.4 seems natural to assume R x z Thus, ReaPER constitutes reasonable proxy for the optimal inverse-variance weighted sampling strategy.
To provide further intuition for formal results, have conducted supplementary simulation- driven analysis showing that that ReaPERR achieves optimal transition selection in a stylized setting, which we detail in Appendix
4 RELIABILITY-ADIUSTE PRIORITIZED EXPERIENCE REPLAY
We have thus far introduced the reliability adjjusted TDE and theoretically proven its effectiveness as a transition selection criterion. In the following, we propose ReaPER] the sampling algorithm built around the reliability-ae reliabilit-adjjusted TDE We give distilled overview of the resulting sampling scheme in [ At its core, we create mini-batches by sampling from the buffer with V as the sampling weight. Specifically, at each training step T (I,...,T) for every transition within the buffer, that is, C2 for all t E {1, f1,....NV .N....... selection eriterion ve (Algorithm Line 5f..). Based on v we sample transitions from the buffer H. to create the next mini-batch X (Allorithh 1 Line 9... ). For the full algorithm and an extended explanation, we refer to Appendix A
we update TDE reliabilities R, and compute the transition
Algorithm 1: Sampling transitions and updating the value function using ReaPER
absolute TDEs 8+ episode vector current episode batch size k. exponents o, w and replay buffer H of size N, policy weights 0, maximum priority Pmaz 1, budget T for 7 (I.....27 )) do
Input:
Initialize accumulated weight change A = 0 and empty batch X' (()) Add novel transitions to the buffer with maximum priority Pmaz and set dr = 4;
Compute maximum episodic sum of absolute TDEs F
max
EN o5 10)=))):
tE(L.....V)
for I E (I,..., N} do Compute TDE reliabilities in Formula Compute transition selection criterion V < R2
Updating transition weights
5,
Compute transition priorities
W.
for m E (l...., k} do 10
// Sampling transitions
Sample transition Cj from H add to batch x such that (C, X,,) Pt for all E N1.
Compute importance sampling weight wy + (N-p:) for all / E (1...., N): Update 55 and accumulate weight-change A + A 83 VoQ(S,,
12
13
Update weights f +- 8 + A: Update maximum priority Pmax max(pmar: max(p));
Starting from the naive implementation ReaPER we require four technical refinements to obtain functional and efficient sampling algorithm.
I. Priority updates. To consistently maintain an updated sampling weight V. we track the TDES and reliabilities of stored transitions throughout the training. As it is computationally intractable to re-calculate all TDES on every model update, we implement leaner update rule: As PER we assign transitions maximum priority when they added to the buffer. Moreover, assign the TDE of transition C, every time C. is used to update the Q-function. We assign the reliability of transition Ct every time C, is used to update the Q-function, if any other transition from the same episode is used to update the Q-function, as it leads to a change in the sum TDES and possibly the subsequent TDES
We update the priority V when TDE or reliability are updated.
II. Priority regularization. As the TDE of given transition may change by updating the model even and, in consequence, reliabilities not guaranteed to
without training this transition, TDES
7

---

Published as a conference paper at ICLR 2026
be up-to-date. Thus, similar to Schaul al. (0015) introduce regularization exponents (0, and w E (0, 1] to dampen the impact extremely high or low TDEs or reliabilities,
Rr 8,"
(15)
III. Reliabilities for ongoing episodes. As the sum of TDE throughout an episode is undefined as long the episode is not terminated, is the reliability. In these cases, the maximum sum of TDEs of any episode within the buffer to obtain a conservative reliability estimate.
For this, introduce é, vector of length N, where o, denotes the t-th position in 6, which contains a scalar counter of the trajectory during which transition C₁ was observed. As such, ø functions as a positional encoding of transitions within the buffer. Specifically, it is used to identify all transitions that belong to the same trajectory. This positional encoding allows us to calculate conservative reliability estimates for multi-episodic buffer.
We then define R₂ as
Eimey 6, Eis 6 R- S F
for transitions of terminated episodes
R₂
(16)
for transitions of ongoing episodes
where
F= max AE
Σ 8+ 1 =os
(17)
Importantly, this formulation of reliability focuses on within-episodic variance instead of inter- episodic comparability. It therefore deliberately does not account for differences in episode length, as this introduces bias in favor of shorter trajectories, which we found to be detrimental in practice.
VI) Weighted importance sampling. Finally, just every other non-uniform sampling method, ReaPER violates the i.i.d. assumption. Thus, it introduces bias into the learning process, which can be harmful when used in conjunction with state-of-the-ard RI algorithms. Similar (Schaul al. (005)), we use weighted importance sampling (Mahmood et al. (0144) to mitigate this bias. When using importance sampling, each transition C₁ is assigned weight we, such that
1
1
L
We
==
(18)
Pt
N
We use this weight to scale the loss and perform Q-learning updates using d, wy instead of &
5 NUMERICAL STUDY
We evaluated ReaPER against PER across diverse of continuous control and Atari environments. For continuous control, we considered the discrete action space environments from the Gymnasium library (Towers al.) 2024), namely CARTPOLE, ACROBOT and LUNARLANDER. For Atari, following prior work, we use ATARI- as computationally efficient yet representative benchmark which recovers 99.2% of median score variance within the Atari-57 benchmark, ensuring relevance to broader Atari-57 evaluations without incurring prohibitive computational overhead (Aitchison) cet al. 2022). Across conditions, we used the same DDQN agent, neural architecture, and model hyperparameters for all experiments. We controlled for all sources of randomness using fixed seeds and compared algorithms using identical seeds per trial. Thus, the only variation between conditions stemmed from the experience replay algorithm. Full experimental details and hyperparameters provided in Appendix G For a detailed introduction to additional deep Q-leaming- related concepts,
refer to Appendix B
8

---

Published as a conference paper at ICLR 2026
Continuous control For each continuous control environment, compared the performance between PER and ReaPER across 20 training runs. Training ended preemptively when a pre-defined score threshold was met (Towers al. 2024).
Across all three environments, ReaPER consistently reached performance thresholds in fewer steps than both uniform replay and PER In ACROBOT, this corresponded to improvements of 25.0% and 16.6%, respectively. For CARTPOLE, ReaPER reduced the steps needed by 41. 41.4% and 32.6%, and similar pattern held LUNARLANDER, with gains of 37.1% and 21.1%.
Required timesteps (x10)
Acrobot
CartPole
LunarLander
30
20
20
50
+
10
10-
ReaPER
PER
UNI
Figure 2: Proportion training steps required by PER uniform experience replay (UNI) and ReaPER to reach pre-defined score thresholds given in Towers al. (2024) across 20 runs in three traditional RL environmens The shaded region corresponds to the interquartile range (IQR), whiskers extend Q1 1.5 IQR and Q3 1.5 IQR, and the horizontal bar indicates the median score.
Mediun nonnelized performance
Amidar
1.00
ReaPER
BattleZone
Bowling
0.75
PER
DoubleDunk
UNI
Frostbite
KungFuMaster
Name TammGame
Phoenix
0.25
Qbert
RiverRaid
0.00
20
40
Performance increase by ReaPER over PER (%)
Timesteps
1c7
Figure Left: Peak score increase of ReaPER over PER Right: Median of the normalized cumulative maximum of scores across the Atari 10 benchmark for Real PER and uniform experience replay (UNT), following reporting standards from [Schaul et al. (2015). The normalized score timestep I is calculated by dividing the difference between the current score and the random score by the difference between the maximum score in this game across all sampling strategies and the random score.
Atari ReaPER consistently outperformed both uniform experience replay and PER on the ATARI- 10 benchmark. Specifically. ReaPER outperformed PER and uniform experience replay eight out of ten games. tying PER in two games. Across all games, ReaPER achieved 22.97% higher median peak score than PER and a 78% higher median peak score than uniform experience replay. Under partial observability, [ReaPER median outperformance grows to 34.98%. These results underline R robustness across heterogeneous game dynamics and its ability to scale to challenging, high- dige--iimesionnll domains. We provide per-game curves in Appendix H (Figure) and extended information on results under partial observability Appendix
Discussion ReaPER consistently outperforms|P PER indicating a substantial methodological advance. RcaPER did so with minimal hyperparameter tuning. We expect further gains through more extensive tuning of key hyperparameters, including regularization exponents a and w, importance sampling exponent and learning rate 17.
limitation ReaPER is its reliance on terminal states, which are a pre-requisite for calculating meaningful TDE reliabilities. Further, [eaPER tracks the episodic cumulative sums of TDEs to calculate the reliabiitty score, which causes computational overhead when TDEs updated. Using naive implementation, this overhead is non-negligible O(N). However, it be reduced to

---

Published as a conference paper at ICLR 2026
On t) by only re-calculating the episodic cumulative sums for transitions their update the update of a preceding transition within the same episode.
CONCLUSION
We introduced ReaPER a seiiabiitt--djjsster experience replay method that mitigates the detrimental effects of unreliable targets in off- aff-policy deep reinforcement learning. By formally linking target bias to downstream temporal difference errors, we proposed a principled reliability score that enables more efficient and stable sampling. Our theoretical analysis shows that [eaPPER] improves both convergence speed and variance reduction over standard PER and our empirical results confirm its effectiveness across diverse benchmarks.
Beyond its immediate practical gains, ReaPPRR highlights the importance of accounting for target reliability in experience replay, particularly deep RL settings where function approximation errors and generalization artifacts are prevalent. We believe our work opens new avenues for incorporating uncertainty and reliability estimates into replay buffers, and future research may explore adaptive reliability estimation, extensions to actor-critic methods and infinite-horioon settings, well as integration with representation learning.
REPRODUCIBILITY STATEMENT
We provide extensive details of experimental settings and hyperparameters reproduce our exper- imental results in Appendix G. Source code for all experiments is available in the supplementary materials, and will open sourced.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Abien Fred Agarap. Deep Learning using Rectified Linear Units (ReLU), 2018. URL https
7/arxiv.org wtw.voorr/bbs//// /000/1103..0 08375
Matthew Aitchison, Penny Sweetser, and Marcus Hutter. Atari-5: Distilling the Arcade Learning Environment down to Five Games, 2022. URL https::/:///xx /ttptp////aaxii.ooorraa////2221 02019
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, Pieter Abbeel, and Wojeiech Zaremba. Hindsight Experience Replay. 2017. doi: 10. 10.48550/ARXXIV.1070.011
Antonin Raffin, Quentin Gallouédec, Noah Dormann, Adam Gleave, Anssi, Alex Pasquali, Juan Rocamonde, M. Emnestus, Patrick Helm, Thomas Simonini, Quinn Sinclair. Corentin, Rohan Tangri, Sidney Tio, Tobias Rohrer, Tom Dörr, Wilson, Steven H. Wang, Sam Toyer. Roland Gavrilescu, Paul Maria Scheikl, Parth Kothari, Oleksii Kachaiev, Megan Klaiber, Marsel Khisamurdinov, Mark Towers, Jan-Hendrik Ewers, Grégoire Passault, Dominic Kerr, and Costa Huang. Stable- Baselines3 v2.4.0, November 2024. URL 14178439
5281 5281//enndo zenodo
Adrià Puigdomenech Badia, Bilal Piot, Steven Kapturowski, Pablo Sprechmann, Alex Vitvitskyi, Daniel Guo, and Charles Blundell. Agent57: Outperforming the Atari Human Benchmark, 2020a.
URL httptttss//axiv.oorrtt abcp//as//2/ /bo/ 13350]
Adrià Puigdomênech Badia, Pablo Sprechmann, Alex Vitvitskyi, Daniel Guo, Bilal Piot, Steven Kapturowski, Olivier Tieleman, Martín Arjovsky, Alexander Pritzel, Andew Bolt, and Charles Blundell. Never Give Up: Learning Directed Exploration Strategies, 2020b. URL https
Mare Brittain, Josh Bertram, Xuxi Yang, and Peng Wei. Prioritized Sequence Experience Replay, 2019. htt.sttsss///aaiiitttt
0tte///955.12222 12726
Rodrigo Carrasco-Davis, Sebastian Lee, Claudia Clopath, and Will Dabney. Uncertainty prioritized experience replay, 2025. URL http:/ttts///aatta org/ abs/ 2506. 09270
Pierluca DrOro, Max Schwarzer, Evgenii Nikishin, Pierre-Lue Bacon, Mare Bellemare, and Aaron Courville. Sample-Ffficient Reinforcement Learning by Breaking the Replay Ratio Barrier. 2023.
Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O. Stanley, and Jeff Clune. Go-Explore: New Approach for Hard-Exploration Problems, 2019. URL httppps://aaxii..o/ /bss/
1901. 10995
William Fedus, Prajit Ramachandran, Rishabh Agarwal, Yoshua Bengio, Hugo Larochelle, Mark Rowland, and Will Dabney. Revisiting Fundamentals of Experience Replay, 2020. URL |
//arxiv. wwwpivvoor/aae. wttp://raaabbbo...oees
Jiashan Gao, Xiaohui Li, Weihui I. Liu, and Jingchao Zhao. Prioritized Experience Replay Method Based Experience Reward. In 2021 International Conference Machine Learning and Intelligent Systems Engineering (MLISE), pp. 214-219, Chongqing, China, July 2021. IEEE. ISBN 9781665417355 doi: 10. 10.1109/M1SS5540066 leee feeee.org/bccumet//61111
URL http:httt//seeeppppppt
Danijar Hafner, Jurgis Pasukonis, Jimmy Ba, and Timothy Lillicrap. Mastering Diverse Domains through World Models, 2023. URL https: aaaaaaivvv.o... www.iv.rrgaaae.e ab2/g// 04110
Matthew Hausknecht and Peter Stone. Deep recurrent q-learning for partially observable mdps, 2017. org.
URL Ttttpp://arav..orr////////////// wtwpa/////1150.00
06527
Matteo Hessel, Joseph Modayil, Hado van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining Improvements in Deep Reinforcement Learning, 2017. URL URL
02298
Dan Horgan, John Quan, David Budden, Gabriel Barth-Maron. Matteo Hessel, Hado van Hasselt, and David Silver. Distributed Prioritized Experience Replay, 2018. URL https: : wttp/iivvv........ o abs/ 1803. 00933
11

---

Published as a conference paper at ICLR 2026
David Isele and Akansel Cosgun. Selective Experience Replay for Lifelong Learning. Proceedings of the AAAI Conference on Artificial Intelligence. 32(1), April 2018. ISSN 2374-3468, 2159- 5399. doi: 10.16099aami.v322111.. articcl/vvew//113
BRLLtttss://ot aaai org index. pww.k/.hhppa.....
Steven Kapturowski, Georg Ostrovski, John Quan, Remi Munos, and Will Dabney. Recurrent Experience Replay in Distributed Reinforcement Learning. 2019.
Diederik P. Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization, 2014. URL https://arxiv wwt./ogg///ooooooo
abs 1412. 6980
Long-Ji Lin. Self-improving reactive agents based on reinforcement learning, planning and teaching. Machine Learning, 8(3-4)293-331,, May 1992. ISSN 0885-6125, 1573-0565. doi: 10.1007/ BF00992699, URL
springer. com 10. 1007/
Cong Lu, Philip J. Ball, Yee Whye Teh, and Jack Parker-Holder. Synthetic Experience Replay, 2023.
URL htttthttt///iiii... 230p://abb233333333 06614
Rupam Mahmood, Hado P van Hasselt, and Richard Sutton. Off-policy learning based on weighted importance sampling with linear computational complexity. Advances Neural Infor- mation Processing Systems, pp. 3014-3022, 2014.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, loannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing Atari with Deep Reinforcement Learning, 2013. URL
https://arxix: wwt.:oogg//boooooo httppa///rrxi..orrr///////333
5602
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Mare 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 Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Na- ture, 518(7540):529 533, February 2015. ISSN 0036-0836, 1476-4687. doi: 10. 00.108//ature142366 URL https::p///// www nature..ecc.....mm.. com/ art www.sticcccceec nature 14236
Youngmin Oh, Kimin Lee, Jinwoo Shin, Eunho Yang, and Sung Ju Hwang. Learning to Sample with Local and Global Contexts in Experience Replay Buffer, April 2021. hRLhttp://arrx
hxq/abb/20077 07358 MrXiv:2007.07355 [cs, stat].
Parham Mohammad Panahi, Andrew Patterson, Martha White, and Adam White. Investigating the interplay of prioritized replay and generalization, 2024. URL https: http:::://axxxv.ooo////.//
09702
Antonin Raffin. RI baselines3 zoo. 2020.
Mirza Ramicic and Andrea Bonarini. Entropy-based prioritized sampling in Deep Q-learning. In 2017 2nd International Conference on Image, Vision and Computing (ICIVC), pp. 1068-1072. Chengdu, China, June 2017. IEEE. ISBN 9781509062386 doi: 10.1100111000 LOV/CIIVC.201...9477716 URL http::tttt:pppppeeeeee
David Rolnick, Arun Ahuja, Jonathan Schwarz, Timothy P. Lillicrap, and Greg Wayne. Experience Replay for Continual Learning, 2018.
Catastrophic Forgetting Using Experience Replay, 2019. URL haaprrggab////lll1 11682
Mohammad Rostami, Soheil Kolouri, and Praveen K. Pilly. Complementary Leamning for Overcoming
1903. 04566)
Sebastian Ruder. An overview gradient descent optimization algorithms, 2017. URL https
//axxiv.or wwwpi//org/abb/1660911
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized Experience Replay. 2015.
doi: 10.48550/ARXIV.15 .05522. URL /tatttps:///xivviie http://wwww...rr/aa//11/11101/
12

---

Published as a conference paper at ICLR 2026
Julian Schrittwieser, loannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel. Timothy Lillicrap, and David Silver. Mastering Atari, Go, Chess and Shogi by Planning with Learned Model. 2019. doi: 10.48550/ARXIV191) 1.08665. URL http::/ wwwvvvaxiivivv/////vv///i///iwvv wtwg/bb/////oaooog///gg////aaee/ .ww.11911211111
Max Schwarzer, Johan Obando-Ceron, Aaron Courville, Marc Bellemare, Rishabh Agarwal, and Pablo Samuel Castro. Bigger. Better, Faster: Human-level Atari with human-leve efficiency, 2023. URL hattps://arxiv.oom http:///xxxvv......... http:////abbb///...././/.
19452
R.S. Sutton and A.G. Barto. Reinforcement Learning: An Introduction. IEEE Transactions Neural Networks, ((5):105411055 September 1998. ISSN 1045-9227, 1941-0093, doi: 10. 109/TNN. 1998.712192. URL htttp:://eeeexppeee//
Leee wttp//ocmeet///22.1.....
Mark Towers, Ariel Kwiatkowski, Jordan Terry, John U. Balis, Gianluca De Cola, Tristan Deleu, Manuel Goulão, Andreas Kallinteris, Markus Krimmel, Arjun KG, Rodrigo Perez- Vicente, Andrea Pierré, Sander Schulhoff, Jun Jet Tai, Hannah Tan, and Omar G. Younis. Gymnasium: A Standard Interface for Reinforcement Learning Environments, 2024. URL wtw.tttpps./m /tt.tttt///aax...oogog/o
2407 17022
Hado van Hasselt, Arthur Guez, and David Silver. Deep Reinforcement Learning with Double Q-learning, 2015. URL http:::ttta..iiiiieeo. htw.g//abb/100000 06461
Shengjie Wang, Shaohuai Liu, Weirui Ye, Jiacheng You, and Yang Gao. EfficientZero V2: Mastering Discrete and Continuous Control with Limited Data, 2024. URL/ptps::/axx/wwor//////
2403. 00564
Christopher Watkins. Learning From Delayed Rewards. PhD thesis, Kings College, London, 1989.
Christopher J. Watkins and Peter Dayan. Q-learning. Machine Learning, 8(3-4):279-292 May 1992. ISSN 0885-6125, 1573-0565. doi: 10.1007/BB000992668. URL http://link
springer com 1007000..00000 1007/02088000 00992698
Weirui Ye, Shaohuai Liu. Thanard Kurutach, Picter Abbeel, and Yang Gao. Mastering Atari Games with Limited Data, 2021. http::::t:////ttttt http//awwwwv..rra///aaaaa//a///e
Daochen Zha, Kwei-Herng Lai, Kaixiong Zhou, and Xia Hu. Experience Replay Optimization. In Proceedings of the Twenty-Eightn International Joint Conference on Artificial Intelligence, pp. 4243 4249, Macao, China, August 2019. International Joint Conferences on Artificial Intelligence Organization. ISBN 9780999241141.
doi: 10.24963/ijcai 2019/589.
URI. https: www
hgtp.//////ccceeeg//////o//// 20199/99/9
Shangtong Zhang and Richard S. Sutton. A Deeper Look at Experience Replay, 2017. URL
https: //ar/vvavvvv////////i//eaa//aa.a org/ abs /tds/171.... 01275
13

---

Published as a conference paper at ICLR 2026
A ALGORITHM
Algorithm 2: Deep Q Learning with adiiabllity-djjusted proportional prioritization
Input: batch size k, learning rate 7), replay period K, replay buffer size N, exponents o, and
3. budget T.
Initialize replay memory H = A 0.
P1 = 1, episode vector & O(N) episodic count 4b = and maximum sum of episodic TDE F
1;
Observe S1 and choose A To (Si): for .I...., T} do
Initialize accumulated weight change A 0 and empty batch X' =(();; Observe Sc-1, Re, de: Store transition C. (Sor Acs Bh, des 1o+1) 1) in H with de 4 and p. maxx(p)) for all t E (l,...,N} N]; if mod K then
for m E {1.....A k} do Sample transition Cy from H. add batch X' such that PCCc Xmm) Pt for all E [1.
Compute iuportance-sampllee weight wy [N
max. for all t {I....,N::
Compute TDE وj - hargett (S,) Q(S)(Sjss Aj):
Accumulate weight-change + + wy oj VoQ(S,,
13
end
Update weights 0 0 n A: From time to time, copy weights into target network, Orrgat + 0;
15
(Em 8, Luu
16
Update maximum sum of absolute TDEs F'
max
Be ()
for / E {1,.... N do TDE reliabilities.
17
18
Compute
Emtti 2i
6t D
for transitions terminated episodes
R2-
for transitions of ongoing episodes
Update transition sampling criterion Vr 4 -R 8,";; Update transition priorities ps + Ei v,
19
W.
21
end end
22
if d, 1 then
24
for 1 E {1,....
N 0: = 6.) do
Eiseti En
Compute TDE reliabilities for the finished episode, R₁
end + 1b +1; 1;
27
28
end
29
Choose action A. no (S.);
end
In the following, we describe how ReaPPR operates in conjunction with Deep N-Network (DQN)
The agent begins by observing the mitial state and selecting an action (Algorithm 2 Line
For fixed number of iterations, the agent interacts with the environment, observes the resulting transition from its latest action, and stores this transition the replay buffer with maximum priority (Algorithm Line 5t..
Every K steps, the agent performs a training update (Algorithm Line samples batch X' from the buffer using the current priorities p as sampling weights (Algorithm 2 Line (f.).. The agent updates the model parameters using -orotancc-smmpliggg (Algorithm Line (4), and uses the observed TD-errors update the priorities p for all transitions
During training,
TD-errors
14

---

Published as a conference paper at ICLR 2026
in the batch (Algorithm Line I7... This involves recomputing the reliabilities based on the new TD-errors. applying a conservative estimate for transitions from ongoing episodes (Algorithm 2
Line 18). The agent then recalculates the sampling criterion & and updates the priorities p accordingly (Algorithm 2 Line 20), concluding the training step.
Upon episode termination, the agent replaces the preliminary reliability estimate with the actual reliability (Algorithm{2 [ Lin) Throughout training, it tracks episode progress to enable continuous
recomputation of reliabilities (Algorithm Line 27p.
At each iteration, the agent selects the next action based on its current policy and state (Algorithm Line 29h. initiating the next eycle.
B SUPPLEMENTARY BACKGROUND
Target networks. Target networks stabilize DQN by maintaining separate copy of the Q-network whose parameters are updated more slowly. This reduces harmful feedback loops between rapidly changing estimates and improves training stability. In practice, the larget network parameters are either periodically copied from the online network or updated via a soft update rule, where parameters slowly track the online network through Polyak averaging. These techniques help ensure that the bootstrap targets change smoothly over time, making optimization substantially more robust. For further information, see Mnih al. (2015).
DDQN
DDQN mitigates Q-value overestimation by decoupling action selection from value evalu- ation: the online network selects the action, while the target network evaluates This leads to more accurate value estimates and often improves policy quality. In addition to reducing positive bias, DDQN can yield more stable learning dynamics, particularly in environments with noisy rewards large action spaces, where overestimation errors tend to accumulate. For further details, see van Hasselt et al. (2015).
Optimizers. We use standard adaptive gradient methods. Adam (Kingma & Ba, 2014 maintains per-parameter first- and second-moment estimates to provide smooth, scaled updates. RMSProp adapts learning rates based on an exponentially weighted average of recent squared gradients, helping control step sizes in non-stationary settings. In practice, these methods reduce the sensitivity to hyperparameter choices such as the initial learning rate and improve convergence speed, especially in deep reinforcement learning where gradient magnitudes vary significantly across parameters and time. We refer to Ruder (2017) for comprehensive introduction.
C LITERATURE REVIEW
In the following, we substantiate our claim that PER constitutes the most practically relevant prior- itized sampling strategy within reinforcement learning this day. We first systematically review of-t--of-thearrtte [L [R[ algorithms and the sampling strategies they are employing. We further discuss possible reasons for the limited adoption of proposed alternatives.
C.I PRIORITIZED EXPERIENCE REPLAY THE STATE-OR-TIIE-AM
When we refer to PER as most practically relevant sampling strategy, we do not claim that DDQN with PER as proposed the original PER paper|Schaul /chhaul et al. (2015), represents the state-of-the-a in solving RL problems overall. Rather, we claim that this day, no transition selection algorithm within experience replay has demonstrated efficiency improvements comparable to those of PER without incurring significant computational overhead. This claim is supported by the fact that most state-of-the-un RL algorithms use PER, while other prioritization strategy are scarcely used within RL algorithms (Panahi al. 2024).
state-of-the-a
To support this notion, we have compiled Table 1 which lists leading algorithms on the Atari benchmark since the introduction PER and indicates whether they use experience replay and PER
The findings within Table [ indicate that all state-of-the-art RL algorithss that rely on experience replay also rely on PER The sole exception of this is Dreamer-v3 (Hafner et al. 2023), which relies
15

---

Published as a conference paper at ICLR 2026
Algorithm (Year)
Authors Year
Uses ER
Uses PER
Rainbow
Hessel et al. (2017
Yes
Yes
Ape-X DQN
Horgan et al. [0018
Yes
Yes
MuZero
Schrittwieser
(2019)
Yes
Yes, for the Atari benchmark
R2D2
Kapturowski et al.
2019
Yes
Yes
Go-Explore
Ecoltct al. (2019
No
No
NGU
Badia ct al.
2020b
Yes
Yes
Agent57
Badia et al.
(022aa)
Yes
Yes
EfficientZero
Ye et al. (2021)
Yes
Yes
Bigger, Better, Faster
Schwarzer et al.
20033
Yes
Yes
Dreamer-v3
Hafner al. (2023)
Yes
No, but PER boosts performance
SR-SPR
OrOro et al.
(0023
Yes
Yes
ElficientZZeo-v2
Wang al. (0244
Yes
Yes
Table 1: Overview of state-of-the-art reinforcement learning algorithms, highlighting whether they utilize Experience Replay (ER) and Prioritized Experience Replay (PER).
on uniform sampling for ease of implementation, but explicitly states PER boost performance. This provides evidence that PhER remains the de-facto standard prioritized sampling strategy, and therefore represents key point of reference for our study.
C.2 SYSTEMATIC REVIEW OF PROPOSED ALTERNATIVES
While discussed alternative prioritized sampling strategies to provide comprehensive overview of related work, these methods have seen limited adoption and are not integrated into state-of-the-art reinforcement learning algorithms. We lay potential reasons for the sparse adoption of the approaches mentioned in the paper, and thereby discuss why we do not consider them relevant baseline for the present paper.
While we have reviewed alternative prioritized sampling strategies to provide a comprehensive overview of related work, these methods have seen limited adoption and have not been widely integrated into state-of-the-ar reinforcement learning algorithms. We outline possible factors con- tributing to their limited uptake and explain why, in the context of this study, we do not consider them appropriate baselines.
Ramicic Bonarini (017)) proposed entropy-basee -aarop sampling. Their evaluation focused on single, non-standard environment and did not include comparison against PER To the best of our knowledge, the authors also did not release code, which may limit the ease of direct application.
Gao et al. (2027) proposed weward-based sampling and evaluated their approach in two environments, FETCHREACHI- and PENDULUM-VO, While these experiments provide useful insights, no evalua- tion was presented more complex domains such Atari games, making direct comparison with the original PER study less straightforward. From a theoretical perspective, an emphasis on rewards could potentially bias the algorithm toward greedier behavior, which might pose challenges in more complex settings. To the best of our knowledge, code was not made publicly available, which may limit immediate applicability.
Brittain el al. (2019) proposed refinement to PER by propagating priorities back through the sequence of transitions. Their evaluation compared the approach proportional variant of PER with different parameterization than the a .5, 8 .5 setting recommended the original paper, which may have influenced baseline performance. To the best of our knowledge, the work was released as a preprint in 2019 but has not appeared in a peer-reviewed venue, making it more difficult fully gauge the impact of the proposed method.
Zha et al. (209) introduced Experience Replay Optimization, dynamic prioritization approach, and evaluated on eight continuous control environments using DDPG. Their method was compared
Whiil the classic Dreamer-v3 algorithm does not use PER but uniform sampling, the authors explicitly report PER to improve performance. To directly quote Hafner al. (2023): "While prioritized replay (Schaul al. 2015) is used by some of the expert algorithms we compare to and we found it to also improve the nerformance of Dreamer, we opt for uniform replay in our experiments for ease of implementation."
16

---

Published as a conference paper at ICLR 2026
against PER and demonstrated improved performance, though not within the original experimental setting of the PER paper. Key hyperparameters such as a and 3 were not reported. and, to the best of knowledge, the authors did not release code, which may limit the reproducibility and practical applicability of their results.
Oh al. 2027) introduced the Neural Experience Replay Sampler (NERS), which frames sample selection as a reinforcement learning problem by training a separate agent. While this approach is conceptually appealing, it introduces notable computational overhead, which may affect its practicality, The evaluation was conducted on Atari games for 100,000 timesteps, rather than the conventional 50,000,000 providing insights into the early stages of learning. The authors report improvements over Weeiin in this regime; however, details on the [ER configuration are not provided, and, to the best of our knowledge, the implementation has not been released, which may limit reproducibility.
D DETAILED FORMAL ANALYSIS
We subsequently theoretically explore the properties of ReaPER This section extends the formal analysis in Section 3.2
D.1 CONVERGENCE BEHAVIOR
In the following, we provide formal motivation for for ReaPER by analyzing the influence of target bias on convergence behavior. We do so by showing that a misaligned target may degrade the value function, and then provide a decomposition of the expected error update.
Lemma D.1 (Update misalignment due to target bias). Let g: Vo(Q(S,, As) - Quarert (Sz))² denote the gradient of the loss and let g? Vo(Q(S,, - A,))² that aligns with the true value error. Then,
be the ideal gradient
(ge, g.) 2(Q(S., A.) Q",S,, A.)) - A.) A.)))e))))
(19)
Proof of Lemma D.I We compute the gradients explicitly. We define
Q(Sr, Aa) Q* At), := Qunger(())
(20)
We now may rewrite the TDE
8, = Q target (S:) - (()
-6e + Et.
(21)
Now, the gradients are
g: 2(Q(S A.) Q urge = 2(0)))002(-6)V0((33.
(22)
g: 2(Q(S,,
2e, VoQ(S, At).
(23)
Hence,
(g = 4(-8) V V 11 4(c, e, VoQ 1
(24)
Simplifying yields
(g. = - A))
(25)
which proves the result up to a constant factor of the norm.
This result shows that even when the TDE is large, its usefulness critically depends on the reliability of the target value. When E; is large, the update may not improve the value function estimation. When e, is sign-misaligned with the current true estimation error et, the update will even degrade the value function, pushing Q(Si, A.) further away from Q* (St, A.).
Based on these considerations, we proceed compare various sampling strategies by analyzing the expected change in the squared Q-value error caused by a single update step. The following lemma provides a decomposition of this change and builds the foundation of our main theoretical result.
17

---

Published as a conference paper at ICLR 2026
Lemma D.2 (Expected error update under sampling strategy μt). Lete, (Q(S), Q" At)).
Let Q denote the Q-function before an update, and let Q' denote the f-function after the up- date. Let E [ A.) (S,,, A.)]l=) EyllIQ"(S,, A,) (S, 2 [IQ(S, , A.)
(S, A.) I. Then,
A) -
= 2n Σ 1 (Q(S,, (o))),A)))
" 1g 2n Σ
Bl
(26)
Proof of Lemma D.2
We analyze the Q-value update
Q'(S, At) Q(S,, A.) + n1=-
(27)
After the update
A.) + nō: A) Q", = ct n7r,
(28)
the squared error becomes
+ n6,)² = e. + 2nero 17. (Q' A,) (S, A,) +
(29)
The expectation under sampling distribution μ is
E[Aer] = 1 + 2npL(erdd)
(30)
Note that 6, = Quarger (St) Q(S,, At) = Et Et, so
eqd; = et(E, - -ee) = EtEt - E,,
(31)
hence
E|Ae;] E
E + 2n [eee)
(32)
(2)
(3)
Summing over all transitions with gives the result.
This decomposition highlights three components: (1) the variance of TDE (2) the true squared error and (3) the bias-enrorinteraction. The latter is key to explaining why ReaPER outperforms other sampling strategies.
A key factor in the reliability of bootstrapped targets is the extent of downstream TDES Intuitively, if future states still exhibit significant TDEs, the bootstrapped target for the current state is more likely to be biased. This motivates the following technical assumption.
D.2 DISCUSSION OF ASSUMPTION 3.4
Assumption 3.4 esttablisss a relationship between the target bias for given transition and the sum of TDES for downstream transitions. This aligns with conventional perspective in TD-learning analysis, wherein bootstrapped targets predominantly inherit bias from inaccuracies in future value estimates.
Although Assumption 3.4 appears rather limiting at first sight, it is in fact less strict than assumptions made in classical Q-learning analyses: classical Q-learning convergence proofs (see, e.g., Watkins Dayan, 1992) rely on global exploration assumptions, ensuring that every state-action pair is visited infinitely often, and on decaying learning rates to control noise. In contrast, Assumption 3.4 takes more local view, postulating that the target bias along observed trajectory can be bounded by unresolved downstream TDEs While classical assumptions ensure eventual global accuracy, our assumption focuses bounding the bias during finite-sample learning along actual agent trajectories. which is more aligned with practical deep |eep|[L||stttingg settings.
Under Assumption 3.4 the reliability score R, which measures the proportion of downstream TDE along a trajectory provides an upper bound on the normalized target bias E,. Lemma 3.5 formalizes this relationship.
18

---

Published as a conference paper at ICLR 2026
D.3 PROOF OF LEMMA 3.5
Proof. From the definition of R2, we have
-i 07
1 - Rr =
(33)
Σ ii=1 8,
Multiplying both sides by En 0, we obtain
Σ
57 = (1-1RRR R₂)
Σ 0
(34)
=
1=1
Substituting this into Assumption 3.4
we find
E
X
8 X(1 - -R,)
Σ 8
(35)
which proves the first inequality. Rearranging the result gives
R₂ S 1
(36)
A
1i=1
completing the proof.
Moreover, it follows that
lEc o7
R2 $ 1
(37)
Lemma 3.5 provides formal link between the reliability score R, used in ReaPER and the target bias εx. Under Assumption 3.4 transitions with large downstream TDEs (i.e., large > 6,-) likely suffer from higher target bias. This justifies using R, to dewg-weiiht transitions with unreliable TDEs in the sampling distribution as long as downstream transitions suffer from high TDE, Consequently, ReaPER not only emphasizes transitions with high learning potential (large o, ) but also prioritizes those with more reliable target estimates.
D.4 PROOF OF PROPOSITION 3.6
Proof. From Lemma D.2 the expected change in squared error per update, conditioned on the current Q-function, is
AE
77
2n
E[e] + 2n
Σ [[ee)]
(38)
1=1
We seek to maximize the second term (true error reduction) while minimizing the third term (bias- error-interaction). The analysis proceeds by comparing the terms under the different sampling strategies.
We now compare three sampling strategics:
Uniform sampling (μe 1/n):: No prioritization occurs. Transitions with small ei and potentially large e are sampled proportionally to their frequency of occurrence in the buffer. Hence, both the error reduction term Σ, [E{]] and the bias term Σ, [4[[(c,er] are solely determined by the buffer content, and sampling does not reduce error or bias.
PER sampling (μ (55 )): PER prioritizes transitions with large TDE 5 which correlates with larger e?. As such, the sampling increases error reduction over buffer content,
PER H
Ele
Uniform B(e)),
(39)
19

---

Published as a conference paper at ICLR 2026
leading to faster true emror reduction compared uniform sampling. However, PER does not account for target bias Et. Nevertheless, since PER focuses updates on transitions with large (DDs (rather than arbitrary ones), it slightly reduces the paas-errorinntraacin compared uniform:
PER Eleee 44
Uniform E(e())).
(40)
ReaPER sampling (1t & R,o,"), ): Prioritizes transitions with large TDE and high reliability Rg, thus additionally considering target bias (see Lemma D.3). Thus, ReaPER achieves
PER Pi
PER Ele
Uniform E[e]].
(41)
for the true error term, and
ReaPER Ele
PER PER Mi
E
#
Uniform E[e
(42)
for the bias term
Therefore, ReaPER leads to the steepest expected decrease in squared error per update, followed by PER, followed by uniform sampling. Summing the per-step improvements over training steps, we conclude
Uniterm [l[Qr - Q2111 2 een
PRR [| - Q- 12 E ReaPRR |||Qr - 10 [1?)
(43)
as claimed.
L
D.5 DISCUSSION OF REMARK 3.7
While Assumption 3.4 is stated under the premise that the agent follows optimal policy, it can be extended to fixed but suboptimal policies. We now briefly outline the modifications necessary if the agent follows fixed but suboptimal policy. In this case, the target bias & cannot be bounded solely by unresolved downstream TDES, as suboptimal actions introduce an additional, vrajectoyy-independee bias. Formally, suppose there exists constant Ç 2 O such that for all transitions along observed trajectories,
(S, A.) (S,, S,
(44)
where Q" denotes the action-value function under the fixed policy Then, under analogous reasoning Assumption 3.4 the target bias satisfies
0 +
(45)
i=++1
This adjusted bound propagates through the subsequent results. In particular, Lemma D.3 becomes
leal $ A(1 R₂) Σ 5 + 1=1
(46)
and the reliability bound adjusts accordingly. In the error decomposition of Lemma D.2 and the convergence hierarchy in Proposition D.4] the additive term ( introduces a bias floor that does not vanish through learning. Consequently, while ReaPER still achieves improved sampling efficiency by reducing the impact of target misalignment, the achievable Q-function accuracy is ultimately lower-bounded by Ç. In the limit > 0 (the policy approaches optimality), recover the original theory.
D.6 PROOF OF PROPOSITION 3.8
Proof. First, we note that can assume without loss of generality that there is 7 0 such that the distribution 4² satisfies
N
Σ
ZT.
(47)
20

---

Published as a conference paper at ICLR 2026
If such r does not exist, that implies Σx= 176 which only holds if 0 for all I.....N
- a setting in which any sampling distribution from the buffer is optimal. Hence, equipped with (47). the optimal sampling distribution μ² is characterized as solution to the following optimization problem
min EEAN
(48)
subject to
Σ
1 2
(49)
We introduce Lagrange multipliers 2 for the inequality constraint and v for the probability normalization constraint. Then, the Lagrangian reads
Σ mig + + (
r
Σ
150
+
1
Mii
(50)
The KKT conditions for optimality are:
OC
(Stationarity)
03 Ao, -v= for all
1, I,...,N N
(51)
0t4
(Primal feasibility)
2 1 2 T, Σ U4 = 1,
14 m:20 0
(52)
(Dual feasibility)
X
(53)
N
(Complementary slackness)
A
T
=0
(54)
In the following we distinguish two cases.
Case 1:
Suppose Ein u > T. Then, complementary slackness implies À = 0. The stationarity of = for all i I,....N,
condition becomes
of v
(55)
which is only possible all of are equal. In general, this is not the case, so the constraint must be active at optimality.
Case 2:
Then Σ Di=1 o and complementary slackness implies À >>> 0. From the stationarity
condition, we obtain
of Ao - 0 of = +
(56)
Solving for X, we get
of V
(57)
8,
This must hold for all 1,..., N, so the right-hand side must be constant across i, which implies
constant
(58)
To justify the implication (a), note that the stationarity condition directly states of Ao 5 -ー-p Therefore, a higher value 5. implies a higher gradient contribution exactly where μi
should be large.
E EMPIRICAL VALIDATION OF ASSUMPTION 3.4
To empirically support Assumption 3.4 we conducted a simulation leveraging a BLINDCLIFFWALK experiment. The BLINDDLIIFFAAL environment stylized RL setting introduced in the original
21

---

Published as a conference paper at ICLR 2026
Reward
Bound violations (%)
Lambda
steps
0.5
0.00
-0.05
0.05
6 steps
0.00
-0.05
0.05
8 Stepp
0.00
00.5
0.05
10 steps
0.00
-0.05
2000
4000
2000
4000
2000
4000
Episode
Episode
Episode
DON
TQL
Figure Rewards, bound violations and À 4-, 6-, 8-, and 10-step BLINDLLIFWALLK environment DQN averaged across 100 runs and smoothened across 50 consecutive data points.
for TQL and
PER paper (Schaul al. 2015), which adopt to enable comparability with prior work. In this environment, an agent has to make n consecutive correct binary decisions to obtain reward of 1. If the incorrect action in given state is selected, the agent is reset the initial state, incurring reward of O. In this controlled environment, the true Q-values can be computed exactly, enabling direct empirical evaluation of our theoretical bound. We evaluated both Tabular Q-learning (TQL) setup and a simple DON with a single 16-neuron hidden layer. Each algorithm was evaluated along four different cliffwalk lengths (4, 6, 10) for 100 iterations, with 5,000 episodes of training time.
We report average rewards as an indicator of convergence. We further report observed bound violations, defined
|eal
8t.
(59)
Additionally, report the empirically observed X, defined
1ex
A
(60)
Ei=141 8
As shown in Figure 4 our results indicate that the bound established in Assumption 3.4 is never violated, neither in the TQL nor in the DQN setting. Moreover, observe that À decreases the model converges. This trend is especially pronounced in the tabular setting, yet also apparent the DONIsetinng setting, and provides empirical support for theoretical claim that the bound tightens the agent's policy improves. Taken together, these findings suggest that the bound is reliable, even under complex non-tabular function-aprroximation dynamics.
DQN
F CONVERGENCE IN A STYLIZED SETTING
We consider single episode within stylized setting. The agent is following the optimal path, Q turgee (St) Q(S+1, A.41) where A x² (S(+1) for all E (1,..., 1]. At the end of this
22

---

Published as a conference paper at ICLR 2026
Parameter Learning rate
TQL.
DQN
0.5
0.01
Gamma
0.99
0.99
Exploration
Random tie break
e
until first reward, then 0
Buffer size Batch size
1000
10
Table 2: Hyperparameters for the TQL and DQN conditions for empirical testing of Assumption 3.4 in the BLINDDLIIFFWAIL environment.
episode, the agent obtains final reward R, = 1. There are no intermediary rewards. The agent aims learn the correct Q-values for all transitions within this trial using a [TQL]appraaee (Watkins & Dayan 1992). (St) are continuously updated to be J.$441,A441.. with (Suger(S,), (S,) being We consider transition C, to be learned if the Q-value reaches its (for real applications mostly unknown) ground-truth Q-value, Q(S, A.) (S,, A.). We consider the model to have converged when all Q-values reach their ground-trute Q Q-value, Q(S, At) = (S, Ar) for t E {1..... n.. This is the case when all TDEs within this trial have a value of O, i.c., 5, 0 for t n).
The agent learns by repeatedly selecting & transition indices. For every selected transition Cy. the Bellman equation is solved to update the Q-value, Q,
QSS Aj) + 7 8j. For the sake of simplicity, we assume a discount factor y = 1, a batch size k = 1, and a learning rate 1j = As ? 1, learning transition Cj implies setting the Q-value to Quarget. i.e., Q(Sj. A,) murger (S,) We repeat this iterative process of sampling and the respective Q-value adaptation until the model converged.
We use three different selection strategies to identify the transition index j. which determines the transition Cj that the model trains on next, uniform sampling. Greedy Prioritized Experience Replay Prioritized Experience Replay (ReaPER-g) Uniform
(PER-g) and Greedy Reliability-adjuset sampling selects transitions at random with equal probability, sellcts the transition with the highest 1 ReaPERRg selects the transition with the highest reliability- adjuuseed TDE V. in both PER and ReaPER-g there no unique maximum, ties are resolved by random choice.
We compare these selection strategies to the optimal solution, the Oracle. The Oracle selects the transition C₁ with the highest index that has a absolute [DD]greatee greater than zero, max(t 6, * 0) for f. E (1...., n). Given
1, using the Oracle, the agent will always converge within Ex=1 16. S n steps and is therefore optimal. We compare the sampling strategies under varying levels of Qurrett reliability. Qurget reliability here is determined by the extent of target Q-values for unlearned transitions without immediate reward varying from zero: Reliability is high if Qurget values remains close to the immediate observed reward unless specifically learned otherwise. Quaget reliability decreases with more Qurzet values deviating from zero without observation of an immediate reward and without being explicitly learned. In reality, this may happen either through Q-value initialization or more importantly, when using Q-functions erroncous Q-value generalization across state-action pairs.
In the present example, we simulate different levels of Quaget reliability using different Q-value initializations. Specifically, we consider three Quareet reliability conditions: High, medium and low Quages reliability. In all conditions, all QSS, Ad) for t {1.....n} n2} are first initialized to zero. Then, depending on the reliability condition, some of these initializations are overwritten with ones to induce unreliability. In the low reliability condition, every second Q-value is overwritten. In the medium reliability condition, every fourth Q-value is overwritten. the high reliability condition, no value is overwritten.
We employ every selection mechanism to train until convergence for episodes of length 10 to 100 across all reliability conditions. As shown in Figure 2, uniform sampling converges the slowest across all reliability conditions. PER-g finds the optimal transition selection order when target reliability is high. However, pER-g|s convergence speed quickly diminishes Quatue reliability decreases. ReaPER-g on the other hand actively accounts for changes in Quafue reliability. By doing so, consistently finds the ideal solution regardless of Q Quatue reliability.
23

---

Published as a conference paper at ICLR 2026
# min. required updates
High target reliability
Medium target reliability
Low target reliability
# required updates
5000
5000
25
50
75
25
50
75
25
50
75
Episode length
Episode length
Episode length
Uniform
PER-g
ReaPER-g
Figure 5: Performance comparison in a stylized setting for three sampling methods; uniform sampling. PER-g and ReaPER-g Performance is quantified as the number of updates until convergence minus the minimally required number of updates given by an Oracle, Each sampling method is evaluated using different episode lengths (between 10 and 100) and different levels of Quaget reliability (high, medium and low).
G EXPERIMENTAL SETTINGS
All training parameters for all environments were set to according to pre-existing recommendations
from previous research (Mnih al. 2015 Schaul al. 2015 van Hasselt al. 2015 Raflin 2020).
The full experimental settings are subsequently described in detail to enable Tull reproducibility.
Experience replay parameters Following the suggestion for proportional PER for DDQN in Schaul et al. (2015), a was set to 0.6 for PER As we expect increased need for regularization due to the reliability-driven priority scale-down, we expected values smaller values for a and w in Rea performed minimal hyperparameter tuning find a suitable configuration. We did so by training single game, QBERT, on three configurations for and (1)
0.2, w 0.4, (2) w = 0.3 and (3) a = 0.4, w 0.2. For the runs presented the paper, the best-performing variant (a 0.4, 0.2) was used. For both PER and ReaPER linearly increased with training time, < (0.4 4 + L.0) as proposed in Schaul ct al. 2015). buffer size of 10th was used.
0.3,
Atari preprocessing As in Mnih et al. (2015), Atari frames were slightly modified before being processed by the network. Preprocessing was performed using StableBaselines3's Atari AtariWrapper (Antonin Raffin et af.] 2024). All image inputs were rescaled to an 84x84 grayscale image. After resetting the environment, episodes were started with randomized number of NoOp-frames (up to 30) without any operation by the agent, effectively randomizing the initial state and consequently preventing the agent from learning single optimal path through the game. Four consecutive frames were stacked to single observation to provide insight into the direction of movement. Additionally. termination signal is sent when life lost. All these preprocessing steps can be considered standard practice for ATARI games (e.g., Mnih et al. 2013 2015): Schaul et al. (2015)).
Training specifications Hyperparameters for learning to play CARTPOLE, ACROBOT and LU- NARLANDER were set to RL Baselines3 Zoo recommendations (Raffin 2020). Hyperparameters for learning to play Atari games set based previous research by Schaul al. 20155 Mnih et al.) (2015)
Mnih
and van Hasselt et al. (0155).
Network architecture For CARTPOLE, ACROBOT and LUNARLANDER, the network architecture equivalent to StableBaselines? default architecture (Antonin Raffin et al. 2024): A two-layered fully-connected net with 64 nodes per layer was used. For image observations as in the ATARI- 10 <benchmark, the input was preprocessed to size 84 x 84 4. It then passed through three convolutional layers and two subsequent fully connected layers. The network architecture was equal the network architecture used in Mnih al. (2015). Rectified Linear Units (Agarap) 2018 were used as the activation function.
II the uniform experience replay condition, the learning rate was increased to 2.5e-4, as recommended in seminal work MMih al. 2015 Schaul al. 2015 van Hasselt 2015).
24

---

Published as a conference paper at ICLR 2026
Parameter
CARTPOLE
ACROBOT
LUNARLANDER
ATARI
Learning rate
2.3e-3
6.3e-4
6.3e-4
625e-5²
Budget in timesteps
5e4
le5
le5
5e7 (2e8 frames)
Buffer size
le5
5e4
5e4
le6
Timestep to start learning
le3
1e3
le3
5e4
Target network update interval
10
250
250
3e4
Batch size
64
128
128
32
Steps per model update
256
Number of gradient steps
128
4
1 0.02
Exploration fraction
0.16
0.12
0.12
Initial exploration rate
1
Final exploration rate
0.04
0.1
0.1
0.01
Evaluation exploration fraction
0.001
0.001
0.001
0.001
Number of evaluations
100
100
100
200
Trajectories per evaluation
1
Gamma
0.99
0.99
0.99
0.99
Max. gradient norm
10
10
00
Reward threshold Optimizer
475
-100
200
Adam
Adam
Adam
RMSprop
Table Comprehensive documentation hyperparameteers used within the CARTPOLE, ACROBOT, LUNARLANDER and ATARI environments.
Evaluation For the environments CARTPOLE, ACROBOT and LUNARLANDER, 100 evaluations were evenly spaced throughout the training procedure. Each agent evaluation consisted of five full trajectories in the environment, going from initial to terminal state. The evaluation score of single agent evaluation is the average total score across those five evaluation trajectories. Training was stopped when the agent reached predefined reward threshold defined in the Gymnasium package (Towers al,, (224)). For ATART environments, as in Schaul et al. (205)) 200 evaluations consisting of single trajectory were evenly spaced throughout the training procedure. No reward threshold was set.
Score normalization: For ATARI games, scores were normalized to allow for comparability between games. Let Eraw denote single evaluation score that is to be normalized. Let Erandom denote the score achieved by randomly initialized policy in this game. Let Emaz denote the highest score achieved in this game across either condition, ReaPER or PER The normalized score Enorm is then calculated via
Eraw
Brendom
Eorm
(61)
high Grandom
Percentage improvement:
For the environments CARTPOLE, ACROBOT and LUNARLANDER, compute percentage improve- ments in median sinestepstto-conveggene T until meeting a specified reward threshold ReaPFR
upon another condition C, as stated within Section 5
Te TReaPER
Improvement over
x 100.
(62)
Tc
For the ATARI environments, compute percentage improvements in peak score P of ReaPER upon another condition C. as stated within Section 5
as
Per-game improvement over C PREAPER Pe
100.
(63)
Pc
The overall improvement across the ATARI-10 benchmark is computed as the median of the improve- ments observed on each individual game.
25

---

Published as a conference paper at ICLR 2026
H ATARI-10 RESULTS
Figure displays the median normalized scores across games gathered throughout 200 evaluation periods, which were evenly spaced-out throughout the 50 million training timesteps.
Median normallaan Irad perfommnns
0.6
ReaPER
PER
0.4
0.2
0.0
Figure 6: Median of normalized scores across the ATARI-10 benchmark for ReaPER PER and uniform experience replay (UNT) with moving average smoothed over 10 points.
Figure displays the cumulative maximum scores per game gathered across 200 evaluation periods.
Amidar
BattleZone
Bowling
DoubleDunk
Frostbite
1000
50000
50
5000
10
0
K KungFunt FuMaster
Name Game
Phoenix
Qbert
RiverRaid
50000
15000
20000
10000
25000
20000
5000
10000
ReaPER
PER
UNI
Figure Cumulative maximum evaluation score per game from the ATARI-10 10 benchmark across the training period for ReaPER PER and uniform experience replay (UNI).
I PARTIAL OBSERVABILITY
In Atari environments, single-frame observation does not convey object velocities or movement directions, making the vanilla problem setting a partially observable MDP (Hausknecht & Stone 2017). Standard practice mitigates this by stacking four consecutive frames as agent's observation to the learning process (Mnih et al. 2015). To perform a deliberate study of performance under partial observability, we intentionally restrict the agent to single-frand observation.
Under this constraint, ReaPER outperforms PER in 8 of 10 games, achieving median relative improvement of 34.97%, substantially exceeding the 22.97% gain observed the fully observable setting. This result indicates that the benefits of reliability adjustment are further amplified under partial observability. Aggregated results are shown Figure Per-game curves are shown in Figure
26

---

Published as a conference paper at ICLR 2026
Medien of normalized perfor performances
1.0
PER
Bowling
DoublaDunk
0.6
Frostbite
KungFuMaster
0.4
NemeenisGame
Phoenix
0.2
Obert
RiverRaid
0.0
ReaPER outperformance
Timesteps
le7
Figure 8: Left: Peak score increase of ReaPER over PER under partial observability, induced by single-frame observations. Right: Median of the normalized cumulative maximum of scores across the Atari-10 benchmark for ReaPPe and PER under partial observability. The normalized score timestep t is calculated by dividing the difference between the current score and the random score by the difference between maximum score this game across all sampling strategies and the random score.
Amidar
BattleZone
Bowling
DoubleDunk
Frostbite
400
20000
75
200
10000
-10
500
25
KungFuMaster
NameThisGame
Phoenix
Qbert
RiverRaid
10000
20000
10000
Figure 9: Cumulative maximum evaluation score per game from the ATARI- 10 benchmark across the under partial observability, induced by single-framm observations.
training period for
J HARDWARE SPECIFICATION
The ATARI experiments
conducted workstation equipped with AMD Ryzen 9 7950X CPU (32 cores at 4.5 GHz), 128 GB of RAM, and an NVIDIA RTX 4090 GPU with 24 GB of memory (driver version 12.3). All other numerical experiments performed 2024 MacBook Air with an Apple M3 processor.
27


Reviews:
[{"review_id": "a3EwKzJu5s", "reviewer": "Reviewer_QGxj", "summary": "This paper introduces ReaPER, an extension to Prioritized Experience Replay by incorporating a new measure of reliability of targets. By down weighting the priority of transitions with large TD error but low reliability, ReaPER is argued to benefit the sample efficiency improvements of PER while also mitigating the harmful updates caused by misleading TD errors. The main idea stems from the fact that the terminal transitions do not bootstrap and have more reliable targets. Target reliability is proposed to be inversely related to the sum of absolute values of TD errors of future transitions in the current episode.\n\nThe paper presents a suite of theoretical justification for why this proposed reliability measure controls the bias-error term in value error caused by bootstrapping. Further analyses discuss a sampling distribution based on this reliability measure that achieves lower value error than TD error-based prioritization and support the soundness of the ReaPER algorithm.\n\nFinally a variant of DDQN equipped with ReaPER is tested on two sets of RL problems: Three smaller classic control domains, and 10 larger Atari games. In classic control domains, ReaPER reaches a good evaluation performance faster than PER, while in Atari, ReaPER performs similar to PER in early learning but outperforms PER in terms of best-so-far checkpoint aggregated across 10 games.", "questions": "1. Regarding the % improvements statements in the paper, is the comparison based on individual agents (per-seed) then aggregated or are performance scores first aggregated and then compared to each other?\n\n2. How did you decide the aggregation scheme for Atari? If this is based on prior work please cite it. Or point me to where you mentioned this design choice.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- This is a good paper and it should be accepted. Its writing is clear, coherent, and well organized. The ideas are easy to grasp and follow with good justification and explanation for most design choices. The authors use illustrative examples and theoretical justification to support their proposed reliability measure and its incorporation in to PER\n\n- The paper does not overreach in its claims and its conclusions mostly match the provided evidence. The theoretical results are presented with easy to follow language and simple notation (although I am not a theoretician). The experiment results mostly match the claims of the authors and I did not feel the authors used overly sensational or exaggerated language\n\n- The authors cover a range of related works that place their paper in the context of past research. There two other recent papers that directly\ninvestigate the limitations of PER and their inclusion in the introduction would better motivate this paper:\n  - Panahi, P.M., Patterson, A., White, M., & White, A. (2024). Investigating the Interplay of Prioritized Replay and Generalization. RLJ, 5, 2041-2058.\n  - Carrasco-Davis, R., Lee, S., Clopath, C., & Dabney, W. (2025). Uncertainty Prioritized Experience Replay. ArXiv, abs/2506.09270.\n\n- The background section is clear and comprehensive, describing the RL problem and relevant objects for this research: MDP, Q-function, TD-error, Experience Replay, Sampling distribution\n\n- The theory section is nicely written, and is easy to understand. The paper does a good job making the theory accessible to a wider audience with intuitive reasoning, leaving the proofs for the Appendix (I did not check the proofs in the Appendix)\n\n- The ReaPER algorithm is clearly described in Pseudocode and its design choices and hyper parameters explained\n\n- The experiment details and setup are fully characterized including environment and agent details, choice of hyper parameters, and evaluation scheme", "weaknesses": "- Most of the justification and intuition behind ReaPER and the proposed reliability score is presented in the tabular setting. Non-linear generalization can wildly change the q-values during learning especially when the data distribution is being modified. Including a discussion of how this reliability measure interacts with non-linear generalization (oversampling certain transitions, higher noise in predicted values, overgeneralization, etc.) would better support and justify the ReaPER algorithm\n\n- One issue with the background section is that only the tabular version of Q-learning is introduced whereas the experiments in this paper focus on DDQN. So concepts such as semi-gradient Q-learning, target network, and optimizers such as Adam are not introduced.\n\n- Regarding the classic control experiments\n  - Agents are run until they reach a certain performance threshold and reported performance metric is averaged over 100 evaluations. RL algorithms are known to have large variability in performance and achieving one instance of good performance does not mean the agent has successfully learned to perform well on a task. A better way to characterize performance in classic control domains would have been to show learning curves of performance during learning for a fixed time step budget aggregated over seeds.\n  - The reported values and shaded regions in Figure 2 are undefined. It seems to be a Box and Whisker plot which suggests the middle horizontal bar is the median score. It is also unclear how the % improvements reported in the text are calculated. \n\n- Regarding Atari experiments,\n  - It is somewhat unclear whether the experiment is run for 50 million steps (200 million frames) or 50 million frames. My guess is that it is 50 million steps (200 million frames).\n  - The learning curves are monotone which suggests that the reported metric is the best-so-far checkpoint. I think reporting performance over time aggregated over games is a better way to characterize performance of an RL algorithm in Atari.", "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": "", "extra_scores": {}}, {"review_id": "AzTthaPHvw", "reviewer": "Reviewer_fBAN", "summary": "The authors introduce Reliability-Adjusted Prioritized Experience Replay (ReaPER), an improvement over traditional Prioritized Experience Replay (PER) in reinforcement learning.  PER prioritizes transitions based on temporal-difference errors to enhance learning efficiency, but it can fail when TDE-based targets are unreliable, leading to inaccurate value estimates.  ReaPER addresses this issue by incorporating a reliability score derived from downstream TDEs, ensuring that transitions with more trustworthy targets are sampled more frequently. In simpler terms, ReaPER applies a backward-decaying weighting scheme from the episode’s end toward its beginning.\n\nThe paper provides theoretical analyses showing improved convergence and variance reduction under reasonable assumptions, supported by extensive experiments on CartPole, Acrobot, LunarLander, and the Atari-10 benchmark. Empirically, ReaPER consistently outperforms PER, achieving faster convergence and higher peak performance, while requiring minimal hyperparameter tuning and introducing only modest computational overhead.", "questions": "- Could you report **wall-clock training time per environment** for PER vs. ReaPER, and quantify the fraction of time spent updating cumulative TD sums? This would confirm that the additional computational cost is indeed negligible in practice.\n- How might the reliability computation be **extended to continuing tasks**? What pitfalls would you anticipate?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- The paper is **well-written and clearly structured**.\n- theoretical foundation linking reliability scores to TDE target biases.\n- Clear methodological improvements over standard PER.  \n- Algorithm is model-agnostic and straightforward to implement in existing off-policy methods.", "weaknesses": "1. **Limited baseline comparisons.**  The paper primarily compares ReaPER only against PER. While the authors justify this by PER’s ongoing adoption in SOTA systems (e.g., Sample-Efficient Deep Reinforcement Learning via Episodic Backward Update) would make the empirical evidence more convincing.\n2. ReaPER does **not robustly address episode-length variance**, limiting its generalizability. This introduces severe biases and undermines reliability scores, making them heavily dependent on arbitrary episode lengths rather than meaningful signal. This weakens the paper’s claims of broad applicability.", "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": "", "extra_scores": {}}, {"review_id": "xGEyR7Lz4H", "reviewer": "Reviewer_aaDF", "summary": "This paper proposes an extension of prioritized experience replay mechanism for off-policy reinforcement learning algorithms. Specifically, the paper first conducts formal analysis of bias-error interaction in prioritized sampling and its impact on Q-value estimation, then practically proposes the reliability-adjusted experience replay. The proposed method down‑weights TD errors using a trajectory‑wise “reliability” score derived from downstream absolute TD errors and provide theoretical guarantees through convergence hierarchy and variance reduction of the Q function update to show better sample efficiency over standard experience replay framework with uniform sampling. The empirical experiments on continuous control tasks and Atari shows outperforming performances over both prioritized experience reply and uniform sampling experience sampling within one percent of variance.", "questions": "1. How often does Assumption 3.4 approximately hold during training? Have you observed that before? If so, can you provide empirical diagnostics or plots validating this assumption?\n2. How robust is the method to episode length variability and partial observability?\n3. Why not include stronger baselines (e.g., PSER, ERO, NERS)?\n4. Can the authors provide confidence intervals, statistical significance tests, and seed counts for Atari results?\n5. Why are results limited to DDQN? \n6. How does the method scale to large replay buffers?", "limitations": "", "rating": 2, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed concept is well-motivated with theoretical analysis and easy to implement on top of prioritized experience replay framework.\n2. The empirical analysis on both continuous control and Atari-10 shows robust and superior performance against all the baselines.\n3. The writing is logically fluent and easy to follow.", "weaknesses": "1. The assumption appears overly strong. Specifically, Assumption 3.4 relies on a bias bound that presumes near-optimal trajectories. During training, policies are far from optimal, so this bound rarely holds early on. Moreover, function approximation and bootstrapping introduce high variance and correlation in TD errors, making the downstream sum an unreliable proxy for bias. Especially, in partially observed environments, future TD errors may fluctuate unpredictably.\n\n2. The empirical experiment result. It is not clear how many random seed was involved for the Atari-10 experiment and there's no confidence interval in the Figure 3 Right. In addition, there is no runtime analysis, which cannot prove that whether ReaPER is practically efficient for training or just theoretically \"sample efficient\" for training. (i.e., Using less timestamp but each timestamp takes way longer runtime).\n\n3. The empirical experiment setting. The authors only demonstrate the ReaPER with DoubleDQN, which is not sufficient to support the claim of \"algorithm-agnostic and can be used within any off-policy RL algorithm\".\n\n4. Missing comparison with state-of-the-arts. Although the author mentions many related works on PER, none of them are being included into the comparison. This makes it hard to evaluate the contribution and novelty of the proposed method given there exists many variants of PER.", "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": "", "extra_scores": {}}, {"review_id": "WnISNkzsEO", "reviewer": "Reviewer_bfXy", "summary": "This paper introduces Reliability-adjusted Prioritized Experience Replay (ReaPER), an enhanced sampling method for reinforcement learning that addresses a key flaw in standard Prioritized Experience Replay (PER). While PER prioritizes training on transitions with high Temporal Difference Errors (TDEs), this paper claims that it overlooks the fact that the target Q-value used to calculate this error may be unreliable, potentially misdirecting the learning process. ReaPER solves this by introducing **a reliability score**, which weights each transition's priority not only by its TDE but also by the stability of its target value, **defined as being inversely proportional to the sum of TDEs in subsequent states of the same trajectory.** The authors provide both theoretical proof that this reliability-adjusted approach leads to faster convergence and lower error , and empirical results in both classic control environments and the Atari-10 benchmark.", "questions": "I have the following questions.\n\n### 1. Insufficient Scope of Algorithmic Validation\n\nFirst and foremost, the **algorithmic scope of the experiments appears insufficient**. Deep Double Q-Network (DDQN) is now considered as a classical algorithm. Consequently, demonstrating the method's effectiveness exclusively within the DDQN framework raises questions regarding its general applicability and robustness. The paper would be significantly more compelling and the findings more rigorously validated if the method's efficacy were also demonstrated across a broader range of popular algorithms, such as **Deep Deterministic Policy Gradient (DDPG)**, **Soft Actor-Critic (SAC)**, or advanced value-based methods after **Rainbow**. Expanding the experimental scope is critical for establishing the generalizability of the proposed approach.\n\n---\n\n### 2. Justification Required for Assumption in Equation (9)\n\nFurther discussion and justification are required regarding the assumption presented in Equation (9). A counterexample, frequently observed in complex, multi-stage tasks (such as Go or Chess), suggests that Q-value estimation difficulty does not always monotonically decrease. Specifically, the difficulty of reliable Q-value estimation often peaks during the initial and mid-game phases due to high uncertainty and complex structure, while the end-game becomes computationally simpler. Therefore, the authors must provide a more detailed and robust justification for this assumption, addressing how it holds in the context of tasks exhibiting these non-monotonic difficulty dynamics. For instance, in [1], it looks like that the authors used model prediction components to handle these situations.\n\n[1] Oh, Youngmin, et al. \"Model-augmented prioritized experience replay.\" International Conference on Learning Representations. 2022.", "limitations": "", "rating": 2, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. Providing some theoretical results to verify the effectiveness of this proposed method.\n\n2. A well-structured motivation", "weaknesses": "1. A limited set of experiments\n\n2. Further discussion is needed regarding the validity of this assumption.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)