Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games. (arXiv:2111.06008v2 [cs.LG] UPDATED)

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 is
$O(\textrm{polylog}(T))$ after $T$ repetitions of the game. We extend their
result from external regret to internal regret and swap regret, thereby
establishing uncoupled learning dynamics that converge to an approximate
correlated equilibrium at the rate of $\tilde{O}(T^{-1})$. This substantially
improves over the prior best rate of convergence for correlated …

arxiv equilibria games general learning lg near