No-regret learning in harmonic games: Extrapolation in the face of conflicting interests

Summary

The paper looks at how no-regret learning algorithms behave in harmonic games, which model situations where players have conflicting interests. This is different from the often-studied potential games where interests are shared. The authors show that in continuous time, FTRL dynamics are Poincaré recurrent and do not converge. In discrete time, FTRL can cause never-ending cycles of best responses. But, by adding an extrapolation step (FTRL+), they show that learning can reach a Nash equilibrium from any starting point, ensuring constant regret and giving important insights into harmonic games.

Strengths

The paper stands out for its novel exploration of no-regret learning in harmonic games, which are less studied compared to potential games. The use of FTRL+ to ensure convergence in these games is a creative extension of existing algorithms. Furthermore, the the result on Poincare recurrence in Theorem 2 is insightful and interesting. The statements and proofs of the results are clear and rigorous, and the figured and presentation aid clarity.

Weaknesses

Empirical results beyond the matching pennies example could strengthen the work. The proofs are somewhat dense and challenging to follow. A stronger differentiation from the work by Legacci et al. would be beneficial.

Questions

How do the choices of parameters $\lambda_i$ and $\eta_i$ affect the performance of the FTRL+ algorithm? How might one select these parameters for different types of harmonic games? Could you expand on the types of harmonic games tested in your experiments? Are there benchmarks the algorithm could be compared against?

Rating

7

Confidence

3

Soundness

4

Presentation

4

Contribution

4

Limitations

Limitations are sufficiently covered given the theoretical nature of the paper.

Summary

The paper studies the behavior of no-regret dynamics, and in particular follow the regularized leader (FTRL), in harmonic games--the strategic counterpart of potential games. They establish the following main results: i) the continuous-time version of FTRL is Poincare recurrent; ii) an extrapolated version of FTRL (FTRL+), which includes the optimistic and mirror-prox variant, converges to a Nash equilibrium; iii) under FTRL+ each player attains $O(1)$ regret.

Strengths

The paper provides a clear and compelling motivation for investigating no-regret dynamics in harmonic games. In particular, the decomposition of Candogan et al. shows that, together with potential games, harmonic games constitute the basic building blocks of any game. Further, harmonic games generalized zero-sum games with a fully-mixed equilibrium, the latter class having received extensive attention in the literature. The results obtained in the paper make a concrete step towards better understanding no-regret dynamics in harmonic games, which I believe is an important contribution and will be welcomed by the learning in games community at NeurIPS. I also believe that the paper may lead to interesting follow-up work on harmonic games. Overall, the main message of the paper is compelling. The writing of the paper is also exemplary and of really high quality. The main body does a great job at providing high-level sketches of the main technical ideas, and the appendix is also very well organized and polished. I did not detect any notable issues with the soundness of the claims.

Weaknesses

Regarding the significance of the results, it can be argued that some of the results are somewhat incremental based on existing results. The fact that FTRL is Poincare recurrent is perhaps not that surprising conceptually given the recent paper of Legacci et al. which shows that for the special case of replicator dynamics; I do understand though that the extension requires some new ideas, as the authors discuss. Moreover, the fact that FTRL+ attains constant regret is also not particularly surprising. To put that result into better context, I would recommend citing the paper of Daskalakis, Fishelson and Golowich (NeurIPS 2021) that shows $O(\log^4 T)$ regret for any game; as far as I understand, the only improvement pertains to logarithmic factors in $T$, which is perhaps not very significant. But I do not believe that the points above constitute basis for rejection.

Questions

No further questions.

Rating

6

Confidence

4

Soundness

4

Presentation

4

Contribution

3

Limitations

The authors have adequately addressed the limitations.

Summary

This paper studies multi-agent no-regret learning dynamics in general harmonic games, which is the strategic complement of potential games. The paper's main contributions are the convergence properties of the family of "Follow-the-regularized-leader" (FTRL) algorithms and its variants in general harmonic games, significantly extending previous results in two-player zero-sum games with fully mixed equilibrium and uniformly harmonic games. Specifically, the main results are (1) the continuous-time dynamics of FTRL are Poincaré recurrent, (2) the discrete-time dynamics of FTRL diverges, but FTRL with an extrapolation step (called FTRL+) guarantees $O(1)$ individual regret and global asymptotic last-iterate convergence/point convergence to a Nash equilibrium. These results show that potential and harmonic games are complementary not only from the strategic but also from the dynamic viewpoint.

Strengths

1. This paper is very well-written and easy to follow. I appreciate that the main body clearly explains the main ideas, and the appendix provides rigorous and detailed proof. 2. The problem of no-regret learning dynamics in games is relevant. This paper contributes to the area by establishing the previously unknown convergence properties of the FTRL dynamics in general harmonic games, including Poincaré recurrence of continuous-time FTRL, last-iterate convergence, and constant regret of FTRL+. The results and techniques in this paper shed light on the further development of learning in harmonic games.

