mlsanityData to 7 Oct 2026

Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability

arXiv 2310.14286 ↗First posted 22 Oct 2023stat.ML cs.LG math.OCcited by 20

Not on the map. Why?

Abstract (arXiv)

In this paper we consider the problem of obtaining sharp bounds for the performance of temporal difference (TD) methods with linear function approximation for policy evaluation in discounted Markov decision processes. We show that a simple algorithm with a universal and instance-independent step size together with Polyak-Ruppert tail averaging is sufficient to obtain near-optimal variance and bias terms. We also provide the respective sample complexity bounds. Our proof technique is based on refined error bounds for linear stochastic approximation together with the novel stability result for the product of random matrices that arise from the TD-type recurrence.

Key facts. Cited by 20 papers in the map (data through 7 Oct 2026). Builds on 14 of its 36 references that are in the map. First posted on arXiv 22 Oct 2023.

Builds on

14 of 36 references.

References · 14

  1. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 165
  2. 2020On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationcited by 65
  3. 2020Least Squares Regression with Markovian Data: Fundamental Limits and Algorithmscited by 56
  4. 2020Is Temporal Difference Learning Optimal? An Instance-Dependent Analysiscited by 41
  5. 2022Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximationcited by 41
  6. 2022Adapting to Mixing Time in Stochastic Optimization with Markovian Datacited by 35
  7. 2022Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizescited by 28
  8. 2021Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsizecited by 26
  9. 2022Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisationcited by 23
  10. 2021On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learningcited by 22
  11. 2014On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergencecited by 20
  12. 2020Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximationcited by 19
2 more
  1. 2021Accelerated and instance-optimal policy evaluation with linear function approximationcited by 18
  2. 2023High-probability sample complexities for policy evaluation with linear function approximationcited by 16

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 4; 2025: 7; 2026: 9.

20 papers.

Sort:

  1. 2024Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learningcited by 19
  2. 2024SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learningcited by 6
  3. 2025A Finite Sample Analysis of Distributional TD Learning with Linear Function Approximationcited by 5
  4. 2025Collaborative Value Function Estimation Under Model Mismatch: A Federated Temporal Difference Analysiscited by 2
  5. 2025A Robust widetildeO(1/√T) Rate for Unprojected TD Learning with Linear Function Approximationcited by 2
  6. 2025Statistical and Algorithmic Foundations of Reinforcement Learningcited by 2
  7. 2025Convergence Guarantees for Federated SARSA with Local Training and Heterogeneous Agentscited by 2
  8. 2026A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak--Ruppert Averagingcited by 2
  9. 2024A Finite-Sample Analysis of an Actor-Critic Algorithm for Mean-Variance Optimization in a Discounted MDPcited by 1
  10. 2026Towards Parameter-Free Temporal Difference Learningcited by 1
  11. 2026Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Frameworkcited by 1
  12. 2024Enhancing Stochastic Optimization for Statistical Efficiency Using ROOT-SGD with Diminishing Stepsizecited by 0
8 more
  1. 2025Convergence of TD(0) under Polynomial Mixing with Nonlinear Function Approximationcited by 0
  2. 2025Accelerated Distributional Temporal Difference Learning with Linear Function Approximationcited by 0
  3. 2026Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Driftcited by 0
  4. 2026Fast and Robust Convergence Rate for TD(0) with Linear Function Approximation, Universal Learning Steps and I.I.D. Samplescited by 0
  5. 2026Mathematical methods of reinforcement learningcited by 0
  6. 2026Regularized Emphatic Temporal-Difference Learning: Stability under Constant Stepsizescited by 0
  7. 2026Clipped or Unclipped? Finite-Sample Trade-offs for Averaged SGD under Heavy-Tailed Noisecited by 0
  8. 2026Sharp Statistical Rates for Asynchronous TD Learning with Markovian Datacited by 0