mlsanityData to 14 Oct 2026

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

arXiv 2210.05918 ↗First posted 12 Oct 2022cs.LG cs.AI cs.SYcited by 23

Not on the map. Why?

Abstract (arXiv)

We study the finite-time behaviour of the popular temporal difference (TD) learning algorithm when combined with tail-averaging. We derive finite time bounds on the parameter error of the tail-averaged TD iterate under a step-size choice that does not require information about the eigenvalues of the matrix underlying the projected TD fixed point. Our analysis shows that tail-averaged TD converges at the optimal Oleft(1/tright) rate, both in expectation and with high probability. In addition, our bounds exhibit a sharper rate of decay for the initial error (bias), which is an improvement over averaging all iterates. We also propose and analyse a variant of TD that incorporates regularisation. From analysis, we conclude that the regularised version of TD is useful for problems with ill-conditioned features.

Key facts. Cited by 23 papers in the map (data through 14 Oct 2026). Builds on 10 of its 25 references that are in the map. First posted on arXiv 12 Oct 2022.

Builds on

10 of 25 references.

References · 10

  1. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  2. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
  3. 2019Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learningcited by 67
  4. 2020Least Squares Regression with Markovian Data: Fundamental Limits and Algorithmscited by 56
  5. 2022Target Network and Truncation Overcome The Deadly Triad in Q-Learningcited by 31
  6. 2021On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learningcited by 23
  7. 2020Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximationcited by 19
  8. 2021Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPscited by 19
  9. 2019Characterizing the Exact Behaviors of Temporal Difference Learning Algorithms Using Markov Jump Linear System Theorycited by 17
  10. 2013Concentration bounds for temporal difference learning with linear function approximation: The case of batch data and uniform samplingcited by 13

Built on by

Cited by year (2026 to 14 Oct)

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

23 papers.

Sort:

By area:

  1. 2023Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stabilitycited by 20
  2. 2024Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learningcited by 19
  3. 2023Federated TD Learning over Finite-Rate Erasure Channels: Linear Speedup under Markovian Samplingcited by 15
  4. 2023A Concentration Bound for TD(0) with Function Approximationcited by 10
  5. 2024Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applicationscited by 7
  6. 2024SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learningcited by 7
  7. 2025A Finite Sample Analysis of Distributional TD Learning with Linear Function Approximationcited by 6
  8. 2025Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Featurescited by 5
  9. 2025A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averagingcited by 4
  10. 2025A Robust widetildeO(1/√T) Rate for Unprojected TD Learning with Linear Function Approximationcited by 2
  11. 2025Parameter-free Optimal Rates for Nonlinear Semi-Norm Contractions with Applications to Q-Learningcited by 2
  12. 2026A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak--Ruppert Averagingcited by 2
11 more
  1. 2024A Finite-Sample Analysis of an Actor-Critic Algorithm for Mean-Variance Optimization in a Discounted MDPcited by 1
  2. 2025Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Ratescited by 1
  3. 2025Parameter-Free Federated TD Learning with Markov Noise in Heterogeneous Environmentscited by 1
  4. 2025Accelerated Distributional Temporal Difference Learning with Linear Function Approximationcited by 1
  5. 2026Towards Parameter-Free Temporal Difference Learningcited by 1
  6. 2026Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Driftcited by 1
  7. 2026Quotient-Categorical Representations for Bellman-Compatible Average-Reward Distributional Reinforcement Learningcited by 1
  8. 2026Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Frameworkcited by 1
  9. 2023Loss Dynamics of Temporal Difference Reinforcement Learningcited by 0
  10. 2025Convergence of TD(0) under Polynomial Mixing with Nonlinear Function Approximationcited by 0
  11. 2026Fast and Robust Convergence Rate for TD(0) with Linear Function Approximation, Universal Learning Steps and I.I.D. Samplescited by 0