# Statistical inference for Linear Stochastic Approximation with Markovian Noise

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 May 2025.

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

- [Gaussian Approximation for Two-Timescale Linear Stochastic Approximation](https://mlsanity.com/paper/2508.07928/) (2025)
- [Central Limit Theorems for Asynchronous Averaged Q-Learning](https://mlsanity.com/paper/2509.18964/) (2025)
- [Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximation](https://mlsanity.com/paper/2510.12375/) (2025)
- [Statistical Inference for Linear Functionals of Online Least-squares SGD when t gtrsim d1+δ](https://mlsanity.com/paper/2510.19734/) (2025)
- [Gaussian Approximation for Asynchronous Q-learning](https://mlsanity.com/paper/2604.07323/) (2026)
- [Self-Normalized Inference for Constant-Stepsize Temporal-Difference Learning under Markovian Sampling](https://mlsanity.com/paper/2608.10896/) (2026)
- [Sharp asymptotic theory for Q-learning with LDTZ learning rate and its generalization](https://mlsanity.com/paper/2604.04218/) (2026)
- [On Gaussian approximation for entropy-regularized Q-learning with function approximation](https://mlsanity.com/paper/2605.17678/) (2026)
- [Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximation](https://mlsanity.com/paper/2605.19629/) (2026)
- [A Diffusion Approximation for Temporal-Difference Learning with Linear Features under Markovian Noise](https://mlsanity.com/paper/2606.18183/) (2026)
- [Mathematical methods of reinforcement learning](https://mlsanity.com/paper/2607.06935/) (2026)
- [Clipped or Unclipped? Finite-Sample Trade-offs for Averaged SGD under Heavy-Tailed Noise](https://mlsanity.com/paper/2609.32962/) (2026)
- [Limit Theory for Online Expectile Estimation under Short and Long Range Dependence](https://mlsanity.com/paper/2610.16030/) (2026)

## Abstract (arXiv)

In this paper we derive non-asymptotic Berry-Esseen bounds for Polyak-Ruppert averaged iterates of the Linear Stochastic Approximation (LSA) algorithm driven by the Markovian noise. Our analysis yields O(n-1/4) convergence rates to the Gaussian limit in the Kolmogorov distance. We further establish the non-asymptotic validity of a multiplier block bootstrap procedure for constructing the confidence intervals, guaranteeing consistent inference under Markovian sampling. Our work provides the first non-asymptotic guarantees on the rate of convergence of bootstrap-based confidence intervals for stochastic approximation with Markov noise. Moreover, we recover the classical rate of order O(n-1/8) up to logarithmic factors for estimating the asymptotic variance of the iterates of the LSA algorithm.