# Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games

arXiv: https://arxiv.org/abs/2412.20291 · HTML: https://mlsanity.com/paper/2412.20291/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Dec 2024.

## Built on by (most cited first, 12 of 12)

- [Full Swap Regret and Discretized Calibration](https://mlsanity.com/paper/2502.09332/) (2025)
- [Swap Regret and Correlated Equilibria Beyond Normal-Form Games](https://mlsanity.com/paper/2502.20229/) (2025)
- [Expected Variational Inequalities](https://mlsanity.com/paper/2502.18605/) (2025)
- [Learning and Computation of Phi-Equilibria at the Frontier of Tractability](https://mlsanity.com/paper/2502.18582/) (2025)
- [The Stability of Online Algorithms in Performative Prediction](https://mlsanity.com/paper/2602.24207/) (2026)
- [Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games](https://mlsanity.com/paper/2511.01852/) (2025)
- [An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to Phi-Regret Minimization](https://mlsanity.com/paper/2604.19592/) (2026)
- [From No-Regret to Strategically Robust Learning in Repeated Auctions](https://mlsanity.com/paper/2601.03853/) (2026)
- [Swap Regret Minimization Through Response-Based Approachability](https://mlsanity.com/paper/2602.06264/) (2026)
- [Efficient Opportunistic Approachability](https://mlsanity.com/paper/2602.21328/) (2026)
- [Stabilizing Performative Feedback Loops with Minimal Model Deployments](https://mlsanity.com/paper/2609.14065/) (2026)
- [Normal-Form Correlation in Markov Games](https://mlsanity.com/paper/2610.03621/) (2026)

## Abstract (arXiv)

We propose efficient no-regret learning dynamics and ellipsoid-based methods for computing linear correlated equilibriaunicodex2014a relaxation of correlated equilibria and a strengthening of coarse correlated equilibriaunicodex2014in general convex games. These are games where the number of pure strategies is potentially exponential in the natural representation of the game, such as extensive-form games. Our work identifies linear correlated equilibria as the tightest known notion of equilibrium that is computable in polynomial time and is efficiently learnable for general convex games. Our results are enabled by a generalization of the seminal framework of of Gordon et al. [2008] for Phi-regret minimization, providing extensions to this framework that can be used even when the set of deviations Phi is intractable to separate/optimize over. Our polynomial-time algorithms are similarly enabled by extending the Ellipsoid-Against-Hope approach of Papadimitriou and Roughgarden [2008] and its generalization to games of non-polynomial type proposed by Farina and Pipis [2024a]. We provide an extension to these approaches when we do not have access to the separation oracles required by these works for the dual player.