- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper studies external regret in finite multiplayer games undder exact full information feedback. it proves that standard optimistic hedge with uniform initialization and a common fixed learning rate has worst case regret expoential in either the number of players or the number of actions. It also introduces ECHO-OFTRL. This combines lifted regularization with an EMA cascade for high order prediction, and proves O(N log m_max) individual regret on self play. Then it gives a regret dependent learning rate which addtionally provides adversarial regret of O(N log m_max + \sqrt(T log m_max)
Critical strengths
- the paper quantifies previously implicit game size dependence, proving expoential worst case regret.
- There is a methodological contribution beyond a single constant regret algorithm as the paper combines lifted regret with prediction error filter and provides an EMA construction which relevant norms remain controlled even when the number of player increases.
Critical weaknesses
The main comparison understates directly relevant concurrent results. Appendix A acknowledges Soleymani and Piliouras's complexity. O(\sqrt(N) log m_max). but table 1 exclude it. Their method also offers a closed form update, adversarial robustness, and O(m_i) update time and memory, compare with ECHO's O(N m_i). This reduces the significance of ECHO's algorithm guarantee and makes its contribution harder to assess. The main presentation should explicitly foreground the lower bounds and general filter framework.
Questions for authors
Under matching feedback and public knowledge assumptions, what additional guarantee or capability does ECHO provide relative to the multiplicative optimism method discussed in appendix A? Please clarify the distinction and incorporate that method into the main comparison table.