# Full Swap Regret and Discretized Calibration

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 38 references that are in the map.
- First posted on arXiv 13 Feb 2025.

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

- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [Strategizing against No-regret Learners](https://mlsanity.com/paper/1909.13861/) (2019)
- [U-Calibration: Forecasting for an Unknown Agent](https://mlsanity.com/paper/2307.00168/) (2023)
- [Selling to a No-Regret Buyer](https://mlsanity.com/paper/1711.09176/) (2017)
- [Stronger Calibration Lower Bounds via Sidestepping](https://mlsanity.com/paper/2012.03454/) (2020)
- [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)
- [Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agents](https://mlsanity.com/paper/2306.02704/) (2023)
- [Forecasting for Swap Regret for All Downstream Agents](https://mlsanity.com/paper/2402.08753/) (2024)
- [Is Learning in Games Good for the Learners?](https://mlsanity.com/paper/2305.19496/) (2023)
- [Selling to Multiple No-Regret Buyers](https://mlsanity.com/paper/2307.04175/) (2023)
- [Breaking the T2/3 Barrier for Sequential Calibration](https://mlsanity.com/paper/2406.13668/) (2024)
- [Mechanisms for a No-Regret Agent: Beyond the Common Prior](https://mlsanity.com/paper/2009.05518/) (2020)
- [Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descent](https://mlsanity.com/paper/2205.15294/) (2022)
- [Calibration Error for Decision Making](https://mlsanity.com/paper/2404.13503/) (2024)
- [Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games](https://mlsanity.com/paper/2412.20291/) (2024)
- [From External to Swap Regret 2.0: An Efficient Reduction and Oblivious Adversary for Large Action Spaces](https://mlsanity.com/paper/2310.19786/) (2023)
- [Polynomial-Time Linear-Swap Regret Minimization in Imperfect-Information Sequential Games](https://mlsanity.com/paper/2307.05448/) (2023)
- [Efficient Phi-Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Games](https://mlsanity.com/paper/2402.09670/) (2024)
- [Efficient Learning in Polyhedral Games via Best Response Oracles](https://mlsanity.com/paper/2312.03696/) (2023)

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

- [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)
- [Simultaneous Swap Regret Minimization via KL-Calibration](https://mlsanity.com/paper/2502.16387/) (2025)
- [Swap Regret and Correlated Equilibria Beyond Normal-Form Games](https://mlsanity.com/paper/2502.20229/) (2025)
- [Efficient Swap Multicalibration of Elicitable Properties](https://mlsanity.com/paper/2511.04907/) (2025)
- [Calibeating Made Simple](https://mlsanity.com/paper/2603.22167/) (2026)
- [Improved Bounds for Swap Multicalibration and Swap Omniprediction](https://mlsanity.com/paper/2505.20885/) (2025)
- [Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games](https://mlsanity.com/paper/2511.01852/) (2025)
- [Dimension-Free Decision Calibration for Nonlinear Loss Functions](https://mlsanity.com/paper/2504.15615/) (2025)
- [Near-optimal Swap Regret Minimization for Convex Losses](https://mlsanity.com/paper/2602.08862/) (2026)
- [Computational and Statistical Hardness of Calibration Distance](https://mlsanity.com/paper/2603.18391/) (2026)
- [Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria](https://mlsanity.com/paper/2609.22757/) (2026)
- [Adaptive Calibration in Non-Stationary Environments](https://mlsanity.com/paper/2605.11490/) (2026)
- [Paradoxes of Game Theoretic Equilibria and Price of Anarchy](https://mlsanity.com/paper/2607.11752/) (2026)
- [Fast Rates for Swap-Agnostic Learning of Proper Losses](https://mlsanity.com/paper/2607.28856/) (2026)

## Abstract (arXiv)

We study the problem of minimizing swap regret in structured normal-form games. Players have a very large (potentially infinite) number of pure actions, but each action has an embedding into d-dimensional space and payoffs are given by bilinear functions of these embeddings. We provide an efficient learning algorithm for this setting that incurs at most tildeO(T(d+1)/(d+3)) swap regret after T rounds. To achieve this, we introduce a new online learning problem we call full swap regret minimization. In this problem, a learner repeatedly takes a (randomized) action in a bounded convex d-dimensional action set K and then receives a loss from the adversary, with the goal of minimizing their regret with respect to the worst-case swap function mapping K to K. For varied assumptions about the convexity and smoothness of the loss functions, we design algorithms with full swap regret bounds ranging from O(Td/(d+2)) to O(T(d+1)/(d+2)). Finally, we apply these tools to the problem of online forecasting to minimize calibration error, showing that several notions of calibration can be viewed as specific instances of full swap regret. In particular, we design efficient algorithms for online forecasting that guarantee at most O(T1/3) ℓ2-calibration error and O(max(√ε T, T1/3)) discretized-calibration error (when the forecaster is restricted to predicting multiples of ε).