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

• URL: http://arxiv.org/abs/2606.05967v2
• Date: Fri, 05 Jun 2026 07:03:28 GMT
• Title: Fast and Robust Convergence Rate for TD(0) with Linear Function Approximation, Universal Learning Steps and I.I.D. Samples
• Abstract summary: We study the finite-time behavior of the TD(0) temporal-difference method with linear function approximation (LFA)<n>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.
• Score: 0.8594140167290097
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Stability and Sensitivity Analysis of Relative Temporal-Difference Learning: Extended Version [0.0]
  Relative temporal-difference (TD) learning was introduced to the slow convergence of TD methods when the discount factor approaches one.<n>This paper analyzes relative TD learning with linear function approximation.
  arXiv  Detail & Related papers  (2026-03-29T21:19:19Z)
• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  The Area Under the ROC Curve (AUC) is a pivotal evaluation metric in real-world scenarios with both class imbalance and decision constraints.<n>We present two simple instance-wise minimax reformulations to close the approximation gap of PAUC optimization.<n>The resulting algorithms enjoy a linear per-iteration computational complexity w.r.t. the sample size and a convergence rate of $O(-2/3)$ for typical one-way and two-way PAUCs.
  arXiv  Detail & Related papers  (2025-12-01T02:52:33Z)
• Uncertainty quantification for Markov chain induced martingales with application to temporal difference learning [55.197497603087065]
  We analyze the performance of the Temporal Difference (TD) learning algorithm with linear function approximations.<n>We establish novel and general high-dimensional concentration inequalities and Berry-Esseen bounds for vector-valued martingales induced by Markov chains.
  arXiv  Detail & Related papers  (2025-02-19T15:33:55Z)
• Convergence of TD(0) under Polynomial Mixing with Nonlinear Function Approximation [49.1574468325115]
  Temporal Difference Learning (TD(0)) is fundamental in reinforcement learning.<n>We provide the first high-probability, finite-sample analysis of vanilla TD(0) on mixing Markov data.
  arXiv  Detail & Related papers  (2025-02-08T22:01:02Z)
• Statistical Inference for Temporal Difference Learning with Linear Function Approximation [55.80276145563105]
  We investigate the statistical properties of Temporal Difference learning with Polyak-Ruppert averaging.<n>We make three theoretical contributions that improve upon the current state-of-the-art results.
  arXiv  Detail & Related papers  (2024-10-21T15:34:44Z)
• Nonsmooth Implicit Differentiation: Deterministic and Stochastic Convergence Rates [34.81849268839475]
  We study the problem of efficiently computing the derivative of the fixed-point of a parametric nondifferentiable contraction map. We analyze two popular approaches: iterative differentiation (ITD) and approximate implicit differentiation (AID) We establish rates for the convergence of NSID, encompassing the best available rates in the smooth setting.
  arXiv  Detail & Related papers  (2024-03-18T11:37:53Z)
• Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability [17.771354881467435]
  We show that a simple algorithm with a universal and instance-independent step size is sufficient to obtain near-optimal variance and bias terms. Our proof technique is based on refined error bounds for linear approximation together with the novel stability result for the product of random matrices.
  arXiv  Detail & Related papers  (2023-10-22T12:37:25Z)
• Distributed TD(0) with Almost No Communication [15.321579527891457]
  We provide a new non-asymptotic analysis of distributed temporal difference learning with linear function approximation. We demonstrate a version of the linear time speedup phenomenon, where the convergence time of the distributed process is a factor of $N$ faster than the convergence time of TD(0).
  arXiv  Detail & Related papers  (2023-05-25T17:00:46Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way Partial AUC (OPAUC) and Two-way Partial AUC (TPAUC) measures the average performance of a binary classifier. Most of the existing methods could only optimize PAUC approximately, leading to inevitable biases that are not controllable. We present a simpler reformulation of the PAUC problem via distributional robust optimization AUC.
  arXiv  Detail & Related papers  (2022-10-08T08:26:22Z)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  We study the inequality and non-asymptotic properties of approximation procedures with Polyak-Ruppert averaging. We prove a central limit theorem (CLT) for the averaged iterates with fixed step size and number of iterations going to infinity.
  arXiv  Detail & Related papers  (2020-04-09T17:54:18Z)
• Adaptive Temporal Difference Learning with Linear Function Approximation [29.741034258674205]
  This paper revisits the temporal difference (TD) learning algorithm for the policy evaluation tasks in reinforcement learning. We develop a provably convergent adaptive projected variant of the TD(0) learning algorithm with linear function approximation. We evaluate the performance of AdaTD(0) and AdaTD($lambda$) on several standard reinforcement learning tasks.
  arXiv  Detail & Related papers  (2020-02-20T02:32:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.