Regularized Emphatic Temporal-Difference Learning: Solving the Stability Puzzle Under Constant Stepsizes

A Hidden Problem in Reinforcement Learning

In off-policy reinforcement learning, Temporal-Difference Learning (TD) is one of the core methods for estimating value functions. However, when the behavior policy differs from the target policy, standard TD algorithms can diverge. Emphatic TD (ETD) was proposed to stabilize the expected values of off-policy TD updates and modify the geometry of their projections.

This study published on arXiv (arXiv:2609.19170v1) identifies a previously overlooked critical issue: while ETD can stabilize updates in expectation, expected stability does not determine sampling dynamics under constant stepsizes. In other words, even if an algorithm converges "on average," the actual sampling process may still be unstable.

Off-policy learning and importance sampling: The central challenge of off-policy reinforcement learning is that the behavior policy used to collect data differs from the target policy the agent wishes to optimize. To correct for this distributional shift, algorithms typically introduce importance sampling ratios to reweight updates. However, these ratios can accumulate over time steps, producing extremely high variance that causes the learning process to oscillate wildly. ETD addresses this by introducing "emphasis weights" that redistribute the importance of updates across states, geometrically altering the projection direction of TD learning so that the off-policy updates correspond to a contraction operator in expectation. This design was originally motivated by the famous "deadly triad" problem — the potential divergence of TD when function approximation, bootstrapping, and off-policy training are all present simultaneously. The meaning of Lyapunov exponents: The top Lyapunov exponent measures the long-run average exponential growth rate of errors in a linear stochastic iterative system. A positive value means the iteration diverges exponentially; a negative value means stable contraction. It captures the asymptotic behavior of "typical trajectories" rather than a single worst case, making it more suitable than the spectral radius for characterizing the stability of random matrix products.

A Counterexample That Exposes the Contradiction

The research team constructed an ergodic two-state counterexample that clearly demonstrates this contradiction. In this example, ETD's mean map exhibits contractive behavior — theoretically implying convergence — yet the sampled products have a positive top Lyapunov exponent, meaning the actual iterative process diverges.

The root cause lies in the infinite variance of the follow-on trace. The authors use a regenerative-cycle analysis to decouple the sign of the Lyapunov exponent from the infinite variance of the follow-on trace, demonstrating that these are distinct problems requiring separate treatment. This analysis provides a new theoretical perspective for understanding the destabilization mechanism of ETD.

The follow-on trace is the core auxiliary variable in ETD, used to accumulate discounted visit-frequency correction terms. Its recursion takes the form $F_{t+1} = \gamma \rho_t F_t + 1$, where $\rho_t$ is the importance sampling ratio and $\gamma$ is the discount factor. In off-policy settings, when $\rho_t$ fluctuates significantly, the multiplicative form of $F_t$ causes its variance to grow without bound over time steps — the "infinite variance" phenomenon. This is analogous to the classical problem of non-existing moments in heavy-tailed distributions: the sequence's mean may be finite and stable, while its second and higher moments diverge. Regenerative-cycle analysis is a classical tool from probability theory for analyzing the long-run behavior of Markov chains: by identifying "regeneration times" (moments when the chain returns to a particular state), it decomposes an infinitely long trajectory into independent, identically distributed cycle segments, reducing asymptotic statistics to finite expectations within a single cycle. This paper uses this framework to decouple the sign of the Lyapunov exponent from the variance properties of the follow-on trace, proving that the two can independently exhibit stable or unstable behavior — laying the theoretical groundwork for designing targeted fixes for each.

RETD: A Regularization-Based Fix

To address these issues, the paper proposes Regularized Emphatic TD (RETD). Its core idea is a normalized first-order post-shock repair mechanism with several key properties:

• Preserves traces and importance ratios: RETD leaves the follow-on trace and importance sampling ratios untouched, avoiding the introduction of additional bias;
• Leaky scalar state for storing signals: The emphatic TD signal is stored in a leaky scalar state;
• Delayed release of corrections: A delayed mechanism releases the correction signal, thereby stabilizing post-shock dynamics.

The recovery of the fixed point deserves particular attention. RETD's natural equilibrium is an affine shift of ETD's equilibrium, and through single- and two-regularization readouts, ETD's fixed point can be exactly recovered. This means RETD strikes a balance between stability and solution correctness — repairing the dynamic instability without sacrificing the target solution of the original algorithm.

The intuition behind the post-shock repair mechanism: In stochastic iterative systems, the sequence of parameter updates can be viewed as a product of random matrices. When an extreme importance sampling ratio occurs at a given time step, it acts like a "shock" to the system, causing parameter values to deviate dramatically. Rather than preventing the shock, RETD's approach is to slowly release a correction signal through an auxiliary scalar state after the shock, smoothly amortizing the excessive update over multiple subsequent time steps. The term "leaky" describes the fact that this scalar state gradually decays to zero at a certain rate — analogous to a capacitor discharging — thereby preventing unbounded accumulation of historical shock signals. Affine shift and fixed-point recovery: Regularization typically changes an algorithm's fixed point — for example, L2 regularization shifts the optimal solution toward the origin. The regularization term introduced by RETD shifts its natural equilibrium to an affine (linear + constant) transformation of ETD's fixed point, rather than the original fixed point. The paper applies a corresponding inverse transformation at the readout stage (single or double regularization readout) to precisely cancel this shift, ensuring unbiased solutions while gaining stability — avoiding the common stability-accuracy tradeoff.

Theoretical Guarantees and Experimental Validation

On the theoretical side, the paper provides two types of convergence results:

1. Almost-sure convergence under diminishing stepsizes: For harmonic diminishing stepsizes, almost-sure convergence of RETD is proven;
2. Conditional moment contraction under constant stepsizes: Based on a Markovian random-product bound, a conditional constant-stepsize moment contraction result is established.

In terms of specific constructions, RETD achieves certified negative Lyapunov exponents (i.e., stability) on both the two-state counterexample and a Baird point, while the positive exponent sign for ETD in the Baird counterexample currently remains at the numerical level.

On the experimental side, the study conducts paired 10,000-run comparisons validating several findings: the existence of the two separation phenomena, exact fixed-point recovery, a nonmonotone stability region, and task dependence.

Scope and Significance of the Method

The paper also candidly identifies RETD's limitations: it modifies post-shock dynamics but does not reduce the shared follow-on trace variance. This echoes the earlier regenerative-cycle analysis — the infinite variance of the follow-on trace is a separate problem, and RETD addresses the sign of the Lyapunov exponent, not the variance.

The value of this work lies in clarifying two concepts that have long been conflated in off-policy TD learning: stability in expectation versus stability in sampling. For reinforcement learning theorists, this distinction enables more precise analysis of algorithmic behavior in real-world deployments; for algorithm designers, RETD offers a practical approach to enhancing stability without compromising existing theoretical guarantees.

The discovery of a nonmonotone stability region and task dependence also reminds practitioners: when using ETD-type algorithms, stepsize selection requires greater care, and naively relying on expected convergence may lead to unexpected divergence.