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 N^ 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 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 N^O (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 N^O (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.