# Accelerated Multi-Time-Scale Stochastic Approximation: Optimal Complexity and Applications in Reinforcement Learning and Multi-Agent Games

arXiv: https://arxiv.org/abs/2409.07767 · HTML: https://mlsanity.com/paper/2409.07767/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Sep 2024.

## Built on by (most cited first, 5 of 5)

- [Nonasymptotic CLT and Error Bounds for Linear Two-Time-Scale Stochastic Approximation](https://mlsanity.com/paper/2502.09884/) (2025)
- [Single-Timescale Multi-Sequence Stochastic Approximation Without Fixed Point Smoothness: Theories and Applications](https://mlsanity.com/paper/2410.13743/) (2024)
- [In-memory Training on Analog Devices with Limited Conductance States via Multi-tile Residual Learning](https://mlsanity.com/paper/2510.02516/) (2025)
- [Rethinking Neural Network Learning Rates: A Stackelberg Perspective](https://mlsanity.com/paper/2605.15530/) (2026)
- [Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework](https://mlsanity.com/paper/2605.31309/) (2026)

## Abstract (arXiv)

Multi-time-scale stochastic approximation is an iterative algorithm for finding the fixed point of a set of N coupled operators given their noisy samples. It has been observed that due to the coupling between the decision variables and noisy samples of the operators, the performance of this method decays as N increases. In this work, we develop a new accelerated variant of multi-time-scale stochastic approximation, which significantly improves the convergence rates of its standard counterpart. Our key idea is to introduce auxiliary variables to dynamically estimate the operators from their samples, which are then used to update the decision variables. These auxiliary variables help not only to control the variance of the operator estimates but also to decouple the sampling noise and the decision variables. This allows us to select more aggressive step sizes to achieve an optimal convergence rate. Specifically, under a strong monotonicity condition, we show that for any value of N the tth iterate of the proposed algorithm converges to the desired solution at a rate widetildeO(1/t) when the operator samples are generated from a single from Markov process trajectory. A second contribution of this work is to demonstrate that the objective of a range of problems in reinforcement learning and multi-agent games can be expressed as a system of fixed-point equations. As such, the proposed approach can be used to design new learning algorithms for solving these problems. We illustrate this observation with numerical simulations in a multi-agent game and show the advantage of the proposed method over the standard multi-time-scale stochastic approximation algorithm.