Finding First-Order Nash Equilibria of Zero-Sum Games with the Regularized Nikaido-Isoda Function
Finding First-Order Nash Equilibria of Zero-Sum Games with the Regularized Nikaido-Isoda Function
复制标题
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Ioannis C. Tsaknakis;Mingyi Hong
中科院分区：
文献类型：
--
作者：
Ioannis C. Tsaknakis;Mingyi Hong
在零和博弈中有效地找到一阶纳什均衡(FNE)可能是具有挑战性的，即使在两人游戏的情况下也是如此。本文提出了一种求解两人零和博弈FNE的算法，该算法的局部代价函数可以是非凸的，而博弈者只能获得局部随机梯度。该方法将感兴趣的问题转化为最小化正则化的Nikaido-Isoda(RNI)函数。我们证明了RNI的全局极小值对应于FNE的集合，并且对于某些非凸对策，RNI最小化问题变为凸的。此外，我们引入了一阶(随机)最优化方法，并证明了其收敛于RNI目标的平稳解的邻域。分析的关键是合理地控制局部随机梯度与真实随机梯度之间的偏差。虽然RNI函数已经被用于分析凸对策，但据我们所知，这是第一次利用RNI公式的性质来寻找随机环境中非凸对策的FNE。
Efficiently finding First-order Nash Equilibria (FNE) in zero-sum games can be challenging, even in a two-player setting. This work proposes an algorithm for finding the FNEs of a two-player zero-sum game, in which the local cost functions can be non-convex, and the players only have access to local stochastic gradients. The proposed approach is based on reformulating the problem of interest as minimizing the Regularized Nikaido-Isoda (RNI) function. We show that the global minima of the RNI correspond to the set of FNEs, and that for certain classes of non-convex games the RNI minimization problem becomes convex. Moreover, we introduce a first-order (stochastic) optimization method, and establish its convergence to a neighborhood of a stationary solution of the RNI objective. The key in the analysis is to properly control the bias between the local stochastic gradient and the true one. Although the RNI function has been used in analyzing convex games, to our knowledge, this is the first time that the properties of the RNI formulation have been exploited to find FNEs for non-convex games in a stochastic setting.