Fast Convergence of Regularized Learning in Games
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 blackbox reduction for any algorithm in the class to achieveÕ(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 [17] and Daskalakis et al. [4], who only analyzed two-player zero-sum games for specific algorithms.
The paper introduces a new method for regret minimization in multiplayer normal-form games. Specifically, the paper generalizes previous algorithms (Optimistic Mirror Descent and Optimistic Follow the Regularized Leader) for two-player zero-sum games to multiplayer general-sum games.The experimental results compared to Hedge is impressive. The content of the paper would appeal to the NIPS community.I have some specific questions and comments:- pg. 3: why is the root removed from the log when claiming "converges to O(n log(d) sqrt(T)", where in r_i(T) the root contains the log? Is this a typo?- pg. 6: "This is the first fast convergence result to CCE using natural, decoupled no-regret dynamics." I have two problems with this statement: 1. "natural" and "decoupled" are not clearly defined; and how is it "decoupled" anyway-- Corollary 12 upon which this claim is base requires all players to use OFTRL with specific choices of M_i^t and \eta. 2. It is a bit strong: what about Hart & Mas-Colell's regret-matching (i.e. [13])? Either clarify, rephrase, or remove this claim.Some things to think about:- Any ideas or comments on whether these results can be extended in a straight-forward way to the partial information setting using sampling (e.g. Optimistic Exp3)?Some minor points for camera-ready if accepted: - pg. 1: ".. a chink that hints", what is "chink"? - pg. 3: Remove the space after PoA in "(PoA )" - pg. 4: end of Thm4 proof, is there a max_{j \in N} missing in the right-most inequality? Maybe just remove the j subscript after removing the \sum_{j \neq i}? - Fix argmax so that the set being maxed over is entirely under the argmax (i.e. arg is not separated from max) - A number of items in the bibliography need to be fixed. Volume, number, pages are missing for [4], write out the full conference names for [19] and [20].