Zero-Sum Games

Follow this topic Ask about this topic

Momentum

5 papers in the last four weeks, against 2 the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 35

Oct 5, 2026cs.GT

Feedback Dominance Analysis for Pursuit-Evasion Games on Graphs

This work identifies the dominance regions for discrete, simultaneous-move pursuit-evasion games on graphs. Existing geometric approaches provide efficient characterizations of winning regions, but typically provide only sufficient conditions and rely on open-loop strategies. To address these challenges, we develop a set-based dynamic programming approach to characterize the pursuer's winning and losing regions, providing necessary and sufficient winning conditions under worst-case behavior. The reachability analysis admits a set-chasing interpretation, allowing translation of dominance sets to feedback strategies that adapt to the players' positions in real time. For states where neither player can guarantee victory, we introduce an instantaneous matrix-game formulation and establish upper and lower bounds on the pursuer's winning probability. Simulation results validate the correctness of the dominance-region characterization and the proposed bounds.

Yue Guan, Daigo Shishika, Dipankar Maity +2

School of Aerospace Engineering, Georgia Institute of Technology, Atlanta, GA, USA. · College of Engineering and Computing, George Mason University, Fairfax, VA, USA. · Department of Electrical and Computer Engineering, University of North Carolina at Charlotte, Charlotte, NC, USA. +1

Game Theory Zero-Sum Games

Oct 5, 2026cs.LG

Fast Last-Iterate Convergence in Zero-Sum Markov Games with Bandit Feedback

We study last-iterate convergence in unknown two-player zero-sum discounted Markov games with bandit feedback. The players learn independently along a single trajectory without observing each other's actions. We develop Adaptive Regularized TD Learning (ARTD), which achieves a

\widetilde{\mathcal{O}}(t^{-1/4})

duality gap bound for the current policies under a uniform hitting time assumption, with high probability simultaneously over all rounds and starting states. This improves the

\widetilde{\mathcal{O}}(t^{-1/(9+ν)})

rate of Cai et al. (2023), for any fixed

ν>0

, under the same feedback model and hitting time assumption. Our algorithm requires no knowledge of the hitting time bound, the time horizon, or the confidence level. To stabilize policy learning as value estimates change, we separate fast temporal difference averaging from bounded value updates. We adapt log-barrier regularization to the progress of value estimation, controlling both policy and value errors throughout learning. Together, these mechanisms enable fast convergence of the policies actually played, even when the players learn independently from bandit feedback.

Yuheng Zhang

University of Illinois Urbana-Champaign

Last-Iterate Convergence Reinforcement Learning Zero-Sum Games Temporal-Difference Learning

Oct 4, 2026cs.LG

Pessimistic Minimax Learning for Public-Private Information Games under Unilateral Coverage

We study offline learning in two-player zero-sum contextual games with public and private information, motivated by strategic settings such as auctions and negotiations with private valuations. We introduce unilateral prescriptive concentrability and show that asymmetric information can change offline coverage through its effect on equilibrium behavior. For finite state-action spaces, we develop a pessimistic algorithm with an

\tilde{O}(1/\sqrt{n})

exploitability rate, matching the standard sample-size dependence for fully observed minimax games. We further develop a pessimistic policy mirror descent framework, PPA-PMD, for general function approximation and obtain a unified

\tilde{O}(1/\sqrt{n} + 1/\sqrt{T})

exploitability rate with no-regret actor updates. Together, these results provide the first theoretical framework for offline equilibrium learning under public-private information constraints.

Shuze Daniel Liu, Claire Chen, Jiuqi Wang +1

Massachusetts Institute of Technology · Purdue University · California Institute of Technology +1

Imperfect-Information Games Zero-Sum Games Policy Optimization Offline RL Offline MARL

Sep 30, 2026quant-ph

Average-and Last-Iterate Lower Bounds for Optimistic Matrix Mirror-Prox in Quantum Zero-Sum Games

Optimistic matrix mirror-prox (OMMP) computes

ε

-approximate Nash equilibria in quantum zero-sum games with an

O(1/\varepsilon)

average-iterate guarantee [arXiv:2311.10859]. We investigate whether this dependence on accuracy is tight and whether geometric last-iterate convergence can be guaranteed. We study these questions through explicit games with one qubit per player. First, we prove an

Ω(1/\varepsilon)

lower bound for the uniform-average output that includes the maximally mixed initial state, independently of the regularizer and step size. Second, we construct a fixed game on which optimistic gradient descent-ascent (OGDA), initialized at the maximally mixed state, has last-iterate Frobenius distance to equilibrium

Θ(1/t)

and duality gap

Θ(1/t^3)

for every sufficiently small fixed step size. A separate fixed game exhibits arbitrarily long delays in reducing the initial error by a constant factor across a family of initial states. Finally, we give a fixed game with a unique, strictly complementary equilibrium on which optimistic matrix multiplicative weights updates (OMMWU) converge only polynomially from the maximally mixed state for every fixed positive step size. The last-iterate Frobenius distance and quantum relative entropy from the equilibrium to the iterates decay as

Θ(1/t)

, while the duality gap decays as

Θ(1/t^2)

.

Yiheng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Pucheng Xiong

Department of Computer Sciences, University of Wisconsin-Madison

Last-Iterate Convergence Oracle Complexity Zero-Sum Games Mirror Descent Nash Equilibrium Computation

Sep 28, 2026cs.LG

Minimax Last-Iterate Convergence in Matrix Games with Observed Actions

We study last-iterate convergence in unknown two-player zero-sum matrix games with bandit payoff feedback and observed opponent actions. For games with

d

actions per player, we develop an algorithm achieving a duality gap of

