- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper derives new bounds for individual swap regret in multiplayer general sum games. The authors study the Blum-Mansour (BM) algorithm instantiated with OFTRL subroutines using higher-order optimism (following the recent advances in OFTRL variants for external-regret minimization in games). They prove that the simultaneous use of this algorithm in general-sum games yields individual swap-regret bounds that are constant in the time horizon T (and with polynomial dependences on the number of players and the sizes of the action sets). This improves over prior state-of-the-art swap-regret bounds that achieved poylogarithmic bounds in T.
Critical strengths
The main strength of the paper is the improved rate for individual swap regret in general-sum games. The result seems to indicate that the classical BM framework is amenable and robust to improved algorithms for external regret minimization. Indeed, the main algorithmic idea of the present work is to incoporate and adapt into BM the recently-introduced higher-order-optimism variants of OFTRL as the base learners.
The authors also establish an adversarial swap-regret guarantee for their new algorithm.
Critical weaknesses
In my view, the paper's main weakness is in the quality of writing. While the technical overview in Section 1 was presented well and gave good initial intuition for the main technical ideas, Sections 4 and 5 were very difficult to follow and feel lacking in intuition. In particular, the start of Section 4 and Subsection 4.1 introduce most of the core objects used in the analysis, e.g., the "curvature energy", but I felt this section offers almost no intuition or discussion as to how to interpret these objects. This makes the remainder of the analysis feel somewhat opaque.
Questions for authors
Suggestions: the continued use of the word "public" when describing parameters, constants, etc. Perhaps it could be clarified what exactly is meant here, e.g., that these parameters or constants are globally known?