acceptodds
Under review as a conference paper at ICLR 2027

Convergence and Implicit Bias of Softmax Extragradient Flow in Bilinear Zero-Sum Games

Abstract

Many learning problems optimize over probability distributions represented by softmax logits. Although extragradient enjoys strong guarantees for convex-concave games in policy space, its behavior under softmax parameterization is less understood: even bilinear games become nonconvex-nonconcave in logit space, and boundary equilibria correspond to logits at infinity. We study the high-resolution ODE of the extragradient method in softmax-parametrized skew-symmetric bilinear zero-sum games under symmetric self-play. We establish ***global convergence*** under two structural conditions. First, if there is an interior equilibrium, every trajectory converges in logit space. Second, under a condition we call *flat dominance*, we show convergence of every trajectory to the Nash set, with explicit rates. We further characterize the initialization-dependent ***implicit bias*** of the dynamics: which policy is selected? Conditional on policy convergence, we show that the trajectory must converge to a Nash equilibrium (NE). Under flat dominance, almost every such initialization leads to a *pure-strategy* NE. We further prove policy convergence for two structured classes of games and derive an explicit initialization-dependent NE selection rule. Finally, we present numerical experiments illustrating our theoretical results.

Primary area:
optimization
Keywords:
zero-sum game, extragradient flow, softmax parameterization, convergence, implicit bias

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_QxQCOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper considers the bilinear skew-symmetric matrix games where each policy is parameterized by a softmax representation. In this game, the authors study the continuous-time Euclidean extragradient applied directly in softmax-logit space, and provide a set of results on convergence, boundary behavior, and equilibrium selection of extragradient flow in the original bilinear game. In particular, the paper identifies two cases (interior NE, ‘flat dominance’) where the direct extragradient achieves global convergence in different senses. The implicit bias characterizes the extragradient flow, including a theorem saying the trajectory almost goes to pure NE instead of mixed Nash equilibrium assuming ‘flat dominance’ and the point-wise convergence in the policy space.

Critical strengths
  • The paper studies an important and interesting problem, given the major applications in neural networks and the nonconvex-nonconcave properties of the logit space.
  • The paper provides a set of results on boundary behaviors and equilibrium selection, which seems to be missing in this setting. These results look interesting to me.
Critical weaknesses
  • The scope of this paper is kind of limited compared to previous work. Even though the specific setting: skew-symmetric matrix games, softmax representation are well-motivated, this setup is more restrictive than, e.g., Vlatakis-Gkaragkounis et al. (2021).
  • The global convergence is meaningful but not very new, especially considering the specific class of games considered in the paper and the two required conditions.
  • (minor) “Nash set”, “Nash convergence”, “Nash face” were used without clear definitions.
Questions for authors
  • Are there any necessary conditions under which the dynamics converges? It seems like the interior NE and flat dominance are not necessary for convergence to the set of NE.
  • What is the benefit of applying the Euclidean extragradient directly in the logit space, compared to using natural gradient algorithms which correspond to OMWU and have better convergence properties?
3 comments

We sincerely thank the reviewer for their careful review, and for recognizing the significance of our research question and theoretical results. We address their points below.

W1. Limited scope of the paper

We believe there is a misunderstanding here: Our setup is not subsumed by [1]; there are two distinctions between the two settings.

First, the parameterizations differ. [1] analyzes the class of games min⁡θ∈RNmax⁡ϕ∈RML(F(θ),G(ϕ))\min_{\theta\in\mathbb R^N} \max_{\phi\in\mathbb R^M} L(F(\theta), G(\phi)), where each coordinate of F,GF, G is controlled by disjoint sets of variables. Specifically, F:RN→RnF: \mathbb R^N \to \mathbb R^n is computed as F(θ)=[f1(θ1)…fn(θn)]⊤F(\theta) = [f_1(\theta_1) \ldots f_n(\theta_n)]^\top where θ=[θ1…θn]⊤\theta = [\theta_1 \ldots \theta_n]^\top is partitioned into nn groups and fif_i are C2C^2 scalar-valued functions. G:RM→RmG: \mathbb R^M \to \mathbb R^m is similarly defined for disjoint ϕ1,…,ϕm\phi_1, \ldots, \phi_m and g1,…,gmg_1, \ldots, g_m. In contrast, our softmax parameterization couples every output to all logits through the shared normalization; it does not fall into this class of games.

