A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak--Ruppert Averaging
Not on the map. Why?
Abstract (arXiv)
We study linear TD(0) under Markovian sampling, where data are generated along a single trajectory. We provide high-probability guarantees for a plain unprojected TD(0) algorithm with Polyak-Ruppert (PR) averaging, using a single stepsize schedule ηt propto frac1τmixlog(t)√t that depends on the mixing time but requires no prior knowledge of the curvature parameter ω. Our first result shows that such a choice of the stepsize guarantees that the TD(0) iterates are automatically and uniformly bounded with high probability, without projections and without any stability argument based on ω. Building on this result, we establish a simultaneous high-probability convergence guarantee for the PR average: the same stepsize yields both a robust curvature-free widetildeO!left(fracτmix√Tright) rate and a fast curvature-dependent widetildeO!left(fracτmix2ω Tright)rate, with the bound taking the minimum of the two. The core technical ingredient is a Poisson-equation toolkit for geometrically mixing Markov chains, which decomposes Markov noise into a martingale term plus a controlled remainder and enables a new self-bounding inductive argument for pathwise stability.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 19 of its 30 references that are in the map. First posted on arXiv 23 Jun 2026.
Builds on
19 of 30 references.
References · 19
- 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
- 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
- 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 95
- 2020On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationcited by 68
- 2019Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learningcited by 67
- 2020Least Squares Regression with Markovian Data: Fundamental Limits and Algorithmscited by 56
- 2022Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximationcited by 41
- 2022Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisationcited by 23
- 2014On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergencecited by 22
- 2020Temporal Difference Learning as Gradient Splittingcited by 21
- 2023Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stabilitycited by 20
- 2023High-probability sample complexities for policy evaluation with linear function approximationcited by 16
7 more
- 2024A Simple Finite-Time Analysis of TD Learning with Linear Function Approximationcited by 16
- 2013Concentration bounds for temporal difference learning with linear function approximation: The case of batch data and uniform samplingcited by 13
- 2018Approximate Temporal Difference Learning is a Gradient Descent for Reversible Policiescited by 10
- 2023A Concentration Bound for TD(0) with Function Approximationcited by 10
- 2024Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noisecited by 10
- 2020Adaptive Temporal Difference Learning with Linear Function Approximationcited by 9
- 2026Towards Parameter-Free Temporal Difference Learningcited by 1
Built on by
Citing papers per year: 2026: 2.
2 papers.