# A Lower Bound on Swap Regret in Extensive-Form Games

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jun 2024.

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

- [High-Dimensional Calibration from Swap Regret](https://mlsanity.com/paper/2505.21460/) (2025)
- [Swap Regret and Correlated Equilibria Beyond Normal-Form Games](https://mlsanity.com/paper/2502.20229/) (2025)
- [Expected Variational Inequalities](https://mlsanity.com/paper/2502.18605/) (2025)
- [Learning and Computation of Phi-Equilibria at the Frontier of Tractability](https://mlsanity.com/paper/2502.18582/) (2025)
- [Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games](https://mlsanity.com/paper/2511.01852/) (2025)
- [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)
- [Swap Regret Minimization Through Response-Based Approachability](https://mlsanity.com/paper/2602.06264/) (2026)
- [Efficient Swap Regret Minimization in Combinatorial Bandits](https://mlsanity.com/paper/2602.02087/) (2026)

## Abstract (arXiv)

Recent simultaneous works by Peng and Rubinstein [2024] and Dagan et al. [2024] have demonstrated the existence of a no-swap-regret learning algorithm that can reach ε average swap regret against an adversary in any extensive-form game within m^tildemathcal O(1/ε) rounds, where m is the number of nodes in the game tree. However, the question of whether a poly(m, 1/ε)-round algorithm could exist remained open. In this paper, we show a lower bound that precludes the existence of such an algorithm. In particular, we show that achieving average swap regret ε against an oblivious adversary in general extensive-form games requires at least expleft(Omegaleft(minleftm1/14, ε-1/6rightright)right) rounds.