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

2023/10/30 by Yuval Dagan, Constantinos Daskalakis, Dagan, Yuval +5 · 1 voice · 2 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Artificial Intelligence (cs.AI) #Computability, Logic, AI Algorithms #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #cs.AI #cs.GT #cs.LG

paper · pdf · doi:10.48550/arxiv.2310.19786

openalex publication_date 2023/10/30 · arxiv published 2023/10/30 · arxiv updated 2025/02/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

We provide a novel reduction from swap-regret minimization to external-regret minimization, which improves upon the classical reductions of Blum-Mansour [BM07] and Stolz-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)^O(1/ε) rounds and with O(N) per iteration complexity, where N is the number of experts, while the classical reductions of Blum-Mansour and Stolz-Lugosi require O(N/ε²) rounds and at least Ω(N²) per iteration complexity. Our result comes with an associated lower bound, which -- in contrast to that in [BM07] -- holds for oblivious and ℓ₁-constrained adversaries and learners that can employ distributions over experts, showing that the number of rounds must be Ω(N/ε²) 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 correlated equilibrium which vastly extends the requirement that the action set is finite, thus answering a question left open by [DG22; Ass+23]. Moreover, it answers several outstanding questions about equilibrium computation and learning in games.

Cited by

• On characterization and existence of constrained correlated equilibria in Markov games
• Smooth Calibration and Decision Making

Discussions

• Here are the two papers that derive this new algorithm: Dagan, Daskalakis, Fishelson, and Golowich: arxiv.org/abs/2310.19786 and Peng and Rubinstein: arxiv.org/abs/2310.19647 [bsky, 0 points, 0 comments]

Related

• A Lower Bound on Swap Regret in Extensive-Form Games
• Polynomial-Time Linear-Swap Regret Minimization in Imperfect-Information Sequential Games
• Computational Lower Bounds for Regret Minimization in Normal-Form Games
• Swap Regret and Correlated Equilibria Beyond Normal-Form Games
• Comparator-Adaptive Φ-Regret: Improved Bounds, Simpler Algorithms, and Applications to Games