On the convergence of two-timescale learning algorithms

Two-timescale learning algorithms are often applied in game theory and bi-level optimization, using distinct update rates for two interdependent processes. In this talk, I will discuss the convergence of two types of two-timescale algorithms.

The first type is the unified two-timescale Q-learning algorithm by Angiuli et al., effective for solving mean field game (MFG) and mean field control (MFC) problems by adjusting the learning rate ratio for mean field distribution and Q-functions. We provide a theoretical explanation for the algorithm’s bifurcated outcomes under fixed learning rates, contributing a Lyapunov function that integrates mean field distribution and Q-function iterates. This function ensures unified convergence across all learning rates under mild assumptions.

The second type is the two-timescale gradient descent-ascent (GDA) algorithm, designed to find Nash equilibria in min-max games with improved convergence properties. Using a PDE-inspired approach, we analyze convergence in both finite- and infinite-dimensional cases. For finite-dimensional quadratic min-max games, we examine long-time convergence in near quasi-static regimes through hypocoercivity. For mean-field GDA dynamics, we study convergence under finite-scale ratios using a mixed synchronous-reflection coupling technique.