acceptodds
Under review as a conference paper at ICLR 2027

Scale-Free Fast Convergence in Games

Abstract

Scale-freeness in games, that is, invariance of learning dynamics under positive rescaling of utilities, has emerged as a desirable property. Yet, almost all fast convergence guarantees in learning in games require prior knowledge of the utility scale. To address this, we develop scale-free learning dynamics that achieve fast convergence without any prior information about utilities. For two-player zero-sum games, we obtain such dynamics with external regret bounded by , where is the payoff range, which implies an convergence rate to Nash equilibrium after rounds. For multiplayer general-sum games, we obtain such dynamics with swap regret bounded by , where is the utility scale and the dependence on the number of players and actions is ignored. This bound yields an convergence rate to correlated equilibrium. Our learning dynamics are based on optimistic follow-the-regularized-leader with adaptive learning rates, and our analyses exploit negative terms in regret bounds without scale-dependent tuning. Specifically, for two-player zero-sum games, we introduce a new analysis based on a stopping time, and for general-sum games, we combine a hybrid regularizer and clipped utilities based on past observations with a new analysis of the time-varying negative terms.

Primary area:
learning theory
Keywords:
learning in games, scale-free and scale-invariant learning, external/swap regret minimization, fast convergence to Nash/correlated equilibrium

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_xwMiOpenReview ↗
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 O(Adifflog⁡m)O(A_{\mathrm{diff}}\log m) external regret bound for two-player zero-sum games and an O(Umax⁡nm2log⁡mlog⁡T)O(U_{\max}nm^2\sqrt{\log m\log T}) 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.

  1. 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.

  2. 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.

  3. 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
  1. 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?

  2. 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
AuthorsOpenReview ↗

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

  1. 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.

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)\sqrt{\log(mT)} and nlog⁡m\sqrt{n\log m}, 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 ii is O(Uin3/2m2log⁡mlog⁡T)O(U_i n^{3/2}m^2\log m\sqrt{\log T}) in expectation over these draws, where Ui≤Umax⁡U_i \le U_{\max} is the scale of the utility function of player ii.

AuthorsOpenReview ↗

Response to Reviewer xwMi (2/3)

W2. Related literature on logarithmic and constant regret

  1. 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 TT 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

  1. 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 UtU^t 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 uiu_i by its own constant ci>0c_i \gt 0 leaves all strategies unchanged for every realization of the random initial strategies. Moreover, the bound for player ii is proportional to its own scale UiU_i rather than Umax⁡U_{\max}. Whether uncoupled and strongly scale-free learning dynamics can achieve the same dependence on mm and nn as in Theorem 2 is open, and we state this question after Theorem 6.

AuthorsOpenReview ↗

Response to Reviewer xwMi (3/3)

Q1. Is coupling necessary?

  1. 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 log⁡(mT)\sqrt{\log(mT)} and nlog⁡m\sqrt{n\log m} 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?

  1. 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 log⁡(mT)\sqrt{\log(mT)} in the regret.

Theorem 5 gives an uncoupled and scale-free learning dynamic with regret O(Adifflog⁡mlog⁡(mT))O(A_{\mathrm{diff}}\log m\sqrt{\log(mT)}), 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 O(Adifflog⁡m)O(A_{\mathrm{diff}}\log m) bound of Theorem 1 is open, as stated after Theorem 5 and in Section 5. In our analysis, the factor log⁡(mT)\sqrt{\log(mT)} comes from the ratio between the gradient norms observed by the two players, for which we only have an upper bound polynomial in mm and TT (Lemma 19).

We hope the above addresses your concerns, and we would be happy to clarify any remaining points.

AuthorsOpenReview ↗

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.

