Gaussian Approximation for Two-Timescale Linear Stochastic Approximation

2025/08/11 by Bogdan Butyrin, A. N. Rubtsov, Butyrin, Bogdan +7 · 1 citation
Computer Science · Decision Sciences · #Stochastic Gradient Optimization Techniques #Simulation Techniques and Applications #Risk and Portfolio Optimization

paper · pdf · doi:10.48550/arxiv.2508.07928

Abstract

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 non-trivial 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 high-order moment bounds for the error of linear TTSA algorithm, which may be of independent interest.

Citations

• Statistical inference for Linear Stochastic Approximation with Markovian Noise
• Nonasymptotic CLT and Error Bounds for Two-Time-Scale Stochastic Approximation
• Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learning
• Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving O(1/k) Finite-Sample Complexity
• Berry--Esseen Bounds for Multivariate Nonlinear Statistics with Applications to M-estimators and Stochastic Gradient Descent Algorithms
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration
• Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise
• Multivariate normal approximation on the Wiener space: new bounds in the convex distance
• A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Bound
• The total variation distance between high-dimensional Gaussians with the same mean
• Concentration inequalities for Markov chains by Marton couplings and spectral methods
• Acceleration of Stochastic Approximation by Averaging
• Reinforcement Learning: An Introduction

Cited by

• Mathematical methods of reinforcement learning

Related

• Nonasymptotic CLT and Error Bounds for Two-Time-Scale Stochastic Approximation
• Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning
• Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applications
• Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noise
• Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximation