CS Paper Radar

From Scalar Games to Unconstrained Network Zero-Sum Games: Transfer Principles for Gradient-Based Learning

Gaoqi Xue, James P. Bailey

cs.GT ·submitted 2026-10-30 17:37 UTC · v1

Abstract

We show that, for a broad class of gradient-based learning rules, scalar zero-sum games form a complete test family for convergence in unconstrained network zero-sum games. Specifically, suppose a learning rule achieves last-iterate or time-average convergence on every scalar game of magnitude $a$ whenever $η\leq f(a)$, where $f$ is nonincreasing. Then the same guarantee holds on an arbitrary network zero-sum game with stacked game operator $\mathbf{G}$ whenever $η\leq f(\lVert\mathbf{G}\rVert_2)$. More generally, finite-time rate guarantees transfer mode by mode: the network response is bounded by the largest response of its scalar canonical games, and under compatible linear initialization conventions the worst-case finite-time network response is exactly the largest scalar canonical rate. Thus, understanding the learning dynamics on scalar games is sufficient to characterize universal convergence and worst-case rates over the corresponding class of network games. The result follows from the classical planar decomposition of real skew-symmetric game operators. Related mode-wise reasoning has appeared implicitly in spectral analyses of particular learning algorithms and in prior work using these decompositions for game representation and visualization; here we isolate the resulting transfer principle for gradient-based learning. We discuss implications for simplifying convergence analysis, time-average guarantees, low-dimensional geometric arguments, accelerated-method design, and worst-case numerical testing.

Closest papers

Nearest neighbours by meaning across the whole index.

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

$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.67
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

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

Regret, equilibrium, and learning in games: A guided tour

cs.GT cs.LGmath.OC ·2026-08-10 ·Panayotis Mertikopoulos
publishedtheory similarity 0.66
Abstract · 44 pages, 3 figures; to appear as a chapter in "Equilibria in Games: Existence, Selection, and Dynamics", edited by Sylvain Sorin and Bernha…

This note aims to serve as an entry point to the literature on learning in games, a topic with significant theoretical appeal and a wide range of applications -- from machine learning and data science to economics and beyond. Our presentation is structured around two complementary viewpoints: We first consider a single agent -- the learner -- engaged in a sequential decision process in an unknown, non-stationary, and possibly adversarial environment. We then examine what happens when the environment is shaped by the decisions of several interacting agents, not necessarily aware of each other's actions or goals, and all seeking to improve their individual rewards. In this general context, we examine a family of regularized learning policies based on best-responding to the past history of play, up to a regularization penalty intended to encourage exploration and prevent over-commitment to suboptimal choices. In the single-agent setting, we present some basic regret bounds for regularized learning in adversarial multi-armed bandits; in the multi-agent setting, we describe an ergodic equilibrium convergence result for zero-sum games in the spirit of classical results on fictitious play, as well as a "folk theorem" linking strategic and dynamic notions of stability -- Nash equilibria and attracting points of regularized learning, respectively. We pay special attention to the information available to the players and, through a unified analysis framework, we study both oracle- and payoff-based (bandit) methods. Our goal is to provide a coherent and comprehensible -- albeit, by necessity, not comprehensive -- account of some recent ideas in the field, and to discuss their implications for the study of rationality.

0.25

On the Convergence of First-Order Methods in Signaling Games

cs.GT ·2026-11-07 ·Rilind Sahitaj, Artem Tsikiridis, Martin Bichler
top venue similarity 0.66
Abstract · Accepted at NeurIPS 2026

We study first-order learning dynamics in Bayesian signaling games, a minimal extensive-form model of strategic interaction under asymmetric information. In these games, a Sender observes a private type and chooses a signal, after which a Receiver forms a posterior belief and selects an action. This Bayesian belief update makes the induced learning field fundamentally different from the affine game-gradient fields of normal-form games. Empirically, we find a sharp dichotomy: standard online learning algorithms reliably converge to strict Perfect Bayesian Equilibria (PE), but not to non-strict ones. We show that this behavior cannot be explained by the global geometric conditions commonly used to prove last-iterate convergence, such as monotonicity or the Minty variational inequality. Indeed, these conditions can fail even in binary signaling games. Instead, we identify the relevant local geometry. Our main result characterizes variational stability in finite signaling games: a PE is variationally stable if and only if it is strict. This yields local last-iterate convergence guarantees for online mirror descent and regularized dual averaging near every strict PE. We then study global average-iterate convergence and identify a class of signaling games in which coarse-trigger regret-minimizing dynamics converge to the unique PE. Finally, we complement the theory with experiments comparing projected gradient ascent, mirror-based methods, optimistic variants, and PPO across canonical signaling-game families. The results position signaling games as a compact testbed for understanding how Bayesian belief formation reshapes the convergence geometry of multi-agent learning.

