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

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($\lambda$) with diminishing stepsizes and non-i.i.d. off-policy data, for state-dependent and history-dependent $\lambda$-parameters. We also propose TDRC($\lambda$)-Huber, which preserves the TDRC($\lambda$) 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($\lambda$)-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($\lambda$) and TDRC($\lambda$)-Huber. When the mean TD matrix is positive stable, both constrained algorithms converge under sufficiently strong regularization without requiring positive definiteness.

arXiv comment66 pages, 1 figure. Submitted to the Journal of Machine Learning Research