Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.25045 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908997064327168 |
|---|---|
| author | Xu, R. Yachbes, E. Zhang, J. |
| author_facet | Xu, R. Yachbes, E. Zhang, J. |
| contents | Our paper studies the setting of players using no-regret algorithms in various two-player games. We address whether having stronger regret guarantees or playing against an opponent with weaker regret guarantees yields higher utilities for the player in question. We consider a hierarchy of algorithms from weakest to strongest: uniform random play, no-regret, and no-swap-regret. We find, counterintuitively, that in many games, no-swap-regret is a worse choice for players (and gives better utility for their opponents). We find the root cause of this phenomenon to be a difference in effective learning rate between the two algorithms, where the no-swap-regret algorithms learn $N$ times slower than no-regret algorithms. To address this, we attempt to equalize learning rates, leading to closer utility between no-regret and no-swap-regret players. Finally, we show that for certain random games with $7$ actions per player, no-swap-regret algorithms can perform noticeably better than no-regret algorithms in a manner that cannot be explained away by unfairly adjusted learning rates. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_25045 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Hierarchies of No-regret Algorithms Xu, R. Yachbes, E. Zhang, J. Computer Science and Game Theory Our paper studies the setting of players using no-regret algorithms in various two-player games. We address whether having stronger regret guarantees or playing against an opponent with weaker regret guarantees yields higher utilities for the player in question. We consider a hierarchy of algorithms from weakest to strongest: uniform random play, no-regret, and no-swap-regret. We find, counterintuitively, that in many games, no-swap-regret is a worse choice for players (and gives better utility for their opponents). We find the root cause of this phenomenon to be a difference in effective learning rate between the two algorithms, where the no-swap-regret algorithms learn $N$ times slower than no-regret algorithms. To address this, we attempt to equalize learning rates, leading to closer utility between no-regret and no-swap-regret players. Finally, we show that for certain random games with $7$ actions per player, no-swap-regret algorithms can perform noticeably better than no-regret algorithms in a manner that cannot be explained away by unfairly adjusted learning rates. |
| title | Hierarchies of No-regret Algorithms |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2604.25045 |