CS Paper Radar

Distributed Learning of $α$-Potential Functions in Strategic Multi-agent Systems

Yifei Chen, Chinmay Maheshwari

cs.MA cs.GTeess.SYmath.OC ·submitted 2026-10-04 20:33 UTC · v2

Abstract

We study the problem of computing the tightest \(α\)-potential approximation of a general-sum game over continuous action spaces, within a prescribed class of potential functions and when each player has access only to its own utility function. The difficulty is twofold: the approximation error involves a worst-case search over an infinite set of unilateral deviations, and the required utility information is distributed across players. For a linear-in-parameters potential class, we use an exact finite-tuple reformulation that separates the problem into a global outer search over deviation tuples and distributed convex inner problems. We develop a primal--dual inner oracle tailored to this structure and establish a uniform one-sided accuracy guarantee. This oracle can be combined with global outer search to obtain an end-to-end guarantee on the outer optimization error. We also develop a projected zeroth-order outer method as a computationally lighter alternative for higher-dimensional problems. Numerical experiments illustrate the accuracy--computation tradeoff between the two outer-search methods and show that the proposed optimization framework can improve upon analytical \(α\)-potential constructions.

Comment
15 pages, 4 figures

Closest papers

Nearest neighbours by meaning across the whole index.

$Q$ Can Play That Game: Online Fitted $Q$-Iteration for Continuous-Action Zero-Sum Markov Games with Convex-Concave Function Approximation

cs.GT cs.MA ·2026-10-02 ·Kushagra Gupta, Jingqi Li, Cade Armstrong, Lasse Peters, Ross E. Allen +2 more
code/data similarity 0.68
Abstract

Zero-sum Markov games arise in a wide variety of sequential decision-making problems such as adversarial learning and planning against modeled uncertainties. However, prior work on finite-sample guarantees on the learned state-action value function ($Q$-function) for zero-sum Markov games is largely restricted to finite-action settings, or to continuous-action games in which agents have linear dynamics and quadratic rewards (i.e. linear-quadratic, or LQ, games). A central challenge in extending such guarantees to more general continuous-action zero-sum Markov games is that the associated Bellman operator involves a minimax problem that need not admit a tractable saddle-point solution. To this end, we first introduce a class of neural network function approximators for the $Q$-function that is convex-concave in the players' actions, which guarantees that this minimax problem admits a pure-strategy saddle point. We then study an online variant of fitted $Q$-iteration employing this function class and establish, to the best of our knowledge, the first finite-sample guarantees for non-LQ zero-sum Markov games with continuous states and actions. Our code can be found at https://github.com/CLeARoboticsLab/QCanPlayThatGame.

0.33

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.66
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

Optimal Competitive Ratios for Chasing Convex Functions with Quadratic Growth

cs.LG ·2026-11-05 ·Linzhe He, Sifan Yang, Wei Jiang, Lijun Zhang
theory similarity 0.65
Abstract

Chasing convex function has attracted much attention in recent years, which can be formulated as a game between a learner and an adversary. In each round, the adversary reveals a convex function, and the learner selects a decision and incurs a hitting cost and a movement cost for changing its decision. The performance of the learner is measured by the \emph{competitive ratio}, which compares its cumulative cost with that of an optimal offline decision sequence. For Euclidean movement, existing upper and lower bounds for $κ$-well-conditioned functions exhibit a polynomial gap. For squared Euclidean movement, dimension-free competitive guarantees have been established under quadratic growth, but the optimal competitive ratio remains unclear. In this paper, we establish optimal dimension-free competitive ratios for convex function chasing under two types of movement costs. For Euclidean movement, we propose Clipped Proximal Descent (CPD), which combines a balanced proximal step with a clipped correction toward the current minimizer. CPD achieves an $O(κ^{1/3})$ competitive ratio for smooth convex functions satisfying quadratic growth, improving the previous $O(\sqrtκ)$ upper bound and matching the existing $Ω(κ^{1/3})$ lower bound. For squared Euclidean movement, we establish the exact optimal dimension-free competitive ratio for convex functions satisfying quadratic growth. Our result is based on a new tight competitive analysis of Regularized Online Balanced Descent (R-OBD) and a matching lower bound against randomized algorithms.

