acceptodds
Withdrawn from ICLR 2027

Constant Swap Regret in General-Sum Games via Two-Scale Higher-Order Optimism

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

We give deterministic and uncoupled learning dynamics for finite multiplayer general-sum games under full-information feedback that achieve constant individual swap regret in self-play, independent of the horizon . With players and at most actions each, every player’s individual swap regret is at every finite horizon. The dynamics use the classical Blum–Mansour framework with optimism. Each player predicts the deviation gains, uses these predictions to update a row-stochastic transition matrix, and plays its stationary distribution. Our new ingredients include a tailored row normalization map and a two-scale higher-order predictor. An adversarially robust variant, obtained through a generic common-prefix switching wrapper, preserves the self-play bound up to a universal constant and guarantees individual swap regret at most in the adversarial setting.

Primary area:
learning theory
Keywords:
swap regret, self-play, online learning, no-regret learning, general-sum games

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_EZvXOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper derives new bounds for individual swap regret in multiplayer general sum games. The authors study the Blum-Mansour (BM) algorithm instantiated with OFTRL subroutines using higher-order optimism (following the recent advances in OFTRL variants for external-regret minimization in games). They prove that the simultaneous use of this algorithm in general-sum games yields individual swap-regret bounds that are constant in the time horizon T (and with polynomial dependences on the number of players and the sizes of the action sets). This improves over prior state-of-the-art swap-regret bounds that achieved poylogarithmic bounds in T.

Critical strengths

The main strength of the paper is the improved rate for individual swap regret in general-sum games. The result seems to indicate that the classical BM framework is amenable and robust to improved algorithms for external regret minimization. Indeed, the main algorithmic idea of the present work is to incoporate and adapt into BM the recently-introduced higher-order-optimism variants of OFTRL as the base learners.

The authors also establish an adversarial swap-regret guarantee for their new algorithm.

Critical weaknesses

In my view, the paper's main weakness is in the quality of writing. While the technical overview in Section 1 was presented well and gave good initial intuition for the main technical ideas, Sections 4 and 5 were very difficult to follow and feel lacking in intuition. In particular, the start of Section 4 and Subsection 4.1 introduce most of the core objects used in the analysis, e.g., the "curvature energy", but I felt this section offers almost no intuition or discussion as to how to interpret these objects. This makes the remainder of the analysis feel somewhat opaque.

Questions for authors

Suggestions: the continued use of the word "public" when describing parameters, constants, etc. Perhaps it could be clarified what exactly is meant here, e.g., that these parameters or constants are globally known?

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

This paper proposes a learning algorithm for finite multiplayer general-sum games that achieves constant individual swap regret in self-play, independent of the time horizon TT. To the best of my knowledge, this is the first result establishing a time-independent swap-regret bound in this setting. The paper also provides an adversarially robust variant that retains the standard O(T)O(\sqrt{T}) regret guarantee.

Critical strengths

Achieving constant swap regret in general-sum games is a significant theoretical advance over previous results with logarithmic dependence on TT. On the technical side, the two-scale higher-order expansion and the use of curvature terms to control prediction errors are particularly interesting and constitute the main novel ingredients of the analysis.

Critical weaknesses

The constants involved in the theoretical guarantees appear to be quite large, potentially limiting the practical applicability of the proposed algorithm. However, I do not consider this a major weakness, given the primarily theoretical nature of the contribution.

Questions for authors

Could the authors clarify why existing constant-regret algorithms, such as ECHO and HOOD, cannot be directly extended to achieve constant swap regret in this setting? In particular, which specific steps of their analyses fail when combined with the Blum–Mansour reduction, and how does the proposed two-scale expansion overcome these difficulties?

Reviewer_zjMCOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes uncoupled learning dynamics that achieve O(nmlog⁡mlog⁡5/2(nm))O(\sqrt{n}m\log m\log^{5/2}(nm)) individual swap regret in general-sum games (under self-play), independent of the time horizon TT. Given recent results establishing constant external regret, it was perhaps expected that constant swap regret could also be achieved. However, the dependence of the regret bound on the number of players nn and the parameter dd is strikingly good.

Critical strengths

Convergence to correlated equilibrium (CE) via uncoupled learning dynamics is a major problem in algorithmic game theory, and the convergence rate established by the authors is particularly impressive.

Critical weaknesses

The current quality of the write-up is a serious concern for me. I think the result is very strong, but the main ideas are extremely difficult to follow. Many parts of the paper need a major revision.

For example, Section 3.1 introduces a rather complicated row normalization map in Eq. (3.1). Why is this particular construction needed? What properties are essential? Similarly, Eq. (3.3) introduces a higher-order predictor involving two EMA cascades and an additional third-order difference. Why exactly these two scales? Why these particular depths? It is difficult to see how the authors arrived at this construction from the main challenge they want to address. The same issue appears in the proof. Section 4.3 introduces independent tree samples and various "atoms," while Section 4.4 switches to tracking repeated transitions using the decomposition in Eq. (4.12). These seem to be the main new technical ideas, but it seems the reader has to go through a large amount of notation before understanding why they are useful. I can keep enumerating ...

I strongly suggest that the authors rewrite the paper with a clearer picture of what they want to communicate. This is a strong mathematical result, and it deserves a much better exposition. I am willing to reconsider if the write-up is improved substantially.

Questions for authors

Could the authors explain more directly what the main mathematical novelty is compared with previous higher-order optimism analyses? In particular, what is the essential new idea that makes constant swap regret possible?

Is the specific normalization map in Eq. (3.1) necessary, or could the analysis work with a broader class of regularizers albeit with some conditions? Which properties are actually essential?

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

Related papers

Discussion (0)

Sign in to comment.