The equivalence of dynamic and strategic stability under regularized learning in games

In this paper, we examine the long-run behavior of regularized, no-regret learning in finite games. A well-known result in the field states that the empirical frequencies of no-regret play converge to the game's set of coarse correlated equilibria; however, our understanding of how the players' actual strategies evolve over time is much more limited - and, in many cases, non-existent. This issue is exacerbated further by a series of recent results showing that only strict Nash equilibria are stable and attracting under regularized learning, thus making the relation between learning and pointwise solution concepts particularly elusive. In lieu of this, we take a more general approach and instead seek to characterize the \emph{setwise} rationality properties of the players' day-to-day play. To that end, we focus on one of the most stringent criteria of setwise strategic stability, namely that any unilateral deviation from the set in question incurs a cost to the deviator - a property known as closedness under better replies (club). In so doing, we obtain a far-reaching equivalence between strategic and dynamic stability: a product of pure strategies is closed under better replies if and only if its span is stable and attracting under regularized learning. In addition, we estimate the rate of convergence to such sets, and we show that methods based on entropic regularization (like the exponential weights algorithm) converge at a geometric rate, while projection-based methods converge within a finite number of iterations, even with bandit, payoff-based feedback.

Paper

Similar papers

Peer review

Reviewer vfB17/10 · confidence 3/52023-07-03

Summary

This paper studies the long run behavior of no-regret learning, and introduces the notion of resilience to strategic deviations as a metric with which to characterize no-regret learning algorithms. Moreover, to further strengthen their results the paper utilizes the idea of setwise strategic stability (m-club). In particular, the paper shows a nice connection between regularized learning and club sets. Finally, they estimate convergence rates to club sets, showing geometric rate for entropic regularizers and finite iterations for projection-based methods.

Strengths

I think this paper is a conceptual step forward in the area of regularized learning dynamics. A major point of contention in many prior works in learning in games has been the disconnect between desirable equilibria and equilibria that are actually converged to by regularized learning. The results given in the paper are fairly broad, and the characterization of club sets as an alternative solution concept for regularized learning is (as far as I can tell) quite watertight and intuitive.

Weaknesses

I only have very minor complaints with the paper, namely the section on regularized learning that introduces a few different algorithms under the RL umbrella. I feel this section is quite long and the notation is unnecessarily heavy, most of these could be in the appendix. I would have preferred to see more space allocated to either an extended proof sketch for Thms 2 & 3, or more experimental details.

Questions

A question regarding the actual convergence properties of regularized learners to club sets in comparison to classical solution concepts: how do the payoffs of these points compare to the Nash equilibrium values? Do you see any interesting behaviors of note between standard FTRL dynamics and other RL dynamics that are significantly different in your experiments? Also, is there any connection between club sets and the chain recurrent set of the dynamics? Of course the paper is focused on discrete time regularized learning, but do you have any intuition as to whether club sets could be useful to construct/converge to chain recurrent sets in the continuous-time setting?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The limitations and scope of the proposed ideas are discussed adequately.

Reviewer 7Hjy6/10 · confidence 3/52023-07-03

Summary

The paper shows the convergence of regularized learning in games to sets satisfying a property called closeness under better replies. Moreover, convergence rates are derived even with bandit feedback.

Strengths

The pointwise behavior of regularized learning in games has gained lots of attention recently, and the paper considers a fundamental question in this field. The authors provide complete and general answers to the questions.

Weaknesses

The paper is super notation-heavy and considers a very general setting in terms of both algorithms and feedback models. It would be much easier to follow if the authors could first provide some basic or toy examples and then generalize. Minor: a corrupted reference at the beginning of Line 267.

Questions

While the questions (line 59-60) are important and the results are mathematically sound, what do they imply to regularized learning, in particular, for practitioners? For example, from prior works, we already know that a day-to-day strategy can be arbitrarily bad so it is probably better to do some averaging. Does this paper extend our understanding in this direction?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

N/A

Reviewer nBFX7/10 · confidence 3/52023-07-05

Summary

The paper deals with a fundamental question about long-term behavior of regularized learning algorithms in finite player finite action static games. They prove an interesting equivalence between the set of strategies which are closed under better replies with that of stochastically stable and attracting fixed points of wide class of regularized learning algorithm popularly studied in literature. Furthermore, they also study the rate of convergence of regularized learning algorithms to this set.

Strengths

The paper studies a very fundamental equivalence relation between payoff structure of a static game with that of limit sets of regularized learning algorithms. This result is very strong result which enhances our understanding of learning in static games. Particuarly, this paper brings the notion of better replies from economic literature and presents a deep connection with asymptotic properties of learning algorithm. The clarity of presentation of this paper is very good. The literature survey is also up to the mark to the best of my knowledge.

Weaknesses

The paper has no major weakness in my view.

Questions

-- Is there any characterization on size of m-club set given certain regularity structure of game. This will provide more predictive power about the asymptotic behavior of common learning dynamics

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Some typographical errors 1. In supplementary material, line 267 has ?? 2. In equation C.13 the right hand side is missing.

Reviewer vfB12023-08-15

Response to Author Rebuttal

Thank you very much for your detailed response. The suggestions for content in the additional page are very reasonable, and should make the paper more suitable for the NeurIPS audience. The comment about Figure 2 and comparisons to other RL methods is interesting but might seem a bit out of place without changes to the flow of the paper, though I think having more discussion about the figure in the appendix would suffice. Regarding chain recurrence, I agree that it is a fascinating connection! It is a shame that this cannot be expanded upon given space constraints but I am eagerly awaiting a future work in this direction. Best regards, Reviewer vfB1

Reviewer 7Hjy2023-08-18

I thank the authors for their response and confirm my positive evaluation.

Reviewer nBFX2023-08-19

Acknowledgement

I have read the rebuttal and comments from other authors. I will keep my score.

Program Chairsdecision2023-09-21

Decision

Accept (spotlight)

© 2026 NYSGPT2525 LLC