Sample-Efficient Tabular Self-Play for Offline Robust Reinforcement Learning
Authors: Na Li
Zewu Zheng
Wei Ni
Hangguan Shan
Wenjie Zhang
Xinyu Li
Venue: NeurIPS 2025 poster ()
Keywords: robust Markov games
self-play
distribution shift
model uncertainty
reinforcement learning
Primary area: theory
TL;DR: We design an algorithm that first achieves the optimal sample complexity regarding both state and action spaces under partial coverage and environment uncertainty in robust two-player zero-sum Markov games.

Abstract: Multi-agent reinforcement learning (MARL), as a thriving field, explores how multiple agents independently make decisions in a shared dynamic environment. Due to environmental uncertainties, policies in MARL must remain robust to tackle the sim-to-real gap. We focus on robust two-player zero-sum Markov games (TZMGs) in offline settings, specifically on tabular robust TZMGs (RTZMGs). We propose a model-based algorithm (*RTZ-VI-LCB*) for offline RTZMGs, which is optimistic robust value iteration combined with a data-driven Bernstein-style penalty term for robust value estimation. By accounting for distribution shifts in the historical dataset, the proposed algorithm establishes near-optimal sample complexity guarantees under partial coverage and environmental uncertainty. An information-theoretic lower bound is developed to confirm the tightness of our algorithm's sample complexity, which is optimal regarding both state and action spaces. To the best of our knowledge, RTZ-VI-LCB is the first to attain this optimality, sets a new benchmark for offline RTZMGs, and is validated experimentally.

