No Coin Left Behind: Maximizing Strategic Surplus Against No-Regret Dynamics

Yiheng Su; Emmanouil-Vasileios Vlatakis-Gkaragkounis

cs.GTApr 6, 2026

No Coin Left Behind: Maximizing Strategic Surplus Against No-Regret Dynamics

Authors: Yiheng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis

Organizations: University of Wisconsin–Madison

Abstract

We investigate the strategic surplus obtainable against a Follow-the-Regularized-Leader (FTRL) learner with constant step size $η$ in $n\times m$ two-player zero-sum games played over $T$ rounds against a clairvoyant optimizer. In contrast with prior analysis, we show that the extraction of such regret-scale surplus is an inherent feature of the FTRL family, rather than an artifact of specific instantiations. First, for a fixed max-min optimizer, we establish a sweeping law of order $Ω(N_{\mathrm{sub}}/η)$ , proving that utility surplus scales with the number of the learner's suboptimal actions $N$ and vanishes in their absence. Second, for an alternating optimizer, a surplus of $Ω(ηT/\mathrm{poly}(n,m))$ can be guaranteed regardless of the equilibrium structure, with high probability, in random games. Our analysis uncovers a sharp geometric dichotomy: non-steep regularizers allow the optimizer to realize the maximal transient surplus via finite-time elimination of suboptimal actions, whereas steep regularizers introduce a vanishing tail correction that can delay surplus saturation. Finally, we discuss whether this leverage persists under bilateral payoff uncertainty and propose a susceptibility measure quantifying which regularizers are most vulnerable to learner-aware strategic steering.

Figures & tables

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: Full-feedback results for RPS. We plot cumulative optimizer surplus under the fixed max-min optimizer (left) and alternating trap optimizer (right) for Negative Entropy, Negative Tsallis $q=1/2$ , and Euclidean regularizers. Curves use $\eta=T^{-\beta}$ , $\beta\in\{0,0.3,0.5,0.7,1.0\}$ , with $T=100$ . For the fixed strategy, all surplus curves are identically zero.

Figure 5: Full-feedback results for Game 1. We plot cumulative optimizer surplus under the fixed max-min optimizer (left) and alternating trap optimizer (right) for Negative Entropy, Negative Tsallis $q=1/2$ , and Euclidean regularizers. Curves use $\eta=T^{-\beta}$ , $\beta\in\{0,0.3,0.5,0.7,1.0\}$ .

Figure 6: Full-feedback results for random Game 3. We plot cumulative optimizer surplus under the fixed max-min optimizer (left) and alternating trap optimizer (right) for Negative Entropy, Negative Tsallis $q=1/2$ , and Euclidean regularizers. Curves use $\eta=T^{-\beta}$ , $\beta\in\{0,0.3,0.5,0.7,1.0\}$ , with $T=10000$ .

Figure 7: Bandit-feedback results for RPS. We plot cumulative realized optimizer surplus under the fixed max-min optimizer (left) and the alternating trap optimizer (right) for Negative Entropy, Negative Tsallis with $q=1/2$ , and Euclidean regularizer (top to bottom). Curves correspond to step sizes $\eta=T^{-\beta}$ , $\beta\in\{0,0.3,0.5,0.7,1.0\}$ , with $T=5000$ and $\gamma=0.02$ . For each setting, we run $500$ independent trials and plot the median together with the $10$ th and $90$ th percentiles.

Figure 8: Bandit-feedback results for Game 1. We plot the cumulative realized optimizer surplus under the fixed max-min optimizer (left) and the alternating trap optimizer (right) for negative entropy, negative Tsallis with $q=1/2$ , and Euclidean regularizer (top to bottom). Curves correspond to step sizes $\eta=T^{-\beta}$ , $\beta\in\{0,0.3,0.5,0.7,1.0\}$ , with $T=5000$ and $\gamma=0.025$ . For each parameter setting we run $500$ independent trials and plot the median together with the $10$ th and $90$ th percentiles.

