On Tractable Φ-Equilibria in Non-Concave Games

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.