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

1 Introduction

• General convex games include normal-form, extensive-form, routing, resource-allocation, and firm-competition settings with compact convex strategy sets and multilinear utilities.Source: §1 · p. 3
• The central challenge is finding an equilibrium stronger than coarse correlated equilibrium that is efficiently computable from oracle access to convex strategy sets, alongside a corresponding stronger-than-external regret notion.Source: §1 · p. 4
• Linear correlated equilibria can be efficiently computed in general convex games, while efficient no-linear-swap-regret procedures operate against adversarial linear losses.These results use polynomially many oracle calls to the players’ strategy sets.Source: §1 · p. 4

1.1 Technical Innovation and Approach

• The paper’s key obstacle is that separation or membership over all linear endomorphisms may be computationally intractable even when the underlying strategy set has efficient oracles.Source: §1 · pp. 4–5, §1.1 · p. 5

1.2 Related Work

• The work extends prior Φ-regret and Ellipsoid-Against-Hope frameworks to settings lacking direct separation access, subsuming and generalizing several earlier linear-swap-regret and equilibrium-computation results.Source: §1.1 · p. 5, §1.2 · pp. 6–7

1.1 Technical Innovation and Approach

• A semi-separation oracle either finds a fixed point in the feasible set or returns a hyperplane separating the candidate transformation from the endomorphism set.Source: §1.1 · pp. 5–6, Figure 1 · p. 5

2.2 Linear Swap Regret and Linear Correlated Equilibria

• Linear swap regret minimizes Φ-regret over all affine linear maps from P to itself and reduces to standard swap regret on a simplex.Source: §2.2 · p. 8
• A convex game has compact convex strategy sets and multilinear payoff functions, encompassing Bayesian, extensive-form, norm-ball, and combinatorial-strategy games.Source: §2.2 · p. 8
• Linear correlated equilibrium is induced by requiring no player to benefit from any affine linear transformation of their strategy.Source: §2.2 · p. 8

2.3 Convex Optimization and Oracle Access

• The oracle model provides membership, separation, and optimization access to a bounded, full-dimensional convex strategy set, with isotropic-position normalization available without loss of generality.Source: §2.3 · p. 9
• The paper does not assume oracle access to the endomorphism set Φ(P), because such access does not necessarily follow from oracle access to P.Source: §2.3 · p. 9

2.4 From Linear Swap Regret Minimization to External Regret Minimization

• Standard swap-regret reductions learn transformations externally, then play a fixed point of each transformation; this makes the dual external regret equal to linear swap regret.Source: §2.4 · p. 10
• Recent alternative swap-regret methods achieve progress but incur exponential dependence on 1/ϵ.Source: §2.4 · p. 10

3.1 Endomorphisms of Simple Polytopes

• Succinct vertex or half-space representations enable efficient membership oracles for the set of linear endomorphisms, including the more general set Lin(A, B).The resulting oracle runs in polynomial time in the dimension and representation size.Source: §3.1 · p. 11
• Strategy sets from Bayesian games, extensive-form games, matchings, and flows can therefore support efficient linear-swap-regret minimization under the stated representation and isotropic-position assumptions.The regret bound is stated as O(poly(d)) in the supplied passage.Source: §3.1 · pp. 11–12
• Generic convex sets may lack any finite vertex or half-space representation, creating a real obstacle to optimizing over their linear endomorphisms.This separates the tractable succinct-polytope cases from the general oracle-access setting.Source: §3.1 · pp. 11–12

3.2 Hardness of Optimization over Linear Endomorphisms

• With only a membership oracle for a generic convex set P, constructing membership, separation, or optimization oracles for its endomorphisms is computationally intractable.The hardness applies even to deciding weak forms of membership.Source: §3 · p. 11, §3.2 · p. 12
• Any algorithm satisfying the theorem's membership guarantee must make at least exp(Ω(d)) queries to P's membership oracle.The lower bound follows from distinguishing a unit ball from one with a randomly removed cap.Source: §3.2 · p. 12
• The hardness result implies that exact linear-swap-regret computation is generally intractable, because regret evaluation can encode optimization over the endomorphism set.Nevertheless, the paper states that linear-swap-regret minimization can still be performed efficiently with only oracle access to the strategy sets.Source: §3.2 · p. 12

4 Linear Swap Regret Minimization for General Convex Sets

