Toward Online Robust Zero-Sum Markov Games with Function Approximation

Chenhao Zhou; Jiyu Wei

cs.LGOct 19, 2026

Toward Online Robust Zero-Sum Markov Games with Function Approximation

Authors: Chenhao Zhou, Jiyu Wei

Organizations: College of Computer Science and Technology, Zhejiang University

Abstract

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.

Figures & tables

Work	Problem class	Robust	Approx. regime	General FA theorem	Closed scalable theorem
Ghosh et al. [6]	robust MDP	$\checkmark$	GFA	$\checkmark$	$\checkmark$
Huang et al. [7] , Jin et al. [8]	zero-sum MG	$\times$	GFA	$\checkmark$	$\checkmark$
Farhat et al. [40]	robust MG	$\checkmark$	tabular / model-based	$\times$	$\checkmark$
Ma et al. [9] , Shi et al. [10] , Shi et al. [11]	robust MG / MARL	$\checkmark$	tabular / generative	$\times$	problem-specific
Zheng and Lin [5]	robust MG	$\checkmark$	linear	$\times$	$\checkmark$
Ours	robust zero-sum MG	$\checkmark$	GFA, projected, linear / kernel	$\checkmark$	$\checkmark$

Table 1: Positioning relative to representative prior work. “General FA theorem” indicates that a paper states a theorem-level guarantee for general or projected function approximation. “Closed scalable theorem” indicates a fully verified large-state result inside the paper, rather than only a tabular or generative specialization.

\mathfrak{F}_{e}:=\left\{f\in\mathcal{F}:\widehat{\mathrm{BV}}_{h,e}(f)\leqslant\beta_{h,e},\ \forall h\right\}

Algorithm 1 Optimistic Dual Robust Bellman (ODRB) with Epochwise Refitting and Cross-Fit Validation

Method	Proxy	Deploy	Proxy gap
Sigma0	$0.230\pm 0.088$	$0.230\pm 0.088$	$0.0080\pm 0.0047$
ODRB $(\beta=0.30,\tau=0.02)$	$0.204\pm 0.069$	$0.239\pm 0.089$	$0.0072\pm 0.0074$
ODRB $(\beta=0.20,\tau=0.02)$	$0.162\pm 0.057$	$0.236\pm 0.089$	$0.0069\pm 0.0066$
NoEx $(\beta=0.30)$	$0.254\pm 0.102$	$0.288\pm 0.115$	$0.0644\pm 0.0687$

Table 2: Main linear_mixture results at

d=8

and

5000

episodes.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Work	Transition model	Complexity / exploration	Distinguishing target
Huang et al. [7]	Nominal	Minimax-Eluder complexity	Value regret under general function approximation
Jin et al. [8]	Nominal	Multi-agent BE dimension and exploiter	Nash-policy learning in large state spaces
This paper, $\sigma=0$	Nominal	Robust MG-BE reduces to nominal counterpart	Same $\sqrt{K}$ -type episode dependence, up to complexity, coverage, horizon, and logs
This paper, $\sigma>0$	Ambiguity set around nominal kernel	Response-branch coverage plus operator transfer	Candidate-dependent robust dual learned from nominal transitions and evaluated on worst-case occupancies

Appendix

Table 3: Relationship to representative non-robust zero-sum Markov-game results.

Experiment group	Jobs	Episodes/run	Seeds	Time/run
Tabular sanity suite	54	1500	3	$<1$ min
Original support-shift calibration	30	2000	3	$<1$ min
Linear-mixture dimension sweep	45	5000	5	$<2$ min
Linear-mixture $d=8$ seed extension	15	5000	5	$<2$ min
Redesigned support-shift sweep	125	2000	5	$<1$ min
Deployment-driven $\beta\times\tau$ resweep	120	5000	10	$<2$ min

Appendix

Table 4: Compute resources for the reported experiment groups. Runtime ranges are approximate single-job wall-clock times on the internal CPU workstation used for the paper.

Method	Seeds	Proxy	Deploy	Proxy gap
Sigma0	10	$0.230\pm 0.088$	$0.230\pm 0.088$	$0.0080\pm 0.0047$
ODRB $(\beta=0.30,\tau=0.02)$	10	$0.204\pm 0.069$	$0.239\pm 0.089$	$0.0072\pm 0.0074$
ODRB $(\beta=0.20,\tau=0.02)$	10	$0.162\pm 0.057$	$0.236\pm 0.089$	$0.0069\pm 0.0066$
NoEx $(\beta=0.30)$	10	$0.254\pm 0.102$	$0.288\pm 0.115$	$0.0644\pm 0.0687$

Appendix

Table 5: Linear-mixture main comparison at

d=8

with

10

seeds. ODRB rows are labeled by

(\beta,\tau)

, where

\beta

is the robustness weight and

\tau

is the validation threshold.

