Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applications
This work provides foundational theoretical insights for iterative stochastic algorithms in machine learning, including optimization and reinforcement learning, by extending CLT results to Markovian noise, though it is incremental in building on prior work.
The authors tackled the asymptotic analysis of two-timescale stochastic approximation (TTSA) under Markovian noise by deriving a central limit theorem (CLT), which reveals coupled dynamics not previously addressed. They applied this CLT to broaden efficient sampling strategies in distributed learning and deduced statistical properties for gradient-based temporal difference algorithms with nonlinear function approximation, showing identical asymptotic performance.
Two-timescale stochastic approximation (TTSA) is among the most general frameworks for iterative stochastic algorithms. This includes well-known stochastic optimization methods such as SGD variants and those designed for bilevel or minimax problems, as well as reinforcement learning like the family of gradient-based temporal difference (GTD) algorithms. In this paper, we conduct an in-depth asymptotic analysis of TTSA under controlled Markovian noise via central limit theorem (CLT), uncovering the coupled dynamics of TTSA influenced by the underlying Markov chain, which has not been addressed by previous CLT results of TTSA only with Martingale difference noise. Building upon our CLT, we expand its application horizon of efficient sampling strategies from vanilla SGD to a wider TTSA context in distributed learning, thus broadening the scope of Hu et al. (2022). In addition, we leverage our CLT result to deduce the statistical properties of GTD algorithms with nonlinear function approximation using Markovian samples and show their identical asymptotic performance, a perspective not evident from current finite-time bounds.