RETD: fixing emphatic TD when the stepsize is constant

Two states are enough. Regularized Emphatic Temporal-Difference Learning: Stability under Constant Stepsizes, published on arXiv on 18 September, builds an ergodic two state chain in which emphatic temporal difference learning (ETD) contracts in its mean map while, at the same time, the sampled matrix product has a positive top Lyapunov exponent. Put plainly: the algorithm converges in expectation and diverges when it actually runs, with samples and a constant learning rate.

ETD was proposed to stabilize the expected off-policy TD update and to change its projection geometry. The paper's thesis is that neither of those two properties determines the constant stepsize sampled dynamics, which is precisely the regime that runs in production: almost nobody trains with diminishing stepsizes, but with a fixed learning rate across millions of updates.

The classic context is the so called deadly triad: bootstrapping, off-policy learning and function approximation. When the three coincide, the TD update can diverge, and ETD is one of the accepted answers to that problem. What this work adds is that the answer was validated mostly at the level of expectation, leaving uncovered the regime where almost everyone trains.

The counterexample and the follow-on trace

The subtle part of the argument lies in separating two causes that are often conflated. ETD destabilizing under a constant stepsize could simply be blamed on the infinite variance of the follow-on trace, a documented problem of the method. The authors use a regenerative cycle analysis to show that the sign of the Lyapunov exponent is independent of that variance: the sampled product blows up because of its own structure, not because of the heavy tail of the trace. That distinction changes the kind of fix you need to look for.

What RETD does

RETD (regularized emphatic TD) is described as a normalized first order post shock repair. It leaves the trace and the importance ratios untouched, stores the emphatic TD signal in a leaky scalar state and later releases a delayed correction. RETD's raw equilibrium is an affine shift of the ETD equilibrium, and the single and two regularization readouts recover the ETD fixed point exactly. In other words: the target is not touched, only the dynamics of the path toward it. For anyone who already has an ETD implementation that matters, because it does not force a rewrite of the estimator.

What is proven and what is numerical

The paper proves almost sure convergence with harmonic diminishing stepsizes and a conditional constant stepsize moment contraction result, supported by a bound on Markovian random products. RETD obtains certified negative exponents on the two state construction and on one Baird point, the reference case for off-policy divergence. The authors themselves mark the limit: the positive Baird ETD sign remains numerical, not proven. They accompany the analysis with paired 10,000 run experiments, although the abstract circulating in the cs.AI listings on arXiv is truncated at that point.

Who this is useful for

For teams training off-policy policies with importance ratios and function approximation, especially if they validate stability with the expectation analysis and then train with a constant stepsize. Also for anyone auditing iterative stochastic loops: the general lesson is that contraction of the mean map does not certify the stability of the sampled product, and that gap is invisible in a smoothed loss curve. The work is theoretical and ships with no reference implementation, so for now it reads more like a validation criterion than a library to install.

We are less interested in RETD as a specific algorithm than in the habit it proposes: check the exponent of the sampled product before calling an off-policy method stable. It is a cheap check and, given the counterexample, hardly redundant.