Gaussian Approximation for Two-Timescale Linear Stochastic Approximation
This work provides theoretical insights for researchers in optimization and reinforcement learning, but it is incremental as it extends existing analysis to specific algorithm variants.
The paper tackles the problem of analyzing the convergence behavior of two-timescale linear stochastic approximation algorithms by establishing non-asymptotic bounds for normal approximation accuracy, revealing that the rate improves with increased timescale separation for last iterates but decreases for Polyak-Ruppert averaging.
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.