mlsanityData to 14 Oct 2026

High-Order Error Bounds for Markovian LSA with Richardson-Romberg Extrapolation

arXiv 2508.05570 ↗First posted 7 Aug 2025stat.ML cs.LG math.OCcited by 1

Not on the map. Why?

Abstract (arXiv)

In this paper, we study the bias and high-order error bounds of the Linear Stochastic Approximation (LSA) algorithm with Polyak-Ruppert (PR) averaging under Markovian noise. We focus on the version of the algorithm with constant step size α and propose a novel decomposition of the bias via a linearization technique. We analyze the structure of the bias and show that the leading-order term is linear in α and cannot be eliminated by PR averaging. To address this, we apply the Richardson-Romberg (RR) extrapolation procedure, which effectively cancels the leading bias term. We derive high-order moment bounds for the RR iterates and show that the leading error term aligns with the asymptotically optimal covariance matrix of the vanilla averaged LSA iterates.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 11 of its 26 references that are in the map. First posted on arXiv 7 Aug 2025.

Builds on

11 of 26 references.

References · 11

  1. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
  2. 2017Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chainscited by 88
  3. 2020On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationcited by 68
  4. 2021Optimal and instance-dependent guarantees for Markovian linear stochastic approximationcited by 33
  5. 2022Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizescited by 30
  6. 2024Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolationcited by 17
  7. 2024Revisiting Step-Size Assumptions in Stochastic Approximationcited by 10
  8. 2023The case for and against fixed step-size: Stochastic approximation algorithms in optimization and machine learningcited by 7
  9. 2023Rosenthal-type inequalities for linear statistics of Markov chainscited by 6
  10. 2024The Collusion of Memory and Nonlinearity in Stochastic Approximation With Constant Stepsizecited by 6
  11. 2024Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Waycited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Self-Normalized Inference for Constant-Stepsize Temporal-Difference Learning under Markovian Samplingcited by 1