Pith. sign in

REVIEW 22 references

TD(0) with linear function approximation attains a 1/k MSE convergence rate independent of feature covariance conditioning.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.3

2026-06-27 23:41 UTC pith:Y435PC2V

load-bearing objection The paper gives an O(1/k) MSE bound for averaged TD(0) under i.i.d. sampling that drops dependence on the smallest eigenvalue of the feature covariance.

arxiv 2606.05967 v2 pith:Y435PC2V submitted 2026-06-04 stat.ML cs.LG

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

Ziad Kobeissi (L2S) , \'Elo\"ise Berthier (U2IS) This is my paper
classification stat.ML cs.LG
keywords TD(0)temporal differencelinear function approximationconvergence ratemean square errorPolyak-Juditsky averagingreinforcement learning
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper derives a new bound showing that the mean square error of TD(0) iterates with linear function approximation decreases as one over the number of steps. The bound depends only on the starting error and fixed constants, remaining unaffected by how small the smallest eigenvalue of the feature covariance matrix becomes. This removes a dependence present in all earlier optimal-rate analyses of the same algorithm. The setting uses constant step sizes and averaged parameters on independent samples drawn from the on-policy distribution. The authors also define a modified version, PCTD(0), that gains further advantages when the data exhibits strong mixing.

Core claim

The mean-square error on the approximated value function for TD(0) with linear parametrization converges at rate O(1/k) under constant step size and Polyak-Juditsky averaging of the iterates. This rate is robust to ill-conditioning of the linear features because the bound does not involve the minimal eigenvalue of the uncentered covariance matrix, and it is sharp within a factor of 11.

What carries the argument

Polyak-Juditsky averaging of the TD(0) parameter sequence with constant learning rate, which enables the eigenvalue-independent bound.

Load-bearing premise

Samples are drawn independently and identically from the stationary on-policy distribution.

What would settle it

Numerical simulation under i.i.d. on-policy sampling where the observed MSE decay rate varies with the smallest covariance eigenvalue or fails to achieve order 1/k.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • The convergence rate stays optimal regardless of the linear parametrization's conditioning.
  • Step size selection does not require knowledge of the covariance matrix eigenvalues.
  • The result extends to a variant PCTD(0) under an additional mixing assumption on the Markov chain.
  • Analysis techniques may inform bounds for other stochastic approximation algorithms in reinforcement learning.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The approach could be tested in high-dimensional feature settings where eigenvalue dependence previously limited applicability.
  • Similar robustness might appear in off-policy or non-i.i.d. regimes if averaging is applied.
  • Universal step sizes become feasible for practical implementations of TD learning.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 0 minor

Summary. The manuscript analyzes the finite-time behavior of TD(0) with linear function approximation under on-policy i.i.d. samples, constant learning step size, and Polyak-Juditsky averaging. It claims to establish an O(1/k) MSE convergence rate that depends only on the initial error and model-independent constants (no dependence on the smallest eigenvalue of the uncentered covariance matrix), is optimal in k, and is sharp up to a multiplicative factor less than 11. The paper also introduces the PCTD(0) variant for improved properties under strong mixing assumptions on the underlying Markov chain.

Significance. If the claimed rate holds under the stated i.i.d. assumptions, the result would be significant because it supplies an O(1/k) bound free of the usual dependence on the smallest eigenvalue of the feature covariance, a quantity that frequently appears in prior TD(0) analyses and can be arbitrarily small. This robustness property, together with the explicit sharpness statement, would strengthen the theoretical foundation for constant-step TD methods with averaging. The scoping to i.i.d. on-policy data and the separate treatment of the mixing case via PCTD(0) are clearly delineated.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for recommending acceptance. We are pleased that the significance of the O(1/k) MSE rate, its independence from the smallest eigenvalue of the covariance matrix, and the clear scoping to i.i.d. on-policy data are recognized.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper derives a finite-time O(1/k) MSE bound for TD(0) with linear function approximation explicitly under the scoped regime of on-policy i.i.d. samples, constant step-size, and Polyak-Juditsky averaging. The claimed rate is presented as obtained from analysis of the algorithm dynamics rather than by fitting parameters to data or redefining quantities in terms of the target bound. No load-bearing self-citations, self-definitional steps, or reductions of the central result to its own inputs by construction appear in the abstract or stated setting. The separate PCTD(0) variant for mixing chains further treats the i.i.d. case as an independent, deliberately simplified regime. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on standard stochastic approximation assumptions plus the explicit i.i.d. sampling condition; no free parameters or invented entities are introduced in the abstract.