\widetilde{\mathcal{O}}(\sqrt{d/t})

with high probability, simultaneously at every round

t

. This improves the dimension dependence of the best previously known guarantee by a factor of

d^{3/2}

. The rate matches a standard bandit lower bound, establishing minimax optimality in both the number of actions and the number of rounds, up to logarithmic factors. The algorithm is computationally efficient, requiring only

\mathcal{O}(d)

time and memory per round. Our technical contribution is a joint design of adaptive averaging and corrected exponential weights that absorbs estimation variance, together with a potential argument that bounds phase durations.

Yuheng Zhang

University of Illinois Urbana-Champaign

Last-Iterate Convergence Zero-Sum Games Adversarial Bandits Nash Equilibrium Computation

Sep 20, 2026cs.GT

Dynamical low-rank equilibrium computation for stochastic games between advanced persistent threats and moving target defense

Moving target defense (MTD) against advanced persistent threats (APTs) in industrial control systems (ICS) has well-established game-theoretic formulations, but their practical value hinges on equilibrium computation, which faces two gaps: full-rank value iteration is prohibitively expensive at industrial scale, and the resulting defense strategies admit no certified robustness against adversarial perturbations. We first reveal that the attack and defense influence matrices of ICS dynamics are intrinsically low-rank: APTs infiltrate through a handful of entry points and MTD reconfigures only a few components per cycle. Our theory makes four contributions. First, an augmented gradient matrix certifies that the low-rank structure propagates through the non-smooth Bellman operator of the zero-sum stochastic game, so that every Bellman target lies near a low-dimensional subspace and low-rank truncation incurs an explicit error bound (Lemma 1, Theorem 1). Second, we propose the Dynamical Low-Rank Nash Equilibrium algorithm, named DLR-NE, which augments the rank-r search space each iteration, regularizes the core matrix spectrum, and retracts via truncated SVD, and prove that it converges geometrically to a neighborhood whose error decomposes into five physically interpretable sources (Theorem 2). Third, its per-step cost is O(nr^2), a Theta(n/r^2) speedup over full-rank value iteration (Theorem 3). Fourth, a single weight trades accuracy against a certified sensitivity bound of the induced defense strategy under core-matrix perturbations (Corollary 1). Six experiments on a nonlinear power-system testbed confirm each prediction, with 94% parameter compression at 2.3% utility loss. All experimental data and code are publicly available.

Tian Zijian, Zhang He, Chen Xinjie +2

College of Control Science and Engineering, Zhejiang University, PC 310027, China · Alibaba Group, Hangzhou, China

Nash Equilibrium Computation Zero-Sum Games Low-Rank Approximation

Sep 17, 2026cs.AI

Steering Equilibrium Selection in Regularized Self-Play via the Reference Policy

Regularized self-play -- the family behind DeepNash's Stratego play -- drives a two-player zero-sum policy to a Nash equilibrium by best-responding to a slowly moving, entropy-regularized reference policy

ρ

. When the game has a polytope of value-equivalent equilibria, the regularizer silently breaks the tie: with a uniform reference it selects the maximum-entropy member, the I-projection of

ρ

onto the Nash set. Can the reference be used to choose the equilibrium on purpose? On five exactly solvable games plus a 2-D polytope, with exact best responses and equivalence tests over independent seeds, anchoring the reference at a target member and refining steers self-play to that member with mean coordinate error 0.007 at median exploitability

5\times10^{-5}

, TOST-equivalent to the request within

\pm0.05

; the anchoring persists through refinement and follows the reference, not the initialization. Selection follows the reach-weighted I-projection (slope 0.969 [0.950, 0.987]). We report with equal emphasis where the story breaks: fixed off-manifold references cost 0.08-0.25 exploitability; stiff or flat families require a smaller mirror step, set by a pre-registered rule; boundary targets undershoot; curvature predicts where boundary saturation bites (rank correlation 0.90, p=0.037) while interior precision is curvature-independent. Table and MLP steering maps are equivalent within

\pm0.03

at every target (30 seeds); matched control arms show attention's robust signature is excess seed variance, any systematic shift bounded at 0.018 and not significant. Against a best response the selection-robustness trade-off is degenerate: steering matters only against fixed, non-equilibrium opponents. The recipe -- anchor the reference at the desired member and refine -- reinterprets the KL anchor of RLHF-style RL as a selection knob, not only a stability leash.

Luis Leal

Nash Equilibrium Self-Play RL KL-Regularized RL Zero-Sum Games

Sep 1, 2026cs.LG

NashDreamer: Model-Based Reinforcement Learning for Zero-Sum Imperfect-Information Games

Model-based reinforcement learning (MBRL) has achieved remarkable results in single-agent domains, yet its extension to competitive imperfect information games (IIGs) remains underexplored. In multi-agent settings, opponent-induced non-stationarity complicates the learning process, and decentralized model learning faces severe identifiability barriers, which we argue make centralized model learning a mathematical necessity. Building on this analysis, we propose NashDreamer, a principled MBRL framework for two-player zero-sum IIGs. It introduces a centralized Multi-Agent Recurrent State-Space Model (MARSSM) that decouples environment dynamics from the effect of players' strategies on their individual observations. NashDreamer is designed to use arbitrary policy gradient algorithms and inherits their convergence guarantees towards Nash equilibria under an idealized model. Empirical evaluations across four benchmark games demonstrate that NashDreamer substantially improves sample efficiency over model-free baselines early in the training. Finally, we theoretically analyze the architecture's optimization landscape, identifying the vulnerability of the Dreamer family of algorithms to posterior collapse in stochastic environments. We leave it as an open challenge.

Tomáš Holeček, Viliam Lisý

