Reinforcement Learning2015intermediate9 min read

Prioritized Experience Replay

إعادة التجربة بالأولوية

Schaul, T. · Quan, J. · Antonoglou, I. · Silver, D. — ICLR

The problem

In , the stores past experiences in a and samples from them uniformly at random. But not all experiences are equally useful: a rare success buried among thousands of failures gets the same replay chance as a redundant, already-learned transition. This wastes computation and slows learning, especially when rewards are sparse.

The contribution

A framework that replays important transitions more frequently, measured by the magnitude of their — how "surprising" a transition is to the current . interpolates between greedy and uniform to maintain diversity, and weights correct the introduced by non-uniform sampling. Applied to DQN on the Atari benchmark, prioritized replay doubles learning speed and improves final score on 41 out of 49 games.

The impact

Prioritized replay became a standard component in deep RL. It is one of the six key improvements combined in Rainbow DQN, the definitive DQN variant. The idea extends beyond RL: prioritized sampling from imbalanced datasets in supervised learning, and curriculum-like strategies that focus computation on the most informative data points.

Imagine a chef preparing for a cooking competition. Every evening she reviews the day's dishes. With uniform replay, she re-tastes every dish equally — the perfect soufflé and the burned risotto get the same attention.

With prioritized replay, she starts with the burned risotto — the dish that surprised her most — because that's where the biggest lesson hides. She still checks the soufflé occasionally (stochastic sampling ensures diversity), but she spends her limited review time where it counts.

The problem: uniform sampling wastes effort

