Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games

Online learning and game theory share an intricately connected history tracing back to Robinson’s analysis of fictitious play [Robinson51:iterative], as well as Blackwell’s seminal approachability theorem [Blackwell56:analog], which served as the advent of the modern no-regret framework [Hart00:Simple, Abernethy11:Blackwell]. These connections have since led to the discovery of broad learning paradigms such as Online Mirror Descent, encompassing algorithms such as the celebrated Multiplicative Weights Update (MWU) [Littlestone94:Weighted]. Importantly, uncoupled learning dynamics overcome the often unreasonable assumption that players have perfect knowledge of the game, while they have also emerged as a central component in several recent landmark results in computational game solving [Brown17:Superhuman, Moravvcik17:DeepStack]. Moreover, another compelling feature of the no-regret framework is that it guarantees robustness even against adversarial opponents. Indeed, there are broad families of learning paradigms [Shalev-Shwartz12:Online] that accumulate $O(\sqrt{T})$ regret after $T$ iterations, a barrier which is known to be insuperable in fully adversarial environments [Cesa-Bianchi06:Prediction]. However, this begs the question: What if players do not face adversarial losses, but instead face predictable losses?

This question was first addressed by [Daskalakis11:Near]. They devised a decentralized variant of Nesterov’s excessive gap technique [Nesterov05:Smooth], enjoying a near-optimal rate of convergence of $O(\log T/T)$ to Nash equilibrium when employed by both players in a two-player zero-sum normal-form game. (For brevity we will henceforth omit the specification “normal-form” when referring to games.) At the same time, their algorithm also guarantees optimal (external) regret under worst-case losses. Subsequently, [Rakhlin13:Optimization, Rakhlin13:Online] introduced an optimistic variant of Online Mirror Descent—considerably simpler than the algorithm proposed in [Daskalakis11:Near]—achieving optimal convergence rate to Nash equilibrium, again in zero-sum games. Then [Syrgkanis15:Fast] identified a broad class of predictive learning algorithms that induce no-regret learning dynamics in multi-player general-sum games that guarantee $O(T^{1/4})$ regret if followed by each player. This line of work culminated in a recent advancement by [Daskalakis21:Near], where it was shown that, when all players employ an optimistic variant of MWU, each player incurs only $O(\operatorname{polylog}(T))$ regret. In turn, this implies that the average product distribution of play induced by optimistic MWU is an $\widetilde{O}\left(T^{-1}\right)$-approximate¹¹1As usual, we use the notation $\widetilde{O}(\cdot)$ to suppress polylogarithmic factors of $T$. Also note that for simplicity, and with a slight abuse of notation, in our introductory section we use the big-$O$ notation to hide game-specific parameters. coarse correlated equilibrium (CCE) after $T$ repetitions of the game.

Yet, it is well-understood that a CCE prescribes a rather weak notion of equilibrium [Gordon08:No]. An arguably more compelling solution concept²²2In general-sum multi-player games it is typical to search for solution concepts more permissive than Nash equilibria [Nash50:Equilibrium] as the latter is known to be computationally intractable under reasonable assumptions [Daskalakis09:Complexity, Chen09:Settling, Etessami07:Complexity, Rubinstein16:Settling, Babichenko17:Communication]. in multi-player general-sum games is that of correlated equilibria (CE) [Aumann74:Subjectivity]. Like CCE, it is known that CE can be computed through uncoupled learning dynamics. Thus, our paper is concerned with the following central question: The main contribution of our paper is to answer this question in the affirmative. Unlike in the case of CCE, typical no-external-regret dynamics such as MWU are known not to guarantee convergence to CE. Instead, specialized no-internal-regret or no-swap-regret algorithms have to be employed to converge to CE [Cesa-Bianchi06:Prediction]. Compared to no-external-regret dynamics, these learning dynamics are considerably more complex in that all known algorithms require the computation of the stationary distribution of a certain Markov chain at every iteration. Our main primary technical contribution is to develop techniques to overcome these additional challenges.

normal-formgameΓconsistingofasetofmplayers{1,2,…,m}suchthateveryplayerihasanaction spaceAi≔,forsomeni∈N.ThejointactionspacewillberepresentedwithA≔A1×⋯×Am.Foragivenactionprofilea=(a1,…,am)∈A,theloss functionΛi:A→[0,1]specifiesthelossofplayeriundertheactionprofilea;notethatthenormalizationofthelossescomeswithoutanylossofgenerality.Amixed strategyxi∈Δ(Ai)foraplayeri∈isaprobabilitydistributionover