axioms (2)
  • domain assumption Existence of a unique fixed point for the projected Bellman operator under the given linear parametrization.
    Implicit in any TD(0) convergence analysis; required for the MSE to be well-defined relative to the fixed point.
  • standard math Finite second moments of the features and rewards under the i.i.d. sampling distribution.
    Needed for the mean-square error analysis to be finite.

pith-pipeline@v0.9.1-grok · 5742 in / 1350 out tokens · 19905 ms · 2026-06-27T23:41:29.248728+00:00 · methodology

0 comments
read the original 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) fast in the sense that it admits an optimal dependency in the number of iterations k (i.e., of order 1/k), (ii) robust to ill-conditioning: it only depends on an initial error and modelindependent constants and (iii) 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.

Figures

Figures reproduced from arXiv: 2606.05967 by \'Elo\"ise Berthier (U2IS), Ziad Kobeissi (L2S).

Figure 2
Figure 2. Figure 2: Same regime as in Figure 1, but with TD(0) using mini [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: We take d = 3 with λ1 = 1 and λ2 = λ3 = 10−j/2 for 0 ≤ j ≤ 4, so that ω ∈ { 1 3 × 10−j , 0 ≤ j ≤ 4}. We use γ = 0.9 and α = 1−γ 4 = 0.025. We draw the bias on the left (taking σ 2 R = 0), the variance in the middle (taking θ0 = θ ∗ = 0 and σ 2 R = 1) and the total MSE error on the right. The curves are averaged over 10 simulations for 3a and 1000 simulations for 3b and 3c, always with the same transition m… view at source ↗
Figure 4
Figure 4. Figure 4: We take d = 100 and X = {1, . . . , 1000}. The transition matrix is drawn at random: each column is a sample from a Dirichlet distribution with parameter 2/|X | = 2 × 10−3 . On the left, using γ = 0.99 and B = 1, we compare the standard TD(0) with an instance of TD(0) using two learning rates, following the theoretical results of Theorems 3.1 and 3.6. In the center, using γ = 0.99 and B = 100, we compare P… view at source ↗
Figure 5
Figure 5. Figure 5: We use similar parameters as in Figure 3 but with [PITH_FULL_IMAGE:figures/full_fig_p014_5.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

22 extracted references · 3 canonical work pages · 1 internal anchor

  1. [1]

    Non-strongly-convex smooth stochastic approximation with convergence rate O (1/n)

    Francis Bach and Eric Moulines. Non-strongly-convex smooth stochastic approximation with convergence rate O (1/n) . Advances in Neural Information Processing Systems, 26: 0 773--781, 2013

    2013

  2. [2]

    A non-asymptotic analysis of non-parametric temporal-difference learning

    \'Eloïse Berthier, Ziad Kobeissi, and Francis Bach. A non-asymptotic analysis of non-parametric temporal-difference learning. Advances in Neural Information Processing Systems, 2022

    2022

  3. [3]

    A finite time analysis of temporal difference learning with linear function approximation

    Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference on Learning Theory, pages 1691--1692, 2018

    2018

  4. [4]

    Lee, and Zhaoran Wang

    Qi Cai, Zhuoran Yang, Jason D. Lee, and Zhaoran Wang. Neural temporal-difference learning converges to global optima. Advances in Neural Information Processing Systems, 32, 2019

    2019

  5. [5]

    Finite sample analyses for TD (0) with function approximation

    Gal Dalal, Bal \'a zs Sz \"o r \'e nyi, Gugan Thoppe, and Shie Mannor. Finite sample analyses for TD (0) with function approximation. AAAI'18/IAAI'18/EAAI'18, 2018

    2018

  6. [6]

    Wainwright, and Michael I

    Koulik Khamaru, Ashwin Pananjady, Feng Ruan, Martin J. Wainwright, and Michael I. Jordan. Is temporal difference learning optimal? an instance-dependent analysis. SIAM Journal on Mathematics of Data Science, 3 0 (4): 0 1013--1040, 2021

    2021

  7. [7]

    Temporal difference learning with continuous time and state in the stochastic setting

    Ziad Kobeissi and Francis Bach. Temporal difference learning with continuous time and state in the stochastic setting. arXiv preprint arXiv:2202.07960, 2022

    work page arXiv 2022

  8. [8]

    Chandrashekar Lakshminarayanan and Csaba Szepesvari. Linear stochastic approximation: How far does constant step-size and iterate averaging go? In International Conference on Artificial Intelligence and Statistics, pages 1347--1355, 2018

    2018

  9. [9]

    A Robust $\widetilde{\mathcal{O}}(1/\sqrt{T})$ Rate for Unprojected TD Learning with Linear Function Approximation

    Wei-Cheng Lee and Francesco Orabona. A finite-time analysis of TD learning with linear function approximation without projections nor strong convexity. arXiv preprint arXiv:2506.01052, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  10. [10]

    Temporal difference learning as gradient splitting

    Rui Liu and Alex Olshevsky. Temporal difference learning as gradient splitting. In International Conference on Machine Learning, pages 6905--6913. PMLR, 2021

    2021

  11. [11]

    A simple finite-time analysis of TD learning with linear function approximation

    Aritra Mitra. A simple finite-time analysis of TD learning with linear function approximation. IEEE Transactions on Automatic Control, 2024

    2024

  12. [12]

    Robust stochastic approximation approach to stochastic programming

    Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19 0 (4): 0 1574--1609, 2009

    2009

  13. [13]

    Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisation

    Gandharv Patil, LA Prashanth, Dheeraj Nagaraj, and Doina Precup. Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisation. In International Conference on Artificial Intelligence and Statistics, pages 5438--5448, 2023

    2023

  14. [14]

    A stochastic approximation method

    Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathematical Statistics, pages 400--407, 1951

    1951

  15. [15]

    Improved high-probability bounds for the temporal difference learning algorithm via exponential stability

    Sergey Samsonov, Daniil Tiapkin, Alexey Naumov, and Eric Moulines. Improved high-probability bounds for the temporal difference learning algorithm via exponential stability. In The Thirty Seventh Annual Conference on Learning Theory, pages 4511--4547, 2024

    2024

  16. [16]

    Mastering the game of go without human knowledge

    David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 550 0 (7676): 0 354--359, 2017

    2017

  17. [17]

    Finite-time error bounds for linear stochastic approximation and TD learning

    Rayadurgam Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation and TD learning. In Conference on Learning Theory, pages 2803--2830, 2019

    2019

  18. [18]

    Richard S. Sutton. Learning to predict by the methods of temporal differences. Machine Learning, 3 0 (1): 0 9--44, 1988

    1988

  19. [19]

    Sutton and Andrew G

    Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: an Introduction. Adaptive Computation and Machine Learning. MIT Press, Cambridge, MA, second edition, 2018

    2018

  20. [20]

    Elf opengo: An analysis and open reimplementation of alphazero

    Yuandong Tian, Jerry Ma, Qucheng Gong, Shubho Sengupta, Zhuoyuan Chen, James Pinkerton, and Larry Zitnick. Elf opengo: An analysis and open reimplementation of alphazero. In International Conference on Machine Learning, pages 6244--6253. PMLR, 2019

    2019

  21. [21]

    Trefethen and Mark Embree

    Lloyd N. Trefethen and Mark Embree. Spectra and pseudospectra: The behavior of nonnormal matrices and operators, 2005

    2005

  22. [22]

    Tsitsiklis and Benjamin Van Roy

    John N. Tsitsiklis and Benjamin Van Roy. An analysis of temporal-difference learning with function approximation. IEEE Transactions on Automatic Control, 42 0 (5): 0 674--690, 1997. doi:10.1109/9.580874

    work page doi:10.1109/9.580874 1997