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

Abstract

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

24 pages. Accepted at NeurIPS 2024