Second, the convergence assumptions differ. The convergence guarantees in [1] require a strict convex-concave property of the utility LL. Namely, LL is strictly convex-concave if it is convex-concave, and either L(⋅,y)L(\cdot, y) is strictly convex or L(x,⋅)L(x, \cdot) is strictly concave for every (x,y)(x,y). When this strictness is absent, [1] introduces L2 regularization and obtains convergence for a perturbed game. In contrast, we establish convergence and implicit-bias results for unregularized bilinear zero-sum games, whose utility is not strictly convex-concave.

We have further clarified these distinctions in the revised manuscript.

[1] EV Vlatakis-Gkaragkounis et al. Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent. In NeurIPS 2021

W2. Novelty of global convergence

Thank you for raising this. Our two global convergence results use alternative sufficient conditions. When the game has an interior equilibrium, S2P-EG-Flow converges in logit space for every γ>0\gamma>0 (Theorem 3.1). Under flat dominance and the stated bound on γ\gamma, it converges in the Nash sense (Theorem 3.2).

Each assumption imposes structure on the underlying game, but the objective in the logits remains nonconvex–nonconcave. This places the logit dynamics outside the scope of standard convex–concave guarantees. A PŁ-based argument would require establishing a suitable inequality in the logits, and entropic regularization would change the objective. The softmax parameterization also gives the game a hidden bilinear structure. S2P-EG-Flow models Euclidean extragradient applied directly in the logits, so prior analyses that exploit this hidden structure by changing the update geometry concern a different flow.

Our technical contribution is to establish global convergence for the unregularized Euclidean logit dynamics under these structural assumptions, despite these difficulties. We found it surprising that this flow admits an equilibrium-anchored Lyapunov potential. We believe that our proof flow, combining conservation of the logit sum induced by softmax with dynamical-systems tools such as LaSalle’s invariance principle, may also help analyze related nonconvex–nonconcave problems.

Extending the boundary convergence guarantee beyond flat dominance would strengthen the results, and we leave this to future work. Our Remark 1 shows that even convergence in the Nash sense can fail in a game with only boundary equilibria, so some restriction on the game class is needed for a global guarantee.

W3. Terminology

We revised the terminology and marked the changes in blue. We explicitly identified SN(A)\mathcal S\mathcal N(A) as the Nash set in Section 2. We replaced "Nash convergence" with "convergence in the Nash sense". Under flat dominance, the Nash face coincides with the Nash set (Proposition K.2). We replaced "Nash face" with "Nash set" or rephrased it.

Q1. Necessary conditions for convergence

It is true that neither condition is necessary; Proposition J.1 implies that convergence in the Nash sense can happen in the absence of both conditions. However, the necessary conditions for convergence are expected to be highly nontrivial to characterize, and initialization should be taken into account. Indeed, Proposition J.2 shows that convergence fails by simply changing the initial values even under the same game. The observation that convergence depends on initialization is somewhat expected, since the game is nonconvex-nonconcave due to the softmax parameterization.

Q2. Benefits of applying EG in logit space

We do not claim that Euclidean extragradient (EG) applied directly in logit space offers an algorithmic advantage over natural-gradient methods such as OMWU. Rather, our motivation is to understand the convergence behavior and implicit bias of a standard first-order minimax method applied directly to softmax-parameterized models. Indeed, softmax parametrization is widely used in machine learning, where gradient-based optimization methods are commonly applied directly in the parameter space (see our Introduction for relevant references). EG is a natural choice in this setting, given its established role in mitigating the instability caused by rotational dynamics in minimax optimization.

We believe that our setting provides a useful theoretical testbed for understanding several challenges arising in modern minimax optimization. Although the underlying game is bilinear, softmax parameterization induces a nonconvex-nonconcave problem in logit space, where standard convex-concave convergence guarantees do not directly apply. Moreover, boundary equilibria can only be approached through diverging logits, and the Euclidean dynamics do not explicitly exploit the hidden bilinear structure. Consequently, even establishing convergence, let alone characterizing the limiting policy, is nontrivial.

