REVIEW 2 major objections 4 minor 2 cited by
Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games
T0 review · 2 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash
Pith's one-line read This paper proves that linear correlated equilibrium — the tightest known tractable refinement of coarse correlated equilibrium — can be computed in polynomial time and learned by efficient no-regret dynamics in every convex game.
desk verdict Genuinely new algorithmic techniques and likely the right answer, but the main-text proof of Theorem 5.4 has a non-full-dimensionality gap and a wrong norm bound, both fixable. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing objects are the semi-separation oracle and the shell sets. The semi-separation oracle minimizes the convex function $\|\phi(p) - p\|^2$ over $P$ for a candidate affine map $\phi$; if the minimum is zero it returns a fixed point of $\phi$ in $P$, and otherwise the residual direction $u = \phi(p^*) - p^*$ yields the linear constraint $\langle \phi'(p_u), u \rangle \le \langle p_u, u \rangle$ that every true endomorphism $\phi'$ of $P$ satisfies but that $\phi$ violates, giving a genuine separating hyperplane from $\Phi(P)$. This oracle is what the classical $\Phi$-regret framework lacked, since full separation over $\Phi(P)$ is provably intractable from oracle access alone. The shell machinery maintains a convex superset $\tilde\Phi$ of $\Phi(P)$, defined by polynomially many half-spaces, and refines it each round: Shell Ellipsoid shrinks the shell until it either finds a transformation with a fixed point in $P$ or cuts the shell away from $\Phi(P)$, and Shell Projection guarantees that the projected transformation still has a fixed point in $P$, so that the dual-regret reduction — playing a fixed point of each played transformation, making primal and dual regret equal — goes through. For equilibrium computation, the same fixed-point-based responses serve as the good-enough-response oracle inside a generalized Ellipsoid Against Hope for general convex sets.
What would settle it
One concrete disproof would be a convex game presented through polynomial oracles that satisfies the polynomial utility gradient property yet whose every $\epsilon$-approximate linear correlated equilibrium requires super-polynomially many product distributions to represent, contradicting the paper's succinct mixture representation; another would be a well-bounded convex set $P$ given by a polynomial separation oracle and adversarial linear losses on which every oracle-polynomial algorithm incurs linear rather than $O(\sqrt{T})$ linear swap regret.
Extended reading notes
Core claim
The central claim is that, for every convex game — $n$ players with compact convex strategy sets $P_i \subset \mathbb{R}^{d_i}$ and multi-linear utilities, accessed only through membership, separation, or optimization oracles — an $\epsilon$-approximate linear correlated equilibrium can be computed in time polynomial in the dimensions and in $\log(1/\epsilon)$, and can be learned by efficient no-linear-swap-regret dynamics. The regret result holds against an adversarial sequence of linear losses over a single convex set $P$, achieving $O(d^4\sqrt{T})$ linear swap regret after $T$ rounds. Both algorithms operate in a regime where no efficient separation oracle for the set $\Phi(P)$ of linear endomorphisms of $P$ can exist, a hardness the paper proves by showing that distinguishing the ball from a capped ball requires exponentially many membership queries. The resolution is the semi-separation oracle: for any affine map $\phi$, it either finds a fixed point of $\phi$ inside $P$ or produces a hyperplane that genuinely separates $\phi$ from $\Phi(P)$, and this weaker primitive turns out to be sufficient for both the shell-based regret minimizer and a generalization of the Ellipsoid Against Hope method to non-polyhedral strategy sets. On this basis the paper identifies linear correlated equilibrium as the tightest known notion of equilibrium that is simultaneously polynomial-time computable and efficiently learnable for general convex games.
Load-bearing premise
The equilibrium-computation result rests on the assumption that each player's expected utility gradient against any product distribution of opponents' strategies can be computed in polynomial time; if that is not possible, the algorithm's fixed-point-based responses cannot be constructed, while the regret-minimization result needs only oracle access to the strategy set.
Editorial extensions
If this is right
- In any convex game with oracle access to the strategy sets and the polynomial utility gradient property, an $\epsilon$-approximate linear correlated equilibrium can be computed in oracle-polynomial time and represented as a mixture of polynomially many product distributions.
- A learner with oracle access to a convex strategy set $P$ can keep linear swap regret at $O(d^4\sqrt{T})$ after $T$ rounds against adversarial losses, and using such learners as players in a convex game drives the joint play toward a linear correlated equilibrium.
- Every previously known polynomial-time result for linear swap regret and linear correlated equilibria, which was confined to extensive-form games, now extends to all convex games, including Bayesian games, routing games, and resource-allocation games.
- The classical $\Phi$-regret algorithm required two subroutines, fixed-point computation and separation over $\Phi$; with fixed points known to be necessary, the paper's result shows the sufficient and load-bearing ingredient is the semi-separation oracle, not separation.
- For convex sets given by small explicit H- or V-representations, efficient membership oracles for the endomorphism set follow directly from the paper's lemmas, so the shell machinery is only needed for the fully general oracle-access setting.
Reading between the lines
- I would take the semi-separation recipe to be the paper's transferable lesson: any deviation class admitting an efficient fixed-point test but no tractable separation could be plugged into the same shell-based regret minimizer and Ellipsoid Against Hope extension, possibly generalizing the result beyond affine linear maps.
- The paper leaves open the boundary question of whether linear correlated equilibrium is literally the strongest polynomial-time notion, or merely the strongest known: a sharper statement would require proving that every $\Phi$ strictly between constant deviations and all linear endomorphisms is either computable or provably hard.
- A natural next target is welfare-optimal linear correlated equilibrium: the oracle model plus the polynomial utility gradient property may suffice to optimize over the linear correlated equilibrium polytope, even though the paper computes one equilibrium rather than the best one.
- Because the learner-side result holds against adversarial linear losses, I would expect it to transfer beyond equilibrium computation, for example to designing learners that resist strategic manipulation in Bayesian games, where this protection was previously available only in restricted game classes.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the computation and online learning of linear correlated equilibria (LCE) in general convex games, i.e., games in which each player's strategy set is an arbitrary compact convex set given by oracle access. The main contributions are: (i) a no-regret algorithm that achieves O(d^4 sqrt(T)) linear swap regret against adversarial linear losses for a convex action set P (Theorem 4.5), and (ii) an oracle-polynomial-time algorithm for computing an epsilon-approximate LCE under the polynomial utility gradient property (Theorem 5.4). The technical engine is a new "semi-separation oracle" for the set of linear endomorphisms of a convex set, together with shell-ellipsoid methods and an extension of the Ellipsoid Against Hope framework. The appendices provide weak-oracle variants of both results, addressing precision issues.
Significance. If the main claims hold, this is a meaningful advance: LCE is identified as the tightest known equilibrium notion that is simultaneously polynomially computable and efficiently learnable for general convex games, and the paper answers an open question about whether regret minimization is possible without a separation oracle over the deviation set. The semi-separation concept is a genuine technical contribution, and the regret side (Theorem 4.5) appears coherent. The computation side, however, currently has two load-bearing proof gaps in the main text; both are localized and the weak-oracle appendix contains the likely intended repair. The paper is also explicit that the equilibrium-computation result depends on Assumption 5.2 (polynomial utility gradient property), which is correctly identified as a structural assumption rather than a hidden free parameter.
major comments (2)
- [§5.2, proof of Theorem 5.4] Theorem 5.1's Condition 2 requires a Euclidean ball B^N(r_y) contained in Y. In the equilibrium construction, Y = {1} × Φ(P_1) × ... × Φ(P_n) lies in the affine hyperplane y_1 = 1, so Y has empty interior in R^N and contains no such ball. The proof of Theorem 5.4 invokes Algorithm 5 / Theorem 5.1 without repairing this. The intended repair -- replacing Y by the inflated full-dimensional set Y' = [1-gamma,1+gamma] × Φ(P_1,delta) × ... × Φ(P_n,delta) -- appears only in the weak-oracle appendix, in the proof of Theorem F.3, and is absent from the strong theorem. As written, the proof of Theorem 5.4 does not establish the stated polynomial-time guarantee.
- [§5.2, proof of Theorem 5.4; Appendix F.2, proof of Theorem F.3] The assertion that ||x^T A||_2 ≤ sqrt(N) is false. By the definition of A, the column j = ∅ is A_{k,∅} = Σ_i U_i[k], so (x^T A)_∅ = Σ_i E_{s∼x}[u_i(s)], which can be as large as n. For example, with n = 3, each d_i = 1, P_i = [0,1], and u_i ≡ 1, this entry is 3 while sqrt(N) = sqrt(7) ≈ 2.65. The same incorrect bound is used in Appendix F.2, where B is set to sqrt(N). The correct bound is B = n sqrt(N), which is still polynomial in the input since n ≤ Σ_i d_i. The proof must be updated in both the strong theorem and the weak-oracle theorem; the subsequent runtime conclusions are unaffected once this correction is made.
minor comments (4)
- [§3, Corollary 3.3] The statement says "it is possible to construct an efficient membership oracle for P," but this is tautological given the existing oracle access; the intended statement is clearly a membership oracle for Φ(P).
- [§4.1, proof of Lemma 4.1] In the sentence "we have that ⟨φ(p) − x, u⟩ > 0 for all p ∈ P," the symbol x should be p; the correct expression is ⟨φ(p) − p, u⟩ > 0.
- [§5.2, final paragraph of Theorem 5.4 proof] The proof refers to "Algorithm 10" and "Algorithm 1" when invoking the Ellipsoid Against Hope routine; the main text's algorithm is Algorithm 5. These cross-references should be corrected.
- [Abstract] The abstract contains a typo: "strenghtening" should be "strengthening."
Circularity Check
No significant circularity: the core algorithms are derived from first principles under explicit oracle assumptions, and the self-citations are contextual or non-load-bearing.
full rationale
The paper's derivation chain is self-contained. Lemma 4.1 constructs the semi-separation oracle directly from convex optimality and oracle access to P, and the shell ellipsoid and shell projection results (Lemmas 4.2 and 4.4, Theorem 4.5) are proved from that oracle together with the standard Gordon et al. regret decomposition; no fitted parameter is renamed as a prediction. The equilibrium computation (Theorem 5.1 and Theorem 5.4) re-proves the Ellipsoid-Against-Hope extension rather than importing it as a black box, and Lemma 5.3 verifies the meta-game payoff equals the sum of linear regrets by direct multilinear expansion. Self-citations to Farina and Pipis (2024a,b) and Dann et al. provide context, an explicitly stated input assumption (Assumption 5.2), or algebraic shorthand; the central algorithms do not reduce to those prior results. The main-text proof's non-full-dimensional Y and the bound ||x^T A||_2 <= sqrt(N) are technical correctness gaps that the weak-oracle appendix addresses, but they are not instances of circularity.
Assumptions & free parameters
assumptions (5)
- domain assumption Well-boundedness and full-dimensionality of strategy sets: B^d(r) ⊆ P ⊆ B^d(0,R) for each player's strategy set P.
- standard math Oracle access (membership, separation, optimization) to each convex strategy set P, with equivalence under well-boundedness.
- domain assumption Polynomial utility gradient property (Assumption 5.2): for any product distribution x, E_{s_-i~x_-i}[∇u_i(s_-i)] is computable in polynomial time.
- domain assumption Isotropic position of P can be computed (or assumed without loss of generality) in polynomial time.
- standard math Brouwer fixed point theorem and the minimax theorem.
Cite this review
Pith. "Pith review of Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games." pith.science (2026). https://pith.science/paper/OZBTMKQF
@misc{pith2026241220291,
author = {Pith},
title = {Pith review of: Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games},
year = {2026},
howpublished = {\url{https://pith.science/paper/OZBTMKQF}},
note = {Machine review of arXiv:2412.20291}
}
abstract
We propose efficient no-regret learning dynamics and ellipsoid-based methods for computing linear correlated equilibria$\unicode{x2014}$a relaxation of correlated equilibria and a strengthening of coarse correlated equilibria$\unicode{x2014}$in 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.
Figures
Forward citations
Cited by 2 Pith papers
-
Full Swap Regret and Discretized Calibration
New algorithms minimize swap regret against arbitrary functions on convex action sets, yielding O~(T^{1/3}) ℓ2-calibration error and O~(max(T^{1/3}, sqrt(ǫT))) discretized-calibration error.
-
Learning to Play Against Unknown Opponents
For repeated games against an unknown optimizer type, the paper gives polynomial-time optimal no-regret commitment, near-optimal general commitment when the game or support size is constant, a polynomial-per-step maxi...
Reference graph
Works this paper leans on
-
[1]
Let Φd ⊆ Rd×(d+1) be the set of linear endomorphisms ofBd. Given a κ ∈ (0, 1) and a unit vector u ∈ Rd, define thed-dimensional κ-capped ball Bd(κ, u) to be the intersection ofBd with the half-space ⟨x, u⟩ ≤κ (note that this corresponds to removing a “cap” fromBd). Similarly, we let Φd(κ, u) ⊆ Rd×(d+1) be the set of linear endomorphisms ofBd(κ, u). We pro...
-
[2]
Then, ⟨∇f ( ˆx), x − ˆx⟩ ≥ −δ ∀x ∈ P−ϵ, where δ := 6B2R2p ϵ/r
For someϵ >0, let x∗ = arg minx∈P −ϵ f (x) and let ˆx ∈ P+ϵ be a weak solution such thatf ( ˆx) ≤ f (x) + ϵ for all x ∈ P−ϵ. Then, ⟨∇f ( ˆx), x − ˆx⟩ ≥ −δ ∀x ∈ P−ϵ, where δ := 6B2R2p ϵ/r. Moreover, ∥M(x∗ − ˆx)∥2 ≤ 5BR p ϵ/r. Proof. ⟨∇f ( ˆx), x − ˆx⟩ = D M⊤(M ˆx + b), x − ˆx E = D M⊤(Mx∗ + b), x − ˆx E − D M⊤M(x∗ − ˆx), x − ˆx E 34 We have min x∈P −ϵ D M⊤...
-
[3]
Moreover, A − 4d−1 4d I ̸∈ Φd 2d−1 2d , u for all A ∈ Rd×d with ∥A∥2 < 1 4d
− 4d−1 4d I ̸∈ Φd 2d−1 2d , u for all u. Moreover, A − 4d−1 4d I ̸∈ Φd 2d−1 2d , u for all A ∈ Rd×d with ∥A∥2 < 1 4d
-
[4]
Thus, it is impossible to solve Weak Membership forΦ(P) with poly(d) membership queries toP
We requireΩ(exp(d)) queries to distinguishBd from Bd 2d−1 2d , u for all u. Thus, it is impossible to solve Weak Membership forΦ(P) with poly(d) membership queries toP. Proof. 1. A linear map ϕ is in Φd iff ∥ϕ∥2 ≤ 1. Indeed, we have − 4d−1 4d I 2 = 4d−1 4d and A − 4d−1 4d I 2 ≤ ∥A∥2 + 4d−1 4d I 2 ≤ 1 for all ∥A∥2 ≤ 1 4d. 36
-
[5]
Indeed, we have − 4d−1 4d (−u) ̸∈ Bd 2d−1 2d , u
A linear map ϕ in Φd 2d−1 2d , u must satisfy ϕ(−u) ∈ Bd 2d−1 2d , u . Indeed, we have − 4d−1 4d (−u) ̸∈ Bd 2d−1 2d , u . Moreover, A − 4d − 1 4d I (−u) 2 ≥ 4d − 1 4d − ∥Au∥2 ≥ 2d − 1 2d for all ∥A∥2 ≤ 1 4d. These two arguments and the fact that∥A∥2 ≤ ∥A∥F prove any algorithm for Weak Membership must accept− 4d−1 4d I for P = Bd and reject it forP = Bd 2d...
-
[6]
We will show that, for all u1, u2 ∈ U, u1 ̸= u2, the corresponding caps are disjoint
Consider the set U = n u ∈ Rd u[i] = ±1/ √ d for all i ∈ [d] o . We will show that, for all u1, u2 ∈ U, u1 ̸= u2, the corresponding caps are disjoint. That is, ifS1 = x ∈ Bd ⟨x, u1⟩ > 2d−1 2d and S2 = x ∈ Bd ⟨x, u2⟩ > 2d−1 2d , then S1 ∩ S2 = ∅. Let i be a coordinate upon whichu1, u2 differ. Assume WLOG u1[i] = −1 and u2[i] = 1. We will showx1[i] < 0 for ...
-
[7]
Taking squares, we have∥a∥2 2 ≥ ϵ/8
Thus, ∥a∥2 = ∥ϕ( ˆx) − ˆx∥2 ≥ ∥ϕ( ¯x) − ¯x∥2 − √ϵ 2 √ 2 ≥ √ϵ 2 √ 2 , (7) where the last inequality follows from (6). Taking squares, we have∥a∥2 2 ≥ ϵ/8. We conclude thata defines a strong separating hyperplane of0 from (A − I)P −ϵ + x0 as a⊤[(A − I)x′ + x0] ≥ ϵ/16 > 0 ∀x′ ∈ P−ϵ =⇒ a⊤ϕ(x′) > a⊤x′ ∀x′ ∈ P−ϵ. (8) Next, consider the convex programmaxx∈P a⊤Ax...
-
[8]
By definition, it must hold that ϕ′(x∗) = x′ for some x′ ∈ P−ϵ
∈ Φ(P, ϵ). By definition, it must hold that ϕ′(x∗) = x′ for some x′ ∈ P−ϵ. Thus, ⟨C, A⟩ + a⊤x0 = a⊤Ax∗ + a⊤x0 > a⊤x′ − γ = a⊤ϕ′(x∗) − γ = C, A′ + a⊤x′ 0 − γ. Finally, to get a valid weak separating hyperplane, it suffices to show thatN := max(∥C∥ℓ∞ , ∥a∥∞) >
Show all 17 references
-
[9]
We conclude that (C/N, a/N) ∈ Rd×(d+1) is a validϵ weak separating hyperplane becauseγ/N ≤ ϵ and 1 N ⟨C, A⟩ + 1 N a⊤x0 > 1 N C, A′ + 1 N a⊤x′ 0 − ϵ, for all (A, x′
To this end, note that, by(7), it holds∥a∥2 ≥ ϵ/8 = ⇒ N >∥a∥2 / √ d ≥ ϵ/(8 √ d). We conclude that (C/N, a/N) ∈ Rd×(d+1) is a validϵ weak separating hyperplane becauseγ/N ≤ ϵ and 1 N ⟨C, A⟩ + 1 N a⊤x0 > 1 N C, A′ + 1 N a⊤x′ 0 − ϵ, for all (A, x′
-
[10]
E.2 Shell Ellipsoid with Weak Oracles This is the weak version of Lemma 4.2
∈ Φ(P, ϵ). E.2 Shell Ellipsoid with Weak Oracles This is the weak version of Lemma 4.2. Lemma E.3(Shell Ellipsoid with Weak Oracles). Let P ⊂Rd be a compact convex set to which we have access via a weak separation oracle and which is well-bounded withBd(r) ⊆ P ⊆ Bd(0, R). For ...
1993
-
[11]
(Almost-empty intersection) For anyϕ ∈ Bd×(d+1)(ϕa, q− ϵ/(2H)) ∩ ˜Φ−ϵ′ it is ∥ϕa − ϕ∥F > q − ϵ 2H − ϵ 8H
-
[12]
˜Φ is a compact convex set such thatΦ(P, η)−ϵ ⊂ ˜Φ
-
[13]
Since ϕb ∈ Bd×(d+1)(ϕa, q), it follows that ∥ϕa − ϕb∥2 F ≤ q (9) and, additionally, Property 1 implies that ϕa − Π ˜Φ−ϵ′ (ϕa) F > q− ϵ 2H − ϵ 8H
(Consistency) There exists ϕb ∈ ˜Φ+ϵ′ ∩ Bd×(d+1)(ϕa, q) with an ϵ′-approximate fixed point inside P When the algorithm terminates, ϕb ∈ ˜Φ+ϵ′ ∩ Bd×(d+1)(ϕa, q) is a valid transformation with an ϵ′-approximate fixed point insideP. Since ϕb ∈ Bd×(d+1)(ϕa, q), it follows that ∥ϕa...
2022
-
[14]
A ∈ RM ×N is a matrix such that∀x ∈ X, x⊤A 2 ≤ B for some B ≥ 1
-
[15]
the set Y is well-bounded asBN (ry) ⊆ Y ⊆ BN (0, Ry),
-
[16]
there exists an oracle that for every pointy ∈ BN (0, Ry), either produces a weak separating hyperplane (SEP) of y from Y or a weak good-enough-response (GER),
-
[17]
min y∈Y x⊤Ay ≥ −ϵ
the encoding lengths of both theSEP and the GER responses produced by the previous oracle are polynomially bounded, then, Algorithm 10 runs in oracle-polynomial time and computes anexact solution x∗ to find x ∈ X (P) s.t. min y∈Y x⊤Ay ≥ −ϵ. Furthermore, x∗ is a mixture of poly...
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.