Fast and Robust Convergence Rate for TD(0) with Linear Function Approximation, Universal Learning Steps and I.I.D. Samples

Ziad Kobeissi, Eloïse Berthier
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:5230-5238, 2026.

Abstract

In this paper, we study the finite-time behavior of the TD(0) temporal-difference method with linear function approximation (LFA). We consider on-policy independent and identically distributed (i.i.d.) samples, a constant learning step, and the Polyak-Juditsky averaging method. We establish a new convergence rate, for the Mean-Square Error (MSE) on the approximated function, that is (i) \emph{fast} in the sense that it admits an optimal dependency in the number of iterations $k$ (i.e., of order $1/k$), (ii) is \emph{robust} to ill-conditioning: it only depends on an initial error and model-independent constants and (iii) is \emph{sharp} up to a multiplicative constant lower than $11$. In particular, it does not depend on the smallest eigenvalue of the uncentered covariance matrix of the linear parametrization, unlike all pre-existing $O(1/k)$ rates in the TD(0) literature. We also introduce PCTD(0), a variant of TD(0), which benefits from better convergence properties under an additional assumption of strong mixing on the Markov Chain.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-kobeissi26a, title = { Fast and Robust Convergence Rate for TD(0) with Linear Function Approximation, Universal Learning Steps and I.I.D. Samples }, author = {Kobeissi, Ziad and Berthier, Elo\"{i}se}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {5230--5238}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/kobeissi26a/kobeissi26a.pdf}, url = {https://proceedings.mlr.press/v300/kobeissi26a.html}, abstract = { In this paper, we study the finite-time behavior of the TD(0) temporal-difference method with linear function approximation (LFA). We consider on-policy independent and identically distributed (i.i.d.) samples, a constant learning step, and the Polyak-Juditsky averaging method. We establish a new convergence rate, for the Mean-Square Error (MSE) on the approximated function, that is (i) \emph{fast} in the sense that it admits an optimal dependency in the number of iterations $k$ (i.e., of order $1/k$), (ii) is \emph{robust} to ill-conditioning: it only depends on an initial error and model-independent constants and (iii) is \emph{sharp} up to a multiplicative constant lower than $11$. In particular, it does not depend on the smallest eigenvalue of the uncentered covariance matrix of the linear parametrization, unlike all pre-existing $O(1/k)$ rates in the TD(0) literature. We also introduce PCTD(0), a variant of TD(0), which benefits from better convergence properties under an additional assumption of strong mixing on the Markov Chain. } }
Endnote
%0 Conference Paper %T Fast and Robust Convergence Rate for TD(0) with Linear Function Approximation, Universal Learning Steps and I.I.D. Samples %A Ziad Kobeissi %A Eloïse Berthier %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-kobeissi26a %I PMLR %P 5230--5238 %U https://proceedings.mlr.press/v300/kobeissi26a.html %V 300 %X In this paper, we study the finite-time behavior of the TD(0) temporal-difference method with linear function approximation (LFA). We consider on-policy independent and identically distributed (i.i.d.) samples, a constant learning step, and the Polyak-Juditsky averaging method. We establish a new convergence rate, for the Mean-Square Error (MSE) on the approximated function, that is (i) \emph{fast} in the sense that it admits an optimal dependency in the number of iterations $k$ (i.e., of order $1/k$), (ii) is \emph{robust} to ill-conditioning: it only depends on an initial error and model-independent constants and (iii) is \emph{sharp} up to a multiplicative constant lower than $11$. In particular, it does not depend on the smallest eigenvalue of the uncentered covariance matrix of the linear parametrization, unlike all pre-existing $O(1/k)$ rates in the TD(0) literature. We also introduce PCTD(0), a variant of TD(0), which benefits from better convergence properties under an additional assumption of strong mixing on the Markov Chain.
APA
Kobeissi, Z. & Berthier, E.. (2026). Fast and Robust Convergence Rate for TD(0) with Linear Function Approximation, Universal Learning Steps and I.I.D. Samples . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:5230-5238 Available from https://proceedings.mlr.press/v300/kobeissi26a.html.

Related Material