Artificial Intelligence Center, Department of Computer Science Faculty of Electrical Engineering, Czech Technical University in Prague

Imperfect-Information Games Zero-Sum Games Multi-Agent Reinforcement Learning Model-Based RL

Aug 10, 2026cs.MA

Distributed Team Orchestration via Supervisor Networks: Convergence, Optimality, and Resilience

In this paper, we study zero-sum potential team games with a supervisor network, where agents rely on supervisor-provided belief information rather than accurate common beliefs. The main challenge is that such belief information can be inaccurate because of supervisors' belief-estimation errors and the misreporting of joint actions by Byzantine teams. We propose the distributed team-orchestrating algorithm (DTOA), which combines team fictitious play with supervisor-based distributed belief learning. We prove the convergence of supervisors' belief estimates and establish that the induced learning dynamics converge to a near team-Nash equilibrium (TNE) in terms of the team-Nash gap (TNG). In the Byzantine setting, we consider a misreporting attack model and develop a Byzantine-resilient DTOA. We further provide probabilistic guarantees for Byzantine-team identification and establish an asymptotic bound on the honest TNG. Numerical experiments illustrate the theoretical findings, compare DTOA with baseline learning methods, and evaluate its performance in a Markov decision process setting.

Juntian Zhu, Guanpu Chen, Tongtian Zhu +3

School of Artificial Intelligence and Data Science, University of Science and Technology of China, Hefei 230026, China · School of Automation, Southeast University, Nanjing 210096, China · College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China +2

Multi-Agent Orchestration Zero-Sum Games Multi-Agent Systems Ad Hoc Teamwork

Aug 7, 2026cs.AI

Beyond the Black Box: Interpretable Models of Human Randomisation Failures

Mixed strategy equilibrium predicts i.i.d play: past actions should not help predict future decisions. Human players, however, systematically depart from this benchmark, and in O'Neill's zero sum card game, these departures can be predicted by black box sequence models such as LSTMs. This paper asks whether that predictive power can be achieved by transparent alternatives that also reveal the behavioural structure behind it. Using 84,060 decisions from 2,802 pairs, the analysis first benchmarks naive and behavioral models against interpretable machine learning and deep learning models, then evaluates the modified EWA specifications of prior work against these benchmarks and uses the LASSO diagnostics to motivate a further nested frequency tracking extension. The results show that repeat or avoid behavior, especially players' management of their own recent action histories, accounts for most of the interpretable and strategically exploitable signal, while frequency tracking adds little out of sample.

Ngoc Linh Dao

Alpen-Adria-University of Klagenfurt, Austria

Interpretable ML Zero-Sum Games Human Behavior Prediction

Jul 30, 2026cs.GT

Agents That Certify Their Own Exploits: Confidence-Scheduled Restricted Responses for Safe Opponent Exploitation

An agent playing a Nash-equilibrium strategy in a two-player zero-sum imperfect-information game secures the game value but forfeits the additional value offered by a flawed opponent. Diffuse deviations pose a particular challenge: binary release rules may gather too little evidence to act, while a full best response to an incomplete opponent model can be highly exploitable. We introduce \emph{budget-constrained confidence-scheduled restricted responses} (CS-RNR), the first opponent-exploitation method whose safety guarantee is a certificate the agent computes on the strategy it actually deploys, so that every exploit it commits to is one it has audited itself. The method tracks pooled action frequencies with anytime-valid confidence sequences and treats a frequency as exploitable only once its interval separates from an equilibrium reference. The confirmed deviations define a conservative opponent model, which a restricted-response solve turns into candidate counter-strategies over a grid of pin levels. Before deployment, each complete candidate is evaluated by a full-tree best response. The resulting certificate is compared with a user-specified budget and committed atomically with the strategy. Because this check is performed on the played strategy, model quality determines the exploitation achieved while the certificate controls reference-relative expected loss. In Leduc hold'em, CS-RNR obtains

6.2\times

the steady-state gain of a money-verified binary gate while keeping every deployed strategy within budget. A trajectory mixture using the same estimator reaches

13.6\times

the budget. Across Leduc, Liar's Dice, and 5-rank Leduc, all

36{,}000

audited hands satisfy the reported certificate tolerance.

Boning Li, Longbo Huang

IIIS, Tsinghua University

Imperfect-Information Games Zero-Sum Games

Jul 20, 2026cs.AI

The Curvature Shadow: An Apparent Failure of Maximum-Entropy Equilibrium Selection is a Removable Artifact

In two-player zero-sum games whose Nash equilibria form a convex set, regularized solvers such as Regularized Nash Dynamics (R-NaD) empirically select the maximum-entropy member: the information projection (I-projection) of a uniform reference onto the Nash set. On a panel of small games this match is exact, with one apparent exception: in Kuhn poker R-NaD lands at bluff coordinate 0.180 while the maximum-entropy member sits at 0.201, a coordinate gap of about 0.021, even though R-NaD attains 99.7 percent of the maximum entropy. We ask whether this gap is a genuine selection bias or an artifact, and answer it quantitatively. We show that for selection on a one-dimensional Nash manifold the coordinate gap factorizes as

\mathrm{gap} \approx \sqrt{2δ/κ}

, where

δ

is the entropy shortfall of the solver and

κ

is the curvature of the entropy landscape at its peak. Across five games this relation holds to within

2 \times 10^{-4}

(under 1 percent relative error). The four matrix games have

δ\approx 0

(R-NaD reaches the maximum-entropy member exactly) and therefore no gap regardless of curvature; only the sequential game (Kuhn) has

δ> 0

. A causal sweep of the magnet strength drives

δ\to 0

