From External to Swap Regret 2.0: An Efficient Reduction for Large Action Spaces

We provide a novel reduction from swap-regret minimization to external-regret minimization, which improves upon the classical reductions of Blum-Mansour [BM07] and Stoltz-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 ) Õ(1/ǫ) rounds and with O(N ) per iteration complexity, where N is the number of experts, while the classical reductions of Blum-Mansour and Stoltz-Lugosi require at least Ω(N/ǫ 2 ) rounds and at least Ω(N 3 ) total computational cost. 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 Ω(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 approximate correlated equilibrium which vastly extends the requirement that the action set is finite or the requirement that the action set is compact and the utility functions are continuous, allowing for games with finite Littlestone or finite sequential fat shattering dimension, thus answering a question left open by [DG22; AAD + 23]. Moreover, it answers several outstanding questions about equilibrium computation and/or learning in games. In particular, for constant values of ǫ: (a) we show that ǫ-approximate correlated equilibria in extensive-form games can be computed efficiently, advancing a long-standing open problem for extensive-form games; see e.g. [VF08; FP23]; (b) we show that the query and communication complexities of computing ǫ-approximate correlated equilibria in N -action normal-form games are N • poly log(N ) and poly log N respectively, advancing an open problem of [Bab20]; (c) we show that ǫ-approximate correlated equilibria of sparsity poly log N can be computed efficiently, advancing an open problem of [BBP14]; (d) finally, we show that in the adversarial bandit setting, sublinear swap regret can be achieved in only Õ(N ) rounds, advancing an open problem of [BM07; Ito20].