Figure 9: Bandit-feedback results for random game. We plot cumulative realized optimizer surplus under the fixed max-min optimizer (left) and the alternating trap optimizer (right) for negative entropy, negative Tsallis with $q=1/2$ , and Euclidean regularizer (top to bottom). Curves correspond to step sizes $\eta=T^{-\beta}$ , $\beta\in\{0,0.3,0.5,0.7,1.0\}$ , with $T=5000$ and $\gamma=0.11$ . For each parameter setting we run $500$ independent trials and plot the median together with the $10$ th and $90$ th percentiles.

Game Theory

Game theory studies how interacting decision-makers choose strategies, form agreements, and shape outcomes under competition and cooperation.

See all 236 papers

Aug 31, 2026

Constant Individual Regret in General Games

Uncoupled no-regret dynamics provide a decentralized route to equilibrium, but prior guarantees for individual regret retain a polylogarithmic dependence on the horizon. We remove this dependence for every finite

N

-player normal-form game under full-information feedback. We introduce ECHO-OFTRL: optimistic follow-the-regularized-leader (OFTRL) equipped with an EMA cascade for high-order optimism (ECHO), where EMA denotes exponential moving average. The algorithm is deterministic and fully uncoupled. If

m_{\max}

denotes the largest action-set size, then, simultaneously for every horizon

T\geq1

, it guarantees that each of the

N

players in the game incurs regret upper bounded by

O(\textrm{poly}(N, \log m_{\max}))

. Our algorithm leverages a new form of optimism inspired by modern filter design.

Mingyang Liu, Gabriele Farina, Asuman Ozdaglar

LIDS, EECS, Massachusetts Institute of Technology

Game Theory Follow-the-Regularized-Leader Regret Minimization

Ask PDF

Sep 3, 2026

Constant regret in general games via higher-order optimism

We introduce an uncoupled learning algorithm which, when employed by all players of an arbitrary

N

-player normal form game with up to

K

actions per player, guarantees

O(N^3\log^2 K)

individual regret, uniformly over the horizon of play. The proposed algorithm - which we call higher-order optimism with discounting (HOOD) is a variant of optimistic follow-the-regularized-leader (OptFTRL) that combines a discounted

(N+1)

-th order predictor with entropic regularization over a suitable "lifting" of the game's strategy space. This combination of ingredients is purposefully designed to dampen large oscillations of the induced sequence of play in a controlled manner, removing in this way a key stumbling block of previous attempts to achieve constant regret in general games. Our approach bears several striking similarities to the concurrent - and completely independent - work of Liu, Farina, and Ozdaglar (arXiv:2608.31166), who very recently derived an

O(N^{21}\log^{4} K)

regret bound through the use of higher-order optimism and an exponential moving average estimator.

Omar Abbadi, Rida Laraki, Panayotis Mertikopoulos

Univ. Mohammed VI Polytechnic, CMSIS, MCGT, 11103 Rabat, Morocco · Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France

Follow-the-Regularized-Leader Regret Minimization

Ask PDF

Sep 18, 2026

Multiplicative Optimism for Constant Regret in Games

We introduce Multiplicatively Optimistic Regret Matching (MORM), an uncoupled learning rule for finite general-sum games. Under simultaneous full-information self-play, every player achieves external regret

O(\sqrt n\log d)

uniformly over all horizons, using only one-step optimism. The analysis combines a potential-based regret-matching argument with multiplicative stability and Hellinger control of strategy movement. A learning-rate safeguard additionally gives

O(\sqrt{T\log d})

regret in the face of adversarial utilities.

Ashkan Soleymani, Georgios Piliouras

MIT · Google Deepmind

Regret Minimization Game-Based Learning

Ask PDF

Abstract

Game Theory

Explore similar work

Constant Individual Regret in General Games

Constant regret in general games via higher-order optimism

Multiplicative Optimism for Constant Regret in Games