In the original DQN, the agent stores every transition $(s, a, r, s')$ in a large replay buffer and draws minibatches uniformly at random. This breaks temporal correlations (good for stable gradients) but treats every transition as equally valuable.

Consider a robot learning to walk. For every step that keeps it upright, there are hundreds of falls. The rare "I took a good step!" transitions carry the most learning signal, yet they're sampled at the same rate as the redundant falls. In the Blind Cliffwalk experiment from the paper, the agent needs an exponential number of random samples ( $2^n$ ) to find the single rewarding path — but with prioritized replay, learning becomes tractable.

Open in Lab

Watch how uniform sampling treats all transitions equally, while prioritized sampling focuses on high-error (surprising) transitions. Click "Step" to draw samples.

The demo wakes as you arrive…

The key idea: TD error measures surprise

How do we know which transitions are "important"? The ideal measure would be the expected learning progress — how much the agent's knowledge would improve by studying that transition. We can't compute this directly, but a powerful proxy is the TD error: the gap between what the agent predicted and what it actually observed.

Think of it as a surprise meter. When the agent predicts a state is worth 5 points but discovers it's actually worth 15, the TD error is large — this transition has a lot to teach. When prediction matches reality, the TD error is near zero — the agent already knows this lesson.

The TD error for a transition is:

\delta = R + \gamma \max_{a'} Q(s', a') - Q(s, a)

TD error — the "surprise" signal — R = immediate reward · γ max Q(s',a') = discounted best future value · Q(s,a) = what the agent predicted · |δ| = how wrong the prediction was — large means more to learn

The simplest approach is greedy prioritization: always replay the transition with the largest |δ|. This works dramatically well on toy problems — but has three serious flaws in practice:

Stale priorities: TD errors are only updated when a transition is replayed, so a transition with low initial error may never be revisited, even if the changing value function would now assign it a large error.
Noise sensitivity: noisy rewards or errors can spike the TD error, causing the agent to obsess over noisy transitions.
Loss of diversity: the agent keeps replaying the same high-error transitions, to them while ignoring the broader distribution.

Open in Lab

Drag the slider to change a transition's actual reward and watch the TD error (surprise) change. Large |δ| means the agent has more to learn.

The demo wakes as you arrive…

Stochastic prioritization: balancing greed and diversity

The solution is to make sampling probability monotonic in priority but never zero — even the lowest-priority transition has some chance of being drawn. The probability of sampling transition $i$ is:

P(i) = \frac{p_i^{\alpha}}{\sum_k p_k^{\alpha}}

Stochastic prioritization — the sampling distribution — p_i = priority of transition i · α = controls how much prioritization is used · α = 0 gives uniform sampling · α = 1 gives fully proportional prioritization

The paper proposes two ways to define the priority $p_i$ :

Proportional: $p_i = |\delta_i| + \epsilon$ , where $\epsilon$ is a small constant preventing zero probability. The sampling probability is directly proportional to the TD error magnitude.

Rank-based: $p_i = 1/\text{rank}(i)$ , where transitions are ranked by $|\delta_i|$ . This creates a power-law distribution that is more robust to outliers because it only cares about the ordering, not the actual error magnitudes.

Think of it like a playlist: proportional prioritization is like playing songs proportional to their play count — a viral hit dominates. Rank-based is like "play #1 most, #2 second most, etc." — the specific counts don't matter, only the ranking.

Open in Lab

Adjust α to see how proportional vs rank-based prioritization distribute sampling probability across transitions with different TD errors.

The demo wakes as you arrive…

Correcting the bias: importance sampling weights

Non-uniform sampling introduces bias: we're no longer computing the expected over the true data distribution. If left uncorrected, the value function converges to the wrong answer. The fix is importance sampling — we reweight each gradient update to undo the distortion caused by prioritized sampling.

Think of a survey: if you oversample one demographic, you must downweight their responses to get accurate population statistics. The same principle applies here.

w_i = \left(\frac{1}{N} \cdot \frac{1}{P(i)}\right)^{\beta}

Importance sampling weight — correcting the bias — N = replay buffer size · P(i) = sampling probability of transition i · β = controls how much correction is applied · β = 1 gives full correction · β < 1 gives partial correction

A clever trick: since is highly non-stationary early on (the and value function change rapidly), a small bias doesn't hurt much. The authors anneal β from a low initial value to 1 over the course of training. Early training gets aggressive prioritization with minimal correction; by , the correction is full.

The weights are also normalized by $1/\max_i w_i$ so they only scale updates downward, preventing instabilities from large gradient steps. This normalization interacts beautifully with annealing: as β approaches 1, the normalization constant grows, naturally reducing the effective step size — a form of implicit annealing.

Open in Lab

Drag the training progress slider to see how β annealing changes the IS weights over time. Early: aggressive prioritization. Late: full bias correction.

The demo wakes as you arrive…

Putting it all together

The full algorithm integrates prioritized sampling into Double DQN. The changes are surgical: only the sampling mechanism changes; the , learning algorithm, and replay memory size stay identical.

The key steps in each learning iteration are:

Store new transitions with maximal priority (ensuring they are seen at least once)
Sample a minibatch according to the prioritization distribution $P(i)$
Compute TD errors and importance sampling weights for the sampled transitions
Update network weights using the weighted TD errors
Update the priorities of the sampled transitions with their new TD errors

Open in Lab

Click on leaf nodes to change priorities and see how the Sum Tree updates propagate upward. Sample by clicking "Draw" to see proportional sampling in action.

The demo wakes as you arrive…

The idea in code

Prioritized replay — core sampling and update logicpython

Simplified to show the idea — not the real implementation.

import numpy as np

class PrioritizedReplayBuffer:
    """Simplified proportional prioritization with importance sampling."""

    def __init__(self, capacity, alpha=0.6, beta_start=0.4):
        self.capacity = capacity
        self.alpha = alpha          # how much prioritization: 0=uniform, 1=full
        self.beta = beta_start      # IS correction: annealed to 1 over training
        self.priorities = np.zeros(capacity, dtype=np.float32)
        self.buffer = [None] * capacity
        self.pos = 0                # circular write position
        self.size = 0

    def add(self, transition, td_error=None):
        """Store with max priority so new transitions get replayed at least once."""
        priority = self.priorities[:self.size].max() if self.size > 0 else 1.0
        if td_error is not None:
            priority = (abs(td_error) + 1e-6) ** self.alpha
        self.buffer[self.pos] = transition
        self.priorities[self.pos] = priority
        self.pos = (self.pos + 1) % self.capacity
        self.size = min(self.size + 1, self.capacity)

    def sample(self, batch_size):
        """Sample proportionally to priority, return IS weights."""
        probs = self.priorities[:self.size] ** self.alpha
        probs /= probs.sum()                            # P(i)

        indices = np.random.choice(self.size, batch_size, p=probs, replace=False)

        # Importance sampling weights: w_i = (N * P(i))^(-β) / max(w)
        weights = (self.size * probs[indices]) ** (-self.beta)
        weights /= weights.max()                        # normalize

        transitions = [self.buffer[i] for i in indices]
        return transitions, indices, weights

    def update_priorities(self, indices, td_errors):
        """Update priorities with fresh TD errors after a learning step."""
        for idx, td_err in zip(indices, td_errors):
            self.priorities[idx] = (abs(td_err) + 1e-6) ** self.alpha

    def anneal_beta(self, progress):
        """Linearly anneal β toward 1.0 as training progresses."""
        self.beta = 0.4 + progress * (1.0 - 0.4)

# Usage: after computing TD errors in your DQN update loop,
# multiply each gradient by the IS weight:
#   loss = (weights * td_errors ** 2).mean()

Results on the Atari benchmark

The authors tested prioritized replay on 49–57 Atari games with identical hyperparameters across all games — no per-game tuning. The key findings:

Adding prioritized replay to DQN improved scores on 41 out of 49 games, raising the median normalized performance from 48% to 106%.
Combined with Double DQN, the median rose from 111% to 128%, and the mean from 418% to 551%.
Learning speed roughly doubled: prioritized agents reached the baseline's final performance in about 40–47% of the training time.
Games with sparse rewards (like Frostbite, Battlezone, and Zaxxon) benefited the most, because prioritization quickly surfaces the rare informative transitions.

Open in Lab

Normalized score improvement from adding prioritized replay to Double DQN across Atari games. Most games see substantial gains.

The demo wakes as you arrive…

Why it mattered

2013
DQN (original)
Introduced experience replay to stabilize deep RL training. Used uniform sampling from a replay buffer of 1M transitions.
2015
Prioritized Experience Replay
Replaced uniform with priority-based sampling using TD error. Doubled learning speed and set a new state-of-the-art on Atari.
2016
Double DQN + Prioritized Replay
Combining prioritized replay with Double Q-learning yielded complementary gains — proving the improvements are orthogonal.
2017
Rainbow DQN
Combined six DQN improvements including prioritized replay into one agent that dramatically outperformed each component alone.

CitationSchaul, Quan, Antonoglou, Silver. Prioritized Experience Replay. ICLR, 2016.

Terms in this paper

Experience Replayإعادة تشغيل التجارب
TD Errorخطأ الفارق الزمني
Samplingاختيار العينات الاحتمالية
Replay Bufferذاكرة التجارب
Importance Samplingأخذ العيّنات المُرجَّحة
Stochastic Prioritizationالترتيب العشوائي بالأولوية
Deep Q-Network (DQN)الشبكة العميقة لتعلم الجودة
Off-Policyخوارزمية التعلم خارج السياسة الحالية