Anchored Bellman Targets for Long-Horizon Deep Reinforcement Learning

Reinforcement learning agents that care about the far future, with a discount factor close to one, learn slowly. One reason is that every environment sample has to pass through many rounds of bootstrapping before its reward shapes the value estimate of distant states. In the optimization literature, Halpern iteration fixes a closely related problem. Halpern iteration is a way of solving an equation $T(x)=x$ in which each new iterate is a weighted average of the operator's output and a fixed "anchor" point, with the weight on the anchor shrinking over time. For the Bellman operator it provably cuts the number of iterations needed to reach a small Bellman error from roughly $1/(1-\gamma)$ scaling down to $O(1/k)$, and it still works when $\gamma=1$. So far this result lives almost entirely in planning with a known model, or in simulators that can be queried at any state. Nobody has tested it in the setting where sample inefficiency actually hurts: online deep RL with a replay buffer and a fixed number of gradient updates per environment step.

We propose a small, concrete change to how deep Q-learning builds its regression targets. Each time the target network is refreshed, the new target is mixed with a frozen "anchor" copy of the critic, using the Halpern weight $\beta_j = 1/(j+2)$. The anchor is re-snapshotted whenever a measured Bellman residual on replayed data has dropped enough. The claim is testable. At a fixed replay ratio, anchored targets should reduce the lag between the critic and the fixed point of the empirical Bellman operator. In long-horizon tasks that lag is what limits returns per environment step, so anchoring at replay ratio one should recover much of the benefit that currently requires high replay ratios and large critics. We also isolate the ingredient a skeptic will point to: anchoring toward zero is a discount-factor schedule in disguise.

Core Claim

In deep Q-learning, the natural discrete counterpart of one application of the Bellman operator is one hard target-network refresh, not one gradient step. Between refreshes, the online critic approximately regresses onto $T(Q_{\text{target}})$. Standard deep RL therefore runs an inexact version of Picard iteration $U^{k}=T(U^{k-1})$. Polyak averaging of the target, $\theta_T \leftarrow (1-\tau)\theta_T+\tau\theta$, is a Krasnosel'skiĭ–Mann relaxation, which damps each step toward the previous iterate. For average-reward and near-undiscounted problems, Optimal Non-Asymptotic Rates of Value Iteration for Average-Reward Markov Decision Processes proves that this relaxed scheme reaches only $O(1/\sqrt{k})$ Bellman error, while the anchored scheme reaches $O(1/k)$ and matches a lower bound up to a constant.

We replace the regression target with

$$y(s,a) = \beta_j\, Q_A(s,a) + (1-\beta_j)\big(r + \gamma\, Q_T(s', a')\big),$$

where $Q_A$ is a frozen anchor critic, $Q_T$ is the target critic, $a'$ is the greedy or policy action at the next state $s'$, and $j$ counts target refreshes since the anchor was last set. Planning results say this reaches small Bellman error in far fewer refreshes. We claim this reduction survives stochastic replay minibatches and function approximation well enough to improve return per environment step when $\gamma \geq 0.99$. We expect the benefit to shrink toward zero at short horizons, where contraction is already fast; that is also a falsifiable prediction.

Two design choices separate the proposal from a literal port of the theory. First, the anchor is a restarted snapshot of the critic, not the random initialization. The restart is triggered when the empirical Bellman residual on a held-out replay batch falls below a fixed fraction of its value at the last restart. We borrow this residual-based, parameter-free stopping idea from SAVIA+ in Near-Optimal Sample Complexity for MDPs via Anchoring. Second, anchoring operates on the targets, that is in function space, not on parameters. The parameter-space rule $\theta_T = \beta_k\theta_0+(1-\beta_k)\theta$ listed as an open direction in the research file has no reason to produce a meaningful value function, because averaging network weights does not average the functions they compute.

Relation to Prior Work

Three papers supply the method and its guarantees. Accelerating Value Iteration with Anchoring introduces Anchored Value Iteration and proves $O(1/k)$ Bellman error with robustness to inexact updates. It also names model-free Q-learning as open and reports that distance to the optimal value can be worse than plain VI by a constant factor. Optimal Non-Asymptotic Rates of Value Iteration for Average-Reward Markov Decision Processes extends the guarantee to multichain average-reward problems, again with a known model. Near-Optimal Sample Complexity for MDPs via Anchoring achieves $\tilde O(|S||A|\|h^*\|_{sp}^2/\epsilon^2)$ sample complexity by combining anchoring with recursive variance reduction. That result requires a generative model and does not address function approximation.

