Algorithmic Asymmetry in Zero-Sum Games: Unilateral Recovery of Fast Convergence Against a Slow Opponent

This paper studies algorithmic asymmetry in learning dynamics for zero-sum games, asking whether fast convergence can be recovered when one agent is fixed to vanilla gradient descent (GD), whose standard regret-based analysis certifies, at best, O(1/√T) ergodic convergence. The authors show that the slow rate is not intrinsic and that "when one agent uses gradient descent, the opposing agent can use a modified optimistic update, which we call Alternating Optimistic Gradient Descent (AOGD), to make the joint dynamics simulate Alternating Gradient Descent on the even iterates. As a result, the time-average of the asymmetric GD vs. AOGD dynamics converges to Nash equilibria at rate O(1/T)."

The paper's key contributions are: (1) framing algorithmic asymmetry as a lens for learning dynamics, distinguishing it from both symmetric fast-convergence analyses and black-box regret-to-convergence arguments; (2) introducing AOGD, a modified optimistic update designed for an agent facing a GD opponent, where the alternating component refers to the fact that the AOGD player holds its strategy fixed on odd iterations and applies an optimistic update on even iterations; (3) proving simulation theorems showing the even-iterate trajectory of GD vs. AOGD is identical to an AGD trajectory, with the simulation being exact in unconstrained games and holding under a fully-mixed condition in normal-form games; and (4) establishing that fast convergence can be recovered even though one agent continues to use vanilla GD.

The paper studies two-player bilinear games where player i receives utility ui(x1, x2) = x i T A(i) x(-i), primarily focusing on zero-sum games where u1 = -u2. Two settings are examined: unconstrained bilinear games (Xi = R ki) and normal-form games (Xi = Δ ki, the probability simplex). The distance to Nash equilibria is measured by the gradient norm in unconstrained settings and by the Nash gap (duality gap) in normal-form settings.

The AOGD update rule is defined as: x i t = x i(t-1) if t is odd, and x i t = P(x i(t-1) + 2η i A(i) x(-i)(t-1) - η i A(i) x(-i)(t-2)) if t is even. This differs from AGD, which is a sequential decision rule where agents take turns updating, whereas AOGD is a simultaneous decision rule where the AOGD agent updates only on even iterations using an optimistic update.

Theorem 1 establishes that when agent 1 uses GD with learning rate η1 and agent 2 uses AOGD with learning rate η2, the resulting dynamics simulate AGD with learning rates η̄1 = 2η1 and η̄2 = η2, specifically showing z 1 t = x 1(2t). Theorem 2 extends this to both agents, showing x(2t) = z t, with the caveat that in normal-form games this requires the iterates to be fully mixed. Proposition 2 provides a counterexample showing the simulation can fail in normal-form games when x 1(2t) is not fully mixed.

Theorem 3 proves that in unconstrained bilinear zero-sum games, when agent 1 uses GD with learning rate η1 and agent 2 uses AOGD with learning rate η2 where 2η1η2 ≤ 2/‖A‖, the time-average strategy converges to the set of Nash equilibria at rate O(1/T). Theorem 4 extends this to normal-form games with a fully-mixed Nash equilibrium, requiring 0 < 2η1 = η2 ≤ min i∈ 1,2,j∈[k i] x* ij/‖A‖ and assuming the iterates become fully mixed after some time t0.

The paper discusses several limitations in the normal-form setting, which almost entirely stem from a lack of understanding of (AGD) in the normal-form setting. These include: (1) the sufficient learning rates for AGD are smaller in the normal-form setting (η ≤ min i,j x* ij/‖A‖2 versus η < 2/‖A‖ in the unconstrained case); (2) convergence guarantees require a fully-mixed Nash equilibrium; and (3) convergence guarantees require fully-mixed iterates. The authors argue these are limitations of current AGD theory rather than fundamental barriers, noting any future improvement in the learning rate analysis for (AGD) in normal-form games will automatically improve our results.

The experiments test random k×k zero-sum games for k ∈ 8, 16, 32, comparing symmetric OGD and AGD baselines with GD vs. AOGD. Learning rates are selected according to theoretical stability scales: η OGD = 1/(2k), η AGD = 2/k, and for GD vs. AOGD, η GD = 1/k and η AOGD = 2/k, yielding effective AGD rates of (2/k, 2/k). In unconstrained games, GD vs. AOGD improves on OGD at the end of the horizon: its mean residual is approximately 34.9% lower at k = 8, 31.9% lower at k = 16, and 31.7% lower at k = 32, with AGD attaining the smallest terminal residual and the asymmetric pairing remaining between AGD and OGD. In normal-form games, GD vs. AOGD improves on OGD at every tested dimension: its mean terminal Nash gap is approximately 43.6% lower at k = 8, 47.4% lower at k = 16, and 48.0% lower at k = 32.

