mlsanityData to 14 Oct 2026

On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergence

arXiv 1411.3224 ↗First posted 12 Nov 2014cs.LG math.OC stat.MLcited by 22

Not on the map. Why?

Abstract (arXiv)

We provide non-asymptotic bounds for the well-known temporal difference learning algorithm TD(0) with linear function approximators. These include high-probability bounds as well as bounds in expectation. Our analysis suggests that a step-size inversely proportional to the number of iterations cannot guarantee optimal rate of convergence unless we assume (partial) knowledge of the stationary distribution for the Markov chain underlying the policy considered. We also provide bounds for the iterate averaged TD(0) variant, which gets rid of the step-size dependency while exhibiting the optimal rate of convergence. Furthermore, we propose a variant of TD(0) with linear approximators that incorporates a centering sequence, and establish that it exhibits an exponential rate of convergence in expectation. We demonstrate the usefulness of our bounds on two synthetic experimental settings.

Key facts. Cited by 22 papers in the map (data through 14 Oct 2026). First posted on arXiv 12 Nov 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 4; 2022: 2; 2023: 4; 2024: 3; 2025: 3; 2026: 6.

22 papers.

Sort:

By area:

  1. 2022Policy Gradient Method For Robust Reinforcement Learningcited by 69
  2. 2023Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneitycited by 27
  3. 2023Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stabilitycited by 20
  4. 2021Accelerated and instance-optimal policy evaluation with linear function approximationcited by 18
  5. 2024Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolationcited by 17
  6. 2024A Simple Finite-Time Analysis of TD Learning with Linear Function Approximationcited by 16
  7. 2023Temporal Difference Learning with Compressed Updates: Error-Feedback meets Reinforcement Learningcited by 12
  8. 2023A Concentration Bound for TD(0) with Function Approximationcited by 10
  9. 2021Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexitycited by 7
  10. 2021Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexitycited by 5
  11. 2025Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learningcited by 5
  12. 2025A Robust widetildeO(1/√T) Rate for Unprojected TD Learning with Linear Function Approximationcited by 2
10 more
  1. 2026A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak--Ruppert Averagingcited by 2
  2. 2022Closing the gap between SVRG and TD-SVRG with Gradient Splittingcited by 1
  3. 2025Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Ratescited by 1
  4. 2026Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Driftcited by 1
  5. 2021Scale Invariant Monte Carlo under Linear Function Approximation with Curvature based step-sizecited by 0
  6. 2024Lyapunov-based reinforcement learning for distributed control with stability guaranteecited by 0
  7. 2026A Diffusion Approximation for Temporal-Difference Learning with Linear Features under Markovian Noisecited by 0
  8. 2026Robust Asynchronous Q-Learning under Reward and State Corruption via Batchingcited by 0
  9. 2026A Concentration Bound for Two-Timescale Actor-Critic Algorithmcited by 0
  10. 2026Learning from Unreliable Trajectories: Adversarially-Robust Federated Q-Learningcited by 0