• The method replaces the intractable endomorphism set with tractable shell approximations that contain Φ(P) and yield transformations with fixed points in P after projection.The shell is refined using separating hyperplanes whenever a fixed-point-free transformation is encountered.Source: §4 · p. 13

4.1 A Semi-Separation Oracle for the Set of Endomorphisms

• A semi-separation oracle either finds a fixed point of a queried transformation in P or returns a hyperplane separating it from the endomorphism set Φ(P).It runs in polynomial time with polynomially many oracle queries to P.Source: §4.1 · p. 14

4.2 The Shell Ellipsoid Algorithm

• ShellEllipsoid either returns a transformation in F with a fixed point in P or constructs a polynomial-size polytope containing Φ(P) whose intersection with F has volume below ϵ.Its running time and number of returned half-spaces are polynomial in d, log ϵ^-1, and log D.Source: §4.2 · pp. 14–15

4.3 Shell Gradient Descent and Shell Projection

• Shell Gradient Descent handles changing shell sets while preserving low regret relative to actions in their common intersection, including every endomorphism in Φ(P).Shell Projection expands a neighborhood around the target transformation and uses ShellEllipsoid to construct a compatible shell.Source: §4.3 · pp. 16–17

4.4 Minimizing Linear Swap Regret

• O(d^4√T) linear swap regret is achieved with polynomial time per iteration using only oracle access to an isotropic convex strategy set.The final algorithm combines shell gradient descent and Shell Projection while maintaining fixed points in the strategy set.Source: §4.4 · pp. 19–20

5 Polynomial-Time Computation of Linear Correlated Equilibria

• An oracle-polynomial algorithm computes high-precision approximate linear correlated equilibria in general convex games.The runtime is polynomial in the game size, log(1/ϵ), and strategy-set conditioning parameters under the stated utility and oracle assumptions.Source: §5 · p. 21, §5.2 · pp. 24, 26, 27

5.2 Computing a Linear Correlated Equilibrium in General Convex Games

• The Correlator–Deviator zero-sum bilinear game converts a min-max solution into an approximate linear correlated equilibrium.The Correlator’s utility equals the sum of players’ expected linear swap regrets, while the joint distribution is recovered from the correlated strategy profile.Source: §5 · p. 21, §5.2 · pp. 25–26

5.1 Generalizing the Ellipsoid Against Hope Framework to General Convex Sets

• The generalized Ellipsoid Against Hope framework handles arbitrary compact convex sets and semi-separation access to the dual strategy set.It uses a convex shell containing the inaccessible set, separating-shell constraints, and good-enough responses to obtain an approximate guarantee.Source: §5 · p. 21, §5.1 · p. 22
• The framework produces a sparse convex combination of good-enough responses that satisfies the required approximate bilinear guarantee.The resulting solution is explicit as a mixture of polynomially many responses, with oracle-polynomial complexity in the lower-dimensional side.Source: §5.1 · pp. 22–24

5.2 Computing a Linear Correlated Equilibrium in General Convex Games

• The computation assumes well-bounded strategy sets, bounded utilities, efficient strategy-set oracles, and the polynomial utility gradient property.The polynomial utility gradient property enables counterfactual payoff computation for product distributions.Source: §5.2 · pp. 24–26
• The construction uses semi-separation by checking fixed points of each affine deviation and either separating invalid transformations or forming a product good-enough response.This avoids direct oracle access to the Deviator’s strategy set.Source: §5.2 · pp. 26–27

A Sufficiency of Regret Minimization in Isotropic Position

• Affine isotropic transformations transfer linear-swap regret minimizers back to the original strategy set with regret scaled by 2R.This supplies the appendix’s reduction from isotropic-position regret minimization to general well-bounded convex strategy sets.Source: A Sufficiency of Regret Minimization… · p. 31

B Properties of Sets of Linear Transformations

