Learning in Games: Robustness of Fast Convergence
We show that learning algorithms satisfying a low approximate regret property experience fast convergence to approximate optimality in a large class of repeated games. Our property, which simply requires that each learner has small regret compared to a (1 + ✏)-multiplicative approximation to the best action in hindsight, is ubiquitous among learning algorithms; it is satisfied even by the vanilla Hedge forecaster. Our results improve upon recent work of Syrgkanis et al. [28] in a number of ways. We require only that players observe payoffs under other players' realized actions, as opposed to expected payoffs. We further show that convergence occurs with high probability, and show convergence under bandit feedback. Finally, we improve upon the speed of convergence by a factor of n, the number of players. Both the scope of settings and the class of algorithms for which our analysis provides fast convergence are considerably broader than in previous work. Our framework applies to dynamic population games via a low approximate regret property for shifting experts. Here we strengthen the results of Lykouris et al. [19] in two ways: We allow players to select learning algorithms from a larger class, which includes a minor variant of the basic Hedge algorithm, and we increase the maximum churn in players for which approximate optimality is achieved. In the bandit setting we present a new algorithm which provides a "small loss"-type bound with improved dependence on the number of actions in utility settings, and is both simple and efficient. This result may be of independent interest.
This paper introduces a property called low approximate regret for the expert algorithm that will ensure faster convergence in games compared to previous work. The authors show that this property can be satisfied by many common algorithms, including the vanilla Hedge algorithm. The feedback model allowed in this paper is also more natural and less restricted: the player only receives a realized loss vector depending on other players’ chosen actions, or even just the chosen coordinate of this loss vector (i.e. bandit feedback).  High probability bounds are also derived. Finally the authors also extend the results to dynamic population games and improve upon previous work by [LST16].
The results in this paper are interesting in general. However, from a technical viewpoint, the main results seem to be a simple generalization of what is discussed in Thm 23 of [SALS15] (on how a small loss bound leads to a faster rate). Indeed, small loss bound implies low approximation regret as discussed in Sec 3 of this paper. Furthermore, although the main results in [SALS15] are about the expectation feedback model, their result in Thm 23 is actually applicable to the same realized feedback model. So the claim that this paper improves upon [SALS15] in terms of the feedback model seems to be an overstatement to me. In fact, the claim about the improved speed is also a bit misleading, at least for the earlier part of the paper. It does convergence faster, but only to an approximation of the PoA. So in some sense these convergence rates not exactly comparable.  In the bandit setting, there is actually a known algorithm that gives a small loss bound against non-oblivious adversary. See Allenberg, Chamy, Peter Auer, László Györfi, and György Ottucsák. "Hannan consistency in on-line learning in case of unbounded losses under partial monitoring." 2006. It looks like this can be directly applied here?  Some detailed comments are listed below: 1. I would suggest explaining why most of the previous work requires the expectation feedback model while it’s not necessary here. 2. As mentioned above, Line 49 (the second bullet point for improvements) seems to be an overstatement. Same for Line 80, “without a constant factor loss” but still not exactly the PoA, right? 3. In Definition 1, maybe \epsilon should be explicitly required to fall in (0,1)? 4. In Definition 2, the right hand side of the inequality is missing the sum over i. 5. In the end of Proposition 2, instead of writing \epsilon in terms of \gamma, maybe it’s more natural to write \gamma in terms of \epsilon? 6. I would suggest putting Example 1-3 (and related paragraphs) to Sec 2, right after giving the definition of low approximate regret. 7. I don’t see how doubling trick can make any algorithm with weak low approximate regret to an algorithm with strong low approximate regret. 8. For Theorem 3, it’s weird to use informal statements like “regret is bounded by \sqrt{Total loss of best action}” in a theorem. I suggest just writing down the exact expression. 9. Line 222, why “within a (1+\epsilon) favor”? It’s \lambda/(1-\mu-\epsilon) compared to \lambda/(1-\mu), right? 10. The proposed noisy Hedge is a bit similar to Fixed Share, see for example Cesa-Bianchi, et al. 2012 "Mirror descent meets fixed share (and feels no regret)."  11. Some typos and small mistakes:  1) Line 3, “a small a multiplicative”  2) Line 34, remove “in”?  3) Line 42, “…more information than is…”? 4) Line 155, “required that is s is…”? 5) Line 207, “…For instance [FS97, YEYS04]…”, maybe should put this into a parenthesis, and make the punctuation right.