# Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 68 references that are in the map.
- First posted on arXiv 3 Oct 2022.

## Builds on (most cited first, 18 of 18)

- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [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)
- [A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants](https://mlsanity.com/paper/2102.01567/) (2021)
- [Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms](https://mlsanity.com/paper/2006.08916/) (2020)
- [An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias](https://mlsanity.com/paper/2006.07904/) (2020)
- [Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis](https://mlsanity.com/paper/2003.07337/) (2020)
- [Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximation](https://mlsanity.com/paper/2207.04475/) (2022)
- [Optimal and instance-dependent guarantees for Markovian linear stochastic approximation](https://mlsanity.com/paper/2112.12770/) (2021)
- [The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learning](https://mlsanity.com/paper/2110.14427/) (2021)
- [Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsize](https://mlsanity.com/paper/2106.01257/) (2021)
- [Concentration of Contractive Stochastic Approximation and Reinforcement Learning](https://mlsanity.com/paper/2106.14308/) (2021)
- [Finite-Sample Analysis of Off-Policy TD-Learning via Generalized Bellman Operators](https://mlsanity.com/paper/2106.12729/) (2021)
- [Stationary Behavior of Constant Stepsize SGD Type Algorithms: An Asymptotic Characterization](https://mlsanity.com/paper/2111.06328/) (2021)
- [Policy Iteration for Factored MDPs](https://mlsanity.com/paper/1301.3869/) (2013)
- [Markovian Foundations for Quasi-Stochastic Approximation with Applications to Extremum Seeking Control](https://mlsanity.com/paper/2207.06371/) (2022)

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

- [Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability](https://mlsanity.com/paper/2310.14286/) (2023)
- [Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning](https://mlsanity.com/paper/2405.16644/) (2024)
- [Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation](https://mlsanity.com/paper/2401.13884/) (2024)
- [Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learning](https://mlsanity.com/paper/2401.15719/) (2024)
- [A Simple Finite-Time Analysis of TD Learning with Linear Function Approximation](https://mlsanity.com/paper/2403.02476/) (2024)
- [Revisiting Step-Size Assumptions in Stochastic Approximation](https://mlsanity.com/paper/2405.17834/) (2024)
- [Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2405.14285/) (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)
- [Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinements](https://mlsanity.com/paper/2306.16502/) (2023)
- [Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation](https://mlsanity.com/paper/2410.05106/) (2024)
- [A Finite Sample Analysis of Distributional TD Learning with Linear Function Approximation](https://mlsanity.com/paper/2502.14172/) (2025)
- [Effectiveness of Constant Stepsize in Markovian LSA and Statistical Inference](https://mlsanity.com/paper/2312.10894/) (2023)
- [Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Way](https://mlsanity.com/paper/2410.13067/) (2024)
- [Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning](https://mlsanity.com/paper/2509.26442/) (2025)
- [Prelimit Coupling and Steady-State Convergence of Constant-stepsize Nonsmooth Contractive SA](https://mlsanity.com/paper/2404.06023/) (2024)
- [A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regression](https://mlsanity.com/paper/2504.08178/) (2025)
- [Statistical Guarantees for High-Dimensional Stochastic Gradient Descent](https://mlsanity.com/paper/2510.12013/) (2025)
- [High-Order Error Bounds for Markovian LSA with Richardson-Romberg Extrapolation](https://mlsanity.com/paper/2508.05570/) (2025)
- [Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGD](https://mlsanity.com/paper/2604.10373/) (2026)
- [Self-Normalized Inference for Constant-Stepsize Temporal-Difference Learning under Markovian Sampling](https://mlsanity.com/paper/2608.10896/) (2026)
- [Near-Minimax-Optimal Rates for Asynchronous TD Learning with Markovian Data](https://mlsanity.com/paper/2609.38880/) (2026)
- [Stochastic optimization with arbitrary recurrent data sampling](https://mlsanity.com/paper/2401.07694/) (2024)
- [Coupling-based Convergence Diagnostic and Stepsize Scheme for Stochastic Gradient Descent](https://mlsanity.com/paper/2412.11341/) (2024)
- [Central Limit Theorems for Stochastic Gradient Descent Quantile Estimators](https://mlsanity.com/paper/2503.02178/) (2025)
- [Wasserstein-p Central Limit Theorem Rates: From Local Dependence to Markov Chains](https://mlsanity.com/paper/2601.08184/) (2026)
- [Clipped or Unclipped? Finite-Sample Trade-offs for Averaged SGD under Heavy-Tailed Noise](https://mlsanity.com/paper/2609.32962/) (2026)
- [Sharp Stationary Gaussian Approximation for Constant-Stepsize SGD](https://mlsanity.com/paper/2609.39144/) (2026)
- [Gaussian Limits for SGD Without Stationary Moments](https://mlsanity.com/paper/2610.05599/) (2026)
- [Limit Theory for Online Expectile Estimation under Short and Long Range Dependence](https://mlsanity.com/paper/2610.16030/) (2026)

## Abstract (arXiv)

We consider Linear Stochastic Approximation (LSA) with a constant stepsize and Markovian data. Viewing the joint process of the data and LSA iterate as a time-homogeneous Markov chain, we prove its convergence to a unique limiting and stationary distribution in Wasserstein distance and establish non-asymptotic, geometric convergence rates. Furthermore, we show that the bias vector of this limit admits an infinite series expansion with respect to the stepsize. Consequently, the bias is proportional to the stepsize up to higher order terms. This result stands in contrast with LSA under i.i.d. data, for which the bias vanishes. In the reversible chain setting, we provide a general characterization of the relationship between the bias and the mixing time of the Markovian data, establishing that they are roughly proportional to each other. While Polyak-Ruppert tail-averaging reduces the variance of the LSA iterates, it does not affect the bias. The above characterization allows us to show that the bias can be reduced using Richardson-Romberg extrapolation with m≥ 2 stepsizes, which eliminates the m-1 leading terms in the bias expansion. This extrapolation scheme leads to an exponentially smaller bias and an improved mean squared error, both in theory and empirically. Our results immediately apply to the Temporal Difference learning algorithm with linear function approximation, Markovian data, and constant stepsizes.