• Affine transformations mapping a larger input set into a smaller output set also map any contained input set into any containing output set.Formally, Lin(A, B) ⊆ Lin(C, D) when A ⊇ C and B ⊆ D.Source: B Properties of Sets of Linear… · p. 31
• For a well-bounded strategy set, its affine endomorphisms contain a ball centered at the constant map to an interior point.If Bd(a, r) ⊆ P ⊆ Bd(0, R), then the transformation set contains a ball around ϕa with radius r/(2R).Source: B Properties of Sets of Linear… · p. 32
• Affine maps between bounded balls have bounded linear and translation components.The linear component has spectral norm at most 2R, while the translation component is bounded using R and r.Source: B Properties of Sets of Linear… · p. 32
• The section also constructs approximate identity transformations whose displacement is controlled by the strategy set’s conditioning and approximation parameter.These maps send expanded strategy sets into contracted ones while remaining close to the identity.Source: B Properties of Sets of Linear… · p. 33

C.1 Definitions and Basic Results

• Weak oracle access relaxes membership, separation, and optimization so algorithms can operate on general convex sets with precision slack.The framework uses inner and outer perturbations of convex sets and oracle-polynomial complexity.Source: §C.1 · pp. 34–35
• Weak membership and separation are connected through oracle-polynomial reductions under standard boundedness assumptions.Weak separation supports weak optimization over circumscribed convex sets, while weak membership can yield weak separation when suitable inner and outer balls are known.Source: §C.1 · pp. 34–35
• An (ϵ, η)-approximate linear equilibrium allows strategies in expanded sets and deviations mapping expanded sets into contracted sets.This weak notion is a relaxation of strong approximate equilibrium and is designed for weak oracle access.Source: §C.1 · p. 35

C.2 Useful Primitives for Weak Oracles

• Projection-based primitives convert weak optimization or membership information into separating hyperplanes for expanded convex sets.The projection direction separates points outside the expanded set from the original set.Source: §C.2 · pp. 35–36
• Additional geometric lemmas bound approximation errors and the volume of intersections needed in ellipsoid-style procedures.These results control transformed quadratic objectives, projection distances, and interior volume under ball intersections.Source: §C.2 · pp. 36–38

• Polynomially many membership queries cannot solve Weak Membership for Φ(P) when P is a compact convex set accessed only through membership queries.Source: D Infeasibility of Membership over… · pp. 38–39
• The passages describe a negative scaling and report accepting 4d I for P = Bd while rejecting it for a capped variant.Source: D Infeasibility of Membership over… · pp. 38–39
• For the unit ball, linear endomorphisms are characterized by operator norm at most one, including the negative scaling map and small perturbations.Source: D Infeasibility of Membership over… · pp. 38–39
• The unit ball and capped-ball instances have indistinguishable membership oracles under poly(d) queries, so a Weak Membership algorithm cannot correctly return different answers for both.Source: D Infeasibility of Membership over… · p. 39
• The capped-ball construction uses exponentially many disjoint caps, forcing any distinguishing algorithm to query points in the relevant cap.Source: D Infeasibility of Membership over… · p. 39

• An oracle-polynomial algorithm either returns an ε-approximate fixed point in P+ε or certifies that every point in P−ε has squared displacement greater than ε/2.Source: §E.1 · p. 39
• The weak semi-separation oracle combines this fixed-point procedure with a weak separating hyperplane for the relaxed affine endomorphism set Φ(P, ε).Source: §E.1 · p. 40
• When no approximate fixed point is found, minimizing the squared displacement over P−ε yields a separating direction for the affine image (A−I)P−ε+x0.Source: §E.1 · p. 40
• A convex optimization step over P then supplies the remaining separation information needed to construct a valid ε-weak separating hyperplane.Source: §E.1 · pp. 40–41

• ShellEllipsoid runs in oracle-polynomial time using weak separation access to P and returns either an affine transformation with an ε-approximate fixed point or a separating frontier.Source: §E.2 · p. 41
• The procedure treats transformations with approximate fixed points outside the relaxed endomorphism set as false positives and returns them when encountered.Source: §E.2 · pp. 41–42
• If the intersection F∩Φ(P, ε) has sufficient volume, the method finds a transformation in F+ε with an approximate fixed point inside P.Source: §E.2 · pp. 41–42
• If that intersection has insufficient volume, the method accumulates halfspaces into a compact convex frontier Q containing Φ(P, ε)−ε while leaving little volume in Q∩F−ε.Source: §E.2 · pp. 41–42

Shell Gradient Descent

• Weak Shell Gradient Descent applies to arbitrary nested shell sets containing X and provides the theorem's regret guarantee for nonincreasing step sizes.Source: §E.3 · p. 43

Oracle assumptions