A support audit of 500 random games per dimension shows that fully-mixed Nash equilibria are rare: approximately 33.2% of 2×2 games, 3.0% of 4×4 games, and 0% of games in dimensions 8, 16, and 32. The authors note that every game contributing to Figures 2 and 4 has a Nash equilibrium supported on a strict face of the simplex; none satisfies the fully-mixed Nash equilibrium assumption in Theorem 4, yet GD vs. AOGD still demonstrates fast convergence, suggesting full mixing is a sufficient condition used by the current proof rather than a necessary condition for the underlying convergence phenomenon.

The paper concludes that a single agent can unilaterally recover the fast convergence rate of a coordinated alternating method, without requiring the GD opponent to modify its update rule, and suggests that algorithmic asymmetry is not merely a complication in learning dynamics; it can be a source of improved behavior. Future directions include "characterizing which asymmetric pairings admit unilateral acceleration, understanding when support identification removes the fully mixed assumptions in normal-form games, and extending these ideas beyond bilinear zero-sum settings to broader saddle-point and primal-dual optimization problems."

Improvements to AI Systems:

1. Unilateral Fast Convergence in Multi-Agent Learning: AI systems can now achieve O(1/T) convergence to Nash equilibria in zero-sum games even when one agent uses only vanilla gradient descent (GD), by deploying the Alternating Optimistic Gradient Descent (AOGD) update on the other agent. This removes the need for both agents to adopt sophisticated symmetric updates, enabling faster, more stable training in adversarial settings (e.g., GANs, multi-agent RL) where one party is constrained to simple GD.

2. Simulation-Based Strategy Transfer: The AOGD update allows an AI agent to exactly simulate the trajectory of Alternating Gradient Descent (AGD) on even iterates, without requiring the opponent to alternate turns. This means an AI can leverage the convergence guarantees of coordinated alternating methods while operating in a simultaneous-move environment, improving performance in real-time games, decentralized optimization, and online learning where turn-taking is impractical.

3. Robustness to Opponent Simplicity: AI systems can now maintain fast convergence even when facing a naive or fixed-strategy opponent using plain GD. This is critical for deployment in competitive environments (e.g., auction bidding, resource allocation, cybersecurity) where the opponent may not be cooperative or may use outdated algorithms, yet the AI can unilaterally accelerate its own convergence to equilibrium.

4. Improved Convergence Rate in Normal-Form Games: In finite games (e.g., matrix games, poker, strategic decision-making), the asymmetric GD vs. AOGD pairing achieves a terminal Nash gap reduction of 43–48% compared to symmetric optimistic GD (OGD) across tested dimensions. This enables AI systems to find equilibria more precisely and quickly in discrete strategy spaces, improving decision quality in game-theoretic reasoning tasks.

5. Relaxed Learning Rate Constraints via Effective Parameter Tuning: The simulation theorem shows that AOGD with learning rate η2 effectively yields an AGD rate of η2, while GD’s rate is doubled (2η1). This allows AI practitioners to tune learning rates more flexibly—e.g., using larger steps for the GD opponent without sacrificing convergence—reducing sensitivity to hyperparameter choices in adversarial training pipelines.

6. Support for Non-Fully-Mixed Equilibria: Although theoretical guarantees require fully-mixed Nash equilibria, empirical evidence shows fast convergence even when equilibria lie on strict faces of the simplex. This suggests AI systems can be designed to handle sparse or boundary-supported equilibria in practice, broadening applicability to real-world games with pure or mixed-but-not-fully-mixed solutions, such as traffic routing or network security games.

7. Unified Framework for Asymmetric Learning Dynamics: The paper provides a new lens for analyzing and designing asymmetric algorithms, enabling AI systems to identify when unilateral acceleration is possible. This can be integrated into meta-learning or automated algorithm selection systems to choose optimal update rules based on opponent behavior, improving adaptability in dynamic multi-agent environments.

8. Bridging Regret-Based and Convergence-Based Analyses: By showing that the slow O(1/√T) regret bound of GD is not intrinsic, AI systems can now use tighter convergence certificates (O(1/T)) for asymmetric dynamics, enabling more reliable performance guarantees in safety-critical applications like autonomous negotiation or decentralized control, where worst-case bounds previously limited deployment.

What the Improved AI System Can Do:

• Achieve faster, more reliable convergence to Nash equilibria in zero-sum games (e.g., GAN training, adversarial robustness) with minimal assumptions on the opponent’s update rule.

• Operate effectively in simultaneous-move settings while enjoying the benefits of alternating optimization, without requiring coordination or communication.

• Maintain high performance in competitive scenarios where the opponent uses simple or legacy algorithms, reducing the need for retraining or complex multi-agent coordination.

• Provide tighter performance guarantees in game-theoretic AI applications, enabling safer and more efficient decision-making in real-time strategic interactions.