Regularized Emphatic Temporal-Difference Learning: Stability under Constant Stepsizes
Authors: Xingguo Chen, Zhaohui Wu, Jinguo Ye, Chao Li, Shangdong Yang, Guang Yang, Skylar Liang, Wenhao Wang
Organizations: Jiangsu Key Laboratory of Big Data Security & Intelligent Processing, Nanjing University of Posts & Telecommunications, Nanjing 210023, China · Nanjing University, 163 Xianlin Avenue, Nanjing 210023, China · Microsoft Corporation, One Microsoft Way, Redmond, WA 98052, USA · College of Electronic Countermeasure, National University of Defense Technology, Hefei 230037, China
Emphatic temporal-difference learning (ETD) stabilizes the expected off-policy TD update and changes its projection geometry, but neither property determines constant-stepsize sampled dynamics. We construct an ergodic two-state counterexample in which the ETD mean map contracts while the sampled product has a positive top Lyapunov exponent. Regenerative-cycle analysis separates this sign from the infinite variance of the follow-on trace. We introduce regularized emphatic TD (RETD), a normalized first-order post-shock repair that leaves the trace and importance ratios unchanged, stores the emphatic TD signal in a leaky scalar state, and releases a delayed correction. RETD's raw equilibrium is an affine shift of the ETD equilibrium; single- and two-regularization readouts recover the ETD fixed point exactly. We prove almost-sure convergence for harmonic diminishing stepsizes and a conditional constant-stepsize moment-contraction result from a Markovian random-product bound. RETD has certified negative exponents on the two-state construction and one Baird point, whereas the positive Baird ETD sign remains numerical. Paired 10,000-run experiments validate both separations, fixed-point recovery, a nonmonotone stability region, and task dependence. RETD changes post-shock dynamics; it does not reduce the shared follow-on-trace variance.
Figures & tables
Figure 1: The new two-state counterexample. Action aπ sends either state to s2 , whereas a0 sends either state to s1 . The target policy always chooses aπ and the behavior policy chooses aπ with probability .3 . Solid blue and dashed gray arrows distinguish the two actions and remain legible in grayscale.
L
P(L)
upper bound on P(L)log∥ML∥S
0
7/10
−0.000919795298289812
1
21/100
−0.035635247962602710
2
63/1000
−0.029235245805596898
3
189/10000
−0.026797225126525312
4
567/100000
−0.002112080306350725
5
1701/1000000
−0.005207967408664208
Table 1: Finite prefix of the two-state RETD cycle certificate. The cycle matrices are rational; only outward-rounded logarithmic bounds are printed.
Figure 2: Baird’s seven-state counterexample. The behavior policy uses the blue solid transition with probability 1/7 and otherwise uses the dashed uniform-to-upper transition. The dashed arcs denote the common kernel from every state.
Method
Mean-map radius
Top-exponent estimate
Rigorous sign
ETD
0.99428571
0.00138528±0.00008328
numerical only
RETD ( c=0.5 )
0.99752059
−0.00143906±0.00006106
λR≤−10−4
Table 2: Baird comparison at α=0.01 . Mean radii are deterministic. Exponent estimates are means plus/minus sample standard deviations over ten independent runs. The RETD negative sign has the uniform cycle certificate in Proposition 6 ; the ETD positive sign remains numerical.
Figure 3: Training curves on the two counterexamples over 10,000 independent paired runs. Curves are mean cumulative log-amplification Gt ; bands are one sample standard deviation. The green half-plane Gt<0 means contraction and the red half-plane Gt>0 means expansion. Both axes are linear. ETD and RETD use the analyzed settings; the remaining methods use configurations selected on independent validation trajectories.
Figure 4: Baird regularization path on linear axes. Panel (a) reports the sample-path exponent and panel (b) the deterministic mean-map margin; negative values denote stability.
Figure 5: Finite-time path-exponent map over one common Baird-family grid. Blue cells have negative exponents and contract; red cells have positive exponents and expand. Black curves mark the zero boundary, stars mark the canonical Baird point, and open squares are independent boundary checks. The in-panel count reports expanding cells out of 225. All mean systems on this grid are positive stable, so the color changes show changes in the sample-path exponent.
Figure 6: Absolute prediction error after tail averaging over 10,000 paired runs. Points are means and bars are one sample standard deviation; lower is better. Raw RETD retains the predicted c -dependent shift, whereas the single- c and two- c readouts return to the ETD error scale. The ordinate is linear.
Figure 7: Learning curves on Boyan’s chain and three representations of the off-policy random walk. Curves are mean RMS value error over 10,000 independent held-out runs; bands are one sample standard deviation. Lower is better, both axes are linear, and no temporal smoothing is applied.
Family
Modified object
Relation to RETD
GTD/GTD2/TDC/
TDRC
Gradient correction with an auxiliary vector
Targets an ordinary projected or MSPBE-related system; it is not an emphatic shock-state modification and does not use the RETD recovery identity
Generalized, PER, learned ETD, and TETD
Emphasis or trace pathway
Changes how emphasis is weighted, estimated, or truncated; RETD leaves Ft and ρt unchanged
V-trace and ratio clipping
Ratios or the effective operator
Changes the sampled ratios or target operator, whereas RETD changes the joint post-shock product
RETD
Scalar leaky post-shock state
Affine-shifted system with exact ETD recovery, diminishing-stepsize convergence, and conditional constant-stepsize path stability
Table 3: Related off-policy methods grouped by the component they modify.