How do you size a replay buffer when its old transitions come from a policy and a world that have both changed?

## Two staleness problems that get confused "Stale buffer" is used for two failures with different severities and different fixes. **Policy staleness.** The transitions were produced by earlier, worse versions of the agent. This is precisely the case off-policy value learning is designed for: the target `r + gamma * max_a' Q(s', a')` never refers to the action the behaving policy chose, so the transition remains a correct sample of the environment's dynamics and reward. The real costs are distributional, not correctness. The loss is averaged over a mixture of every policy the agent has had, so network capacity is spent fitting values in regions the current policy has abandoned; and because that mixture changes only as fast as old data is evicted, the agent is slow to reflect a policy improvement in its own training distribution. **Environment staleness.** The world itself changed. In a recommendation-slate agent, a buffer holding impressions logged two weeks ago against a catalogue that has since turned over contains transitions whose actions index items that no longer exist and whose rewards were generated by a demand pattern that no longer holds. These are not off-policy samples of the current problem; they are on-policy samples of a *different* problem. No importance weighting or off-policy argument makes them valid, because the underlying transition and reward functions moved. Training on them biases the value function toward a world that is gone, and the symptom is an agent that performs well against replayed history and poorly live. The first question to ask about any buffer, therefore, is not "how old is the data" but "is the environment stationary over that horizon". ## What capacity actually controls A useful piece of arithmetic keeps expectations straight. With FIFO eviction, one insertion and one batch of size B per environment step, a transition survives about `N` steps in a buffer of capacity `N` and is drawn on each step with probability roughly `B / N` — so it is expected to be sampled about `B` times before eviction, *independently of N*. Capacity does not control how much each sample is reused. It controls the age distribution: the expected age of a sampled transition is on the order of `N / 2` environment steps, and the fraction of any batch that is recent is the recent window divided by `N`. Sizing a buffer is therefore a decision about how far into the past you are willing to average, expressed in environment steps. ## Costs of shrinking it The reflex fix for staleness — make the buffer smaller — reintroduces exactly what replay was for. Two specific costs: **Correlation returns.** A small buffer holds a narrow slice of recent episodes, so a uniform batch drawn from it contains near-duplicate transitions again, and updates start chasing current behaviour. **Rare events are lost first.** Imagine a driving agent whose buffer is 95% uneventful lane-keeping transitions and a few percent hard-braking or near-miss events. Halving the capacity halves the *count* of rare events while the common ones remain plentiful in absolute terms — and rare events are usually the ones with the largest reward signal and the least redundancy. The value function forgets the situations that matter most, and it does so silently, because average loss barely moves. ## Practical levers - **Timestamp or version every transition** with the policy iteration and any environment version identifier that exists (a catalogue release, a pricing change, a firmware update). Once you have that, staleness becomes a filter you can reason about rather than a guess. - **Evict on the change cadence, not a round number.** If the catalogue turns over on a two-week cycle, a capacity that spans several cycles is wrong regardless of how much memory is free. - **Mix rather than choose.** Draw most of the batch uniformly from the buffer and a fixed slice from a recent window. This keeps decorrelation while guaranteeing every gradient step sees current data. - **Partial invalidation beats flushing.** On a known environment change, drop the transitions the change actually invalidates — those involving removed items, or reward components affected — and keep the ones whose dynamics did not change. A full flush hands you a cold, correlated buffer and forgets everything the agent learned about parts of the world that are unchanged. - **Segregate rare events.** Retaining an uncapped or separately-capped store of terminal, failure or high-reward transitions protects them from FIFO eviction. ## Diagnosing it instead of guessing Staleness is measurable. Log the age distribution of sampled transitions, in environment steps and in wall-clock time. Compare the state distribution the current policy visits with the buffer's — even coarse feature histograms show a gap. Most directly, hold out a small stream of freshly collected transitions and evaluate the value error on fresh versus buffer-drawn data: if the error on fresh transitions is systematically worse, the buffer is teaching the wrong world. Under real non-stationarity that gap grows monotonically with buffer age, which distinguishes it from ordinary off-distribution effects. ## The judgment call There is no default capacity. The honest answer names the horizon over which the environment is approximately stationary, sets capacity inside that horizon, then checks whether the shrunken buffer still holds enough rare events and enough diversity to keep batches decorrelated. If those two requirements conflict — the world changes faster than you can collect diverse data — the buffer is not the thing to fix; the agent needs a way to adapt that does not depend on averaging over a long past.