Technical Summary: Endpoint Replay: Compressing the Recency Buffer in Deep Reinforcement Learning

Problem Statement

Deep Reinforcement Learning (DRL) algorithms, particularly off-policy methods like DQN, SAC, and DreamerV3, rely heavily on large experience replay buffers (typically 1 million transitions) to de-correlate samples, retain data for hard exploration, and propagate sparse rewards. While effective, these large buffers incur significant storage costs and computational overhead.

Prior attempts to reduce buffer size have focused on:

1. Continual RL: Compressing buffers to track non-stationary tasks, often sacrificing long-term retention.
2. Streaming/Generative Methods: Eliminating buffers entirely or using generative models, which can introduce simulation bias or instability.
3. Coreset Construction: Selecting representative transitions (e.g., via reservoir sampling) to summarize a large buffer.

The central problem addressed by this paper is whether a large recency buffer can be compressed by an order of magnitude (10x to 50x) while maintaining the performance benefits of the original large buffer. The authors identify a critical, previously unrecognized failure mode in existing coreset approaches: unanchored bootstrap targets. When a coreset consists of isolated, non-contiguous transitions, the bootstrap targets (the next state-action pairs) often do not exist within the coreset itself. Consequently, the value estimates for these targets are never updated by transitions in the buffer, leading to inaccurate, unanchored targets that corrupt the value function.

Methodology: Endpoint Replay

The authors propose Endpoint Replay, a method that compresses experience by maintaining a small recency buffer and a larger coreset buffer constructed from "chained" $n$-step transitions.

1. Chained $n$-Step Transitions (Anchoring)

Instead of storing isolated transitions $(s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1})$, Endpoint Replay constructs a coreset of "jumpy" transitions. As data ages out of a small recency buffer ($D_r$), it is aggregated into $n$-step sequences.

• Mechanism: A "lag buffer" accumulates $n$ transitions from the recency buffer. Once full (or upon termination), it computes the $n$-step return $G_{t,n} = \sum_{i=0}^{n-1} \gamma^i r_{t+i+1}$ and stores a single transition: $(s_t, a_t, G_{t,n}, \gamma^n, s_{t+n}, a_{t+n})$.
• Anchoring: Crucially, the endpoint $(s_{t+n}, a_{t+n})$ of one transition serves as the starting point for the next transition in the coreset. This ensures that every bootstrap target is "anchored"—it exists as a starting state in another transition within the coreset and is therefore updated during training. This eliminates the unanchored target issue found in naive coreset sampling.

2. Expectile Sarsa Update

Using $n$-step targets introduces a new challenge: pessimistic bias. In off-policy settings, $n$-step returns are computed from trajectories generated by older, potentially suboptimal policies. Standard $n$-step updates using the maximum action value ($\max_a Q$) can be overly optimistic or biased, while standard Sarsa updates (using the actual taken action $a_{t+n}$) can be pessimistic if the older policy was suboptimal.

To mitigate this, the authors introduce $n$-step Expectile Sarsa:

• Loss Function: They replace the standard squared-error loss with an expectile loss with parameter $\tau \in (0, 1)$.
• Mechanism: The expectile loss $u$ balances expected downward deviations (weighted by $1-\tau$) and upward deviations (weighted by $\tau$). By setting $\tau > 0.5$ (e.g., $\tau=0.7$), the update focuses on higher returns, effectively maximizing over the sequence of actions taken in the dataset without querying out-of-distribution actions.
• Sarsa vs. Q-Learning: The update uses the action actually taken at the endpoint ($a_{t+n}$) rather than $\max_a Q(s_{t+n}, a)$, ensuring the action is also "anchored" within the dataset distribution.

3. Algorithm Architecture

The system utilizes a two-buffer architecture:

• Recency Buffer ($D_r$): Stores the most recent $j$ transitions (e.g., 10k). Updated with standard Double DQN (DDQN) updates.
• Coreset Buffer ($D_c$): Stores the compressed $n$-step transitions (e.g., 90k). Updated with the $n$-step Expectile Sarsa loss.
• Sampling: Mini-batches are sampled with a high ratio from the recency buffer (e.g., 7:1 ratio of $D_r$ to $D_c$) to prioritize learning from fresh data while using the coreset for regularization and value propagation.

Key Contributions

1. Endpoint Replay Algorithm: A buffer compression method that pairs a small recency buffer with a coreset of chained $n$-step transitions, updated via Expectile Sarsa. It achieves performance comparable to large buffers with 10x to 50x less storage.
2. Identification of Unanchored Targets: The paper formally identifies and demonstrates that isolated coreset transitions lead to unanchored bootstrap targets, causing value function corruption. It proves that chaining $n$-step transitions resolves this by ensuring all bootstrap states are updated.
3. Theoretical Analysis of $n$-step Expectile Sarsa:
   • Formalizes $n$-step expectile action-values and proves the associated Bellman operator is a contraction, guaranteeing convergence for $n \ge 1$.
   • Proves that policy iteration converges to an optimal policy under deterministic dynamics.
   • Establishes an ordered relationship between $n$-step expectile values, showing that longer horizons yield more conservative estimates.

Experimental Results

The authors evaluated Endpoint Replay on the Pinball environment and 12 Atari 2600 games.

• Pinball: Endpoint Replay with a 50x smaller buffer (10k total vs. 500k standard) matched the performance of a large recency buffer (1M) and significantly outperformed equal-sized small buffers, reservoir-sampling coresets, and MeDQN.
• Atari 2600:
  • 10x Compression (100k buffer): Endpoint Replay outperformed equal-sized small buffers and reservoir coresets, matching or slightly exceeding the performance of a standard 1M buffer baseline.
  • 50x Compression (20k buffer): Endpoint Replay outperformed all small-buffer baselines (1-step and 10-step) and matched the large buffer performance in 5 out of 12 games.
• Ablation Studies:
  • Anchoring: Removing the chaining (unanchored states) or the action anchoring (using DDQN instead of Sarsa) significantly degraded performance.
  • Expectile Loss: Replacing the expectile loss with standard squared error (removing the bias correction) resulted in lower performance, confirming the necessity of the expectile update for $n$-step targets.

Significance and Claims

The paper claims that Endpoint Replay successfully addresses the trade-off between storage efficiency and learning performance in off-policy DRL. By identifying the "unanchored bootstrap target" issue, the authors demonstrate that simple coreset selection is insufficient for DRL. Their solution—anchoring endpoints via $n$-step chains and correcting bias via expectile losses—allows agents to retain the benefits of large buffers (long-horizon credit assignment and exploration) with a fraction of the memory footprint.

The authors note that while the method is robust to low stochasticity, the theoretical guarantee of convergence to the optimal policy holds strictly under deterministic dynamics, as the expectile loss can otherwise chase environment stochasticity rather than action sequences. The work suggests a path toward more resource-efficient DRL without sacrificing the stability and sample efficiency provided by large replay buffers.