Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving 𝒪(1/k) Finite-Sample Complexity

• 成果类型: Article
• 署名作者: Doan, Thinh T.
• 署名单位: University of Texas System; University of Texas Austin
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2025.3590113
• 发表日期: 2026
• 关键词: Convergence rate; optimization

摘要

This article proposes to develop a new variant of the two-time-scale stochastic approximation to find the roots of two coupled nonlinear operators, assuming that only noisy samples of these operators can be observed. Our key idea is to leverage the classic Polyak-Ruppert averaging technique to dynamically estimate the operators through their samples. The estimated values of these averaging steps will then be used in the two-time-scale stochastic approximation updates to find the desired solution. Our main theoretical result is to show that under the strongly monotone condition of the underlying nonlinear operators, the mean-squared errors of the iterates generated by the proposed method converge to zero at an optimal rate & Oscr;(1/k), where k is the number of iterations. Our result significantly improves the existing result of two-time-scale stochastic approximation, where the best known finite-time convergence rate is & Oscr;(1/k(2/3)). We illustrate this result by applying the proposed method to develop new reinforcement learning algorithms that achieve a better performance than the existing ones in two numerical simulations.