O(1/k) Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximation

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 true time-scale separation, the previous best bound was O(1/k2/3). We improve this to O(1/ka) for any a<1 approaching the optimal O(1/k) rate. The key step in our analysis involves rewriting the original iteration in terms of an averaged noise sequence whose variance decays sufficiently fast. Additionally, we use an induction-based approach to show that the iterates are bounded in expectation. Our results apply to Polyak averaging, as well as to algorithms from reinforcement learning, and optimization, including gradient descent-ascent and two-time-scale Lagrangian optimization.