Reviewer_VZMmOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies scale-free learning dynamics in repeated games that achieve fast convergence to equilibrium without prior knowledge of the utility scale. For two-player zero-sum games, the authors propose an optimistic Hedge algorithm with an adaptive learning rate and establish an O(Adifflog⁡m)O(A_{\mathrm{diff}}\log m) external-regret bound using a novel analysis based on stopping time, implying an O(Adifflog⁡m/T)O(A_{\mathrm{diff}}\log m/T) convergence rate to Nash equilibrium.

For multiplayer general-sum games, they combine the well-known reduction of Blum & Mansour (2007) that converts swap regret minimization into multiple instances of external regret minimization, optimistic follow-the-regularized-leader (OFTRL) online learning algorithms to instantiate each external regret minimization, hybrid regularizer of Tsuchiya (2026b), and utility clipping to obtain an O(Umaxnm2log⁡mlog⁡T)O(U_{\mathrm{max}}nm^2\sqrt{\log m\log T}) swap regret bound.

Critical strengths

From a theoretical perspective, the problem of designing scale-free learning dynamics seems interesting and relevant. Their two-player zero-sum game result provides a scale-free and scale-agnostic approach that also affirmatively answers the question raised in Zhang et al. (2025) of whether one can retain the scale-free convergence while removing the dependence on the 1/δ1/\delta factor in the regret bound, where δ\delta can be arbitrarily small. Moreover, it seems that they are the first to provide a scale-free and scale-agnostic result of this kind for the swap regret bound in multiplayer general-sum games.

Critical weaknesses
  • The improved scale adaptation is obtained at the cost of requiring coordination among players. In the two-player case, the learning rates depend on gradient-variation information from both players. In the general-sum setting, all players must share statistics to compute a common learning rate. This undermines the real-world applicability of the proposed dynamics, as in decentralized multi-agent learning, players may be autonomous, unwilling to exchange information, or simply unable to coordinate their algorithms.
  • In both settings, each player observes the exact expected utility vector after every round, rather than a sampled outcome. This is quite restrictive for many real-world applications, where sampled or bandit feedback would be more natural.
  • In the context of online learning, the assumption that the horizon TT is known in advance in the multiplayer general-sum setting seems counterintuitive.
Questions for authors
  • Could the authors elaborate on the realism of the considered problem setting and its connection to practical game-theoretic applications? In particular, how realistic is the assumption that each player observes the entire gain vector in the two-player setting or the entire expected utility vector in the multiplayer general-sum setting? It seems that observing only a sampled realization would be more realistic and practically feasible in many applications.
  • In which practical applications are existing scale-free online learning algorithms insufficient? The numerical experiments compare the proposed algorithm with optimistic Hedge variants using fixed and adaptive learning rates, with parameters selected for Amax⁡=1A_{\max}=1. While these experiments illustrate the benefits of scale adaptation, they do not establish an advantage over existing scale-free alternatives. Given the additional communication requirements of the proposed approach, I believe it would be valuable to include comparisons with existing scale-free algorithms to better demonstrate its practical benefits.
  • Would it be possible to include a small-scale numerical experiment illustrating the results obtained for multiplayer general-sum games?
  • Algorithm 1 requires multiple external-regret learners and the computation of stationary distributions. Would it be possible to provide a more explicit discussion of the computational and information-sharing costs compared with existing methods?
  • Would it be possible to develop a version of Algorithm 1 that does not require prior knowledge of the time horizon TT, without significantly weakening the convergence guarantees?
  • Although the paper has a generally clear exposition, it appears incomplete in its current form. In particular, it ends rather abruptly after the discussion of the proof techniques for Theorem 2, without a concluding section addressing the main findings, limitations, and potential directions for future research. I would encourage the authors to consider making some parts of the exposition more concise to accommodate these elements.
7 comments
AuthorsOpenReview ↗

Response to Reviewer VZMm (1/4)

We thank the reviewer for the detailed comments and questions. Our responses are below.

W1. Coordination among players (coupled dynamics)

