Timezone: »

Global Convergence to Local Minmax Equilibrium in Classes of Nonconvex Zero-Sum Games
Tanner Fiez · Lillian Ratliff · Eric Mazumdar · Evan Faulkner · Adhyyan Narang

Thu Dec 09 04:30 PM -- 06:00 PM (PST) @ None #None
We study gradient descent-ascent learning dynamics with timescale separation ($\tau$-GDA) in unconstrained continuous action zero-sum games where the minimizing player faces a nonconvex optimization problem and the maximizing player optimizes a Polyak-Lojasiewicz (PL) or strongly-concave (SC) objective. In contrast to past work on gradient-based learning in nonconvex-PL/SC zero-sum games, we assess convergence in relation to natural game-theoretic equilibria instead of only notions of stationarity. In pursuit of this goal, we prove that the only locally stable points of the $\tau$-GDA continuous-time limiting system correspond to strict local minmax equilibria in each class of games. For these classes of games, we exploit timescale separation to construct a potential function that when combined with the stability characterization and an asymptotic saddle avoidance result gives a global asymptotic almost-sure convergence guarantee for the discrete-time gradient descent-ascent update to a set of the strict local minmax equilibrium. Moreover, we provide convergence rates for the gradient descent-ascent dynamics with timescale separation to approximate stationary points.

Author Information

Tanner Fiez (University of Washington)
Lillian Ratliff (University of Washington)
Eric Mazumdar (UC Berkeley EECS)
Evan Faulkner (University of Washington)
Adhyyan Narang (University of Washington, Seattle)

More from the Same Authors