and the gap toward zero along the predicted curve (fitted scaling exponent 0.50,

R^2 > 0.999999

, against the exact prediction of 1/2), until the dynamics destabilize at a stability floor: behavior consistent with a removable shortfall and inconsistent with a fixed bias. We quantify the curvature half of the law from measured curvatures and flag a moving-target pitfall in the natural Tsallis-entropy experiment. The Kuhn gap is thus the curvature shadow of a small, removable entropy shortfall on an unusually flat peak; the I-projection account is upheld up to a flatness-limited residual.

Luis Leal

Nash Equilibrium Imperfect-Information Games Zero-Sum Games Selection Bias

Jul 7, 2026cs.AI

FootsiesGym: A Fighting Game Benchmark for Two-Player Zero-Sum Imperfect-Information Games

We present FootsiesGym, an open-source environment for learning in a non-trivial two-player, zero-sum, imperfect-information game. Built on HiFight's minimalist 2D fighting game Footsies, it isolates the cyclic, non-transitive strategic interactions of fighting game neutral play while remaining simple enough for efficient analysis. We provide a vectorized simulator that enables high-throughput training on standard hardware, making the environment accessible and reproducible. We describe the design of the environment, benchmark several reinforcement learning algorithms, and discuss open research directions it enables. The code is available at https://github.com/como-research/FootsiesGym.

Chase McDonald, Nathan Tsang, Wesley N. Kerr

Como Research · Riot Games

RL Benchmarks Game-Playing Agents Imperfect-Information Games Zero-Sum Games Agent Benchmarks

Jul 1, 2026cs.LG

Towards Learning Representations of Policies in Two-Player Zero-Sum Imperfect-Information Games

We investigate the problem of learning useful policy representations (embeddings) in two-player zero-sum imperfect-information games. We make three contributions: First, we introduce methods of creating datasets of policies for a given game. Second, we propose methods to learn policy representations. Third, we introduce downstream tasks to evaluate the effectiveness of such representations. We evaluate each dataset method, embedding method, and downstream task on Kuhn and Leduc Poker. Although our methods are very basic, we demonstrate that useful behavioral representations are present in the learned embeddings. To our knowledge, this work is among the first to systematically compare self-supervised learning techniques for learning policy representations in games. Our code is available at https://github.com/VitamintK/ssl-project for others to extend.

Kevin Wang, Kevin Yang, Arjun Prakash +1

Brown University

Representation Learning Imperfect-Information Games Self-Supervised Learning Zero-Sum Games

Jun 27, 2026cs.LG

Entropy Regularized Reinforcement Learning for Zero-Sum Stochastic Differential Games in a Regime-Switching Jump-Diffusion Process

To address parameter misspecification and sudden structural environmental changes in conventional stochastic differential game (SDG) frameworks, this paper introduces a distributional control approach that characterizes optimal strategies as probability distributions over actions, conditioned on the continuous state, the discrete regime state, and parameters. This forms a reinforcement learning framework for entropy-regularized zero-sum stochastic differential games (ERRL-ZSSDGs) in a regime-switching jump-diffusion process. Using the dynamic programming principle (DPP), we derive the associated coupled systems of Hamilton-Jacobi-Bellman-Isaacs (HJBI) equations, from which equilibrium strategies are expressed via gradients of the value function. For linear-quadratic problems, semi-analytical solutions for both value function and equilibrium strategies are obtained by solving a system of coupled ordinary differential equations (ODEs). In more general settings, an Actor-Critic policy improvement algorithm is developed to approximate the value functions and equilibrium policies across different regimes. The method is applied to an investment game, and numerical examples illustrate the effect of the temperature parameter and regime transitions on optimal policies and values.

Congde Hu, Zhuo Jin, Danping Li +1

School of Mathematics and Statistics, Anhui Normal University, Wuhu, 241002, Anhui, China. · Department of Actuarial Studies and Business Analytics, Macquarie University, Sydney, 2109, NSW, Australia. · School of Statistics, KLATASDS-MOE, China Inclusive Ageing Finance Research Center, East China Normal University, Shanghai, 200062, Shanghai, China.

Zero-Sum Games Maximum Entropy RL

Jun 26, 2026cs.GT

Which Nash Equilibrium? Solver-Dependent Selection on Zero-Sum Nash Polytopes

Many two-player zero-sum games admit not a unique Nash equilibrium but a convex set of them: a polytope of profiles that all share the minimax value V* yet prescribe different behaviour. Standard solvers each converge to some equilibrium and are treated as interchangeable. We ask whether they instead select different members of the Nash set, systematically as a function of the algorithm rather than the seed. Using a tabular, exactly solvable testbed of six games with analytically known Nash sets -- including a two-dimensional Nash polytope and Kuhn poker -- we find that (i) selection is determined by the algorithm, not the seed, but families differ only on asymmetric Nash sets; (ii) regularized last-iterate methods (R-NaD, magnetic mirror descent) select the maximum-entropy member, the information projection of their uniform reference onto the Nash set -- exactly on the 2-D polytope and at 99.7% of maximum entropy in Kuhn -- while regret-averaging methods (CFR, CFR+, fictitious play) drift to a lower-entropy face; we confirm this on a randomized 180-game ensemble, where R-NaD attains the maximum-entropy member in 100% of converged games while CFR+ sits strictly below it in 94% (paired Wilcoxon p < 10^-27); (iii) the selected member has downstream consequences against sub-optimal opponents that scale with sequential/hidden-information structure but stay bounded -- in Kuhn the max-entropy member is a strictly better hedge, whereas on the matrix games the members differ without either dominating. We also report two negative results correcting common intuitions: removing CFR's positive-orthant (max(R,0)) projection does not eliminate boundary drift; and R-NaD's selection is anchor-following, not initialization-independent. We state the maximum-entropy / I-projection characterization as a strongly data-supported conjecture, checked throughout against analytic ground truth.

