# From External to Swap Regret 2.0: An Efficient Reduction and Oblivious Adversary for Large Action Spaces

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Oct 2023.

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

- [Full Swap Regret and Discretized Calibration](https://mlsanity.com/paper/2502.09332/) (2025)
- [Calibration Error for Decision Making](https://mlsanity.com/paper/2404.13503/) (2024)
- [High dimensional online calibration in polynomial time](https://mlsanity.com/paper/2504.09096/) (2025)
- [Smooth Calibration and Decision Making](https://mlsanity.com/paper/2504.15582/) (2025)
- [Swap Regret and Correlated Equilibria Beyond Normal-Form Games](https://mlsanity.com/paper/2502.20229/) (2025)
- [Is Knowledge Power? On the (Im)possibility of Learning from Strategic Interactions](https://mlsanity.com/paper/2408.08272/) (2024)
- [The complexity of approximate (coarse) correlated equilibrium for incomplete information games](https://mlsanity.com/paper/2406.02357/) (2024)
- [Rate-Preserving Reductions for Blackwell Approachability](https://mlsanity.com/paper/2406.07585/) (2024)
- [The Stability of Online Algorithms in Performative Prediction](https://mlsanity.com/paper/2602.24207/) (2026)
- [Learning to Play Against Unknown Opponents](https://mlsanity.com/paper/2412.18297/) (2024)
- [High-dimensional online calibration from harmonic weights](https://mlsanity.com/paper/2610.07740/) (2026)

## Abstract (arXiv)

We provide a novel reduction from swap-regret minimization to external-regret minimization, which improves upon the classical reductions of Blum-Mansour [BM07] and Stolz-Lugosi [SL05] in that it does not require finiteness of the space of actions. We show that, whenever there exists a no-external-regret algorithm for some hypothesis class, there must also exist a no-swap-regret algorithm for that same class. For the problem of learning with expert advice, our result implies that it is possible to guarantee that the swap regret is bounded by ε after log(N)O(1/ε) rounds and with O(N) per iteration complexity, where N is the number of experts, while the classical reductions of Blum-Mansour and Stolz-Lugosi require O(N/ε2) rounds and at least Omega(N2) per iteration complexity. Our result comes with an associated lower bound, which -- in contrast to that in [BM07] -- holds for oblivious and ℓ1-constrained adversaries and learners that can employ distributions over experts, showing that the number of rounds must be tildeOmega(N/ε2) or exponential in 1/ε. Our reduction implies that, if no-regret learning is possible in some game, then this game must have approximate correlated equilibria, of arbitrarily good approximation. This strengthens the folklore implication of no-regret learning that approximate coarse correlated equilibria exist. Importantly, it provides a sufficient condition for the existence of correlated equilibrium which vastly extends the requirement that the action set is finite, thus answering a question left open by [DG22; Ass+23]. Moreover, it answers several outstanding questions about equilibrium computation and learning in games.