The improved scale adaptation is obtained at the cost of requiring coordination among players. In the two-player case, the learning rates depend on gradient-variation information from both players. In the general-sum setting, all players must share statistics to compute a common learning rate. This undermines the real-world applicability of the proposed dynamics, as in decentralized multi-agent learning, players may be autonomous, unwilling to exchange information, or simply unable to coordinate their algorithms.

Thanks very much for this important comment. We agree that the learning dynamics of Theorems 1 and 2 are coupled, which is undesirable to compare to uncoupled dynamics. They are nevertheless useful and have technical contributions, and as we discussed below, this is useful to develop uncoupled scale-free learning dynamics.

First, the shared statistics are available when a learning dynamic is used to compute an equilibrium of a given game, which is one of the most important applications of learning dynamics with fast convergence. 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).

In the revised version, we also provide uncoupled learning dynamics for both settings, at the cost of an additional factor in each regret bound. Each player uses only its own observations, and the learning dynamics remain scale-free and scale-agnostic.

  • In two-player zero-sum games, we construct a learning dynamic where the external regret of each player is O(Adifflog⁡mlog⁡(mT))O(A_{\mathrm{diff}}\log m\sqrt{\log(mT)}) (Theorem 5 in Appendix F). This bound is larger than that of Theorem 1 by a factor of log⁡(mT)\sqrt{\log(mT)}.
  • In multiplayer general-sum games, we construct a learning dynamic where the swap regret of player ii is O(Uin3/2m2log⁡mlog⁡T)O(U_i n^{3/2}m^2\log m\sqrt{\log T}) in expectation over the random initial strategies, where Ui≤Umax⁡U_i \le U_{\max} is the scale of the utility function of player ii (Theorem 6 in Appendix G). This bound is larger than that of Theorem 2 by a factor of nlog⁡m\sqrt{n\log m}.

W2. Expected utility vectors instead of bandit feedback

In both settings, each player observes the exact expected utility vector after every round, rather than a sampled outcome. This is quite restrictive for many real-world applications, where sampled or bandit feedback would be more natural.

We agree that bandit feedback, in which each player observes only a sampled outcome, is natural in many applications. In the revised version, we state scale-free fast convergence under bandit feedback as an important direction for future work in the conclusion (Section 5).

The setting with expected utility vectors is the one studied in the literature on fast convergence, including all the existing results in Table 1 (Syrgkanis et al., 2015; Chen & Peng, 2020; Anagnostides et al., 2022b; Tsuchiya et al., 2025; Zhang et al., 2025; Tsuchiya, 2026b). Even in this setting, the existing scale-free bounds either grow as T\sqrt{T} or depend on 1/δ1/\delta for an instance-dependent δ\delta that can be arbitrarily small, and Zhang et al. (2025) raised the question of removing this dependence. Our paper therefore starts from this fundamental setting, and our response to Q1 explains where expected utility vectors are available in practice.

To our knowledge, fast convergence under bandit feedback is known only in an instance-dependent sense, for external regret in two-player zero-sum games (e.g., Ito, Luo, Tsuchiya, and Wu, "Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback," COLT 2025), and whether scale-free fast convergence is possible in this setting is open.

AuthorsOpenReview ↗

Response to Reviewer VZMm (2/4)

W3 and Q5. Known horizon TT in multiplayer general-sum games

In the context of online learning, the assumption that the horizon TT is known in advance in the multiplayer general-sum setting seems counterintuitive.

Would it be possible to develop a version of Algorithm 1 that does not require prior knowledge of the time horizon TT, without significantly weakening the convergence guarantees?

Algorithm 1 can be made horizon-free without worsening the order of the convergence guarantee or introducing restarts.

One possible approach is to adapt the dynamics of Anagnostides et al. (2022b) using essentially the same scale-adaptive learning-rate technique as in our paper. However, this would lead to an O(log⁡T)O(\log T) dependence in the swap regret bound. Instead, we built on Tsuchiya (2026b), which achieved the best-known O(log⁡T)O(\sqrt{\log T}) dependence at the time of preparing our submission, to obtain a sharper scale-free guarantee.