Stochastic Halpern iteration in normed spaces and applications to reinforcement learning gives model-free guarantees, but only with minibatch sizes that grow very quickly and a sample complexity of order $\epsilon^{-7}$. It warns that naive stochastic Halpern iteration is impractical. We take that warning as a constraint on the design. We never grow batches. Instead we rely on the replay buffer and a many-step regression between refreshes to average out noise, and we test directly whether that is enough.

On the deep RL side, three works set the bar and the shape of the comparison. Bigger, Regularized, Optimistic (BRO) gets its sample efficiency from a critic of about 5M parameters, high replay ratios, layer normalization and periodic resets. We ask whether a change to the operator can buy part of that gain without the extra compute and latency. Bridging the performance-gap between target-free and target-based reinforcement learning (iS-QL) shares the feature network and freezes only the linear output layer, which cuts target-network memory. Our anchor adds a second frozen copy, so we reuse the iS-QL trick and anchor only the output head. Frictional Q-Learning treats a different failure mode, overestimation off the data manifold. It supplies a strong continuous-control reference number, but it is not our mechanism.

Research Program

The work has three parts, each feeding the next.

The first part is a controlled tabular study, where the Bellman residual and the true error $\|Q-Q^*\|_\infty$ can both be computed exactly. We generate random communicating and multichain MDPs and chain-like MDPs whose effective horizon is long. We run online Q-learning with a replay buffer and a fixed number of updates per environment step, under four target rules: hard refresh (Picard), Polyak (KM), anchored with a fixed anchor, and anchored with residual-triggered restarts. We record residual, true error and greedy-policy value against environment samples.

This study answers the tension raised in Accelerating Value Iteration with Anchoring about whether faster residual decay translates into better policies, or whether the constant-factor slowdown in solution distance dominates. We will also prove a modest extension of the inexact Anc-VI analysis. It covers restarts and per-refresh regression error $\varepsilon$, and shows that after $k$ refreshes the residual is bounded by a $O(1/k)$ term plus a term proportional to $\varepsilon$. The $1/k$ term comes from the Halpern rate and the $\varepsilon$ term from the inexact-update analysis. We then count environment samples by tying refreshes to the replay ratio.

The second part is the deep RL algorithm itself. Anchored DQN adds the anchor-mixed target to a standard DQN with periodic hard target updates. Anchored SAC applies the same rule to the soft Bellman target, with the anchor restricted to a frozen copy of the output head as in iS-QL. The only new hyperparameter is the restart threshold. The schedule $\beta_j$ is fixed by the theory, not tuned.

The third part is diagnosis. We ask whether any gains come from faster fixed-point solving, as claimed, or from an implicit reduction in effective horizon. To separate the two, we measure the empirical residual on held-out replay and the value error against Monte Carlo returns along evaluation rollouts.

Baselines

The naive reference point is the unmodified base agent with its standard target rule: DQN with hard target refreshes on Atari, SAC with Polyak averaging on MuJoCo and the DeepMind Control Suite (DMC). All of these run at replay ratio one with the same network, optimizer and discount factor. Any anchored agent that fails to beat this baseline at $\gamma \ge 0.99$ refutes the core claim.

The strongest existing competitor for sample efficiency in continuous control is BRO (Bigger, Regularized, Optimistic). It is the strongest because it attacks the same symptom, slow value learning per sample, by spending more gradient steps and parameters per sample. BRO reports solving DMC Dog and Humanoid within 1 million environment steps, over 85% of maximal returns on DMC, and about 2.5x better sample efficiency than TD-MPC2.

We will not claim to beat full BRO outright at equal compute. The fair comparison is instead at matched gradient updates and wall-clock time. Anchored SAC at replay ratio one is compared against SAC and BRO-style agents at replay ratios one, two and four. The same number of environment steps, seeds and hyperparameter search budget apply to every arm; we allot the same number of tuning trials to the Polyak coefficient and to the anchor restart threshold. A second arm adds anchoring on top of BRO itself, to test whether the effects compound.

Beating the baseline means one of two results. Either anchored replay-ratio-one matches the area under the learning curve of Polyak at replay ratio two or higher on long-horizon tasks, or anchoring added to BRO improves its area under the curve at equal compute.

For discrete control, the reference is iS-DQN from Bridging the performance-gap between target-free and target-based reinforcement learning. It reports a 6% improvement in area under the curve over target-based DQN on 15 Atari games, so anchored DQN should exceed that margin on the same games.

For MuJoCo Humanoid-v4, the reported numbers are about 6437 average return for FQL, about 5682 for SAC and about 5373 for TD3 (Frictional Q-Learning). These serve as calibration points, and we will reproduce SAC in our own code rather than compare to the quoted figures.

