# Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 40 references that are in the map.
- First posted on arXiv 23 May 2024.

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

- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learning](https://mlsanity.com/paper/2002.00260/) (2020)
- [Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains](https://mlsanity.com/paper/1707.06386/) (2017)
- [Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning](https://mlsanity.com/paper/1905.11425/) (2019)
- [An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias](https://mlsanity.com/paper/2006.07904/) (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)
- [Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noise](https://mlsanity.com/paper/2303.15740/) (2023)
- [Concentration of Contractive Stochastic Approximation and Reinforcement Learning](https://mlsanity.com/paper/2106.14308/) (2021)
- [Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation](https://mlsanity.com/paper/2401.13884/) (2024)
- [Lyapunov Theory for Discrete Time Systems](https://mlsanity.com/paper/1809.05289/) (2018)
- [The case for and against fixed step-size: Stochastic approximation algorithms in optimization and machine learning](https://mlsanity.com/paper/2309.02944/) (2023)
- [Hoeffding's Inequality for Markov Chains under Generalized Concentrability Condition](https://mlsanity.com/paper/2310.02941/) (2023)

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

- [Revisiting Step-Size Assumptions in Stochastic Approximation](https://mlsanity.com/paper/2405.17834/) (2024)
- [Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation](https://mlsanity.com/paper/2410.05106/) (2024)
- [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)
- [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)
- [Homogenization of Multi-agent Learning Dynamics in Finite-state Markov Games](https://mlsanity.com/paper/2506.21079/) (2025)
- [Beyond Client Averaging: A Client-Independent Second-Order Stationary-Bias Component in Stochastic SCAFFOLD](https://mlsanity.com/paper/2608.26765/) (2026)
- [Sharp Stationary Gaussian Approximation for Constant-Stepsize SGD](https://mlsanity.com/paper/2609.39144/) (2026)

## Abstract (arXiv)

We study stochastic approximation algorithms with Markovian noise and constant step-size α. We develop a method based on infinitesimal generator comparisons to study the bias of the algorithm, which is the expected difference between θn -- the value at iteration n -- and θ^* -- the unique equilibrium of the corresponding ODE. We show that, under some smoothness conditions, this bias is of order O(α). Furthermore, we show that the time-averaged bias is equal to α V + O(α2), where V is a constant characterized by a Lyapunov equation, showing that mathbbE[barθn] ≈ θ^*+Vα + O(α2), where barθn=(1/n)sumk=1nθk is the Polyak-Ruppert average. We also show that barθn converges with high probability around θ^*+α V. We illustrate how to combine this with Richardson-Romberg extrapolation to derive an iterative scheme with a bias of order O(α2).