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

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

We investigate the strategic surplus obtainable against a Follow-the-Regularized-Leader (FTRL) learner with constant step size ηη in n×mn\times m two-player zero-sum games played over TT 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 Ω(Nsub/η)Ω(N_{\mathrm{sub}}/η), proving that utility surplus scales with the number of the learner's suboptimal actions NN and vanishes in their absence. Second, for an alternating optimizer, a surplus of Ω(ηT/poly(n,m))Ω(η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

Figure 1
Figure 1: Fixed max-min strategy, Game 1 * . Surplus Θ(Tβ)\Theta(T^{\beta}) , confirming the Inverse-Rate Law .
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/2q=1/2 , and Euclidean regularizers. Curves use η=T−β\eta=T^{-\beta} , β∈{0,0.3,0.5,0.7,1.0}\beta\in\{0,0.3,0.5,0.7,1.0\} , with T=100T=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/2q=1/2 , and Euclidean regularizers. Curves use η=T−β\eta=T^{-\beta} , β∈{0,0.3,0.5,0.7,1.0}\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/2q=1/2 , and Euclidean regularizers. Curves use η=T−β\eta=T^{-\beta} , β∈{0,0.3,0.5,0.7,1.0}\beta\in\{0,0.3,0.5,0.7,1.0\} , with T=10000T=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/2q=1/2 , and Euclidean regularizer (top to bottom). Curves correspond to step sizes η=T−β\eta=T^{-\beta} , β∈{0,0.3,0.5,0.7,1.0}\beta\in\{0,0.3,0.5,0.7,1.0\} , with T=5000T=5000 and γ=0.02\gamma=0.02 . For each setting, we run 500500 independent trials and plot the median together with the 1010 th and 9090 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/2q=1/2 , and Euclidean regularizer (top to bottom). Curves correspond to step sizes η=T−β\eta=T^{-\beta} , β∈{0,0.3,0.5,0.7,1.0}\beta\in\{0,0.3,0.5,0.7,1.0\} , with T=5000T=5000 and γ=0.025\gamma=0.025 . For each parameter setting we run 500500 independent trials and plot the median together with the 1010 th and 9090 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/2q=1/2 , and Euclidean regularizer (top to bottom). Curves correspond to step sizes η=T−β\eta=T^{-\beta} , β∈{0,0.3,0.5,0.7,1.0}\beta\in\{0,0.3,0.5,0.7,1.0\} , with T=5000T=5000 and γ=0.11\gamma=0.11 . For each parameter setting we run 500500 independent trials and plot the median together with the 1010 th and 9090 th percentiles.
More in this topic

Game Theory

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

See all 236 papers

Explore similar work

CardsList

  1. Constant Individual Regret in General Games

    Aug 31, 2026Mingyang Liu, Gabriele Farina, Asuman OzdaglarGame TheoryFollow-the-Regularized-Leader

    LIDS, EECS, Massachusetts Institute of Technology

  2. Constant regret in general games via higher-order optimism

    Sep 3, 2026Omar Abbadi, Rida Laraki, Panayotis MertikopoulosFollow-the-Regularized-LeaderRegret Minimization

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

  3. Multiplicative Optimism for Constant Regret in Games

    Sep 18, 2026Ashkan Soleymani, Georgios PiliourasRegret MinimizationGame-Based Learning

    MIT · Google Deepmind