# Swap Regret Minimization Through Response-Based Approachability

arXiv: https://arxiv.org/abs/2602.06264 · HTML: https://mlsanity.com/paper/2602.06264/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 62 references that are in the map.
- First posted on arXiv 5 Feb 2026.

## Builds on (most cited first, 26 of 26)

- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Omnipredictors](https://mlsanity.com/paper/2109.05389/) (2021)
- [Strategizing against No-regret Learners](https://mlsanity.com/paper/1909.13861/) (2019)
- [Variance Reduction for Matrix Games](https://mlsanity.com/paper/1907.02056/) (2019)
- [Strategizing against Learners in Bayesian Games](https://mlsanity.com/paper/2205.08562/) (2022)
- [Fast swap regret minimization and applications to approximate correlated equilibria](https://mlsanity.com/paper/2310.19647/) (2023)
- [Swap Agnostic Learning, or Characterizing Omniprediction via Multicalibration](https://mlsanity.com/paper/2302.06726/) (2023)
- [Faster Algorithm for Structured John Ellipsoid Computation](https://mlsanity.com/paper/2211.14407/) (2022)
- [Volumetric Spanners: an Efficient Exploration Basis for Learning](https://mlsanity.com/paper/1312.6214/) (2013)
- [Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium](https://mlsanity.com/paper/2104.01520/) (2021)
- [Coarse Correlation in Extensive-Form Games](https://mlsanity.com/paper/1908.09893/) (2019)
- [Pareto-Optimal Algorithms for Learning in Games](https://mlsanity.com/paper/2402.09549/) (2024)
- [The entropic barrier: a simple and optimal universal self-concordant barrier](https://mlsanity.com/paper/1412.1587/) (2014)
- [Coordinate Methods for Matrix Games](https://mlsanity.com/paper/2009.08447/) (2020)
- [High dimensional online calibration in polynomial time](https://mlsanity.com/paper/2504.09096/) (2025)
- [High-Dimensional Calibration from Swap Regret](https://mlsanity.com/paper/2505.21460/) (2025)
- [Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games](https://mlsanity.com/paper/2412.20291/) (2024)
- [Polynomial-Time Linear-Swap Regret Minimization in Imperfect-Information Sequential Games](https://mlsanity.com/paper/2307.05448/) (2023)
- [A Lower Bound on Swap Regret in Extensive-Form Games](https://mlsanity.com/paper/2406.13116/) (2024)
- [Swap Regret and Correlated Equilibria Beyond Normal-Form Games](https://mlsanity.com/paper/2502.20229/) (2025)
- [Bayes correlated equilibria, no-regret dynamics in Bayesian games, and the price of anarchy](https://mlsanity.com/paper/2304.05005/) (2023)
- [Expected Variational Inequalities](https://mlsanity.com/paper/2502.18605/) (2025)
- [Rate-Preserving Reductions for Blackwell Approachability](https://mlsanity.com/paper/2406.07585/) (2024)
- [Learning and Computation of Phi-Equilibria at the Frontier of Tractability](https://mlsanity.com/paper/2502.18582/) (2025)
- [Mediator Interpretation and Faster Learning Algorithms for Linear Correlated Equilibria in General Extensive-Form Games](https://mlsanity.com/paper/2310.15935/) (2023)
- [Uncertainty Quantification of Set-Membership Estimation in Control and Perception: Revisiting the Minimum Enclosing Ellipsoid](https://mlsanity.com/paper/2311.15962/) (2023)

## Built on by (most cited first, 2 of 2)

- [An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to Phi-Regret Minimization](https://mlsanity.com/paper/2604.19592/) (2026)
- [Constant Swap Regret in General-Sum Games via Two-Scale Higher-Order Optimism](https://mlsanity.com/paper/2609.16751/) (2026)

## Abstract (arXiv)

We consider the problem of minimizing different notions of swap regret in online optimization. These forms of regret are tightly connected to correlated equilibrium concepts in games, and have been more recently shown to guarantee non-manipulability against strategic adversaries. The only computationally efficient algorithm for minimizing linear swap regret over a general convex set in ℝd was developed recently by Daskalakis, Farina, Fishelson, Pipis, and Schneider (STOC '25). However, it incurs a highly suboptimal regret bound of Omega(d4 √T) and also relies on computationally intensive calls to the ellipsoid algorithm at each iteration. In this paper, we develop a significantly simpler, computationally efficient algorithm that guarantees O(d √T) linear swap regret for a general convex set that has been preconditioned via the John ellipsoid. Our algorithm leverages the powerful response-based approachability framework of Bernstein and Shimkin (JMLR~'15) -- previously overlooked in the line of work on swap regret minimization -- and simultaneously minimizes profile swap regret, which was recently shown to guarantee non-manipulability. Moreover, we establish a matching information-theoretic lower bound: any learner must incur in expectation Omega(d √T) linear swap regret for large enough T, even when the set is centrally symmetric. This also shows that the classic algorithm of Gordon, Greenwald, and Marks (ICML '08) is existentially optimal for minimizing linear swap regret, although it is computationally inefficient. Finally, we extend our approach to minimize regret with respect to the set of swap deviations with polynomial dimension, unifying and strengthening recent results in equilibrium computation and online learning.