Research map / Learning theory and algorithms / Submodular and game algorithms
Robust Equilibria in Continuous Games: From Strategic to Dynamic Robustness
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.
Defines strategic robustness of equilibria in continuous games via gradient-field perturbations, characterizes it geometrically, and shows it is equivalent to dynamic robustness under FTRL with constant step-size (sufficient and essentially necessary), with geometric convergence for entropic regularization under affine constraints.
Problem
Which equilibria of continuous games remain robust both to small perturbations of the payoff structure (strategic robustness) and arise as stable limit points of noisy FTRL learning dynamics (dynamic robustness)?
Approach
Measure game perturbations by the sup distance between individual payoff gradient fields rather than payoff values; define strategically robust equilibria as those invariant under small gradient perturbations, show this is equivalent to the gradient lying in the interior of the polar cone, and prove that such equilibria attract FTRL with high probability under stochastic gradient or payoff-based (
Key results
- Strategically robust equilibria (gradient in interior of polar cone) are shown to be stochastically asymptotically stable under FTRL with SFO and SPSA feedback, with high probability from a neighborhood.
- For affinely constrained polyhedral domains with decomposable regularizer, convergence to robust equilibria is geometric (exponential) for entropic regularization, versus subgeometric for vanishing step-size.
- A 1-player counterexample shows that the same non-robust boundary equilibrium attracts FTRL with probability 0 under x log x regularizer but with probability 1 under -2 sqrt(x), so strategic robustness cannot be relaxed.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use FTRL with sufficiently small step-size and stochastic gradient feedback | Strategically robust equilibria in continuous games · Continuous games | convergence probability: ≥1-conf | Helped |
| Use SPSA payoff-based feedback with mix_n proportional to 1/n^mixexp, mixexp in (0,1/2), and sufficiently small step-size | Strategically robust equilibria in continuous games · Continuous games | convergence probability: ≥1-conf | Helped |
| Use SPSA payoff-based feedback under affine constraints and a decomposable regularizer | FTRL at a strategically robust equilibrium · Affinely constrained domains | convergence rate: rate(-Θ(n)) | Helped |
| Use a decomposable regularizer on a polyhedral domain | FTRL at a strategically robust equilibrium · Polyhedral domains | convergence rate: rate(-Θ(n)) | Helped |
| Use an entropic regularizer | FTRL at a strict Nash equilibrium · Simplex | convergence rate: exp(-Θ(n)) | Helped |
| Apply FTRL with i.i.d. noise having positive-definite covariance at an interior equilibrium | Interior Nash equilibria · Continuous games | probability of convergence: 0 | Hurt |
| Use an entropic regularizer instead of the regularizer -2√x | FTRL in the one-player game with payoff -3/4 x^(4/3) · [0,1], equilibrium 0 | probability of convergence to 0: 1 -> 0 | Hurt |
| Use the regularizer -2√x instead of an entropic regularizer | FTRL in the one-player game with payoff -3/4 x^(4/3) · [0,1], equilibrium 0 | probability of convergence to 0: 0 -> 1 | Helped |
Surprising findings
- The same unique boundary equilibrium can be almost surely attracting or almost surely non-attracting depending only on the regularizer.
Limitations
- Robustness results are local, applying only to neighborhoods of equilibria
- Rate results require affinely constrained polyhedral domains and decomposable regularizers
- Theoretical paper with no empirical experiments
Experimental setup
Metrics: convergence to equilibrium convergence rate
Baselines: projected gradient ascent / stochastic gradient ascent vanishing step-size FTRL in concave games
Builds on: follow-the-regularized-leader stochastic approximation SPSA evolutionary stability of strict equilibria
Closest papers by meaning
- The impact of uncertainty on regularized learning in games (ICML 2025 · similarity 0.92)
- Roping in Uncertainty: Robustness and Regularization in Markov Games (ICML 2024 · similarity 0.90)
- Multi-Agent Learning under Uncertainty: Recurrence vs. Concentration (NeurIPS 2025 · similarity 0.89)
- The Complexity of Computing Robust Mediated Equilibria in Ordinal Games (AAAI 2024 · similarity 0.89)
- No Coin Left Behind: Maximizing Strategic Surplus Against No-Regret Dynamics (NeurIPS 2026 · similarity 0.88)
- Robust PAC Learning of Concurrent Stochastic Games (NeurIPS 2026 · similarity 0.88)
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.