Hierarchies of No-regret Algorithms

Ruqing Xu, Eric Yachbes, James Zhang · 2026

Read Hierarchies of No-regret Algorithms by Ruqing Xu, Eric Yachbes, James Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-25045.txt.

Description

Xu, Yachbes and Zhang study hierarchies of no-regret algorithms in two-player games. The hierarchy runs from weakest to strongest: no-swap-regret, no-regret, and uniform random play. Counterintuitively, no-swap-regret often hurts its players, giving better utility to opponents. The root cause is a difference in effective learning rate: no-swap-regret algorithms learn substantially slower than no-regret algorithms. For games where each player has 7 actions, no-swap-regret algorithms perform clearly better in ways not explained by unfairly adjusted learning rates.

Catalog record

CREATORRuqing Xu, Eric Yachbes, James Zhang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE24723
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.25045

Browse the full library · About the Tower of Babel