Research map / Bandits and online learning / Online convex optimization and games
No Coin Left Behind: Maximizing Strategic Surplus Against No-Regret Dynamics
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies how much surplus a clairvoyant optimizer can extract from an FTRL learner in zero-sum games, showing regret-scale surplus (Omega(N/eta) for fixed max-min strategies, Omega(eta T) for alternating trap strategies) is structural to FTRL and governed by regularizer steepness.
Problem
Whether a strategic optimizer can extract regret-scale utility surplus from a no-regret FTRL learner in repeated two-player zero-sum matrix games, and how the regularizer geometry governs this.
Approach
Shows surplus extraction is a structural feature of the whole FTRL family: decomposes optimizer payoff into a value gap plus a learner approximation gap, derives an inverse-rate law (surplus ~ N_sub/eta) for fixed max-min play, and an alternating-trap strategy yielding Omega(eta T) on random games; steep vs non-steep regularizers give a dichotomy in saturation.
Key results
- For a fixed max-min optimizer, surplus scales as Theta(N_sub/eta) (inverse-rate law), vanishing when no suboptimal learner actions exist.
- For an alternating trap optimizer on random games, surplus at least Omega(eta T / poly(n,m)) holds with high probability, with explicit constant C = 1/(2M(nm)^6).
- Non-steep regularizers (Euclidean) saturate surplus in finite time while steep ones (entropic) have an infinite tail; the price of eps-best-response is Theta(1) for Euclidean vs Theta(log(1/eps)) for entropic.
Surprising findings
- Surplus extraction against FTRL learners persists even in zero-sum games, where prior work mostly considered general-sum settings.
- Steep regularizers (entropy), which are robust near the boundary, are the ones with unbounded learning cost in the price-of-best-response analysis.
Limitations
- Results hold for zero-sum matrix games with separable regularizers and full-information feedback.
- Constant step size only; optimizer assumed clairvoyant (knows learner rule, step size, regularizer and payoff matrix).
- Bandit-feedback results carry multiplicatively suboptimal constants.
Experimental setup
Metrics: cumulative surplus over von Neumann value regret scaling in eta and T
Baselines: Assos et al. (MWU/replicator dynamics exploitation)
Builds on: Multiplicative Weights Follow-the-Regularized-Leader Assos et al. MWU exploitation analysis
Closest papers by meaning
- Optimism Without Regularization: Constant Regret in Zero-Sum Games (NeurIPS 2025 · similarity 0.91)
- The impact of uncertainty on regularized learning in games (ICML 2025 · similarity 0.91)
- No-regret Learning in Harmonic Games: Extrapolation in the Face of Conflicting Interests (NeurIPS 2024 · similarity 0.91)
- Convergence of No-Swap-Regret Dynamics in Self-Play (NeurIPS 2024 · similarity 0.89)
- Learning from Delayed Feedback in Games via Extra Prediction (NeurIPS 2025 · similarity 0.89)
- Best of Both Worlds: Regret Minimization versus Minimax Play (ICML 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.