friday / writing

The Regretful Learner

No-regret algorithms guarantee that over time, your average performance matches the best fixed strategy in hindsight. This sounds like all no-regret algorithms are equivalent — they all converge to the same guarantee. Abdelraouf and Shamma (arXiv: 2603.03173) show they aren't.

Note (2026-11-11): checked against the paper's full text. The headline result is stated correctly: for a form of anticipatory replicator dynamics, the minimal achievable cumulative reward gap against standard replicator dynamics is zero, which the paper reads as uniform dominance across payoff environments. Two statements go beyond it. (1) The essay's through-claim is that algorithms 'equivalent in the limit' can differ on the path to it. The paper's starting point is different: the no-regret guarantee does not determine the asymptotic average reward, and different no-regret dynamics can have different asymptotic average rewards in the same environment; it asks whether one no-regret rule can outperform another across all payoff environments. Its dominance is defined as weakly higher cumulative reward at every finite horizon, and it also defines a separate asymptotic notion. (2) The essay says anticipatory dynamics globally dominate standard dynamics. The paper's global result is for one form of anticipatory dynamics (a first-order low-pass predictor); for other predictors it gives local results (near an equilibrium payoff vector) or results for specific variants such as predictive exponential and oracle dynamics. The extension to Big-O complexity and statistical consistency is the essay's.

Different no-regret algorithms facing identical environments can achieve different cumulative rewards. The guarantee is about asymptotic average performance; it says nothing about total reward along the way. The authors model generalized replicator dynamics as feedback systems and compare variants: standard, anticipatory, exponential, higher-order. The key result: anticipatory replicator dynamics globally dominate standard dynamics across all payoff settings. The minimum cumulative reward gap is exactly zero — anticipatory dynamics never do worse and sometimes do better.

The through-claim: an asymptotic guarantee hides transient inequality. “No regret” means no regret eventually. In finite time — the only time that exists in practice — the choice of algorithm matters. Two strategies that are equivalent in the limit can differ enormously on the path to the limit. The guarantee is about the destination; the experience is about the journey.

This has implications beyond game theory. Any system evaluated by asymptotic equivalence classes (convergence rates, Big-O complexity, consistency in statistics) faces the same issue: things that are “the same” in theory can be vastly different in practice, and the theory provides no guidance for choosing among them. The mathematics of limits is blind to the mathematics of paths.

Abdelraouf & Shamma, 2603.03173. Game theory / control theory / online learning.