Our approach based on Tsuchiya (2026b) can also be extended to the horizon-free setting. Specifically, we replace log⁡T\log T in the definitions of θ\theta and γ\gamma by 1+log⁡t1+\log t at round tt, while keeping the clipping rule and the form of the OFTRL updates unchanged. The resulting dynamics remain scale-free and achieve the same O(Umax⁡nm2log⁡mlog⁡T)O(U_{\max}nm^2\sqrt{\log m\log T}) swap regret bound. The additional term caused by the time-varying regularizer can be controlled by bounding the log barrier along the OFTRL iterates and applying the path-length argument at a prefix maximizing St/γt\mathbb{S}^t/\gamma^t, where St\mathbb{S}^t is the maximum squared path length in Section 4.3 and γt\gamma^t is the value of γ\gamma at round tt. This extension is based on the time-varying regularization approach in Tsuchiya (2026b, Appendix D), with additional analysis to handle our observation-dependent learning rates.

We did not include this since the aim of our paper is scale-free fast convergence, and making it horizon-free would obscure the arguments that make scale-free fast convergence possible. If the reviewer thinks this is useful, we are happy to mention this.

Q1. Practical relevance of the problem setting

Could the authors elaborate on the realism of the considered problem setting and its connection to practical game-theoretic applications? In particular, how realistic is the assumption that each player observes the entire gain vector in the two-player setting or the entire expected utility vector in the multiplayer general-sum setting? It seems that observing only a sampled realization would be more realistic and practically feasible in many applications.

Observing the entire expected utility vector is realistic 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.

In equilibrium computation, the algorithm runs the learning dynamics of all players and computes the expected utility vectors exactly from the current strategies, for example AytAy^t and A⊤xtA^\top x^t in two-player zero-sum games. Its cost is determined by the number of rounds needed to reach a given accuracy, and fast convergence rates are established in this setting (Daskalakis et al., 2011; Rakhlin & Sridharan, 2013; Syrgkanis et al., 2015). Scale-freeness is regarded as a useful property there, and several studies suggest that such invariance may be important for strong empirical performance (Section 1). Our learning dynamic reaches an ϵ\epsilon-approximate Nash equilibrium in O(Adifflog⁡m/ϵ)O(A_{\mathrm{diff}}\log m/\epsilon) rounds without prior knowledge of the scale of the payoff matrix.

For applications in which only a sampled realization is observed, please see our response to W2 above.

AuthorsOpenReview ↗

Response to Reviewer VZMm (3/4)

Q2. Empirical comparison with existing scale-free algorithms

In which practical applications are existing scale-free online learning algorithms insufficient? The numerical experiments compare the proposed algorithm with optimistic Hedge variants using fixed and adaptive learning rates, with parameters selected for Amax⁡=1A_{\max} = 1. While these experiments illustrate the benefits of scale adaptation, they do not establish an advantage over existing scale-free alternatives. Given the additional communication requirements of the proposed approach, I believe it would be valuable to include comparisons with existing scale-free algorithms to better demonstrate its practical benefits.

Existing scale-free algorithms are insufficient when an equilibrium is computed to high accuracy, that is, when we want to construct dynamics with fast convergence. In the revised version, we added empirical comparisons with scale-free Hedge, which achieves the bounds of the scale-free OLO in Table 1, for two-player zero-sum games (Appendix E.1) and multiplayer general-sum games (Appendix E.2).

The existing scale-free bounds in games are either the O(T)O(\sqrt{T}) regret of scale-free online linear optimization or bounds that depend on 1/δ1/\delta for an instance-dependent δ\delta that can be arbitrarily small (Table 1). The former guarantees an ϵ\epsilon-approximate equilibrium only after on the order of 1/ϵ21/\epsilon^2 rounds, whereas our learning dynamics guarantee it after on the order of 1/ϵ1/\epsilon rounds, up to a logarithmic factor in the multiplayer case.