0.35

Optimal Alternating Regret for Online Learning and Games

cs.LG cs.GTstat.ML ·2026-08-25 ·Yixin Tao, Weiqiang Zheng
theoryhighly cited similarity 0.66
Abstract · 21 pages

We settle the minimax-optimal alternating regret, a regret notion motivated by alternating learning dynamics in games, for both online linear optimization (OLO) and online convex optimization (OCO). For OLO over the probability simplex $Δ_d$, we give an algorithm with $O(\log d)$ alternating regret that remains a constant for any time horizon $T$, and a matching lower bound. Our constant regret bound significantly improves previous results with $O(\log ^{2/3}d \cdot T^{1/3})$ regret [Cevher, Cutkosky, Kavis, Piliouras, Skoulakis, Viano, NeurIPS 2023, Hait, Li, Luo, Zhang, COLT 2025]. As a result, we obtain alternating learning dynamics with $O(\log d /T)$ convergence to Nash equilibria in two-player zero-sum games and $O(\log d /T)$ convergence to coarse correlated equilibria in two-player general-sum games. This is the first uncoupled learning dynamics with $O(1/T)$ convergence to CCE in two-player general-sum games, while all prior works suffer additional $\log T$ factors. For general OCO over a $d$-dimensional compact convex set, we give an algorithm with $O(d\log (1+T/d))$ alternating regret, improving the previous best of $\widetilde{O}(d^{2/3}T^{1/3})$. We also prove a matching lower bound of $Ω(d\log (1+T/d))$, showing that the $Ω(\log T)$ factor is unavoidable.

0.32

Fictitious Play When Agents Are Not Expected-Utility Maximizers: A Geometric Analysis in $2$-Action Games

cs.GT eess.SYmath.OC ·2026-11-12 ·Hao Liang, Solaleh Mohammadi, Kaiqing Zhang
similarity 0.65
Abstract

Fictitious play (FP) is one of the earliest and most fundamental learning procedures in games, where each agent independently chooses a best response to the empirical distribution of opponents' past actions by maximizing the expected payoff with respect to it. However, learning agents may not always be expected-utility maximizers: they may use nonlinear evaluation functionals to account for the uncertainty induced by the opponents, e.g., via risk measures. In this work, we study nonlinear fictitious play (NL-FP), in which each pure action is evaluated by a general, possibly nonlinear functional of the payoff distribution induced by the opponent's empirical belief. To analyze NL-FP, we first identify a single-crossing property (SCP) of evaluation functionals that preserves the classical geometry of FP in $2\times2$ games. Furthermore, we conduct a novel geometric analysis of the convergence behavior of NL-FP in $2\times2$ games, even when the SCP fails. Beyond $2\times2$ games, we show that the convergence of NL-FP in $2\times n$ ($n\ge3$) games may fail even for continuous-time NL-FP, when the two-action player uses conditional value-at-risk (CVaR) in a $2\times3$ game. In addition, we identify a finite-crossing condition that ensures convergence of the selected continuous-time dynamics and the discrete-time iterates in general $2\times n$ games, which also provides new insights into the global landscape of continuous-time classical FP in such games.

0.13

The Complexity of Strategizing Against No-Regret Learners: Pure When It Is Easy, Hard Even When Mixed

cs.GT ·2026-10-26 ·Yiheng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis
benchmark similarity 0.65
Abstract

We study the computational complexity of clairvoyant strategy optimization against a known online learner in finite-horizon repeated games. In general-sum games with bounded payoffs, unless $\mathsf{P}=\mathsf{NP}$, no polynomial-time optimizer can achieve a reward within $cT$ of the reward of the optimal pure-action sequence for an absolute constant $c>0$, even when allowed to output explicitly represented mixed strategies at every round. Our hardness result strengthens prior work along two complementary axes: it extends to a broader class of learning dynamics, including widely used mean-based algorithms, answering an open question of Assos, Dagan, and Rajaraman (2025) for learners beyond multiplicative weights; and it permits mixed outputs while retaining the weaker pure-sequence benchmark. Thus, neither mixed strategies nor algorithmic specificity removes the computational obstruction in general-sum games. In sharp contrast, zero-sum games exhibit the reverse phenomenon: deterministic pure actions suffice for efficiently recovering the leading surplus guarantees previously obtained through mixed play against Follow-the-Regularized-Leader (FTRL) opponents. Thus, the two regimes form a striking mirror image: mixed play cannot overcome general-sum hardness even against a pure benchmark, whereas pure play retains the full surplus guarantees of mixed strategies in zero-sum games.

0.13