Central Limit Theorem For Two-timescale Stochastic Approximation With Markovian Noise: Theory And Applications

Abstract

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 approxi

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyhu2024central

Related papers

• Finite Time Analysis Of Linear Two-timescale Stochastic Approximation With Markovian Noise (2020)0.00
• Finite Sample Analysis Of Two-timescale Stochastic Approximation With Applications To Reinforcement Learning (2017)0.00
• Sample Complexity Bounds For Two Timescale Value-based Reinforcement Learning Algorithms (2020)0.00
• Two Time-scale Off-policy TD Learning: Non-asymptotic Analysis Over Markovian Samples (2019)0.00
• Finite-time Performance Bounds And Adaptive Learning Rate Selection For Two Time-scale Reinforcement Learning (2019)0.00
• Non-asymptotic Analysis For Two Time-scale TDC With General Smooth Function Approximation (2021)0.00
• On The Convergence Of Consensus Algorithms With Markovian Noise And Gradient Bias (2020)0.00
• The ODE Method For Stochastic Approximation And Reinforcement Learning With Markovian Noise (2024)0.00