Luis Leal

Nash Equilibrium Imperfect-Information Games Zero-Sum Games Regret Minimization Nash Equilibrium Computation

Jun 22, 2026cs.LG

EMAgnet: Parameter-Space EMA Regularization for Policy Gradient Self-Play in Large Games

Recent work has established that regularized policy gradient methods such as PPO, when used in self-play, can match or exceed specialized game-theoretic algorithms for solving two-player zero-sum imperfect-information games. The uniform distribution has emerged as a strong policy regularization target for this purpose, but it regularizes equally toward all actions regardless of their viability. We introduce EMAgnet, which instead regularizes toward an exponential moving average (EMA) of the last-iterate policy's parameters, providing an adaptive regularization target that evolves with the agent's improving strategy. We evaluate EMAgnet on both standard two-player zero-sum benchmarks and modified benchmarks with exploration challenges and large numbers of strictly dominated strategies. Relative to PPO self-play with uniform-magnet regularization under both linear and power-law annealing schedules, EMAgnet achieves lower exploitability in the majority of tested environments, with consistent performance gains across games containing strictly dominated strategies.

Tristan Maidment, JB Lanier, Chase McDonald +5

1Riot Games · 3New York University · University of California, Irvine

Self-Play RL Imperfect-Information Games Zero-Sum Games Policy Gradient Methods Proximal Policy Optimization Policy Learning

Jun 21, 2026cs.MA

GARIP: A Running-Average Moving Reference for Last-Iterate Self-Play in Two-Player Zero-Sum Games

Self-play with naive gradient ascent cycles in two-player zero-sum games: the last iterate orbits the equilibrium. Modern methods restore last-iterate convergence by regularizing toward a reference policy -- MMD a fixed one (reaching only the regularized equilibrium), R-NaD a periodic snapshot (the engine of DeepNash). We study GARIP, which anchors to the running average, and isolate what the choice of reference controls. Our central result is a mechanism: collapse tracks the peak lag of the reference, and among causal convex averages of a fixed mean lag the running average (flat profile, peak

=

mean) uniquely minimizes that peak, while a snapshot's sawtooth has peak

= 2\times

mean (a one-line theorem). Two consequences follow. Convergence: we prove local last-iterate convergence at constant anchor strength -- the anchor scales the base map's rotation by

1-β

, crossing the stability boundary and turning a recurrent base into a contraction (global convergence is conjectured at small

β

; we characterize a large-

β

consensus failure). Robustness: GARIP matches R-NaD's peak performance -- on matrix games, the Coin Game, and the board games Connect Four/Othello, both moving references are far more robust than fixed-magnet and magnet-free baselines -- but is the better hyperparameter default; we report it both ways: over the full grid collapse rates are statistically indistinguishable, yet at conventional parameterizations a matched-mean-lag setting collapses in 0/40 vs 10/40 seeds (a snapshot matches it only by knowing to shorten

K

). The boundaries: an anticipatory (negative-weight) reference does better still on the stale side, and the advantage appears only where naive self-play cycles (five deep self-play loops). All experiments are pure JAX and reproducible.

Can Savcı

Independent Researcher İzmir, Türkiye

Nash Equilibrium Last-Iterate Convergence Self-Play RL Zero-Sum Games Convergence Analysis Nash Equilibrium Computation

Jun 1, 2026cs.MA

A Game-Theoretic Decision Framework for Optimal Selection of Coordination Detection Methods in Multi-UAV Fleet Operations

Detecting coordination among unmanned aerial vehicle (UAV) fleets operating in shared airspace and identifying the route-lead aircraft whose navigation decisions govern fleet behavior presents a fundamental speed--accuracy trade-off: fast methods enable real-time traffic management but sacrifice detection fidelity, while accurate methods may exceed the time budget for actionable airspace deconfliction. This paper presents a game-theoretic decision framework that resolves this trade-off by formulating method selection as a two-player zero-sum game between a Monitor (selecting computational methods and parameters) and Nature (selecting the unknown traffic scenario). We construct an end-to-end pipeline from trajectory surveillance data through eight candidate detection algorithms, a Monte Carlo sensitivity analysis characterizing their stochastic performance, and finally a multi-objective optimization layer that identifies Pareto-optimal method portfolios. The minimax solution provides a robust mixed strategy with a probability distribution over methods that guarantees worst-case performance regardless of scenario uncertainty. Experimental evaluation across 200 randomized configurations spanning 5--50 aircraft demonstrates that the framework recommends distinct method portfolios depending on operational priority: Koopman Phase dominates balanced (70.6%) and speed-priority (79.7%) profiles, while CRQA emerges as primary (47.4%) when route-lead identification is prioritized. The framework achieves a guaranteed game value of 0.29--0.53 (normalized utility) across all tested preference profiles, providing the first principled, scenario-adaptive methodology for computational method selection in UTM fleet monitoring operations.

Christian Manasseh, Savana Ammons

Mobius Logic Inc., Tysons, VA, USA

Algorithm Selection Air Traffic Management Intelligent Transportation Systems Zero-Sum Games

May 31, 2026cs.LG

Fairness in two-player zero-sum games with bandit feedback

We study two-player zero-sum games (TPZSGs) with bandit feedback under fairness constraints requiring every action to be played with probability at least

α/m

. Existing instance-dependent results target

\textit{pure}

Nash equilibria, while fairness generically produces

\textit{mixed}

