Research map / Optimization / Nonconvex and smooth optimization
On Tractable $\Phi$-Equilibria in Non-Concave Games
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 tractable Φ-equilibria in non-concave games: an efficient uncoupled algorithm for finite Φ, and for local deviation families shows Online Gradient Descent (via proximal regret) achieves first-order-stationary-regime approximate equilibria, with NP-hardness below O(δ²).
Problem
Non-concave games lack tractable equilibria: Nash may not exist and local Nash, mixed Nash, CCE have infinite support or are intractable. The paper asks whether Φ-equilibria, which always exist, can be computed efficiently.
Approach
For finite Φ, sample strategies from an approximately stationary tree-structured distribution so that no fixed-point computation is needed, giving sqrt(T log|Φ|) Φ-regret. For infinite local deviation families, reduce non-concave smooth losses to linear losses in the first-order regime (ε ≥ δ²L/2), and introduce proximal regret, which online gradient descent minimizes simultaneously for all convex
Key results
- Finite-Φ algorithm achieves O(sqrt(T log|Φ|)) Φ-regret with high probability in O(sqrt(T)|Φ|) time per iteration, using only bounded rewards.
- Online Gradient Descent achieves O(sqrt(T)) proximal regret for all convex or lsc functions f simultaneously, and O(T^{1/4}) under a stronger smoothness assumption with optimism.
- Approximating local Φ-equilibria with ε = o(δ²) is NP-hard, via a reduction from max clique using the Motzkin-Straus theorem.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the sampling-based algorithm with Hedge for a finite set of strategy modifications | Online learning with arbitrary bounded, possibly non-concave rewards · Finite strategy-modification sets | Φ-regret: 8\sqrt{T (\log |\Phi| + \log(1/\beta))} | Helped |
| Use Online Gradient Descent to control proximal regret as well as external regret | Online convex optimization · Convex loss functions | proximal regret: O(\sqrt{T}) | Helped |
| Have all players use Optimistic Gradient Descent in the game setting | Φprox(δ)-equilibrium learning · L-smooth games with shared gradient-variation assumption | individual proximal regret: O(T^{\frac{1}{4}}) | Helped |
| Target approximation finer than the first-order stationary regime | Computing Φ(δ)-equilibria · Smooth non-concave games | computational tractability: \varepsilon = o(\delta^2) | Hurt |
Surprising findings
- Some Φ-equilibria in non-concave games have support size exponential in dimension, so even writing down an ε-approximate mixed Nash equilibrium can require exponential size.
Limitations
- Approximation guarantee for infinite local families holds only in the first-order stationary regime (ε = Ω(δ²)); beyond it the problem is NP-hard.
- Extending the finite-Φ algorithm to infinite local families makes running time exponential in a natural parameter.
Experimental setup
Metrics: Φ-regret approximate Φ-equilibrium gap iteration complexity
Baselines: Gordon et al. Φ-regret algorithm with fixed-point computation
Builds on: Hedge Optimistic Gradient Descent Φ-regret minimization (Gordon et al.)
Closest papers by meaning
- Constrained Phi-Equilibria (ICML 2023 · similarity 0.91)
- On the Interplay between Social Welfare and Tractability of Equilibria (NeurIPS 2023 · similarity 0.91)
- Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem (NeurIPS 2024 · similarity 0.88)
- The Complexity of Correlated Equilibria in Generalized Games (NeurIPS 2025 · similarity 0.87)
- Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms (NeurIPS 2024 · similarity 0.87)
- Certifying Concavity and Monotonicity in Games via Sum-of-Squares Hierarchies (NeurIPS 2025 · similarity 0.87)
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.