Two-player zero-sum games. In the revised version, we added scale-free Hedge to the experiments of the submission on 30 random 32×3232 \times 32 games (Figures 1–6 are updated). In Figure 1, we can see that the Nash gap of scale-free Hedge divided by AdiffA_{\mathrm{diff}} does not depend on Amax⁡A_{\max}, but its median at T=104T = 10^4 is about 2929 times ours. When the payoff range AdiffA_{\mathrm{diff}} is small, for example Adiff=10−3A_{\mathrm{diff}} = 10^{-3} with Amax⁡=1A_{\max} = 1, its Nash gap stays close to the initial value even after 10510^5 rounds (Figure 5).

Multiplayer general-sum games. As requested in Q3 below, we conducted experiments also for multiplayer general-sum games in Appendix E.2. We compare our learning dynamic also with scale-free Hedge (Proposition 2 in Appendix C.4) on nine random general-sum games with T=108T = 10^8 rounds (Figure 7). In five of the nine games, the swap regret of scale-free Hedge grows roughly in proportion to t\sqrt{t} and is more than ten times ours at T=108T = 10^8, whereas ours changes little after t=104t = 10^4. In the other four games, scale-free Hedge has smaller swap regret than our learning dynamic with the theoretical learning rate. Scale-free Hedge has no guarantee better than its O(T)O(\sqrt{T}) bound, and it happens to benefit from these particular games. Note also that with a learning rate 2020 times larger than the theoretical choice (as done in existing studies such as Anagnostides et al. (2022b, Appendix D), since the learning rate obtained purely from theory can be conservative), which is not covered by Theorem 2, our learning dynamic has smaller swap regret at T=108T = 10^8 than scale-free Hedge in eight of the nine games.

Q3. Numerical experiment for multiplayer general-sum games

Would it be possible to include a small-scale numerical experiment illustrating the results obtained for multiplayer general-sum games?

Yes. In the revised version, we report experiments on nine random general-sum games with two players and three actions per player, with T=108T = 10^8 rounds (Appendix E.2, Figures 7 and 8). We compare the learning dynamic of Theorem 2 with scale-free Hedge and with optimistic Hedge with the fixed learning rate of Chen & Peng (2020, Theorem 5.1), which is set for Umax⁡=1U_{\max} = 1.

  • At Umax⁡=1U_{\max} = 1, our learning dynamic with the theoretical learning rate has smaller swap regret at T=108T = 10^8 than optimistic Hedge with the fixed learning rate in all nine games (Figure 7). The comparison with scale-free Hedge is in our response to Q2 above.
  • Since our learning dynamic is scale-free, its swap regret divided by Umax⁡U_{\max} does not depend on Umax⁡U_{\max}, whereas that of optimistic Hedge with the fixed learning rate depends on Umax⁡U_{\max} (Figure 8). In all nine games, its value is more than 10410^4 times that of our learning dynamic with the theoretical learning rate at Umax⁡=10−4U_{\max} = 10^{-4} and is smaller than that at Umax⁡=10U_{\max} = 10 and Umax⁡=100U_{\max} = 100. At Umax⁡=104U_{\max} = 10^4, its value exceeds 10410^4 in five of the nine games.

Note that the submission used loose constants in the analysis of Theorem 2 to keep the presentation simple. In the revised version, we tightened these constants so that the learning dynamic of Theorem 2 works well with its theoretical parameters, which reduces the parameter γ\gamma in Eq. (6) from 210m3log⁡T2^{10}m^3\log T to 4e m2(m−1)log⁡T4e\,m^2(m-1)\log T (Appendix C). The statement of Theorem 2 is unchanged.

