mlsanityData to 14 Oct 2026

A Concentration Bound for TD(0) with Function Approximation

arXiv 2312.10424 ↗First posted 16 Dec 2023cs.LG cs.SY eess.SYcited by 10

Not on the map. Why?

Abstract (arXiv)

We derive uniform all-time concentration bound of the type 'for all n ≥ n0 for some n0' for TD(0) with linear function approximation. We work with online TD learning with samples from a single sample path of the underlying Markov chain. This makes our analysis significantly different from offline TD learning or TD learning with access to independent samples from the stationary distribution of the Markov chain. We treat TD(0) as a contractive stochastic approximation algorithm, with both martingale and Markov noises. Markov noise is handled using the Poisson equation and the lack of almost sure guarantees on boundedness of iterates is handled using the concept of relaxed concentration inequalities.

Key facts. Cited by 10 papers in the map (data through 14 Oct 2026). Builds on 16 of its 33 references that are in the map. First posted on arXiv 16 Dec 2023.

Builds on

16 of 33 references.

References · 16

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  2. 2018Is Q-learning Provably Efficient?cited by 487
  3. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  4. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
  5. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 96
  6. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 95
  7. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  8. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 77
  9. 2019Variance-reduced Q-learning is minimax optimalcited by 73
  10. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  11. 2021Concentration of Contractive Stochastic Approximation and Reinforcement Learningcited by 23
  12. 2022Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisationcited by 23
4 more
  1. 2014On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergencecited by 22
  2. 2015A Concentration Bound for Stochastic Approximation via Alekseev's Formulacited by 16
  3. 2013Concentration bounds for temporal difference learning with linear function approximation: The case of batch data and uniform samplingcited by 13
  4. 2019A Multistep Lyapunov Approach for Finite-Time Analysis of Biased Stochastic Approximationcited by 10

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 2; 2026: 7.

10 papers.

  1. 2024Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noisecited by 12
  2. 2025Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learningcited by 5
  3. 2025A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averagingcited by 4
  4. 2026A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak--Ruppert Averagingcited by 2
  5. 2026Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chainscited by 1
  6. 2026Towards Parameter-Free Temporal Difference Learningcited by 1
  7. 2026Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Driftcited by 1
  8. 2026Concentration and Mean-Square Bounds for Contractive Stochastic Approximation: A Unified Elementary Approachcited by 0
  9. 2026Online Policy Evaluation for MDPs with Dynamic UBSR Measurescited by 0
  10. 2026A Concentration Bound for Two-Timescale Actor-Critic Algorithmcited by 0