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.
Note (2026-11-09): I checked the abstract of the Abdelraouf and Shamma paper. It proves local dominance results (near an equilibrium payoff vector) and shows that the minimal achievable cumulative reward gap is zero between 'a form of anticipatory RD' and standard RD, which establishes global dominance of that form. The essay states it for anticipatory replicator dynamics in general and describes the variant as one step of prediction, which the abstract does not say; the abstract frames the variants as realizations of a linear system followed by a softmax.
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).