equilibria, a harder learning target. Our key technical tool is a reparametrization: every fair strategy decomposes as

p = (α/m)\mathbf{1} + (1-α)\widetilde{p}

with

\widetilde{p} \in Δ_m

, and substituting into the payoff form yields

p^{\top}Aq = \widetilde{p}^{\top}\widetilde{A} q

for a fair payoff matrix

\widetilde{A} := (1-α)A + α\mathbf{1} c^{\top}

, where

c_j = \tfrac{1}{m}\sum_i A(i,j)

is the column-mean vector. The fair game on

A

is then equivalent to a standard zero-sum game on

\widetilde{A}

, so equilibrium existence, KKT structure, and LP basis stability reduce to classical results applied to

\widetilde{A}

. We derive the fair minimax value, fair Nash equilibrium, fair regret, and a clean dual representation showing the price of fairness is at most

α(1-1/m)

and vanishes whenever the unconstrained equilibrium already has full support. Our main result is an

\widetilde{O}(T^{2/3})

regret bound for an Explore-Then-Commit algorithm,

\texttt{Fair-ETC-TPZSG}

, applicable to general mixed fair equilibria, together with a discussion of why naive action elimination does not readily improve it. When the fair equilibrium has a single dominant action, equivalently when

\widetilde{p}^{\star}

is a vertex of

Δ_m

, the bound sharpens to instance-dependent

\widetilde{O}(1/\widetildeΔ(α)^{2})

, where

\widetildeΔ(α)

is the LP-margin gap.

S Akash, Pratik Gajane

LatentForce.ai Bengaluru, India · Laboratoire d’Informatique Fondamentale d’Orléans University of Orléans, France

Nash Equilibrium Zero-Sum Games Algorithmic Fairness Adversarial Bandits Nash Equilibrium Computation

May 27, 2026cs.AI

Global Policy-Space Response Oracles for Two-Player Zero-Sum Games

The Policy-Space Response Oracles (PSRO) framework scales equilibrium computation to large zero-sum games by iteratively expanding a restricted strategy set using deep reinforcement learning (DRL). A central challenge is to construct, under limited computational budgets, a small strategy population whose induced game well approximates the full game. Existing PSRO variants typically expand the population using best responses to meta-strategies computed from restricted-game payoffs, which can lead to inefficient expansions that provide limited global improvement. We propose to guide population expansion by directly evaluating the post-expansion population quality. Specifically, we adopt Population Exploitability (PE) to measure how well a restricted strategy set represents the full game, and introduce a two-phase exploration--selection framework that explicitly minimizes PE during expansion. We instantiate this framework as Global PSRO, a practical DRL-based algorithm that efficiently generates candidate responses and estimates PE via parameter-sharing conditional neural networks. Experiments across multiple two-player zero-sum games show that Global PSRO achieves lower exploitability and approximates Nash equilibria with significantly fewer policy iterations than prior PSRO methods.

Junyu Zhang, Feihong Yang, Jian Wang +2

Department of Electronic Engineering, Tsinghua University, Beijing, China · Qiyuan Lab, Beijing, China

Nash Equilibrium Game Theory Zero-Sum Games Multi-Agent Reinforcement Learning Nash Equilibrium Computation

May 26, 2026cs.LG

Bilevel Optimization over Saddle Points of Zero-Sum Markov Games

Reinforcement learning (RL) often has a hierarchical structure, where an upper-level (UL) learner selects model parameters and a lower-level (LL) decision-making process responds, naturally leading to a bilevel optimization problem. Most existing bilevel RL methods assume a single-policy LL Markov decision process (MDP), and therefore fail to capture competitive structures arising in applications such as incentive design, where multiple policies interact. We study bilevel optimization problems in which the LL problem is a regularized min-max zero-sum Markov game and the UL objective is optimized through the saddle-point equilibrium induced by the LL game. In this work, we propose penalty-augmented Nikaido-Isoda descent-ascent (PANDA), a penalty-based first-order policy-gradient method based on the Nikaido-Isoda function. By exploiting the min-max game structure, PANDA avoids computing UL hypergradients and does not require second-order information. We prove that PANDA converges to stationary points without convexity assumptions on either the UL or LL objectives. Moreover, PANDA reaches an

ε

-stationary point in

\tilde{\mathcal{O}}(ε^{-1})

iterations with sample complexity

\tilde{\mathcal{O}}(ε^{-3})

, matching the best-known rates for bilevel RL with single-policy LL MDPs. Experiments demonstrate the superior performance of PANDA over closely related baselines.

Zihao Zheng, Irwin King, Songtao Lu

Department of Computer Science and Engineering, The Chinese University of Hong Kong · Shun Hing Institute of Advanced Engineering, The Chinese University of Hong Kong

Game Theory Zero-Sum Games Min-Max Optimization Bilevel Optimization Policy Gradient Methods

May 22, 2026cs.AI

GENSTRAT: Toward a Science of Strategic Reasoning in Large Language Models

Large language models (LLMs) are increasingly deployed as economic agents in marketplaces, auctions, and bidding settings. Anticipating their behavior in any specific deployment is hard. Existing strategic-reasoning benchmarks evaluate models on fixed canonical games. These benchmarks may saturate as the frontier improves, and they do not allow evaluators to generalize with confidence from benchmark performance to the varied and messy strategic environments that actual deployments involve. We introduce GENSTRAT, which uses procedurally generated strategic environments to address these challenges. Concretely, we generate a distribution of two-player zero-sum imperfect-information card games. The generator can draw fresh games on demand, allowing for evergreen evaluation and resistance to contamination. We pair the game distribution with a capability-profile methodology that decomposes model competence across six axes (state space, temporal depth, information sensitivity, opponent modeling, risk, and brittleness). We also introduce a jaggedness measure of within-distribution smoothness that detects when a model's advantage jumps unpredictably between strategically similar games. We sample 50 benchmark games from a 2,000-game generated pool and evaluate nine frontier and open-weight LLMs in a head-to-head tournament with over 36,000 matches. Newer frontier-tier models score higher on average. Beyond that average, models with near-identical overall strength show qualitatively different capability profiles, and two of the top three leaderboard models (gpt-5 and claude) are noticeably more locally volatile than the third (gemini-3.1-pro), despite being close in overall strength. Together, the capability profile and the jaggedness measure give a deployment-relevant diagnostic that the overall ranking alone cannot provide.