• The weak-oracle algorithms assume well-bounded strategy sets and a compact transformation set containing Φ(P).Source: §E.3 · p. 44

Weak Shell Projection

• Weak Shell Projection returns a shell containing Φ(P, η)−ε and a nearby affine transformation with a min(ε, η)-approximate fixed point.Source: §E.3 · p. 44
• The projection procedure maintains containment of the relaxed endomorphism set while expanding shells around the queried transformation and invoking ShellEllipsoid.Source: §E.3 · pp. 44–45
• Its search invariants ensure that candidate transformations near the shell boundary are sufficiently separated while a consistent approximate-fixed-point transformation remains available.Source: §E.3 · p. 45
• The resulting transformation is valid within the prescribed shell and retains an ε′-approximate fixed point under the stated precision relation.Source: §E.3 · p. 45

E.4 Minimizing Linear Swap Regret with Weak Oracles

• Algorithm 9 outputs strategies in P+η with the stated regret guarantee under weak oracle access and has oracle-polynomial per-iteration complexity.The result assumes a compact convex strategy set in isotropic position and loss vectors in [-1,1]^d.Source: §E.4 · p. 46
• The proof bounds the transformation-set diameter and gradient norms using D ≤ 8d^2 and G ≤ 2d^3/2.These bounds feed into the final linear-swap-regret guarantee.Source: §E.4 · p. 47
• ShellProj handles the restricted deviation set by producing an enclosing set and an approximate projected update for linear-swap regret minimization.The construction uses the inclusion Φ(P,η)-ϵ ⊂ ˜Φ ⊂ M and controls projection error by ϵ.Source: §E.4 · p. 47

F Computing a Linear Correlated Equilibrium with Weak Oracles

• The weak-oracle section extends the approach from regret minimization to computing a high-precision linear correlated equilibrium in polynomial time.This is presented as the weak-oracle counterpart of the main equilibrium-computation results.Source: F Computing a Linear Correlated… · p. 48

F.1 The Ellipsoid Against Hope framework with Weak Oracles

• Algorithm 10 computes an exact solution to the stated bilinear convex optimization problem and represents it as a mixture of polynomially many GER responses.The framework assumes compact convex sets, weak oracle access, and polynomially bounded response encoding lengths.Source: §F.1 · pp. 48–49
• Ellipsoid iterations first establish near-infeasibility of the dual and then use minimax reasoning to obtain a weakly feasible primal solution.The construction also provides an interior-radius certificate needed for ellipsoid computation.Source: §F.1 · pp. 49–50
• The method constructs weak separation for the primal feasible region by checking simplex feasibility and optimizing over an oracle-defined response set.A violating approximate optimizer yields a weak separating hyperplane; otherwise the candidate is certified feasible.Source: §F.1 · pp. 50–51
• Projecting the weak solution onto the simplex yields x* = Xλ̂* in X and establishes an ϵ-approximate solution to the original problem.The final feasibility argument compares λ* with the closest feasible point in K2.Source: §F.1 · pp. 51–52

F.2 Computing an Equilibrium in Convex Games with Weak Oracles

• Theorem F.3 gives an oracle-polynomial algorithm for an (ϵ,η)-approximate linear correlated equilibrium in well-bounded convex games with weak separation oracles.The guarantee assumes polynomial utility gradients and bounded utilities.Source: §F.2 · p. 52
• The resulting optimal solution satisfies the individual deviation inequalities and therefore defines an (ϵ,η)-approximate linear correlated equilibrium.The proof tests the bilinear constraints on deviations for individual players and uses approximate identities.Source: §F.2 · p. 53
• The construction enlarges the deviation set to a full-dimensional, well-bounded set so the weak Ellipsoid Against Hope theorem applies despite the original domain's dimensionality issue.An inflation parameter γ is used in Y′ = [1−γ,1+γ] × Φ(P1,δ) × ··· × Φ(Pn,δ).Source: §F.2 · pp. 52–53
• For each candidate deviation, the oracle either returns a weak separating hyperplane or constructs a good-enough response from approximate fixed points.The latter response is computed in oracle-polynomial time using the players' gradient information.Source: §F.2 · pp. 53–54
• The computed equilibrium is represented as a mixture of polynomially many product distributions over strategy profiles.This sparse representation follows from the Ellipsoid Against Hope construction.Source: §F.2 · pp. 53–54