A Lower Bound on Swap Regret in Extensive-Form Games

Recent simultaneous works by Peng and Rubinstein [2024] and Dagan et al. [2024] have demonstrated the existence of a no-swap-regret learning algorithm that can reach ε average swap regret against an adversary in any extensive-form game within mÕ(1/ε) rounds, where m is the number of nodes in the game tree. However, the question of whether a poly(m, 1/ε)-round algorithm could exist remained open. In this paper, we show a lower bound that precludes the existence of such an algorithm. In particular, we show that achieving average swap regret ε against an oblivious adversary in general extensive-form games requires at least exp(Ω(min1/14, ε-1/6\)) rounds.