Can a Learner Regret Using a No–Regret Algorithm? A Control–Theoretic Study of Performance Dominance

Hassan Abdelraouf, Jeff S. Shamma · 2026

Read Can a Learner Regret Using a No–Regret Algorithm? A Control–Theoretic Study of Performance Dominance by Hassan Abdelraouf, Jeff S. Shamma (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-2603-03173.txt.

Introduction

Hassan Abdelraouf and Jeff Shamma ask whether choosing the wrong good learning rule can itself be a mistake. No-regret algorithms guarantee that, over time, a learner does about as well as the best fixed strategy. Yet that promise says nothing about how high the final average actually is, and different no-regret rules can land at different heights.

Framing generalized replicator dynamics as control systems, they compare variants by reshaping one internal block. Near equilibrium, a passivity test ranks the variants. Globally, an anticipatory variant provably dominates the standard rule across every payoff environment, with an optimal-control argument showing the reward gap can reach zero. A genuine free lunch exists among no-regret dynamics, at least in this family.

Catalog record

CREATORHassan Abdelraouf, Jeff S. Shamma
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE79442
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Can a Learner Regret Using a No–Regret Algorithm? A Control–Theoretic Study of Performance Dominance Hassan Abdelraouf, Jeff S. Shamma Abstract No-regret learning dynamics ensure that a learner asymptotically achieves an average reward no worse than that of any fixed strategy. This no-regret guarantee does not determine the value of the asymptotic average reward. Indeed, it is possible for different no-regret learning dynamics to exhibit different asymptotic average rewards when facing the same environment while both assure the no-regret guarantee. This paper asks whether a “free-lunch” phenomenon can arise among no-regret algorithms. Namely, is it possible for one no-regret learning rule to uniformly outperform another no-regret learning rule across all payoff environments. Stated differently, can a learner regret not using a particular no-regret algorithm? We consider generalized replicator dynamics (RD) as a cascade interconnection between a linear time-invariant (LTI) system and the softmax nonlinearity. Varying this LTI system leads to different realizations of replicator dynamics, including so-called anticipatory RD, exponential RD, and other forms of higher-order RD. Setting the LTI system to be an integrator realizes standard RD, which is known to satisfy the no-regret property. Within this framework, we analyze and compare various realizations of these generalized realizations RD by varying the LTI system. We first formulate performance comparison as a passivity property of an associated comparison system and establish “local” dominance results, i.e., comparing the asymptotic performance near an equilibrium payoff vector. We then cast performance comparison between a form of anticipatory RD and standard RD as an optimal-control problem. We show that the minimal achievable cumulative reward gap is zero, thereby establishing global dominance of anticipatory RD across all payoff environments and establishing a “free lunch” among no-regret learning dynamics. I Introduction As autonomous AI agents become more widely deployed across dynamic, multi-agent environments, they will continuously learn and interact in real time to achieve complex goals. In this setting, online learning has emerged as a powerful framework for adaptive decision-making in uncertain, competitive environments. A learning agent selects actions without a full model, observes feedback, and updates its strategy in real time. This approach is widely used in online recommendation systems [ 1 ] , traffic routing and congestion management [ 2 ] , network resource allocation [ 3 ] , and market prediction [ 4 ] . Performance is typically measured by regret, the difference between the learner’s cumulative utility and that of the best fixed strategy in hindsight. An algorithm is said to be no-regret if its regret grows sublinearly in time, so that the average regret vanishes asymptotically [ 5 , 6 , 7 ] . A broad family of first-order methods has this guarantee, including online mirror descent (OMD) [ 8 , 9 ] , follow-the-regularized-leader (FTRL) [ 10 ] , follow-the-perturbed-leader (FTPL) [ 11 ] , multiplicative weight updates (MWU) [ 12 , 13 ] , EXP3 [ 14 ] , and online gradient descent (OGD) [ 15 ] . When the learner interacts with other adaptive learners, each agent’s utility depends not only on its own action but also on the actions of others. Game theory provides the mathematical framework to model and analyze such strategic interactions [ 16 , 17 ] . In this context, learning in games refers to adaptive procedures in which each agent updates its strategy based on past observations (realized payoffs and opponents’ actions) and then plays the updated strategy in the next round [ 18 , 19 ] . A foundational result in this literature is that if every player runs a no-regret algorithm, then the empirical distribution of joint play converges to the set of coarse correlated equilibria (CCE); equivalently, the time-averaged play approaches CCE without centralized coordination [ 20 , 21 , 22 ] . These guarantees help explain the success of no-regret learning in deployed multi-agent systems, including distributed sensor coverage and target assignment [ 23 ] , multi-robot coordination and consensus [ 24 ] , and distributed energy and resource management [ 25 ] . To move from equilibrium outcome to the process by which adaptive learners reach them, it is natural to adopt a dynamical-systems perspective. Within this perspective, passivity is a fundamental input–output property that captures energy conservation and dissipation in mechanical and electrical systems [ 26 ] . In the online learning setting, a learning algorithm can be viewed as an input–output operator mapping payoff signals to strategy trajectories. This perspective enables the use of passivity–based tools for both analysis and design. Building on this perspective, [ 27 ] introduced the notion of \delta –passivity to analyze convergence of learning dynamics to Nash equilibria in contractive games, modeling learning in games as a feedback interconnection between a learning operator (payoff \to strategy) and a game operator (strategy \to payoff). Subsequent works [ 28 , 29 ] employed equilibrium–independent passivity to study convergence in zero–sum games and to design higher–order learning dynamics that converge in settings where first–order models fail. More recently, citeabdelraouf2025passivity proposed a passivity–based classification of learning dynamics according to the notion of passivity they satisfy, incremental passivity, equilibrium–independent passivity, and \delta -passivity, and used it as a unifying framework to analyze convergence in contractive games. Moreover, [ 30 ] employs counterclockwise dissipativity to study convergence in potential games. Going beyond convergence guarantees, the primary objective of a learning agent is to maximize its cumulative reward over time. Finite regret ensures that, in the long run, a learning dynamics achieves an average reward no worse than that of any fixed strategy in hindsight. Building on this perspective, [ 31 ] establishes a rigorous equivalence between finite regret and a passivity property: passivity from the payoff signal to the deviation of the evolving strategy from any fixed strategy in the simplex is equivalent to finite regret. This result raises a fundamental question: is finite regret alone sufficient to assess the performance of learning dynamics as measured by asymptotic average reward? In particular, when two learning models both satisfy no–regret guarantees, does one outperform the other in the long run? Equivalently, does there exist a “free lunch” among no–regret algorithms, namely, a learning rule that achieves uniformly higher average reward across all payoff environments? If so, a learner may incur regret not for violating no–regret, but for selecting an suboptimal no–regret algorithm. Addressing this question is the central focus of this paper. The main contributions are summarized as follows: • We provide explicit counterexamples demonstrating that finite regret alone is not sufficient to assess the performance of learning dynamics, by showing environments in which finite–regret dynamics outperform dynamics without finite regret, and vice versa (Section III ). • We model payoff–based higher–order replicator dynamics as a cascade interconnection between a diagonal LTI system G(s)=g(s)I_{n} and the softmax mapping, and show that anticipatory replicator dynamics is dynamically equivalent to predictive replicator dynamics equipped with a first–order low–pass predictor (Section IV ). • We introduce an oracle replicator dynamics (predictive RD with perfect prediction) and prove that it uniformly dominates standard replicator dynamics for all payoff trajectories (Section V ). • We provide a frequency–domain interpretation of performance for higher–order replicator dynamics, modeled as a cascade interconnection between a diagonal LTI system g(s)I_{n} and the softmax mapping, and establish rigorous links

Read the complete text