Our contribution is to show that, despite these difficulties, the high-resolution EG flow admits a detailed theoretical characterization. In particular, we establish global convergence under two structural conditions, derive sharp convergence rates to boundary equilibria, and characterize initialization-dependent equilibrium selection. These results provide insight into how softmax parameterization shapes the behavior of a standard minimax optimization method, rather than establishing its superiority over natural-gradient algorithms.

I thank the authors for the clarifications and for answering my questions. I think this work indicates some interesing future directions, e.g., studying learning dynamics in the logit space, studying more general minimax optimization instances. The results in this paper are meaningful, although I think simpler (alternating) gradient-descent-ascent algorithm might be more standard first-order minimax method in practice. I lean towards acceptance.

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

The paper studies skew-symmetric zero-sum bilinear games reparameterized with the softmax map. The method analysed in the paper is the continuous flow of the extra-gradient algorithm under self-play (which suffices for games with symmetric equilibria), coined Softmax Self-play Extragradient Flow or S2P-EG-Flow. The paper’s results can be categorized into two directions. First, the authors establish the following convergence results: a) Linear convergence after an initial time period for games with an interior equilibrium and b) (sublinear) convergence for games that satisfy flat dominance; this is a notion that requires a partition of the support into two sets II and JJ such that every strategy in II is strictly better than every action in JJ. In a sense this notion generalizes quasi-strictness, as the relative interior of II coincides with the set of quasi-strict equilibria. This difference appears qualitatively in the convergence analysis of boundary equilibria as well. Second, they treat the problem of equilibrium selection. There it is proved that if the method converges then the limit is a symmetric NE. Moreover, they prove that under almost every initialization for three special cases (including the flat dominance assumption) the flow converges to a vertex and not a mixed profile. The main tools used for the analysis are high-resolution ODEs and a series of results from dynamical systems.

Critical strengths

The authors present an array of results that are highly non trivial from a technical standpoint. Conceptually, I also found the assumption on flat dominance interesting and could potentially apply to other settings as well.

Critical weaknesses

The paper’s treatment is limited to symmetric games only. Moreover, and while I understand this is due to space constraints, the proof sketches, especially in Section 3, are quite short and do not provide enough intuition.

Questions for authors
  1. Could the authors provide a bound on T in the statement of Theorem 3.1? Specifically, is it polynomially bounded in the description of the game?
  2. Are there any results that carry over to non symmetric games?
2 comments

We sincerely thank the reviewer for their careful review, for recognizing the significance of technicality, and for finding the flat dominance assumption intriguing. We address their points below.

W1, Q2. Beyond symmetry of the game

We thank the reviewer for raising this question.

The role of skew-symmetry. Skew-symmetry makes the diagonal (θ=φ\theta=\varphi) invariant under the two-player EG dynamics, allowing reduction to our single-policy S2P-EG flow. It also plays a central role in the Lyapunov construction and boundary analysis underlying our global convergence and implicit bias results (Theorems 3.1–3.2 and 4.2–4.4). These results therefore do not immediately extend to general two-player zero-sum games.

Extensions beyond symmetry. Two of our results extend by analyzing the players separately. First, the argument of Theorem 4.1 extends to nonsymmetric two-player zero-sum games: under a sufficiently small stepsize, convergence of both policies implies that their limit is a Nash equilibrium. Second, the boundary-rate results (Theorem 3.3 and Corollary 3.4) extend player-wise, using separate logit conservation laws and intrinsic clocks. In particular, positive-margin boundary actions retain the t−1t^{-1} decay rate, with coefficients determined by each player's support size and equilibrium margins. We note that these extensions do not imply global convergence of the two-player dynamics.

Our focus on skew-symmetric games is also motivated by pairwise preference learning, where reciprocal comparisons naturally yield skew-symmetric payoff matrices and allow for intransitive preferences without requiring an underlying scalar utility function. Such formulations have been widely studied in preference-based alignment and self-play (Munos et al., 2024; Swamy et al., 2024; Wu et al., 2025). Thus, our setting is motivated by preference-based learning as well as analytical tractability.

