Can I read Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games on EtoBox?

Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games by Anagnostides, Ioannis; Daskalakis, Constantinos; Farina, Gabriele; Fishelson, Maxwell; Golowich, Noah; Sandholm, Tuomas is a scholarly article available to read on EtoBox.

What is Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games about?

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 equilibria of $O(T^{-3/4})$ due to Chen and Peng (NeurIPS`20), and it is optimal -- within the no-regret framework -- up to polylogarithmic factors in $T$. To obtain these results, we develop new techniques for establishing higher-order smoothness for learning dynamics involving fixed point operations. Specifically, we 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

Author

Anagnostides, Ioannis; Daskalakis, Constantinos; Farina, Gabriele; Fishelson, Maxwell; Golowich, Noah; Sandholm, Tuomas

Published

2021

Language

EN