$O(1/k)$ Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximation
arXiv:2504.19375v2 Announce Type: replace-cross Abstract: Two-time-scale stochastic approximation (SA) is an algorithm with coupled iterations which has found broad applications in reinforcement learning, optimization and game control. In this work, we derive mean squared error bounds for non-linear two-time-scale iterations with contractive mappings. In the setting where both stepsizes are order $Theta(1/k)$, commonly referred to as single time-scale SA with multiple coupled sequences, we obtain the first $O(1/k)$ rate without imposing additional smoothness assumptions. In the setting with […]