We have clarified these extensions in the Conclusion, with supporting mathematical arguments provided in the appendix (highlighted in blue). While the conditional Nash-limit and boundary-rate results extend beyond skew-symmetry, establishing global convergence and implicit-bias guarantees for general two-player zero-sum games remains an interesting direction for future work.

W2. Proof sketches lacks intuitions

We thank the reviewer for this helpful suggestion. We agree that additional intuition would improve the accessibility of our proof sketches, particulary for Theorem 3.3.

To address this concern, we have added a concise proof sketch immediately following Theorem 3.3 in the revised manuscript (highlighted in blue). The new sketch outlines the key steps of the argument, explaining how the intrinsic clock and logit conservation lead to different convergence rates. We hope this addition helps readers better understand the intuition behind the theorem, while the complete technical proof remains availabe in Appendix G.1. If the reviewer has any other specific suggestions, please let us know.

Q1. Polynomial Bound for TT in Theorem 3.1

Thank you for this question. In the proof of Theorem 3.1, LaSalle’s invariance principle (Theorem B.3) shows that the trajectory eventually approaches the equilibrium manifold. Once the trajectory enters a suitable neighborhood of an equilibrium, the local asymptotic-phase theorem (Theorem B.5) gives exponential convergence. Due to the asymptotic nature of LaSalle's principle, it is unclear how to further quantify TT, at least in the current proof. We defer the question of whether TT admits a polynomial bound in the game description to future work.

I thank the reviewers for reading my review and for answering my question. I will maintain my score.

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

This paper studies the convergence and implicit bias of extragradient dynamics in softmax-parameterized bilinear zero-sum games. The authors focus on skew-symmetric games under symmetric self-play and analyze a high-resolution continuous-time ODE associated with extragradient in logit space.

The paper establishes global convergence when an interior Nash equilibrium exists and convergence to the Nash set under a structural condition called flat dominance, together with explicit convergence rates. It further investigates equilibrium selection, showing that under flat dominance, almost all convergent trajectories select a pure-strategy Nash equilibrium. For two structured classes of games, the authors establish policy convergence and characterize the selected equilibrium. Numerical experiments on small games illustrate these theoretical findings.

Critical strengths
  1. Technically interesting convergence analysis. The paper establishes nontrivial convergence guarantees for extragradient dynamics in softmax-logit space, where the original convex-concave structure is lost. The distinction between interior and boundary equilibria, together with the characterization of convergence rates, is theoretically interesting.

  2. Characterization of equilibrium selection. The implicit bias results under flat dominance provide an interesting characterization of how the parameterization and initialization influence the selected Nash equilibrium. In particular, the almost-everywhere selection of pure-strategy equilibria is a noteworthy theoretical observation.

Critical weaknesses
  1. Insufficient motivation for the research question and its significance.

Although the mathematical results are interesting, I find the broader motivation for studying this particular learning dynamics insufficiently developed. The paper addresses a rather specialized question that may primarily appeal to researchers already deeply familiar with learning in games.

In particular, I have difficulty understanding the significance of the flat dominance assumption and the resulting implicit bias. What meaningful classes of games or practical situations are captured by flat dominance? Furthermore, even if we understand which Nash equilibrium is selected, what does this achieve from the perspective of equilibrium computation? Under flat dominance, all mixtures over the retained strategies are Nash equilibria, so it is unclear why selecting a pure-strategy equilibrium should be considered particularly meaningful or consequential.

I do not dispute the mathematical interest of these results. However, the paper would benefit from a more convincing explanation of why these specific questions matter beyond their theoretical characterization.

  1. Unclear positioning between practical algorithm analysis and dynamical systems theory.

I find it somewhat unclear whether the primary goal is to understand learning algorithms used in practice or to establish mathematical properties of a particular class of nonconvex-nonconcave dynamical systems.