Two ablations isolate the key ingredient. The zero-anchor ablation sets $Q_A \equiv 0$, which makes the target $(1-\beta_j)(r+\gamma Q_T)$: exactly a schedule that grows the effective discount and rescales rewards. The discount-schedule ablation instead runs a plain agent with $\gamma_{\text{eff}}=(1-\beta_j)\gamma$ and restarts on the same trigger. If snapshot anchoring does not beat both, the Halpern interpretation adds nothing beyond a discount curriculum. A third ablation removes the restarts, anchoring once to the initialization, to test whether the snapshot and its refresh are what make the method work under function approximation.

Why not just…?

Why not just use Polyak averaging, which already damps target updates? Polyak averaging is a Krasnosel'skiĭ–Mann relaxation, which damps each update toward the previous iterate. In average-reward planning it reaches only $O(1/\sqrt{k})$ Bellman error, against $O(1/k)$ for anchoring (Optimal Non-Asymptotic Rates of Value Iteration for Average-Reward Markov Decision Processes). In stochastic normed spaces its known last-iterate rate is also worse, $\epsilon^{-6}$ against $\epsilon^{-5}$ (Stochastic Halpern iteration in normed spaces and applications to reinforcement learning). Those are planning or worst-case results, so they do not settle the deep-RL question. The tabular study with exact residuals, and the matched-tuning Polyak arm in the deep experiments, test it directly.

Why not just anneal the discount factor upward? This is the most serious threat. With a zero anchor, Halpern targets are algebraically a rising discount schedule with rescaled rewards. If our gains came only from starting with a short horizon, then a well-tuned discount curriculum would match them. The two dedicated ablations are designed to expose exactly that. We commit to reporting the outcome either way. If snapshot anchoring gives no advantage over the matched discount schedule, the honest conclusion is that deep RL should use discount curricula, and the anchoring interpretation adds nothing in practice.

Why not just raise the replay ratio and enlarge the critic, as BRO does? That works, but it multiplies gradient computation per sample and, through the larger critic, adds inference latency, which is a problem for high-frequency control. Anchoring changes the target rule and costs one frozen output head. The matched-compute comparison shows whether anchoring buys a comparable gain more cheaply. If it does not, the anchoring-on-top-of-BRO arm shows whether it is at least complementary. If neither holds, anchoring is not worth adopting in continuous control.

Why not just use shared-head targets or BRO's periodic resets? iS-QL removes target-network memory and lag but, by its own framing, does not change the operator's convergence rate. BRO's resets discard parameters to restore plasticity rather than to speed up fixed-point solving. Our residual-triggered anchor restart is superficially similar to a reset, but it keeps the current critic as the anchor instead of reinitializing. We report anchor-restart timing next to BRO's reset schedule and include a variant that resets without anchoring, to separate the two effects.

Proposed Experiments

The decisive tabular experiment plots Bellman residual, true value error and greedy-policy value against environment samples for $\gamma \in \{0.9, 0.99, 0.999\}$ and for multichain average-reward MDPs, comparing the Picard, KM, fixed-anchor and restarted-anchor target rules. The prediction is a clear gap in favor of anchoring at $\gamma \ge 0.99$ that vanishes at $\gamma=0.9$, with policy value following the residual rather than the constant-factor worse distance bound. No reported result exists on Lacuna for online anchored Q-learning, so this experiment establishes the first one.

The deep continuous-control experiments use Gymnasium MuJoCo (Humanoid-v4, Walker, Ant) and the DMC hard tasks (Dog, Humanoid), which are the benchmarks used by BRO, iS-QL and FQL. We run $\gamma \in \{0.99, 0.995, 0.999\}$ and report return, area under the curve at 1M steps and wall-clock time, averaged over at least ten seeds. The discrete experiments use the same 15-game Atari protocol as iS-QL, with area under the curve relative to DQN as the metric.

Across all benchmarks, the empirical residual on held-out replay and the Monte Carlo value error are logged, so that each gain in return can be attributed to faster residual reduction or ruled out as due to it.

The proposal is judged successful only if three conditions hold together. Anchored agents at replay ratio one must reach the area under the curve of the Polyak baseline at replay ratio two or more on long-horizon tasks. Snapshot anchoring must beat both the zero-anchor and discount-schedule ablations. The advantage must grow as $\gamma \to 1$. If any one condition fails, the result is informative: it tells the field whether the Halpern acceleration proved in planning carries over to deep RL, or reduces in practice to horizon shaping.