Fast Convergence of Regularized Learning in Games

By Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, Robert E. Schapire. Neural Information Processing Systems, 2015

305 citations recorded by the source corpus.

We show that natural classes of regularized learning algorithms with a form of recency bias achieve faster convergence rates to approximate efficiency and to coarse correlated equilibria in multiplayer normal form games. When each player in a game uses an algorithm from our class, their individual regret decays at $O(T^{-3/4})$, while the sum of utilities converges to an approximate optimum at $O(T^{-1})$--an improvement upon the worst case $O(T^{-1/2})$ rates. We show a black-box reduction for any algorithm in the class to achieve $\tilde{O}(T^{-1/2})$ rates against an adversary, while maintaining the faster rates against algorithms in the class. Our results extend those of [Rakhlin and Shridharan 2013] and [Daskalakis et al. 2014], who only analyzed two-player zero-sum games for specific algorithms.

Subfields: Artificial Intelligence, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/49984bc327ef6952118c4b871eeef2a907f7a4ed

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Training GANs with Optimism (2017, background): “…that Optimistic Mirror De-scent and its generalization of Optimistic Follow-the-Regularized-Leader (OFTRL), achieve faster convergence rates than gradient descent in convex-concave zero-sum games (Rakhlin & Sridharan, 2013a;b) and even in general normal form games (Syrgkanis et al., 2015).”
ODE Analysis of Stochastic Gradient Methods with Optimism and Anchoring for Minimax Problems and GANs (2019, unknown): “Although the recent name ‘optimism’ originates from its use in online optimization [6, 55, 56, 62], the idea dates back to Popov’s work in the 1980s [53] and has been studied independently in the mathematical programming community [35, 32, 34, 33, 7].”
Near-Optimal Model-Free Reinforcement Learning in Non-Stationary Episodic MDPs (2021, background): “This notion of smoothness is motivated by the deﬁnition of smooth games in Roughgarden (2009); Syrgkanis et al. (2015), as stated in Radanovic et al. (2019).”
Cycles in adversarial regularized learning (2017, background): “[43] further analyzed a recency biased variant of FoReL in more general multi-player games and showed that it is possible to achieve an O(t−3/4) regret minimization rate.”
From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization (2020, background): “…used in self-play to learn an equilibrium: regret minimization methods have been extensively studied in zero-sum games (Cesa-Biachi & Lugosi, 2006; Syrgkanis et al., 2015; Fudenberg & Levine, 1998; Zinkevich et al., 2008; Hofbauer et al., 2009; Cesa-Biachi & Lugosi, 2006), for which the average…”
Differentiable Game Mechanics (2019, background): “Optimistic mirror descent is a family of algorithms that has nice convergence properties in games (Rakhlin and Sridharan, 2013; Syrgkanis et al., 2015).”
Introduction to Multi-Armed Bandits (2019, background): “However, recent literature obtains Õ(1t ) convergence rates, under various assumptions about the game matrix, the feedback model, or the algorithms themselves (Rakhlin and Sridharan, 2013; Daskalakis et al., 2015; Syrgkanis et al., 2015; Foster et al., 2016; Wei and Luo, 2018).”