A Lower Bound on Swap Regret in Extensive-Form Games
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929391129329664 |
|---|---|
| author | Daskalakis, Constantinos Farina, Gabriele Golowich, Noah Sandholm, Tuomas Zhang, Brian Hu |
| author_facet | Daskalakis, Constantinos Farina, Gabriele Golowich, Noah Sandholm, Tuomas Zhang, Brian Hu |
| contents | 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^{\tilde{\mathcal O}(1/ε)}$ rounds, where $m$ is the number of nodes in the game tree. However, the question of whether a $\mathrm{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 $\mathrm{exp}\left(Ω\left(\min\left\{m^{1/14}, ε^{-1/6}\right\}\right)\right)$ rounds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_13116 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Lower Bound on Swap Regret in Extensive-Form Games Daskalakis, Constantinos Farina, Gabriele Golowich, Noah Sandholm, Tuomas Zhang, Brian Hu Computer Science and Game Theory 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^{\tilde{\mathcal O}(1/ε)}$ rounds, where $m$ is the number of nodes in the game tree. However, the question of whether a $\mathrm{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 $\mathrm{exp}\left(Ω\left(\min\left\{m^{1/14}, ε^{-1/6}\right\}\right)\right)$ rounds. |
| title | A Lower Bound on Swap Regret in Extensive-Form Games |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2406.13116 |