If the former is the main motivation, I would expect a more direct investigation of discrete-time extragradient and comparisons with other learning algorithms. In particular, it would be important to understand whether the observed equilibrium-selection behavior is specific to extragradient or also arises under standard softmax gradient dynamics.

If the latter is the intended contribution, the paper should more clearly explain why the pure-strategy selection result under flat dominance is mathematically nontrivial relative to existing dynamical systems theory, and what conceptual insights it provides beyond the particular setting considered.

Questions for authors
  1. Motivation for flat dominance: Could the authors provide concrete examples or applications in which flat dominance is a meaningful structural assumption? Why is this class of games particularly important to study?

  2. Significance of implicit bias: What is the implication of selecting a pure-strategy Nash equilibrium rather than a mixed-strategy Nash equilibrium under flat dominance? Does this selection offer any advantage in equilibrium computation, or is the main contribution purely descriptive?

  3. Role of extragradient: To what extent is the pure-strategy selection phenomenon specific to extragradient? Could similar results be obtained for the standard softmax gradient flow without the extragradient correction? A theoretical explanation or an experimental comparison would help clarify the contribution.

  4. Intended scope of the contribution: Is the main objective to understand the behavior of practically used softmax-parameterized learning algorithms, or to develop a theoretical analysis of a particular dynamical system? If the former, how closely do the continuous-time results reflect discrete-time extragradient? If the latter, what makes the results under flat dominance particularly significant from a dynamical systems perspective?

3 comments

We sincerely thank the reviewer for their thoughtful questions about the motivation for flat dominance, the significance of pure-strategy selection, and the role of extragradient in the dynamics. We address these points below.

W1-1, Q1. Significance of flat dominance

Flat dominance provides a tractable setting for studying implicit equilibrium selection in games with multiple Nash equilibria. In particular, it separates the elimination of dominated actions from the selection among tied dominating actions. We further motivate this assumption through its connection to preference learning and illustrate it with two concrete examples.

Connection to preference learning. Flat dominance captures preference structures in which a subset of actions is preferred over all remaining actions, without requiring a consistent ranking among the latter. When ∣I∣=1|I|=1, this corresponds to the classical Condorcet-winner assumption studied in dueling bandits [1,2]. When ∣I∣>1|I|>1, the dominating actions are weak Condorcet winners, a related notion in social choice theory [3–5]. Such preference structures are relevant to applications including information retrieval, where alternatives can be difficult to distinguish [6], and pairwise preferences may exhibit nontransitive cycles [1, Appendix 8.1].

To illustrate how flat dominance arises in these settings, we consider two examples: one based on scalar utilities with multiple optimal actions, and another allowing nontransitive preferences.

Example 1: Bradley–Terry preferences with tied utilities. Let Aij=σ(uj−ui)−1/2A_{ij}=\sigma(u_j-u_i)-1/2, where σ\sigma is the sigmoid function and uiu_i denotes the utility of action ii. Suppose ui=u⋆u_i=u_\star for all i∈Ii\in I and uj<u⋆u_j<u_\star for all j∈Lj\in L. Then AI,I=0A_{I,I}=0 and AL,I=a1⊤>0A_{L,I}=\mathbf{a}\mathbf{1}^\top>0, where aj=σ(u⋆−uj)−1/2>0a_j=\sigma(u_\star-u_j)-1/2>0. Thus, flat dominance holds.

Example 2: Tiered rock-paper-scissors games. Consider two dominating actions that tie against each other and strictly beat three dominated actions forming a rock-paper-scissors cycle. The dominating actions may have different winning margins against the dominated actions. This satisfies flat dominance while allowing nontransitive preferences that cannot generally be represented by scalar utilities.

In both examples, the Nash set is the simplex over the dominating actions, so convergence to the Nash set alone does not determine the limiting policy. Moreover, although the dominated actions vanish in probability space, their residual influence can determine which equilibrium is selected. Our results show that, conditional on policy convergence, almost every initialization selects a pure-strategy equilibrium (Theorem 4.2), and further characterize convergence and selection for structured classes (Theorems 4.3–4.4). Thus, flat dominance allows us to investigate how softmax dynamics select among multiple equilibria, beyond merely establishing equilibrium convergence.

