Two-Scale Gradient Descent Ascent Dynamics Finds Mixed Nash Equilibria of Continuous Games: A Mean-Field Perspective
Two-Scale Gradient Descent Ascent Dynamics Finds Mixed Nash Equilibria of Continuous Games: A Mean-Field Perspective
复制标题
DOI：
10.48550/arxiv.2212.08791
复制
发表时间：
2022-12
期刊：
影响因子：
--
通讯作者：
Yulong Lu
中科院分区：
文献类型：
--
作者：
Yulong Lu
寻找两人零和连续博弈的混合纳什均衡(MNE)是机器学习中的一个重要而具有挑战性的问题。求解MNE的经典算法是噪声梯度下降上升法，它在无限粒子极限下产生概率测度空间上的平均场梯度下降上升动力学(GDA)。在这篇文章中，我们首先研究了一个双尺度平均场GDA动力学的收敛问题，以求取熵正则目标的MNE。更准确地说，我们证明了对于每个有限温度(或正则化参数)，具有合适的{em有限}标度比的双尺度平均场GDA指数收敛到唯一的MNE，而不假设相互作用势的凸凹性。我们证明的关键部分在于构造了新的Lyapunov函数，它沿平均场GDA指数地耗散。我们进一步研究了平均场GDA动力学的模拟退火法。我们证明了，在一个随时间对数衰减的温度时间表下，退火平均场GDA收敛到原始非正则化目标的MNE。
Finding the mixed Nash equilibria (MNE) of a two-player zero sum continuous game is an important and challenging problem in machine learning. A canonical algorithm to finding the MNE is the noisy gradient descent ascent method which in the infinite particle limit gives rise to the {\em Mean-Field Gradient Descent Ascent} (GDA) dynamics on the space of probability measures. In this paper, we first study the convergence of a two-scale Mean-Field GDA dynamics for finding the MNE of the entropy-regularized objective. More precisely we show that for each finite temperature (or regularization parameter), the two-scale Mean-Field GDA with a suitable {\em finite} scale ratio converges exponentially to the unique MNE without assuming the convexity or concavity of the interaction potential. The key ingredient of our proof lies in the construction of new Lyapunov functions that dissipate exponentially along the Mean-Field GDA. We further study the simulated annealing of the Mean-Field GDA dynamics. We show that with a temperature schedule that decays logarithmically in time the annealed Mean-Field GDA converges to the MNE of the original unregularized objective.