Sample-Eficient Tabular Self-Play for Offline Robust Reinforcement Learning
Na Li Zhejiang University nlee@zju. edu. en
Zewu Zheng The Chinese University of Hong Kong zhengzw@link. cuhk. edu. hk
Wei Ni
Edith Cowan University and University New South Wales wei ni www.iiiieee... org
Hangguan Shan Zhejiang University hshandzju. edu. en
Wenjie Zhang University of New South Wales wenjie zhwngounsw. edw...swwwedeeee................ au
Xinyu Li Huazhong University of Science and Technology iixinyuhhust. edu, cn
Abstract
Multi-agent reinforcement learning (MARL), as a thriving field, explores how multiple agents independently make decisions in a shared dynamic environment. Due to environmental uncertainties, policies in MARI. must remain robust tackle the sim-to-real gap. We focus on robust two-player zero-sum Markov games (TZMGs) in offline settings, specifically on tabular robust TZMGs (RTZMGs). We propose model-based algorithm (RTZ-VI-LCB) for offline RTZMGs, which is optimistic robust value iteration combined with data-driven Bernstein-style penalty term for robust value estimation. By accounting for distribution shifts the historical dataset, the proposed algorithm establishes near-optimal sample complexity guarantees under partial coverage and environmental uncertainty. An cormmation-thhorete lower bound is developed to confirm the tightness of our algo- rithm's 's sample complexity, which is optimal regarding both state and action spaces. To the best of our knowledge, RIZ-VI-LCB is the first to attain this optimality, sets new benchmark for offline RTZMGs, and is validated experimentally.
Introduction
Multi-agen multi-agent reinforcement learning (MARL), which focuses developing algorithms that enable multiple agents to learn and make decisions in dynamic environments, has garnered significant attention in gaming [35] and autonomous driving 4.. Offline MARL, addresses the high cost of interacting with the environment by leveraging historical data collected from past interactions generated under unknown biased behavior policies 22 The dynamic and non-stationary nature of real-world environments introduces critical uncertainties. Robustness becomes important in ensuring stable decision Decision-making, because standard MARL algorithms under ideal conditions are highly sensitive and prone to catastrophic failures when faced with even minor adversarial perturbations [48] 45). In this sense, robust guarantees are particularly vital in offline MARL,, highlighting the of offline robust MARI. Two-player zero-sum Markov games (TZMGs) represent a compelling setting of MARL, giving rise the field of robust TZMGs (RTZMGs) from robust MARL.
A key challenge in offline RTZMGs is addressing environmental uncertainties with as few samples as possible under partial and limited coverage. Historical data often only offers partial and limited coverage of the state-action space, leading to poor estimates of model parameters and unreliable policy. Besides, environmental uncertainties arise from model mismatches, system noise, and the disparity between simulation and real-world scenarios. To address uncertainties, RTZMGs incorporate
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table A comparison between RTZ-VI-LCB and PºMPO 55] on finding an e-
optimal robust Nash policy in finite-horizon offline RTZMGs with f(o o .H)
min (Ho - 1S) (Ho -1+(1-0 )a) } where the uncertainty set is quantified by to- [a+
tal variation (TV) distance. The sample complexities omit all logarithmic factors.
Algorithm
Sample complexity
Uncertainty level
P²MPP S
not considered
C. S flot H)
RTZ-VI-LCB (Ours)
full range min fat o S min fo 0 2
(A
Lower bound
C (A+ 2 min 0 .
Lower bound
equilibria not only between the two players but also with their advensarial strategies, considering worst-case environments selected from predefined uncertainty sets for each player.
Despite recent efforts 221 5 48 [9], there remains a fundamental gap in learning effectively in offline RTZMGs, primarily due to high sample complexity. For a tabular RTZMG (formal definition in Section 2) with horizon length H. states S, actions {A, B}. and uncertainty levels fott for the two players, the best sample complexity for e-optimal robust Nash equilibrium (NE) in the
offline setting to date is Ô S= achieved by P² (5), which demonstrates near-optimal sample complexity in H, S, and A, B, but overlooks the influence of uncertainty levels and faces the curse of multiagency [40]. Hence, the key research question addressed in this paper is
Can we design efficient algorithm for offline RTZMGs with partial state-action coverage while ensuring robustness to uncertainties?
1.1 Contribution
In this paper, we design novel model-based algorithm RTZ-VI-LCB for offline RTZMGs, which is an optimistic variant of robust value iteration. RTZ-VI-LCB involves a data-informed Bernstein-style penalty for robust value estimation to effectively capture the variance structure, and a two-stage subsampling method to suppress the statistical dependencies of the historical data. Notably, this is the first time that the optimal dependence of sample complexity on S and {A, B} and the best dependence on H has been achieved for offline RTZMGs. Table comppres the sample complexity between our approach and the status quo. The main contributions are outlined as follows.
(i) Robust unilateral clipped concentrability: With this new criterion, we define a measure C, E L) oo) for the quality of historical data. It captures the distribution shift hetween the hehavior policy (n", ,v") and the single optimal robust policies (H,v") and (μ", .2) under environmental uncertainty in the partial coverage, and offers a tighter measure of distribution mismatch than C, used in PºM [5]. The introduction of O improves sample complexity.
(ii) Near-optimal sample complexity upper bound: RTZ-VI-L can provably find an 8-optimal robust NE policy long as the sample size exceeds Ö
f(a [attoo, , .H) with independent burn-in cost. This significantly improves upon the prior art [3] on state S and action {A, and further delineates the impact of the uncertainty levels (at. ,
C S(A++) 8²
(iii) Information-theorele sample complexity lower bound: We establish a tight lower bound for RTZMGs, revealing at least Ω (C:SH(AA + B)/=²) samples are needed for an e-optimal robust NE policy under the uncertainty level min (at,o-) S +. and least a (C; + (e² min
samples are needed under min (a (ot,oo) 2 H. Com- paring these upper and lower bounds confirms the optimality of RTZ-VI-LCB w.r.t state $ and actions {A, B} in sample complexity across uncertainty levels.
(iv) Extension to multi-agent RL: We generalize RTZ-VI-LCB to Multi-RTZ-VI-LBB for ro- bust multi-player general-sum Markov games, and achieve an s-optimal robust NE policy for Ō HCHS 1 Ammin { {{H,, + +1- ( H) /e2) samples with M players,
A, actions, and uncertainty level o; per player.
2

---

1.2 Related Work
This section reviews a curated selection of related research focusing on provably tabular RL.
Finite-sample studies of standard TZMGs. Markov games (MGs), or stochastic games, were proposed in the early 1950s [32]. Then, extensive research has been conducted, and MARL has gained significant attention 30], particularly around Nash equilibrium 22 23 Numerous MARL algorithms with provable convergence and asymptotic guarantees have been developed [3I. More recent work has focused on creating algorithms for standard MARL with non-asymptotic guarantees through finite-sample analysis. In this area, most efforts to compute Nash equilibria are focused on TZMGs. The studies in [2] and [41] were the first to provide non-asymptotic sample complexity guarantees for model-based (e.g.. VI-Explore and VI-ULCB) and model-free algorithms (e.g.. OMNI- VT). Further improvements in sample complexity have been explored 10
13 26
Robustness in MARL. Although progress has been made in MARI,, existing algorithms may struggle when faced with environmental uncertainties, leading significantly deviated equilibria. MARL robustness against uncertainties has drawn attention different parts of MGs [38), includ- ing state [49] environment (reward and transition dynamics), agent types [47], and other agents' policies 20]. typical method to address robustness against uncertainties of the environment is
distributionally robust optimization (DRO), which is method predominantly explored in supervised learning B [4 6). The application of DRO to manage model uncertainty in single-agent RL [17] has attracted considerable attention. However, when extended to MARL, researchers formulated the problem as robust MGs armed with DRO and developed a relatively understudied field with only a Thus, relevant algorithms based on partial coverage of datasets while considering the uncertainty level are lacking.
few proved algorithms [5] 21
29
48 R4
Single-agent robust offline RL. In single-agent offline RL, addressing uncertainties of environ- ments using DRO such as robust Markov decision processes (MDPs) and distributionally robust dynamic programming-han attracted considerable interest in both theoretical research and practical applications [16]. Recent work has focused on the finite-sample performance of provable robust offline RL algorithms, exploring different divergence functions for uncertainty sets, various sampling mechanisms, and related challenges (5). It has been shown that addressing robust MDPs does not demand more samples compared with those needed for standard MDPs (33]. However, RTZMGs present additional complexities beyond those in robust single-agent offline RL.
DRO-such
2 Problem Formulation
This paper focuses on offline RIZMGs, which is a robust version of standard offline TZMGs by taking environmental uncertainties into consideration. RTZMGs form broader class than standard TZMGs, accommodating various prescribed environmental uncertainty sets. In RTZMGs, the dynamics extend standard TZMGs by incorporating two players, as well as their respective situations that determine the worst-case transitions. We investigate an efficient algorithm to achieve robustness and optimal sample complexity on state and actions (A, B} under partial coverage of the state-action space.
An RTZMG under the finite-horizon setting can be defined as MG, (PO), (S,,, u (PO) T. H. where S = {1....,Sh is the state space of size S; (1, A), == (1,.... .....,,, ,B)) denotes the action spaces of the max-player and the min-player with sizes A and B, respectively; H is the horizon length; r = [rx) represents the immediate reward obtained at time step h. Specifically, Th (s, a, b) is assumed to be deterministic on a state-action pair (s,a, a, b) and falls within the range [0. 1). This reward can represent both the gain of the max-player and the loss of the min-player. Here, ug (PO) and Ug (PO) represent the uncertainty sets for the max-player and min-player, respectively.
Unlike standard TZMGs that assume fixed transition kernel, these uncertainty sets account for bounded perturbations in the transition kernel and enable modeling of environmental uncertainties. These uncertainty sets are centered on a nominal kernel مD S x A x B + A(S), with their size and shape defined by distance metric P and radius parameters o > 0 and a > 0. Considering players' individual properties, both players can independently define their uncertainty sets Ug* (PD)
3

---

and Up (P"), by specifying different sizes (o+ > 0 and oー > 0) and potentially using distinct divergence functions (p) to shape these sets. For illustration convenience, we consider the same divergence function for both players in this paper.
Uncertainty set with two-player (s, a, b)-teaaanglllr According to the transition kernel un- certainty sets 4g" (P") and 4g (Po) defined above, we adapt the rectangularity condition to a two-player setting inspired by B3 termed wwo-player-wise (s, a, b) -reetanggulariyy The adapta- tion enhances computational tractability and facilitates the robust version of Bellman recursions. It permits each player to select its uncertainty set independently, which can be decomposed for each state-action pair into product of subsets. Thus, the uncertainty sets UØ (Po) and Ug (P") for the two players, adhering to two-player-wise a, () rectanguallr,,, are mathematically defined as
Ug (Pt) = =U (Ph ug (P*) : (Ph.s,a)):
where Up" (Ph.aas) = Pheaa E AA(S)
(Pnsab Ph Ph.ca..) S k @ represents the Carte-
sian product, and Up (P (Ph.a.o.)) can be defined similarly. We define a vector of the transition kernel P or po at any state-action pair (s, a, b) as
Ph.s,a.: == (- s, a, b) E RIXS,
Ph h,s,a,b := := (- s, E R RIxs.
(2)
Here, the distance function p for each player's uncertainty set can be selected from various options that quantify differences between probability vectors. These include f-divergences (e.g.. KL divergence,
TV distance, and chi-square) [44) the Wasserstein distance [4]. and lg norms (9.
Offline dataset. Let D be a dataset consisting of K episodes under independence, with each episode produced by implementing a behavior policy {ug thi in nominal MDP M (S, H1 pd = I (r For S k S K, the k-th episode
(sf, at, "t....,,ft, s/1 i U/g sk +1)) is generated as follows:
of 0", ~ (x,))1))) b ~ ( S/+1~~ P. s oh bl).
IshsH. (3)
Throughout this paper, e" denotes the initial distribution related to historical dataset. We use the short-hand notation for the occupancy distribution with respect to (w.r.t) the behavior policy (n", vn) as: V(,, 8, a, b) E [ x x A x B.
// (5) :P) = s/51 e² 1²: 2o, Po); N. (s, (s, P
(s) ()) s), (4)
which are simplified to d (s) df un (s) and dh (s,a,b)
S.P.P. (s,a, b). Similarly,
di
for any product policy (H, we define: v(h, s, a) E Н x x x Ax
de u. P (s) = Pss = s s| P,K,P) df (eei(sss,, (),a,b) = (s) () (n) (5)
Robust value functions. In RTZMGs, players seek optimize their worst-case performance across all possible transition kernels within their respective uncertainty sets u (19)) and Ug (PO). For any product policy (μ x v) E A(A x B), the max-player's worst-case performance time step h is measured with the robust value function h v(h, 8, a, b) [H] x S x Ax B, as given by
Vumot and the robust Q-function Qu
Vuinot (s) inf peup* (Po) VI V. (s),
Quinot (s,a,b) inf peup* (Po) QK.,P.
(6a)
V Vu.s0 (s) sup PEUF (Po) Vi. V...P (s),
Qui" (s,a,b) sup peug (Po) Q.R,P.
(6b)
where
V. =
Σ 11
Lmm re re(ss, alss,ae,
sh = =
h
P.u.P
QII (s, b), =
_ re( are be) =/== = s, an = a, by =
Σ r=h
P.u.P

---

Robust Bellman equations. Based on the robust value functions in 66. RTZMGs include a robust version of the Bellman equation, dubbed robust Bellman equation. The robust value functions
Vulso (8) for the max-player with any product policy (1, satisfy: v(h, 6) E [H]] x S.
h
(n,s,,,)) (c))
inf Peup" (P PV
(7)
Likewise, Vi (s) can be obtained for the min-player. Note that the robust Bellman equations are intrinsically connected to the two-player-wise (s, (s,a,Du reecanggallrit condition (see (I) applied to the uncertainty set. This condition separates the dependencies of uncertainty subsets among different time steps, the players, and state-action pairs, thus leading the Bellman recursion.
Optimal robust policy. Again, based on (6). we define the maximum robust value function of the max-player under the fixed opponent policy as: v(h, s) E [H] x S,
Vi.eo ma (
h
Vi (s) max x [| (AA) inf PEN: ! (PO) V.l.M, (s))
(s).
The maximum robust value function for the min-player can be obtained similarly.
As proved in (5] there is least one policy, denoted by (s) S [H] + A(A) (for the max- player) and (6) x [M] + ABB) (for the min-player), corresponding to the robust best-response
policy. These policies can simultancously achieve Vir V/ (s) (for the max-player) and Vi (s) (for the min-player) for all S and h E [H].
Robust Nash equilibrium. NE for RTZMGs. A product policy (μ, v) is considered robust NE if: v(s) E S
We introduce the robust variant of standard solution concepts- robust
Ve (s) Vi (s); V.i* (s) V,
h
(s).
(8)
robust NE signifies that given the product policy (n, v) of the opponents, no player can enhance their outcome by deviating from their current policy unilaterally when each player accounts for the worst-case scenario within their uncertainty set Ug (P") or Ug"" (Pt).
Since finding exact robust equilibria can be complex and may not always be feasible, practitioners often seek approximate equilibria. In this context, product policy (p v) A(A B) can be termed an s-robust NE if
Gap(u,v) = max VV Vitiio
(0) Vi (e), ViLoO (0) - Viuit o (0)) SE
(9)
where
Vi ViLiM (0) Egng VianeVViiee Viaio (8); Vit0* (0)= Vitoo (s).
The definitions of V (g) and Vi (e) can obtained similarly. The existence of a robust NE has been proved for general divergence functions in the uncertainty set in 55)
Our Goal With a dataset collected from the nominal environment, our objective is find solution yielding an s-robust NE for RTZMG w.r.t. specified uncertainty set U(P)) around the nominal kernel, minimizing the number of samples required under partial coverage of the state-action space.
3 Algorithm Design
In this section, we propose an efficient model-based algorithm, RTZ-VI-LCB, to learn a robust NE policy. Notably, RTZ-VI-LCB achieves near-optimal sample complexity with robustness, which is designed for offline RTZMGs within the fnite-horizon setting.
3.1 Building an Empirical Nominal MDP
According to the empirical frequencies of state transitions, we can construct an empirical estimate Po ( of pD, where V(h, s, a, b,) E [I]] x S Ax S EN, 1f (x.o.b),"))
( = {
if N2 (s, a, b) 0; if N₁ (s, a, =0,
Nals.a.0
(10)
1/S,
5

---

rh (s, (s,
N (s, a, b) 0:
Fh (s,
(11)
if NA (s, a, 0, where (M,5, a, b) represents the total number of sample transitions from (s, b) step h, and
(0
1((8,, as b,) = (s, a. b)}. (s, as a) > .V
(12)
Although it is feasible to decompose the historical dataset D into sample transitions, the dependencies between transitions within the same episode introduce significant complexities the analysis.
Algorithm Two- stage subsampling for RTZ-VI-LCB.
input Dataset D, probability ò.
1: Step 1: Data Partitioning. Split D into two equal-sized subsets, Dm and D*, each containing //2 trajectories.
2: Step 2: Defining Transition Bounds. For step h and state denote the number of transitions
from Dm (resp. Da) as No (s) (resp. (s).)). Construct the trimmed count as:
HS
(*) max (N)(s) 10 Ng(s) log 8. }
(13)
3: Step 3: Generating Subsampled Dataset. Randomly sample transitions (quadruples of the form (8, a, b, h, s')) from Dm uniformly. For each (s, E S x [H], include min(NN NT(()) transitions in the new dataset D output Set Do- = D
Inspired by 24 we design a new two-stage subsampling method for RTZMGs, as shown in Algorithm 1 This method effectively reduces statistical dependencies, resulting in distributionally equivalent dataset Do composed of independent samples. The property of Do is summarized in the following lemma and formally proved Appendix
Lemma 3.1. The dataset produced by the two-stage subsampling method is distributionally identical to Do with probability of at least 1- -6, where (N (s, a, b)} are independent of the sample transitions in DO and obey: s,,,b,
[
x x A B.
Na(s,a,)2 Kd ())
KH
5% K Kdggb.
(14)
By applying the two-fold sampling method, treat the dataset Do as having independent samples, simplifying the analysis significantly as supported by Lemma 3.1
3.2 Optimistic Variant of Robust Value Iteration with Lower Confidence Bounds
We propose a model-based algorithm, RTZ-VI-LCB, for solving RTZMGs using an approximate So for Pd) which is the nominal transition kernel. Specifically, we introduce value iteration with lower confidence bounds for RTZMGs to compute a robust NE for two players, along with a data-informed penalty, summarized in Algorithm
Our algorithm begins at the final time step h = and proceeds backward through h = H 1, 2. 1. Following from single-agent offline RL algorithms [9] design optimistic robust Q-value for all (h, s, a, b) E H] x S Ax B as
T (s, = min { (s, a, b) + inf peu
PV.t. h+l + 3n (s, Pitt1 1...)). .1 {): (15a)
θ (8,a,b) max (Th (s, b) + suppeu (Pn...)) PV h+1 - Bn (s,u,d, phtt 0). (15b)
to estimate the robust Q-function at time step h E [H] as Q7, and θ
Dual problem. Solving (15) directly is computationally intensive because it requires optimizing over S-dimensional probability simplex, which becomes exponentially more difficult the state

---

space size S innrreses. Fortunately, strong duality for TV distance allows us to tackle this problem by solving its dual [7
inf PEllo (Pha.a.))
PV A+1
max aE(min A-1 max V.t
po
h.aaa [ -o* (a-min Vittal (s))} (16)
where
V h+1]
denotes the clipped versions of V E R$ based on some level 2 0. as follows.
(s) = Sa. =
(s) > a;
1i h++
V (
(17)
otherwise.
Moreover, suur (PR. PV can be defined similarly. See Appendix for details.
Penalty term. We design data-driven penalty term, (s,, a, V), to account for uncertainty in value estimates, resulting in an optimistic robust Q-function estimate. To achieve this, we utilize a Bernstein-style penalty, which effectively captures the variance structure over time (24). In partieular, for any (s, b, E ESEEXA
[H] and 8 E (0, 1). the penalty term 3x a, b, V) defined as
Bn (s.a,b.i) min max {
KH On log of Var
20, log KH 5 Nn (s, a.
}
{V
Pa (V)
{ (.H..
(18)
Nn (s, a)
where C, is some universal constant, and
Var po hea.a.a
(v)= = 5O b
12 (Po b.s.a,b D)).
(19)
Note that we choose po0 in the variance term Var Biria,b (V). as opposed to po, since we have no access to the true transition kernel pd, The penalty term Br 8s b, V is crafted to address the unique structure of RTZMGs, distinguishing it from the penalty terms used in standard offline TZMGs [10 24). In particular, it provides tight upper bound on statistical uncertainty, considers the non- linear and implicit dependency introduced by the uncertainty set (PP),, and addresses challenges not present in standard MDPs.
Policy estimation. We update the policies using the estimated Q- Q-functions with uncertainty, as described in line 5 of Algorithm 2 For any matrix N RAxB the function ComputNash(N) (N) returns a solution (w, 2) to the minimax problem maX minge w Nz I... In other words, for each S, compute the NE policies (H, (s), (s)) and (Ny (s), Mn (s)) E A(A) x A(B) for the robust zero-sum matrix games with payoff matrices Q (s.:.)) and Q (s, -) :), respectively. Solving robust zero-sum matrix games is generally PPAD-hard as the players can potentially choose different worst-case transition kernels.
Performance Guarantees
We provide the theoretical guarantee of RTZ-VI-LCB, including the upper and lower bounds of sample complexity. We also validate the theoretical guarantee through numerical experiments; Appendix
Robust unilateral clipped concentrability. For offline RTZMGs, it is essential to measure the distributional discrepancy between the historical data and the target data. Drawing on the single-policy clipped concentrability in the single-agent RL (44], we propose novel criterion, robust unilateral clipped concentrabilify, to measure the distributional discrepancy for RTZMGs:

---

Algorithm 2 Value iteration with lower confidence bounds for RTZMGs (RTZ-VI-LCB)
1: Initialization: Set uncertainty levels o- and o+; set V (+) 0 and (s) H for all (s,h)
(s, S [H + I]; set Q7 (s, a, b) 0 and (7, a, b) H for all (s, a, b, h) E S Ax B [H 1..
2: Compute the empirical reward function F with and empirical transition kernel Po with 10
3: for h = H, 1,, ...... do
4: Update the robust Q-value estimate as 15 with 3n (s, a, b, V) defined in 18
5: Compute Nash policy for each s E as
(H (s) 2 (s)) ComputNash (श (8,
(14 (8); U/ (8) ComputNash
@ (8, ;
6: Update the robust value estimate for each s as
(s) Bann, (o),bwn, (0) @ (s, a, b) V (s) E Banuy (s), (0) @ (s, a.]
7: end for output The policy pair (7t, D), where 7t = {14 M and &- = (1st )
Definition 4.1 (Robust unilateral clipped concentrability). We define C E [STA=E, oo) as the smallest value that satisfies
min {dh Laree (s, s(A+A))
max
sup
p (s, (s,
(Po)
min {dh M. (s, b), S(A+B)
sup
S S (20)
(Po)
for the behavior policies of the historical dataset 'D satisfies, and refer to it as the robust unilateral clipped concentrability coefficient. For consistency, we define the convention "0/0=
-P(ss a, or di (s, a, b) is larger than 1/(S(A+ + B)), the robust unilateral Notably, if d
clipped concentrability assumption does not require the data distribution P (s, a, b) to scale with dl.p". P (s, a, b) or d' P o, b) proportionally. Estimating the concentrability coefficient Cf from offline data is generally information-thhorettcaal impossible, as demonstrated even in the single-agent case by the example construction in Section 3.4 of (24). Fortunately, this does not affect the execution of our algorithm.
Next, outline the principal theoretical findings concerning the sample complexity of learning robust NE in RTZMGs, including an upper bound for RTZ-VI-LCB (Algorithm and an information- theoretic lower bound. We start with the finite-sample guarantee for RTZ-VI-LCD. with the proof
provided in Appendix D
Theorem 4.2 (Upper bound for RTZ-VI-LCB). Under the TV uncertainty set u (-) und (-)
defined in 2 with o+,, o E (0, 1), define d minh,s.. {dg (s, b) ds, b) > 0}, and ler
fla = min {(Ho+ - 1 (1 o () (Ho -1 (1 (1- - ) )/
) )200)2220 H}. Con-
sider any E (0, 1) and any RTZMG MG, = {S, A, B, u (P*), r, H}. For sufficient large constants co C1 > 0, with probability of at least 1 ò,
achieve
C; C3SA + B) log KH 5
Gap(ā, S on
f(0 (00t,0-111
(21)
K
with the total number of samples T exceeding
H2S(A
KH
T KH 2 cp
log
fla .0
(22)
dn
8

---

Remark 4.3, Under generative model with uniform sampling, the visitation distribution becomes
explicit; that is, d (s, a, b) = SAB- In this case, it is sufficient to choose C; min (A, B}. which can be readily verified to satisfy Eq. (20). This choice leads to the sample complexity
δ (( [HSAB =foot .H)) which matches the bound established in S4 and confirms the effi-
ciency of our approach in the generative model setting.
We derive an information-theorehe lower bound of sample complexity, with its proof in Appendix B
Theorem 4,4 (Lower bound for RTZMGs). Consider any tuple MG, > 16 16 2 and o+, o E (0, col with
{S. AS,A B (P r,"),,,Ht H} obeying
any small efficiently positive constant < co S ... Let
o 2H H if max {ot, } S
E
(23)
1,
otherwise,
for any 02 S With initial state distribution Q. we can construct set of RTZMGs { {Milf
F {0, 1,... SA 13. o = [oNlISHSH & S (0,1) For any dataset with K independent sample trajectories of length H per trajectory satisfying C S O I 2C, we have { Gap((A 2) > E) 2 1/8,
inf max N. (f+))Fxt
(24)
provided that
T= CCH + B) min minn o Y
(25)
Here, e is an efficiently small constant. The infimum is obtained over all estimators (7t, D).
These theorems offer the following key implications:
(i) Theorem 4.2 demonstrates that the proposed RTZ-VI-LCB algorithm can attain E-robust NE solution when sample size exceeds C (IA+)
,(ot,o-, ,)). suggesting that the sample efficiency for robust offline TZMGs is strongly influenced by the dataset quality (quantified by C;)) and problem structure of RTZMGs (reflected in the occupancy distributions dz,). If Cf is as small as STA+B] the upper bound of the sample complexity exhibits a weaker dependency on actions {A. }} and state S. Combining this upper bound with the lower bound in Theorem shows that RTZ-VI-LCB' s sample complexity is optimal w.r.t. key factors S, A, B and E. This is the first optimal sample complexity upper bound for offline RTZMGs, regarding state S and actions {A,
ex
(ii) Theorem 4.4 conveys
important points. When the uncertainty level is small (i.e., )), no algorithm can find an s-optimal robust policy with fewer than C samples for all offline RTZMGs, matching the complexity requirement for non- Ω
min o
2²
robust offline TZMGs [18. This implies that robust TZMGs are at least as challenging as standard TZMGs for low uncertainty. When the uncertainty level satisfies min(ot, , Z H. algorithm
can find an e-optimal robust policy with the numbers of samples fewer than Ω C (A+())))))
min(al,a To
this end, RTZ-VI-LCB is the first provably optimal algorithm on S and (A, B) for RTZMGs without requiring full coverage assumptions.
Moreover, our algorithm can be extended to multi-player general-sum MGs with m players and A actions and uncertainty level o; per player; see Appendix [F] We can obtain the following theoretical guarantee for this extended algorithm, named Multi-RTZ-VI-LCB::
Theorem 4.5 (Upper bound for Multi-RTZ-VI-LCBB multi-player general-sun -um MGs MG, MMSS, (A,, ) H, H (P") )m
Consider any 8 (0. and any robust
{m Under the TV uncertainty set (-) defined in (2) with o; E (0, 1] for = 1,2, ... m. Define d
ming.s.a (s, a): df, a) > 0}, and f(lo,) H) = min [Ho i=1
(o.)
For sufficient large constants co, C1 0, with probability of at least 6, we can achieve
C: 2m A, KH
Gap(T) < 01
log
[((a,)m H), 8
K

---

with the total number of samples T exceeding
H2 m A
KH log
T-KH
f((o)) II).
(26)
dm
Theorem 4.5
demonstrates that RI-It--RTZ-V--LCE can attain e-robust NE solution when the Di=
sample size exceeds O
C. H
A;
f((a;) H)). breaking the curse of multiagency.
5 Numerical Experiments
To effectively evaluate our algorithm, we have conducted numerical experiments on randomly generated transition kernels, following the code proposed by [39]. In particular, we adopt the parameter setting as $ = 50, A = B = 2, and H 100, averaged over 100 seeds. Experiments are conducted on PyTorch 2.0.0 with a single NVIDIA RTX 4090 24GB GPU. In our experiments, the robust NE at each state and timestep is computed using standard NE solvers, i.e., the Python package nashpy. Our algorithm compatible with any exact or approximate NE solver, including computational relaxations or sampling based methods.
As shown in Figure (a) the case of K 148 x e² demonstrates that proposed algorithm consistently outperforms the baseline value iteration for robust TZMGs (RTZ-VI) across all states and all sample sizes. This trend remains consistent across other values of K well. Moreover,
have plotted the sub-optimality performance gap of RTZ-VI-LCCH w.r.t. the sample size on a log-log scale corroborate the scaling of the sample size the performance gap. Fitting using linear regression leads to a slope estimate of -0.487. This nicely matches the finding of our theoretical guarantee.
ITALL Parn
V- (3) ye [g]]
lo
Index states
Sample size
loglsample size
(a) Value gap versus states
(b) Value gap versus sample size
(c) Value gap dependency w.r.t. K
Figure 1: The performances of RIZ-VI-LCB and RTZ-VI in the stochastic TZMG problem.
6 Conclusion
In this paper, we design an efficient robust model-based algorithm for offline RTZMGs, which is value iteration with lower confidence bounds for RTZMGs. Our algorithm integrates robust value iteration with the principle of pessimism. By imposing tailored assumption (robust unilateral clipped concentrability) on the historical dataset to account for the distribution shift, we address robustness in the worse-case scenario of the shared environment, analyze the finite-sample complexity of the proposed RTZ-VI-LCB algorithm, and establish an information-theoredd lower bound to evaluate its optimality across various uncertainty levels. To the best of our knowledge, this the first provably optimal algorithm for offline RTZMGs that addresses the dependency states S and actions {A, B). while accounting for model perturbations and partial coverage. Furthermore, we extend RTZ-VI-LCB to multi-agent general-sum MGs, demonstrating a breakthrough in breaking the curse of multiagency.
This paper presents work whose goal is to advance the field of Reinforcement Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Broader Impacts
10

---

Acknowledgements
The work was supported in part by the National Natural Science Foundation of China (NSFC) under Grants U2IB2029, 62531019, and U21A20456; in part by the Zhejiang Provincial Natural Science Foundation of China under Grant LR23F010006, and in part by a Nokia Donation Project. The work of Na Li was supported by the China Scholarship Council.
References
[1] Alekh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with a generative model is minimax optimal. In Conference Learning Theory, pages 67-83. PMLR, 2020.
[2] Yu Bai and Chi Jin. Provable self-play algorithms for competitive reinforcement learning. In International conference machine learning, pages 551-560. PMLR, 2020.
[3] Dimitris Bertsimas, Vishal Gupta, and Nathan Kallus. Data-driven robust optimization. Mathe- matical Programming, (67:235-292, 2018.
[4] Sushrut Bhalla, Sriram Ganapathi Subramanian, and Mark Crowley. Deep multi agent rein- forcement learning for autonomous driving. In Canadian Conference on Artificial Intelligence, pages 67-78. Springer, 2020.
[5] Jose Blanchet, Miao Lu, Tong Zhang, and Han Zhong. Double pessimism is provably efficient for distributionally robust offline reinforcement learning: Generic algorithm and robust partial coverage. Advances in Neural Information Processing Systems, 36, 2024.
[6] Jose Blanchet and Karthyek Murthy. Quantifying distributional model risk via optimal transport. Mathematics of Operations Research, 44(2):565-600, 2019.
[7] Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma. et al. Spectral methods for data science: A statistical perspective. Foundations and Trends in Machine Learning, 14(5):566-8066 2021.
[8] Zixiang Chen, Dongruo Zhou, and Quanquan Gu. Almost optimal algorithms for two-player zero-sum linear mixture Markov games. In International Conference on Algorithmic Learning Theory, pages 227-261. PMLR, 2022.
[9] Pierre Clavier, Erwan Le Pennec, and Matthieu Geist. Towards minimax optimality of model- based robust reinforcement learning. arXiv preprint 2rXiv:2302.05372 2023.
[10] Qiwen Cui, Kaiqing Zhang, and Simon Du. Breaking the curse of multiagents in large state space: RI in markov games with independent linear function approximation. In The Thirty Sixth Annual Conference on Learning Theory, pages 2651-2652. PMLR, 2023.
[11] Constantinos Daskalakis. On the complexity of approximating a nash equilibrium. ACM Transactions on Algorithms (TALG), 933):1335, 2013.
[12] John C Duchi. Introductory lectures on stochastic optimization. The mathematics of data, 25:99-186, 186, 2018
[13] Songtao Feng, Ming Yin, Yu-Xiang Wang. Jing Yang, and Yingbin Liang. Model-free algorithm with improved sample efficiency for zero-sum markov games, 2023.
[14] Rui Gao. Finite-sample guarantees for Wasserstein distributionally robust optimization: Break- ing the curse of dimensionality. Operations Research, 71(6):221--2000 2023.
[15] Edgar Gilbert. comparison signalling alphabets. The Bell system technical journal, 5122:500-- 1952.
[16] Vineet Goyal and Julien Grand-Clement. Robust markov decision processes: Beyond rectangu- larity. Mathematics of Operations Research, 48(1):203-226, 2023.
[17] Garud N Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2):257-280, 2005.

---

[18] Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu. V-learning simple, efficient, decentralized algorithm for multiagent RL. In ICLR 2022 Workshop on Gamification and Multiagent Solutions, 2022.
[19] Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline RL? In International Conference on Machine Learning. pages 5084-5090 PMLR, 2021.
[20] Shyam Sundar Kannan, Vishnunandan LN Venkatesh, and Byung-Cheol Min. Smart-llm: Smart multi-agent robot task planning using large language models. arXiv preprint arXiv:2309.10066 2023.
[21] Erim Kardeş, Fernando Ordóñez, and Randolph W Hall. Discounted robust stochastic games and an application to queueing control. Operations research, 59(2):365-382, 2011.
[22] Nathan Lambert, Markus Wulfmeier, William Whitney, Arunkumar Byravan, Michael Bloesch, Vibhavari Dasagi, Tim Hertweck, and Martin Riedmiller. The challenges of exploration for offline reinforcement learning. arXiv preprini arXiv:2201.11800 2022.
[23] Chung- Wein Lee, Haipeng Luo, Chen- Yu Wei, and Mengxiao Zhang. Linear last-iterate conver- gence for matrix games and stochastic games. arXiv preprint arXiv:2006.095: 2020.
[24] Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi, and Yuting Wei. Settling the sample complexity of model-based offline reinforcement learning. The Annals of Statistics, 52(1):233 2600 2024.
[25] Gen Li, Yuting Wei, Yuejie Chi, and Yuxin Chen. Breaking the sample size barrier model- based reinforcement learning with generative model. Operations Research, 72(1):203-221, 2024.
[26] Na Li, Yuchen Jiao, Hangguan Shan, and Shefeng Yan. Provable memory efficient self-play algorithm for model-free reinforcement learning. In The Twelfth International Conference on Learning Representations, 2024.
[27] Michael L Littman. Markov games as a framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pages 157-163. Elsevier, 1994.
[28] Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. A sharp analysis of model-basee reinforce- ment learning with self-play. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning. volume 139 of Proceedings of Machine Learning Research, pages 7001-7010. PMLR, July 2021.
[29] Shaocong Ma. Ziyi Chen, Shaofeng Zou, and Yi Zhou. Decentralized robust v-learning for solving markov games with model uncertainty. Journal of Machine Learning Research, 24(371):1-40, 2023.
[30] Afshin Oroojlooy and Davood Hajinezhad. A review of cooperative multi-agent deep reinforce- ment learning. Applied Intelligence, 53(11)213677-13722, 2023.
[31] Tabish Rashid, Gregory Farquhar, Bei Peng, and Shimon Whiteson. Weighted qmix: Expanding monotonic value function factorisation for deep multi-agent reinforcement learning. Advances in newral information processing systems, 13:10999100200, 2020.
[32] Lloyd S Shapley. Stochastic games. Proceedings of the National Academy of Sciences, 39(10):1095- 1953.
[33] Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, Matthieu Geist, and Yuejic Chi. The curious price of distributional robustness in reinforcement learning with a generative model. Advances in Neural Information Processing Systems, 36, 2024.
[34] Laixi Shi, Eric Mazumdar, Yuejie Chi, and Adam Wierman. Sample-efficient robust multi-agent reinforcement learning in the face environmental uncertainty. In Forty-first International Conference Machine Learning. 2024.
[35] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, al. Mastering the game of go without human knowledge. Nature, 550(7676):354359, 2017.
12

---

[36] Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer Publishing Company, Incorporated, 1st edition, 2008
[37] Roman Vershynin. /ligh-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[38] Daniel Vial, Sanjay Shakkottai, and R Srikant. Robust multi-agent bandits undirected graphs. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 6(3):1- 57, 2022.
[39] Antony Vijesh et al. A multi-step minimax q-learning algorithm for two-player zero-sum markov games. arXiv preprint arXiv:2407.042400 2024.
[40] Yuanhao Wang. Qinghua Liu, Yu Bai, and Chi Jin. Breaking the curse of multiagency: Provably efficient decentralized multi-agent with function approximation. In The Thirty Sixth Annual Conference Learning Theoor, pages 2798-2848. PMLR, 2023.
[41] Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang. Learning zero-sum iamultancuus-oov Markov games using function approximation and correlated equilibrium. Math. Oper. Res., 48(1):433 462, Jun. 2022.
[42] Zaiyan Xu, Kishan Panaganti, and Dileep Kalathil. Improved sample complexity bounds for distributionally robust reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 9728-9754. PMLR, 2023.
[43] Yuling Yan, Gen Li, Yuxin Chen, and Jianqing Fan. Model-based reinforcement learning for offline zero-sum markov games. Operations Research, 2024.
[44] Wenhao Yang, Liangyu Zhang, and Zhihua Zhang. Toward theoretical understandings of robust markov decision processes: Sample complexity and asymptotics. The Annals of Statistics, 3066):3223-3248, 2022.
[45] Christopher Ych, Chenlin Meng. Sherrie Wang, Anne Driscoll, Erik Rozi, Patrick Liu, Ji- hyeon Lee, Marshall Burke, David B Lobell, and Stefano Ermon. Sustainbench: Benchmarks for monitoring the sustainable development goals with machine learning. arXiv preprint arXiv:2111.04722, 2021.
[46] Lanting Zeng, Dawei Qiu, and Mingyang Sun. Resilience enhancement of multi-agent reinforce- ment Bearning-based demand response against adversarial attacks. Applied Energy, 324:1 19688, 2022.
[47] Huan Zhang, Hongge Chen, Duane S Boning, and Cho-Jui Hsieh. Robust reinforcement learning on state observations with learned optimal adversary. International Conference on Learning Representations, 2021.
[48] Kaiqing Zhang. Tao Sun, Yunzhe Tao, Sahika Gene, Sunil Mallya, and Tamer Basar. Robust multi-agent reinforcement learning with model uncertainty. Advances in neural information processing systems, 33:10571- 2020.
[49] Ziyuan Zhou and Guanjun Liu. Robustness testing for multi-agent reinforcement learning: State perturbations on critical agents. arXiv preprint 2306:2306006/33 2023.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction precisely reflect the contribution and scope of this paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of work in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Justification:
We explicitly list all key Theorems in Section and provide complete proofs in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
We provide detailed illustration of our proposed algorithm in the Appendix A
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

Answer: [Yes]
Justification:
Code is available at
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ //ippe.cc/pullic/uuiii wwwpc//ggue////eeeeeoooc CoodeSubeiiie ssi asionnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide full details in Appendix A
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We report the average results across 100 seeds with standard deviations.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
16

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We point out the specific compute resources in Appendix
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
Our paper obeys the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: There is no societal impact of the work performed since this work focuses on theoretical analysis.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We respect the Licenses for existing assets that use.
Guidelines:
The answer NA means that the paper does
existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: We will release new assets proposed in paper once the paper is accepted.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/cooe/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
19

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: This paper does not LLM to impact the methodology, scientific rigorousness, or originality of the research.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
20

---

Contents
Introduction
1.1
Contribution
1.2
Related Work
Problem Formulation
3
Algorithm Design
3.1
Building an Empirical Nominal MDP
3.2
Optimistic Variant of Robust Value Iteration with Lower Confidence Bounds
4
Performance Guarantees
5
Numerical Experiments
10
Conclusion
10
Numerical Experiments
23
Preliminaries
23
B.1 Dual equivalence of robust Bellman
23
B.2 Facts of RTZMGs and empirical RIZMGS
23
Proof of Lemmal 3.1
24
Independence property
24
Proof of (8) No
25
Proof of (38).
27
D Proof of Theorem 4.2
27
D.I Step 1: Decoupling statistical dependency
27
D.2 Step Decomposing the error Gap(a,
28
D.3 Step 3: Summing up
36
Proof of Theorem44.44
36
Step Constructing a family of hard Markov game instances
36
E,2 Step 2: Establishing the minimax lower bound
39
Multiplayer General-sum Markoy Games
43
Problem formulation
43
Muli-RRIZ-VI..CBB
44
F3
Analysis of Multi-ME-Nash- QL
45
Proofs of lemmas for Theorem 4.2
51
Proof of Lemma D
51
21

---

G.2
Proof of Lemma D.2
54
Proof of Lemma D.3
54
Proof of Lemma
55
Proof for Theorem|44
58
Proof of Lemma
58
H.2
Proof of (105)
60
H.3
Proof of (107)
61
H.4
Proof of (112)
62
22

---

A Numerical Experiments
log( H
6
7
9
RTZ-VI-LCB
3,1699
2.1498
0.2324
0.0819
PO 3.5970
2.2503
0.2404
0.0890
These results highlight the superiority our method across varying dataset sizes and validate the theoretical claims under controlled experimental conditions. While we focus on tabular settings in this work, our algorithm can serve as a theoretical foundation for scalable extensions based on linear or kernel-based function approximation.
B Preliminaries
In this appendix, we introduce the dual equivalence robust Bellman operators and key facts about RTZMGs and their empirical counterparts, laying the foundation for our theoretical analysis.
B.1 Dual equivalence of robust Bellman
We can compute the robust Bellman operator by solving its dual formulation rather than the original form, long the predefined uncertainty set is in benign form (e.g., utilizing TV distance as the divergence function) 17 33). Taking TV distance as an example, we describe the equivalence under strong duality between the robust Bellman operator and its dual form Lemma B.I
Lemma B.1. Consider any TV uncertainty set (P) and (P) associated with fixed uncertainty levels ot, a E (0, 1] and any probability vector P A(S). For any vector V R obeying
V 2 0, one has
max oE [min, max, V(+) (IV a (a (a-min [Vl (8'))
inf
PV
(27a)
Pell (P)
PIV 0 (a-max max [V] (s }
sup PV
min
(27b)
PEU=-(P (P)
aElmin, max,,ax V(8)
where [V]a is defined in
Lemma B.T can be proved similarly to Lemma 4.3 [7]. Compared the standard Bellman operator,
this lemma guarantees that no additional computing cost is required when applying the robust Bellman operator.
B.2 Facts of RTZMGs and empirical RTZMGs
Recall the definition of any RTZMG MG, = (S,A, (P"), (Pº), r,)),,H) H}. According to robust Bellman equations in (7), one has: for any product policy (),v) and any (h, s, a, b)
[M] x S x Ax
Qua (s,0,b) = rn(,,,,b)
inf peug (pR.
PVP.v.** Pi11
(28a)
Qu:a (s,0, = (n(,,,,))
sup pEU (
PVALa
(28b)
where
Vu.u.ot
(8) = Earppa bren)))))))
Quuirt (s,a,b)
h
Va
(8) Barpan (s),bwen(()
Qu (s,a,b)
Considering the offline setting, we use MG, B, (P (P"), .1} to represent the empirical RTZMG, which is established along with the estimated nominal distribution po
23

---

in 10 Therefore, for any product policy (1, we define the empirical robust value function (resp. empirical robust Q-function) in MG, as Piuno and Viuu (resp. 1% and @% ) which analogous to (6). Moreover, we can similarly define the optimal empirical robust value function for both players over MMg Vs E,
An
max D (s) Vil p.o"* (s) 1 ((A)
Vh
max 5u [ PEtfot (Pu)
inf (iiie((s) (s);
h
(29a)
Vitiiti (s) = Vil o
(s) =
max v (B)
V.u (8)
max x=S PELL" (Pa)
inf
V.u (s).
(29b)
Notably, for all 8, there exists at least one robust best-response policy that achieve Vi and A V.a.t. (s), proved in [5). Therefore, we can obtain the empirical robust Bellman equation similar to as: for any product policy (H,,V),
Quanot (s, = rr((8, b)),
inf PEup (PR.
Piunot h+11
(30a)
Q (s, = b)) +
sup PEUg (Po (Ph.....)
Piruo 1+11
(30b)
where
Vuliot (s) Parpp (e) (e) Qu (8, (9,a,b)]: b)]:
Vuueo (s) (Ea-p (01) as,a,b))
C Proof of Lemma 3.1
C.1 Independence property
Let us examine two distinct data-generation mechanisms, where a sample transition quadruple (s, a, b, h, s') represents transition from state with actions (a, to state s' at step h.
Step 1: Creating D based on D'. To construct the augmented dataset Dr for each (s, h) e S x (H). we first include all (s) sample transitions in 2' originating from state at step h in Di.a, If (s) > (s),, we supplement Di.a with additional [N%(s) - -NT independent sample
transitions {s,, hhor Whe h 8h,
(1)
(1) }. follows:
lid. ag.s
fid. (b(()s), (-1ss)) Ubss
(1) lid.
( Pa 1s, anss (2)
(T) <i (s).
Step 2: Constructing Diid, For each (s, E x [H], we generate (s) independent sample transitions {ss, h (6) h, s ((0)) }. follows:
(1) L.d. (1s),,
l.d. ()()s),,
M.d. pa (1) isig Ni(s).
h,s
h,s
The resulting dataset is defined as:
Did = (0, a ( 12
10
| H, s 3.)
Establishing independence property. The dataset Dita deviates from Dt only if N3(s) > (s). This augmentation ensures that a contains precisely (s) sample transitions from state s at step h. Both D and Dild comprise exactly (s) sample transitions from state s at step h. with (s)) being statistically independent of random sample generation. Consequently, given (+), the sample transitions in Di.a across different steps are statistically independent. As a result, both Dt and Dild can be regarded as collections of independent samples.
24

---

C.2
Proof of (s) I (s)
Since D is generated by half of the sample trajectories line 2 in Algorithm
we have
(R(s)
E
=) S,
k=K/2-1
Thus, we can view (s) the sum of K/2 independent Bernoulli random variables with mean di 10 (s). According to the Bernstein inequality and the union bound, we derive
P 3(s :
K v² (s) 2 No
Na(s)
d
2
E xES,hEiH)
P NE((s)
K
die
vv
(s) 2 No.
2
N
<2HS (NN.. + No/3
ANo 0,
where
K Var (1)) =]] Kd (s) oh (s) Kilf (8)
Nr.s
2
Therefore, with probability of at least 1 - 28, we have that: Vs E S and A1 S h S H,
(R(s) dh 0" (s)
SVAN,, log
HS
+
2
log
HS
S 22Kd (s)
(()) log
HS
+ log
HS
8
3
8
5
5
(31)
Since Dm and D are generated in the same way, we obtain that with probability exceeding - 28,
(s)
K
dh
n (s)
2kd v (s) log 8
HS
+ log
HS Vs
(32)
8
By combining (31 and 32 it follows that
HS HS (N] - ()()) 2 2K dr 10 (s) log
2og
8 Ys E 5, H. (33)
Now, we prove (s) N [)] by considering two cases, In the first case, ( < 100 log Hs According to the definition in
13 we obtain
HS (s)s) max Ng(ss) 10 NR(s) log
0 0
= 0 =
(34)
8
HS In the second case, (*(s) > 100 10g
From 31
follows that
5
K
d
0 (s) + v 2 2K
" " (s) log
HS
+ log
HS > NH(ss,
2
8
which leads to
HS
HS 8
K d " (s) 2 (9 log
> 100
log
(35)
8
By substituting (35 into
we obtain
K
HS log
HS
K
(+.()) 2
g h
(s) 1/ 2Kd 10 (s) log
n
(s).
(36)
2
h
25

---

Consequently, in the case of (g(s) > 100 log # we have
HS
(s) = max (s)(s 10 No log
0
HS
= NN(()) 1 (R(6) log 5
HS
S (E(s) 5V Kdh (s) log 8
2//2 2K M (8) log
HS
+ 2 log
HS
(i))
(+),
(37)
where (i) holds under condition (36.. (ii) holds under the condition 35 and (iii) comes from the
inequality (33 with probability of least 25.
Combining and (37). we establish (s) & (s). As proved in Appendix C.3
we have: V(s, a, b, ES X Ax [H], with probability exceeding
1 26.
KH 8
KH
MMss, a,
s))R(b] log
log
(38)
Employing the fact (8) S (s) and 38 we can prove 14 in two cases, i.e, Kdd 20 (s, a ())
160 KH and Kd ./ (8, , 1600 log o
K" 8
In the case K Kdd (s.a) & 1600 log KH 8
we can readily obtain
hh n² (s) -0- 5v Kdt log
KH
SOS (s.
(39)
In the case of Ka . (s. Kall (s))2((a 8) > 1600 log we obtain
NR(s) 2 dx v" (s) 400 log
K
KH
(40)
4
which can derived following the same line of 36 Then, 40 and the definition of N7((s) together yield
KH (g(() log
(s)s 2 (s) 10
- nh //¹ (s) 10
K
dle
yun 1n (s)log
KH
K (s).
8 h
As a consequent,
K
" s)bR(b|s)
(41)
8
K
n (s, (s, b) 2 200 log
KH
(42)
8
where the last inequality holds under the assumption of the second case. Combining (4) with yields
38
b) >
K (s,a,b)
dhh
-V
dff dn (s, a, 6) log
KH
log
KH
g
8
K
KH
(s, 2/ Kn (8. (s.00D0 log
g
Combining the result above with 39 and referencing
38
conclude the proof of Lemmal 3.1
26

---

C.3
Proof of (88)
To prove 388 we analyze two cases, i.e., ((()) S (a s) > log KH. 8
log and
In the first case of N (s) (a ())g(b18) v log KH negative, leading special set D as
8. we conclude the right-hand side of (38 is 38 In the second case of (a(s) s) >
KH 4 log o we compose
D (1..
KH [i] N(G)))((1))))0 8) 4log 8
(43)
Given the fact that
Σ
E (T(ss) Σ
| s)p{(b|s)
(sA))SS(()
(a.))
NR(s) KH
E
(1)
E
(+A))SS(H)
(s,A)ESx(H]
the cardinality of 'D' can be bounded as:
|DI| E(sabhi (Z(() ( (b))())))
S KH/22
(44)
4 log KH
Moreover, we can view N,, a) as the sum of (g) independent Bernoulli random variables with mean Pf (a 8b 8), due (s) (s) with high probability and conditioned (s) and (s). Analogous to (31 based on the condition N S N (s), we can repeat the
Bernstein-type argument and obtain that for any fixed triple (s, a, h). with probability of least 1 -
KH 5
KH
(M a) (((()))(((
(5)()) s) 8) log
log
(45)
8
With probability exceeding 5, 8, 45 holds V(s, b, D by utilizing the union bound of over all (s, a, b, h) E DD. Combining the two cases, we conclude that (38) holds V(s, a, b, h) A x [H] with probability of at least 6.
(4
D Proof of Theorem 4.2
Theorem can be proved in three steps.
D.1 Step 1: Decoupling statistical dependency
Before bounding Gap(ū, D), we introduce an important lemma, quantifying the difference between P and P when projected in the direction of the value function.
Lemma D.I. Instate the assumptions in Theorem 4.2 Consider any vector V E R with ||V < H for all (h, s, a, b) E [H] x S A B satisfying No. (s, b) > O. With probability of at least one has
KH
H log KB 8
inf Pey (PO (
PV-
inf Peyo (Pp,....))
PV
CCa
pa (V) Nu(s,a,))
+C
Nn (s,a,b)
(46)
for some sufficiently large constant C4 > and
H²
KH
Var pa (V) & 2Var
(V)+0
+0
log
(47)
No a)
27

---

Proof can be found in Appendix G.1
In simple terms, (46) provides Bernstein-type concentration bound, while (47) ensures that the empirical variance estimate (i.e., the plug-in estimate) closely matches the true variance. Notably, Lemma D.1 does not require V to be statistically independent of Ph. h.e.o,b. which is essential given the complex statistical dependencies RIZ-VI-LCB, Under the leave-one-out analysis (see, e.g.,
24
25
we prove Lemma D.I to decouple statistical dependencies, as illustrated in Appendix
With Lemma
D.1
we now have: for any (h, a. E [H] X S x satisfying N1 a, b) 2
inf (PR,
PV
inf "eue
PV
S Bh (s,
(48)
DeU
(PR
Therefore, we conclude that Q7, (s, a, b) is an optimistic estimation of Quinoo* below.
(8, a, b), as summarized
Lemma D.2. With probubility exceeding 1 5, holds that
(s, 2 Q2 B, (8, (8,a,b) b)
and
(s)( 2 VAD.o (5);
(49)
See Appendix G.2 for detailed proofs.
Moreover, we introduce another key lemma highlighting the difference between RTZMGs and standard TZMGs from the same idea Lemma in [34]. The range of the robust value function narrows the uncertainty level a+ of its uncertainty set increases, shown below.
Lemma D.3. Consider the uncertainty set u (+) with TV distance and any RTZMG MG, (S,A,B (P),u* (P), H... The optimistic robust value function estimate V
11) (1- o ))) H
vh E [H]:
max V min V min $ES
sES
See Appendix G.3 for detail proofs.
D.2 Step 2: Decomposing the error Gap(ū.
The goal of RIZ-VI-LCB to output an e-robust NE policy (ū, D)) satisfying Gap(i D) in (9) i.e.
Gap(β, D) == max ( Vy (e) - ViNio (e), Vi (e) va (0) Se.
Due to the interchangeabilltyy between the max-player and the min-player, assume without loss of generality that D.o.B.ot (e) Viot (o) is larger than Vi
(0) vit. (e), leading to
Gap(ă, 1) < [v V. (o) - Vi (0)
According to the relationship in Lemma
D.2 we obtain
V D,ot
(8) S (+)
max min B(as))((ttss [ot(s, (EA(A) vEA(B)
max ((a.)))( [Qt (8, a. b)].
(50)
(EA(A)
where the first equality comes from line 5 in Algorithm 2 Therefore, there exists a deterministic policy μd - < A(A) satisfying that for any E
1 (s) == arg max ((a))))((()) [Q] (s, a, 6)] HEA(A)
(51)
We start by defining the following notation:
The state-action space covered by the behavior policy (n",'' v²) in the nominal transition kernel p0 is denoted as
C" = ((h,,,a,b) dh, 0}.
(52)
28

---

For any time step h E [H], the sets of potential state occupancy distributions w.r.t. the policy (s)) and the uncertainty set P 4 (Po) given by
Dg. = c (o) (0).P (s)
-PEE' (Pn)
(53)
BES
D/ = { {1h (10 (0) (8, a,
PPE (Po)
(54)
(s.M))SXXX
For convenience and without ambiguity, we introduce additional notation for [H] as
3h (s) = E(a.b)-(ae()))) (s, a,a, Vitr1)
In particular, the vector 8% M' E R is defined with its s-th term given by 8% (s). Similarly, we can define the notation related to rewards for h E [H] as
(s)) a.
According to the update rule in line in Algorithm and robust Bellman equality
28 we derive
Vn V. (8) - Vi (s)
(55)
SV. (s) - 1/ 10 (s)
< ((a)))((())))
Peu inf
PV
h+1 + 3pepe (s) (x)
(P.....))
po
PVu"'
- (aa))) (+))
inf
petpt (pp (PRina))
inf
PV
inf
PVu",0" oot let1
PEU (pa
h+1
Petro
(pa (Ph.o...)
+
inf
PV l+11
inf Pe
h+1
+ gar ae
(s)
Peuer (Ph.n...))
(Pa....a)
(
inf Peu (Phrnait)
PV+
inf PEt
PVu".0" o0 h+1
+
20
(s)
Not1
(P......))
Dinf.V (
Vu lar't ] + .er 2.3 (8).
E (x) (+))
(56)
h4t1
h+1
Here, (i) holds due to 48 in Lemma
D.I for (s, b) > 0 and
inf
+
inf r (Pr.
$ HH " for for b) 0. (57)
Petr (P
Moreover, (ii) is due to
PVulu ot lt11
V h.e,a,b == argmin
peyo (p8....i)
(58)
and consequently,
inf PEUL
w + h+1 P u" and
inf Petfo
PV S Pinf.V
V
h+1
(
(PH)....))
For of exposure, we introduce notation as Fin = (( Dinf. h, Furthermore, we define sequence of matrices Pinf. 8x8 We can utilize (56) recursively over the time steps
29

---

h + 1, .... H and derive
V.D.ot (s) V/2.0
(s) - (s) (s) - V/h Vireeesoo (s)
s V (Vitz V/ffi )
20t (8)
S /inf v Pint.
(Vit2
val ler nar
2P
2.3% (s)
h+l
ph+l +
H
... 2
Σ
20h (8)
(59)
1=h+1
j=h
H
i-1
= 2 >
V
(60)
i=h
(II) h-1
Pj v)
For conciseness, we define
I to simplify notation.
For any di E Di (ef. (33
taking inner product with
59 yields
( (atien
.V7 VA..B,0* Vi I
2
II P v
3pe .c.
(61)
where
]
df
(d
II
pinty
D.
(62)
j=h
by the definition of DP (cf. 53 for all = h + 1, 1,..,,.............. H.
Next, control (dp."""" .²" first demonstrate that the pessimistic penalty satisfies
,00h by using concentrability. According (18) in Lemma D.1
{
lo log a Var (V) 2C, log KH V N: (s,
B, b, V) < max
N, (s,
On log (s,
KH 5 Varpa
pana, (V)+ 2C, log KH 8 N: a))
log KH
o N. (s, b)
2Varpp (V)
H2H2
KH log
20, log KH o N₂ as,
N a, b)
8
2C, log KH
pa pa (V) (2Cn + VC,Co) H Hog KH
(63)
N; (s, a, b)
N: (s,
where (i) holds by applying 47 for some sufficiently large Co and (ii) follows from the Cauchy- Schwarz inequality. Therefore, combining the definition of "n"""" (s), we obtain
dP (s) " (s)
SES
Σ dp.l N AES
Le (a) (0000=
(5..))SSXAX
Σ
(64)
(x.))ESxB
30

---

where the last equation holds due to the definition in 5 Then, observe d' (s, a, b) p cf. (54.. Thereafter, we divide the bound (64 into two cases. In the first case, i.., E S
where max Pear((po) die "f (s, (s),b) 0, it follows from the definition 53) that: For any dpll"in" (s)
E D.e.
de N' (s), =0. O.
(65)
In the second case, i.e., S where max peu (Po) o²" ( (s), 0, under the assumption
in (20)
min {ah fdll w (,, S(A+
max per (P*)
S C, 0o,
(s, (s).
which implies that
d) (s), and (i,,, E c
(66)
Lemma 3.1 tells that with probability at least 88.
Kd. (s, (s).
KH
(s)s
5/ (s, log 8
8
W Kd p (s).
16
K maxp min P( (s), STA-BT
(
16C;
K min (dpul"" (s, b), s(A+A))
(67)
160;
Ho -1-(1- y
He +1-(1-a )
Here, (i) holds since, with (attta_, H) min
H
(a+))²
(o (a
HS(A+ + B)
KH
Kd 8, pf (s). c0
log
f(o ,0, .H)d (5, (s), b)
do
KH
flat o-, "H,) > 1600 log K
coHIS(A+ B) log
(68)
8
8
where the first inequality follows from condition
22 and the second inequality follows from
dm min (s),b
(s, (6). 00 < df(ss,u(()))))
(69)
Moreover, (ii) comes from Assumption 4.1
31

---

Combining 63 and (64) we arrive at
(dPwul :v-
Σ
=
(B
20, log KH 5
<
(o)))()))))
Var pa
No (8, (s),
(x
Σ
don'N (s)
(2Cn + vC,Co N₂ (s, (s).
H KH
(s,
32C log KH K Kmin dg."M.rr (8, (s), b), STA+B)
dpP. (s)
Var
(x.
16C; (2C, + VC,Co) H Hog KH
dp-"" (8),
(70)
K min dp (s, (s),
(s),b), 6), S(A+
(x,))
B2
From 61.
we
need
bound
df d. (s., EtH E
and
E dp:""" M" (s, (s)
D.2.1 Bounding Σ E( J. (s),
Combining (68) with Σ#1 E(EDESSX af dp1'N"" (s, (s). yields
Σ Gali'' (s),
(xB
32C C. log KH
geuiie (s),)
Var po
K Kmin { (ppnr"" (s), b), S(A+B)
(o))
(xB
dpaute v' (s)
(xB
32C log KHl
32C+C,S(A + B) log KH
Var Gandea (V),
Var po
(V Kap.t" (s)
K aande
(71)
32

---

Therefore, we have
Σ
Σ
df (s),
i= (xx
320 log KH
5 dp 2n (8, (s). pa
K
(x
KH 32C; B) log
duul"u" (b)
Var Gand
K
1= (x,
C ((A + B) log KH
H
b
Σ
df (s), b))
K
(x
H
H Σ
Σ
Σ
P. (s, (s), Var
VV) x
dpiumu (1,
pe
T=
(x
l=1
(s,b)
C, B) log
KH H
dp.t",.r (8, (8), Var
Sa) (V),
(72)
K
(x
where the last inequality follows from the Cauchy-Schwarz inequality.
Then, we introduce the following lemma about Σi=1
de "' (s,
(x
with its proof in Appendix G.4
Lemma D.4. Considering 46 E (0, 1), with probability at least 1 - 8, one has: for any product policy (),
2(H - o )H)
dptti..'" .²" (s) ais (Vi+1) S H min
H
(ot)²
(xx
x
+H
(73)
iml (B.
Armed with Lemma D.4 722 can be further bounded as
Σ
dftl" N²
(s),
(8,b)
HS B) log KH
2(Hot 2(Hot 1 (t)
(4) H
H min
K
(o+)2
X
4
Σ
gare (8, (s) (H +3)
(74)
i= I (x
33

---

D.2.2 Bounding Σ ( df (s),
Combining (67 with E (x. N' (s, (s), B2 yields
Σ &u''ee (s),
1= (#.b)ESx8
160; (2C, + vC H log KH
deu v' (s),)
8
K min (d.iee (8, (s), 5(1BB)
(
322 (2C, VC,Cs)
H B) log
(75)
K
where the inequality holds by the trivial fact
pua (s),
Σ
(x min Pe (s, b), S(A+B)
Σ
aea .'' (s),)
<
dg (s. 1/5(A+B)
(x
Σ
1+ S(A+B))
Σ
dptH" (s) s 25(A+ B).
(76)
(5.))
D.2.3 Putting all together
Combining 74 and 775)
obtain
ap- (s. (33s
i=1 (x
C280; B) log KH
12 H
K
(o+)2
H
de.ttivr (s), (z), V) + (H+3)
x
i=l (x,
32C; (2C, + V3)C3)
H2S(A+ log KH
5
(77)
K
34

---

which can further bound as
de (1,
(x.
128C; C (H + 3)S(A+ + B) log KH
2(HH+ 1 (1 - -+) H
5
min
K
(o+)2
32C; (2C, + VC S2 + B) log KH
512C; - B) log KH 5
5
+
K
K
2(Hot 1 (1 H)
x
min
Σ (x
de (s, (s)
(o+)2
128C; + 33S(A + Bog Kи
2(1lo 1 H
&
min
K
(o+)2
320; (2C, + VC,C3
H² B) log
KH 8
K
C,
+ B) log
KH
2(Ho* + -1 -1 o+h"
min
K
(o+)2
H
qu' v'
(78)
2
i=
(*.b)ESxB
where the last relation follows from the AM-GM inequality. Rearranging the terms, follows that
H
detth N' (s,
(s.b)ESxB
512C H2 + +3)S(A + B) log KH 8
2(Ho+ - (1 )
min
H
K
(at)2
64C; (2C, + (C,Cs)
HRS(A B) log
KH 3
K
512C; + B) log KH
2(Hoo - 1 (1 ))) (1)
min
K
(ot)²
(12 + 3)S(A+ + B) log KH 5
2(Hot - 11 (1 (1-
o+)"
min
(o+)²
C2 S(A + B) log KH 5 min
((H - 1 (1 o+)
(79)
K
(o+)2
Along with the above analysis, sufficiently large constants C₁, C22 C3 > 0, and
ready bound Vi (g) Vinit
(e): There exist some
C;C.HS((A + B) log KH
2(Ho+ 1 (1- (1-0+)
Vi vi (0) Vi (0) =V
min
K
(a+)²
C;C,H S(A + B) log KH
min 2(Ho 1 o1- )
8
H
K
(a+)²
C:C.H'S(A + B) log KH
2(Hot - 1+ (1 )
min
H
K
(a+)
(80)
where the last inequality follows from condition
22
35

---

D.3 Step 3: Summing up
Consequently, we obtain the upper bound of V/- V. (0) - ViL. (0) in 80 Similarly,
V @
Vilitio (0)
C:CaH2S A + B) log
KH
(H (H+ 1)HHo - 1 (1 ) H..
min
(81)
K
(0
which directly leads to
C;H+S(A+B) log
Gap(A, D) S V
K
2(Hot - 1+ (1 oth 2(Ho 1+ (1 o "n) H j
min
(82)
(o+)
(0
for some sufficiently large o₁ and
KH
2Ho - 1+ (1- 2(Ho - 1+ o )-) (0
K HS(A+ + B) log min
(o-)²
Discussion of (82). For the term T min (f(ot ), H), considering the interchangeabil-
ity between of and o", we define g(o+, H) = Ho* - -H1 - - - (o )² For
H derive the first derivative as Øg(a .II 11 (1 - 2Hot. The 1I2 1)(1 - 2H 0, indicat- ing that 9 is concave. By evaluating the first derivative at the boundaries, we find Oofo ".H) do - + H + И > and 0o(a" Bo(a".H) increases monotonically, reaches maximum o -H < 0, showing that g .)) first some point o², and then decreases monotoni- cally. Furthermore, since g(o - 0, H) - -H < and gio+ = =1, H) = 0, there exists 0 < 00 < such that g(0 H) 0. If 00 S min(ot o _ S 1, we have T H. Otherwise, T = min (Hot (1---tt(1--t)) )t)) (He 1+(1-1111 -1--
dat
second derivative is given by P'ga ((at)²
do .H)
(o+)²
E Proof of Theorem 4.4
We focus on simple class RTZMGs: robust Markov decision processes (RMDPs), which single-agent versions of RTZMGs. Recall that RTZMG with uncertainty set is .M (S,A, 8. (P")) H). For illustration convenience, assume A B and |8] meaning the min-player's actions do not affect transitions or rewards. Thus. finding robust NE RTZMGs reduces finding the max-player's optimal policy in corresponding RMDP M, AS, rp"),,,H}
Thus, we construct the lower bound for finding the optimal policy in RTZMGs, which also implies lower bound for finding robust NE in RTZMGs. We start by re-stating a useful property about KL divergence from Lemma 2.7 in (36].
Lemma E.1. Vp. (0. 1), it holds that
KL(p g) < (p -)
(83)
q(1 q)
F.1 Step 1: Constructing a family of hard Markov game instances
The hard instances developed here differ from standard MDP since we need to consider that the transition kereel can be perturbed in robust MDPs.
36

---

E.1.1 Constructing hard robust MDP instances
We introduce an auxiliary collection + S {0, 13th comprising H-dimensional vectors, Resorting to the Gilbert- Varshamov lemma [1], there also exists set + S {0, 1) such that:
H and
for any o, o E & obeying o + ő
||
[ 2 e//8
(84)
Bearing this in mind, we construct a set of RMDPs as
M(F. +) M(F.0)= M (TT.))=(M3-0
AS, (S,
(fE F= (0,1, 1... ,SA 12A-13,64 = 1onlishs
(85)
where S = (0,
(0, 10. AA
13. and a+ will be introduced momentarily.
In simple terms, the collection MMFF Φ) consists of SA subsets, each containing | different RMDPs associated with some f E F. The state space for each RMDP My E MMF, (). denoted as Sone: includes two types of states: M {mm i E F} and N (mz E F). Each state in M and N has two possible actions, Aone {0. 1). Thus, there are total of 25A states and 4$ A state-action pairs.
Now, we can define the transition kernels for MMF Φ). For any RMDP My E M(F, +), the transition kernel pfo = (pf.0 J is defined as follows, for any (8, 8,, E Sone x Aone X Sone x {...
(s + +1- =)) if 8 my Oni
pf. ( s, = (1 = my) (1- (1-
if 8 s= my,a = Uni otherwise,
(86)
1(s' = s),
where p >>>>> 92 1/4 In addition, the reward function is defined as
Y(h, a,)) [H] X Sone X Aone (s) {
1,
if s
(87)
0, otherwise.
E.1.2 Uncertainty set of the transition kernels
Denote the transition kernel vector as V(h, s, a) E [H] Sone X Aone: Pha = p.
(88)
Recall the uncertainty set defined in (1. 40 (pf.0) represents
ud (pf.)= u0t (Pf.e.)) u (PHi
Phiaa E
-Pf.
s
hiaaa
where represents the Cartesian product over (h, s, E [A] Sone Aone- For the convenience of the subsequent proof, we analyze the TV distance as an uncertainty set for example, which means
ud (Pf. = (p Phis. A(S):
p/. so+].
(89)
For any RMDP Mÿ E M(F 3) and any (h, 8, a, s') E [H] x Sone x Aone x Sone, we define the minimum transition probability from (8,a) to s', determined by any perturbed transition kernel Ph,s,a EUO (P. a
pint.f as
inf P EU (P
Pa(s' ss max ss o+.0),
(90)
where the last equation inherits from the definition of U1" (-) in 89). with the remaining probability distributed to other states. We also define the transition from each s E M to the corresponding state mm++n N for any M) for all E [H]
for my Ph = pi pinnf..0 f.t (ny my. 0n) p - at
Dh. = pint (ny m 1- 9%) +
inf
(ng
(91)
37

---

It is obvious that
P1
P2
PH
iin
42
QH
(92)
which motivates us to abbreviate them consistently as gint = inn and qint = qi" later.
E.1.3 Robust value functions and optimal policies
We now define the robust value functions and identify the optimal policies for RMDP instances. For any RMDP My MMF, $) let ji*.. - fffffnff
T==1 represent the optimal policy, given that is deterministic. At each step h, we use V f. and V ... to denote the robust value function of any policy z and the optimal policy fi*- respectively, under uncertainty level a The following lemma highlights key properties of robust value functions and optimal policies; the proof is deferred to Appendix H.T
Lemma E.2. Consider any M2 MMF, b) and any policy ji. Defining
Tn - ob |m)), m R.f.0 = - pi (n /m + q
(93)
holds that
Vh E [ vi (m)) = mh v.. f: (:(())))))))))))))))())) + m,
R.. vi (my): (mm))
V
(94a)
S E V. =
(1 Via' (s) + o o Vug ...0 (m))) h+1
(94b)
h+1
In addition, for all h E [H) the optimal policy and the optimal value function obey
Pb
f (on ())) - 7h ... (chn (mg) =,
(95)
vi" Vi V f (my) = p h+1 5.0 + (1 - S.0 (mm)))
(96)
E.1.4 Construction of the history/batch dataset
In the nominal environment M a batch dataset is generated with K independent sample trajectories with length H per trajectory, according to (3) and based on the initial state distribution g" and behavior policy ft" {4h Wh= satisfying
!!f
1 (s()) = e(s) and (a)a)) 2'
a(s,a,)) E Sone x Aone x [H].
(97)
We define the nominal transition kemnels for M where any state m, M transitions only the corresponding n, N or remains at itself. For simplicity, for any m, E M, we denote the corresponding state n, E N as mnn The basic nominal transition kernel is defined as: For all (h, [H] X Sone X Aoner
(p+ s + (1- (1---))) if SEN.
=
if s SE = On;
P. 8, s,
ps sm=++) + (1 (ps-ppsss-
if SE 0n
1(s' = 8),
(98)
In other words, the transition kernel of each My E M(F, 3) differs slightly from the basic nominal transition kernel M when my, making all components within M(F, Φ) close to each other. Specifically, p and y are set according to
Espsp=
< and <q=p- p- for some p, A 0.
(99)
Without loss generality, let + E (0, co] for some < Co < be the uncertainty level. Taking C2 and C₁ = -/2 v 1 p and A are set
if a
C2
if S
=
(1 H a+ otherwise
and
<
2ff
otherwise
2H
(100)
H
38

---

which establishes the fact that
C2
P + P max
(101)
2H
Combined with H 2 2, it is easily verified that - p A S as follows:
when o+
C2
1
9
9 o
- co + 20 o S
co(11 1)
1,
2H
H
H
when a+
C2
302
(102)
2H
2H
In addition, let ((s) represent a state distribution supported on the state subset (m,, n25) E M x NV: 1
1
CISA) [(s I - nf),
((s)
CSA 1(s m2)
(103)
where 1()) is the indicator function, and C' > is some constant that determines the concentrability coefficient C (as we shall detail momentarily) and obeys
1
(104)
CSA 4
As turns out, for any MDP M the occupancy distributions of the above batch dataset are the same (due to interchangeability) and admit the following simple characterization:
po-1 (s,a) = =5(()),
v(s,a) a) E Sone
Aone:
dh
(105a)
V(s,a,)) h)) E Sone x Aone x [H),
Ø(s)
po. S ch
(8) s 20(0),
Ø(s)
S dh
(8, () S <T()).
4
(105b)
In addition, we choose the following initial state distribution
if M i
e(s)
CSA 0,
(106)
With this choice of the single-policy clipped concentrability coefficient C and the quantity C are intimately connected:
C C 2C.
(107)
The proofs of (005) and 107 are postponed to Appendix H.2 and H.3 respectively.
E.2
Step Establishing the minimax lower bound
Recall our goal: for any policy estimator f computed based the empirical dataset, we plan to control the quantity
Vvtto (.0((() Viñ .f (
max (Fx))FFx
(108)
with initial state distribution defined in (106).
E.2.1 Step 1: Converting the goal to estimate (f)Φ)
As verified Appendix H.4 we have
o
< otherwise,
8
H
(109)
1,
and
if otherwise,
< 27
A = C5
H
(110)
39

---

which satisfies (100) and leads to that for any policy jı obeying
H
H
(. (mm)
-1% -...1.0 (-) (e|m))ll
(-1
2
(111)
8
one has
Vi J. (m²) - Villa if (my) EE
(112)
whose proof is postponed to Appendix H.4 Now, optimal policy to estimating (f, Let f. represent the probability distribution when the RMDP
ready convert the estimation of an
is M v(S, F x Φ. For any (1 E F x t, suppose that there exists policy jú achieving
Ps Vioal (ma) - Viã.o' (f00m) S se 2
3 4'
(113)
which, in view of (12 indicates that
ps Σ [1
1 (. ((1m))ll
H
2 4
(114)
8
Consequently, taking σ arg minge n= | mm) 12,
we construct the - m Il,
estimate of a as T Φ. If プ |m my) 10. (- |m))ll1 ø' E & obeying ø' + o one has
H for some á o then for any
|mn (mf)) mh T...da (. (11m))ll
hm1
1h 1. (11m))l
Σ
T ( (.1m))
1% 1...5000 (1mm))li
(-1
k=1
H
H
H
(115)
8
where the first inequality holds due to the triangle inequality, and the last inequality follows from the assumption Σ [
(m)m))) Th F.06
[mf)ll
<
H and the separation property of d E 4; see g
184. Similarly, we have Φ- Φ if
H
H
H
M my) - Th 5. (.)
<
M (mm)= - 1 (-1m))ll Aa E $ of # o.
8
A=1
(116)
which can be directly achieved when Σm= to
|iān (- (11m)) 5. (-1m))ll < and further leads
P f - ②
2 IP
f
pm - (
H
(117)
E.2.2 Step 2: Developing the probability of error in testing multiple hypotheses
Next, we address the hypothesis testing problem over ø E t and derive the information-theoreti lower bound for the probability of error. Specifically, define the minimax probability of error as:
Pe == inf max (f.) (
F + +),
where the infimum taken over all possible tests constructed from the available batch dataset.
Given the dataset D, with K independent trajectories, let n (and ej (s, a)) represent the distri- bution vector (and distribution) of each sample tuple (sh, ah s/,) at time step h under the nominal
40

---

transition kernel P for M Then, employing Fano's inequality [6 additivity of KL divergence 36 Page 85], it follows that
Theorem 2.2] and the
max (0,
(L(e0 0
+ loog
Pe 2 1 - K
log (b)
()) 8K
KL (L (
8log 2 H
max
H
(
(i)) 8K
max (6.6)
1
(118)
where (i) holds due to |+|
> e 1/8 and (ii) follows from H 2 16 logo2 2.
Since the occupancy state distribution d; is the same for any MDP My, Ve 4, we apply the chain rule of KL divergence [12 Lemma 5.2.8] and the Markov property of the independent sample
trajectories to obtain:
Σ
KL
|| (-1s,a)
E (ndd
1=1
p((mg)
Σ
KL(P) mf; |l (. (119)
(0/0111
where (i) follows from applying (105) and obtaining
E
KL
(L((ptt (+18,,)))) || (-10,a)
snvdf (8)
24 (a ()) s) (s' ()
(s)
pa ((laas)pp0 P) (8' 8, Σ
(611,,08) a) log
7 (a 8) P) (s' (8,a)
0,a!
ph (s') m) pr (s' my.
2 ((m))
ΣΣ poun (s'l my. a) log
1
2 {mm))
(L (-1my.a) Pfn (my
Consequently, combining (118) and 119 leads to
Pe
4K
max (0.0)
e(mm)
ΣΣ
KL (L (: (.Imy,a)
|| Ph my
(1 a))
(120)
h=1
We proceed analyze
120 by considering different cases of the uncertainty level o+.
For 0 <t
_ If on =ōh, it obvious that
oh.
Σ
(-18,a))
(121)
aE/0,11
Consider the case of dh + Φn. Without loss of generality, we suppose di and Sh 1, which indicates
P (0) (0|my,00) 0)) I (p - 9)
A
q(l q)
9(-9)
(cs)
4(cz)
4(cs)
262
(122)
H 9)
H2H
where the first inequality exists by applying Lemma F.
(i) follows from the definitions in
(99), (ii) holds due to the definition in (100). and the last inequality arises from q p A 2
41

---

(see 100 and - q 2 1- - H Similarly, we establish the same bound 2H
for (L, [0) m 1) (0 mn 1)). Further incorporating
122 yields
16(c;) (2
Σ
my KL(PA (. a) PK Pr (1mm,,a) <
(123)
02 C2
ac (0.1)
For 20 < ot - 1 eo: Following the same pipeline, it then boils down to control the main
term as below:
KL (0) my. 0) || (0 my m2.0)) 0)) - (p g)-
(
A
q q)
9(1
9)
(ii) (cs) 2 222
2
S
(124)
g g)
co
where (i) and (ii) follow from the definitions in 99 and (110). Here, the last inequality arises from
C1
(ii)
1-q21-p=1-
(1+
0
C0
H
(iii)
p2リ=リ-2 A
2 oz
(125)
where (ii) holds due to the definition of c and (iii) follows from we arrive at
6o
101
Consequently.
ot=
Σ
(
P (x (,1,8,a)
(126)
co H2
(E
Summing up 123) and 126). we achieve for any (Ø, 3) E + with o क and any time step h E
[H]
16(c))
Σ
KL(P)
PL. (. (1my,a) || (. ( a)) v H22 max
(127)
h
ac (0.1)
Plugging 127 back to 120 under the definition in 106). we obtain
H
Pe
4K
max
d(mf)
Σ
Σ
KL (L (m) || Px (-Im,,a))
H
(0.0)
h=1
4K
(g
2
e(mf)
max fa 1/H}
C0C2H2
(4K(cc))2
IV
Co22 CSAH max at 1/H) 2 4'
(128)
long the sample size, T KH, of the dataset is selected as
T T C min H.} C min (1/o+,tn H
(129)
256
256
E.2.3 Step 3: Putting all together
Next, we establish 108 by contradiction. Suppose that there exists an estimator jú such that
max Ps. (irt (10 VēL + .1 (e) 2 e 4/4
1
(130)
(feeF)x
4
According to (108. we would need
max f.0 Kvrort ( 1:00 (m)) 26 < deb
Vu E F:
(131)
42

---

To meet 131 for any E F, we would require
Vo E Φ y. (v (y (my) - v. (:0(m))) <
3
(132)
which, in view of 112 indicates that we would need
H
vg E +
Pyo
| -m7 (-
< こ
(133)
8
4
On the other hand,
117 indicates
VΦ E o P/.
6 -=
3
(134)
To achieve 130 or, in other words.
133 we apply
(34 to all w E F, which would require
3
v(f
ps.
(f. = (f,0) 4'
(135)
This contract with (128) as long as the sample size condition in (129) is satisfied. Thus, if the sample
size obeys 129
we cannot achieve an estimate jú that satisfies 130 which completes the proof.
F
Multiplayer General-sum Markov Games
In this section, we extend RTZ-VI-LCB to the setting of multi-player general-sum Markov games and present the corresponding theoretical guarantees.
F.1 Problem formulation
A robust general-sum Markov game is a tuple M(S, {- H, (P))(P))) ))==: {r.) with m players, where S denotes the state space and H is the horizon length. We have m different action spaces, where A. is the action space for the 7th player and [A| = A. We let A = Ai x ... x Am denote the joint action space, and let a == (a1.... am) E denote the joint actions by all m players. A notable deviation from standard MGs is that: for < i S m, instead of assuming fixed transition kernel, each jth player anticipates that the transition kernel allowed to be chosen arbitrarily from a prescribed uncertainty set U (P"). Here, the uncertainty set 24 (PD) is constructed centered on (- a), with its size and shape defined by certain distance metric p and radius parameter o; > 0. ri = [rn,shee(H is a collection reward functions for the 7th player, so that is, a) gives the reward received by the 1th player if actions are taken at state at step h.
The policy of the 7th player is denoted as := { S A heeaH We denote the product policy of all players π == player as T-4. We define (s) as the expected cumulative reward that will be received by the 7th player if starting at state s at step h and all players follow policy л. For any strategy π-i- there also exists a robust best response of the Tth player, which is a policy μ² (T= satisfying Va p=="=_)i=--10 (s) = supm, h1 V (s) for any hs, E S [H]. For convenience, we denote Vi V K (=-1)=--0; The Q-functions of the robust best response be defined similarly.
... TM. and denote the policy of all players except the 7th
Similar to the definition of behavior policy (1²", v)), use the short-hand notation for the occupancy distribution w.r.t the behavior policy T" = x",)) as: v(h,s, a) E [M] x A.
,,);; dh Pp (s, = drh pp' a) P(st, = = e², Pd) π (( (s).
d Pm = dr .P (8) = P(sh = =s|s-
(136a)
(136b)
Similarly, for any product policy (Ti, n-)), there is, v(h,s, [I|] x S x A
J i.P (s) =P(ss =s|s] ~5 g)
(137a)
d -. (s, a) = P(s =s|s ~ 2, P) n (a; ()) () T (a=
(137b)
43

---

Therefore, the robust variant of standard solution concepts robust NE for Robust multi-player general-sum MGs introcuded as follows: A product policy is considered robust NE if
v(s) E S, (T = Vn VA* (s).
(138)
robust NE signifies that given the product policy (α) of the opponents, no player can enhance their outcome by deviating from their current policy unilaterally when each player accounts for the worst-case scenario within their uncertainty set ug: (P") for all = 2, m
Since finding exact robust equilibria can be complex and may not always he feasible, practitioners often seek approximate equilibria. In this context, product policy A(A) can be termed an e-robust NE if
Gap(n) == max
(1 M (e) V (e) (e))
Se,
(139)
where
Vi (p) = Egnu Vi (s), and
V Esng (s).
The existence robust NE has been established for general divergence functions used in the uncertainty set in [5].
Goal
With dataset collected from the nominal environment, our objective is to find a solution among the e-robust NEs for the robust multi-player general-sum MG Mg, w.rt. specified uncer- tainty set 4 (P') around the nominal kernel, while minimizing the number of samples required under partial coverage of the state-action space.
F.2 Multi-RTZ-VI-LCE
Here we present the Multi-RT7-VI-LCC algorithm in Algorithm 4 which is an extension of Algo- rithm for multi-player general-sum Markov games.
According to the empirical frequencies of state transitions, we can naturally construct an empirical estimate P00 = { (50 J of p0, where
Na Ex (sj) = (8, (s),
if N₁ (s, a) > 0; if N₂ (s. =0,
50 (s' 8, a)
(140)
rinh (s,a),
if N₁ (8, a) > 0: if Nr (s = 0,
Pi,h (s, 0) =
(141)
0.
for any (i, s, a's) [m] [1]] x S Ax S. Besides, Nn a) represents the total number of sample transitions from (8, a) at step h, and
Nn(s, Σ -1((saa))
(142)
Before the details of Multi-RTZ-VI-LCB. we extend Algorithm as Algorithm 3 which reduces statistical dependencies and produces distributionally equivalent dataset Do with independent samples. Similar to Lemma 3.1] we present the following lemma concerning the dataset Do. whose proof is similar to the context in Appendix
Lemma F.1. The dataset produced by the two-stage subsampling method is distributionally identical to Do with probability at least 1 88, where (Nn(s, a)} are independent of the sample transitions
in DO and obey: v(h, s, a) E [H] x S A.
Kd (s. a) - 5/ (sf a) log
KH 8
Na(s, 2
(143)
8
Based on Algorithm we propose a model-based approach for solving robust multi multi-player general- sum MGs using approximate 0o0 for p0, summarized in Algorithm
44

---

Algorithm 3 Two-stage subsampling for Multi-RIZ-VI-LCB.
input Dataset D, probability 8.
1: Step I: Data Partitioning. Split D into two equal-sized subsets, Dm and D*, each containing
K/2 trajectories.
2: Step 2: Defining Transition Bounds. For step h and state 8, denote the number of transitions
from D (resp. D*) g (s) (resp. (*)))). Construct the trimmed count
HS 00
()(() max (R((s) 1 (2 log
3: Step 3: Generating Subsampled Dataset. Randomly sample transitions (quadruples of the form (s, a, h, s')) from Dr uniformly. For each (s, E S x [H], include min( NT, (s) transitions in the new dataset Dt.
output Set Do = DE.
Algorithm 4 Multi-RTZ-V--LCB
1: Initialization: Set uncertainty levels o; for 1,2, m. (s) H and (s, H for all (i, s, a, h) [m] X A [H 1].
2: Compute the empirical reward function using 141 and the empirical transition kernel Pg
using 140).
3: for h -,..,,... do
4: Update the robust Q-value estimate
Prn 2i (s) min Pin
a) +
inf PEtP: PR...))
PV.: i,++1 + Br, (s, Vi Vithti H.
C, log Nuls,a)
Var (V), 20, H KH
with Bin (8, a, V) = min max
haa
Nx(s,a)
5:
Compute Nash policy for each s S
Th (s) (Fi, (8) -iih (s)) ComputNash (Qri (8.-))
6: Update the robust value estimate for each S as
V (s) (s)
[Q (s, a)
7: end for
output
The product policy (s) = { (s)) with TA (8) = II T, (8).
Similar to (16), we can tackle the multi-player general-sum MGs problem as:
inf PVoit1= reur: (Po ..)
50 h,
Do 1
(a-min
Vi iitt1 ] (o))
max
ag oejmin, Dor 4, max, Vihi
(144)
where
[(at1] follows.
respectively denote the clipped versions of Do. 2,++1
IRS based on some level a 2
(s) = Vo (s),
Voa
De: (8) > a;
(145)
ar.
otherwise;
F.3 Analysis of Multi-ME-Nash-QU.
In this subsection, we prove Theorem Theorem 4.2
which can separated into three steps as the proof of
45

---

First of all, similar to Assumption 4.1 historical data and the target data assess the effectiveness of the historical dataset for achieving the desired goal. We propose novel assumption for robust multi-agent general-sum MGs as:
we measure the distributional discrepancy between the
Assumption F.2 (Robust multiple clipped concentrability). The behavior policies of the historical dataset ID satisfies
min (dh - (s. a), 5 SL A:
max
sup Mta.saahhpyaaMM..xxxxxxXxX
dh (s
C
(146)
F.3.1 Step 1: decoupling statistical dependency
Before bounding Gap(T), we introduce an important lemma whose proof is similar to Lemma D.1 in Appendix G.1 quantifying the difference between P and P when projected in the direction of the value function.
Lemma F.3. Instate the assumptions in Theorem 4.5 Consider any vector RR with || S H for all (i. h, 8, a)) E [m]] x [H] S x A satisfying Nr. (8, a) > O. With probability at least 6, one has
KH
H log KH 8
inf PEU (PR
PV
inf PE
PV & Cuy
Var po
(V) log
+ C4
N₂ ().
haaaa
5
N₂ (s, a) (147)
for some sufficiently large constant C4 > 0, and
H² NA (8,a)
KH
Varpa h.a.a
(V) & 2Varpp p (V) +0
log
(148)
8
With Lemma F3
we can now have
inf
PV
PV S Bn as (PM
inf
(149)
P (Po...)
for any (i, h a) E [m] x [H] x XSXxxx x A satisfying (s, 1
Therefore, we conclude that Q (s, a) an optimistic estimation of 2 (s, a) for any
1,2. m, which is summarized below, whose proof is similar to Lemma D.2 Appendix G.2 Lemma F.4. With probability exceeding - 5, it holds that
(s, 2 Q 1.th (s, a) and
(1)
2
1. :.*(s))..
(150)
2.
Besides, we introduce another key lemma highlighting the difference between robust multi-player general-sum MGs and standard multi-player general-sum MGs from the same idea of Lemma D.3 as shown below.
Lemma
Consider any multi-player general-sum MGs Mg. {S, (A,)m H, (1, (P") (riben) and the uncertainty set {Uz (m)) with TV
F.5.
distance. The optimistic robust value fanction estimate Vo:.
(H + (1- 0,) -1 H
v(i, h) E [m] x [H]:
max Vo
min Da S min GA
eES
SES
F.3.2 Step 2: decomposing the error Gap(f)
The goal of our algorithm to output an e-robust NE policy (R) satisfying Gap(*) in 139 iee,
Gap(f) = max {
y i,
1,1
(0)
V
S c.
i=1
46

---

According to the relationship in Lemma F.4 under the definition of A-; = A x ... x Ai-1
A1+1 Am we obtain
, (s) (()(ss)
min
(x)(= (()) [ a)
(151)
(A(A-))
where the first equality comes from line 8 in Algorithm Therefore, there exists deterministic policy T= :.:8 :S & ((A-;) satisfying that for any E
π (s) 2 arg
min EAAA)
(a-()(())) (fi((s,))
(152)
Before starting, we introduce several useful notations:
The state-action space covered by the behavior policy n² in the nominal transition kernel pD is denoted as
[h, s, d', a) > 0}.
(153)
For any (i, h) E [m] [4], the set of potential state occupancy distributions w.r.t the policy m2, and the uncertainty P u (Po) is denoted as
{
:P (PO)
=
dh
(8)
(154)
(o 10),P (s,a)
Peu: (PO))
dh
(155)
(s.a)ESXA
For convenience and without ambiguity, we introduce additional notation for (i, h)) [m] x [M] as
- (8) = E (e)) (s, Vo, v.h+1).
In particular, the vector " E TR. is defined with its s-th item given by (i, "..."" iss). (()).
Similarly, we can define the notation related to rewards for (i,h) E [m] x [M] as
(m)() Pi (s,a).
To proceed with the analysis, we need to introduce a pessimistic V-estimation VT (s) that are defined similarly as (s). Similar to Lemma we have V22,, (8) Vi (s).
Therefore, according the update rule in line 4 in Algorithm and robust Bellman equality similar to (28). we derive
V+ 2a (8) v.00 (s)
< Vo (.((ss) (7))(()(8)
inf peur: (fo...
PVo. Piot +
+28 - Ea)(x(()) PEU (PP...)
inf
PV
<B (B))))()))))
inf Peur (ph.
PVo.
inf (Pu (Ph...a)
PV
PVint
+
inf (Po a....a)
PVa:
r.h+1
inf
Pit+1
+ 2,9 (s)
PEU Pr
Ph...)
(1)
E a~ (T))
inf Pelrs (pu..(ph..))) (pn
PVo:
i,h-1
inf (Po
PVa,
PLint1
+ +38,1 ((s)
(11
B (T,
pint.V (Do: Ciisa 1,h+1
Light)
Vog
(156)
47

---

Here, (i) in 156 exists due to (149) in Lemma F33 for (s,s,a) > 0 and
inf PEuui(Ph.s.
PVa. Whit1
inf Ph
PVa. i1++1
S Pin ((s) for (M a)
(157)
Peu"i
and (ii) is valid under the notation
Pinf. ihasa argmin
Petlo (Ph...a)
PVi+1 i,1+1
(158)
and consequently,
inf PEt(" (eEMM((PE,.. (Ph...a)
PV
Pii
Pinf.V Vo. S.h.a iht1
and
inf PEurs(Ph,..
PVo. S
Pinf,y Voa i,,,, G,+11
For ease of proof, introduce notation as Pinf.V PinffV
i,h,s,a" Furthermore, E RSS. We can utilizing 156 recursively over the time steps 1,
(e)) pinf.
i.h,
define a sequence of matrices
h, 1, and derive
V+ 1.0
(8)
(8) S (ih(s)) 1igh (x)
V it
(Vehtt - -Vihhtt)
+ 33 (8)
< V pint.y (V. (Vihh- Liht2)
3.innt. -,
Pinti + 3,0 3.3,x.--((8
(s)
S < Σ
II
pint. Pij
Biy 3,, (ss)
j=h+1
H
= 3
Σ
pinf. v bi
g
(159)
==hh
(IT pint,
where we define
for conciseness.
For any d Fu
Dr. (ef. (53), taking inner product with 59 yields
1.
Vū,a
5
h
3
II
pint.v
H
3
de
(160)
#
where
]
4-1
p
(c
II
V
E Dal
(161)
by the definition of D. (cf. 154 for all i' h + 1,... H.
48

---

Next, we control (d. " P of penalty, we demonstrate that the pessimistic penalty satisfies
- utilizing concentrability, First of all, according to the definition
KH Cn log & Var po
( 2C, log
KH N, (s,a)
a, & max
(V
5
N; (s,
Cn log KH
(V)+ 2C, H log KH
Varpo cam
())
N₂ (8, a)
WA IA
Co log KH
Co
KH 8
2C, log KH
pV (V) +
log
N₂ (s,
N: (s,a)
N₂ (s. a)
20, log KH
pa po. (V) (2Cn + VC N₂ (s. a)
H log
KH
(162)
N₂ (s,
where (i) holds by applying (148) for some sufficiently large Co and (ii) exists follows from the Mauchy-Schwan inequality. Therefore, combining the definition of P 35""="(s) ((),, we obtain
Σ #ES
(8)
T.. (8)
Σ
dy
(8) (8) (a)
#ES
Σ (s.4)SSAAxB
Σ
(163)
(s.A))SXA
where the last equation holds due to the definition in 137b Then, we observe di pp. '(8, a) E DRa (cf. (155) Thereafter, we divide the bound (163) into two cases.
For the first case, i.e., E S where maxpe d Fh (s,a;, (s)) = 0, it follows from
definition (cf. 154 that for any d. p. (s, a; n (s)) E Dpai, it satisfies that
& 8 as, xb((s)) = 0.
(164)
For the second case, i.e., 8 E S where max pey+ (po) di Ft riP ,.P (8, ai xb,())) > O. by the assump-
tion in (146)
min {d T (8, ais 7 (,)())) 3 3EinAA
max (PO)
< CC,, oc.
dp (s, mb (s)
implies that
dy ai ( >0 and (f,,,a,=2,(55) E
(165)
49

---

Lemma F.1
tells that with probability at least 1 86,
Kd (s, ai, -h (s))
KH 5y/ Kd (s, (s) log 8
az n (s))
8 Kdd (s, 0i =+)
16
aoinine (s, ais n =s,())) SIILI A
K maxpett (Pa) min dy
160
& di min dp (s, (s, T ,h,
(166)
16C;
where (ii) comes from Assumption F22
and (i) holds due
HS
Ei
Ai
KH
Kd
uz, (s,0,, 2
log
((1o:)11: H)d (8,0;, u;, (6)
dm
KH
KH
2 (gHS) Σ
A log
f(1o, )= H) 2 1600 log
(167)
8
where f(fo;11 H) min { (Ha dition (26). and the second inequality follows from
m
H the first inequality follows from con-
(a=)²
i=1
dm min (d, (s), : di (s, (s). a > 00 s dG (s. a, (s)).
(168)
Combining the results in 633 and 64
we arrive
(d, (
p (8, as, =
at at, =5, V)
(s.;))SSA;;
KH 2C, log N; (s, as, nb (s)
Σ
(s, ai, (1)))
b
Var po
(x,
KH (2Cn + VC,Co) H log N₂ [s, (s)
Σ
po (8, (s, (b)
8
(s,,))xAA
KH 8 160; (2C, + (C H log
p (s, ais (s))
K min (op (.. (s, as Tb (s)); 9 & A.
(Sx;;)
C2C²C, log KH
Var pm
ioniuiih (b) (P)
K min dg
g (s, as, T (1)),,,, s S
1
(169)
Similar to the proof in Appendix D.2 we are ready to bound V siart some sufficiently large constants CT Oz, C3 0, and
(0)
Vi0 ih
(0).
There exists
a a +.r
(0)
(0) s
H&C Ei=1
KH Aog
8
min
2(Ho:
(1 H)
3,
K
(0,)²
CC 1i=1
A log
KH
(2HH, 1+ o;)
min
K
(a:)2
0:0gH'S Ei=
A; log KH
2(Ho, 1+ (1 H) H
8
K
(0,)²
(170)
where the last inequality follows from condition
26
50

---

F.3.3
Step 3: summing up the results
Consequently, we obtain the upper bound of V i::7 (0)(e)
(e) in 170 which directly leads
to
C; E K
A
KH log
2(Ho; - 1 (1 o;)
m
Gap(A) S S
6 min
H
(171)
(a,)
for some sufficiently large 01 and
KH K 2 HS Σ A; log
11 11 (1- o;) -
min
H1
8
(0:)
1=1
G Proofs of lemmas for Theorem 4.2
G.1 Proof Lemma D.1
We prove Lemma D.I similar the proof of Claim 1 introduced by 43
G.1.1 Proof of 46
According to the definition in 16 for any fixed value vector V independent of Do
haaa have
inf Petfo (PA (Phna
PV
inf
PV
Petoo Pep (Pp.))
max 5o Ph,s.a [V - o+ (a (a-ming [V1 (s')
ac aE(min, max),mx, v(a)
po Phonas (Vaa ot (a- -a- [V) (5
max aE(uni, max) v(Nil
po Phona, [V - Phonall (V
max
a//min, max, V(s))
max a
po
h.s.a,b [V], Ph. [Ma.
(172)
where the last inequality exists due the fact that the maximum operator 1-Lipschitz. According to the definition of empirical transition kernel SS0
h.s.a,b. we have
(Ph,,,,b
Ph.s.a,t [V]a
ΣN 1hi h1, 8, a 6,6% 8'}
Σ V (s))l. S'ES
Ph (s' (18(8,,a,))
N₂ ()
as sum of independent random variables. Based on the relationship between Ph Ph.s,. and po b.s.a.b we verify [ 0 and X < H for all s' E S. With probability exceeding - ô and for some universal constant C2 > O, under the Bernstein inequality [37 Theorem 2.8.4], we have
KH C4ll log KH
(Ph..ab DD p M4. 5 SCa
Nn (s, Var pg..... ((V),) log
N₁ ()
KH
C4H log KH Nv (x, b) (173)
< <Cp Nn (s),,b)
Var ph..... (V)
+
where the last inequality comes from the definition of [V], in 17
51

---

Let V V -V(Ppeaaa (Ph.s.a.p v)
we have
pe
(V) = P.a.a,bb V V)
Ph h.s.a,bbl (V V) + (Ph Ph b. -) (VoV)
Var po h.s.
(V) + [ p,,,aa P Ph. h,a,a,)) 112 2/2
+ (Phoaa 0o
Phoaad (VoV) (174)
(Vo)))
where the last equation holds since
Ph R.s.a,b (V /oV)=
Ph h,s,a, (DV-(Ph.s.a) (Phss,a [V (V-((P (Ph.sa,)V) 1])
PD h.s,aabb 6 (V o V) 2 (Ph.s.aiV)) (Pn (Ph.saos) + (Phisaa.))
-Ph Phis.a,b (IV - (PhisaoV) 1/ IV (Phanav)) 11) (PR (Pheact)
2 (Ph (Phaass)) V) (Ph
Phaaaa) (Ph ()
Var po
(V) + [ h.,,a. Ph, V1.
Analogous to 173
with probability exceeding 1 -
[ h.s,ab Ph. b
(V [VoV) s Cap
1
Var Varpp. po Phin. (Vo V) log
KH
+
C.Hllogg log KH 8 Nn ())
Nú (s, a)
8
H²
KH C log KH 8
log
S <Ca Nv (s,
Varpa, a (V) log
No (s,
(175)
where the last inequation comes from the fact that
Va aa. h, h <
p a.
V VVV.VVV S 22 hea (VoV) = Var po, hinia (V).
Employing 175) we further bound (74)
Var hino (V) <ar pa
(V) + [[
Po v
122 log KH Var po
KH (V) + Call2 log
+ Cup
8
Nn (8, b)
N₂ (8, a, b)
C2H log KH
Var pr han
(V) + (Ph...a
5o Ph.s.aN) v1²
Nn (s
C2 log 2N
KH 8 b))
Varpp
(V)
2
where the last relation holds due to the AM-GM inequality. Therefore, we obtain
(C2 + 2Ca) N₂ (s,
H² KH
Var po Ph (V) E 2Var po p (V) (V)+2 R.s.a.b
5o V1 (P
5 (176)
Combining 176) and 173). we derive
v 0 (C +2,) H log KH KH
207
KH + (V)
(Ph - Po V
Var
No. (s,a,
his.a.b
N₁ (8,
2C3
log 1 (......
KH
p0 ph. V
CaH log KH N₂ (8, a, b)
No (8, b)
(177)
52

---

Next, we consider two cases, i.e., Nu, (s, a. b) S first case of N₁ a) I 8C4 5.
1
log KH and N₂ (s, > sC
1
log KH.. In the
8C;
log KH 46 is valid since
inf
PV
inf Pe (Ph (Pinaa))
PV
max OrE ae(cunn, m(x), V(+)
(P Ph. Pho.a.)
Pellot (Ph, (Ph.a.,)
H Hog KHH No (s, a,
S 2H 2H =
(178)
In the second case of No (s, >
1 log KH it follows from
177 that
808
(Ph.aa Ph. p..aa, )
2
1
(PD n,s,a,b Ph. V1
2C7 Var pr h.a.a.s
(V) log
KH
No (8, a))
C4 + +
KH
Hlog 8
Nn (8,
which, by arranging the terms, leads to
8C3
KH
PPh (hh.. Dh R.eo S
Var po P......
(V) Volog
Nn (s,
C4 VC² (C² 2C4)
KH log 6
+ 2H
(179)
N  (s,
Combining (122 and 179p. obtain
8C2
KH (V)
inf
PV
inf (PR (P
PV S
Var hes.a,0
PEt
PEL"
Nu (s)
8
+2H C4 + C7 (C} +24
KH log
(180)
N₁ (s,
Joining these two cases, conclude the proof of (46)
G.1.2 Proof of
We consider two cases, i.e., N₁ (s, a, b) first case of N₂ b)) < 1607 log
< 16C log KH and N₂ b) 2 16C7 log & 47) is valid since
8
KH In the
KH 8
H2 log KH Nn (s,
Var po P.....b (V) < =
KH In the second case of NA (s, b) 16C? log
3 we have
Var po b
(V)
Var po R (V)
po Ph...a.)) V12 -(ph, (Ph,
Po ph..a,t) (V (VoV)
H2
KH
C2H KH
Varpo po
(V) (V) + Cay
Var po h.s.o. (V) log
No. (s,
N₁ (8,0,b)
KH (V) (Cf/4 C4) 1!2 log
2Va po s
8
No (8, a,a)))
112 log KH 8
2a h.ea.
+V)+0
N₂ (s, a,
where (i) comes from 174), (ii) holds due to (155 and (iii) based on the AM-GM inequality.
Combining the two cases, 47 holds and Lemma D.I. is proved.
53

---

G.2 Proof of Lemma D.2
Assuming that (8, a, b) 2 2x (s, b). then we can obtain (s)) 2 Veua
(8), since
4
V h (s) = E a (s).omuT()) (+)
@ (s, as)
@h (s, b)] 2 (o) [ (s,a,
VABeot (8);
2 (s)
h
where (i) holds due to the fact that D vit and (1 v is the Nash equilibrium of Q% (s, b) Hence, we need to verify
(s. 2 2 (s, b),
(181)
which can be proved by mathematical induction. Specifically, (181) holds when = H + under the trivial fact Q+++16 (s, a, b) QH a, b) A x B at some time step E [L]. According the update rule in line 4 in Algorithm 2 (881) exists if Q7 (s, a, b) H because Q7 (s, a, b) H 2% (s, a, b). Besides, in the case of (s, a, b) O, have Bn (s,a,b, b, 1 h+1)
Suppose that 181 holds for all (s, a. b)
H, leading to (s, H Qi 2 (s,
Otherwise, for a. b) > 0. @1 (s, a. b) is updated as 2 (s,a,)) =F -F, +
peu inf (Ph.....)
PV h+1 + Bh (s, b, h++1)
28 +
inf (Pa
PVt h+1 + Bh (s, b, V
PEU
inf
PV+
inf Pello (PR
PV h+11
Pelrot(An (Ph
h+1
28 (s, +
inf peuo (Ph.....))
PV PV +0
as,
inf PEU (Ph.n..t)
PV..Biot h+1
+0= +0=Qh 2, (s,
(182)
where the second inequality holds due 488 in Lemma D.I
D.I and the last equality comes from the empirical robust Bellman equation (30). Together with the case of h H + 1, we complete prove Lemma D.2
G.3 Proof of Lemma D.3
Following the proof by Lemma 3 in 34
we bound min,es 1it (s) and max.es Vs+(s,..
(s). Specifically,
min Vit (s) min E
(s,
(a.0)) xut
PV + 3h (s, Piote)
min E (a.b)) xux SES
bs,
inf P (Po
20+ + min
4+ (3) +0,
(183)
h+1
#ES
where the second equality valid due the update rule in line 4 in Algorithm 2
Similarly,
V max E,
Q (s,a,
max EES
(o,b))m;, x
#ES
pV+ + Bn (s,a, b, Pioti)
max E, #ES
(o, Xtn
Fn +
inf reus peu (Ph....))
max
inf
PV. H.
(184)
(sxx,))SxAxX P (Ph.na.))
54

---

For any h E [H], there exists at least one state sj that satisfies V (s%)) = min V (s). Further- more, for any accessible uncertainty set o+ > 0 and (s,a, b) E S x A x B, we define an auxiliary vector P/ h.s,a.b E ERS by reducing the values of several elements of Pn h,s,a.b strictly, namely,
S P Phaaa I Raa and Σ Ph.,ac(8') Ph Ph.).a,()'))= #'ES
| Phoa.
Ph P...oabl = =o+
(185)
Let (, represent an S-dimensional standard basis under sh. We can derive that
2 Pha + ot [[,]]] .h...../ |1,
1 2 Ph.a.a.b - Ph...., ||, + 2
a [4:i]] ",, S Sot, (186)
where the first inequality valid since the 'distance" function (e.g., TV distance) satisfies the triangle inequality.
Therefore, we can conclude that P h. + + [mx]] Euo (Phmar) and Pk Planas a distribution vector based I86). leading to
+ [Mag]] is
inf PEtt" (PR
PV
h+1
(Phiaa to [linl Vit
$ Pr blll lloo + +o-
max Viti(() a sES
min D (8);
(187)
SES
where the last incquality holds since
" EPhraals
E
(PD (P.naa - Ph (h)na((s)) + ΣEP pb Ph (hss, ot.
(188)
Putting 187 and 184
together shows
max SES
V (s) 11+
max (8,a, (s,a,))ESxAr pette
inf
PV+ h+11 + H
+++ (1 -
max SES
(s) + + min Dztt (+). #ES
(189)
By substituting 189
183).
readily follows that
max
V
min SES
4 A
SH + 1 + (1 o max D
h+1 (8) + a
min Ditt (8) - min V (s)
ES
SES
sES
aES
=H 1 (1 -+)
max D+ (8)
1+
min +
SES 1+1 (8)
$5S
SH 1+ (1 -ot)
1 + (1 (1-o+)
V 2
min Vitt2 (s)
max
SES
SES
II 11)
(1 ot)
(190)
a+
which, combined with max,ee Vyt minge 1 (s) H, conclude this proof.
G.4
Proof of Lemma D.4
First,
we
introduce auxiliary
values
and reward functions to control
Dt Endeess dp." (s, nd ()) (o), (V) as below:
for any time step
mm min.es Vrr (s): the minimum value of all the entries in vector Vi+.
W = Vt 1 truncated value function.
pill (s) (1.)))- b): average reward function.
55

---

pT rf +
(V:
1: truncated reward function.
Applying the robust Bellman's 's consistency equation in 30 gives
V = V +
p.m
pl .e¹ + P 1 Vit1 20 N² V.mi
8/. :v¹ + Piint 1 Vit + ( 1- - p/m1)
Vm 1 + 23
p. + Pilnt. 1 Vit1 - 1.m 1 + 2,3 :
.T Pi
1 V/41 + 2.
(191)
where (i) follows from the fact that
+ ((a,)))((((())))))))))))))
inf
141 + 300)
(8)
peu (Po (Pom...))
(i) Spae
Spue (s) + ((())))(((()))))))
inf (penair)
PV#+1
PEt
inf PEU
PV
inf PeUo (punta (Ph.nii)
PV. i41
+ x( (s)
(1)
S ppe (s) + E(a.)) (s))
pint
D+ i+1
+ +2 (s)
(1))
(s) + Pint 1+1 + 2035 (8),
17 V+
(s),
(192)
(ii) is valid under the notation
P. = argmin
Pet (pe...)
PV 1+1
(193)
plat. V and (iii) holds under the notation as plut, = ((a (o)) f.a. and the sequence as
Pint.y E SRS, Besides, (i) in 192) exists due to 48 in Lemma D.1 for Ni(s, b) > 0 and
pet inf (PP)
PV+ H1
inf (Pe
PV
for ( S H
(s)
Ni( = (194)
Pet
Then, we have
((ab))((u(())) Var pint.
(Viti)
Var p
(v/ (1)+)
-E (1)) (s))
1/t11) (Pintay
Vi o (pirad 1+1)
(V/+1
1//11) - (Pint Dz o (pint. P.
Baaab)) (x))
1+11
(1)
1+11 1/411)
( 1/111) (Pilnt (
Vinf.V
(V/,, o Vi.1)
V(s) o 17((s) + Vs(s o 1/((s) - P 1i
i,s Vini)
P.
= i,s
Vinf.V
(V/42 V/41)
V/(+ 17(0) + (R/(6) (Pinn (itt))tt))))))))>)))
(V/(()) + (pint P Vi+1))
(1) Vint.V
(Vit1 ((1))
(/(5 o 1/(() + (77(()+ + (r (i/(s) + ( vit1))
(iv)
Pinf.V
(V/42 o Viti) 1/(s) o 17(s) + (|1:11 00 + +| (1
2, :0' (ss + (195)
56

---

where (i) follows from that Var pint. (V - b1) = Var pins (V) for any value vector V E R and
scalar b, (ii) holds since
(Piiat Vit1)
(Pinia iia Pitz)
E (a
(Pint vit1) B(a.))
(Pinta 1/+1))
2B (1))
(iii) comes from 191 and (iv) arises from P.T r4 S 1 due Consequently, combining 622 we arrive at
V. 1.. 20 by definition.
Σ
ppll"in"" (s,
biar inai i+1)
(V++1)
(x,b)ESxB
Σ pPuller (a) Var plater (Vit1)
EES
Σ deuetee (s) (Pint.v (V/+1 o Pit1) (1(s) o (s()
#ES
-|1/441 1a)) (204t (8)
(20 +))
BPite (s)
Pint.V (Vi+, o Pi..) (i(s) + (| + +110-111
SES
|?!1 +
-|| |
Σ apmn" (3) (s)
SES
(.. (8)
dP (7(())((())))) + (|1:11 + +1[2=111)
Vitz Σ apiu"ii (s)) (s)
SES
Σ
pant.ur ++1
(s) (8) ((())))(((())) de.e (L) D(()) + (/|: + +1(%111
EES
+ -| Σ dpl'r (3)
+ 2
(196)
(x
Besides, under TV distance, we have
pa
(Vit1)
(VZzi
Var haad (Vi+1) Var pint.v (Vitz)
< p0 L,,aab - -pinf,r /|,
|
- + / | 12 (HH+1)
|i (197)
where the last inequality comes from Lemma D.3
57

---

Therefore, we derive
q (s)
Va
(Vit1)
141
haad
1= (s,0)E8xB
H
pf (8,
(V++1)
6+1
(x
Bi (s),b)
Var
(Vit)
1+1
Var p
i.... 1+1)
(V+
1=1
(5
11
(11:
+ +
Σ SES
df (8)
(s) +
+ + +2) Vi+1
1=1
Σ
P N² H++
(o) (5) (s))())
H
(H (1- H-1)
minl
H
Σ
g+
1=1
(x,
H
(H +1 (1 (1
H
+ (H + 3)
min
H
at
1=1
(
H-1)
<4
min
.
gt
i=l (x,
H Σ
[1I+1] (1- (1-1
+ (H
gt
(
2(Ho -1+ (1- ot)
H
det (s)19(())))(((,,=)))))))
S4H min
(a+)2
(s.
2(Hot 1+ (1 (1-oot) o+)")
+ (H + H min
(198)
(o+)2
where (i) comes from Cauchy-Schward inequality and the (ii) holds since
H
(H 1) (1 (1 --) H(H +1)
#-1
(H + 1)(1 ot)
gt
g+
ot
H(H+1)
(H + +1)(1 (1 - -
at
(ot)²
(H (H+1) 1 11+ o
(a+)2
2H - 1 (1- )
(a+)²
H Proof for Theorem 4.4
To establish Theorem 4.4 present key auxiliary facts, each addressing critical components of the proof and providing essential theoretical underpinnings.
H.1 Proof of Lemma
Since all RMDPs in M(F, 4) are constructed similarly for each w E F and 6 E D we will focus on specific RMDP M M(F, Φ), with the results applicable to all other RMDPs in M(F Φ).
58

---

H.1.1 Ordering the robust value function over different states
Before proceeding, we introduce several facts and notations that will be useful throughout this section. First, for any My and any policy jú, observe the following at the final step H + 1:
E MUN:
V
Vū.o".ee0 (.) O.
(199)
Then for step H, we can easily verify that
W: VHl ()) Ba-ān(-1a)
(n(s,a) +
inf Pet (P
PV i50 H41
=1 (200a)
M: v)()+ -Bawānt-le rn((,a)+ +
PViloo .10
inf Peu (Phie
0, (200b)
which holds by (199) and the definition of the reward function (see indicates that
(87) The above fact directly
Ex min 8ES
V .f0 (3) = V
(m0)) S V
v < V/ 3.
(201a)
V(s ((,,5') EN V VãLo 51 (i(
(201b)
Then introduce a claim which we will prove by induction in moment as below:
8(h,8,8) 8) E [H]
M N
V .5 (. (m²) S /Vi. (.((s) V < ViL .f (80)
(202a)
((s,s))ENN) V f ((((s) V (s))s))
(202b)
Note that the base case when the time step is H + 1 is verified in 201). Assume that the following fact at time step h + 1 holds
v(s,5) E MxN: min Vūoot 8ES h+1
./
V 3.0 (mg) S V.jiat < Vii (s'). h+1
(5)
(203a)
(1,
V a k41
(s)
f (s)).
(203b)
The rest of the proof focuses on proving the same property for time step h. For RMDP MI M(F D) and any policy ju, we characterize the robust value function of different states separately:
* For state E N: we observe that for any E.
vil J.ō = Eampp((1)) an(s,a)+ + inf
PVB S. PEl
+ Earpitt-1)) [p (p avvaat (i((s) (s) to ymottil (mf)
(mrr)
=1+ a V)ti (3) + to vvii if sf0(m)))
(204)
where (i) holds by rn(s,a) = for all 8 E N (see 88 the fact that minges Vāat (:)(3) = vi
(m()) induced by the induction assumption (cf. 203 and the definition of pi s,))) in 190). and the last equality follows from pf s, a) for all (s,a) E N Aone. Resorting to the induction assumption in (003) we have
141
V(s,s') E NN yuaa .1. (. viaa (.. (s
(205)
59

---

For state my: first, the robust value function at state my obeys
vū.aa (my) V
5:
ra(m),a)) +
inf PEUr (Phimy.a)
PVBa !5 .510 h+1
h
@ + jun (pn my)
PVBia* $1.0
inf peup (Phimyith)
+ Mnn (1 on mm))
inf Pello (P/ (hhmy.a-o
PVñaa :f.0 h+1
(
(dn my) V yiu (m1) + (1 - -piul) Viin 110 (m/))
Th (1 Φn mt)
(nz) (: (1 -pmtt) Viiaa V J. (mp))
h+1
(ii)
mi V.f
V fi. f.0 (1z) + (1 m R. } Vnrt ..00 (m)))
(206)
(1 v S. (nf) + V S. (mç).
(207)
where (i) uses the definition of the robust value function and the reward function in (87) (ii) uses the induction assumption in (203) that the minimum is attained by picking the choice specified in (9T) to absorb probability mass to state m, and (iii) holds by plugging in the definition (93 of m..e R.f. Finally, the last inequality follows from the fact that function
[(m) == mm mVVa .f (nz) + (1 m)) - ((0(m))) is monotonically increasing with m h+1
since ViJ.ot. .f (ny) (f
Vüla .. 5.0 (my) (see the induction assumption (203) and the fact
mf... R.S.0 < - o+.
Combining the above results with (05). we confirm the claim in (02
H.1.2 Deriving the optimal policy and optimal robust value function
We shall characterize the optimal policy and corresponding optimal robust value function for different states separately:
For states in M: Recall (06)
v J:0 (m)) mh J. f (ng) + (1 m.....00 V
F. pit.atfee S. 5:0(m))))) (my)
(208)
and the fact V.l.o V (nz) > vūão* .f f. (my) 202 We observe that 208 monotonic- ity increasing w.r.t. m. m... and m/ R.S. is also increasing in (un(d,, |my) (refer the fact
jun > iuf since p 2 gi see (99) and (91p). Consequently, the optimal policy and optimal robust value function in state my thus obey
wh E [H]:
1th f (on m,) = 1,
p v 1 (my) (m((m)) =piufy V (nl) + (1 (1- (1-p virat
.6 (my). (209)
For states E N: Recall the transitions in (98) and (86). Considering that the action does not influence the state transition for all states E N, without loss of generality, we choose the robust optimal policy obeying
V:
T f (on [s)
(210)
H.2 Proof of 105
With the initial state distribution and behavior policy defined in 197. have for any MDP M
d p (s) = (s) =((s),
60

---

which leads to
V(my,a) a) E EM x Aone : d (my, = 2 20(m))
(211)
Along with df pe. (nz:a) a) = = 0. 105a is proved.
In view of 188 the state occupancy distribution at any step h 2, 3.... ... .H obeys
(m²) 2 P (SA = 8h-1 = m,;
d h-1
pa.
(my) [7 - +
Ph-1 (1 Φb- 1 p)]
h-1
2 R-1 (m/) (1 - p p A) 2 ... ...2 ch dh. pe
pad
(m)
p -A)
j=0
# m(m))
2 c p (my) 1 p- - A
(212)
2
where the last line makes use of the properties and A in (1O) and
(1 (1---
(1
1
2 2
2H
2H
provided that 0 < 02 < 1. In addition, as state n is an absorbing state and state my will only transfer to itself or state n at each time step, we directly achieve that
po
(m²) S ب. (m²) S S ag. (my) S ((m)).
(213)
For state ny,, as it is absorbing, we directly have
dh po.s (ng) = P {sh =y sh-1 = ny; 2 d-1 (n²) 2. ... 2 d.. pa.
po.s
(nl)= = @((n).
(214)
According to the assumption [104.
it is easily verified that
pe. (n²) S 1 S 2g(ny).
dn
(215)
Finally, combining 212
213
3
214b.
215
the definitions of PE s,a) a) in (88 and the Markoy
property, arrive for any (h,
H S.
((s)
< dh
po.
(8) S 2g(s),
(216)
2
which directly leads to
((6)
S dr.
po.s
(8, a)
(a) po.
5 e(s).
(217)
4
H.3 Proof of 107
Examining the definition of C in 20 we make the following observations.
For h = 1, we have
min {dht (x, 7SA
max P)ES, x Arn xXx (Pe)
Pn. (8,0)
min (1r. (s.
(st.P(s. 01): ISaL
max (s. (PP))MMX(P(PP)
d. po.l (s, (1))
1 (s. (x)P) Ad PO.J (1,
max
6ii
1
max
C.
(218)
SEM
2SA7(s)
where (i) holds by d (s) p(s) 0 for all E N (see 106 and 1 (ón {) 1
-+. "
for all (s, h) E M x [ (see (95),, (ii) follows from the fact that d (1, = for all
s M, (ii) is verified in [105. and the last equality arises from the definition in (03
61

---

Similarly, for h = 2.3,... H, we arrive at
min fih (8, a), TSA
(s,a, Ann (P6)
max
pn. (s,
min {d
(d (5, @nds 15x
①
max
(s.P) (Po)
dh (s, @h)
(s. P).M (Pe)) AS Poil (b)
max
(s, Ad
(ii
max
REM 2S Ap(s) = 2C,
(219)
where (i) holds by the optimal policy in 195 and the trivial fact that (s) 0 for all 8 N (see (106) and (98). (ii) arises from 1055, and the last equality comes from (103)
Combining the above cases, we complete the proof by
C S
min (
(s, (5A I C.
2
max (N.ss,, SSm Aom (Pe)
n. PG.J
(8, a)
H.4 Proof 112
Recalling (94a) and 96
first consider general form
Vi v (my) Vulao appiat...000 3. (m,)
=p Vnra 1.0 (ng) + (1 ( (m,) (m,))
S:
h+1
h+1
(mf intisvviia S: (:((n)) + [1 al- 1.
viooo S. (m
h+1
h+l
(pint miB..10)
Vh4 (mg) + +m Tio (vrsr :fd (nz)
(verot
h+1 3. (10(m)))
+ (1 (1-pint)
varot wi (:0(m)) - Vh41 w1 ( (10(m)))
(Dine mmy mi..ii)) vida"" if (m)r)
Vh+l
=mh 3..i0 (V ((()))) - V (n)) + (1 (1-p1) (1-p (vaia* (v.rootiso iiit inddd (m,) - Vht1 S (m0)
(nee m/ ) V (yx.ot.:0((n))) Vi+t1 :. (m())
2(1 )
(v (.0
"/
-f((m)))
h+1
me my m
(v Vitt1 (:
21 )
(ve.ot
(v*.r) ..0 (m²) ( :5((m))))
1 [p 0) (-1m)) - (.ll-
(n0) ( Vn+1 .1. (m(())).
h+1
(220)
where the last inequality holds since
pint m/
(p inf - -nin)) (1-x)((- (
(p 4)(11 - -iin mm))
= 5 (p -g)(1 1 -Øn(onn (my) + Fin - on my))
(p 4) 1 [.
(1Imm)))
(221)
with the first equality holding by
93 and the second existing by 91
62

---

To further control 220p, we have
Via + ..0 (nz) (12)
V/2 or S. (m²) -1 (1 - ot Wiit Ni0 (mz) + o V wnd (mp)
V w1 (nz) + (1- -1-p"()) wi (i((ma)) (n)(
h+l
=1 + (1 - punt - -at) (v=-1" -5.0
( (.0()))) vana"
So ((0m))))
1 + (1 (1p)) p) (Vitt S1 (((((())) - Vn+1 Vntaa ( (:0(m)))
H-h
Σ ()- 1=0
(222)
where (i) follows from Lemma E.2
and (ii) holds by respectively:
91
Then, we consider two cases w.r.t. the
uncertainty level o+ to control 222
When O <o< S Co
Recall p 9 if S
ea 2H
In this case, applying 222 we have
2H
V
Via 5.0 (nz) (1z)
Vi (:00m))))
-1- 2 Σ
H-h
1 (
)
1
H1h++
202 h +
(223)
H
02 H
1=0
Here, the final inequality holds by observing
(- (-2(H (1-1)"/Aa" Sexp
(1-1) 02 1-h+1
h h 1)
202 H h + 1)
S
(224)
H
311
where the first inequality holds by noticing < 2 and then 1 - S exp( II), and the last inequality holds by exp(-2) < 2x for any 0 S S 2.2
Plugging above fact in 223 back to (220. we arrive
ViA 11 (m²) - Vi S (mn)
2 (1 - ) (Vi-1 1 (mr) - v poat.rre .f (m0)m)))
1 + (p 9)17 (-Imy) (-
pin ( 20 202 - -h+11
(225)
3
Then, invoking the assumption
H
H
Thn ( (m))) - -m% (- 2
(226)
g
in
111
and applying (255)
recursively for l = 1,2, ,H
,H yields
Vi
S.
(m²)
-f:0 + (m)))
H
p
) ( (H - h + 1)|17 mm))
h=1
(1) 02
C1 h-1 (p (H h 1) 5:0 my) -
H
H
(p g) (H h + 1)]l f.0 (-1mm) - (m))mmm))l
h=1
"
h
f.6
H- (-1my) Pu
H//6J
(iv)
2h
>
[H116] (LH/16) +1),
(227)
6
63

---

where (i) follows from 1 --p -p'nf 21 - p = 1 B
and (ii) holds by
H b vh E [H] : (1 / |ー (1 H
(228)
as long as S 2. Here, (iii) arises from the definition of p. q in (99; (iv) can be verified by the fact that for any series & mi, m2, has
t m. S Mmmax that obeys Σh=1 my 2 y. one
[mmax//t) /n]
Σ mah
Σ
Mmaxh
(229)
and taking m, = 1| (- my) - 5..
(-1m))] S = mmax and n H. 8.
Consequently, observed from (227). the following inequality holds
2
Vytie" (:0mm)) - v S. J. (m²)
[H/16] [[H/16) + +) 2 c3 >E a (230)
6
for some small enough constant e3 and letting A = cgH
When C2 < a+ S 1 - co. Similarly, recalling p- = (1+ + q ot if if
ca and invoking 2H
2H
222
gives
H-h
vioa J. (1r) - vro J. (:0(m)) = Σ p)- Σ
1
(1+ c
ot)
H
j=0
j=U
1 1 (1 - (1+ + H )at H-h+1
(1 m lot +
H
0/ c2 -1 h+11) 1)
(231)
30 H
where the final inequality holds by observing
(1-
C1
o
11
++1
W exp
- (1 1+ C1 o (H - h+1))
H
H
C2
(1+ (H h
exp
211
(1+ CI C2 (H
(2 11
< 1
H)
(232)
3H
Here, (i) holds by observing
02
< a+ and the last inequality holds by (1 + #) s 2,
2H
C2 S 2. and the fact exp( (-x) S 3
2
for any S x } 2-
Plugging (23T) into 220 gives
Vi SS (m))
V. (m,)
211 )
(ve (my) - vil.at 5:0 (m²))
(Vi-a" .:
h+1
(p - n 111i (- mmy) - - 62 (H h + 1)
+ 2
(233)
30 H
Following the steps to achieve (27 applying 233
recursively for = 1,2, H gives
Va S (m²) - Vii.0* S. (my)
H
jutth-1 (p-
c2(11 h + 1)
11, 5. (:) /my) - 7.
6a+H H
h=1
(p
ci h- (H - 1) 5:00 mmm) - (11mm))
6at + H
(i)
H |6] (1 [H/ + 1),
(234)
12o + H
64

---

where (i) follows from 1 - p'n = (p (p=
= 1 o and (ii) holds by letting C1 S 1/ and following the same routine of (227). Consequently, 234 yields
V. (m,) v/..0'
5: (m)) 2
[H/66] [[H/16] + 1)
CAH
o+ >
12o
(235)
which holds for some small enough constant e1 and letting A a+g C
65


Reviews:
[{"review_id": "lxZIbPL8tf", "reviewer": "Reviewer_S3RM", "summary": "The authors of this work develop a new lower bound on the sample complexity of robust MARL. They also present an offline algorithm nearly whose sample complexity is near optimal based on the lower bound.", "questions": "It is known that computing robust policies and even approximating them is NP-hard in many regimes. What is the time complexity of your algorithm and do the authors foresee a potential tradeoff between time complexity and sample complexity for robust settings? Also, do the authors believe their results could potentially extend to uncertainty sets beyond (s,a,b) rectangularity? In particular, other works have been able to handle more complex uncertainty sets through a relationship with regularized Markov games.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "The brand new lower bound is very significant to the robust MARL literature, and the near-optimal attaining algorithm presents new ideas that push the field forward. The primary downside to this model is the adherence to the (s,a,b)-rectangular model of uncertainty, and the potential computational difficulties that typically arise in such works. Despite these downsides, the results presented are still significant.", "was_revised": true, "final_justification": "Overall, I feel very highly of the paper. The robustness literature for standard RL has been very rich, but the literature for MARL has yet to catch up. Much of the robust MARL literature focuses on the planning setting, with only a few results on the sample complexity. This work nicely fills this gap by not only giving improved results, but also giving optimal results. The lower-bound provided not only elevates their proposed algorithm, but also gives new insights on what is possible in the robust MARL regime, which is a significant theoretical discovery. The main downsides of this work are the focus on (s,a,b)-rectangularity, use of NE concept, and high time complexity, but I would argue these plague many of these game-theoretic approaches, so making progress on the orthogonal issue of sample complexity is welcomed and moves the field nicely forward until the planning issue is resolved.", "rebuttal": "**Answer to Question about time complexity and the tradeoff between time complexity and sample complexity**\n\nWe thank the reviewer for this important question. As the reviewer mentioned, computing Nash Equilibria (NE) for two-player general-sum games is PPAD-hard. Since our algorithm solves an NE at each horizon and state, its overall time complexity is also PPAD-hard.\n\nRegarding the tradeoff, there does not exist a direct tradeoff between time complexity and sample complexity, as the main computational bottleneck is NE computation. A potential aspect of tradeoff could lie in the number of NE computations required by the algorithm. In this regard, the number of NE computations in our algorithm is $HS$ (with $H$ as the horizon and $S$ as the number of states), which is optimal. Therefore, our work primarily focuses on improving sample efficiency, as the time complexity per NE computation is dictated by the underlying hardness of NE-solving itself.\n\n**Answer to uncertainty sets beyond $(s,a,b)$-rectangularity**\n\nWe thank the reviewer for this valuable suggestion. Extending our framework to uncertainty sets beyond $(s,a,b)$-rectangularity is indeed an important direction. In particular, KL-divergence-based uncertainty sets offer a principled connection between hard robustness and soft entropy regularization. To extend our algorithm to handle KL divergence, two key aspects must be addressed.\n\nAlgorithmically, RTZ-VI-LCB can be generalized by replacing its robust Bellman operator with an entropy-regularized (soft) Bellman operator and solving for a \\emph{regularized} Nash equilibrium. Additionally, the data-driven penalty term would need to be modified. Instead of relying on the empirical variance $\\mathsf{Var}_ {\\widehat{P}^0_ {h,s,a,b}}(\\widehat{V})$, the penalty should incorporate the minimal nonzero transition probability $\n\\hat{P}_ {\\min, h}(s, a, b) = \\min_ {s'} \\\\{ \\hat{P}_ h^0(s' \\mid s, a, b) : \\hat{P}_ h^0(s' \\mid s, a, b) > 0 \\\\}$.\n\nAs for theoretical analysis, this generalization would require a different complexity characterization. In particular, the sample complexity would depend on the smallest positive transition probability $P_ {\\min}^\\star = \\min_ {h, s, a, b, s'} \\\\{ P_ h^0(s' \\mid s, \\mu_h^\\star(s), \\nu_h^\\star(s)) > 0 \\\\}$ under the optimal robust policy, as well as a burn-in cost condition on the smallest positive state transition probability $P_ {\\min}^{\\sf{n}} = \\min_ {h, s, a, b, s'} \\\\{ P_ h^0(s' \\mid s, a, b) > 0 : d_h^{\\mathsf{n}, P^0}(s, a, b) > 0 \\\\}$ of the behavior policy.\n\nWe will include this discussion in Section 5 to clarify how our algorithm can be extended to more general uncertainty structures, including KL-divergence-based sets."}, {"review_id": "1qBgBausEY", "reviewer": "Reviewer_V9XV", "summary": "This paper addresses robust two-player zero-sum Markov games (TZMGs) by introducing the RTZ-VI-LCB algorithm, under the offline setting.", "questions": "(1). Can you explain the major difference of your method compared to [a]+offline LCB approach for robust RL?\n(2). Can you connect your result together with the generative model setting? Namely, if the dataset is generated based on a uniform distribution, what will the $C^*_r$ term become, and what is the resulting result? And how is that result compared to [34]?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "S: (1). Robust Markov game is a very interesting topic with growing research interests. \n(2). The paper provides a rigorous theoretical framework, including upper and lower sample complexity bounds. The upper bound is near-optimal. \n\nW: (1). The major weakness is on the limited technical novelty of the work. The algorithm is an direct extension of [a], together with standard LCB technique for offline RL. \n(2). Some references on offline single-agent robust RL are missing, e.g., [b-e]. Also a work [f] on robust games: \n \n[a] Model-Based Reinforcement Learning for Offline Zero-Sum Markov Games\nY Yan, G Li, Y Chen, J Fan - arXiv preprint arXiv:2206.04044, 2022\n\n[b] Distributionally robust off-dynamics reinforcement learning: Provable efficiency with linear function approximation\nZ Liu, P Xu\nInternational Conference on Artificial Intelligence and Statistics, 2719-2727\n\n[c] Minimax optimal and computationally efficient algorithms for distributionally robust offline reinforcement learning\nZ Liu, P Xu\narXiv preprint arXiv:2403.09621\n\n[d] A unified principle of pessimism for offline reinforcement learning under model mismatch\nY Wang, Z Sun, S Zou\nAdvances in Neural Information Processing Systems 37, 9281-9328\n\n[e]Distributionally robust model-based offline reinforcement learning with near-optimal sample complexity\nL Shi, Y Chi - Journal of Machine Learning Research, 2024\n\n[f]Breaking the Curse of Multiagency in Robust Multi-Agent Reinforcement Learning\nL Shi, J Gai, E Mazumdar, Y Chi, A Wierman - arXiv preprint arXiv:2409.20067, 2024", "was_revised": true, "final_justification": "Authors have addressed most of my concerns.", "rebuttal": "**Answer to W1 and Q1**\n\nWe sincerely appreciate the reviewer’s insightful comment regarding the novelty of our work. The study by Yan et al. [a] investigates offline Markov games (MGs) using the LCB approach. Our work builds upon this line by explicitly incorporating environmental uncertainty, resulting in a substantially stronger and more challenging formulation. In the presence of uncertainty, we can no longer solve the value function in its primal form and need to operate instead in the dual space. To address this, we introduce a novel Bernstein-style penalty that ensures the empirical variance estimate (i.e., the plug-in estimate) closely matches the true variance. Through these innovations, we establish a minimax optimal sample complexity that significantly improves over prior results in its dependence on the state and action spaces under uncertainty. While the best existing bounds scale as\n$\nO\\left( \\frac{C_ \\mathrm{r} H^5 S^2 A B}{\\varepsilon^2} \\right),\n$\nour result achieves\n$\nO\\left( \\frac{C^\\star_\\mathrm{r} H^4 S(A+B)}{\\varepsilon^2} \\cdot f(\\sigma^+, \\sigma^{-}, H) \\right)\n$ with $C^\\star_\\mathrm{r}\\le C_\\mathrm{r}$ and $f(\\sigma^+, \\sigma^{-}, H)\\le H$,\nwhich notably reduces the dependence on both the state and action dimensions.\nWe will revise the manuscript to include a discussion clarifying the novelty, stating: \"*RTZ-VI-LCB extends the offline MGs algorithm proposed in [a] by explicitly incorporating environmental uncertainty and solving the dual problem.*\"\n\n**Answer to W2**\n\nThank you for pointing this out. We apologize for the omission and will revise Section 1.2 (Related Work) to incorporate the missing references more comprehensively. Specifically, in the paragraph on Single-agent robust offline RL, we will include the following sentence as \"*Several works [b, c] study offline robust RL with linear function approximation, while others consider various uncertainty metrics such as total variation, $\\chi^2$-divergence, and KL-divergence [d], or operate under more general settings without requiring strong coverage assumptions [e].*\" In the paragraph on Robustness in MARL, we will add \"*Optimal dependence on the action space size $\\{A, B\\}$ has been achieved in recent work from an online learning perspective [f], but the offline robust formulation in multi-agent settings remains largely underexplored.*\"\n\n**Answer to Q2**\n\nThank you for this insightful and inspirational question. Under a generative model with uniform sampling, the visitation distribution becomes explicit; that is, $d_h^{\\mathsf{n}, P^0}(s, a, b) = \\frac{1}{SAB}$. In this case, it is sufficient to choose $C_{\\mathrm{r}}^\\star = \\min\\\\{A, B\\\\}$, which can be readily verified to satisfy Eq. (20). This choice leads to the sample complexity\n$$\n\\widetilde{\\mathcal{O}}\\left( \\frac{H^{4} SAB}{\\varepsilon^{2}} \\cdot f(\\sigma^+, \\sigma^{-}, H) \\right),\n$$\nwhich matches the bound established in [34] and confirms the efficiency of our approach in the generative model setting.\nWe will add a corresponding remark after Theorem 4.2 to clarify this point."}, {"review_id": "w7RAvxrrIY", "reviewer": "Reviewer_A8VL", "summary": "This paper tackles the challenging problem of offline robust reinforcement learning in two-player zero-sum Markov games (RTZMGs), with a focus on tabular environments under partial coverage and environmental uncertainty. The authors introduce RTZ-VI-LCB, a novel model-based algorithm combining robust value iteration with lower confidence bounds. It incorporates a Bernstein-style penalty and a two-stage subsampling procedure to handle statistical dependencies in offline datasets. The paper provides theoretical guarantees by deriving both upper and lower bounds on sample complexity, showing that RTZ-VI-LCB achieves optimal sample efficiency with respect to state and action sizes. The method is further generalized to the multi-agent setting.", "questions": "1. The concentrability coefficient C_{r}^* plays a central role in your bounds. Is there a principled way to estimate or bound C_{r}^* from offline data in practice, especially when the robust optimal policies are unknown?\n\n2. Solving robust zero-sum matrix games is generally PPAD-hard. In your implementation of RTZ-VI-LCB, how do you compute the robust NE at each state and timestep efficiently? Are there computational relaxations or approximations used?\n\n3. Your theoretical contribution is strong, but the empirical validation is limited to synthetic tabular environments. Do you envision obstacles in extending RTZ-VI-LCB to high-dimensional? What are the main challenges in applying your framework to more realistic offline multi-agent domains?\n\n4. The proposed Bernstein-style penalty and two-stage subsampling are key components to deal with partial coverage and statistical dependence. Could you provide insights into how much each of these components contributes to the algorithm's performance and stability?", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths\n- The paper presents a significant theoretical contribution by establishing optimal sample complexity bounds for robust Nash equilibrium computation in offline RTZMGs. The use of robust unilateral clipped concentrability (Definition 4.1) is novel and tighter than previous assumptions (e.g., in P2M2PO).\n- The method is carefully constructed with a dual formulation for value computation, a tailored penalty function, and proofs of optimality across uncertainty regimes.\n- First optimal bound in robust MARL under offline constraints\n\nWeaknesses\n- While the paper is positioned as theoretical, it includes a small experimental section that aims to support the theoretical results. However, the experiments are limited to synthetic, low-dimensional settings with no real-world applicability or comparison to existing baselines like P2M2PO. As such, the empirical section offers limited additional insight and does not strongly validate the practical robustness of the method.\n- The paper could benefit from a short discussion on how to move toward larger and practical domains.", "was_revised": true, "final_justification": "The authors have provided clear answers to my questions, addressing both theoretical aspects, namely, the infeasibility of estimating  $C_{\\mathrm{r}}^\\star$​ from offline data, and implementation details such as robust NE computation and the roles of the Bernstein penalty and subsampling. Based on these clarifications, I maintain my initial score of 5 (Accept).", "rebuttal": "**Answer to W1**\n\nWe thank the reviewer for this valuable feedback. To strengthen the empirical validation, we have added a new comparison against $\\mathrm{P}^2\\mathrm{M}^2\\mathrm{PO}$, a recent baseline designed for RTZMGs. Specifically, we report the performance gap $\\mathrm{Gap}({\\mu}, {\\nu})$ with respect to dataset size across both methods. To demonstrate our optimal sample complexity scaling in the action space, we use a setting with $S = 50$, $A = B = 3$, and $H = 100$, which differs from the configuration in Appendix A (where $AB = A + B$). The new results are presented in the following table, which will be included in the revised manuscript:\n\n| $\\log(KH)$            | $6$      | $7$      | $8$      | $9$      |\n|-----------------------|----------|----------|----------|----------|\n| **RTZ-VI-LCB**        | **3.1699** | **2.1498** | **0.2324** | **0.0819** |\n| $\\mathrm{P}^2\\mathrm{M}^2\\mathrm{PO}$ | 3.5970   | 2.2503   | 0.2404   | 0.0890   |\n\nThese results highlight the superiority of our method across varying dataset sizes and validate the theoretical claims under controlled experimental conditions. While we focus on tabular settings in this work, our algorithm can serve as a theoretical foundation for scalable extensions based on linear or kernel-based function approximation.\n\n**Answer to W2**\n\nThank you for this helpful suggestion. Our current study focuses on tabular settings, which provide a clean foundation for precise theoretical analysis and algorithmic development. To scale to larger and more practical domains, straightforward approaches are function approximation methods, particularly linear or kernel-based methods, as explored in prior works, e.g., Refs. [1,2]. These approaches enable generalization over large or continuous state-action spaces while preserving a degree of theoretical tractability. We will include a brief discussion of this extension path in Section 5 of the revised version, stating that: \"*While RTZ-VI-LCB is developed in the tabular setting, it offers a solid theoretical foundation for robust offline multi-agent learning. Generalizing its core principles, such as data-driven penalization, to high-dimensional settings via function approximation (e.g., linear or kernel-based methods [1,2]) represents a promising direction toward practical deployment.*\"\n\n**Answer to Q1**\n\nThank you for this insightful question. In general, estimating $C_{\\mathrm{r}}^\\star$ from purely offline data is information-theoretically impossible. Consider, for example, the degenerate robust two-player Markov game with $\\sigma^+=\\sigma^- = 0$ and $B=1$, which reduces to the standard single-agent RL setting.  For an MDP with horizon $H=2$, whose first step has a singleton state space $\\mathcal{S}_ 1=\\\\{0\\\\}$ and action space $\\mathcal{A}_ 1=\\\\{0,1\\\\}$, and whose second step has state space $\\mathcal{S}_ 2=\\\\{0,1\\\\}$ and singleton action space $\\mathcal{A}_ 2=\\\\{0\\\\}$, [24] has shown it is impossible to determine the sample size required or provide a valid certificate. Therefore, estimating $C_ {\\mathrm{r}}^\\star$ is also generally infeasible in RTZMGs.\n\nFortunately, our algorithm does not rely on prior knowledge of $C_{\\mathrm{r}}^\\star$. It can be executed with any offline dataset and will succeed once the underlying task becomes statistically feasible. Although we cannot determine in advance whether a given dataset is sufficient, RTZ-VI-LCB remains practically useful by avoiding reliance on unverifiable assumptions.\n\nWe will incorporate this discussion near Definition 4.1 in the revised manuscript, adding:\n\"*Estimating the concentrability coefficient $C_{\\mathrm{r}}^\\star$ from offline data is generally information-theoretically impossible, as demonstrated even in the single-agent case by the example construction in Section 3.4 of [24]. Fortunately, this does not affect the execution of our algorithm.*\"\n\n**Answer to Q2**\n\nThank you for this thoughtful question. In this work, we do not explicitly address the computational complexity of solving the robust Nash equilibrium (NE). That is, our algorithm assumes access to arbitrary robust NE solver and focuses on the sample complexity of the overall procedure. In addition, our framework is compatible with any computational relaxations or approximation methods for solving RTZMGs, such as Monte-Carlo sampling (Ref. [3]).  In our experiments, we use the Python package *nashpy* for NE computation.\n\nWe will add the following remark to the manuscript to clarify this implementation detail: *\"In our experiments, the robust NE at each state and timestep is computed using standard NE solvers, i.e., the Python package nashpy. Our algorithm is compatible with any exact or approximate NE solver, including computational relaxations or sampling-based methods. If an approximate solver is used, the corresponding approximation error will be introduced into our theoretical analysis as an additional term.\"*\n\n**Answer to Q3**\n\nThank you for highlighting this important point. Our current work focuses on multi-agent tabular settings (see Theorem 4.4 and Appendix F) to facilitate precise theoretical analysis. To extend RTZ-VI-LCB to high-dimensional cases, a natural direction is to incorporate function approximation, particularly using linear function classes or kernel-based representations. Key challenges in this setting include ensuring concentration and coverage conditions in high-dimensional spaces. As responded to Weakness 2, we will include a discussion of this extension path in Section 5 of the revised version.\n\n**Answer to Q4**\n\nThank you for the insightful question. \nThe Bernstein-style penalty acts as an adaptive, variance-aware term. In particular, it significantly improves the algorithm’s performance when the actual variance is much smaller than the trivial bound of $H^2$. By leveraging a tighter, data-dependent penalty, the algorithm can achieve improved performance.\n\nIn contrast, the two-stage subsampling is primarily introduced for theoretical analysis, specifically to handle within-episode temporal dependence. In practice, we have observed that this subsampling step is not strictly required for the empirical performance. However, how to rigorously remove this step while maintaining theoretical guarantees remains an open problem for future research.\n\nWe will clarify these insights in Section 1.1 and discuss the practical and theoretical roles of each component in more detail.\n\n**Reference**\n\n[1] Nika, Andi, et al. \"Corruption-robust offline two-player zero-sum Markov games.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2024.\n\n[2] Lim, Shiau Hong, and Arnaud Autef. \"Kernel-based reinforcement learning in robust Markov decision processes.\" International conference on machine learning. PMLR, 2019.\n\n[3] Ponsen, Marc, Steven De Jong, and Marc Lanctot. \"Computing approximate Nash equilibria and robust best-responses using sampling.\" Journal of Artificial Intelligence Research 42, 575-605, 2011."}]

Author rebuttal:

Meta-review: This paper gives a near-optimal sample-complexity algorithm for offline robust two-player zero-sum Markov games, along with a matching lower bound. The theory is clean and addresses an important gap in robust MARL, where offline data and uncertainty interact in subtle ways. The presentation is clear, the assumptions are stated upfront, and the proof techniques look reusable by others in the area.
Decision: Accept (poster)