We have added these examples and the corresponding motivation immediately after Assumption 1 in the revised manuscript (highlighted in blue).

[1] M. Zoghi et al. Relative Upper Confidence Bound for the K-Armed Dueling Bandit Problem. ICML (2014).

[2] B. Chen & P. I. Frazier. Dueling Bandits with Weak Regret. ICML (2017).

[3] D. S. Felsenthal & T. N. Tideman. Weak Condorcet Winner(s) Revisited. Public Choice (2014).

[4] I. J. Good. A Note on Condorcet Sets. Public Choice (1971).

[5] J. H. Smith. Aggregation of Preferences with Variable Electorate. Econometrica (1973).

[6] X. Yan et al. Human Preferences as Dueling Bandits. SIGIR (2022).

W1-2, Q2. Significance of implicit bias

Thank you very much for raising this distinction. Our contribution is descriptive in the sense that it identifies a bias toward pure limiting policies in games that admit both pure and mixed equilibria. We study this bias in the softmax extragradient flow, a minimal model of symmetric self-play in which both players update their policies directly in logit space, in softmax-parametrized bilinear game over simplex.

If the goal is to compute any Nash equilibrium, either a pure or a mixed equilibrium suffices. By von Neumann’s minimax theorem, both attain the same value in a two-player zero-sum game. Yet, equilibria with the same value can differ in which actions they use and how stable they are under a given learning rule; in game theory, this has been extensively studied under the name equilibrium selection [1]. They can also yield different payoffs against the same opponent who departs from equilibrium play [2,3]. For example, in our toy game A1A_1 (described in Section 5), the pure equilibrium e2e_2 weakly dominates every other Nash strategy and earns twice as much as e1e_1 whenever the opponent plays a dominated action with positive probability. In A2A_2 (also described in Section 5), if the opponent assigns a fixed total probability ε>0\varepsilon>0 to actions 3 and 4, the mixed equilibrium 35e1+25e2\frac35 e_1+\frac25 e_2 guarantees a payoff of 115ε\frac{11}{5}\varepsilon for any split of that probability. The worst-case payoff of either pure equilibrium is ε\varepsilon. Our goal is not to argue that pure-strategy equilibria are necessarily preferable to mixed-strategy equilibria, but rather to characterize and explain the implicit bias of the learning dynamics toward pure-strategy equilibria. As illustrated by the examples above, different equilibria can have different consequences, making it important to understand which equilibrium is selected by the learning dynamics.

Finally, we note that the question of which equilibrium emerges under a given learning dynamics (e.g., when players adapt their policies via softmax extragradient flow) has been extensively studied in evolutionary game theory [4,5] and the modern minimax optimization literature [6,7]. A similar phenomenon of implicit bias is of great interest in deep learning theory, where characterizing the minimizer selected by an optimizer [8] or the limiting direction of its iterates [9] helps explain how the optimization rule shapes the learned model.

We have added this discussion to the Introduction in blue to clarify the motivation for our equilibrium-selection result. Thank you again.

[1] J. C. Harsanyi & R. Selten. A General Theory of Equilibrium Selection in Games. MIT Press (1988)

[2] R. Selten. Reexamination of the Perfectness Concept for Equilibrium Points in Extensive Games. International Journal of Game Theory (1975)

[3] G. Farina & T. Sandholm. Equilibrium Refinement for the Age of Machines: The One-Sided Quasi-Perfect Equilibrium. In NeurIPS 2021

[4] L. Samuelson. Evolutionary Games and Equilibrium Selection. MIT Press (1997)

[5] M. Bernasconi et al. The evolutionary dynamics of soft-max policy gradient in multi-agent settings. Theoretical Computer Science (2025).

[6] S. Chen et al. Unregularized Linear Convergence in Zero-Sum Game from Preference Feedback. arXiv preprint arXiv:2512.24818 (2025)

[7] K. Lee and D. Kim. Zero-Infinity GAN: Stable Dynamics and Implicit Bias of Extragradient. In NeurIPS 2025 OPT Workshop

