M8-T5 — Replay Buffers and Data Efficiency

Learning objectives

After this lesson, you should be able to:

• Implement a ring buffer with uniform sampling, and say what replay buys (decorrelation, reuse) and what it risks (staleness, forgetting).
• Compute prioritised-replay probabilities p^α / Σp^α and importance weights by hand, and explain what each is for.
• Describe hindsight relabelling, augmentation and the update-to-data ratio, and the way each reuses data.
• Read a replay experiment over 20 seeds, including its instabilities, and cost a buffer in robot-hours and storage.

The intuition

A nurse robot bumps into a trolley once in two thousand steps. The learner trains from a buffer of recent steps. If the buffer holds the last 50 steps, then at any moment it contains a collision only about 2.5% of the time, and when it does, the collision is sampled for a few updates and then gone. The learner is trained mostly on corridors, and what it believes about trolleys is whatever it remembers from the last time one appeared. The figure shows the probability that a first-in-first-out buffer holds at least one collision, as a function of its capacity: 0.025 at 50, 0.221 at 500, 0.918 at 5,000.

Replay is therefore two things at once. It is a way to reuse data (cheap computation in place of expensive robot time) and a memory policy (what the learner is allowed to remember). Getting the first right and ignoring the second is a common cause of learners that look fine on average and fail on the rare event that matters.

The mathematics

The ring buffer and uniform sampling

