CS Paper Radar

Gradient-extrapolation-based distributed mirror descent algorithm for multi-cluster aggregative games

Rui Zhu, Fuyong Wang, Zhongxin Liu, Zengqiang Chen

cs.GT math.OC ·submitted 2026-08-25 07:49 UTC · v1

Abstract

This paper studies a class of multi-cluster aggregative games characterized by the coexistence of cooperation and competition, where each agent's cost function depends on its own strategy and the aggregate of all agents' strategies. To address the Nash equilibrium seeking problem for such games in the non-Euclidean setting, a distributed mirror descent algorithm with gradient extrapolation is proposed over time-varying intra-cluster and inter-cluster networks. The mirror descent framework employs a general Bregman divergence as the distance measure, providing greater flexibility than Euclidean-based methods, while gradient extrapolation exploits historical gradient information to improve convergence performance. Under the restricted strong monotonicity characterized by the Bregman divergence, the convergence of the proposed algorithm is established, and it achieves the $\mathcal{O}(1/k)$ convergence rate with the appropriately selected step-size and parameters. Finally, the effectiveness of the proposed algorithm is verified by an example on the demand response of energy systems.

Closest papers

Nearest neighbours by meaning across the whole index.

Distributed Nash Equilibrium Seeking for Open Multi-Coalition Games: A Mass-Preserving Gradient-Tracking-Based Algorithm

eess.SY ·2026-10-06 ·Daning Lei, Jiamin Wang, Jian Liu, Feng Xiao, Yuanshi Zheng
similarity 0.68
Abstract · 13 pages, 5 figures

This paper studies distributed information aggregation and Nash equilibrium seeking over open multi-coalition networks, where both agents and coalitions may dynamically enter and leave the network. The varying network population poses a fundamental challenge to conventional gradient-tracking methods, as agent departures may cause the loss of gradient information required for distributed aggregation. To overcome this issue, a mass-preserving gradient-tracking method is designed, in which the gradient information carried by departing agents is redistributed to the remaining agents within the same coalition. The proposed method preserves the aggregate gradient information of the coalition objective over the intra-coalition communication network and achieves gradient tracking under dynamic population changes without imposing additional initialization conditions beyond those of conventional gradient-tracking methods. Based on the proposed gradient-tracking mechanism, a distributed Nash equilibrium seeking framework is developed, and its convergence is established under both uncoordinated fixed and diminishing stepsizes. Furthermore, to alleviate the slowdown of convergence caused by classical diminishing stepsize schemes ($\frac{η_0}{t}$, where $η_0>0$ is a constant), an exponential-interval diminishing stepsize scheme is designed based on the agents' exploration intervals. Finally, a numerical simulation based on an open connecting control game demonstrate the effectiveness of the proposed information-tracking and Nash equilibrium seeking framework.

0.35

Optimization Frameworks & Learning Algorithms for Discrete-Time Mean Field Games

cs.LG math.OC ·2026-11-01 ·Xin Guo, Mathieu Laurière
similarity 0.61
Abstract

This monograph introduces discrete-time mean field games with finite state and action spaces, emphasizing optimization formulations and learning algorithms. Starting from Markov decision processes and finite-player stochastic games, it develops the notion of mean field Nash equilibrium, establishes existence and uniqueness results under suitable assumptions, and explains how mean field equilibria yield approximate equilibria in large finite-player games. Building on the linear programming formulation of Markov decision processes, occupation measures and primal-dual formulations connect equilibrium computation with mathematical optimization. The monograph presents fixed-point iterations, fictitious play, online mirror descent, and optimization-based methods, discussing their convergence properties and limitations. Numerical examples illustrate crowd motion, traffic routing, epidemic management, and the computation of multiple equilibria. It combines examples, theoretical results, and implementable algorithms, with bibliographic notes providing connections to the broader literature.

0.22

Learning Global Equilibria in Non-Concave Prospect Theoretic Games

cs.GT ·2026-11-09 ·Ashok Krishnan K. S., Lilou Malfoy, Helene Le Cadre, Ana Busic
similarity 0.61
Abstract

Human agents in non cooperative games often exhibit non rational behaviour. Prospect theory provides a behavioural framework to capture how agents perceive gains and losses under risk, but, its incorporation into games typically leads to non concave and non convex utility functions, making equilibrium computation challenging. In such cases, it is difficult to obtain algorithms that have global convergence behaviour. This paper proposes a learning algorithm which uses minorization-maximization (MM). Under a proximal Polyak-Lojasiewicz (PL) condition on the potential function, we establish global convergence of the algorithm to a potential-maximizing Nash equilibrium. We further show how the structure of the MM minorizer can be used to enable a distributed implementation of the algorithm. With additional noise injection, the individual updates of the agents can be obscured, while still ensuring global convergence.

0.24

Learning monotone game-theoretic linear MPC

eess.SY math.OC ·2026-11-12 ·Alberto Bemporad, Tatiana Tatarenko
similarity 0.60
Abstract · 15 pages, 1 figure

