Sebastian Allmeier, Nicolas Gast
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 $\mathbb{E}[\barθ_n] \approx θ^*+Vα+ O(α^2)$, where $\barθ_n=(1/n)\sum_{k=1}^nθ_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)$.