Vartan Shadarevian, Kia Ghods, Alex Kenich +1

Princeton University · Google

LLM Evaluation Imperfect-Information Games Game Theory Zero-Sum Games Strategic Reasoning Risks in Language Models AI Agent Benchmarks+2

May 19, 2026cs.LG

Understanding Dynamics of Adam in Zero-Sum Games: An ODE Approach

The remarkable success of the Adam in training neural networks has naturally led to the widespread use of its descent-ascent counterpart, Adam-DA, for solving zero-sum games. Despite its popularity in practice, a rigorous theoretical understanding of Adam-DA still lags behind. In this paper, we derive ordinary differential equations (ODEs) that serve as continuous-time limits of the Adam-DA. These ODEs closely approximate the discrete-time dynamics of Adam-DA, providing a tractable analytical framework for understanding its behavior in zero-sum games. Using this ODE approach, we investigate two fundamental aspects of Adam-DA: local convergence and implicit gradient regularization. Our analysis reveals that the roles of the first- and second-order momentum parameters in zero-sum games are exactly the opposite of their well-documented effects in minimization problems. We validate these predictions through GAN experiments across multiple architectures and datasets, demonstrating the practical implications of this reversed momentum effect.

Yi Feng, Weiming Ou, Xiao Wang

Aarhus University, Aarhus, Denmark · Shanghai University of Finance and Economics, Shanghai, China · MoE Key Laboratory of Interdisciplinary Research of Computation and Economics, Shanghai University of Finance and Economics, Shanghai, China

Zero-Sum Games Min-Max Optimization Adaptive Gradient Methods Neural Network Training Dynamics Implicit Regularization Gradient Descent Dynamics

May 14, 2026cs.LG

Data-Augmented Game Starts for Accelerating Self-Play Exploration in Imperfect Information Games

Finding approximate equilibria for large-scale imperfect-information competitive games such as StarCraft, Dota, and CounterStrike remains computationally infeasible due to sparse rewards and challenging exploration over long horizons. In this paper, we propose a multi-agent starting-state sampling strategy designed to substantially accelerate online exploration in regularized policy-gradient game methods for two-player zero-sum (2p0s) games. Motivated by an assumption that offline demonstrations from skilled humans can provide good coverage of high-level strategies relevant to equilibrium play, we propose the initialization of reinforcement learning data collection at intermediate states sampled from offline data to facilitate exploration of strategically relevant subgames. Referring to this method as Data-Augmented Game Starts (DAGS), we perform experiments using synthetic datasets and analytically tractable, long-horizon control variants of two-player Kuhn Poker, Goofspiel, and a counterexample game designed to penalize biased beliefs over hidden information. Under fixed computational budgets, DAGS enables regularized policy gradient methods to achieve lower exploitability in games with significantly more challenging exploration. We show that augmenting starting state distributions when solving imperfect information games can lead to biased equilibria, and we provide a straightforward mitigation to this in the form of multi-task observation flags. Finally, we release a new set of benchmark environments that drastically increase exploration challenges and state counts in existing OpenSpiel games while keeping exploitability measurements analytically tractable.

JB Lanier, Nathan Monette, Pierre Baldi +1

University of California Irvine · University of Oxford

RL Benchmarks Self-Play RL Imperfect-Information Games Game Theory Zero-Sum Games RL Exploration+1

May 13, 2026cs.GT

When and Why is Optimistic Multiplicative Weights Slow? The Geometry of Energy Dissipation

This paper studies the convergence of the Optimistic Multiplicative Weights Update algorithm (OMWU) in two player zero-sum games. Recent works have identified instances on which the last-iterate of OMWU can converge arbitrarily slowly, but understanding when and why this slow convergence occurs has remained open. In this work, we develop a new analysis framework that gives sharp, quantitative explanations for this behavior. Our analysis is based on viewing the algorithm's dual iterates as an optimistic skew-gradient descent with respect to an energy function. We prove over the dual iterates that energy is dissipative, and by establishing tight bounds on the magnitude of dissipation, our analysis quantifies the geometric bottlenecks that arise when the corresponding primal iterates are close to the simplex boundary. This further translates into a new linear last-iterate convergence rate in KL divergence on games with a unique and interior Nash equilibrium. Compared to prior work, this new rate contains a much sharper dependence on game-specific constants, and we prove this dependence is optimal. Moreover, these geometric insights further translate into new separations on uniform convergence rates for OMWU. On the one hand, we prove constant lower bounds on the uniform best-iterate convergence rate in KL divergence and total variation distance from Nash. On the other hand, we establish for the

2\times 2

setting a new

{\widetilde O}(T^{-1/2})

best-iterate rate in duality gap, improving substantially over prior work. Together, this shows in general that uniform convergence rate guarantees do not transfer across different measures of distance to Nash.

John Lazarsfeld, Anas Barakat, Georgios Piliouras +2

SUTD · Google DeepMind · NUS CQT +2

