Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performance

• 成果类型: Article
• 署名作者: Doan, Thinh T. T.
• 署名单位: Virginia Polytechnic Institute & State University
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2022.3210147
• 发表日期: 2023
• 页码: 4695-4705
• 关键词: Reinforcement learning; stochastic approximation; two-time-scale stochastic approximation

摘要

Two-time-scale stochastic approximation, a generalized version of the popular stochastic approximation, has found broad applications in many areas including stochastic control, optimization, and machine learning. Despite its popularity, theoretical guarantees of this method, especially its finite-time performance, are mostly achieved for the linear case while the results for the nonlinear counterpart are very sparse. Motivated by the classic control theory for singularly perturbed systems, we study in this article the asymptotic convergence and finite-time analysis of the nonlinear two-time-scale stochastic approximation. Under some fairly standard assumptions, we provide a formula that explicitly characterizes the rate of convergence of the main iterates to the desired solutions. In particular, we show that the mean square error generated by the method convergences to zero at a rate O(1/k(2/3)), where k is the number of iterations. The key idea in our analysis is to properly choose the two step sizes to characterize the coupling between the fast and slow time-scale iterates.