0.20

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.63
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.63
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

Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights

cs.DS stat.MLcs.LG ·2026-09-22 ·Shinsaku Sakaue
theoryhighly cited similarity 0.62
Abstract

We study online inverse linear optimization with a fixed unknown linear utility: in each round, an environment presents a compact action set, the learner recommends an action from it, and the environment returns an action that maximizes the utility over the same set. When the utility vector and the actions lie in the $d$-dimensional Euclidean unit ball, we give a randomized algorithm whose regret---the cumulative utility shortfall relative to optimal actions---is $O(\sqrt d)$ in expectation for every time horizon, without knowledge of the horizon. The dependence on $d$ is optimal up to a constant factor by the known $Ω(\sqrt d)$ lower bound for horizons $T\ge d$. Our algorithm maintains matrix multiplicative weights on polynomial feature spaces at geometrically spaced scales. It selects a recommendation distribution by solving a linear program and updates its score matrices by comparing the available actions with the feedback action. With rational oracle outputs and feedback actions, an implementation computable relative to a linear-optimization oracle preserves the $O(\sqrt d)$ regret bound. Whether the same rate is attainable with running time polynomial in the dimension, horizon, and input length remains open.

0.41

Interactive Distributionally Robust Multi-Agent Learning with General Function Approximation

cs.LG cs.AI ·2026-09-25 ·Debamita Ghosh, George K. Atia, Yue Wang
similarity 0.62
Abstract · 62 pages, 3 figures

Model misspecification poses a fundamental challenge in multi-agent reinforcement learning, where transition uncertainty can be amplified by strategic interactions among agents. Distributionally robust Markov games (DRMGs) provide a principled framework for addressing such uncertainty, yet existing methods often rely on restrictive assumptions or scale poorly to large state and joint action spaces. We study online learning in general-sum DRMGs with general function approximation and $φ$-divergence uncertainty sets. We propose RoMEX-$φ$, a model-free framework that integrates equilibrium-based exploration with dual fitted learning. Through a functional dual representation of the robust multi-agent Bellman operator, RoMEX-$φ$ enables tractable worst-case value estimation from nominal interaction data using a centered empirical robust discrepancy. We introduce the robust Multi-Agent Decoupling Coefficient (robust MADC) to characterize the intrinsic exploration complexity arising from strategic interactions and adversarial transition uncertainty. We establish sublinear robust regret guarantees governed by the robust MADC rather than explicitly by the state and joint action space sizes, replacing tabular dependence with intrinsic function-class complexity. Numerical experiments on a scalable general-sum DRMG under total variation uncertainty show that RoMEX-$φ$ is substantially more resilient to transition shifts than its non-robust counterpart while remaining competitive with an exact tabular robust baseline. Our results provide a scalable framework for distributionally robust multi-agent reinforcement learning with general function approximation.

0.28

Toward Online Robust Zero-Sum Markov Games with Function Approximation

cs.LG cs.AI ·2026-10-19 ·Chenhao Zhou, Jiyu Wei
top venuetheory similarity 0.62
Abstract · Accepted at NeurIPS 2026. 70 pages, including appendices

Online robust zero-sum Markov games pose a coupled operator-learning and game-solving problem: from nominal interaction data, the learner must recover a worst-case minimax Bellman operator while maintaining strategic coverage and controlling stage-game approximation error. Existing robust reinforcement-learning theory does not yet provide such an operator-learning perspective beyond specialized multi-agent settings. We develop an optimistic dual robust Bellman framework that combines dual robust Bellman fitting, optimistic minimax planning, backward-validated confidence sets, and exploiter-mix data collection. Our analysis is organized around the robust Bellman residuals induced by the candidate value class and yields a regret reduction that separates exploration complexity, robust operator-estimation error, stage-game solution error, and misspecification. Under explicit interpretable assumptions, we obtain conditional theorem interfaces for general and projected function approximation, together with closed results in several structured regimes, including tabular, epochwise cross-fit linear, self-normalized pure-online linear / finite-rank kernel, and projected RKHS truncation. Small-scale numerical experiments illustrate robustness calibration, strategic coverage, and the return-gap trade-off predicted by the framework.

0.52