Optimization methods and control theory

Research Article

Gaussian approximation for linear stochastic approximation with an application to reinforcement learning

Danil Eldarovich Gainanov¹, Ilya Valerievich Levin²

1,2	Higher School of Economics, Moscow, Russia
2	ivlevin@hse.ru

Abstract. We consider The problem of statistical inference for solving a system of linear equations $\overline{\mathbf{A}}$ ${\theta }^{\star }$ = $\overline{\mathbf{b}}$, where the matrix $\mathbf{A}$ and the vector $\mathbf{b}$ are unknown, and noisy observations are available instead. we use linear stochastic approximation with a constant stepsize and Markovian noise. Polyak–Ruppert averaging reduces variance but retains a stationary bias of order $\alpha$, which degrades a Gaussian approximation centered at $\theta^\star$. To remove the leading bias, Richardson–Romberg extrapolation combines averages of two recursions with step-sizes $\alpha$ and $2\alpha$, driven by the same Markov-chain trajectory. This correction is shown to improve the Gaussian approximation without changing the limiting variance.
We establish a non-asymptotic bound in Kolmogorov distance for scalar projections of the averaged iterates with Richardson–Romberg extrapolation. For a trajectory of length $n$, choosing a stepsize of order $n^{-1/2}$ yields the rate $n^{-1/4}$ up to logarithmic factors. As an application of our theory, we consider the construction of confidence intervals for the parameters estimated by the TD(0) algorithm in reinforcement learning. Numerical experiments on synthetic data confirm the correction of the center and improved confidence-interval coverage without a material increase in width. (In Russian).

Keywords: Linear stochastic approximation, Gaussian approximation, Richardson-Romberg extrapolation, confidence intervals, reinforcement learning

MSC-2020 62L20; 60J20, 65C40

For citation: Danil E. Gainanov, Ilya V. Levin. Gaussian approximation for linear stochastic approximation with an application to reinforcement learning. Program Systems: Theory and Applications, 2026, 17:4, pp. 33–56. (In Russ.). https://psta.psiras.ru/2026/4_33-56.

Full text of article (PDF): https://psta.psiras.ru/read/psta2026_4_33-56.pdf.

The article was submitted 18.08.2026; approved after reviewing 15.09.2026; accepted for publication 21.09.2026; published online 13.10.2026.