[8] S. Gunasekar et al. Characterizing Implicit Bias in Terms of Optimization Geometry. In ICML 2018

[9] D. Soudry et al. The Implicit Bias of Gradient Descent on Separable Data. Journal of Machine Learning Research (2018)

W2, Q4. Positioning of the paper

Our main goal is the latter: to theoretically characterize how softmax parametrization shapes extragradient dynamics applied directly in logit space. Softmax transforms a simplex-constrained bilinear game into a nonconvex–nonconcave game in logits and represents boundary policies only as limits of diverging logits. Prior work has studied how hidden bilinear structure can be used to analyze and design learning dynamics [1,2]. Our interest is in gradient-based updates applied directly in logit space without adapting the update geometry to the hidden structure, motivated by the direct optimization of parametrized models in deep learning.

Flat dominance simplifies the interactions among actions and yields convergence in the Nash sense: the probability mass over dominated actions, ρ(t)\rho(t), decays to zero. However, convergence in the Nash sense alone does not guarantee convergence to a single policy when the Nash set contains a continuum of equilibria. Furthermore, standard arguments about local stability around isolated finite equilibria do not directly apply to such continua.

The key mechanism is that dominated actions exert an unbounded influence on dominating actions: ρ(t)=Θ(t−1)\rho(t)=\Theta(t^{-1}) implies ∫0∞ρ(t)dt=∞\int_0^\infty\rho(t) dt=\infty. We introduce blow-up coordinates to retain the relative proportions within dominating and dominated actions, along with a rescaled clock, thereby revealing the persistent influence of dominated actions. In this system, we show that an equilibrium corresponding to a limiting support of size ss has s−1s-1 unstable directions. This stability in the blow-up coordinate is also connected to the original flow, demonstrating that almost every initialization that converges to a policy selects a pure-strategy equilibrium. Therefore, the technical contribution of implicit bias is to justify a boundary system that retains the influence of dominated actions.

Conceptually, this shows how the geometry induced by softmax can favor pure strategies even when a continuum of policies has the same equilibrium value, and the actions absent from the limiting policy could determine which equilibrium is selected. Such behavior cannot be captured solely by the geometry of the Nash set. The approach may also help analyze other parametrized dynamics whose equilibria correspond to diverging parameters.

[1] L. Flokas et al. Poincaré Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Games. In NeurIPS 2019

[2] S. Pattathil et al. Symmetric (Optimistic) Natural Policy Gradient for Multi-Agent Learning with Parameter Convergence. In AISTATS 2023

Q3. Role of Extragradient

After revisiting our proofs, we are happy to share that all of our main theoretical results except Theorem 3.1 extend to standard softmax gradient flow (γ=0\gamma=0). We have marked these extensions in blue in the main text and appendices.

First, Theorem 3.1 requires γ>0\gamma>0. When an interior equilibrium exists, gradient flow conserves the Lyapunov potential in Appendix F. The extragradient correction makes this potential strictly decrease away from equilibrium and damps rotation. Figure 1(a,d) in Section 5 illustrates this in rock–paper–scissors, where gradient flow keeps cycling and the extragradient flow converges exponentially in logit space.

For the remaining results, the first-order term already provides the relevant drift. Under flat dominance, the positive payoff margins of dominated actions drive their total probability mass ρ(t)\rho(t) to zero at rate Θ(t−1)\Theta(t^{-1}) (Theorem 3.2). Near the Nash set, the gradient term is O(ρ)O(\rho) and the extragradient correction is O(γρ2)O(\gamma\rho^2). After the time rescaling dτ=ρ,dtd\tau=\rho\\,dt, the correction is O(γρ)O(\gamma\rho) and vanishes as ρ→0\rho\to0 for every fixed γ\gamma. Both flows therefore have the same limiting boundary dynamics (Appendix D), and the stability analysis underlying Theorems 4.2–4.3 applies to gradient flow as well. The boundary rates likewise use the first-order payoff margins at the limiting policy (Appendix G). In the rank-one case, the adjusted inverse-weight differences in Appendix H are constant at γ=0\gamma=0, yielding the same explicit selection rule as in Theorem 4.4.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.