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

arXiv: https://arxiv.org/abs/2508.05570 · HTML: https://mlsanity.com/paper/2508.05570/

## Key facts

- Cited by 1 papers 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 (most cited first, 11 of 11)

- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains](https://mlsanity.com/paper/1707.06386/) (2017)
- [On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration](https://mlsanity.com/paper/2004.04719/) (2020)
- [Optimal and instance-dependent guarantees for Markovian linear stochastic approximation](https://mlsanity.com/paper/2112.12770/) (2021)
- [Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes](https://mlsanity.com/paper/2210.00953/) (2022)
- [Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation](https://mlsanity.com/paper/2401.13884/) (2024)
- [Revisiting Step-Size Assumptions in Stochastic Approximation](https://mlsanity.com/paper/2405.17834/) (2024)
- [The case for and against fixed step-size: Stochastic approximation algorithms in optimization and machine learning](https://mlsanity.com/paper/2309.02944/) (2023)
- [Rosenthal-type inequalities for linear statistics of Markov chains](https://mlsanity.com/paper/2303.05838/) (2023)
- [The Collusion of Memory and Nonlinearity in Stochastic Approximation With Constant Stepsize](https://mlsanity.com/paper/2405.16732/) (2024)
- [Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Way](https://mlsanity.com/paper/2410.13067/) (2024)

## Built on by (most cited first, 1 of 1)

- [Self-Normalized Inference for Constant-Stepsize Temporal-Difference Learning under Markovian Sampling](https://mlsanity.com/paper/2608.10896/) (2026)

## 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.