Hypergradient Replay Without the Sparsity Trap

Off-policy reinforcement learning agents store past experience in a replay buffer and train on random samples from it. Which samples they replay largely decides how many environment interactions they need. An appealing idea is to learn the replay distribution: treat the weight on each stored transition as a parameter, and adjust it so that the agent's next update most improves performance on its freshest experience. This is a bilevel problem, meaning an outer optimization (choosing replay weights) whose objective depends on the result of an inner optimization (the agent's gradient step on the weighted batch). It also has a known failure mode. When sample weights on a probability simplex are learned jointly with the model, the weights provably collapse onto at most $p$ samples, where $p$ is the model's feature dimension. The only known remedy is slowing the outer updates by roughly 1000x (A Challenge in Reweighting Data with Bilevel Optimization). For a replay buffer of $10^6$ transitions and a critic with a 256-unit last layer, that collapse would throw away almost everything the agent has collected.

This note proposes to test whether that collapse actually happens in reinforcement learning replay, and to break it with a specific fix. The fix is to compute the replay hypergradient cheaply, as a first-order one-step lookahead, and to feed it into a small amortized scorer. Instead of storing a free weight per transition, the scorer maps a handful of transition features to a sampling priority. The core bet is that the collapse comes from per-sample weights receiving a gradient that lives in a $p$-dimensional subspace, and that routing the same signal through a low-parameter scorer removes the mechanism without resorting to slow outer updates. If the bet holds, the result is a replay rule that uses the correct nested gradient signal, keeps a broad replay support, and needs fewer environment steps than hand-designed priorities.

Core Claim

Consider a critic with last-layer features $\phi_i \in \mathbb{R}^p$ for transition $i$ and temporal-difference (TD) error $\delta_i$, the gap between the critic's prediction and its bootstrapped target. After one inner step with learning rate $\eta$ on a weighted batch, the change in a validation loss $L_{\text{val}}$ with respect to the weight $w_i$ is, to first order,

$$\frac{\partial L_{\text{val}}}{\partial w_i} \approx -\eta\, \langle g_{\text{val}}, \nabla \ell_i \rangle = -\eta\, \delta_i \langle g_{\text{val}}, \phi_i \rangle ,$$

where $g_{\text{val}}$ is the gradient of $L_{\text{val}}$ with respect to the last-layer weights and $\ell_i$ is the TD loss of transition $i$. Here $L_{\text{val}}$ is the TD loss on a small held-out batch of the most recent transitions. The vector of these hypergradients across $N$ buffer entries lies in the span of $p$ feature directions. This low-rank structure is what Ivanova and Ablin identify as the driver of the collapse. We therefore predict that per-sample mirror-descent replay weights in deep RL will concentrate on roughly $p$ transitions, and that the size of the support will scale with critic width.

We also claim that a scorer $s_\psi$ with a few dozen parameters, trained on the same hypergradient, will not show this collapse at normal outer learning rates. The scorer reads reward, $|\delta_i|$, age, and the alignment term $\delta_i\langle g_{\text{val}},\phi_i\rangle$, and replay probabilities are $\mathrm{softmax}(s_\psi/\tau)$ over the buffer with temperature $\tau$. The reason is that the scorer's gradient averages over all transitions that share features, rather than pushing individual simplex vertices. We further claim that this scorer reaches returns at fixed environment budgets that match or beat the heuristic and learned-replay competitors.

Relation to Prior Work

Two papers motivate the gap. Experience Replay Optimization learns a replay policy from reward, TD error, and age, but trains it with REINFORCE on the change in evaluation return. It treats the agent update as a black box, and its signal is high variance and delayed. We keep its feature-based scorer design and replace the black-box signal with a differentiated one-step hypergradient. Its finding that useful replay often prefers low TD error transitions is a prediction our alignment feature should reproduce. A Deeper Look at Experience Replay shows that uniform replay degrades as buffers grow from $10^2$ to $10^6$, because informative transitions get diluted. Its Combined Experience Replay (CER), which forces the newest transition into each batch, is a strong cheap fix. Our proposal targets the historical $N-1$ samples that CER still draws uniformly.

One paper constrains the design. A Challenge in Reweighting Data with Bilevel Optimization proves the sparsity trap for warm-started single-loop reweighting and shows it on MNIST data cleaning, where the model ended up training on a single point. Its analysis is supervised and uses a fixed dataset. An RL buffer differs in that it churns, its targets move, and its data comes from a changing policy. Those differences could either soften or worsen the trap, and nobody has checked.

Other work supplies the method. Meta-SAC shows that differentiating through a single actor step to tune a scalar temperature is stable and useful. We apply the same one-step lookahead to the replay distribution, and restrict it to the critic's last layer to avoid second-order cost. The single-timescale actor-critic results of Optimal Sample Complexity for Single Time-Scale Actor-Critic with Momentum found that a small uniform sliding buffer is enough to smooth non-stationarity in the tabular setting. They explicitly left open whether that buffer should be optimized, and our choice of a "freshest transitions" validation set borrows their buffer design.

We deliberately do not pursue the bilevel RL work on reward learning, PARL, On the Sample Complexity Bounds of Bilevel Reinforcement Learning, and Hypergradient-based Bilevel Reinforcement Learning with Improved Sample Complexity. Those papers put the reward model in the outer level. Here the outer variable is the data distribution, and the question is empirical and dynamical rather than a convergence rate.

Research Program

