# Efficient Phi-Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Games

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Feb 2024.

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

- [Full Swap Regret and Discretized Calibration](https://mlsanity.com/paper/2502.09332/) (2025)
- [Swap Regret and Correlated Equilibria Beyond Normal-Form Games](https://mlsanity.com/paper/2502.20229/) (2025)
- [Rate-Preserving Reductions for Blackwell Approachability](https://mlsanity.com/paper/2406.07585/) (2024)
- [Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games](https://mlsanity.com/paper/2511.01852/) (2025)
- [Optimism Without Regularization: Constant Regret in Zero-Sum Games](https://mlsanity.com/paper/2506.16736/) (2025)
- [Paradoxes of Game Theoretic Equilibria and Price of Anarchy](https://mlsanity.com/paper/2607.11752/) (2026)

## Abstract (arXiv)

Recent breakthrough results by Dagan, Daskalakis, Fishelson and Golowich [2023] and Peng and Rubinstein [2023] established an efficient algorithm attaining at most ε swap regret over extensive-form strategy spaces of dimension N in Ntilde O(1/ε) rounds. On the other extreme, Farina and Pipis [2023] developed an efficient algorithm for minimizing the weaker notion of linear-swap regret in mathsfpoly(N)/ε2 rounds. In this paper, we develop efficient parameterized algorithms for regimes between these two extremes. We introduce the set of k-mediator deviations, which generalize the untimed communication deviations recently introduced by Zhang, Farina and Sandholm [2024] to the case of having multiple mediators, and we develop algorithms for minimizing the regret with respect to this set of deviations in NO(k)/ε2 rounds. Moreover, by relating k-mediator deviations to low-degree polynomials, we show that regret minimization against degree-k polynomial swap deviations is achievable in NO(kd)3/ε2 rounds, where d is the depth of the game, assuming a constant branching factor. For a fixed degree k, this is polynomial for Bayesian games and quasipolynomial more broadly when d = mathsfpolylog N -- the usual balancedness assumption on the game tree.