Research map / Bandits and online learning / Online convex optimization and games
Convergence of No-Swap-Regret Dynamics in Self-Play
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that in almost all symmetric zero-sum games, self-play with identical no-swap-regret learners converges in frequent-iterate sense to Nash, while no-swap-regret algorithms must be time-asymmetric functions of past rewards.
Problem
Whether no-swap-regret dynamics give stronger convergence than no-external-regret dynamics in repeated games, specifically Nash convergence in zero-sum games, and whether such algorithms can be symmetric functions of the history of play.
Approach
In symmetric zero-sum games with identical symmetric initializations, time-averaged convergence of xt⊗xt to a product distribution implies frequent-iterate convergence to Nash (via a quadratic linear functional lemma), combined with the genericity of unique CE/Nash in symmetric zero-sum games. Also shows no-swap-regret learners cannot be symmetric functions of the history, using card-guessing boun
Key results
- Theorem 3: in generic symmetric zero-sum games, identical no-swap-regret learners with same initialization have frequent-iterate convergence to Nash equilibrium, and last-iterate convergence cannot be proven in general.
- Lemma 5: for 2-action games, swap regret is at most twice external regret.
- Theorem 6: any no-swap-regret algorithm whose action depends symmetrically on Bob's mixed-strategy history incurs Omega(T) swap regret in a 3-action matching pennies construction.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use identical no-swap-regret algorithms with the same initialization | Self-play in a generic symmetric zero-sum game · Generic symmetric zero-sum games | frequent-iterate convergence to Nash equilibrium | Helped |
| Use asymmetric initial conditions instead of symmetric initialization (ablation) | Blum-Mansour self-play · Rock-Paper-Scissors | convergence to Nash equilibrium | Hurt |
| Replace no-swap-regret dynamics with no-external-regret dynamics (ablation) | Symmetric self-play in zero-sum games · Rock-Paper-Scissors | frequent-iterate convergence to Nash equilibrium | Hurt |
| Use an asymmetric zero-sum game instead of a symmetric zero-sum game (ablation) | No-external-regret self-play · Matching Pennies | last-iterate convergence to Nash equilibrium | Hurt |
| Make the action depend symmetrically on the history of opponent strategies | A learning algorithm in the three-action game · Adversarial opponent sequence | swap regret: Ω(T) | Hurt |
| Allow vanishingly infrequent arbitrary symmetric play in the trajectory (ablation) | No-swap-regret dynamics · Generic symmetric zero-sum games | last-iterate convergence to Nash equilibrium | Hurt |
Surprising findings
- Symmetric initializations are necessary: asymmetric Blum-Mansour initializations in Rock-Paper-Scissors do not converge to Nash.
- No-external-regret dynamics like MWU can be symmetric functions of cumulative rewards, but no-swap-regret algorithms cannot be, so swap regret requires time-asymmetry.
Limitations
- Results are for two-player games; generalization to more players left open.
- Frequent-iterate convergence is weaker than last-iterate; last-iterate convergence cannot be established by this argument.
- Asymmetric zero-sum games (e.g. matching pennies) are not covered by the convergence result.
Experimental setup
Baselines: Multiplicative Weights Follow-the-Regularized-Leader
Builds on: Blum-Mansour algorithm Multiplicative Weights Forges correlated equilibrium uniqueness in zero-sum games
Closest papers by meaning
- No-regret Learning in Harmonic Games: Extrapolation in the Face of Conflicting Interests (NeurIPS 2024 · similarity 0.92)
- Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games (ICLR 2025 · similarity 0.91)
- Memory Asymmetry Creates Heteroclinic Orbits to Nash Equilibrium in Learning in Zero-Sum Games (AAAI 2024 · similarity 0.90)
- Mediator Interpretation and Faster Learning Algorithms for Linear Correlated Equilibria in General Sequential Games (ICLR 2024 · similarity 0.90)
- Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions (NeurIPS 2026 · similarity 0.90)
- Optimism Without Regularization: Constant Regret in Zero-Sum Games (NeurIPS 2025 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.