We propose a method to learn a game-theoretic model predictive control (GT-MPC) law by imitation from input and output data of a running multi-agent system. By interpreting the recorded inputs as the first moves of the equilibria of a game played by the agents, we learn the GT-MPC weights under hard input constraints and soft output constraints, without requiring the agents to reveal their objectives. We also impose that the resulting generalized Nash equilibrium (GNE) problem is strongly monotone, which ensures the existence and uniqueness of the equilibrium and, hence, that the learned GT-MPC law is well defined and can be evaluated efficiently online by variational GNE-seeking algorithms for linear-quadratic games. Moreover, strong monotonicity implies that the equilibrium is almost everywhere differentiable with respect to the references and the weights, which enables automatic differentiation for gradient-based optimization. In addition, we promote closed-loop stability of the unconstrained equilibrium feedback by incorporating a penalty that involves a jointly learned quadratic Lyapunov function. Learning a GT-MPC formulation enables us to explain the agents' objectives, reproduce their behavior in simulation in new scenarios, optimize their set-points, design mechanisms, and enforce additional constraints. A numerical example illustrates the approach.

0.27

Finite-Sample Convergence in Networked Average Reward MARL: Decentralization Pitfalls and Entropy Remedies

cs.LG cs.MA ·2026-11-02 ·Yizhou Zhang, Yashaswini Murthy, Laixi Shi, Adam Wierman
similarity 0.59
Abstract

We study the problem of average reward Multi-Agent Reinforcement Learning (MARL) where agents interact within a network. Each agent in the network conducts local updates with information within its $k$-hop neighborhood and collaboratively maximizes the overall reward of the entire network. We first provide impossibility results in achieving convergence to the global optimal joint policies in our setting. These impossibility results highlight the challenges of decentralized learning with local information in multi-agent systems, namely the issues of multiagency, where each agent independently optimizes its policy, and partial observability, where agents have limited visibility into the global state. Given these challenges which indicate that decentralized policy optimization can generally be certified only up to stationarity, we provide finite-sample convergence guarantees for a decentralized actor-critic algorithm with linear function approximation that converges to an approximate stationary point with small gradient norm. To overcome such impossibility results, we further show that adding fixed-state entropy regularization reshapes the objective landscape which leads to even stronger global convergence guarantees for our proposed actor-critic algorithm.

0.18

AltGDA Achieves Global $O(1/T)$ Ergodic Convergence in Matrix Games

cs.GT math.OC ·2026-09-26 ·Tianlong Nan, Garud Iyengar, Christian Kroer, Shuvomoy Das Gupta
similarity 0.59
Abstract

Alternating gradient descent-ascent (AltGDA) is a simple and practically effective method for solving finite two-player zero-sum matrix games. However, the theory of AltGDA remains limited: existing results either apply only to unconstrained settings or require restrictive assumptions on the equilibrium in constrained settings. We show that AltGDA converges globally at an $O(1/T)$ ergodic rate in every finite two-player zero-sum matrix game. Unlike prior results, our guarantee holds for every initialization and every horizon $T$: the uniform averages of the AltGDA iterates satisfy an $O(1/T)$ duality-gap bound. Our proof is inspired by numerical results obtained using a novel performance estimation programming (PEP) framework for Lyapunov function search over compact convex sets. Additionally, we provide simple counterexamples showing that the last-iterate duality gap of AltGDA does not converge to zero. This justifies why averaging of iterates is indeed necessary to achieve an $O(1/T)$ rate. We have formalized and machine-checked our global ergodic convergence result in Lean 4.

0.28

Algorithmic Asymmetry in Zero-Sum Games: Unilateral Recovery of Fast Convergence Against a Slow Opponent

cs.GT math.OC ·2026-08-10 ·James P. Bailey, Soham Das
similarity 0.59
Abstract

Learning dynamics in zero-sum games are typically analyzed under algorithmic symmetry: both agents use the same update rule, or methods from a common algorithmic family. This is at odds with the nature of zero-sum games; competing agents need not coordinate on algorithm selection. This paper studies algorithmic asymmetry in learning dynamics in zero-sum games. In particular, we ask whether fast convergence can be recovered when one agent is fixed to vanilla gradient descent, whose standard regret-based analysis certifies, at best, $O(1/\sqrt{T})$ ergodic convergence. We show that the slow rate is not intrinsic. When one agent uses gradient descent, the opposing agent can use a modified optimistic update, which we call Alternating Optimistic Gradient Descent (AOGD), to make the joint dynamics simulate Alternating Gradient Descent on the even iterates. As a result, the time-average of the asymmetric GD vs.\ AOGD dynamics converges to Nash equilibria at rate $O(1/T)$. Our results show that fast convergence need not require coordinated algorithm selection: one agent can compensate for a slower opponent. More broadly, the paper highlights algorithmic asymmetry as a useful lens for understanding cross-class interactions in multiagent optimization.

0.04

Independent Reinforcement Learning in Discounted Markov Games

cs.GT cs.AIcs.LGeess.SY+1 ·2026-09-01 ·Asrin Efe Yorulmaz, Ugur Aydin, Tamer Basar
similarity 0.58
Abstract · 54 pages, 3 figures

In this work, we study radically uncoupled learning in discounted general-sum Markov games. Assuming ``$\mathsf{ETH}$ for $\mathsf{PPAD}$", we show that, for every fixed discount factor, there is no polynomial-time algorithm for computing inverse-polynomially accurate coarse correlated equilibria in discounted general-sum Markov games when players learn independently in decentralized settings. Complementing this hardness result, we provide what appears to be the first \emph{radically uncoupled} algorithm with sub-exponential convergence guarantees to coarse correlated equilibria in discounted general-sum Markov games without imposing any structural restrictions on the game. Our algorithm is a \emph{layered} variant of optimistic mirror descent with an increasing step-size schedule tailored to the multi-agent setting. Finally, we develop both full-feedback and partial feedback versions of the aforementioned algorithm and establish sub-exponential convergence guarantees for each case.

0.39