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

Sihan Zeng, Thinh T. DoanarXiv 2024 · DOI · arXiv

Abstract

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 $t^{\text{th}}$ iterate of the proposed algorithm converges to the desired solution at a rate $\widetilde{O}(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.

Introduction

Many problems in Reinforcement Learning (RL) and Game Theory—such as Actor-Critic methods or multi-agent competitions—are solved using Stochastic Approximation (SA). These problems often involve a "hierarchy" of scales. For example, in an Actor-Critic setup, the "Critic" evaluates a policy (one scale) while the "Actor" improves it (another scale).

When you have $N$ such scales (coupled equations), the standard approach is to use different step sizes for each scale. However, there is a major catch: as $N$ increases, the performance of standard Multi-Time-Scale SA (MSA) degrades. Errors and noise from one scale propagate instantly to others, forcing researchers to use tiny, conservative step sizes. This leads to sub-optimal convergence rates—meaning the algorithm takes much longer to find a solution as the problem gets more complex.

Methodology: The A-MSA Algorithm

The authors introduce A-MSA (Accelerated Multi-Time-Scale Stochastic Approximation). The core innovation is the introduction of auxiliary variables ($f_i$) that act as dynamic estimators for the operators. Instead of updating the decision variables ($\theta_i$) directly using a single noisy sample, the algorithm maintains a running, weighted average of the operator samples.

This seemingly small change has two massive benefits:

  1. Variance Control: It smooths out the "noise" inherent in stochastic sampling.
  2. Decoupling: It breaks the direct link between the sampling noise and the decision variables.

Because the noise is buffered by these auxiliary variables, the algorithm can afford to use much more "aggressive" (larger) step sizes. The authors prove that this allows the algorithm to hit the theoretical optimal convergence rate of $\widetilde{O}(1/t)$ even when samples are generated from a single Markov process trajectory.

A comparison of A-MSA against existing literature, highlighting its unique ability to handle more than two equations under Markovian noise without smoothness assumptions.

Key Insights

  • The "Curse of Scales" is not fundamental: Previously, it was thought that as you added more coupled equations ($N$), the problem became fundamentally harder to solve quickly. This paper shows that the slowdown was actually a limitation of the algorithm (MSA), not the problem itself.
  • Decoupling is key: The bottleneck in standard MSA is how noise from the "fast" scale immediately corrupts the "slow" scale. By using an averaged estimator, A-MSA effectively "insulates" the scales from each other's immediate noise.
  • Unified Framework: The authors show that a wide variety of topics in AI—like distributionally robust RL, TD-learning with momentum, and Mean Field Games—can all be viewed as the same type of coupled fixed-point problem.

Results and Evaluation

The paper focuses on theoretical proofs and algorithmic framework, evaluated using synthetic Multi-Agent Games (specifically a Mean Field Game with 30 states and 10 actions) and Markovian trajectories to test robustness to temporally dependent noise.

The most striking result is the comparison of Sample Complexity (how many samples you need to reach an error of $\epsilon$). While standard MSA gets exponentially slower as $N$ grows, A-MSA maintains the same optimal complexity regardless of $N$.

Sample complexity comparison showing that A-MSA maintains optimal complexity as the number of equations increases.

In numerical simulations of Mean Field Games, A-MSA converged visibly faster and more reliably than the standard MSA baseline, confirming the theoretical findings.

Conclusion

A-MSA represents a significant step forward in stochastic approximation by achieving optimal convergence rates for complex, multi-scale systems. While the primary proof relies on a "strong monotonicity" condition, the authors demonstrate its applicability to a wide range of RL problems. Future work may investigate cases where lower-level operators satisfy weaker conditions, further expanding the algorithm's reach in multi-agent environments.

Summary updated

Abstract

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 $t^{\text{th}}$ iterate of the proposed algorithm converges to the desired solution at a rate $\widetilde{O}(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.
BibTeX
@misc{zeng2024accelerated,
  author = {Sihan Zeng and Thinh T. Doan},
  title = {{Accelerated Multi-Time-Scale Stochastic Approximation: Optimal Complexity and Applications in Reinforcement Learning and Multi-Agent Games}},
  year = {2024},
  eprint = {2409.07767},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2409.07767},
}
Figure