A Lower Bound on Swap Regret in Extensive-Form Games
<|reference_start|>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 $\epsilon$ average swap regret against an adversary in any extensive-form game within $m^{\tilde{\mathcal O}(1/\epsilon)}$ rounds, where $m$ is the number of nodes in the game tree. However, the question of whether a $\mathrm{poly}(m, 1/\epsilon)$-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 $\epsilon$ against an oblivious adversary in general extensive-form games requires at least $\mathrm{exp}\left(\Omega\left(\min\left\{m^{1/14}, \epsilon^{-1/6}\right\}\right)\right)$ rounds.<|reference_end|>
@article{daskalakis2024a,
    title={A Lower Bound on Swap Regret in Extensive-Form Games},
    author={Constantinos Daskalakis, Gabriele Farina, Noah Golowich, Tuomas
  Sandholm, Brian Hu Zhang},
    journal={arXiv preprint arXiv:2406.13116},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.13116},
    primaryClass={cs.GT}
}