Nash Equilibrium Last-Iterate Convergence Optimization Convergence Analysis Game Theory Zero-Sum Games Convergence Analysis+1

May 13, 2026cs.LG

Offline Two-Player Zero-Sum Markov Games with KL Regularization

We study the problem of learning Nash equilibria in offline two-player zero-sum Markov games. While existing approaches often rely on explicit pessimism to address distribution shift, we show that KL regularization alone suffices to stabilize learning and guarantee convergence. We first introduce Regularized Offline Sequential Equilibrium (ROSE), a theoretical framework that achieves a fast

\widetilde{\mathcal{O}}(1/n)

convergence rate under \textit{unilateral concentrability}, improving over the standard

\widetilde{\mathcal{O}}(1/\sqrt{n})

rates in unregularized settings. We then propose Sequential Offline Self-play Mirror Descent (SOS-MD), a practical model-free algorithm based on least-squares value estimation and iterative self-play updates. We prove that the last iterate of SOS-MD attains the same

\widetilde{\mathcal{O}}(1/n)

statistical rate up to a vanishing optimization error of order

\widetilde{\mathcal{O}}(1/\sqrt{T})

in the number of self-play iterations

T

.

Claire Chen, Yuheng Zhang, Xinyu Liu +3

1California Institute of Technology. · University of Illinois Urbana-Champaign. · University of Virginia. +2

Nash Equilibrium Reinforcement Learning Self-Play RL KL-Regularized RL Game Theory Zero-Sum Games+3

May 11, 2026cs.LG

Equilibrium Residuals Expose Three Regimes of Matrix-Game Strategic Reasoning in Language Models

Large language models can score well on named game-theory benchmarks while failing on the same strategic computation once semantic cues are removed. We show this gap with procedurally generated zero-sum matrix games: a model that recognizes familiar games drops to 34%, 18%, and 2% success on anonymous

2{\times}2

,

3{\times}3

, and

5{\times}5

payoff matrices. The benchmark separates semantic recall, learned approximate Nash computation, and an output-interface bottleneck that limits scale. Training only on

2{\times}2

and

3{\times}3

games, supervised fine-tuning raises unseen

5{\times}5

--

7{\times}7

success from 2% to 61%, while exploitability-reward training averages 37% with high seed variance. We prove that the exploitability residual is

2

-Lipschitz in payoff perturbations, unlike discontinuous vertex-returning LP equilibrium selectors, explaining why residual training can transfer under payoff shifts even when formatting instability limits mean performance. A dominated-action padding experiment provides causal evidence: trained models solve

3{\times}3

games embedded in much larger matrices, while random-padded controls fail and dense

12{\times}12

games remain near failure. Procedural evaluation is therefore necessary for measuring strategic reasoning, and residual rewards expose a real but format-limited route to approximate equilibrium computation.

Wenhua Nie, Binhan Luo, Zijie Meng +2

National Taiwan University

Nash Equilibrium LLM Evaluation Game Theory RL for Language Model Reasoning Zero-Sum Games Nash Equilibrium Computation

May 10, 2026cs.LG

Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions

Last-iterate convergence of learning dynamics in games has attracted significant recent attention. In two-player zero-sum games with bandit feedback, where only the loss of the selected action pair is observed, Fiegel et al. (2025) show a separation between average-iterate and last-iterate convergence in duality gap: while the optimal t^(-1/2) rate after t rounds is achievable for the former via standard no-regret algorithms, the latter cannot converge faster than t^(-1/3) in expectation or t^(-1/4) with high probability. However, in many practical settings, such as preference learning, the players observe not only their loss but also the opponent's action. This raises a natural question: can such additional information enable faster last-iterate convergence? We answer this question affirmatively, showing that t^(-1/2) last-iterate convergence is achievable with high probability in this setting, via an efficient algorithm that updates its strategy infrequently by solving an estimated log-barrier-regularized game. We identify fundamental obstacles preventing standard analysis for multi-armed bandits, the single-player case, from generalizing to games, and develop a novel analysis to overcome them. Experiments confirm that our algorithm indeed converges faster than naive baselines and prior methods that do not exploit opponent-action feedback. Finally, we note that our results also improve those for dueling bandits, a special case with skew-symmetric game matrices.

Soumita Hait, Ping Li, Haipeng Luo +1

University of Southern California · Shanghai University of Finance and Economics · University of Iowa

Last-Iterate Convergence Imperfect-Information Games Game Theory Zero-Sum Games Convergence Analysis

Apr 17, 2026cs.LG

The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback

We study the problem of learning in zero-sum matrix games with repeated play and bandit feedback. Specifically, we focus on developing uncoupled algorithms that guarantee, without communication between players, the convergence of the last-iterate to a Nash equilibrium. Although the non-bandit case has been studied extensively, this setting has only been explored recently, with a bound of

\mathcal{O}(T^{-1/8})

on the exploitability gap. We show that, for uncoupled algorithms, guaranteeing convergence of the policy profiles to a Nash equilibrium is detrimental to the performance, with the best attainable rate being

Ω(T^{-1/4})

in contrast to the usual

Ω(T^{-1/2})

rate for convergence of the average iterates. We then propose two algorithms that achieve this optimal rate up to constant and logarithmic factors. The first algorithm leverages a straightforward trade-off between exploration and exploitation, while the second employs a regularization technique based on a two-step mirror descent approach.

Côme Fiegel, Pierre Ménard, Tadashi Kozuno +2

ENSAE Paris - CREST, Palaiseau, France · Inria - FairPlay · ENS Lyon, Lyon, France +3

Nash Equilibrium Last-Iterate Convergence Game Theory Zero-Sum Games Convergence Analysis Mirror Descent+1