Gaussian Approximation for Two-Timescale Linear Stochastic Approximation

P. 36627–36635.

Bogdan Butyrin, Artemy Rubtsov, Naumov A., Ulyanov V. V., Samsonov S.

In this paper, we establish non-asymptotic bounds for accuracy of normal approximation for linear two-timescale stochastic approximation (TTSA) algorithms driven by martingale difference or Markov noise. Focusing on both the last iterate and Polyak–Ruppert averaging regimes, we derive bounds for normal approximation in terms of the convex distance between probability distributions. Our analysis reveals a nontrivial interaction between the fast and slow timescales: the normal approximation rate for the last iterate improves as the timescale separation increases, while it decreases in the Polyak–Ruppert averaged setting. We also provide the highorder moment bounds for the error of linear TTSA algorithm, which may be of independent interest. Finally, we demonstrate that our theoretical results are directly applicable to reinforcement learning algorithms such as GTD and TDC.

Keywords: stochastic approximation, contraction Gaussian approximation

Publication based on the results of: Fundamental and methodological aspects of machine learning, optimization and reinforcement learning and their applications to deep learning (2026)

In book

Proceedings of the AAAI Conference on Artificial Intelligence. AAAI-26: AAAI Technical Track on Planning, Routing, and Scheduling; AAAI Technical Track on Reasoning under Uncertainty; AAAI Technical Track on Search and Optimization. Main Track, volume 40 no. 43

American Association for Artificial Intelligence (AAAI) Press, 2026.