A buffer of capacity C holds transitions (s, a, r, s', done). A ring buffer appends while it is not full; when full, it overwrites the oldest entry at the position ptr, then moves ptr to (ptr + 1) mod C. Sampling a minibatch of B items draws B indices uniformly from the stored entries: index = floor(u × size) for a uniform u in [0, 1), with the guard that an empty buffer cannot be sampled. Lab M8-L1 asks you to write these two functions, and the usual bugs are an off-by-one at the top index (the newest entry is never drawn) and an overwritten pointer that is not advanced.

What replay does

• Breaks correlation. Consecutive steps are almost the same state. A minibatch of consecutive steps pushes a network the same way B times; a uniform sample from the buffer mixes many situations.
• Reuses data. Each transition can feed many updates, which matters when a step costs robot time (lesson M6-T6).
• Needs an off-policy learner. A transition in the buffer was made by an older policy. Q-learning and SAC (lessons M4-T6 and M6-T6) allow this; plain policy gradients (lessons M6-T2 and M6-T5) do not.
• Introduces staleness and forgetting. An old transition may be unrepresentative of the current policy, and a transition older than C steps is gone.

Prioritised replay

Schaul et al. (2016) sample transitions in proportion to a priority p_i, typically the magnitude of the temporal-difference error |δ_i| plus a small constant so that no transition has zero probability. The sampling probability and the correction weight are:

With α = 0 sampling is uniform; α = 1 is proportional to the priority. Because high-priority items are over-sampled, the gradient is biased, and the importance weight w_i multiplies the loss to correct it: β = 1 corrects fully, and the original paper increases β toward 1 during training. The denominator normalises the weights so that the largest is 1 and the update never gets larger than uniform replay would. This is the same importance-sampling idea as in off-policy evaluation, applied to the sampling of the buffer.

Hindsight relabelling

In goal-conditioned tasks with sparse rewards (lesson M5-T3), most episodes end without reaching the goal and carry no reward signal. Hindsight experience replay (Andrychowicz et al., 2017) stores each transition a second time with the goal replaced by a state that was actually reached later in the same episode; with that goal, the episode succeeded, and the reward is recomputed accordingly. The learner receives a reward signal from failures. It applies when the goal is a part of the state that can be substituted and when the reward is a function of the goal, which is true for reach-and-place tasks and not for every task.

Data augmentation

If the observation is an image, a small random shift or crop of each sampled image gives the learner many slightly different views of the same transition. Laskin et al. (2020) and Kostrikov, Yarats and Fergus (2021) showed that this simple change improves the sample efficiency of pixel-based RL substantially on the benchmarks they used. The principle is the one of lesson M2-T5: an augmentation is a claim that the label does not change under the transformation, so it should be chosen only for transformations of which that is true (a horizontal flip of a camera image swaps left and right, and is wrong for a steering task).

The update-to-data ratio

The update-to-data (UTD) ratio is the number of gradient updates per environment step. A UTD of 1 is the usual default; a larger one extracts more learning from each transition at the price of computation, and of the risk of overfitting a network to the contents of the buffer, since the same transitions are fitted again and again. Chen et al. (2021) report that high UTD ratios can be made to work with ensembles of Q-functions that reduce the bias, which indicates that the naive version is fragile; I describe their result at that level.

C

Buffer capacity in transitions.

K

Updates per environment step (the UTD ratio) in the experiments below.

p, α, β

Priority, how strongly priority sets the sampling probability, and how strongly the weights correct it.

N

The number of transitions currently in the buffer.

A worked example

Every number below was computed with Node. The first two parts are hand-checkable; the third is a 20-seed experiment on the grids of Module 4.

1. A rare event in a FIFO buffer

A collision has probability 1/2000 per step. The probability that a buffer of capacity C holds at least one is 1 − (1 − 1/2000)^C = 0.0247 for C = 50, 0.2212 for C = 500 and 0.9180 for C = 5,000 (the figure). If collisions were exactly 2,000 steps apart, a buffer of 500 would contain one for 500 / 2000 = 25% of the time and a buffer of 50 for 2.5%. A collision enters, is drawn about B × (updates / size) times while it stays, and leaves. Both calculations assume the buffer is filled with steps in order and that the events are independent; a real log has bursts, and the calculation shows the order of magnitude and not the exact retention.

2. Prioritised replay by hand

Four transitions have priorities p = 0.1, 0.5, 1 and 4, with α = 0.6 and β = 0.4.

The transition with priority 4 is drawn with probability 0.546, compared with 0.25 for uniform sampling, and 9.1 times as often as the one with priority 0.1 (0.546 / 0.060). With α = 1 it would be 0.714, which is 40 times (4 / 0.1) as often as the low-priority one. The weights go the other way: the over-sampled transition is down-weighted to 0.413 and the rarely drawn one has weight 1.000. A rarely drawn transition is in this way not neglected by the update.

3. Replay on the cliff and the ward

The setting: Q-learning of lesson M4-T6 on the cliff (deterministic, step reward −1, goal +10, stairwell −100 with reset, discount 0.99) and the ward (slip 0.2, step reward −0.1, goal +10, stairwell −10 terminal, discount 0.95), step size 0.5, epsilon 0.1, at most 200 steps per episode, 300 episodes. I wrote the replay loop myself in Node: after each environment step, the transition is written into a ring buffer of capacity C and then K updates are made, each on a transition drawn uniformly from the buffer. The baseline without replay does K updates on the newest transition only (K = 1 is ordinary Q-learning). After every episode I compute the exact value at the start of the greedy policy (RLCore.evaluatePolicyDP). "Good" is a value of at least −3.5 on the cliff (the safe path that avoids the stairwell is worth −3.38; the optimum is 0.58) and at least 80% of the optimum, 2.65, on the ward (optimum 3.31). Twenty seeds, SLAMCore.rng(1..20). First = the first episode at which the greedy policy is good, mean over the seeds that reached it. Steps = environment steps at that moment (the robot’s cost).

What the numbers say.

• Replay with one update per step did not help. On the cliff, C = 50 was a little faster in episodes (8.1 against 11.9) but took more environment steps (898 against 596), because its episodes were longer. Larger buffers were no better than 11.9 and used 1,397 to 1,429 steps. On the ward, replay with K = 1 was slower (38.5 to 46.5 episodes against 30.9). The reason I believe, not tested separately: with K = 1 a sample from a big buffer is mostly an old transition, so the newest information, which is the most informative for a learner that is still changing, is applied rarely.
• Replay with more updates did help, in this tabular setting. Cliff with C = 500 or 5,000 and K = 8: 3.8 episodes and 361 to 364 steps, about a third of Q-learning’s episodes and 61% of its steps. Ward with C = 5,000 and K = 8: 12.4 episodes and 740 steps against 30.9 and 1,698, a factor of 2.3 in real steps. Updates cost computation: 2,916 on the cliff and 5,918 on the ward at the moment of success against 596 and 1,698.
• Repeating the same newest transition 8 times (no replay, K = 8) gained little on the cliff (10.3 against 11.9, intervals overlap) and nothing reliable on the ward. The gain with replay comes from the variety of transitions in the 8 updates.
• The benefit was not free of cost. On the ward, C = 5,000 with K = 8 failed to reach a good policy in 300 episodes in 3 of 20 seeds, and C = 500 in 1 of 20 (and C = 500, K = 1, in 2 of 20). I did not diagnose the failed seeds. A candidate (untested) is that a big buffer keeps replaying early, mis-valued transitions.
• "Good" is not the same as "stays good". With step size 0.5 in a slippery world the greedy policy keeps flipping between good and bad: only 5 to 10 of 20 ward runs were good at episode 300 whatever the buffer, so the first-good episode overstates how soon a learner is dependable. On the deterministic cliff, replay with K = 8 became good at about episode 4 and stayed good (4.0 to 4.3); Q-learning needed 16.0 to stay good, and replay with K = 1 needed 15.7 to 20.6. The step size is large for noisy problems, and I did not tune it.

The cost of a buffer in robot time

At a control rate of 10 Hz, 5,000 transitions are 500 s, or 8.3 minutes, of robot time; one million transitions are 100,000 s = 27.8 hours, about three working days of continuous operation, before any resets, charging or failures. The 364 real steps in the best cliff run correspond to 36 seconds at 10 Hz; the tabular tasks of this lesson are far smaller than any real task, and these are costs of the toy, not of a robot.

What this simulation simplifies. Tabular, tiny state spaces, uniform sampling only, a constant step size, no function approximation (so no overfitting to the buffer) and no prioritised-replay experiment: the prioritisation part of the lesson is a hand calculation and was not run on the grids. Conclusions about the update-to-data ratio with neural networks should not be drawn from these tables.

Engineering implications and limitations

Design checklist for a replay buffer

1. Choose the capacity from the time scale of what must be remembered, not from the memory available: how many steps between rare but important events, and how much the policy changes over that time.
2. Store everything needed to reconstruct the update: state, action, reward, next state, a terminal flag that is separate from a time-limit truncation (lesson M4-T6), and the policy or version that produced it.
3. Decide what is never overwritten: a reserved region for rare events (collisions, recoveries, successes) or a second buffer, so that the corridor does not push them out. A reservoir sample is a simple alternative to FIFO when old data must stay representative; lab M8-L1 draws the three side by side.
4. Sample uniformly first. Add prioritisation only if the learner is limited by rare informative events, and then correct with importance weights.
5. Raise the UTD ratio step by step and watch the value-loss and the evaluation return (lesson M6-T7); stop when evaluation stops improving or the Q-values grow without the returns.
6. Evaluate on fresh episodes in the real or simulated environment, never on buffer data.

Reuse versus overfitting to the buffer

With a network, many updates on a small buffer can fit the buffer’s contents (including its noise) instead of the task; the evaluation return then stops following the training loss. The remedies are the same family as in lesson M2-T5: more diverse data, augmentation, regularisation, and a smaller UTD ratio. Another failure is feedback: the policy collects data, the data train the policy, and the buffer holds a narrow slice of experience. That is the online counterpart of the coverage problem of lessons M8-T2 and M8-T3.

Real robot costs

• Robot-hours are the scarce quantity, and a buffer is the record of how they were spent. Count the hours behind each dataset: setup, resets, failures, supervision, and the hours that produced nothing usable.
• Storage: images dominate. A 64 x 64 RGB frame is 12,288 bytes uncompressed, so a million transitions with two frames each is about 25 GB before compression; plan for it.
• Safety of collecting the data is part of the cost (lesson M5-T5); randomness used for exploration must itself be safe.
• Reuse across experiments: a buffer from one policy is an offline dataset for the next, which is exactly the setting of module 8’s first lessons, so treat it with the same coverage checks (lesson M8-T2).

Logging and versioning

Treat the buffer as a dataset with a version. Record the code revision, the policy checkpoint and exploration noise that wrote each part, the robot and calibration, the observation and action definitions, and the reward function (a reward change makes old rewards wrong; relabel or discard). Keep an immutable copy of the data used by each reported result and the random seeds (lessons M11-T3 and M2-T6). Hindsight relabelling and augmentation should be applied at sampling time, never written over the stored data, so the original is recoverable. If a log is later used for offline learning, the conservative methods of lesson M8-T4 and the checks of lesson M8-T3 apply.

Common misconceptions

Engineering takeaways

1. A ring buffer overwrites the oldest entry; uniform sampling breaks correlation and allows reuse, and it needs an off-policy learner.
2. A FIFO buffer forgets rare events: with a collision rate of 1 in 2000, capacity 50, 500 and 5,000 hold one 2.5%, 22.1% and 91.8% of the time.
3. Prioritised replay samples P(i) = p^α / Σp^α and corrects with w_i normalised by the largest: for p = 0.1, 0.5, 1, 4 at α = 0.6 and β = 0.4, P = 0.060, 0.157, 0.238, 0.546 and w = 1.000, 0.680, 0.575, 0.413.
4. Measured over 20 seeds: replay with 1 update per step was not faster than Q-learning on either grid; with 8 updates per step the cliff needed 3.8 episodes against 11.9 and the ward 12.4 against 30.9 (with 3 of 20 failed seeds), and the ward policy kept flipping.
5. Hindsight relabelling and augmentation reuse data by changing how it is read, the UTD ratio reuses it by computation; all are paid for in assumptions, in overfitting risk, and in the robot-hours that produced the buffer, which need logging and versioning.

References and further reading

Lin introduced experience replay for RL and Mnih et al. made it standard for deep Q-learning; the other entries are the primary sources of the techniques named above. The numbers are my own measurements, not from these papers.

• L.-J. Lin, “Self-Improving Reactive Agents Based on Reinforcement Learning, Planning and Teaching”, Machine Learning 8, 1992.
• V. Mnih et al., “Human-Level Control through Deep Reinforcement Learning”, Nature 518, 2015.
• T. Schaul, J. Quan, I. Antonoglou and D. Silver, “Prioritized Experience Replay”, International Conference on Learning Representations (ICLR), 2016.
• M. Andrychowicz et al., “Hindsight Experience Replay”, Advances in Neural Information Processing Systems (NeurIPS), 2017.
• M. Laskin, K. Lee, A. Stooke, L. Pinto, P. Abbeel and A. Srinivas, “Reinforcement Learning with Augmented Data”, Advances in Neural Information Processing Systems (NeurIPS), 2020.
• I. Kostrikov, D. Yarats and R. Fergus, “Image Augmentation Is All You Need: Regularizing Deep Reinforcement Learning from Pixels”, International Conference on Learning Representations (ICLR), 2021.
• X. Chen, C. Wang, Z. Zhou and K. Ross, “Randomized Ensembled Double Q-Learning: Learning Fast Without a Model”, International Conference on Learning Representations (ICLR), 2021.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

That completes the theory of Module 8: fixed datasets, coverage, extrapolation error, conservative methods and buffers. Labs M8-L1 to M8-L3 build a replay buffer, find a coverage gap and compare an online and an offline policy. Module 9 turns to where learning meets contact: grasping, manipulation and locomotion.

Related content

Nothing below is required to finish this lesson.

• Before
  M8-T4: Conservative and Implicit Methods

  Describe the idea behind behaviour-constrained, conservative and implicit methods, without claiming more than they guarantee.

• Lab
  M8-L1: Build a Replay Buffer

  The buffer forgets the rare collisions and over-samples the corridor: fix sampling and capacity.