Global Convergence to Local Minmax Equilibrium in Classes of Nonconvex Zero-Sum Games
Global Convergence to Local Minmax Equilibrium in Classes of Nonconvex Zero-Sum Games
复制标题
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Tanner Fiez;L. Ratliff;Eric V. Mazumdar;Evan Faulkner;Adhyyan Narang
中科院分区：
文献类型：
--
作者：
Tanner Fiez;L. Ratliff;Eric V. Mazumdar;Evan Faulkner;Adhyyan Narang
我们研究无约束连续动作零和游戏中具有时间尺度分离（τ - GDA）的梯度下降-上升学习动态，其中最小化玩家面临非凸优化问题，而最大化玩家优化 Polyak-Łojasiewicz (PŁ) 或强凹 (SC) 目标。与过去在非凸 PŁ/SC 零和博弈中基于梯度学习的工作相比，我们评估与自然博弈论均衡相关的收敛性，而不仅仅是平稳性概念。为了实现这一目标，我们证明了 τ - GDA 连续时间限制系统的唯一局部稳定点对应于每类博弈中严格的局部最小最大平衡。对于这些类别的博弈，我们利用时间尺度分离来构造一个势函数，当与稳定性表征和渐近鞍点避免结果相结合时，为离散时间梯度下降-上升更新到一组严格的局部最小最大平衡提供全局渐近几乎确定的收敛保证。此外，我们提供了梯度下降-上升动力学的收敛率，并通过时间尺度分离来近似驻点。
We study gradient descent-ascent learning dynamics with timescale separation ( τ - GDA ) in unconstrained continuous action zero-sum games where the minimizing player faces a nonconvex optimization problem and the maximizing player optimizes a Polyak-Łojasiewicz (PŁ) or strongly-concave (SC) objective. In contrast to past work on gradient-based learning in nonconvex-PŁ/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 τ - 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.