Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games
Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games
复制标题
多人一般和博弈中相关均衡的近乎最优无悔学习
DOI：
10.1145/3519935.3520031
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Sandholm, Tuomas
中科院分区：
文献类型：
--
作者：
Anagnostides, Ioannis;Daskalakis, Constantinos;Farina, Gabriele;Fishelson, Maxwell;Golowich, Noah;Sandholm, Tuomas
最近，Daskalakis，Fishelson和Golowich（DFG）（NeurIPS '21）表明，如果多人一般和正规型博弈中的所有代理都采用乐观乘法权重更新（OMWU），则每个玩家的外部遗憾是O（polylog（T））。在本文中，我们将他们的结果从外部后悔扩展到内部后悔和交换后悔，从而建立了以O（T−1）的速度收敛到近似相关均衡的解耦学习动态。这比Chen和Peng（NeurIPS '20）提出的O（T-3/4）的先验最佳收敛率有了显着提高，并且对于多对数因子来说是最佳的。为了获得这些结果，我们开发了新技术来建立高阶光滑度学习动态涉及不动点运算。具体来说，我们首先建立的无内部后悔学习动力学的Stoltz和Lugosi（马赫学习'05）的组合空间上的无外部后悔动力学等效模拟。这使得我们可以将多项式大小的马尔可夫链上的平稳分布的计算转换为指数大小的集合上的线性变换，使我们能够利用与DGF类似的技术来接近最优地限制内部遗憾。此外，我们为Blum和Mansour（BM）（JMLR '07）的经典算法建立了O（polylog（T））无交换遗憾界。我们这样做是通过引入一种技术的基础上的柯西积分公式，规避了更有限的组合参数DFG。除了澄清BM的接近最优的遗憾保证，我们的论点提供了各种方式的见解，在这些方式中，DFG的技术可以扩展和利用更复杂的学习算法的分析。
Recently, Daskalakis, Fishelson, and Golowich (DFG) (NeurIPS ‘21) showed that if all agents in a multi-player general-sum normal-form game employ Optimistic Multiplicative Weights Update (OMWU), the external regret of every player isO(polylog(T)) afterTrepetitions of the game. In this paper we extend their result from external regret to internal and swap regret, thereby establishing uncoupled learning dynamics that converge to an approximate correlated equilibrium at the rate ofO(T−1). This substantially improves over the prior best rate of convergence ofO(T−3/4) due to Chen and Peng (NeurIPS ‘20), and it is optimal up to polylogarithmic factors.To obtain these results, we develop new techniques for establishing higher-order smoothness for learning dynamics involving fixed point operations. Specifically, we first establish that the no-internal-regret learning dynamics of Stoltz and Lugosi (Mach Learn ‘05) are equivalently simulated by no-external-regret dynamics on a combinatorial space. This allows us to trade the computation of the stationary distribution on a polynomial-sized Markov chain for a (much more well-behaved) linear transformation on an exponential-sized set, enabling us to leverage similar techniques as DGF to near-optimally bound the internal regret.Moreover, we establish anO(polylog(T)) no-swap-regret bound for the classic algorithm of Blum and Mansour (BM) (JMLR ‘07). We do so by introducing a technique based on the Cauchy Integral Formula that circumvents the more limited combinatorial arguments of DFG. In addition to shedding clarity on the near-optimal regret guarantees of BM, our arguments provide insights into the various ways in which the techniques by DFG can be extended and leveraged in the analysis of more involved learning algorithms.
登录
查看更多内容
零和博弈的近乎最优无悔算法
DOI：
10.1016/j.geb.2014.01.003
发表时间：
2011
期刊：
ArXiv
影响因子：
--
作者：
C. Daskalakis;Alan Deckelbaum;A. Kim
通讯作者：
A. Kim
DOI：
--
发表时间：
2012-08
期刊：
ArXiv
影响因子：
--
作者：
A. Rakhlin;Karthik Sridharan
通讯作者：
A. Rakhlin;Karthik Sridharan
DOI：
10.4230/lipics.itcs.2019.27
发表时间：
2018-07
期刊：
--
影响因子：
--
作者：
C. Daskalakis;Ioannis Panageas
通讯作者：
C. Daskalakis;Ioannis Panageas
布莱克威尔平易近人和无悔学习是等效的
DOI：
--
发表时间：
2010
期刊：
Annual Conference Computational Learning Theory
影响因子：
--
作者：
Jacob D. Abernethy;P. Bartlett;Elad Hazan
通讯作者：
Elad Hazan
DOI：
--
发表时间：
2018-07
期刊：
--
影响因子：
--
作者：
C. Daskalakis;Ioannis Panageas
通讯作者：
C. Daskalakis;Ioannis Panageas