The work has three parts. The first is a diagnostic. We implement per-sample replay weights on the simplex, updated by mirror descent with the first-order hypergradient above, inside Soft Actor-Critic (SAC). We then measure the effective support $\exp(H(w))$, where $H(w)$ is the entropy of the replay distribution, over training. Three knobs are varied: critic last-layer width $p \in \{64, 256, 1024\}$, buffer size from $10^3$ to $10^6$, and outer learning rate. The theory makes a sharp prediction: if the trap transfers, the plateau of effective support should track $p$, not buffer size. If it does not transfer, that is itself a publishable negative result about how buffer churn interacts with bilevel reweighting.

The second part is the amortized scorer described in the Core Claim. The hypergradient is backpropagated into $\psi$ through the softmax. Priorities are recomputed lazily on sampled candidates rather than over the whole buffer, so the cost stays close to that of prioritized replay. We analyze why the scorer escapes the trap in the linear-critic case: its gradient is a feature-weighted average of per-sample hypergradients, so the number of distinct "vertices" it can concentrate on is bounded by how finely the scorer partitions feature space, not by $p$. We then check whether temperature $\tau$ is the only thing preventing collapse, or whether the amortization itself matters.

The third part is an evaluation of sample efficiency, described below, on standard continuous-control benchmarks and on sparse-reward variants where dilution should matter most.

Baselines

The naive reference is SAC with uniform replay over a $10^6$ buffer. Every method must beat it at matched environment steps, or the exercise is pointless.

The cheapest serious heuristic is CER from A Deeper Look at Experience Replay, plus prioritized experience replay (PER) by TD error. CER is the strongest cheap competitor on the dilution problem specifically, because it guarantees that new information is used at a cost of $\mathcal{O}(1)$. We run both on the same SAC backbone, with their priority exponent or recency settings tuned over the same number of trials as our temperature and outer learning rate.

The strongest learned competitor is ERO from Experience Replay Optimization. It is the only existing learned replay policy in this setting and uses the same feature family, so a win over it isolates the value of a differentiated signal over REINFORCE. We reimplement it on SAC rather than its original DDPG so that the backbone is shared, and give it the same scorer architecture and tuning budget. The file reports that ERO "consistently outperformed both vanilla DDPG and PER variants" on eight MuJoCo tasks, but no reported numerical return was found on Lacuna for ERO, CER, or PER. We will therefore rerun all of them rather than quote figures. For context only, Meta-SAC reports outperforming SAC-v2 by more than 10% on Humanoid-v2, which indicates the scale of gain that one-step metagradients have delivered on this suite. Beating ERO means higher return at 300k and 1M steps, or fewer steps to a fixed return threshold, with non-overlapping 95% bootstrap intervals over at least ten seeds on a majority of tasks.

Two ablations isolate the key ingredient. The first is per-sample simplex weights with the same hypergradient, which is the configuration expected to fall into the trap. The second is the amortized scorer with the alignment feature removed, which leaves an ERO-style scorer trained by hypergradient on reward, TD error, and age only. The first ablation tests whether amortization is what prevents collapse. The second tests whether the hypergradient-alignment feature carries information that the heuristics lack.

Why not just…?

Why not just use CER or PER? They may be enough on dense-reward locomotion. That is exactly why they are primary baselines and not strawmen. The evidence against their sufficiency is that CER leaves historical sampling uniform, and that ERO found TD-error priority to be the wrong direction in many states. The sparse-reward variants and the buffer-size sweep are designed to separate them from our method. If CER matches us there too, we will say so, and the contribution reduces to the sparsity-trap diagnostic.

Why not just mix learned weights with a uniform distribution, or add an entropy penalty? This is the most serious threat. It trivially guarantees broad support, and it is the obvious move Ivanova and Ablin left unexplored. It may also work as well as the scorer. So we run per-sample weights plus uniform mixing and per-sample weights plus a KL-to-uniform penalty as full competitors, each tuned over the same budget. The distinguishing prediction is that mixing buys breadth by diluting the signal: to keep the support above $p$, its mixing coefficient must be large enough to wash out the gains. The amortized scorer should keep both breadth and gains. If the mixing curves match the scorer's, we adopt the simpler method and report that.

Why not just keep ERO's REINFORCE signal, or slow down the outer learning rate? Slowing the outer rate is the documented fix, but it costs roughly 1000x in convergence speed on MNIST (A Challenge in Reweighting Data with Bilevel Optimization), and a replay distribution that adapts that slowly cannot follow a moving policy. We include a slow-rate per-sample run to measure what that costs in RL. REINFORCE avoids the low-rank gradient structure, but it pays for this in variance. The "hypergradient scorer versus ERO" comparison under an identical scorer architecture settles which signal is better.

Proposed Experiments

We use SAC on OpenAI Gym MuJoCo Hopper, Walker2d, HalfCheetah, Ant, and Humanoid, and on DeepMind Control Walker-walk and Cheetah-run. These are the suites used by ERO, Meta-SAC, and the bilevel RL papers. We add sparse-reward versions that reward only reaching a velocity or height threshold, and Lunar Lander for the $10^2$ to $10^6$ buffer sweep of Zhang and Sutton. Metrics are return at 100k, 300k, and 1M steps, area under the learning curve, steps to threshold, effective replay support $\exp(H)$, and wall-clock overhead relative to uniform replay. The overhead target is under 30%.

Two checks are decisive. The first is whether per-sample hypergradient weights in SAC show effective support that plateaus near $p$ and moves with critic width. That result confirms that the trap transfers to RL and justifies the whole design; its absence redirects the work toward explaining why buffer churn prevents it. The second is whether the amortized scorer keeps its support orders of magnitude above $p$ at the same outer learning rate while beating CER, ERO, and uniform mixing on the sparse-reward tasks at matched steps. If the scorer only ties uniform mixing, the honest conclusion is that the RL sparsity trap is real but cheaply fixed, and we would report that.