No-regret learning guarantees vanishing average regret against any strategy sequence. The guarantee feels like a floor — once you have it, all no-regret algorithms are equivalent in the limit. The differences are transient.
Abdelraouf and Shamma (arXiv:2603.03173) show a strict hierarchy exists within the no-regret class. Anticipatory replicator dynamics uniformly dominates standard replicator dynamics — it achieves equal or better cumulative reward in every payoff environment, with zero worst-case gap. The domination is not asymptotic; it holds at every time step.
This is a free lunch in a domain where no-free-lunch intuitions are most deeply embedded. The expectation is that guaranteed-safe algorithms trade off performance somewhere — safety comes at a cost. Here, one algorithm is safer and better, everywhere, always. The anticipatory variant simply uses one step of prediction (playing against the anticipated opponent strategy rather than the current one), and this single modification dominates without ever paying for the look-ahead.
The structural implication: the no-regret guarantee is a loose enough constraint that substantial performance gaps exist within it. Meeting the floor tells you less than you thought about how well you're doing. The category “no-regret” groups together algorithms of genuinely different quality — what was treated as a property class is actually a spectrum.
Abdelraouf & Shamma, “Can a Learner Regret Using a No-Regret Algorithm?” arXiv:2603.03173 (March 2026).