Finite-Time Last-Iterate Convergence for Learning in Multi-Player Games
Finite-Time Last-Iterate Convergence for Learning in Multi-Player Games
复制标题
DOI：
--
复制
发表时间：
2022
影响因子：
6.8
通讯作者：
Yang Cai;Argyris Oikonomou;Weiqiang Zheng
中科院分区：
文献类型：
--
作者：
Yang Cai;Argyris Oikonomou;Weiqiang Zheng
我们研究了[Kor76]的外聚算法和[Pop80]的乐观梯度算法在多人游戏中的最后迭代收敛速度问题。我们证明了这两种具有恒定步长的算法在平滑单调博弈的间隙函数方面具有O（1√T）的最后迭代收敛速度到纳什均衡，其中每个参与者的行动集是一个任意凸集。之前的结果只研究了无约束的设置，其中每个玩家的行动集是整个欧几里德空间。我们的研究结果解决了最近几篇论文[HIMM19， GPD20， GPDO20]中提出的一个开放性问题，该问题要求在约束设置下，提取梯度算法或乐观梯度算法的最后迭代收敛速度。我们的两种算法的收敛率都很紧，并且符合[GPD20， GPDO20]的下界。我们研究结果的核心是一个新概念——切线残差，我们用它来衡量与纳什均衡的接近程度。在我们分析超梯度算法（或乐观梯度算法）时，我们使用正切残差（或正切残差的修改）作为势函数。
We study the question of last-iterate convergence rate of the extragradient algorithm by [Kor76] and the optimistic gradient algorithm by [Pop80] in multi-player games. We show that both algorithms with constant step-size have last-iterate convergence rate of O ( 1 √ T ) to a Nash equilibrium in terms of the gap function in smooth monotone games, where each player’s action set is an arbitrary convex set . Previous results only study the unconstrained setting, where each player’s action set is the entire Euclidean space. Our results address an open question raised in several recent works [HIMM19, GPD20, GPDO20], which ask for last-iterate convergence rate of either the extragradient or the optimistic gradient algorithm in the constrained setting. Our convergence rates for both algorithms are tight and match the lower bounds by [GPD20, GPDO20]. At the core of our results lies a new notion – the tangent residual , which we use to measure the proximity to a Nash equilibrium. We use the tangent residual (or a modification of the tangent residual) as the the potential function in our analysis of the extragradient algorithm (or the optimistic gradient algorithm).