Reviewer_c2DmOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The authors study scale free learning in online games. In particular, the learning dynamics is invariant under positive scaling of the given utilities. Two main results are provided: a two-player zero-sum game and a multiplayer general-sum game. The authors show that under both setting, the proposed method is scale free with a regret bound that matches similar results when the scale is known.

Critical strengths
  1. the goals, definitions, motivations and constructions of the proposed method are easy to follow and clear. All the concepts are well explained.
  2. the lemmas and the main theorems are well-written and clear to understand. The contributions are clear and well organized.
Critical weaknesses

The constant dependencies on mm and nn is much worse than the OLO method. It is not very clear to me. Besides, we lose the robustness in the main theorem 2.

Questions for authors

Can you provide more comments on the result of Theorem 2, e.g., the nn, mm and the lack of corrupt?

2 comments
AuthorsOpenReview ↗

Response to Reviewer c2Dm

We are grateful to the reviewer for the helpful comments. Our responses are below.

W1 and Q1. Dependence of Theorem 2 on mm and nn compared with OLO

The constant dependencies on mm and nn is much worse than the OLO method. It is not very clear to me.

Can you provide more comments on the result of Theorem 2, e.g., the nn, mm and the lack of corrupt?

Compared with scale-free OLO, the bound of Theorem 2 has a larger dependence on the number of actions mm and the number of players nn, but a much smaller dependence on the number of rounds TT. The dependence on TT determines the convergence rate, and improving it is the focus of the literature on fast convergence in games.

The bound of scale-free OLO is O(Umax⁡mTlog⁡m)O(U_{\max}\sqrt{mT\log m}). It grows as T\sqrt{T} and gives only an O(1/T)O(1/\sqrt{T}) convergence rate to a correlated equilibrium. The bound of Theorem 2 is O(Umax⁡nm2log⁡mlog⁡T)O(U_{\max}nm^2\sqrt{\log m\log T}). It grows as log⁡T\sqrt{\log T} and gives an O(log⁡T/T)O(\sqrt{\log T}/T) convergence rate, and it is smaller than the bound of scale-free OLO for moderately large TT.

A dependence on nn and mm larger than that of OLO is common to all existing results on fast convergence, namely Chen & Peng (2020) with T1/4T^{1/4}, Anagnostides et al. (2022b) with log⁡T\log T, and Tsuchiya (2026b) with log⁡T\sqrt{\log T} (Table 1). These results require the scale Umax⁡U_{\max} in advance. Theorem 2 has the same dependence on nn, mm, and TT as Tsuchiya (2026b) without this requirement. Obtaining this fast rate without knowing the scale is the contribution of our paper.

W2 and Q1. Robustness of Theorem 2

Besides, we lose the robustness in the main theorem 2.

Can you provide more comments on the result of Theorem 2, e.g., the nn, mm and the lack of corrupt?

Robustness to corruption. Sorry for not including the discussion on robustness to corruption for Theorem 2. In fact, the robustness to corruption is not lost in Theorem 2. It can be obtained in the same way as in the two-player case, and we omitted it to keep the paper focused on scale-free fast convergence.

In particular, we prove a square-root dependence on the amount of corruption for two-player zero-sum games (Theorem 3 in Appendix B.4). For Theorem 2 in multiplayer general-sum games, the same corruption robustness can be obtained along the same lines by combining our analysis with that of Tsuchiya et al. (2025, Section 5). No change to Algorithm 1 is needed, since the learning rate in Eq. (6) is determined by the squared path lengths of the observed utility vectors and thus decreases when corruption increases these path lengths. The entry "No" for Theorem 2 in the column "Corrupt\sqrt{\text{Corrupt}}?" of Table 1 means that our paper does not include the analysis of the corrupted regime of Tsuchiya et al. (2025) for Theorem 2.

We omitted this extension for two reasons. The aim of our paper is scale-free fast convergence, and robustness to corruption is not its main contribution. Moreover, the analysis of the corrupted regime in general-sum games is considerably more involved than that of the honest regime (see the analysis leading to Theorem 13 of Tsuchiya et al. (2025, Section 5)). Including it would obscure the arguments that make scale-free fast convergence possible. In the revised version, the caption of Table 1 explains this point.

