Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving ${\mathcal O}(1/k)$ Finite-Sample Complexity
IEEE Transactions on Automatic Control · 2026-01 · 71 (1) · 230-242
DOI: 10.1109/tac.2025.3590113 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Automatic Control, 2026-01. Verfasst von Thinh T. Doan. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 66 Literaturangaben. Gefördert von: National Science Foundation.
Abstract (Originalsprache)
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 ${\mathcal O}(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 ${\mathcal O}(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.
Förderung
- National Science Foundation
Zitieren
APA
Doan, T. T. (2026). Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving ${\mathcal O}(1/k)$ Finite-Sample Complexity. IEEE Transactions on Automatic Control, 71(1), 230-242. https://doi.org/10.1109/tac.2025.3590113
Vancouver
Doan TT. Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving ${\mathcal O}(1/k)$ Finite-Sample Complexity. IEEE Transactions on Automatic Control. 2026;71(1):230-242. doi:10.1109/tac.2025.3590113
BibTeX
@article{Doan2026,
author = {Doan, Thinh T.},
title = {Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving $\mathcal O(1/k)$ Finite-Sample Complexity},
journal = {IEEE Transactions on Automatic Control},
year = {2026},
volume = {71},
number = {1},
pages = {230--242},
doi = {10.1109/tac.2025.3590113}
}
EUVIMED