On Convergence of Gradient Temporal-Difference Learning with Regularized Corrections and Eligibility Traces

Jingyi Jin; Martha White; Hao Wang

cs.LGNov 4, 2026

On Convergence of Gradient Temporal-Difference Learning with Regularized Corrections and Eligibility Traces

Authors: Jingyi Jin, Martha White, Hao Wang

Organizations: Department of Mathematical and Statistical Sciences Interdisciplinary Lab for Mathematical Ecology and Epidemiology University of Alberta Edmonton, Alberta, Canada · Department of Computing Science University of Alberta and the Alberta Machine Intelligence Institute (Amii) Edmonton, Alberta, Canada

Abstract

Temporal-difference (TD) learning underlies many prediction and control algorithms, but can diverge when combined with off-policy learning, bootstrapping, and function approximation. TD with Regularized Corrections (TDRC) is theoretically sound and practically simple, but existing convergence theory covers only the one-step case under i.i.d. sampling, while the Huber Bellman-error formulation has not been extended to TDRC or eligibility traces. In this work, we establish convergence of constrained TDRC( $λ$ ) with diminishing stepsizes and non-i.i.d. off-policy data, for state-dependent and history-dependent $λ$ -parameters. We also propose TDRC( $λ$ )-Huber, which preserves the TDRC( $λ$ ) fixed point while reducing sensitivity to large Bellman errors. For both algorithms, we apply an ODE-based weak-convergence method from stochastic approximation theory. For the nonlinear mean dynamics of TDRC( $λ$ )-Huber, we give an integral small-gain condition that guarantees uniqueness and global asymptotic stability of the target equilibrium. We then establish convergence of the constrained algorithm, derive computable sufficient conditions for convergence, and identify a regularization-based convergence mechanism shared by linear TDRC( $λ$ ) and TDRC( $λ$ )-Huber. When the mean TD matrix is positive stable, both constrained algorithms converge under sufficiently strong regularization without requiring positive definiteness.

Figures & tables

Figure 1: Four-state off-policy prediction problem. The target policy moves clockwise, whereas the behavior policy chooses the clockwise and counterclockwise actions with equal probability.

$\beta$	$\Gamma_{0}^{\mathrm{num}}(\beta)$	$\widehat{\Gamma}_{0}^{\mathrm{dir}}(\beta)$	$\widehat{\Gamma}_{0}^{\mathrm{Lyap}}(\beta)$
$0$	$1.181$	$15.696$	$39.530$
$1/2$	$0.092$	$0.556$	$1.401$
$1$	$0.049$	$0.283$	$0.713$

Table 1: Numerically evaluated integral gain and its analytic upper bounds for

\lambda=0

. A value below one verifies the corresponding small-gain condition.

$\lambda$	$\beta=0$	$\beta=0.02$	$\beta=0.05$	$\beta=0.1$
$0$	$3.465$	$1.781$	$1.072$	$0.662$
$1/4$	$2.281$	$1.162$	$0.694$	$0.427$
$1/2$	$1.417$	$0.717$	$0.426$	$0.261$
$5/8$	$1.069$	$0.539$	$0.320$	$0.196$

Table 2: Direct numerical evaluation of

G_{\lambda}^{\mathrm{num}}(\beta)

with

\eta=1

. A value below one verifies the sufficient small-gain condition.

Temporal-Difference Learning

Temporal-difference learning estimates values by bootstrapping from later predictions, enabling online learning and control from sequential experience.

See all 88 papers

Oct 14, 2026

On the Convergence of Semi-Gradient TD: A Mean Field Perspective

Semi-gradient temporal-difference learning is a core algorithmic component of reinforcement learning, but bootstrapping with function approximation generally induces a non-conservative vector field and can lead to instability. We analyze this effect for two-layer neural networks in the mean-field regime and identify a simple stability mechanism in which entropy-induced relaxation dominates the sensitivity of the moving bootstrap target. Under this condition, we prove exponential convergence to a unique fixed point and quantify its bias relative to the unregularized Bellman solution. We also show that the same mechanism extends to entropy-regularized off-policy control through soft Q-learning.

Haruki Settai, Tadashi Kozuno, Shinji Ito

The University of Tokyo · Sun Intelligence · The University of Tokyo & RIKEN

Temporal-Difference Learning RL Stability Q-Learning Off-Policy RL

Ask PDF

Mar 3, 2026

Towards Parameter-Free Temporal Difference Learning

Temporal difference (TD) learning is a fundamental algorithm for estimating value functions in reinforcement learning. Recent finite-time analyses of TD with linear function approximation quantify its theoretical convergence rate. However, they often require setting the algorithm parameters using problem-dependent quantities that are difficult to estimate in practice -- such as the minimum eigenvalue of the feature covariance (

ω

) or the mixing time of the underlying Markov chain (

τ_{\text{mix}}

). In addition, some analyses rely on nonstandard and impractical modifications, exacerbating the gap between theory and practice. To address these limitations, we use an exponential step-size schedule with the standard TD(0) algorithm. We analyze the resulting method under two sampling regimes: independent and identically distributed (i.i.d.) sampling from the stationary distribution, and the more practical Markovian sampling along a single trajectory. In the i.i.d.\ setting, the proposed algorithm does not require knowledge of problem-dependent quantities such as

ω

, and attains the optimal bias-variance trade-off for the last iterate. In the Markovian setting, we propose a regularized TD(0) algorithm with an exponential step-size schedule. The resulting algorithm achieves a comparable convergence rate to prior works, without requiring projections, iterate averaging, or knowledge of

τ_{\text{mix}}

ω

Yunxiang Li, Mark Schmidt, Reza Babanezhad +1

University of British Columbia · Samsung AI - Montreal · Simon Fraser University

Temporal-Difference Learning

Ask PDF

Sep 14, 2026

Regularized Emphatic Temporal-Difference Learning: Stability under Constant Stepsizes

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.

Xingguo Chen, Zhaohui Wu, Jinguo Ye +5

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 +1

Temporal-Difference Learning Stochastic Approximation

Ask PDF

Abstract

Temporal-Difference Learning

Explore similar work

On the Convergence of Semi-Gradient TD: A Mean Field Perspective

Towards Parameter-Free Temporal Difference Learning

Regularized Emphatic Temporal-Difference Learning: Stability under Constant Stepsizes