Weaknesses

I do not see any major weakness in the paper. Minor comments: Theorem 3/4: $m_i$ is used to choose the step size but has not been defined? The definition is in the appendix but a pointer should be given in the main body. Line 314: "Similar bounds have only been established for optimistic methods in two-player zero-sum games [25]". [25] established constant regret bounds for all variationally stable games, a class of multi-player games that includes two-player zero-sum games. This should be acknowledged. [25] Hsieh, Yu-Guan, Kimon Antonakopoulos, and Panayotis Mertikopoulos. "Adaptive learning in continuous games: Optimal regret bounds and convergence to nash equilibrium." In Conference on Learning Theory. 2021

Questions

1. $m_i$ is used to choose the step size for convergence of FTRL+. Is there an efficient way to estimate an upper bound of $m_i$? 2. This paper left the rate of convergence for FTRL+ as an open question. I would like to know if similar results hold for optimistic online mirror descent (OOMD)-type algorithms in harmonic games. I think proving convergence rates for OOMD algorithms, especially OGDA, might be more promising than FTRL+.

Rating

7

Confidence

4

Soundness

4

Presentation

3

Contribution

3

Limitations

N/A

Summary

The contributions of this paper are two-fold: i) They prove that continuous FTRL dynamics for general harmonic games are Poincaré recurrent and hence do not converge. Their result generalizes the original result of Mertikopoulos, P., Papadimitriou, C. H., and Piliouras, G., 'Cycles in adversarial regularized learning,' In SODA ’18: Proceedings of the 29th annual ACM-SIAM Symposium on Discrete Algorithms, 2018, for zero-sum games with an interior equilibrium (as a trivial example of harmonic games), and the result of Legacci, Davide, Panayotis Mertikopoulos, and Bary Pradelski, 'A geometric decomposition of finite games: Convergence vs. recurrence under no-regret learning,' arXiv preprint arXiv:2405.07224 (2024), for uniform harmonic games to general harmonic games by volume-preserving flow arguments. ii) Moreover, they show that the regret of general harmonic games for the class of Extrapolated FTRL algorithms (discrete-time dynamics) is constant in time ($T$).

Strengths

- The contributions of this paper are solid and interesting. This paper addresses fundamental problems in harmonic games. - I enjoyed reading the paper. It is well-written, especially the introduction to harmonic games in the appendix and the new viewpoint of Mixed characterization of harmonic games and its role on upper bounding the path length of the no-regret dynamics.

Weaknesses

- Just some missing citations on no-regret learning for games, e.g., -- Daskalakis, Constantinos, Alan Deckelbaum, and Anthony Kim. "Near-optimal no-regret algorithms for zero-sum games." Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms. \ -- Chen, Xi, and Binghui Peng. "Hedging in games: Faster convergence of external and swap regrets." Advances in Neural Information Processing Systems 33 (2020). \ -- Piliouras, Georgios, Ryann Sim, and Stratis Skoulakis. "Beyond time-average convergence: Near-optimal uncoupled online learning via clairvoyant multiplicative weights update." Advances in Neural Information Processing Systems 35 (2022). \ ... __Minor Suggestions__ - Please emphasize in the claims that the regret bounds entailed are constant in $T$ and not potentially in the dimension of the action sets $\mathcal{A}$, since $H_i$ is not constant in $|\mathcal{A}_i|$. - Regarding the notation for $\nu_i(x)$, maybe consider changing it to $\nu_i(x_{-i})$ to improve readability. - In line 268, $x_{n + 1}$ instead of $x_{n}$? - In line 277, "and" before "which" seems to be a typo.

Questions

I do not have any particular question (as the results shown in this paper are not unexpected) except that could authors provide some intuition on the conjecture that convergence to Nash Eq. of no-regret learnings for general harmonic games would be linear beyond the work of Wei, C.-Y., et al. Linear last-iterate convergence in constrained saddle-point optimization. In ICLR ’21: Proceedings of the 2021 International Conference on Learning Representations, 2021. ? (Non-asymptotic version of Theorem 4)

Rating

7

Confidence

5

Soundness

3

Presentation

3

Contribution

3

Limitations

Not applied.

Response by the Reviewer

Thank you for the response! I agree that developing algorithms that require no knowledge of $m_i$ is an important question. I will keep my score. Additional Comment: I think providing more examples of Harmonic games would be helpful. Are there other natural families of games (beyond that obtained by the decomposition or 2p0s game with fully mixed NE) that are harmonic?