Optimal Coarse Correlated Equilibria in Mean Field Games: Linear Programming and No-Regret Learning

• URL: http://arxiv.org/abs/2606.20062v1
• Date: Thu, 18 Jun 2026 10:35:01 GMT
• Title: Optimal Coarse Correlated Equilibria in Mean Field Games: Linear Programming and No-Regret Learning
• Abstract summary: We introduce optimal coarse correlated equilibria for continuous-time mean field games.<n>A coarse correlated equilibrium is a randomized recommendation scheme from which no player can gain.<n>We design a no-regret primal-dual algorithm, based on an equivalent Lagrangian formulation of the external-regret constraint, for learning such equilibria.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce optimal coarse correlated equilibria for continuous-time mean field games. A coarse correlated equilibrium is a randomized recommendation scheme from which no player can gain by ignoring the recommendation and switching to an alternative strategy. The problem is as follows: a moderator selects, among all mean-field coarse correlated equilibria, one that optimizes a prescribed performance criterion, which may differ from the representative player's objective. After formulating the problem, we develop a linear programming (LP) formulation, prove the existence of optimal LP coarse correlated equilibria, and relate the LP characterization to the original probabilistic setting. Building on this characterization, we design a no-regret primal-dual algorithm, based on an equivalent Lagrangian formulation of the external-regret constraint, for learning such equilibria. We provide explicit convergence rates for the learning algorithm, and numerical examples illustrate the method.

Related papers

• N(CO)$^2$: Neural Combinatorial Optimization with Chance Constraints to Solve Stochastic Orienteering [7.0274229967026045]
  We present N(CO)$2$: Neural Combinatorial Optimization with Chance cOnstraints to solve the Orienteering Problem (SOP) without the use of hand-crafteds.<n>The proposed approach reduces human effort while enabling adaptive and efficient decision-making in uncertain environments.
  arXiv  Detail & Related papers  (2026-06-16T22:05:51Z)
• Optimal Data Acquisition for Reinforcement Learning: A Large Deviations Perspective [5.848643785361479]
  We introduce the exponential decay rate of the policy-selection error probability as a principled efficiency metric.<n>We formalize two complementary notions of optimality in terms of the optimal solution of the nested problem.<n>We prove that the resulting reinforcement learning algorithm is near-robustly optimal under our optimality criterion, up to a constant factor.
  arXiv  Detail & Related papers  (2026-05-27T16:08:56Z)
• Not All Preferences Are Created Equal: Stability-Aware and Gradient-Efficient Alignment for Reasoning Models [52.48582333951919]
  We propose a dynamic framework designed to enhance alignment reliability by maximizing the Signal-to-Noise Ratio of policy updates.<n>SAGE (Stability-Aware Gradient Efficiency) integrates a coarse-grained curriculum mechanism that refreshes candidate pools based on model competence.<n> Experiments on multiple mathematical reasoning benchmarks demonstrate that SAGE significantly accelerates convergence and outperforms static baselines.
  arXiv  Detail & Related papers  (2026-02-01T12:56:10Z)
• Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games [60.981847057352695]
  We introduce proximal regret, a new notion of regret based on proximal operators that lies strictly between external and swap regret.<n>We show that the classic Online Gradient Descent algorithm achieves an optimal $O(sqrtT)$ bound on proximal regret.<n>This provides a new explanation for the empirically superior performance of gradient descent in online learning and games.
  arXiv  Detail & Related papers  (2025-11-03T18:57:49Z)
• Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [53.03951222945921]
  We analyze smoothed (perturbed) policies, adding controlled random perturbations to the direction used by the linear oracle.<n>Our main contribution is a generalization bound that decomposes the excess risk into perturbation bias, statistical estimation error, and optimization error.<n>We illustrate the scope of the results on applications such as vehicle scheduling, highlighting how smoothing enables both tractable training and controlled generalization.
  arXiv  Detail & Related papers  (2024-07-24T12:00:30Z)
• An Inexact Halpern Iteration with Application to Distributionally Robust Optimization [8.722877733571796]
  We show that by choosing the inexactness appropriately, the inexact schemes admit an $O(k-1) convergence rate in terms of the (expected) residue norm.<n>We demonstrate how the proposed methods can be applied for solving two classes of data-driven distributionally robust optimization problems.
  arXiv  Detail & Related papers  (2024-02-08T20:12:47Z)
• Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Games [44.95137108337898]
  We provide an uncoupled policy optimization algorithm that attains a near-optimal $tildeO(T-1)$ convergence rate for computing a correlated equilibrium. Our algorithm is constructed by combining two main elements (i.e. smooth value updates and (ii. the optimistic-follow-the-regularized-leader algorithm with the log barrier regularizer)
  arXiv  Detail & Related papers  (2024-01-26T23:13:47Z)
• Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
  We revisit the likelihood-based inference principle and propose to use likelihood ratios to construct valid confidence sequences. Our method is especially suitable for problems with well-specified likelihoods. We show how to provably choose the best sequence of estimators and shed light on connections to online convex optimization.
  arXiv  Detail & Related papers  (2023-11-08T00:10:21Z)
• Offline Learning in Markov Games with General Function Approximation [22.2472618685325]
  We study offline multi-agent reinforcement learning (RL) in Markov games. We provide the first framework for sample-efficient offline learning in Markov games.
  arXiv  Detail & Related papers  (2023-02-06T05:22:27Z)
• Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
  In this paper, we develop a simple yet efficient approach for the problem of comparing uncertain quantities. We recast inner optimization in the Lagrangian as a learning problem for surrogate approximation, which bypasses apparent intractability. The proposed light-SD demonstrates superior performance on several representative problems ranging from finance to supply chain management.
  arXiv  Detail & Related papers  (2022-11-14T21:54:31Z)
• Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation [78.48747645545944]
  We study the problem of finding optimal correlated equilibria of various sorts in extensive-form games. We introduce a new algorithm for computing optimal equilibria in all three notions.
  arXiv  Detail & Related papers  (2022-03-14T15:21:18Z)
• Invariant Risk Minimization Games [48.00018458720443]
  In this work, we pose such invariant risk minimization as finding the Nash equilibrium of an ensemble game among several environments. By doing so, we develop a simple training algorithm that uses best response dynamics and equilibria in our experiments, yields similar or better empirical accuracy with much lower variance than the challenging bi-level optimization problem of Arjovsky et al.
  arXiv  Detail & Related papers  (2020-02-11T21:25:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.