Robustness against adversarial opponents. In addition, the learning dynamic of Theorem 2 can easily be made robust against adversarial opponents, in the sense of existing work (Syrgkanis et al., 2015; Anagnostides et al., 2022b, Corollary 4.6), that is, its swap regret is O(T)O(\sqrt{T}) even when the other players do not follow it. This is a weaker property than the robustness to corruption above. We did not include this result in the submission since it follows from our analysis by a standard argument, in which the negative term in the regret bound is dropped. In the revised version, we state it as Corollary 1 in Appendix C.5. With a convention for the rounds before the first nonzero utility vector, the swap regret of a player using Algorithm 1 is O(Umax⁡(m2log⁡mlog⁡T+Tmlog⁡m))O(U_{\max}(m^2\sqrt{\log m\log T}+\sqrt{Tm\log m})) for arbitrary utility vectors.

We hope the above addresses your concerns, and we would be happy to clarify any remaining points.

AuthorsOpenReview ↗

Brief follow-up on our response

Thank you very much for taking the time to review our paper. We are also grateful for your question on the comparison with OLO, and we would like to highlight the main point of our answer. The bound of the standard scale-free OLO has a smaller dependence on mm and nn but grows as T\sqrt{T}, whereas the bound of Theorem 2 grows as log⁡T\sqrt{\log T}. This improves the convergence rate from O(1/T)O(1/\sqrt{T}) to O(log⁡T/T)O(\sqrt{\log T}/T), which is the focus of the literature on fast convergence in games.

We hope that our response resolves your concerns, and we would be grateful if you could take it into account in your final assessment. We are happy to clarify any remaining points.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of revisions

We would like to sincerely thank all reviewers for taking the time to carefully review our paper and for their comments. Our responses to each reviewer are posted separately. The main changes in the revised version are listed below. New text is shown in dark blue, and for the new sections and subsections only the titles are in dark blue.

  1. Uncoupled scale-free learning dynamics. Appendix F gives uncoupled, scale-free, and scale-agnostic learning dynamics for two-player zero-sum games with external regret O(Adifflog⁡mlog⁡(mT))O(A_{\mathrm{diff}}\log m\sqrt{\log(mT)}) (Theorem 5). Appendix G gives uncoupled learning dynamics for multiplayer general-sum games in which the expected swap regret of player ii is O(Uin3/2m2log⁡mlog⁡T)O(U_i n^{3/2}m^2\log m\sqrt{\log T}) (Theorem 6). The latter are also invariant under rescaling the utility function of each player by a different positive constant (Definition 3). (In response to the comments of Reviewers VZMm and xwMi)
  2. Adversarial robustness (Corollary 1 in Appendix C.5). (In response to the comments of Reviewer c2Dm)
  3. A comparison with scale-free Hedge in the experiments for two-player zero-sum games (Appendix E.1), and new experiments for multiplayer general-sum games, which also include scale-free Hedge (Appendix E.2). (In response to the comments of Reviewer VZMm)
  4. A concluding section (Section 5) and a discussion of recent logarithmic and TT-independent regret bounds (Appendix D). (In response to the comments of Reviewers VZMm and xwMi)
  5. Table 1 has a new column "Uncoupled?", rows for Theorems 5 and 6, and notes on the entries "No" of our results in the column "Corrupt\sqrt{\text{Corrupt}}?". (In response to the comments of Reviewer c2Dm)
  6. Tighter constants in the analysis of Theorem 2 for multiplayer general-sum games (Appendix C), so that its learning dynamic works well with the theoretical parameters in the experiments of Appendix E.2. This changes the parameter γ\gamma in Eq. (6), and the statement of Theorem 2 is unchanged. (In response to the comments of Reviewer VZMm)

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.