- Rating
- 3(+1)
- Confidence
- 4
- Informativeness
- 1(−1)
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies scale-free learning dynamics in games, aiming to achieve fast convergence without knowing the utility scale in advance. The authors establish an external regret bound for two-player zero-sum games and an swap regret bound for multiplayer general-sum games. The authors achieve that by multiple set of ideas including an adaptive learning rate and clipping technique of Cutkosky (2019).
Critical strengths
Finding fast-converging, scale-free learning dynamics is a meaningful problem in games, since while the set of equilibria remains invariant under scaling, standard learning dynamics can change significantly. This creates an asymmetry between equilibrium concepts and learning dynamics. The convergence rates established by the authors, particularly the one for zero-sum games, are interesting.
Critical weaknesses
I have three main concerns and some questions.
-
Coupled learning dynamics. The proposed algorithms require communication between players so it seems these algorithms break uncoupledness. In Eq. (1), the learning rate of each player depends on the payoff variation observed by both players. Similarly, Eq. (6) requires sharing statistics across all players. This seems to be an important limitation. The authors provide a communication-free alternative in Appendix B.5, but it loses scale-freeness and has a worse regret guarantee.
-
Missing related literature. I think the paper should better discuss recent progress on external and swap regret minimization in general-sum games. There have been several recent results achieving logarithmic or even constant regret, including for uncoupled learning dynamics. Although these results do not necessarily provide scale-free guarantees, they are relevant to understanding the significance of this work.
-
A stronger notion of scale-freeness? Definition 2 considers a common positive rescaling of all players' utilities. However, in general-sum games, independently rescaling each player's utility also preserves the set of equilibria. Can the proposed dynamics satisfy this stronger invariance property? I think this is the correct version that should be studied.
I'm very receptive to update my score if my concerns are addressed,
Questions for authors
-
Is coupling necessary? Both Eqs. (1) and (6) rely on information from other players to determine the learning rate. Is there a fundamental reason why scale-free fast convergence requires such coordination, or is this a limitation of the current analysis?
-
Is the communication-free limitation inherent? Appendix B.5 gives a communication-free algorithm, but with weaker guarantees. Is there any evidence that one cannot simultaneously achieve uncoupled learning, scale-freeness, and constant regret in two-player zero-sum games?
4 comments
Response to Reviewer xwMi (2/3)
W2. Related literature on logarithmic and constant regret
- Missing related literature. I think the paper should better discuss recent progress on external and swap regret minimization in general-sum games. There have been several recent results achieving logarithmic or even constant regret, including for uncoupled learning dynamics. Although these results do not necessarily provide scale-free guarantees, they are relevant to understanding the significance of this work.
To our knowledge, these recent results on logarithmic and constant regret were all posted on arXiv shortly before the submission deadline of September 25, 2026, and only one of them concerns swap regret in general-sum games, which is the setting of our Theorem 2.
- Swap regret. The work related to ours is that of Mai (arXiv:2609.16751), which was posted on September 15, ten days before the deadline. It establishes a swap regret bound independent of for uncoupled learning dynamics. This is a strong bound, and its learning dynamic is considerably more involved, as it adds a row normalization map and a two-scale higher-order predictor to the reduction of Blum & Mansour (2007).
- External regret. To our knowledge, the recent works are those of Abbadi et al. (arXiv:2609.04113, September 3), Ha (arXiv:2609.19677, September 17), Soleymani & Piliouras (arXiv:2609.21976, September 18), and Ha (arXiv:2609.22839, September 19), all posted shortly before the deadline. They study external regret and are therefore not directly related to the correlated equilibria considered in our paper.
Since these works were posted on arXiv shortly before the submission deadline, we could not discuss them in the submission. In the revised version, we discuss these developments in Appendix D and state the extension of the bound of Mai (arXiv:2609.16751) to scale-free learning dynamics as an open question in Section 5.
We also emphasize that the main question of our paper is whether fast convergence can be achieved by scale-free and scale-agnostic learning dynamics, whereas these works assume that the scale of the utilities is known.
If these are not the works that the reviewer has in mind, please let us know.
W3. Stronger notion of scale-freeness
- A stronger notion of scale-freeness? Definition 2 considers a common positive rescaling of all players' utilities. However, in general-sum games, independently rescaling each player's utility also preserves the set of equilibria. Can the proposed dynamics satisfy this stronger invariance property? I think this is the correct version that should be studied.
We thank the reviewer for this insightful comment, and we agree that this stronger invariance is the appropriate notion in general-sum games. In the revised version, we define this property (Definition 3) and provide an uncoupled learning dynamic that satisfies it (Theorem 6 in Appendix G).
Algorithm 1 does not satisfy it in general, since its common scale and its common learning rate change when the utility function of a single player is rescaled. In the learning dynamic of Theorem 6, each player uses only its own observations, and thus multiplying each by its own constant leaves all strategies unchanged for every realization of the random initial strategies. Moreover, the bound for player is proportional to its own scale rather than . Whether uncoupled and strongly scale-free learning dynamics can achieve the same dependence on and as in Theorem 2 is open, and we state this question after Theorem 6.
Response to Reviewer xwMi (3/3)
Q1. Is coupling necessary?
- Is coupling necessary? Both Eqs. (1) and (6) rely on information from other players to determine the learning rate. Is there a fundamental reason why scale-free fast convergence requires such coordination, or is this a limitation of the current analysis?
Coupling is not necessary for scale-free fast convergence, as Theorems 5 and 6 in the revised version show. The coupling in Eqs. (1) and (6) allows us to match the best known bounds for a known scale without additional factors. Whether the factors and of the uncoupled learning dynamics can be removed is open, and Section 5 in the revised version states this question.
Q2. Is the limitation of the communication-free learning dynamic inherent?
- Is the communication-free limitation inherent? Appendix B.5 gives a communication-free algorithm, but with weaker guarantees. Is there any evidence that one cannot simultaneously achieve uncoupled learning, scale-freeness, and constant regret in two-player zero-sum games?
We are not aware of any evidence that the three properties cannot be achieved simultaneously, and Theorem 5 in the revised version achieves them up to a factor of in the regret.
Theorem 5 gives an uncoupled and scale-free learning dynamic with regret , and thus the weaker guarantee of Appendix B.5 is not inherent. We have no lower bound for uncoupled scale-free learning dynamics, and whether they can achieve the bound of Theorem 1 is open, as stated after Theorem 5 and in Section 5. In our analysis, the factor comes from the ratio between the gradient norms observed by the two players, for which we only have an upper bound polynomial in and (Lemma 19).
We hope the above addresses your concerns, and we would be happy to clarify any remaining points.
Brief follow-up on our response
Thank you again for the time you have devoted to reviewing our paper. Following your comments, we added a discussion of the recent literature on logarithmic and constant regret. On uncoupledness and the stronger notion of scale-freeness that you suggested, we added new dynamics that have both properties, building on those given at the time of the submission.
In your review, you kindly noted that you would be open to updating your score if your concerns were addressed. If the revision resolves them, we would be grateful if you could consider doing so. We are happy to clarify any remaining points.
Response to Reviewer xwMi (1/3)
We thank the reviewer for the careful review and the constructive comments. Our responses are below.
W1. Coupled learning dynamics
We agree that the coupling was an important limitation. In the revised version, we provide uncoupled learning dynamics that remain scale-free and scale-agnostic, and their bounds are larger than those of Theorems 1 and 2 by factors of log(mT) and nlogm, respectively (Theorems 5 and 6 in Appendices F and G, and the new column "Uncoupled?" in Table 1).
Advantage of coupled dynamics. The coupled learning dynamics of Theorems 1 and 2 are nevertheless useful for the following three reasons.
First, the shared statistics are available when a learning dynamic is used to compute an equilibrium of a given game, which is a main application of learning dynamics with fast convergence. Each player shares one real number per round in Eq. (1) and two real numbers per round in Eq. (6), and no strategy or utility vector is shared. In this application, our learning dynamics achieve fast convergence without prior knowledge of the scale of the payoffs. In the revised version, we state this point after Theorem 1.
Second, scale-free fast convergence does not follow from existing analyses even when these statistics are shared. Existing analyses exploit the negative term in the regret bound by keeping the learning rate below a constant that depends on the scale, and we remove this requirement with a new analysis based on a stopping time (Section 3.3).
Third, the uncoupled learning dynamics that we newly provide have larger regret bounds, and thus slower convergence rates, than our coupled learning dynamics. Moreover, they do not have the square-root dependence on the amount of corruption in general, as noted in Table 1 of the revised version.
Details of new uncoupled dynamics. Both uncoupled results build on the techniques of the main body. In two-player zero-sum games, the learning rate in Eq. (1) uses the squared path length of the gradients observed by the opponent, and Section 3.3 shows that the increments of this quantity are bounded by the changes of the strategy of the player. Each player therefore replaces it with a quantity computed from its own strategies and gradients (Eq. (70)), and the proof uses the same regret bound with a negative term as the proof of Theorem 1 (Eq. (2) in Section 3.3).
In multiplayer general-sum games, each player applies the clipping in Eq. (5) and the learning rate in Eq. (6) with its own observed scale and its own squared path length, and the regret analysis of Theorem 2 applies to each player (Lemma 20). The players draw their strategies in the first round at random, which ensures that the first utility vector observed by each player is not much smaller than the scale of its utility function (Lemma 21). The swap regret of player i is O(Uin3/2m2logmlogT) in expectation over these draws, where Ui≤Umax is the scale of the utility function of player i.