Lune

NeurIPS2024Top-tier venue

On Tractable Φ-Equilibria in Non-Concave Games

Yang Cai, Constantinos Daskalakis, Haipeng Luo, Chen-Yu Wei, Weiqiang Zheng

Abstract

While Online Gradient Descent and other no-regret learning procedures are known to efficiently converge to a coarse correlated equilibrium in games where each agent's utility is concave in their own strategy, this is not the case when utilities are non-concave -a common scenario in machine learning applications involving strategies parameterized by deep neural networks, or when agents' utilities are computed by neural networks, or both. Non-concave games introduce significant game-theoretic and optimization challenges: (i) Nash equilibria may not exist; (ii) local Nash equilibria, though they exist, are intractable; and (iii) mixed Nash, correlated, and coarse correlated equilibria generally have infinite support and are intractable. To sidestep these challenges, we revisit the classical solution concept of Φ-equilibria introduced by Greenwald and Jafari [GJ03], which is guaranteed to exist for an arbitrary set of strategy modifications Φ even in non-concave games [SL07]. However, the tractability of Φ-equilibria in such games remains elusive. In this paper, we initiate the study of tractable Φ-equilibria in non-concave games and examine several natural families of strategy modifications. We show that when Φ is finite, there exists an efficient uncoupled learning algorithm that converges to the corresponding Φ-equilibria. Additionally, we explore cases where Φ is infinite but consists of local modifications. We show that approximating local Φequilibria beyond the first-order stationary regime is computationally intractable. In contrast, within this regime, learning Φ-equilibria reduces to achieving low Φ-regret in online learning with convex loss functions, and we show Online Gradient Descent efficiently converges to Φ-equilibria for several natural infinite families of modifications. A byproduct of our convergence analysis is a new structural family of modifications inspired by the well-studied proximal operator, and we refer to the corresponding regret as proximal regret. This set of modifications is rich, and we show that small proximal regret implies not only small external regret but also other desirable properties, such as marginal coverage in online conformal prediction. To our knowledge, this notion has not been previously studied, even in online convex optimization. Despite the complexity of handling a rich set of modifications, we prove that Online Gradient Descent achieves sublinear proximal regret fore convex loss functions.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

6 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Comparator-Adaptive Φ-Regret: Improved Bounds, Simpler Algorithms, and Applications to Games cites Near-Optimal No-Regret Learning in General Games
  • Implicit Learning Dynamics in Stackelberg Games: Equilibria Characterization, Convergence Analysis, and Empirical Study cites What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
  • Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games cites Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games
  • Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games cites Near-Optimal No-Regret Learning in General Games
  • Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games cites First-Order (Coarse) Correlated Equilibria in Non-concave Games
  • First-Order (Coarse) Correlated Equilibria in Non-concave Games cites Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers6

  1. Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex GamesConstantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Charilaos Pipis et al.STOC 2025 · 14 citations
  2. First-Order (Coarse) Correlated Equilibria in Non-concave GamesMete Seref AhunbaySTOC 2026 · 6 citations
  3. Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and GamesYang Cai, Constantinos Daskalakis, Haipeng Luo, Chen-Yu Wei et al.STOC 2026 · 5 citations
  4. Comparator-Adaptive Φ-Regret: Improved Bounds, Simpler Algorithms, and Applications to GamesSoumita Hait, Ping Li, Haipeng Luo, Mengxiao ZhangNeurIPS 2025 · 4 citations
  5. Online Conformal Prediction via Universal Portfolio AlgorithmsTuo Liu, Edgar Dobriban, Francesco OrabonaICML 2026 · 4 citations

Builds on28

  1. What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?Chi Jin, Praneeth Netrapalli, Michael I. JordanICML 2020 · 381 citations
  2. Implicit Learning Dynamics in Stackelberg Games: Equilibria Characterization, Convergence Analysis, and Empirical StudyTanner Fiez, Benjamin Chasnov, Lillian J. RatliffICML 2020 · 144 citations
  3. Near-Optimal No-Regret Learning in General GamesConstantinos Daskalakis, Maxwell Fishelson, Noah GolowichNeurIPS 2021 · 141 citations
  4. On Solving Minimax Optimization Locally: A Follow-the-Ridge ApproachYuanhao Wang, Guodong Zhang, Jimmy BaICLR 2020 · 106 citations
  5. The Limits of Min-Max Optimization Algorithms: Convergence to Spurious Non-Critical SetsYa-Ping Hsieh, Panayotis Mertikopoulos, Volkan CevherICML 2021 · 96 citations

Related papers

  1. Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror DescentYu Bai, Chi Jin, Song Mei, Ziang Song et al.NeurIPS 2022 · 24 citations
  2. Exploiting hidden structures in non-convex games for convergence to Nash equilibriumIosif Sakos, Emmanouil V. Vlatakis-Gkaragkounis, Panayotis Mertikopoulos, Georgios PiliourasNeurIPS 2023 · 7 citations
  3. Turbocharging Solution Concepts: Solving NEs, CEs and CCEs with Neural Equilibrium SolversLuke Marris, Ian Gemp, Thomas Anthony, Andrea Tacchetti et al.NeurIPS 2022 · 22 citations
  4. Equivalence Analysis between Counterfactual Regret Minimization and Online Mirror DescentWeiming Liu, Huacong Jiang, Bin Li, Houqiang LiICML 2022 · 13 citations
  5. Near-Optimal No-Regret Learning Dynamics for General Convex GamesGabriele Farina, Ioannis Anagnostides, Haipeng Luo, Chung-Wei Lee et al.NeurIPS 2022 · 43 citations
Dusk over the sea between two cliffs drawn in fine vertical lines