Seed	ODRB $(0.30,0.02)$	ODRB $(0.20,0.02)$
0	0.002070	0.002015
1	0.024937	0.008538
2	0.031841	0.032091
3	0.020964	0.016377
4	-0.001782	-0.001730
5	-0.000085	-0.001470

Appendix

Table 6: Paired seed-level deployment-return differences, ODRB minus Sigma0 , for the main

d=8

comparison.

Dim	Method	Proxy	Deploy	Gap
8	Sigma0	$0.230\pm 0.088$	$0.230\pm 0.088$	$0.0080\pm 0.0047$
8	ODRB $(\beta=0.30,\tau=0.02)$	$0.204\pm 0.069$	$0.239\pm 0.089$	$0.0072\pm 0.0074$
8	NoEx $(\beta=0.30)$	$0.254\pm 0.102$	$0.288\pm 0.115$	$0.0644\pm 0.0687$
16	Sigma0	$0.0556\pm 0.0313$	$0.0556\pm 0.0313$	$0.0166\pm 0.0115$
16	ODRB $(\beta=0.30,\tau=0.02)$	$0.0532\pm 0.0336$	$0.0532\pm 0.0336$	$0.0093\pm 0.0074$
16	NoEx $(\beta=0.30)$	$0.105\pm 0.074$	$0.105\pm 0.074$	$0.0604\pm 0.0638$

Appendix

Table 7: Linear-mixture dimension sweep across

d\in\{8,16,32\}

Setting	Proxy	Deploy	Gap	Entropy
ODRB $(\beta=0.20,\tau=0.01)$	$0.168\pm 0.063$	$0.245\pm 0.092$	$0.0120\pm 0.0164$	$4.585\pm 0.229$
ODRB $(\beta=0.20,\tau=0.02)$	$0.162\pm 0.057$	$0.236\pm 0.089$	$0.0068\pm 0.0065$	$5.067\pm 0.197$
ODRB $(\beta=0.30,\tau=0.02)$	$0.204\pm 0.069$	$0.239\pm 0.089$	$0.0073\pm 0.0074$	$5.076\pm 0.192$
ODRB $(\beta=0.30,\tau=0)$	$0.254\pm 0.102$	$0.288\pm 0.115$	$0.0624\pm 0.0669$	$3.781\pm 0.209$
ODRB $(\beta=0.50,\tau=0.02)$	$0.232\pm 0.091$	$0.236\pm 0.094$	$0.0126\pm 0.0148$	$5.022\pm 0.191$

Appendix

Table 8: Deployment-driven

d=8

ODRB resweep over

(\beta,\tau)

Method	$m=0.05$	$m=0.08$	$m=0.10$	$m=0.12$	$m=0.15$
Sigma0	0.5365	0.5618	0.4983	0.5049	0.4600
ODRB $\beta=0.10$	0.5952	0.5940	0.5742	0.5924	0.5912
ODRB $\beta=0.20$	0.5835	0.5940	0.5742	0.5924	0.5912
ODRB $\beta=0.30$	0.5600	0.5779	0.5552	0.5486	0.5912
NoEx $\beta=0.20$	0.5739	0.6000	0.6000	0.6000	0.6000

Appendix

Table 9: Redesigned support-shift benchmark: deployment worst-case return across overlap levels.

Robust RL

Robust reinforcement learning develops agents that maintain performance and safety under uncertainty, disturbances, attacks, and distribution shifts.

See all 222 papers

$Q$ Can Play That Game: Online Fitted $Q$ -Iteration for Continuous-Action Zero-Sum Markov Games with Convex-Concave Function Approximation
Oct 2, 2026Kushagra Gupta, Jingqi Li, Cade Armstrong +4Zero-Sum Games Game-Theoretic RL
The University of Texas at Austin · The University of California, Berkeley · Massachusetts Institute of Technology (MIT) Lincoln Labs
Interactive Distributionally Robust Multi-Agent Learning with General Function Approximation
Sep 25, 2026Debamita Ghosh, George K. Atia, Yue WangFunction Approximation in RL Reinforcement Learning
Department of Electrical and Computer Engineering, University of Central Florida, Orlando, FL 32816, USA · Department of Computer Science, University of Central Florida, Orlando, FL 32816, USA
Offline Two-Player Zero-Sum Markov Games with KL Regularization
May 13, 2026Claire Chen, Yuheng Zhang, Xinyu Liu +3Nash Equilibrium Computation Reinforcement Learning
1California Institute of Technology. · University of Illinois Urbana-Champaign. · University of Virginia. +2

Oct 2, 2026J/K move · Enter open · S save

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

Kushagra Gupta, Jingqi Li, Cade Armstrong, Lasse Peters+3

The University of Texas at Austin · The University of California, Berkeley · Massachusetts Institute of Technology (MIT) Lincoln Labs

Zero-Sum Games Game-Theoretic RL Q-Learning

Open paper AskPDF arXiv

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.

Abstract

Robust RL

Explore similar work

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

Interactive Distributionally Robust Multi-Agent Learning with General Function Approximation

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

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