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

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 NO(1/ε) rounds. On the other extreme, Farina and Pipis [2023] developed an efficient algorithm for minimizing the weaker notion of linear-swap regret in poly(N)/ε² rounds. In this paper, we take a step toward bridging the gap between those two results. 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. We develop parameterized algorithms for minimizing the regret with respect to this set of deviations in NO(k)/ε² rounds. This closes the gap in the sense that $k=1$ recovers linear swap regret, while $k=N$ recovers swap regret. 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)³/ε² rounds, where d is the depth of the game, assuming constant branching factor. For a fixed degree k, this is polynomial for Bayesian games and quasipolynomial more broadly when d = polylog N -- the usual balancedness assumption on the game tree.