Sample-Efficient Distributionally Robust Multi-Agent Reinforcement Learning via Online Interaction
Authors: Zain Ulabedeen Farhat
Debamita Ghosh
George K. Atia
Yue Wang
Venue: ICLR 2026 Poster (2026)
Keywords: distributionally robust
multi-agent
markov game
Primary area: reinforcement learning

Abstract: Well-trained multi-agent systems can fail when deployed in real-world environments due to model mismatches between the training and deployment environments, caused by environment uncertainties including noise or adversarial attacks. Distributionally Robust Markov Games (DRMGs) enhance system resilience by optimizing for worst-case performance over a defined set of environmental uncertainties. However, current methods are limited by their dependence on simulators or large offline datasets, which are often unavailable. This paper pioneers the study of online learning in DRMGs, where agents learn directly from environmental interactions without prior data. We introduce the Multiplayer Optimistic Robust Nash Value Iteration (MORNAVI) algorithm and provide the first provable guarantees for this setting. Our theoretical analysis demonstrates that the algorithm achieves low regret and efficiently finds the optimal robust policy for uncertainty sets measured by Total Variation divergence and Kullback-Leibler divergence. These results establish a new, practical path toward developing truly robust multi-agent systems.

Published as a conference paper at ICLR 2026
SAMPLE-EFFICIENT DISTRIBUTIONALLY ROBUST MULTI-AGENT REINFORCEMENT LEARNING VIA
ONLINE INTERACTION
Zain Ulabedeen Farhat Debamita Ghosh"., George Atia Yue Wang
1 Department of Electrical & Computer Engineering Department of Computer Science University of Central Florida, Orlando, FL 32816, USA (za464241, de881780, george.atia, yue yue.wangJeuct.co edu
ABSTRACT
Well-trained multi-agent systems can fail when deployed in real-world environments due to model mismatches between the training and deployment environments, caused by environment uncertainties including noise adversarial attacks. Distributionally Robust Markov Games (DRMGs) enhance system resilience by optimizing for worst-case performance environmental uncertainties. However, current methods are limited by their dependence on simulators large offline datasets, which are often unavailable. This paper pioneers the study of online learning in DRMGs, where agents learn directly from environmental interactions without prior data. We introduce the Mulriplayer Optimistic Robust Nash Value Iteration (MORNAVI) algorithm and provide the first provable guarantees for this setting. Our theoretical analysis demonstrates that the algorithm achieves low regret and efficiently finds the optimal robust policy for uncertainty sets measured by Total Variation divergence and Kullback-Leible divergence. These results establish new, practical path toward developing truly robust multi-agent systems.
a defined set of
INTRODUCTION
Multi-agent reinforcement learning (MARL), along with its stochastic game-based mathematical formulation (Shapley 1953 Littman 1994), has emerged cornerstone paradigm for intelligent multi-agent systems capable of complex, coordinated behavior. It provides the theoretical and algorithmic foundation for enabling multiple agents to learn, adapt, and make sequential decisions in shared, dynamic environments. Its practical impacts span strategic gaming, where MARL agents have achieved superhuman mastery (Silver et al. 2016; Vinyals al. 2019); autonomous transportation, where it is used to coordinate fleets of vehicles to navigate complex traffic scenarios (Shalev-Shwartz al. 2016 Hua et al.) 2025 ; and distributed robotics, where teams of robots learn execute tasks
Lowe et al. 2017 Matignon et al. 2012)..
Despite the remarkable progress MARL, fundamental and pervasive challenge severely restricts its reliable deployment in practice: the Sim-to-Real gap (Zhao et al. 2020 Peng et al. (0188.. A standard pipeline of RL involves training extensively within high-fidelity simulator and then deploying in practice. However, any simulator inevitably fails to capture the full richness and complexity of the real world, omitting subtle physical effects, unpredictable sensor noise, unmodeled system dynamics, or latent environmental factors (Padakandla et al. 2020 Rajeswaran al., (017). Consequently, policy that appears optimal within the simulation can be brittle and perform poorly or even fail catastrophically--wo when deployed into the noisy, unpredictable environment.
This vulnerability to model mismatch is magnified exponentially in the multi-agent context: this uncertainty is amplified through a cascading feedback loop of agent interactions. A minor, unmodeled perturbation that affects one agent can cause it to deviate from its expected behavior. This deviation alters the environment for its peers, who in turn must adapt their policies. Their adaptations further change the dynamics for all other agents, including the one first affected. This can trigger chain of
"The first authors contributed equally.

---

Published as a conference paper at ICLR 2026
unpredictable responses, destabilizing the collective strategy and leading to highly non- stationary learning environment far more volatile than that caused by strategic adaptation alone Paapoudakis et al. 2019; Canese et al. 2021 Wong et al.] 2023). The entire multi-agent system becomes fragile, as the intricate inter-agent dependencies act as amplifiers for even the smallest model inaccuracies.
To enable MARL against such uncertainty, the framework of Distributionally Robust Markov Games (DRMGs) offers a principled and powerful solution (Zhang et al.) 2020 Kardey et al. 2011). DRMG approach embraces a principle of pessimism. It defines an uncertainty set of plausible environment models centered around the nominal one, and the goal is to maximize the worst-case expected returns across the entire uncertainty set. This robust optimization strategy yields two profound benefits. First, it provides a formal performance guarantee: if the true environment lies within the uncertainty set, the policy's 's performance Second, it acts as a powerful regularizer, forcing agents to discover more generalizable policies that are inherently less sensitive to perturbations, thereby enhancing generalization even to environments outside the set (Vinitsky al. 2020 Abdullah et al. 2019
guaranteed to be no worse than the optimized worst-case value.
Liu et al. 2025).
However, despite its theoretical appeal, the current body of research on DRMGs is built upon assumptions that create critical disconnect from the realities of many high-stakes applications. The prevailing algorithmic frameworks fall into two main categories: those that assume access to generative model (Shi al.] 2024: Jiao & Li 2024), which is tantamount to having perfect, queryable oracle or simulator, and those designed for the offline setting (Li et al. 2025 Blanchet et al. 2023), which presuppose the existence of a large, static, and sufficiently comprehensive dataset collected beforehand. These assumptions are untenable in precisely the domains where robustness is most crucial. Consider applications in autonomous systems (Demontis al., 2022) or personalized healthcare (Wang et al.) [018:: Lu et al. 202T). In these settings, creating a high-fidelity simulator is often impossible, and pre-collecting a dataset that covers all critical scenarios is infeasible. Agents have no choice but to learn online, through direct, sequential interaction with the complex and unknown real world. In this online paradigm, data is not a free commodity to be sampled at will; it is earned through experience, where every action has real cost and naive exploration can lead to severe or irreversible outcomes. This necessitates a new class of algorithms that can navigate the exploration-exploiittio tradeoff under the additional burden of worst-case environmental uncertainty.
We aim for robustness that survives contact with reality: agents must cope with misspecification while learning purely from experience. Without simulators sizable offline datasets, existing approaches struggle to bridge theory and practice. This shortfall clarifies the gap we address and motivates the central question of our work: How to design provably effective online algorithms for distributionally robust Markov games?
In this paper, answer the above question by designing model-based online algorithm for DRMGs and providing corresponding theoretical guarantees. Our contributions are summarized as follows.
Hardness in Online DRMGs: We first reveal the inherent hardness of online learning in DRMGs. Specifically, we first show that the online learning can suffer from the support shifting issue, where the support of the worst-case kernel is not fully covered by the support of the nominal environment, by constructing hard instance that incurs an 2 (K min H, II, A: -regret for any algorithm. Moreover, we use another example to show that even without the support shifting issue, the regret can still have minimax lower bound of 1 / K 1I: A:). Here, K is the number of iteration episodes, H/ is the DRMG horizon, and II, A, is the size of the joint action space. These results directly imply the hardness of online learning, compared to other well posed learning schemes, including generative
model (Shi et al. 2025 Jiao & Li. 2024) or offline learning (Li et al. 2025).
We introduce f Í-MORNAVI, novel mosel-based meta-algorithm designed specifically for online learning in DRMGs. Our framework pioneers dual approach that synergizes the pessimism required for robust optimization with the optimism essential for provably efficient online exploration. At its core, f-MORNAVI learns the nominal environment model from online interactions and then incorporates a carefully constructed, data-driven bonus term, B. This bonus term is uniquely tailored to the geometry of the chosen uncertainty set, guiding exploration while guaranteeing that the learned policy is robust to worst-case model perturbations. We further present two concrete instantiations of our framework for uncertainty sets defined by Total Variation (TV) distance and Kullback-Leeis (KI.) divergence.
Framework for Online Robust MARL:
2

---

Published as a conference paper at ICLR 2026
Near-Optimal Regret Bounds for Online DRMGs: We establish the first known theoretical guarantees for online learning in general-sum DRMGs by providing rigorous, high-probability regret bounds for our algorithms. The regret measures the performance gap between our algorithm and an optimal robust policy, thus formally characterizing the sample complexity needed to solve the DRMG. We futher prove that algorithms converge to an 6-optimal robust policy with high sample efficiency (see Corollary ( Our results are significant as they are the first to demonstrate that finding robust equilibrium in general-sum DRMG is achievable in a sample-efficient manner through online interaction, without requiring simulator or pre-collected dataset.
2 PROBLEM FORMULATION
2.1 DISTRIBUTIONALLS ROBUST MARKOV GAMES
A Distributionally Robust Markov Game (DRMG) can be specified as My (M, A, H, (Pilie,,r). where M = {l,..., m} is the set of m agents, = (1,2..... S} denotes the finite state space, A denotes the joint action space for all agents A = A1 x... x Am is the action space of agent i, and H denotes the horizon length. We IShSH with ALAA : S x A > [0,1] I.. Specifically, for any (i, 8, a) E M x [H] x S x A. (8, is the immediate (deterministic) reward received by the i-th agent in state s when the joint action profile is a. Agents in a DRMG maintain their own uncertainty sets of transition kernels P., to capture the potential environment uncertainties in their perspective. At each step, the environment transits following an arbitrary kernel from the uncertainty set.
where A,- = {1, .......... ..}
consider non-stationary DRMGs, i.e., r is the reward function: r =
Drawing inspiration from the rectangularity condition in robust single-agen agent RL [yengar 2005
Wiesemann et al., 2013 Zhou et al.) [2021] [hh et al.. 20033) and following standard DRMG studies (Shi al. 2024| 2025| /hang et al. 2020), we consider the agent-wise (s, rectanngull uncertainty set, due to its computational tractability[] Specifically, for each agent the DRMG specify an uncertainty set P,, which is independently defined over all horizons, states, and joint actions:
P.
Ph P (s, a),
(H)
where & denotes the Cartesian product. At step h, if all agents take a joint action an, at the state shs the transition kernel can be chosen arbitrarily from the prescribed uncertainty set P p an)) We consider the uncertainty set P. i, (s, a) centered on a nominal kernel P*:
Definition (J-Divergence Uncertainty Set). The f-divergence uncertainty set is defined as:
( = {PA E A(S): / ( (7)s,)())s,)))) S p:).
where the f-divergence is f(P,, P)(+),, = Σ ( (s
Pa( (p(("laaa)
8'ES
The f-divergence uncertainty sets with different ff have been extensively studied in distributionally robust RL (Clavier et al. 2023 Shi et al.) [223] Panaganti et al. [202 Yang et al. 2222] Wang et al.) 2024d Zhang et af. 2025). In this work, we focus on TVV and Ki-divereence.
Robust Value Functions. For a DRMG, each agent aims to maximize its own worst-case performance over all possible transition kernels in its own (possibly different) prescribed uncertainty set. The strategy of agent i taking actions is captured by policy n, { S A(A.)) Since the immediate rewards and transition kernels are determined by the joint actions, the worst-case performance of the i-th agent over its own uncertainty set P; is determined by joint policy = {TA : S + A(A) which we refer to as the robust value function V.T.P. and the robust Q-function The for an initial state s and initial action a: Q. (s, A
inf PEP, E.P T at) sh s,aa = and Vx. Pi & TaT(s)) a).
where the expectation is taken over the randomness of the joint policy x and the kernel P.
Robust MDPs without rectangular assumption can be NP-hard solve WWesemann et al. 2013
3

---

Published as a conference paper at ICLR 2026
Solutions to DRMGs. Due different objectives among players, the goal of a DRMG is to achieve some notions of equilibrium (Fudenberg & Tirole 1991). For any given joint policy я. --द is the marginal policies of all agents excluding the 2-th agent. The agent i's best response policy to π- i T-P (TT-)), is the policy that maximizes its own robust value function, the given step / and state s: ( (TT=:xx()PP(( (s). The corresponding robust value function is
T. 1 (T-x) e arg (E n
V -it- (8)
V.. (8). 1.
max
T(EA(A))
The goal of DRMG is to compute equilibrium policy (Fudenberg & Tirole 1991). such that each agent's policy is the best response to the others, so that no single agent can improve its robust value by deviating while the rest remain fixed. Standard notions of equilibria include robust Nash
Equilibrium (NE), robust Coarse Correlated Equilibrium (CCE), and robust Correlated Equilibrium (CE) (their existence is shown (Blanchet al. 2023)), defined as follows:
Robust e-NE. A product policy т E A(A)) x ... x A(Am) is a robust-e NE if for any E S: gaPNE (T, 8) A max;cM V.!1" (PE(()) V,,II' (8) S.
Robust NE ensures that, the agent i's policy induced by the NE is best response policy to the remaining agents' joint policy (up to c). thus no agent can improve its worst-case performance-
over its own uncertainty set P.-by unilaterally deviating from the NE.
Robust &- e-CCE. A (possibly correlated) joint policy π E (AA) is a robust-e CCE if for any 8 E S: gapOCa (T, s) A maxieM [V,i-- (s) Vi, (a) S e. Robust CCE relaxes the notion of NE
by allowing for potentially correlated policies, while still ensuring that agent has an incentive unilaterally deviate from it.
A(A) is robust-E CE if for any E S: gaPCE(TT, A maxieM maxxes, ((ooR (s) S s. Here, strategy modification
Robust E-CE. A joint policy
é (1..))))) for player is a set of [H] S functions from A; to itself. Let e, denote the set of all possible strategy modifications for player i. Given joint policy æ, applying a modification n, which matches æ everywhere except that at each state s and timestep h. player i's action a is replaced by (a:))
yields a new joint policy Φon,
Online Learning in DRMGs. We consider online learning in DRMGs, aiming to compute equilibria (NASH, CCE, CE} via interaction with the nominal environment p* over K E N episodes. Each episode starts from s proceeds with a policy x² chosen from experience, and ends with an update for the next round. We use robust regret as performance metric, which compares the learned outcome to the target equilibrium the presence of model error.
Definition (Robust Regret). Let z be the execution policy the 1tth episode. After total of K episodes, the corresponding robust regret is defined as Regret (HAS,CCCAAS =
ΣK (4P(NASS,,CE,,EE) ,
Notably, if an algorithm has a sub-linear regret, it achieves robust equilibrium as K + co.
3 OPTIMISTIC ROBUST NASH VALUE ITERATION
We then present Multiplayer Optimistic Robust Nash Value Iteration for f-Divergence Uncertainty Set (f-MORNAVD, a meta-algorithm for episodic, finite-horizon DRMGs with interactive data collection. M-MONNVII handles general f-divergences, with emphasis on KL and TV.
3.1 ALGORITHM DESIGN
Our algorithm has the following three stages.
Stage 1: Nominal Transition Estimation (Line 4). At the start of each episode k E [K], we
maintain estimate of the nominal kernel P* using the historical data D {(5,, ai, 8 T=
1-1
4

---

Published as a conference paper at ICLR 2026
Algorithm 1: /MMONAVII
1: Input: Uncertainty level p; > 0 for all i E MM.
2: Initialize: Dataset D 0
3: for episode k 1,..., K do
4: Compute the transition kernel estimator P) a, s') as given in eq. V.
5: Set #+1 (.) V k.p: (.)
for all i M.
6: for step = H ........
h.Pi (s, a) leq. and 2 (s, a) [eq. 6
7: For all (s, a) E S A and E M, update
For all E S, update x by eq. update i.h (s) and ViR h (-) by eq. 9: end for
8:
Receive initial State s E
11: for step h I,...,d ....,. H. do
12:
Take action af. ~ (h(( st) observe reward (s a5) and next state sh end for
13:
14: Set D = ((5), a sh++) 1
15:
end for
16: Output: Return policy nu = {x* 1k=1" K
collected from past interactions with the training environment. Specifically, M-MORNAVI updates the empirical transition kernel for each tuple (h, s, a') E [H] XSx Ax as follows:
(s (s, a,)s (if (s, > 0), and (s (s,
1 S
(ir (ir = 0),
(4)
where (s, and (s, are calculated on the current dataset ID by (s.
11(7, sT.1 = ss),, and (s. = E (s, s')). Note that adopt
''ES
model-based approach that estimates transition kernels. Although this leads to higher memory consumption, model-free DRMGs are inherently challenging due to the non-linearity of worst-case expectation w.r.t. nominal kernels, which makes model-free estimators biased or sample-inefficien (Liu et al. 2022 Wang et al. 2023d 2024c Zhang et al. 2025).
Stage 2: Optimistic Robust Planning (Lines 5-9). The M-MORNAVI constructs the episode policy
R via optimistic robust planning based the empirical model PA: This involves estimating an upper bound on the robust value function, following the principle of Upper-Confident Sown--CCoooneeeeBBuuieee Bound (UCB)
methods. which are well-established in online vanilla RL (Auer Ortner 2010 Azar al. 2017 Zanette & Brunskill 2019 Zhang et al. 2021b Ménard et al. 2021 Zhang et al. 2024b). and this
optimism encourages exploration eessiiisitd action pairs.
To this end, M-MORNAVI maintains bonus term at each episode k, capturing the gap between the robust value function under p and that under the true model. This bonus is added to the robust Bellman estimate to ensure its optimism. Specifically, for each (h, s, a) E [H] x S x A, we set
Qii (s, a) = min (s, a) (s.a)
1,4+1 + 3 (8, H}. 1ittill
(5)
@ (s. a) max (sr a) + o pp (s.a)
B (s, a), 0}.
(6)
Here, [V[ = Per Ep(V] is the support function of V over the uncertainty set P, and can be calculated through its dual representation (see Lemma 7 Pli r is the uncertainty set centered at Pk 5er (s. a) = Pr. E A (Ph, pk
from eq.
(-1s,a sp.}.
Each of these estimates in eq. 5 and eq. are based estimated robust Bellman operators (see Appendix C for details) and a bonus term 3 , (s.a) a) 2 0. The bonus term is constructed (we will discuss the construction later) to ensure the estimation becomes a confidence interval of the true robust value function, i.e., 0. f.
(8, E @Q (s, k.Ph (8, a)), with high probability.

---

Published as a conference paper at ICLR 2026
EQUILIBRIUM subroutine (Line 8). Given robust Q-function estimates 2% (s, a) and Qhe (s, a) for i E M at step h, the sub-routine EQUILIBRIUM E (NASH, CCE, CE} finds corresponding equilibrium (-Iss for the matrix-form game with pay-off matrices {Q (s, heM
(f0th" k. (s, (emm)
T (-18) < EQUILIBRIUM
Note that finding a NE be PPAD-hard (Daskalakis et al., 2009). but computing CE CCE remains tractable in polynomial time (Liu et al. 2021). We follow standard MG studies, assuming EQUILIBRIUM be executed, and mainly focus on sample complexity and statistic efficiency.
We then update the estimation of Vf
V kift i, (8) = Eaann (-1c) ( a) and V. (s) Ea Eaar+((11))) (+1s) O (s, a)
(8)
Note that while the lower estimate in eq. 6 does not influence policy execution directly, it plays a crucial role in constructing valid exploration bonuses and ensuring strong theoretical guarantees. By leveraging both upper and lower bounds, the algorithm performs optimistic robust planning, enabling structured, uncertainty-aware exploration that balances exploration, exploitation, and robustness.
Stage 3: Execution of Policy and Data Collection (Lines 10-16). After evaluating the policy (= for episode k; the learner takes action based on म and observes the reward rh (s a and next state *h+1, which get appended the historical dataset collected till episode k
HARDNESS OF ONLINE LEARNING
In this section, we aim to discuss the inherent hardness of online learning DRMGs from two aspects: (1) When there is a support shift issue, MARL algorithm can obtain sub-linear regret on certain DRMG; (2) Even if there is no support shift issue, there exists a DRMG such that any online algorithm suffers from the eurse of multi-agency. This is a separation between DRMGs with interactive data collection and generative model/offline data, and also between DRMGs with non-robust MGs, showing the inherent challenges of online DRMGs.
4.1 HARDNESS WITH SUPPORT SHIFT
2024 refers the case that the support of the worst-case transition kernel is Support shift (Lu et al.
not covered by the support of the nominal kernel. can happen when, for instance, the uncertainty set is defined through TV. It will result in challenge that, for those states that not covered by the nominal kernel, there is no data available, so that the agent can never learn the optimal robust policy efficiently. Specifically, derive the following result to illustrate the hardness.
Theorem 1. There exists TV-DRMG, such that any online learning algorithm satisfies that:
inf E RegrettsssH(K a(pk min II Aii). 1EM
ALG
Our construction deferred to Example 10 in Appendix. This regret bound linear in the number of episodes K, creating combinatorial explosion that makes the problem information:theorrtiiallyy intractable. Moreover, our result shows that when the game horizon H large enough, the minimax lower bound depends on the joint action space, showing the hardness of online learning compared to generative models and offline settings.
4.2 HARDNESS WITHOUT SUPPORT SHIFT
We then illustrate the hardness of online DRMGs when there is no support shift. Note that when the uncertainty set is defined through, e.g., KL divergence, the worst-case support will be covered by the nominal one, so there will not be any support shift. However, we construct another example to show that, even without the support shift, online learning can still be challenging and inefficient.

---

Published as a conference paper at ICLR 2026
Theorem 2 (Lower Bound for Robust Learning without Support Shift). There exists DRMG, such that any learning algorithm suffers the following cumulative regret lower bound over K episodes:
inf BlRegret K)] 2012000 20)1 ACG
2(1/ II IA). IEMM
This result illustrates that, even without any support shift, some hard instance can require at least Ω ( II; A3) regret. Our result thus suggests that the dependence on the joint action space may be inevitable in online DRMGs, which suffer from the curse of multi-ageney. Specifically, in DRMGs, agents need to solve the robust optimization (i.c., estimate the support function (-()), which requires knowledge of the whole transition kernels find the worst-case from the uncertainty set. Thus, the agents have to explore the whole model, introducing an inevitable dependence on II, A, In non-robust MGs, however, agents can estimate the single nominal performance merely from samples instead of model estimations, thus the multi- agency curse can be broken.
5
THEORETICAL GUARANTEES
5.1 REGRET BOUND FOR TOTAL VARIATION
As discussed in Section efficient algorithm can be expected due to the support shifting issue. We hence adopt a standard fail-state assumption (Lu et al. 2024 Liu et al.) (024) to ensure the worst-case kernel support will be covered by the nominal one, bypassing the issue.
Assumption 3 (Failure States). For any agent i, there exists an (agent-specified) set of failure states Sj S S, such that (s, a)= O, and P7 (s'ls, a) 0, Va E A, E Sj. Vs' & Sj.
This assumption is only needed for the TV case. Assumption Bis standard assumption in single-agent robust RI. studies (Panaganti et al. 2022 Lu et al. 2024). and we adapt to multi-agent cases.
We then present our threotical guarantees.
Theorem 4 (Upper bound of TV-MORNAVD, Denote Pmin == minie Pe. For any E (0, 10,
Valpkclla.a)
1 ptptcina Vini vhet
we sel f (s, a) as
(=.a)1
JK' where: log (II
A A)H22332112 and C1. C2 are absolute constants. Then, under
Assumption for EQUILIBRIUM being one of {NASH, CE, CCE), with probability least 1 8. the regret of our TV-MORNAVI algorithm can be bounded as: Regret (NASH,CCE,CE) (K) =
δ (V mim (Pmin. HJ H2SK (IIIEMA) )
5.2 REGRET BOUND FOR RL.DIIERGENCE
We then study the regret bound of the KL-divergence set. As discussed, the KL set is free from the support issue hence no additional assumption is required. Our regret bound result is as follows.
Theorem 5. For any 8, set (s,n)(s,a) a) in KL-DRMG as 20,
P
(N
Ae (s.a)
VK. K. where Pk (s,
res (s((ss)))
(s'(s,,
0}.
log (S K3122233210) and es is an absolute constant. being one of (NASH, CE, CCE), with probability at least 8, it holds that
Then for EQUILIBRIUM
Reggee(/NASH.cCEEE)] = ò 0( V (ThEM ( P* min
) where
Ps A min(ssa,.' (o) P(s'|s. a) is the smallest positive entry of the nominal kernel. min
We note that the exp(H) term is inherently from the duality form of the distributionally robust optimization with KI-ball (see equation 12). It is standard in existing robust RL studies under KI.
7

---

Published as a conference paper at ICLR 2026
2022 Blanchet jet al. 2023 Ghosh et al. 2025, Si et al. 2020 Xu et al. 2023: Zhou et al., 2021)). )) It reflects the
settings, and can be directly replaced by (P+ )-1 (see, e.g., (Panaganti & Kalathil
inherent hardness of the KL-based robust RL, and is ievitaabe in sample complexity. In practice, for
moderate horizons, minn > 0, and non-vanishing o, these worst-case factors remain controlled and
do not pose serious issues.
We then briefly discuss the construction f-MORNAVI, for each agent episode k and step h, we maintain optimistic and pessimistic robust Q @-esiimate Q (8, a), L. (s,a), a), defined via the empirical robust Bellman operators as in eqs 5 and shifted by an exploration bonus ( a) 2 O. We use ap [v[]]= := inf Ep[V] for the support function over the uncertainty set. The purpose of the bonus to make these estimates form tight, uniform high probability confidence interval around the true robust Q-values, i.c
under the two cases. Recall that in our meta algorrttm
P. (s,a) (siin(s (s) (iin(s, ih
for all (i, h, k, s,
TV-uncertainty. For TV-balls equation 11 Under Assumption 3 (failure states), it holds that min, V(s) = O, and the deviation between the true and empirical robust operators (h,, 8, a) then decomposes as
the dual representation of the robust Bellman operator in
(P8)0g((aa)))) a
S
max (0,00, Pmnto]
E P [n)
T PP [vll
To simultaneously control the estimation error for all (i, h, k, 8, a) and all value functions of the
form V V.P. A11 and VPa 1 we utilize the standard c-net (Shi & Chi 2024 Li al. 2024a) of the interval [0, H Puinl, and construct a Bernstein-type concentration inequality for empinica expectations of the random functions V,, as
(t (U)
H2
E Erg(1s,) [0] Bp (p S
(10)
for all U with |0| S H. our algorithm we U VMANNI+Y +iinti+Ve.... and AV V k,i,++1
Ve: 1 which allows to relate the variance under P* and pk and to control the gap [[AV] that appears in the robustness amplification term. Combining equation 10 with these comparisons yields
"PPL(Pe (V ki op (lle,)) [VRi
Var Varpa()),,a)
(V M,A.4+1 + VR vR..++1)
H
1
Be:claa)) [A]]
a5,
H
Czs Var Vargau Glleea (VV +Ve ver
This motivates choosing the TV- B P (s,
N (s.a)11
2 R (l AV] H under TV-uncertantyy
+
1
With this choice, Lemma 20 shows that equation holds
VK*
Thus, the robust Bellman operator becomes a log-moment generating function of V. The key difficulty is that we now need to control the deviation between the true and empirical log MGFFs
KL-uncertainty, For KL-balls we again appeal to the dual formulation equation 12
| log Lg pegepp
+ log E () [xppccppppp0_ exp(-AV)]
uniformly over all (i, h. s, a) and the random value functions V V k generated by the algorithm. We utilize Hoeffding's inequality to derive self normanzzdd concentration inequality for empirical MGFs: log p- (e- -V] log Ep [v]]]]] $ V (N.((.))V1)) Pri..
8

---

Published as a conference paper at ICLR 2026
Multiplying both sides by H/p, (since À ps/ H) and using the boundedness ||V H control higher-onee order terms in the MGF expansion, we obtain the local deviation
| [P - (P (P
H Pi (N) Pai P
Since only the support of P matters, and we only observe empirical transitions, we replace (s, by its empirical counterpart Pk A a), at the cost of an extra factor that is absorbed into the constants (ef. Lemma 31.. This leads to the KL-bonus as H. (. = 20g pi (NE().))V) Pa m (8,0)
5.3 SAMPLE COMPLEXITY
As direct corollary, derive the sample complexity learn an s-equilibrium. Using standard online-to-bant to-ncch conversion (Cesa-Bianchi Bianchi et al. (001)) we have the following results.
Corollary 6 (Sample Complexity). With probability at least 1-ô, and under the settings of Thhhorem the number of samples required find an e-approximate equilibrium is bounded as:
and Theorem 5
min (Pmin: H} H (IIiEm A.)). 8 2 (Sp((2 (:) P ) for KL-DDRG
for TV-DRMG
KH-
Our results hence imply that, despite the inherent hardness of online learning in DRMGs,, our algorithm able to learn an equilibrium with efficient sample complexity. we shall discuss in the next section, our complexity bounds are near-optimal (except the term II A,).
6 COMPARISON WITH PRIOR WORKS AND DISCUSSION
We then compare our results with prior works (the detailed Comparisons are shown in Table I.
Table I: Comparison with prior results. C.ipp are coverage coefficients for offline learning.
Setting & Algorithm Generative (Shi et al.
Uncertainty Set
Sample Complexity
TV
Ó 0( Ad) min {Prin H})
2024)
Generative
Contamination
0(6-2 A,) min (ruin H})
Jiao & Li
2024
Generative
TV (fictitious)
0 iEM A,) min (P H})
(Shi al.
2025)
Offline
KL
2p C exp(H)))* (M Ac))
Blanchet et al.
2023
TV
Ö 2 S2 IIEM (4)
Offline
TV
Ō O(=2CHHAS( A.mmn (f p). H})
(Li et al.
2025)
Online
KL
2 H5-2 (Ar))3) (with an oracle)
(Ma al.
2023)
Online
TV
012 S( l M As) min {Pmln. H}) Ó(E 2 (P+ ) 1 exp(2112) ll As))
(Our work)
KL
Generative
Lower bound
TV
á 2f(=2HH35m A:) min (pml. H})
(Shi al. 2024)
A substantial body of research DRMGs has focused two primary settings: (i) generative model
setting, where the agents can freely sample from all state-action pairs (Shi et al. 2025 2024 Jia
Li 2024); (ii) offline setting, which relies comprehensive, pre-collected dataset (Blande Blanchet

---

Published as a conference paper at ICLR 2026
et al. 2023 Li et al. 2025). As discuss in Section 4 both of these avoid exploration and are therefore easier than the online regime we consider. Despite this added difficulty, our algorithm attains complexities comparable to those reported for the generative and offline settings.
For both uncertainty sets, our results match or improve upon previous results and the minimax lower bound in all parameters except for the action- irtion-productt term, II, A,, under the generative model setting. In the offline setting, the dataset is generated uniformly, the convergence coefficients Ci,p from
(Li et al. 2025 Blanchet et al. 2023) introduce additional II, A, term into the sample complexity. Consequently, our results also match or surpass the offline complexity in all parameter dependence. This raises important open question: Can any DRMG learning algorithm overcome the curse of multi-agency and eliminate the dependence on II, A, under general settings?
While some works (Shi al. 2025 Jiao & Li 2024 Li et al. 2025 Ma al. 2023) have achieved independence from I1 A,, remains unclear whether these improvements are applicable to general
DRMGs. Specifically, the results in (Shi al. 2025) and (Jiao & Li, 2024) developed for special uncertainty sets with desirable properties. For instance, the fictitious TV uncertainty set in (Shi et al. 2025) allows the global transition kernel to be estimated from single agent's local information; and robust RL under contamination models is known to be equivalent to a non-robust problem with specific discount factor (Wang et al. (023a). And the improvement in the offline setting attributed to the benefits of the coverage coefficient.
The only online method (which also breaks the curse of multi-agency) is presented in (Ma al. 2023). However, their algorithm relies on additional assumptions about uncertainty sets and a powerful oracle. This oracle is required to provide an e-aceurate estimation of the worst-case performance, op, [V] (see Theorem 12 of (Ma et al. 2023)), without any need for exploration. A central challenge in the analysis of robust learning algorithms is precisely quantifying this estimation error, as demonstrated in works like (Shi et al. 2023) Xu et al. 2023 Panaganti & Kalathil 2022 Liu & Xu 2024). By assuming the existence of such an oracle, they bypass this core challenge, which significantly reduces their sample complexity. Moreover, their results need additional assumptions on the radius p. For instance, is assumed that <
Pigin. whereas ours do not require any of them. H
Therefore, the complexity reduction in these works is in fact blessing of their specific uncertainty set structures, the properties offline coverage coefficients, or the use an impractical oracle. Given our lower bound derived in Section 4 we argue that the dependence on the joint action space may be inevitable in DRMGs. In the robust settings, agents need to estimate the entire nominal kernel so that they can learn the worst-case from the uncertainty which requires samples from all joint actions to estimate the whole transition kernel; whereas the non-robust case, there is only one transition kernel and agents can use samples directly estimate the performance under it, instead of estimating the whole transition model. We leave the exploration of this direction, including whether practical relaxations and techniques can avoid it, for future work.
through distributionally robust optimization,
CONCLUSION
In this paper, we introduced the Multiplayer Optimistic Robust Nash Value Iteration (MORNAVI) algorithm, pioneering the study of online learning in DRMGs. Our work provides the first provable guarantees for this challenging setting, demonstrating that MORNAVI achieves low regret and efficiently identifies optimal robust policies for TV-divergence and KI. -ivdeergeee uncertainty sets. This research establishes practical path toward developing truly robust multi-agent systems that learn directly from environmental interactions. Despite the inherent hardness of online DRMGs, our algorithm achieves complexity results comparable to the generative model and offline settings. This work also highlights a critical open question: whether online DRMG learning algorithms can overcome the curse of multi-agency and eliminate the dependence on the joint action space size. Future work will explore this fundamental challenge to advance the scalability of robust MARL.
ACKNOWLEDGMENT
This work was supported by DARPA under Agreement No. HR001 1-22---044277 and NSF under Award CCF-2106339.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Mohammed Amin Abdullah, Hang Ren, Haitham Bou Ammar, Vladimir Milenkovic, Rui Luo, Mingtian Zhang, and Jun Wang. Wasserstein Robust Reinforcement Learning. arXiv preprint arXiv: 13.00..11/9,, 2019.
Peter Auer and Ronald Ortner. UCB Revisited: Improved Regret Bounds for the Stochastic Multi-Armed Bandit Problem. Periodica Mathematica Hungarica, 61(1-2):55-65, 2010.
Peter Auer, Nicolo Besa-Bianchi, Yoav Freund, and Robert E Schapire. The Nonstochastic Multiarmed Bandit Problem. SIAM Journal Computing, 32(1):48-777 07448877,200 2002.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax Regret Bounds for Reinforcement Learning, In International Conference on Machine Learning (ICML), pp. 263-272.
PMLR, 2017.
Kishan Panaganti Badrinath and Dileep Kalathil. Robust Reinforcement Learning Using Least Squares Policy Iteration with Provable Performance Guarantees. In Proc. International Conference on Machine Learning (ICML), pp. 511-520. PMLR, 2021.
Yu Bai and Chi Jin. Provable Self-Play Algorithms for Competitive Reinforcement Learning. In International conference Machine Learning (ICML), pp. 551-560. PMLR, 2020.
Jose Blanchet, Miao Lu, Tong Zhang, and Han Zhong. Double Pessimism Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coverage. Advances Neural Information Processing Systems (NeurIPS), 36:66845 36:66845-66859 2023.
Alexander Bukharin, Yan Li, Yue Yu, Qingru Zhang, Zhehui Chen, Simiao Zuo, Chao Zhang, Songan Zhang, and Tuo Zhao. Robust Multi-Agent Reinforcement Learning via Adversarial Regularization: Theoretical Foundation and Stable Algorithms. Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 36, pp. 68121-68133 2023.
Lucian Busoniu, Robert Babuska, and Bart De Schutter. A Comprehensive Survey of Multiagent Reinforcement Learning. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 38(2):156-172, 2008
Lorenzo Canese, Gian Carlo Cardarilli, Luca Di Nunzio. Rocco Fazzolari, Daniele Giardino, Marco Re, and Sergio Spanò. Multi-Agent Reinforcement Learning: A Review of Challenges and Applications. Applied Sciences, ((11)):4948 2021.
Nicoló Cesa- Bian-Bianchi Alex Conconi, and Claudio Gentile. On the Generalization Ability On-Line Learning Algorithms. Advances in neural information processing systems (NeurIPS), 14, 2001.
Zixiang Chen, Dongruo Zhou, and Quanquan Gu. Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Games. In Sanjoy Dasgupta and Nika Haghtalab (eds.), Proceedings of The 33rd International Conference on Algorithmic Learning Theory, volume 167 of Proceedings of Machine Learning Research, pp. 227-261. PMLR, 29 Mar-01 Apr 2022.
Pierre Clavier, Erwan Le Pennec, and Matthieu Geist. Towards Minimax Optimality of Model-based Robust Reinforcement Learning. arXiv preprint arXiv:2302.05377 2023.
Qiwen Cui, Kaiqing Zhang, and Simon Du Breaking the Curse of Multiagents Large State Space: RL in Markov Games with Independent Linear Function Approximation. In The Thirty Sixth Annual Conference on Learning Theory, pp. 2651-2652. PMLR, 2023.
Constantinos Daskalakis. On the Complexity of Approximating Nash Equilibrium. ACM Transactions on Algorithms (TALG), 93):1-335 2013.
Constantinos Daskalakis, Paul Goldberg, and Christos Papadimitriou. The Complexity of Computing Nash Equilibrium. Communications of the ACM, 52(2))89-97, 2009.
Ambra Demontis, Maura Pintor, Luca Demetrio, Kathrin Grosse, Hsiao- Ying Lin, Chengfang Fang, Battista Biggio, and Fabio Roli. A Survey on Reinforcement Learning Security with Application to Autonomous Driving, 2022.
11

---

Published as a conference paper at ICLR 2026
Xiaotie Deng, Ningyuan Li, David Mguni, Jun Wang, and Yaodong Yang. On the Complexity of Computing Markoy Perfect Equilibrium in General-Sune Stochastic Games. National Science Review, (0()), 2023.
Jing Dong. Jingwei Li, Baoxiang Wang, and Jingzhao Zhang. Online Policy Optimization for Robust Markov Decision Process. In Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence (UAI), UAI '24. JoLR.org, 2024.
Devdatt P Dubhashi and Alessandro Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 2009.
Songtao Feng, Ming Yin, Yu-Xiang Wang, Jing Yang, and Yingbin Liang. Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games, In Proceedings of the 41st International Conference on Machine Learning (ICML), ICML'24. JMLR.org. 2024.
Arlington M Fink. Equilibrium a Stochastic PePreson Game. Journal of Science of the Hiroshima 1964.
University, Series ai (Mathematics),
Drew Fudenberg and Jean Tirole. Game Theory. MIT Press, 1991.
Debamita Ghosh, George K Atia, and Yue Wang. ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learning. arXiv preprint arXiv:2508.04. 03768, 2025.
Amy Greenwald and Keith Hall. Correlated Q-Learning. In Tom Fawcett and Nina Mishra (eds.), Machine Learning, Proceedings of the Twentieth International Conference (ICML 2003), August 21-24, 2003, Washington, DC, USA, pp. 242-249. AAAI Press, 2003.
Songyang Han, Sanbao Su, Sihong He, Shuo Han, Haizhao Yang, Shaofeng Zou, and Fei Miao. What is the Solution for State-Adversarial Multi-Agent Reinforcement Learning? Transactions on Machine Learning Research (TMLR), 2024. ISSN 2835-8856.
Thomas Dueholm Hansen, Peter Bro Miltersen, and Uri Zwick. Strategy Iteration is Strongly Polynomial for 2-Player Tume- Stochastic Games with a Constant Discount Factor. Journal of the ACM (JACM), 60(1):1-16, 2013.
Sihong He, Songyang Han, Sanbao Su, Shuo Han, Shaofeng Zou, and Fei Miao. Robust Multi-Agent Reinforcement Learning with State Uncertainty. Transactions on Machine Learning Research (TMLR), 2023.
Junling Hu and Michael Wellman. Nash Q-learning for General-Sum Stochastic Games. Journal of Machine Learning Research (JMLR), 40Nov): 2003.
Min Hua, Xinda Qi, Dong Chen, Kun Jiang, Zemin Eitan Liu, Hongyu Sun, Quan Zhou, and
Hongming Xu. Multi-Agent Reinforcement Learning for Connected and Automated Vehicles Control: Recent Advancements and Future Prospects. IEEE Trans Autom. Sci. Eng., 22: 16266-16286, 2025, doi: 10.1109TASEE22225:554222.
Garud N Iyengar. Robust Dynamic Programming. Mathematics of Operations Research, 30(2): 257-280, 2005.
Yuchen Jiao and Gen Li. Minimax-Optimal Multi-Agent Robust Reinforcement Learning. CoRR, 198733, 2024. doi: 10.48500AARXI..441..999
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is Q-Learning Provably Efficient? In Proc. Advances in Neural Information Processing Systems (NeurIPS), pp. 18668-877,, 2018.
Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu. V-Learning A Simple, Efficient, Decentralized Algorithm for Multiagent RL. ICLR 2022 Workshop on Gamification and Multiagent Solutions, 2022.
12

---

Published as a conference paper at ICLR 2026
Yujia Jin, Vidya Muthukumar, and Aaron Sidford. The Complexity of Infinite-Horizen General-Sun Stochastic Games. In Yael Tauman Kalai (ed.), 14th Innovations in Theoretical Computer Science Conference. ITCS 2023, MIT, Cambridge, Massachusetts, USA. January 10-13, 2023, volume 251 of LiPles, pp. 76: 16:1-76:20. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2023. doi: ITA4330LIIICSS..CCS..00000 20233.66.
Erim Kardeş, Fernando Ordóñez, and Randolph W Hall. Discounted Robust Stochastic Games and an Application to Queueing Control. Operations Research, 59(2):365-385 2011.
Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi, and Yuting Wei. Settling the Sample Complexity of Model-Basee Offline Reinforcement Learning. The Annals of Statistics, 52(1):233 260, 2024a.
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 (ICLR), 2024b.
Na Li, Zewu Zheng, Wei Ni, Hangguan Shan, Wenjie Zhang, and Xinyu Li. Sample Efficient Robust Offline Self-Play for Model-based Reinforcement Learning. Manuscript, OpenReview preprint, 2025.
Shihui Li, Yi Wu, Xinyue Cui, Honghua Dong, Fei Fang, and Stuart Russell. Robust Multi-Agent Reinforcement Learning via Minimax Deep Deterministic Policy Gradient. In Proc. Conference on Artificial Intelligence (AAAI), volume 33, pp. 4213-4220, 2019.
Yan Li, Tuo Zhao, and Guanghui Lan. First-Order Policy Optimization for Robust Markov Decision Process. CoRR, abs/2209. 10579, 2022. doi: 10.4850/ARXIV.2209.000
Zhipeng Liang, Xiaoteng Ma, Jose Blanchet, Jun Yang, Jiheng Zhang, and Zhengyuan Zhou. Single-Trajectory Distributionally Robust Reinforcement Learning. In Proceedings of the 41 International Conference on Machine Learning, ICML'24. JMLR.org. 2024.
Jieyu Lin, Kristina Dzeparoska, Sai Qian Zhang, Alberto GarcGar and Nicolas Papernot. On the Robustness of Cooperative Multi-Agent Reinforcement Learning. CoRR, abs/2003.03722, 2020.
Michael L. Littman. Markov Games as Framework for Multi-Agent Reinforcement Learning. In William W. Cohen and Haym Hirsh (eds.), Machine Learning, Proceedings of the Eleventh International Conference, Rutgers University, New Brunswick, NJ, USA, July 10-13, 1994, pp. 157-163, Morgan Kaufmann, 1994. doi: 10.1016/B978---5555 1-55866--33--66500222-
Michael L Littman and Csaba Szepesvári. A Generalized Reinforeement-earnine Model: Convergence and Applications. In ICML, volume 96, pp. 310-318, 1996.
Michael L Littman al. Friend-or-Foe Q-Leaming in General-Sum Games. In ICML, volume 1, pp. 322-328, 2001.
Guangyi Liu, Suzan Iloglu, Michael Caldara, Joseph W Durham, and Michael M. Zavlanos. Distributionally Robust Multi-Agent Reinforcement Learning for Dynamic Chute Mapping. In Proc. International Conference on Machine Learning (ICML), 2025.
Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. A Sharp Analysis of Model-Based Reinforcement Learning with Self-Play. In Proc. International Conference on Machine Learning (ICML), pp. 7001-7010. PMLR, 2021.
Zhishuai Liu and Pan Xu. Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learning. Advances Neural Information Processing Systems (NeurIPS), 37:86602-866511 2024.
Zhishuai Liu, Weixin Wang, and Pan Xu. Upper and Lower Bounds for Distributionally Robust Off- Mif-mynamics Reinforcement Learning. CoRR, abs/2409.2052. 2024. doi: 10.48550/ARXIV. 2409.20521.
Zijian Liu, Qinxun Bai, Jose Blanchet, Perry Dong, Wei Xu, Zhengqing Zhou, and Zhengyuan Zhou. Distributionally Robust Q-Learning In Proc. International Conference on Machine Learning (ICML), pp. 13623- 13643. PMLR, 2022.
13

---

Published as a conference paper at ICLR 2026
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-Agent Actor-Critic for Mixed Cooperatve-Coompetin Environments. In Proc. Advances in Neural Information Processing Systems (NIPS), pp. 6390, 2017.
Miao Lu, Han Zhong, Tong Zhang. and Jose Blanchet. Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithm. The Thirty-eighth Annual Conference on Neural Information Processing Systemss (NeurIPS), 2024.
Ming Yu Lu, Zachary Shahn, Daby Sow, Finale Deshi-Velez, and Li-wei H Lehman. Is Deep Reinforcement Learning Ready for Practical Applications in Healthcare? A Sensitivity Analysis of Ducl-DDQN for Hemodynamic Management in Sepsis Patients. In AMIA annual symposium proceedings, volume 2020, pp. 773. 2021.
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 (JMLR), 24(371): 1-40, 2023.
Xiaoteng Ma. Zhipeng Liang, Jose H. Blanchet, Mingwen Liu, Li Xia, Jiheng Zhang, Qianchuan Zhao, and Zhengyuan Zhou. Distributionally Robust Offline Reinforcement Learning with Linear Function Approximation. CoRR, abs/2209.06622 2022. doi: 10448550/ARXI..2200666
Weichao Mao and Tamer Başar. Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Games. Dynamic Games and Applications, 13(1):165-186, 2023.
Lactitia Matignon, Guillaume J Laurent, and Nadine Le Fort-Piat. Independent Reinforcement Learners Cooperative Markov Games: A Survey Regarding Coordination Problems. The
Knowledge Engineering Review, 27(1):1-31,2011
Andreas Maurer and Massimiliano Pontil. Empirical Bernstein Bounds and Sample-Variance Penalization. In COLT 2009 The 22nd Conference on Learning Theory, Montreal, Quebec, Canada, June 18-21, 2009, 2009.
Variance
Pierre Ménard, Omar Darwiche Domingues, Xuedong Shang, and Michal Valko. UCB Momentum Q-Learning: Correcting the Bias without Forgetting. In International Conference on Machine Learning (ICML), pp. 7609-7618. PMLR, 2021.
Arnab Nilim and Laurent El Ghaoui. Robust Control of Markov Decision Processes with Uncertain Transition Matrices. Operations Research, 53(5):780-798, 2005.
Afshin Oroojlooy and Davood Hajinezhad. A Review of Cooperative Multi-Agent Deep Reinforcement Learning, Applied Intelligence, 53(11):13677-13722, 2023.
Sindhu Padakandla, Prabuchandran KJ, and Shalabh Bhatnagar. Reinforcement Learning Algorithm for Non- Von-SStaionaayy Environments. Applied Intelligence, 50(11):3590-3606 2020.
Kishan Panaganti and Dileep Kalathil. Sample Complexity of Robust Reinforcement Learning with Generative Model. In International Conference Artificial Intelligence and Statistics (AISTATS), pp. 9582-9602. PMLR, 2022.
Kishan Panaganti, Zaiyan Xu, Dileep Kalathil, and Mohammad Ghavamzadeh. Robust Reinforcement Learning using Offline Data. Advances in Neural Information Processing Systems (NeurIPS), 35: 32211-32224, 2022.
Georgios Papoudakis, Filippos Christianos, Arrasy Rahman, and Stefano V. Albrecht. Dealing with Non-Stationarity in Multi-Agent Deep Reinforcement Learning. CoRR, abs/1906.04737, 2019.
Xue Bin Peng, Marcin Andrychowicz, Wojciech Zaremba, and Pieter Abbeel. Sim-to-Real Transfer of Robotic Control with Dynamics Randomization. In 2018 IEEE international conference on robotics and automation (ICRA), pp. 3803-3810, IEEE, 2018.
Aravind Rajeswaran, Sarvjeet Ghotra, Balaraman Ravindran, and Sergey Levine. EPOpt: Learning Robust Neural Network Policies Using Model Ensembles. Proc. International Conference on Learning Representations (ICLR), 2017.
14

---

Published as a conference paper at ICLR 2026
Shyam Sundhar Ramesh, Pier Giuseppe Sessa, Yifan Hu, Andreas Krause, and Ilija Bogunovic. Distributionally Robust Model- based Reinforcement Learning with Large State Spaces. In Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li (eds.), International Conference Artificial Intelligence and Statistics, 2-4 May 2024, Palau de Congressos, Valencia, Spain, volume 238 of Proceedings of Machine Learning Research, pp. 100-108. PMLR, 2024.
Zachary Roch, George Atia, and Yue Wang. A reduction framework for distributionally robust reinforcement learning under average reward. In Proc. International Conference on Machine Learning (ICMI.). PMIR, 2025a.
Zachary Roch, Chi Zhang, George Atia, and Yue Wang. A sinite-sample analysis of distributionally robust average-reward reinforeement learning. arXiv preprint arXin:2505./2462, 2025b.
Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua. Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving. CoRR, abs/1610.0322) 2016.
Lloyd S Shapley. Stochastic Games. Proceedings of the National Academy of Sciences, 39(10): 1095-1100, 1953.
Laixi Shi and Yuejie Chi. Distributionally Robust Model-Basee Offline Reinforcement Learning with Near-Optimal Sample Complexity. Journal of Machine Learning Research (JMLR), 25(200):1-91, 2024.
Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, Matthieu Geist, and Yuejie Chi. The Curious Price of Distributional Robustness in Reinforcement Learning with Generative Model. Advances in Neural Information Processing Systems (NeurIPS), 36:79903-79917, 2023.
Laixi Shi, Eric Mazumdar, Yuejie Chi, and Adam Wierman. Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertainty. arXiv preprint arXiv:2404.1890, 2024.
Laixi Shi, Jingchu Gai, Eric Mazumdar, Yuejie Chi, and Adam Wierman. Breaking the Curse of Multiagency in Robust Multi-Agent Reinforcement Learning. In Aarti Singh, Maryam Fazel, Daniel Hsu, Simon I Lacoste-Julien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, and Jerry Zhu (eds.), second International Conference on Machine Learning, ICML 2025, Vancouver, BC, Canada, July 13-19, 2025, volume 267 of Proceedings of Machine Learning Research. PMLR / OpenReview.net, 2025.
Yoav Shoham and Kevin Leyton-Brown. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press, 2008
Nian Si, Fan Zhang, Zhengyuan Zhou, and Jose Blanchet. Distributionally Robust Policy Evaluation and Learning in Offline Contextual Bandits. In Proc. International Conference on Machine Learning (ICML), pp. 8884-8894. PMLR, 2020.
David Silver, Aja Huang, Christopher Maddison, Arthur Guez, Laurent Sifre, George Driessche, Julian Schritwiesser, Ioannis Antonogiou, Veda Panneershelvam, Mare Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukeuoglu, Thore Graepel, and Demis Hassabis. Mastering the Game of Go with Deep Neural Networks and Tree Search. Nature, 529:484-444 489, 01 2016. doi: 10.1038/nature 16961.
Ziang Song, Song Mei, and Yu Bai. When Can We Learn General-Sum Markov Games with Large Number of Players Sample-Eiffiieently In The Tenth International Conference on Learning Reprexentations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.
Eugene Vinitsky, Yuqing Du, Kanaad Parvate, Kathy Jang, Pieter Abbeel, and Alexandre Bayen. Robust Reinforcement Learning Using Adversarial Populations. arXiv preprint arXiv:2008.01825, 2020.
Oriol Vinyals, Igor Babuschkin, Wojciech M. Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung. David Choi, Richard Powell, Timo Ewalds, Petko Georgiev. Junhyuk Oh, Dan Horgan, Manuel Kroiss, Ivo Danihelka, Aja Huang, L. Sifre, Trevor Cai, John P. Agapiou, Max Jaderberg, Alexander Sasha Vezhnevets, Rémi Leblond, Tobias Pohlen, Valentin Dalibard, David Budden,
15

---

Published as a conference paper at ICLR 2026
Yury Sulsky, James Molloy, Tom Le Paine, Caglar Gulcehre, Ziyun Wang, Tobias Pfaff, Yuhuai Wu, Roman Ring, Dani Yogatama, Dario Wünsch, Katrina McKinney, Oliver Smith, Tom Schaul, Timothy P. Lillicrap, Koray Kavukcuoglu, Demis Hassabis, Chris Apps, and David Silver. Grandmaster Level in StarCraft II Using Multi-Agent Reinforcement Learning. Nature 575:350 354, 2019.
He Wang, Laixi Shi, and Yuejie Chi. Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processes. RIJ, 3:1467-115, 2024a.
Lu Wang, Wei Zhang, Xiaofeng Hc, and Hongyuan Zha. Supervised Reinforcement Learning with Recurrent Neural Network for Dynamic Treatment Recommendation. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 2447-2456, 2018.
Qiuhao Wang, Chin Pang Ho, and Marek Petrik. Policy Gradient Robust MDPs with Global Convergence Guarantee. In International Conference Machine Learning (ICML), pp- 35763-35797. PMLR, 2023a.
Shengbo Wang, Nian Si, Jose Blanchet, and Zhengyuan Zhou. A Finite Sample Complexity Bound for Distributionally Robust Q-learning. In International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 3370-3398. PMLR, 2023b.
Shengbo Wang, Nian Si, Jose H. Blanchet, and Zhengyuan Zhou. On the Foundation of Distributionally Robust Reinforcement Learning. CoRR, abs/2311.09015 2023c. doi: 10.48550/ ARXIV.2311.0901
Shengbo Wang, Nian Si, Jose Blanchet, and Zhengyuan Zhou. Sample Complexity of Variance-Reduced Distributionally Robust Q-Learning. Journal of Machine Learning Research (JMLR), 25634)):1-77, 2024b.
Yudan Wang, Yue Wang, Yi Zhou, Alvaro Velasquez, and Shaofeng Zou, Multi-Agent Reinforcement Learning. In 2022 IEEE 32nd International Workshop Machine Learning for Signal Processing (MLSP), pp. 1-6. IEEE, 2022.
Robust
Yudan Wang, Shaofeng Zou, and Yue Wang. Model-Free Robust Reinforcement Learning with Sample Complexity Analysis. In Proc. International Conference on Uncertainty in Artificial Intelligence (UAI), 2024c.
Yue Wang and Shaofeng Zou. Online Robust Reinforcement Learning with Model Uncertainty. Advances in Neural Information Processing Systems (NeurIPS), 34:7193-7206, 2021.
Yue Wang and Shaofeng Zou. Policy gradient method for robust reinforcement learning. In Proc. International Conference on Machine Learning (ICML), volume 162, pp. 23484-23526. PMLR,
2022.
Yue Wang, Alvaro Velasquez, George K Atia, Ashley Prater-Bennette and Shaofeng Zou. Model-Free Robust Average-Reward Reinforcement Learning. In Proc. International Conference on Machine Learning (ICML). pp. 36431-36469. PMLR, 2023d.
Yue Wang, Zhongchang Sun, and Shaofeng Zou. A Unified Principle of Pessimism for Offline Reinforcement Learning under Model Mismatch. Advances in Neural Information Processing Systems (NeurIPS), 37:9281-9328. 2024d.
Yue Wang, Alvaro Velasquez, George Atia, Ashley Prater-Bennette, and Shaofeng Zou. Robust average-reward reinforcement learning. Journal of Artificial Intelligence Research, 80:719-803, 2024c.
Wolfram Wiesemann, Daniel Kuhn, and Berç Rustem. Robust Markov Decision Processes. Mathematics of Operations Research, 3811).153-18, 2013.
2013.
Annie Wong, Thomas Bäck, Anna Kononova, and Aske Plaat. Deep Multiagent Reinforcement Learning: Challenges and Directions. Artificial Intelligence Review, 56(6):503-55556 2023.
16

---

Published as a conference paper at ICLR 2026
Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang. Learning Zero-Sum Simultaneous-Mil Markov Games Using Function Approximation and Correlated Equilibrium. In Proc. Annual Conference on Learning Theory (CoLT), pp. 3674-3682. PMLR, 2020.
Yang Xu, Swetha Ganesh, and Vaneet Aggarwal. Efficient q-learning and actor-critic methods for robust average reward reinforcement learning. arXiv preprini arXiv:2506.07040, 2025.
Zaiyan Xu, Kishan Panaganti, and Dileep Kalathil. Improved Sample Complexity Bounds for Distributionally Robust Reinforcement Learning. In International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 9728-9754, PMLR, 2023.
Wenhao Yang. Liangyu Zhang, and Zhihua Zhang. Toward Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptotics. The Annals of Statistics, 50(6): 2223-3248, 2022.
Wenhao Yang, Han Wang, Tadashi Kozuno, Scott M Jordan, and Zhihua Zhang. Robust Markov Decision Processes without Model Estimation. arXiv preprint arXiv:2302.0122 2023,
Andrea Zanette and Emma Brunskill. Tighter Learning without Domain Knowledge using Value Function Bounds. In International Conference on Machine Learning (ICML), pp. 7304-7312. PMLR, 2019.
Regret Bounds in Reinforcement
Chi Zhang. Zain Ulabedeen Farhat, George K. Atia, and Yue Wang. Model-Free Offline Reinforcement Learning with Enhanced Robustness. In Proc. International Conference on Learning Reprexentations (ICIR), 2025.
Kaiqing Zhang, Tao Sun, Yunzhe Tao, Sahika Gene, Sunil Mallya, and Tamer Basar. Robust Multi-Agent Reinforcement Learning with Model Uncertainty. In Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 33, 2020.
Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms. Handbook of Reinforcement Learning and Control, pp. 321-384, 2021a.
Runyu Zhang, Yang Hu, and Na Li. Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexity. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024a.
Zihan Zhang, Xiangyang Ji, and Simon Du. Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon. In Conference on Learning Theory (CoLT), pp. 4528-4531 PMLR, 2021b.
Zihan Zhang, Yuxin Chen, Jason D Lee, and Simon Du. Settling the Sample Complexity of Online Reinforcement Learning. In Proc. Annual Conference on Learning Theory (CoLT), pp. 5213-5219. PMLR, 2024b.
Wenshuai Zhao, Jorge Peña Queralta, and Tomi Westerlund. Sim-to-Real Transfer in Deep Reinforcement Learning for Robotics: A Survey. In 2020 IEEE Symposium Series on Computational Intelligence (SSCI), pp. 737-744. IEÉE, 2020.
Zhengqing Zhou, Zhengyuan Zhou, Qinxun Bai, Linhai Qiu, Jose Blanchet, and Peter Glynn. Finite-Sample Regret Bound for Distributionally Robust Offline Tabular Reinforcement Learning. In International Conference on Artificial Intelligence and Statisties (AISTATS), pp. 3331-3339. PMLR, 2021.
Ziyuan Zhou, Guanjun Liu, and Mengehu Zhou. A Robust Mean-Field Actor-Critic Reinforcement Learning Against Adversarial Perturbations on Agent States. IEEE Transactions on Neural Networks and Learning Systems, 35(10):14370-1433 October 2024. ISSN 2162-2388.
17

---

Published as a conference paper at ICLR 2026
A USE OF LARGE LANGUAGE MODELS
We used ChatGPT only as a general-purpose assistant for language editing and typesetting. Its role was limited to (i) improving grammar, style, and readability, and (ii) LaTeX aupport-adjusting algorithm placement, tidying BibTEX entries and citation styles, and resolving compile issues (e.g.. Type-3 font warnings and package conflicts). All ideas, derivations, and final claims were conceived, checked, and validated by the authors, who bear full responsibility for the paper's content.
B RELATED WORKS
In this section we discuss other related works.
Single-Agent Robust RL. Robust RL for single-agent settings has been extensively studied across wide range of formulations. In particular, substantial body of work has examined the
generative-model setting (Clavier et al. [023 Liu et al. 2022 Panaganti & Kalathil 2022 Ramesh
al. 2024 Shi et al. 2023; Wang et al.. 2023b d 2024b
2023a Wang & Zou, 2022| Xu et al.
2023 Yang et al. [022] Roch et al. 2025b Xu et al. 2025). where the agent is assumed to
have access to a simulator. These studies develop distributionally robust RL algorithms under various
uncertainty sets, including TV, KL, x², and Wasserstein divergences. Another, and arguably more
challenging, line of research focuses on the offline setting (Blanchet et al. [2023] Ma et al. 2022
Panaganti et al. 2022 [Sh & Chil 2024; /Zhang et al. 2024a][Liu & Xu | Wang et al.] 2024d
Blanchet et al. 2023 Wang et al. 2024a). In this setting, the agent must learn exclusively from a
fixed offline dataset, without the ability to collect additional online samples. Finally, we consider the
online setting (Badrinath & Kalathil 2021; Dong et al. 2024 Li al. 2022 Liang et al. 2024 Wang & Zou 2021), where the agent learns exclusively through direct interaction with the environment. Prior work spans model- based, model-free. and policy-gradee gradient approaches, with some methods, such as the policy optimization algorithm of (Dong al. 2024), achieving sublinear regret guarantees.
Robust MARL. Besides the distributionally robust Markov games we considered in our paper, there also other works that investigate robustness in MARL for cooperative tasks, where all agents share a unified objective. (Bukharin et al., 2023) enhance robustness through adversarial regularization, perturbing the environment encourage Lipschitz-continouus policies. (Lin et al.
2020) explore
adversarial attacks on MARL agents as a means of improving resilience, while (Li et al. 20119] extend this approach continuous action spaces by modifying the MADDPG algorithm (Lowe al. (017)) to focus on worst-case actions- narrower interpretation of worst-case optimization in robust RT.. (Wag et al. 2022) studied robust MARL with network agents.
Another line of research focuses on the robustness in MARL under observation uncertainty, under the formulation of partially observable MDPs. The framework of abservation-robut games is proposed
in (He et al. 2023 Han et al. 2024). Observation-robust cooperative MARL is studied in (Zhou
cet al. 2024).
Non-Robust Markov Games. Markov games (MGs), or stochastic games, introduced by (Shapley 1953), form the standard foundation for MARL, particularly in equilibrium learning. Comprchensive surveys such as (Busoniu et al.] 2008 Oroojlooy & Hajinezhad 2023 Zhang et al., 202 la) offer thorough coverage of the field's s evolution. Early work in MARL focused on asymptotic convergence guarantees (Littman et al. 2001 Littman & Szepesvári 1996), whereas recent research emphasizes finite-sample analyses to establish non-asymptotic guarantees, especially for learning Nash equilibria (NE)-a central solution concept. The existence of NE in general-sum MGs was shown by (Fink)
1964), and the algorithmic foundation was laid by the seminal work of (Littman 1994). Classical algorithms such as Nash- Q (Hu & Wellman, 2003), FF-Q (Littman et al.) 2001). and correlated-Q learning (Greenwald & Hall, 2003) were proposed to compute NE and its variants. However, computing NE in general-sun -sum multi-player settings remains PPAD-complete (Daskalakis 2013). and
no polynomial-tima algorithms exist for this case (Jin et al.) 2023 Deng et al. 2023). In contrast,
the two-player zero-sum setting admits tractable solutions, with the first polynomial-time algorithm developed by (Hansen et al. 2013). To address the computational intractability in general-sum MGs, attention has shifted to weaker notions like CE and CCE, with polynomial-tinn time algorithms
such as V-learning (Jin et al.) 2022; Mao & Başar 2023] Song al. 2022) and Nash value iteration (Liu et al., (2021) enabling efficient computation. Furthermore, significant progress in finite-sample analysis-spanning both model-based and model-free algorithms has been achieved
18

---

Published as a conference paper at ICLR 2026
in the two-player zero-sum setting, as evidenced by (Bai & Jin 2020, Xie al. 2020 Cui al.
2023, Chen et al. 2022 Liu et al. 2021] Feng et al. 2024 Li et al.
2024b). advancing the theoretical
understanding of equilibrium learning standard MARL without robustness considerations.
C DRMG WITH f-DIVERGENCE UNCERTAINTY SET
We review the formulation of DRMG with f-divergence uncertainty sets. This framework operates under the S x A-rectangularity assumption, where the nominal transition probability P and the agent-specific radius pi for E M define the robust problem as per Definition]]
Lemma 7 (Strong duality for f-divergence). Let Py (s, a) be an f-divergence uncertainty set as defined in Definition 7 For any value function V, S + Rt and nominal transition kernel P : S x A + (SS). the worst-case expected value, oppy (saa)]]) == inf PEE" (s.a) [PV];] (s. a), admits dual representation given by:
AP V(5)
1 Api + n7.
sup A20, vER
SES
where f* is the convex conjugate of f.
The detailed proof is given in Lemma B.1 of (Yang et al. 2022).
Corollary 8 (Dual representation for TV and KL-divergence). Under the assumption of S x A-rectangularity, the dual representation from Lemmal 7 simplifies to the following for two specific cases of f-divergence. For any value function V S (0, H] and nominal distribution P7 over the next states:
TV-Divergence. For an uncertainty set defined by TV-divergence, where f(t) = 1/2 2 the robust expectation op av.laa)))) [V] is expressed as:
1/
(pg((1ssa)) max(0, 16-177-v) V.) P max(0. min Vi(s')) + +
Pp (Phrrv(sa)) sup n
SEES
(11)
KL-Divergence. For an uncertainty set defined by Kl.-divergence, with f(t) = t (og( the robust expectation ppi (s,a) [V.) is expressed as:
{ 17 17 (Ep((ss.))
{
exp { Vi 1
(11 - mp, mpp
- sup Opt. (s gE Hf(y.H/ps)
(12)
ROBUST BELLMAN EQUATIONS.
Analogous to standard MGs, the following proposition provides the robust Bellman equation for DRMGs. In particular, the robust value functions ViTh* (s) associated with any joint policy π for all s) E M [H] obeys the following proposition given below:
Proposition 9 (Robust Bellman Equation). Under the S x A-rectangularity assumption, for any nominal transition kernel P* and joint policy π,, the robust Bellman equation holds for any (i. h, s, a):
Q7 (s. a) (s, op
V.T.A ih+11
(13)
VT Vi,h (s) (a-mm)-)))) 0
(s, a))
(14)
The detailed proof of Proposition 9 for finite-horizon RMDP is given in (Blanchet et al. 2023 Proposition 2.3). We emphasize that the robust Bellman equation in 14 fundamentally grounded in the agent-wise (s, a) rectannuguyyr condition imposed the uncertainty set. This condition decouples the dependencies of uncertainty across agents, state-action pairs, and time steps, thereby enabling the recursive structure of the Bellman equation.
19

---

Published as a conference paper at ICLR 2026
D NUMERICAL EXPERIMENTS
In this section, we develop numerical experiments to validate our theoretical results. We highlight that numerical experiment for Markov games be significantly challenging due e.g., the equilibrium identification challenge and computational barrier (Shoham & Geyton-Brown 2008 hence we use some small-scale experiments to validate results.
D.1 FULLY COOPERATIVE DRMG
As the first step in numerical experiment, we design a 2-agent, 2-step fully cooperative DRMG (with identical rewards for both players), to illustrate the separation between our robust learning algorithm and the non-robust ones in standard Markov games.
The game is formally defined by the following components:
Agents (M): The set of agents is M = [1,
Horizon (H): The game has finite horizon of H 2.
State Space (S): The state space is S {so, SH, sT The game always starts in state So at h = 1. The states &μ (High), 8a (Medium), and 8r (Trap) are the potential states for h = 2, and the episode terminates after this step.
Action Space (JA): Each agent has two actions, A; = 10 for i E M. The joint action space is A A1 x A2, with joint actions (01, 02) E ((0,0), (0, (1, (1, 1)).
In our game, agents receive no reward at the first step: (so, a) = 0 for all a, At step h = 2, the reward (s, a) for both agents is determined by the current state E {SH, SM, 87} and the joint action a. The rewards are defined as:
At sy (High): This the high-reward state, where (i, a) for all i,
At S (Medium): This is medium-rewan state, where ( a) 0.6 for all i, a,
At 8T (Trap): This is the low-reward, trap state, where (8T, a) = 0 for all i,a
We then set the nominal transition kernel from So h 1, (f The probabilities are detailed as follows:
Table 2: Nominal transition probabilities (- a) from the start state.
Joint Action a
(s (s0. a)
(MMMM|80. a)
(srrsls, a)
Description
a (1,1)
0.90
0.00
0.10
Risky (high reward, trap support)
a (0,0)
0.60
0.40
0.00
Safe (no trap support)
(1,0)
0.50
0.25
0.25
Mediocre
a (0, 1)
0.50
0.25
0.25
Mediocre
be seen that, under the nominal kernel, the risky action is preferred it has higher probability to transit to sи. However, when there are model mismatch between the training and deploying environment, and under the risky action, the probability transiting to the Trap state sr becomes higher, then the non-robust equilibrium becomes sub-optimal. On the other hand, our robust learning considers the worst-case, so it prefers to take the safe action. We will numerically show that our robust learning algorithm will learn more robust policy that performs better under model uncertainties or the sim-to-rea gap.
We aim numerically verify two of our claims: (1). Our MORNAVI algorithm converges to the robust equilibria, And (2). The robust equilibria learned are more robust against model uncertainty compared to non-robust ones.
Specifically, we construct the uncertainty set as a KL-divergence ball centered at P as in Equation which P: = p. We then implement algorithm (Algorithm II together with the non-robust Nash value iteration (Liu et al. 202T) as the baseline. Due to the hardness computing Nash equilibria (which is PPAD-hard in the worst-case (Deng et al. 2023)), we compute the CCE for the games.
20

---

Published as a conference paper at ICLR 2026
We develop two experiments as follows. Firstly, rum both algorithms (we set p 0.25 in algorithm) for 10 times, and plot the averaged robust value function of Player against the total number of samples. We also plot the standard deviation to show statistical errors. Secondly, test the learned equílibria from both algorithm under different uncertainty radii For different compute the robust value function of Player (since both players have identical performance) under the KL-ball, to showcase the robustness of our algorithm. The experiment results are shown in Figure
EL revovvrgencc
0.30
KL EL-Oteergetc
0.43
Expacted Robust Return
Expacted Robust Ratumn
0.80
840-
0.75
220
0.60
050
05
Episodes
Uncortaintyy radilss (p)
Performance KL-MORNAVI vs. Episodes
(b) KL-MORNAVI vs. Uncertainty Level (p)
Figure I: f-MORNAVI v.s. Multi-Nash- VI under KL-Divergence
TV- TVvGivergence
TVl Ti:Dtvergence
98
Multt Altah-M
Hulli Nask
Expected Reburt Return
Expected Robustt Return
07
0.5
24-
202
400
603
a50
303e
1050
5.6
60
6/1
0.6
3.6
1.5
Episodes
Uncertainty redius (p)
(a) Performance of TV-MORNAVI vs. Episodes
(b) TV-MORNAVI vs. Uncertainty Level (p)
Figure 2: J-MORNAVI v.s. Multi-Nash-Vi VI under TV-Divergence
As the results shown, our algorithm converges to the robust equilibrium, validating the convergence of our theoretical results and convergence guarantees. Moreover, our robust equilibrium shows an enhanced robustness when model mismatch exists. Specifically, when p zs 0 and there is model mismatch, then the non-robust algorithm outperforms ours (as we are conservative and robust while non-robust is optimization for the nominal kernel); However, when the uncertainty radius increasing and model mismatch is introduced, performance of the non-robust equilibrium decreases significantly. whereas ours shows more stable and robust performance. We trained the plots of uncertainty level radius for 400 episodes. Our results hence validate our theoretical results and claims.
Similarly, we develop experiments with ba-based uncertainty set, and plot results in Figure 2 As results shown, our algorithm converges to a robust equilibrium, which is more stable and robust against model uncertainties. Our results hence align with and validate our theoretical findings.
D.2 GENERAL- SURERAL-SUM DRMG
We then slightly modify the fully cooperative DRMG considered, transferring it to a general-sum DRMG, to further validate theoretical results.
21

---

Published as a conference paper at ICLR 2026
We set the nominal kernel as follows. At step 1, the nominal transition (f Su. a) is
0.82 6. + 0.18 6.7
a (1, (risky),
( 80: a)
0.60 0.60 + 0.40 83317
a (0, 0) (safe);
0.48 6.h + 0.22 83rr + +..30
E {11, 0), (0. 1)) (off-diag).
At step 2 the kernel is absorbing: P/ (s' s, 1fs'= for s {SH, SM, ST
The rewards are settled as follows. At the terminal step (step 2), each terminal state induces a 2x2 matrix game; let R (s), (s), (s) E x2 denote the row/column players' payoffs. We set
0.55
0.90
[0.70
0.85
High: (sn)= = 1.00
(*)) = 0..0 1.00)
1.20
00.45
0.35
T0.65
0.55
Medium: (SM)
((
0.35
0.30
0.50
0.45
Trap:
(sT) O,
R (ST) = O.
Both players then have different rewards and the game becomes a general-sum DRMG.
Similarly, we implement our algorithms with non-robust baseline under both KL and TV uncertainty sets. We plot the performance of both players (as they are different). Our observations from the experiment results remain the same. In Figure 33 and Figure 4a. our robust algorithm converges to robust equilibrium (sample) efficiently. And in Figure 3b and Figure [4b] the robust equilibria learned by our algorithms maintain a more robust and stable performance under model mismatches, showcasing the enhanced robustness of our methods in MARL settings.
Experse
Sptenes
Invertadly radiay
(a) Performance of KL-MORNAVI vs. Episodes
(b) KL-MORNAVI vs. Uncertainty Level (p)
Figure 3: f-MORNAVI v.s. Multi-Nash- VI under KL-Divergene
Traceson
Eaperter FARIIN
(a) Performance of TV-MORNAVI vs. Episodes
(b) TV-MORNAVI vs. Uncertainty Level (p)
4: f f-MORNAVI v.s. Multi-Nash- VI under -V-Dvveree
22

---

Published as a conference paper at ICLR 2026
E HARDNESS OF MULTI-AGENT ONLINE LEARNING
E. HARDNESS WITH SUPPORT SHIFT
Example 10 (The "Initial Shock" Game). Consider a class of N-agent DRMGs, (Mar Jar parameterized by "secret escape route" a" E.A.
Action Spaces: A; = M for each agent. The joint action space has size |A| = -lligNN/ A M
States, Horizon, Rewards: S {8goods Shad horizon H, initial state 81 ggoods and rewards are defined
1, if ggood or is Sbad and a*) (+ a)
0, if s = Stad and a + a*
Dynamics: The system dynamics create the trap.
From Sgood: Nominally, the system stays in Sgood. An adversary can force transition Shod with probability p.
From Sbadt This is the trap. The only way to escape is to play the secret joint action:
Next State =
goods
if a*
Sbods if + a*
Uncertainty Set: The uncertainty is non-zero only at the first step.
-At h = 1 and 81 = &good: The uncertainty set is a TV-ball with radius
For all h >> 1 or + Sgood: There is no uncertainty (p 0). The transition is the nominal one.
Theorem 11. For the "Initial Shock" DRMG, any decentralized online learning algorithm suffers the following best-response regret lower bound:
})
inf sup [[Regret,(K)] Ω pk min H, II A AC9 areA
xE[N]
Proof. Step 1: Decomposing the Per-Episode Regret. The best-response regret for Agent 1 in an episode is Regret, Vi ViT. We expand this using the robust Bellman equation at 81 goods where uncertainty exists.
Regret = (1 (1- (1-p)111---0) (8good) + -V, (sbad)
- (11 (1+(111 ('. (Syood) + (VTT2((Sbaal
(1 p) (v112 (vtta--i10 (B V.T.p (8guod) + P 1,2
V.
Vi.2 (Sbad)
Since there is no uncertainty for h > 1, the transition from Syood h 2 is deterministically to 8good at = 3. Thus, Vi,2(8good) is a constant independent of the policy in the trap state, which means (t(x=(i(tssspaa)) = (V[2(( The first term is exactly zero, and thus have that
Regret = (V1,2- (yt.-ri-(saod - V)T.2(Sboa)) (Sboa) p (Sboa))
(15)
Step 2: Formalizing the Value Gap AV2 The value gap is the expected difference in total future rewards. This difference is precisely the expected number of steps wasted in the trap. Note that the value of state Stad step h under policy n is the expected sum of future rewards. Let T = T(=') ) the random variable for the number steps to escape (i.e., play a a"), starting from step h. Let H h + be the number of steps remaining in the episode, then the total reward
23

---

Published as a conference paper at ICLR 2026
collected from 2 is " [[[[T s (C T 2)] it will always receive when at Sgood-
Moreover, note that the total number of available rewards is C, and since C min(r-1,C)+11p C](C - - + 1), the value can therefore be expressed as V1,2" (Sbad) = C - 11mminn-11,000 -
Therefore, the value gap the difference in the expected number of wasted steps:
A AV2 (Sbad) = (C' - R[min(r* - 1, C))) (C E[min(r - 1, C)]) Eijin 1, C)] E[min(T* C)].
where 7* is the escape probability of π². Since the best-response policy oi plays deterministically. so its escape time 5" depends only on the other agents' policies, π-1- The algorithm's escape time т depends on its full policy π.
Step 3: Lower Bounding the Value Gap. The best response for Agent 1 is to play aj so T does not involve any search for Agent In contrast,
However, the algorithm does not know a and must search. We are interested in the worst-case regret over the choice of a The expected wasted steps for the algorithm is E[min(r 1, C)]. Let Pr. 1 (a_1 = a=1))= The algorithm's 's one-step escape probability is p1 p-1- 1- Its expected escape time is E(T] 1/(p) p-1) )) The expected wasted steps is lower-bounded by:
= Prx, (4) a and
E|min(r- C) 2 1:min 1], ()) 22(min(1/(p) P-1), H 1)),
where the inequality due to Lemma 12
In the worst case over the unknown a", the probabilities pl and p-1 are minimized:
inf pi - 1/AI and inf p-1 - $1 11 1=2
I1) A.).
ai
The best-response policy suffers much less waste. Thus, the value gap A V22 (Sbaa) is dominated by the algorithm's 's large number of wasted steps.
sup A V.2 (sbad) 2 min { (
N 1/((1/A)) - (1 /II44) H
II A H 1)
N
= Ω
min
Step 4: Finalizing the Bound. Substituting this back into the per-episode regret expression from Step 1:
sup E[Regret]] 2 Ω min I A.,
This per-episode regret is incurred because the information bottleneck prevents the algorithm from learning a". Summing over episodes gives the final total regret bound:
K
H 1)
inf sup E E(Regret, (K)] = Σ sup E[Regret 2 pK min
II A (AAH))
ACG
This completes the proof.
Lemma 12. Let be the random variable for the escape time from the trap state, and let C' И 1 be the number of steps remaining in the episode. The true expected number of wasted steps, Elmin(r 1, C)], has the following asymptotic lower bound:
E[min(T - 1, C))
Proof. Note that follows a Geometric distribution Geo(p) and have the probability mass function P(r = k) = (1 (1-p)*-1 -)* for & E number of failures before the first success. Its expectation is IE[-
The random variable r - represents the 1-2 P
We first derive expression for E/min(r 1, C)). We use the tail sum formula for the expectation of a non-negative, integer-valued random variable X, which states E[X] Σ P(X > k))
Let X min(T 1, C). The event (X k) is equivalent the event (7- 1 > 1 and C k).
24

---

Published as a conference paper at ICLR 2026
k 2 C, then P(X k) 0.
If k < C, then P(X k) P(T 1 R).
The event {T 1 > k} means the first & + 1 trials resulted in failure, so its probability is P(r > k + 1) = (1 - p
The expectation is therefore the sum over the non-zero probabilities:
C-1
C-1 Σ k=
E|min[T - 1, 1, Σ
P(min(7-1,,0) P(min(7 - 1, >) Σ
1
P(r 1
(1-p)t11
k=
Letting q 1 p, this finite geometric series:
q = 1 1-9 g(1 -
Σ
p
1=1
Substituting = 1--pp back, we express the expectation in terms of E[[T - 1]:
1 11 (1- Eir 1](1 -1- p)
Elmin(r- 1,
p
Let μ [8 1]
1-P, p
We want to show that there exists a universal constant such that:
u(1 (1 - p) 2 k min(j,, C).
We proceed with a case analysis based on the relationship between μ and C.
Case 1: j C: In this case, min C) J.. We need show that yu(1 (1-)))) 2 k p4, which simplifies to proving that - (1 - p) 2 k:
The condition μ S C implies lower bound p:
1-
Cp = (C(++ll) = p C+1
P
Using the standard inequality 1 x 5- = we have (1 - p)c² -e Thus,
1 - (1- 2 1 FC
1 Since p 2 C+I, we have pC 2 C41 . As the function f(x) = e x is increasing for x > 0,
C
1- -pC 1 11-e-C((Ct)
The function g(C) C is increasing for C 2 1, with minimum value of g(1) 1/2. Therefore, for any integer C 1,
CFI
(1 p) > 1 - -1/2
Thus, the incquality holds in this case with the constant k = - 1-2 1/2 x 0.393.
Case 2: C: In this case, min(p, C* C. We need to show that μ - (1-p) 2 KC.
The condition μ > C implies upper bound p:
P C 1- Cp 1 1>
1
C+1
p
From our calculation of the expectation, we have a sum of C positive, decreasing terms:
C-1 (1-
- -,
k=
This sum is greater than C times its smallest term, which is (1 p)
E[min(7 1, > C(1 c
25

---

Published as a conference paper at ICLR 2026
From the condition p C+I+ it follows that 1 1-p p>> - 1 C
Therefore,
C+1 C+I-
= )
( -c(1-ot1)
C
- 1, 1[,in(--1,C)]
(0+1)
The sequence ac for all C 2 1, the sequence is bounded below by its limit:
is decreasing for 2 1, and its limit C oo is 1/e. Hence,
C+1
(1-
lim (1- +
This gives the lower bound:
- [mmi((=1,C)]>C:
So, the inequality holds in this case with the constant 2₂ 1/c ~ 0.368. By combining the two cases. the inequality is shown to hold for universal constant & = min(k; k2) min(1 - 1/2 1/e) 1/e.
Therefore, for all p E (0, 1) and integers C 2 1, we have established that:
1
Eimin(r 1, C)] 2 min (E|7 1], C* = 52 (2mmmnn (enmminnEEr--a -1,
which hence completes the proof.
E.2 HARDNESS WITHOUU SUPPORT SHIFT
Example 13 (The "Robust Corrupted Bandit" Game). Consider a class of N-agent DRMGs, {Ma where each game is parameterized by secret "best" joint action 0 E A.
States and Horizon:
A single state, and horizon H = 1. This reduces the problem one-shot game, equivalent to multi-armed bandit setting where each episode corresponds single step arm pull.
Action Spaces: The joint action space A is the set of arms, with size |A|
II A.
Reward Function (R {0, 13): The rewards are stochastic. Let (0, 1/2) be small constant. The nominal model My defines the following Bernoulli reward distributions for any agent
1/2++, ia=
(s,
1/22 if + 0.
KL-Divergence Uncertainty Set: The true reward distribution for an action denoted Pl-la), can be any distribution that is close to the nominal one P* (-la)):
P Pl =pp= KL(P(()))) (+la)) Pr. Va A
This uncertainty set does not have a support shift.
The learning problem to identify the best arm by observing noisy rewards that are actively corrupted by an adversary.
Theorem (Lower Bound for Robust Learning without Support Shift), For the "Robust Corrupted Bandit" game, any learning algorithm suffers the following cumulative regret lower bound over K episodes (steps):
N
inf sup E[Regret,(13) 2 Ω
II (=1
A.K
ACG AEA
26

---

Published as a conference paper at ICLR 2026
Proof. The proof proceeds by formal reduction the classic mulli--rmee bandit (MAB) problem.
Let M₁ = ph denote the class of robust game instances from our example, with uncertainty radius p > O. Let Mo {Adg o eeEA be the corresponding class of non-robust instances, where the uncertainty radius zero and the rewards are always drawn from the nominal distributions.
Note that since the horizon H 1, the robust problem reduces to non-robust one, and thus the worst-case regret over the robust class MM must be at least as high as the worst-case regret over the non-robust class Mo:
E Regrett K; Ma.p)] 2 E[Regret( K; Mo,o))
And thus
inf sup E[[egret K; Mo.p)) 2 inf sup [[[eeret( (K; Ma,o)]- AL9 AEA
(16)
AC9 AEA
Therefore, we can establish lower bound for the robust problem by proving one for the simpler non-robust case.
The non-robust problem instance, MM, is a classic stochastic multi-armed bandit problem with M = ||| arms. A foundational result in this area provides a strong lower bound on regret.
Note that following standard lemma:
Lemma 14. (Auer er al. 2202) For any integer M 2 2 and K M, and for any bandit algorithm, there exists a multi-armer bandit problem instance with M arms whose reward distributions are supported on [0, l]. such that the expected cumulative regret after K steps is lower-bounded by:
E Reg Z (KVMK).
We apply the lemma to our non-robust problem instance Mo-
The number of arms, M, is the size of the joint action space, |A].
The number of steps is K.
The reward distributions (Bernoulli) supported on [0,
The conditions the lemma are met. Therefore, for the class problems Mg, the worst-case regret lower-bounded:
N
inf sup E[Regret K; Mo,o)) 2 S2 ACG BeA
II
A,K
(17)
Combining the regret dominance principle from eq. 16 with the specific lower bound from eq. 17 we arrive at the final result for our robust problem:
N
inf sup E[Regrett Ma. 2 Ω
II
ATK
(18)
ACG GEAA
This completes the formal proof by reduction.
F PROOF OF REGRET BOUND OF TV-MORNAVI
In this section, we prove our regret bound for TV-DRMG. Before presenting all the proofs, we first denote I as the joint robust best responses over the agents, and gven by
म = n 1. (T- x ... x TI 1.0m ( (m.
(19)
We will use the notation of .ी later generalizes to the case where the minimal value vanishes, i.c, min.es V(s) = 0, to address the support shift extrapolation challenge arising in interactive data collection, discussed in Remark
mine-llies.. In addition, leverage Assumption which
27

---

Published as a conference paper at ICLR 2026
B.3 of (Lu et al. 2024). Consequently, this allows us to eliminate the minges V(s) term in the dual formulation of the TV-DRMG optimization problem, as shown in
We now recall the bonus term used in TV-MORNAVI for agent in episode & at step h, as follows:
Vilui Vh Vihti +h+11 2
C1 ci (1(sm))
2B (t(l,,)))))
V
1,h+1
(8,
(s, V
H
C2
(20)
(N (s) 1
VK
where log { A3 and c1, 02 are absolute constants.
We begin by defining the high-probability event εyv, stated in the next lemma. Our proof outline is inspired by (Lu et al. 2024 and (Ghosh et al. 2025).
Lemma 15 (Uniform Concentration Bound of event &Tv). Let Egy be the event in which, for all (8, a, 8', k) 8 Axxx [A] x [K], and for all n in (SV/)SKKOOoo of [0, HJ, and is defined
as
ciVarp (n-
- E (1 Eppclea)) (n-
)
1,h+1
S
N a)) V
o2Hi
(s,
c1 min Ps 8, a), (h( (s |s a)
P s,a) - (s ss.))
(s) V13
C2
(N)
(s,,a,s'h,, h, MXS Xxxx [M] [K] N MY (10,H) ) (21)
where: log 5 (I. A)H c1,2 are two absolute constants, N1 H))
denotes an 1/SV Kover of the interval [0, H).
Then, this event εςy occurs with high probability, i.e., Pr(Erv) 2 8.
Proof. This proof builds upon standard techniques by applying classical concentration inequalities and union bound. To simplify our analysis, we first consider fixed stateacction-imi tuple (s, a, h) within a given episode k. We can then construct equivalent stochastic process:
Before the agents' interaction, the environment draws sequence of next states independently from the nominal distribution PT a), where (i represents the state sampled episode i.
(1(1), ,(()),,,,,........
,..., ((k-1)) s(t-))
(ii) When the agents visit the (s, a) tuple time step for the i-th time, the environment causes transition the pre-sampled next state ((()
The randomness of this constructed process is identical to that of our original, interactive learning environment. Consequently, the probability of any event is the same in both contexts. This allows us to prove the required concentration inequalities within this more tractable, simplified setting.
Leveraging this fact, directly apply Lemma 40 which presents variant of Bernstein's inequality and its empirical counterpart from (Maurer & Pontil 2009). To establish a uniform bound, we apply union bound across all tuples (h, s, a, s k,,,)) [H] x Ax x S [K] N1)(svR) ((0, H)).
The size of this e-cover, .N, Wi)(SRR) (10, H),, is the order of O(SHVK).
28

---

Published as a conference paper at ICLR 2026
F.1 PROOF OF THEOREM 4 (TV-DRMG SETTING)
Proof. By leveraging Lemma 20 we can establish an upper bound on the regret by considering the difference between the optimistic and pessimistic value functions:
K
Regret (K)
max EM
(vi (y- - Vi,1 PP: (5))
max iEM
(s)).
(22)
k=
For the TV-divereence uncertainty set, we begin by analyzing the difference between the upper and
lower Q-values. Given our definitions for Qi 24ieh v and V/,,"" (from eq. 5-8) 8). along with
the bonus term P (s, a) defined in eq. (h, k) E [H] [K] and (s, a) ES x A:
20 we can establish bound on this difference for any
as) 2 S o P.i (s.a)
V ib+1]
V
o P. (s.a)
vki 1+1 + +23 (s, a).
(23)
We introduce two key terms, A and B, to simplify this expression:
Vilung
0 pid (e.a)
o Pit (s.a)
+ Oppii (n.a)
Lib+1
P. Pi (s,a)
iih-
(24)
:= (x.a)
V i1h+1
- Pp (N.a)
k.:: 1,h+1
(25)
By substituting these definitions into eq.
we obtain new bound:
Qi,h k.Pi (s, a)
Q Ks.P 1.4
as) S A B + 23,,,, (s,
(26)
We then proceed to bound each of these terms. A concentration bound argument tailored for TV robust
expectations in Lemma 18 shows that A < 2,3 (s, a). For term B, we use the dual representation
of opp (s.a [V] from eq. and Assumption to first establish that B S suPnejo.ey (n (Br (-1s.a) [n
k.ee 1]+ Epg (-1a,a) [n
k.pe }. Since Vi,t4 2 ihht1 (by Lemma 200, we can simplify this
1.
kip: 1
further B < (-bsa))))
By substituting the bounds for and B back into eq. 26 arrive the following inequality:
Q, (s, a) - Q (s, a) S (pg(
[V
k,p: i,+1 - Li + 4,8,, (s, a).
(27)
Using Lemma t9 upper bound the bonus term, and rearranging the terms, we obtain:
Q as) 2 (s,a) s
1+ H
20
E Bp:()s))
The K.tt1l
Vinti +4| (N V1}
H
4
(28)
(N
K'
where G1, 62 > 0 are absolute constants. From the definitions in eq. g the difference in V-functions is given by:
V.A (s)
Vk..e (s) Rawo+
Thipy Qih as (s.
(29)
Now, let's define a new recursive value function Vyl and a corresponding Q-function Qe.P
with H+1
Pmin O. where Pmin min Ps. Furthermore, consider that there exists p² such that TEM
p = argmax Varpg(-la.a)
1 .s 1,1+1
Using these facts we now define
P.MEMMEE(
ciNaarp;( pp
20
Ep (1)
Piii h+1
+ +4\
H
(N)
40² S
4
+
(30)
{N ( 8 a) v1
K'
Pmii (s) = E (a
Pu.i (s, (s,
(31)
29

---

Published as a conference paper at ICLR 2026
It is a well-known property of robust value functions under TV-divergence that they become more conservative as the uncertainty radius Pr decreases (e.g., (Iyengar 2005 Nilim & El Ghaoui (005 )
Given that Pmiin S Pi for all agents i E M, it follows that for every next state s' E St
v s (s') S V Priin (s')
Vi E M and E S.
We can inductively prove that for any (i, h 8, a) EM x [ x S x A:
kipi QiA (8, 24pp (5, a)) - Puin (s,
max iEM
(32)
(ViR i. (s) Vit (5) S v/ Viiimiin (s).
max iEM
(33)
Inductive Proof: Let eq. eq. 28 we have
33 hold for h + 1. So, we will show that eq. (32) holds for h. For any h, by
Qih as) - (s, (s)
20> 1+
4e2 H2 4
H)
iiht1
Light + +
(1)
a) VK' K
(0)
20
(]Varr
Vinti
4c2
1
H
E Bpp(-la (Vh+1 J
(s, V13
[N (s, + +
K
(b) Phin a))
V (8) - Viipe (6) (c) E (()))(
Quin (s, -2tx (8, (s,
(d) S E (1s)
@+ Quit (s, a)
Vkipmin (s).
where ineq. (a) holds by eq. 33 which is true for h + 1 and by the def. of p* which implies
(- V .P:
< Var (-le.a)
V -p"
equality (b) holds by the definition of Qh (s, a) 29 ineq. (d) holds by (b); equality (e) holds by eq. 3T
ih+1
sh+1
as in eq. 30 equality (c) holds by eq.
Therefore, we only need to upper bound the sum Σ --l P.kiaain (sf). For simplicity, we define the
following notations for the differences at any (h,, k) E
[M]] [K]:
A = V/ Pakin (s%)
(34)
ch A Sh.Paii (sh, a
(35)
< = Epp (-ltt a/t (V
(36)
We can confirm that {Ch) ) () and ($)) (n are martingale difference sequences with respect to their respective filtrations. By substituting eq. 30 into eq. 35
we get:
A ch + Q2 (s)
Vi (1
V
s ct + (1 + H
20
E B (-o((1o)aa))
Papaii h+1
+ +41
{NN a V1}
4cg St
4 K
V
(1 a V13
Vx c1e c1Varr A+1
= ct + (1 20
ch (1
20 H
A + +4\
H
[N (s a V1]
422H² St.
4
+ (N +
V
(37)
K
30

---

Published as a conference paper at ICLR 2026
By recursively applying eq. 37 and noting that (1+ - (1 (1+
20
17
for some constant
2 0, we can upper bound the right-hand side of eq.
22 as:
K
H
Regret (K)
(sh + 5h
V o0 h+1
C1 (]Varpp;Hoa.)
402H²Si a) as. v
+
+ +V
(38)
(s, V1)
The first term, sum of martingale differences, is bounded using the Aruma-Hoeffding inequality from Lemma 39 yielding:
K
{1L.. )
ΣΣSt
(ch
(
Sa min
(39)
Pmii
k=1
where 01 > 0 is am absolute constant. For the second term, we apply the Cauchy-Schwarr Schwarz inequality to the summation of the variance terms:
v h+1
K
H
Varrit ak)
H
Varrg (intier))
(5
a V1
#= h=1
A= 1=1
" ΣΣ k= 11
(40)
No (o at) VT
The second factor on the right-hand side is bounded by c2 S A,),, as shown in (Liu et al. 202T Theorem 3), while the first factor is bounded using the Law of Total Variation and standard martingale concentration arguments (from (Jin et al. 2018) and (Luu et al. 2024
Var par
cs c
min
px H) HK min
p
H
H
1 . HK + min
min
H
He).
(41)
Pmin
Pmii
where (a) uses the fact that p² 2 Pmin+ which implies that min(1/p" H) S. min(11 Pmin H). By combining these bounds and substituting them into eq. 40 we can obtain a final bound for the second
term. The third term, Σk Em= V & is straightforwardly bounded by os v VH2K. By combining the bounds for all three terms, we arrive at the final regret bound for Regret (K):
Regret NASH (K) = 00
(V ( {
1
HJHSSK
HESK
II A. 1EM
(42)
Pmin
where c' log" (SHKITICM
This completes the proof of Theorem
4
Remark 16. The methodology for bounding the regret for Correlated Equilibrium (CE) and Coarse Correlated Equilibrium (CCE) settings mirrors the approach outlined here for the Nash equilibrium in the TV-DRME context. The proofs leverage Lemma 21 and Lemma 22 respectively.
F.2 KEY LEMMAS FOR TV-DRMG
Lemma 17 (Gap between maximum and minimum (Lu et al.
2024 Consider any RMG Mg {S, A, H, (PP) (P)) "" The robust value function Var for all E M and h E [H] associated with any joint policy satisfies
V(i,h) h) E M x [H]
max VT- 3,
(8)
min #E$
VT (x) S H 4
#EB
where Vi = min
1 p. и - h 1 < min
H
31

---

Published as a conference paper at ICLR 2026
Proof. Refer to the proof- proof-lines of Lemma 3 in (Shi et al. 2024
Lemma 18 (Bound of optimistic and pessimistic value estimators with bonus for TV-DRMG). Under the typical event Egy defined in eq.
21 and by setting the bonus Pi as in eq. 20 holds that
N.Pi i
Op (v.aa
Vitt1
P. P.N (s.a)
pp (s.m)
σ poij phin(sia) (sica)
Vki 11,+1]
S
2, (8, a).
Proof. Let's denote the term to be bounded as A.
=
(+.a)
(s.a)
+ o Jp (e.a))
1,h+1]
σ Pil (a,a)
v
1,h-1 (43)
Under the high-probabiilty event εrV (as defined in eq. 21 we can apply the concentration inequality from Lemma 24
upper bound as follows:
(at i
Vh.pe Vkopi ihh+1
C1 Varpy PK
2 2
ih+11
2d (s, V1
2 VK
A 2
H
(44)
where , = log (I
result from Lemma 26 ==1 A,) /3322/3///0) and cr d
> O are absolute constants. By applying the
the variance term in eq. obtain the required bound presented in the
lemma statement. This concludes the proof.
Lemma 19 (Bound of the bonus term for TV-DRMG). Under the typical event εgv, the bonus term defined in 20 is bounded by
C1c Var (1
V pi iht1
5 5 (()()))))
Viltt
kk.pt i,h+1
(8,
as)
H
12
(s, VT R
where = log(S A3 (8) and c1, 02 > are constants.
Proof.
The proof-lines similar (Lu et al. 2024 Lemma E.4) (Ghosh al. 2025
Lemma
K.3). Recall the bonus term defined in eq. 20 We need to bound the first and second term of eq. 20 We first bound the second term of B3 (8, a) by using Lemma 25 and get
2E
A
Viht+
HiPE 1i+++
2 2
Epg (1s..)
ihh+1
kkp.p ihtt
CHHSt
H
H
H22
(N a)
v1)
4TE (-le,a)
kiips
Vkp.p
HH (s.a)
(45)
H
where the second inequality from H 2 1. We now bound the first term (variance term) of eq. by using Lemma 27
20
which gives
Phop h.p. k.pg
Cr Varpy (+laa)
ch Varp: ihti
V
(s,
No (s, V1
E (()
Viuee pkp
1itt1
sh++
(46)
H
Ca
N a) V
where C3 > is an absolutely constant. Thus by combining eq. and eq. 46 with the choice of
bonus term in eq. 20 conclude the proof of Lemma 19
32

---

Published as a conference paper at ICLR 2026
NE VERSION: OPTIMISTIC AND PESSIMISTIC ESTIMATION THE ROBUST VALUES FOR TV-DRMG.
Here we will proof the optimistic estimations are indeed upper bounds of the corresponding robust V-value and robust Q-value functions fro NE version.
Lemma 20 (Optimistic and pessimistic estimation of the robust values for TV-DRMG for NE version).
By setting the bonus term 95, in eq. 20 with probability - 8, for any (s, a, h, and k E [K], it holds that
Q
Qi (s, S Qin (s,a), S a) - Qin (s,a),
(47)
yll=
kipt (8), Vin (s) S V se (s). i,h (s) (8) Vih
(48)
Proof. The proof-lines similar (Ghosh et al. 2025) adapted to the multi-agent case. We will run a proof for each inequality outlined in Lemma 20
Ineq. 1: To prove Q
t (s, < (s,
&i (s, a)
Ineq. 2: To prove Q (s, a) s 0i (s,aa.
We know that, step h = H 1, Vi (s) - and eq. 48 hold the (h + 1) step.
(s) (HH- (s) 0. Now, we assume that both eq. 47
Proof of Ineq. 1: We first consider robust Q at the h-th step. Then, by Proposition 9 Bellman Equation) and eq. we have that
(Robust
Q.im t.ati.e (s,a)
Qh (s,
v tir ih+i
Qtaiiin (s, (s,
=min
Bth (s,
σ poj (s)a)
Tp" (s,a)
2 min
{o pij
(c.a)
(x.aa
tirri ih+1l
Op (ps
(K,a)
V torrsipp iitt1
(s)
(49)
where the second inequality follows from the induction of y tixt iP step and the fact that Q.1x"". 1.="..Pt
k.pp ihtt at the h 1-th
s,h+1
Ult by Lemma 17 By Lemma 23 get
ytot ch41
vttn ih+t
ci Var pa
1,41
Oiti (s.a)
-ppi (s,a)
(N, V13
C2Hi + VK
1
(50)
(N
33

---

Published as a conference paper at ICLR 2026
Now by further applying Lemma 26 to the variance term in the above inequality. we obtain that
bore sips i,+1
v sipe ch+1
pi (a,0)
Oiih (aaa
kioo
Libil + ti h+t 2
Varpy(laa)
+ +4HE (-1,,a))
(s) V13
1 + (s, V13
ozHi
VK
Viltit the
Vhuei vki
C1 Sioaarpe(ls.
2
4He (1..))))
1,++1
(s)
(s, V13
o2
(NE(s,))
VK
(0) (N VK"
GuVar (RCl
E (-1o,a))
Vinti 1,,
(s)
H
H'd +
(51)
where the inequality (i) is due va v vb. and the last incquality (ii) is from
Vab S a where c 0 is absolute constant. Therefore, combining eqns. 49 50, 51
and the choice of bonus 20 can conclude that k.pt (s. a)
i Qi (s, z 0.
Proof of Ineq. 2: By Proposition 9 (Robust Bellman Equation) and eq. we have that
2t. - O (s, a)
-max
Opti (v,a)
[un* .o:
- B (s,
otatiin (s, (0.
< max
Pei (m.a)
v** 1,b+1
- Opp (s.a)
(s,,
(52)
where second inequality follows from induction V. 2 Viit at the + 1-th 1i++1
step and the fact that Q 2 0. By Lemma 23 we can confirm that
ei Varpp ph
4 .p:
/ ,p ih+1
((.(a)))
iht1
- -pp)((aa)
(s,
E (p
kki. (iht1 (it11)
kkn
H +
CHHSSt.
1
+
(53)
(N, V VK
34

---

Published as a conference paper at ICLR 2026
Now by further applying Lemma 26 to the variance term in the above inequality, with an argument similar to eq. 550 we can obtain that
Varpp
(intin siht1
S
{N
Vhile - [ihh+1)
E (1s.a)))))
H
(54)
(s, V13
VK
where d' > is an absolute constant. Therefore, combining eqns.
52
53
54
and the choice
bonus in 20 Q E.Pi (s, a) - Q PP (s. a) S
Therefore, by eq. 51 and eq. 54 we have proved that at step h. it holds that
(s, S Qinh a), Qhi (s, a) s o ot (s,
Qih
(55)
We now assume that eq. 47 hold for h-th step. Then, by the definition of robust value function as given by robust Bellman equation (Proposition 9. and eq. g and NASH Equilibrium, we get
R.pi Qin (s. a)
k.Pt Qihh (s,a)
i.h
Bawr"((s))
max EE Ba ()
(56)
By the definition of - siPL ihh
(s) in eq.
get
yt R: (8) max E
n x (1
(57)
x
Since by induction, for any (s, a).
Q
(s,
2 Q. Ql (s, As result, also have
khii (s) 2 vita timii.p (s), which is eq.
48 for h-th step. Similarly, can show that
Vhlee (s) = E Ea (-1s)
Q (s a)
E
Ba (1x)
~ (s,
(6)
v pt (s)
(58)
i.h
where (i) is due to the fact that 1hat (s, a) S Q .Ps (s, a) and (ii) is by definition of v (s) as
given by Bellman equation in Proposition
CCE VERSION: OPTIMISTIC AND PESSIMISTIC ESTIMATION THE ROBUST VALUES TV-DRMG.
Here will proof the optimistic estimations are indeed upper bounds of the corresponding robust V-value and robust Q-value functions for CCE version.
Lemma 21 (Optimistic and pessimistic estimation of robust values for TV-DRMG for CCE version). By setting the bonus term 3% in eq. 20 with probability 1 5, for any (s. a, h, i) and k [K]. holds that
max OooT* .P (s. S Q.A. (s, a), PED; i.
k.p.
Q (s, a) S Q (s.
(59)
max t (P((s) < Ti (s), vha (s) S V (s).
(60)
35

---

Published as a conference paper at ICLR 2026
Proof. The proof-lines similar (Ghosh et al. 2025) adapted to the multi-agent case. We will run a proof for each inequality outlined in Lemma
Ineq. 1: To prove Qi
tta= 1 (s, Tie (s,a).
Ineq. 2: To prove 2 (s, a) S 2 a).
We know that, step h = H P +. (8) yf."* 1oPe (s) (s) 0. Now, assume that both eq. 59 i,8+1
and eq. hold the (h 1) step.
Proof of Ineq. 1: We first consider robust Q at the /-th step. Then, by Proposition 9 (Robust Bellman Equation) and eq. we have that
0 (s,
- (s,
=min pop (s,a)
Vileo (ih--
8th (s,
Qia (s. (s.
(s)a)
2 min
{o Pii (ma)
vit i,++1
(e.a)
(e.a)
8K (s, 0).
(61)
where the second inequality follows from the induction of yi 1,h+1
Rip i at the 1-th
step and the fact that Q 1. rli by Lemma
17 By Lemma 23 get
c1 Var 1,+1 )
V pP ihtt
Pi (s.a)
Opp (s,a)
(s, V1}
H2Hi + VK
1
(62)
(s.
Now by further applying Lemma 26 to the variance term in the above inequality, we can obtain that
t ih+1
(s.a)
Opp (v,a)
yhting p.:pp Vihli 2
Varps((aaa)
+4E (2()))
Viht1
(N)(s,)) V1)
H2
(N) V1 + VK
Thips Khe Kihh
Vite khipi
(1)
(8, V1}
HH +
+ (NH(sa) VR
Thini + kip thin 2
Thue vhiee
E (-(laa)))
(6)
(N) V1
H
H&ly
(63)
(N((,,) VK'
36

---

Published as a conference paper at ICLR 2026
where the inequality (i) is due va+b Vā + vb, and the last inequality (ii) is from
Vab I where c2 is absolute constant. Therefore, combining eqns. 61 62 63
k.PL and the choice of bonus in 20 we can conclude that Qih (s, a)
Q :
1. 1
(8, a 2 0.
Proof of Ineq. 2: By Proposition (Robust Bellman Equation) and eq. 6 we have that
2h (s. a) - 0 " Pi (s, a)
=max
Pii (+.a)
pkkpp
1
0 (rp (e.aa
V= 1,4+1
(s,
(
vT .p: 1,6+1
- .p: 1,441
p (s, 0}.
max
Pii (e,a)
Opt (s.a)
(64)
where the second inequality follows from the induction of V. -pi 2 iitt 1 at the h + 1-th step and the fact that Q,""" O. By Lemma
1,4+1
23
we can confirm that
ci Var pa
V 1,++1
)
P
P(a(saa)
S
(
Tkipi
kkoi
+
H
S (N)
(65)
VK
Now by further applying Lemma 26 to the variance term the above inequality, with an argument similar to eq. 62 we obtain that
ca Var pt
Pp iht1
VT' sp ii4tl
(a,a)
Oppi (p(a)
S
(N (3, V1
E Epp (11s.))
1,1+11
H
H
(66)
(N, a) V13
VK
where o 0 is absolute constant. Therefore, combining eqns. 2 A (s. s O.
64
65
66
and the choice
of bonus in 20 Bh as.
Therefore, by eq. 63 and eq. 66 have proved that step h. it holds that
Q PP as,a) I Qh (s,a), Qu (s,a) a) I O (s,a).
(67)
We now assume that eq. 59 hold for h-th step. Then, by the definition of robust value function as given by robust Bellman equation (Proposition 9. eq. g and CCE Equilibrium, we get
Kenps (s) E Ba-xh((1s)
R.Pi Qin (s, a)
max EE Baanfx x!
(s, a)
(68)
By the definition of Vi (8) in eq.
3 we get
V 1m sips
e oPi (s,
i.
(s)
max R
a xm (-10))
(69)
x!
37

---

Published as a conference paper at ICLR 2026
Since by induction, for any as, Quk a)) 2 Quh
1oth 1it ( (s) As result, we also have
Vhi (8) 2 V (s), which is eq. 60 for 1-th step. Similarly, we can show that
[ott (s, (s,
(s)
E Ba (+|s)
10,th (s, (s,
E
v i.
(s)
(70)
where (i) is due to the fact that 2 (s, a)
I Q -Pi (s, a) and (ii) is by definition of V (s) as
given by Bellman equation in Proposition
CE VERSION: OPTIMISTIC AND PESSIMISTIC ESTIMATION OF THE ROBUST VALUES FOR TV-DRMG.
Here we will proof the optimistic estimations are indeed upper bounds of the corresponding robust V-value and robust Q-value functions for CE version.
Lemma 22 (Optimistic and pessimistic estimation of the robust values for TV-DRMG for CE version).
By setting the bonus term 3h,n, as in eq. 20 with probability - 8, for any (s, a, h, and E [K], it holds that
L Qik
(s, S Qinh (s,a),
k.P:
Q (s, a) S Q Pi (s,a),
(71)
Vli (s) S i. (s), 4,
RiPE
kkp. i.h
(s)
V 1
(s).
(72)
Proof. The proof-lines are similar to (Ghosh et al. 2025) adapted to the multi-agent case. We will run a proof for each inequality outlined in Lemma 22
t.at.0n (s,a)= S T (s, Ineq. prove Qi
Ineq. 2: To prove 2f (s,a) S Q "s, a).
k.p: We know that, at step h = /1 + 1, V (s) = i1141 (s) = 0. Now, we assume that both eq. 71 and eq. 72 hold at the (h + 1) step.
Proof of Ineq. 1: We first consider robust Q at the h-th step. Then, by Proposition 9 (Robust Bellman Equation) and eq. we have that
Q. a) - t.t=-.0p (s, a)
-min
pon (a.0)
V imh-1
+ (s,
Q. Qtatiipt (s)
by Vitti
+ (s, 0}.
2 min ( (aa)
app (e.a)
(73)
where the second inequality follows from the induction of p fltt1
< khip at the h 1-th
step and the fact that t.r_.np < v by Lemma
17 By Lemma 23 we get
ci Var
ytot
Vtta sh+t
p
(s.a)
ch41
-ppi (s,a)
(N V1]
C2Hi
1
+
(74)
(N VK
38

---

Published as a conference paper at ICLR 2026
Now by further applying Lemma 26 to the variance term in the above inequality. we obtain that
bore sips i,+1
V sipe ch+1
p. (a,0)
Oiih (a.a
kioo
Libia + ti h+t 2
Varpy(1aa)
+ +4HE (-1,,a))
(s) V13
1 + (N, V13
ozHi
VK
Viltit hig + 2
Vhuei vki
C1 Sioaarpeels.
4He (1..)))
1,++1
(s)
(s, V13
o2
(NE(s,))
VK
(0) (N VK"
GuVar (RCl
E (-1o,a)
Vinti 1i,
(s)
H
H'd +
(75)
where the inequality (i) is due va v vb. and the last incquality (ii) is from
Vab S a where c 0 is absolute constant. Therefore, combining eqns. 73 74 75
and the choice of bonus 20 can conclude that k.pt (s. a)
Qi (s. a) N 0.
Proof of Ineq. 2: By Proposition 9 (Robust Bellman Equation) and eq. we have that
2t. - T.T (s, a)
[um* .o
- (s, etattin (s
-max
Oppi (v,a)
v** 1,b+1
- (s, 0).
< max
Pei (s.a)
- Oppl (s.a)
(76)
where second inequality follows from induction V
2 Viit at the + 1-th
1i++1
step and the fact that Q 2 0. By Lemma 23 we can confirm that
ei Varpp ph
4 _p:
T sp ih+1
p
((.(a)))
iht1
- -pp(((aa)
I
(s, v
E (+lo.a))
k.P. (itt1
kkn
H1
S
(77)
(N V1]
VK
39

---

Published as a conference paper at ICLR 2026
Now by further applying Lemma 26 to the variance term in the above inequality, with an argument similar to eq. 74 we can obtain that
e1 Varpa )
Vaa 12 iht1]
Vo :pc 1,+t1
0 p (x,a)
- (p.
S
V13
E (p
+
H
SHH
(78)
(N
V13
VK
where d' is an absolute constant. Therefore, combining eqns. 76
77
78
and the choice
bonus in 20 Qu (s, (s)
Q (s. S
Therefore, by eq. 75 and eq. 78 we have proved that at step h, it holds that
k.Pt Q iipt (s, S Qinh (s,
2th (s, a) s o (s,a).
(79)
We now assume that eq. Tolld for h-th step. Then, by the definition of robust value function as given by robust Bellman equation (Proposition 9. eq. and CE Equilibrium, get
V (s) = Ea-a (118)
k.P: QiA (s, a)
RiPi Qih (s. (s,
max Ea Φe
(80)
By the definition of max ddoo" dea;
pi (s) in eq.
get
mAx Vdoo** P: (8) = max aa-oor (11s) max Q (s, dEP.
(81)
Since by induction, for any (s, a),
kips (s, 2 max Quoor (n (8, a). As a result, we also have Qu
DE
V Pi (s) max yoot" .e (s), which is eq. 162 for h-th step. Similarly, we can show that
Vkie (s)
Bart (-1s
@ (s.a))
(
T (s,
E Ea (11))
(0))
yx" pi (s)
(82)
i
where (i) is due to the fact that Q (s,
< Q sp (s, a) and (ii) is by definition of v=*... .p (s) as
given by Bellman equation in Proposition
F.3 AUXILIARY LEMMAS FOR TV-DRMG
Lemma 23 (Bernstein bound for TV-DRMG and the robust value functions of Th and Tt). Under event Erv eq. 21 and definition of n² as given eq. 19 we assume that for any EQUI.IBRIUM E (NASH, CE, CCE) the optimism and pessimism inequalities holds at (h + 1, k), where these inequalities can correspond to any of the following cases of EQUILBBRIUME
NE: Lemma 20 using eq. and eg.
CCE: Lemma 21 using eq. 59 and eq.
60
CE: Lemma
22 using eq. and eq. 72
40

---

Published as a conference paper at ICLR 2026
Then, it holds that
[VT (1+11
0
Pla (s.aa
11--1 pf (0,0)
a Vargk 1,41
+ 1
if π
(ealvi)
VK
a Var
E Eppcinan
Viiet v 1,44
di S (x.vi))
+ VK
otherwise,
(xa]vi)
H
and C1, 6 > O are absolute constants. ( A,)
where
log
Proof.
By our definition of the operator pia (s.aa)
(V PP 1,h+1 in eq.
11 we can arrive at,
lo po
[VT .(1] (en()
Jp. (s.a) (s.
[V .P1
1,4+1
S
sup nE(0.
E (( [11
V
i,4+1 )+]
-Epp s, [111
V
1,++1 )
Term (i) + Term (ii).
(83)
where we denote
E Epg [(n Vilhi1" - )+] Epp ((lo.)) (n7 vitart )+
Term (i) == sup []
(84)
(Epccisa) (n- vinht
-(1
17--iline Vit iittl
Term (ii) == sup nE(U,H]
(1- v viiifi))
- vatti
(85)
We deal with Term (i) and Term (ii) respectively.
Bound for Term (i): Term (i) is referred to Bernstein bound for Bernstein bound for TV-DRMG and the robust value function of the robust best response tipt (m= More specifically, we find the Bernstein bound on the gap definition of the operator "P"i
- "p (s.a) 1,h+1 (01)) Therefore, by the
(s.a)
ii+11
/ Pi 1,441
in eq.
we can arrive at,
(V wipi
1,1+1
Epptlea))
(1-
(1-
vtaainn (1
< sup nE[O.H]
Epp(-ls.a)
= Term (i).
(86)
By now according to the first inequality of event E in eq.
21 we can bound eq.
86
ci Var pa (n 1 ){
Hi
Term (i) S
(N, a) V1
(N,
tiat (i0s)
ci Var ae
i,++1
rgHi
(87)
V1
(N
41

---

Published as a conference paper at ICLR 2026
for any n N1/(SVK) ([0, H]). Here the second inequality is because Var x)+1 I Var[X].
(l0,
Therefore, by applying the covering argument eq. 87 for any 1 E [0, HJ it holds that
ei Varpy (Vileti ioPs 1,441
).
cy (M.
Term (i) S
(88)
(s,
vK
Bound for Term (ii): For Term (ii), we apply the second inequality of event in eq. obtain that
21 and
C1 min (
s, a), (s s, s,
C2
Term (ii) S sup n
(N V1}
(N)(s,)) v
S'ES
(1
v ih+t1
x
-
(89)
Now by assuming that eq.
48 holds at (h + 1, k.), we can upper bound the absolute value above by
(1
11 VITh v.)
v .ps
V
i,++1
(6i)
kip: i,h+1 (5')
Vk.pi i,h+1 -
(5')
(90)
where the first inequality (i) is due to the 1-Liisshhizz continuity of uh (x) = (1) - x)+, and the second
inequality (ii) is due eq. 48 Thus combining eq. 89 and eq. 90 we get
ci (s' s,
Term (ii) <
Σ 8'8
C2
(o - x())t((6))
{NN (s.
V1}
(N)
(R 8,a) H
CiH
C2
(s)
S'ES
V (s')
(3)
E Exp(
Vkips
61h+1
DR..p Lihtl
CH (s)
(91)
H
where cg > 0 is an absolute constant.
The first inequality (i) is by aa < a + b and the second
inequality (ii) is due to Vi Vigt (0, H). Finally, by combining eq. 88 and eq. 91 and applying in eq. 83 we get the required bound as
a Var (viitt.P)) E (p
Vho kipi i,tt1
6gH2S
Term (ii) S
\
(N)
H
[N ()) V
+
(92)
KK
This concludes the proof of Lemma 23
Lemma 24 (Bernstein bound for TV-DRMG and optimistic and pessimistic robust value estimators).
Under event ετy in eq. 2/ and definition of m² as given in eq. 19 we assume that for any EQUILIBRIUM E {NASH, CE, CCE) the optimism and pessimism inequalities holds at (h + 1, k).
where these inequalities can correspond any of the following cases of EQUILIBRIUM:
NE: Lemma 20 using eq. 47 and eq.
48
CCE: Lemma
27 using eq.
59 and eq.
60
42

---

Published as a conference paper at ICLR 2026
CE: Lemma 22 using eq.
71 and eq.
72
Then, it holds that
[vint
pkip iiht1
max
(a,()
Opei (e,a)
(ihtll
pic (s,a)
Opppi (s,a)
c Varpa
V-t.ot
",41 )
E
Epaclesa)
Vilip
iih+1
Vlipp i
(s)
H
(s)
VK"
( 1,) and c1 2g > O are absolute constants.
where log
Proof. This follows from the same proof as Lemma 23 and thus omitted.
Lemma 25 (Non-robust Concentration for TV-DRMG), Under event Exy in eq. 21 and definition of x² given in eq. 19 assume that for any EQUILIBRIUM (NASH, CE, CCE) the optimism and pessimism inequalities holds at (h + 1, k), where these inequalities can correspond to any of the following cases BQUILIBRIUM:
NE: Lemma
20
using eq. and eq.
48
CCE: Lemma
21 usinge eq. 59 and eq. 60
CE: Lemma
22 using eq. 71 and eq.
72
Then, it holds that
Vkkp kk.pt i,tt]
E Epp((l,.)
Viiee kips
Vhon Rege
Poee 1,4+1
kkkpp 1,++11
EE Ph (-leaa)
1,h41
i1+41
d H
(s)
where 1 = log S' A.)H2R3/2
and di > 0 are absolute constants.
Proof. Assuming that eq. 48 holds for (h + 1,k), we apply the second inequality of event & in eq.
21 to get the required bound Lemma 25
Lemma 26 (Variance analysis for # for TV-DRMG), Under the definition of n² given in
eq. 19 we assume that for any EQUILIBRIUM E (NASH, CE, CCE) the optimism and pessimism inequalities holds (b++kk) where these inequalities can correspond to any of the following cases of EQUILIBRIUM:
NE: Lemma 20
uusinn eq. 47 and
48
CCE: Lemma
27 using eq. 59 and eq. 60
CE:: Lemma
22 using eq. 71 and eq. 72
Then, it holds that
Var (l.a))))
kip + thes thht 1h:1
Var (ar)
foat ih41
<
4H
(
R.
1k h+1
43

---

Published as a conference paper at ICLR 2026
Proof.
Our proof closely follows the lines of Lemma 22 in (Liu al. 2021 and Lemma E.11 in (Lu
ct al.
2024). with detailed elaboration on each step for clarity. The left hand side the incquality in
Lemma
26 can be upper bounded by the following
V i,++1 + p.
vtv== sh+1
Var Varpt (-1s,a)
Var Pt (-1s,a)
Vips iiitl + Vkipp
Lihht
2
v vptintee sope 6h41
27
L8 pk (-loaa)
Viige ii++1 +
I]
+
Ppp (1)5,a)
(intt
(93)
By applying eq. 48 and the facts that Vhet s,tt1 and Vhen
E [0, HJ. we
can further upper bound eq. [93as
kip: i + Vhee
vntiate espo] hhtt1
Var pt(-sa)))
Var p((()10a)
2
I 4H (pge-ls.)
Thin 1.6
+ Vi
tomt 1,441
I 4H Bppe-laa))
Vihti - VK,00
(94)
This concludes the proof of Lemma 26
Lemma 27 (Variance analysis for any robust joint policy n² for TV-DRMG). Under event EτV in eq. 21 and definition of π² as given in eq. 19 assume that for any EQUILIBRIUM e
(NASH, CE, CCE} the optimism and pessimism inequalities holds at (h + L,k), where these inequalities correspond to any of the following cases of EQUILIBRIUM:
NE: Lemma
20
using eq. 47 and eq.
48
CCE: Lemma
21 using eq. 59 and eq.
60
CE: Lemma
22 using eq. and eq.
72
Then, then the following inequality holds,
V iitt1
k.ps
kipp Lihhi
]
voat ip 1h+1
Var Varpy (-Ia,a)
- Varpg((ea)
- Vhipi h+1
+1.
(s,
Proof. We follow the proof-lines of Lemma 23 in (Liu et al.
2021) and Lemma E. 12 of (Lu al. 2024). We present detailed derivation as follows. We first relate the variance on Pk to the variance on P. Specifically, we have
V Kip:
V.
}
i
[v .e
Var pt ((
Varp:(1le.a)
< Term (i) + Term (ii), (95)
where we denote
Vhin +..t.
iihts t.
Term (i) =
Var (-)l.a))
-Varpg(-la.a)
(96)
V kipe i,tt1 -i,h+11
)
T .pi
Term (ii) = Varp;
Varp
(97)
2 We will now bound Term (i) and Term (ii) respectively.
44

---

Published as a conference paper at ICLR 2026
Term (i): By applying the fact (Vi
iih+1 + V.hni kihbt )
/22 [0, HJ in the variance terms on
Term (i), we upper bound Term (i)
Term (i)
112
Σ s'ES
Ph (s (s'(s,))))
ci ( ss,a).
H
22 V (8, V13 (M
S'ES
(6)
e2Si (s) (s,
enSt
$ H2
(06)
SH'S.
1+
(98)
(s.aa)
where the inequality (i) is by the second inequality in event & in eq. 21 the inequality (ii) is by Cauchy- Schwartz inequality and the probability distribution sums up to 1, and the last inequality (iii) is from the fact vab & a a+b
Term (ii): By using the proof-lines of Lemma 26 and assuming that the optimism and pessimism inequality eq. 48 holds for (h + 1, k)), we can bound Term (ii) as
Term (ii) < 44H (1sm))
W44
(99)
Applying eq. 98 and eq. 99 we get the required bound in Lemma 27
G
PROOF OF REGRET BOUND OF KL-MORNAVI
Similar to GGosh al. 2025). consider the following definitions:
S A (s, a) min
| (s'lss s a) =))
(100)
ES
P min, (s, a) == min (s'lss a) (s 0},
(101)
eS
min P* (b.))
P P (s)),
(102)
where the following inequality is satisfied: () 2 P (s) 2 p P
We now recall the bonus term of KL-MORNAVI for agent episode i at step h, follows:
H
I V
B (s, a)
V
(103)
di V a) min (s,
where P.: P (s. a) (P) and ey is an absolute constant.
(s a) 0}, loog S2 (I 1)H233/116)
Before proceeding to all key lemmas, we introduce the nigh-probability "typical" event EKt. in the lemma below. The proof strategy follows (Lu et al. 2024) and (Ghosh et al., 2025).
Lemma 28 (Uniform Concentration Bound of event εKL). Let EKL be the event in which, for all (s, a, s', h, k) E S x A S x H x [K], and for all in a Sv -covr of [0, H Pmiul and is
45

---

Published as a conference paper at ICLR 2026
defined as
exp Vh+1 }1) log Epp( s.a)
Vh+1 }
ExL
log
E Epp(-1s.a)
exp
L
I sa1 (N V 1} Ph
1} min,h ())
((,,
H
}} (104)
8 x [K], VKJ V(,, 8, a, 6 kk) [ x
Pimi Pmin
SVR
Pmin
where Pk min. (s, a) is defined in eq. 100 log (
ci i absolute
constant and 7) N Proin
(10, [//minn), where Pmin = min P; and N (10, PMmm))
Puntr
denotes an SPmin K cover of the interval [0, H/Hmii/mn) )
Then, this event εK2. occurs with high probability, i.e., Pr(ExL) 2
Proof. The proof follows standard techniques: we apply classical concentration inequalities followed by a union bound. Consider a fixed tuple (s, a, h) for a fixed episode Now we consider the following equivalent random process: (i) before the agents starts, the environment samples {1()), g(2) ...... ....,,(( g(k-1) independently from P7 (-Is, a), where g(t) S denotes the state sampled at episode i; (ii) during the interaction between the agents and the environment, the i-th time the state and joint actions (s, a) tuple is visited step h, the environment will make the agents transit to the next state g(t), Note that the randomness induced by this interaction procedure is exactly the same as the original onc, which means the probability any event in this context is the same as in the original problem. Therefore, it suffices prove the target concentration inequality in this context.
Based on the above fact, we directly apply (Wang et al. 2024d. Lemma 16). To extend the bound
uniformly, we apply union bound over all tuples (h, s, a, s' k, [H] x S A x S x [K] x N // RV) (10, H ///mi))) Note that the r-cover for each agent lies in the interval [0, H/ pt) <
[0, H/ Pmin]] for all E M,, and this cover contains a valid P.SVK -ovvr for each agent-specific
interval (0,
#1 p Therefore, we define the common 1y-oovrr as 1) E N
([o, pmii 1). where Pmin
SVR
A
([o,,
Penins )) denotes
Pmiin S VR -over of the interval Jo.
H
Pinin
Panin
PROOF THEOREM (KL-DRMG SETTING)
Proof. With Lemma 32
we can establish an upper bound on the regret by considering the difference between our optimistic and pessimistic value functions:
K
RegretNAsH (K)
max m Σ
ti SEM 1,1
V (P (s))
max
Vho ( (105)
kip i.1
E.
For the KL-divergence uncertainty set, we will refer to the bonus term as B (s, a), as given in eq.
103.
Our first step is to establish bound on the difference between the upper and lower Q-values.
Mine Given our definitions for Q Qlaes i Ligh and the bonus term Bha (s, a) defined in eq.
5 through eq. 103, for any (i, h, k, 8, a) M x [ x
[ x S x A, we have
Qui
k.Pt (s, a) 2t (),
kips ch+1
Vki iih+1
2. (s,
(106)
P
(s.a)
(s.a)
We define the following terms, A and B. to simplify analysis:
A 0 ppi (s,a)
V.hue i
Op (s.a)
Tho: ihht1
+ Toph (s.a)
R.p [iht1
- 0 poy
(a,a)
kkpp
Lin++
(107)
B Opri (x.a)
Opfi
iitt1
(108)
46

---

Published as a conference paper at ICLR 2026
By applying eq. 107 and eq.
108 to eq.
106 obtain:
Qihh (s, a) 2 (s. a) s A+ B 28, (s.
(109)
We can upper bound term A using a concentration argument tailored for KL robust expectations from Lemma 30 which shows that
A S 2
pi (s, a).
(110)
For term B, we use the definition of (p. [V] from eq. 12 to establish the following bound:
exp {
V
Ripe 1,+41
}1)
B sup
17 log
(Bp:(110.0)
nE o.
"
{
Vkies
}1) np:
sup EE 0o.
- 17 log
(pp(-)asa))) exp
P.
Vkin iib+1
}1)
sup n/
17
log
Epp (-1x,a)
exp
7
V ki
i
-log
Ep (pp(.la.a)
cxp
exp
sup H/(0
log
E (1
exp
Tik.pt
E (11,,))))
exp
exp
77
sup HE(o
17 log
+
v
Bpt
exp
ihil
cxp
exp
IVE
"
sup 17
Vi
Epp(le.)
exp
V k.ps 1.441
ksp V
IA3
H
2,++1
exx nE(n.H/ed
sup
E Eppe-la (1)aa)
exp
exp
?
17
exp
H
E Eg (s.a)
Vilee Vi+++
kip i1h+1
(111)
Vkipp k.p:
where inequality (a) uses the fact that log(1 + x) S inequality (b) holds because 0 S
i,,+1
S H
and 17 [n. H//p., and inequality (c) is due the for x 2 0, as well as Vir I Viup: Vi++1
17 L-Lipschitz continuity of (,((x) exp }
By applying the bounds for and to eq.
109
we get
k.pt (s. a) Qui (s, a) I exp
H
(pg
T
Vh ihtt1
+ P (s. (112)
Using Lemma 31 to upper bound the bonus term, and rearranging the terms, we further obtain:
Qui (s, a) - 2th (s, a) s exp
E (p
pkop, i,h+1
4c1 H
12
4 +1
(113)
Pmin
V
(N a) VIP...
47

---

Published as a conference paper at ICLR 2026
where 01 > 0 is an absolute constant. From the definitions in eq. 8 the difference in V-functions is given by:
i.h ViA (s) - ViLl (s) = -Eantt(1a Qinh (s, a) - 24 (s, (s.
(114)
We now define a new recursive value function Vi Viiipmin and corresponding Q-function P.imii with Vkiinmin O, where Puain = min Pt: JEM
H41
Qh (8, = exp {
H
Prlppann h+1
4e1 H
2 +
1 4 K
R Pz (o,a)
+
(115)
!
Punin
(N V13P
vh Priin (8) = E (116s)
@h (s,
(116)
By an inductive proof, we can show that for any (i, (i,,, Ex [H] x S x A. the following bounds hold:
max Qu - -hh (8, S Shilaain (8)
max iEM
Ripi
(117)
k.ps (Z) s Pri-Pain(s))
max
(118)
iEM
Therefore, our analysis can focus on bounding the sum Ei introduce the following notations for the differences any (h, k)
k=1 V Polin (st). For simplicity, we
K
[ x [K]:
A = Vh Puiin (s%)),
(119)
ch A PhiPai (sh a
(120)
<h == Epp (1stt,a)))))
pimppmin h+1
(121)
We can confirm that { l () and {eh (n. are martingale difference sequences with respect to their respective filtrations. By substituting eq. 115 into eq. 120] we obtain the recursive relationship:
A = Sh.h + +hh Phip (sh. a
H
4cp H
4
< ch + exp
E Ep.ceaa)
+
+
Pmin
(NV (s, a) 13PP
K
H
{ H
4c, H
12 Pmiia V (s) VIJP:
chin exp
Si
+ exp
A
11
r)
+VK'
K
(122)
By recursively applying eq. can upper bound the right hand side of eq. 105 as:
122 and noting that <
# )) exp
s (exp
#1 41)
= dH.
7
Regret (K)
A
<
dd
(Sh + Eh
1=1
Rim F=m
|cc H
12
4 KKK
} (123)
Pmnin V/ (N) (s. a) V 1)
min
Next, bound each of these two main terms. The first term, sum of martingale differences, is bounded using the
incquality from Lemma 39 yielding:
K
(h + kow &VHHKL
(124)
k=1
48

---

Published as a conference paper at ICLR 2026
where cf > 0 is absolute constant. For the second term, apply the proof lines of (Lu et al.
2021
Theorem 3) to bound the sum of the inverse counts:
K
"
S
H2KS II
A.
HHSS
HS
II A
(125)
v
A=
BEM
iEM
By applying eq.
125 to the second term of eq.
123
get the following:
11
4ci
2
H*KS(III A.)
S Sa
Pmin
Prin Pa
min
H2S TEE Ad)
H²K
(126)
Pmin
Puin
By combining the bounds for both terms in eq.
123
we can upper bound the final regret follows:
H*KS LLEEMM.)))
RAgHeE S cdd
Pmin Pr
11 114exp(2112) KS (ILEM (:)
(127)
Pmin pa
This completes the proof of Theorem 5
Remark 29. The proof techniques for bounding RegrelacE (K) and RegretcE follow the same lines of proof for Regrel K), leveraging Lemma 33 and Lemma 34 respectively, in the context of KL-DRMG.
G.1 KEY LEMMAS FOR KL-DRMG
Lemma 30 (Concentration Bound for Robust Value Estimators in KL-DRMG), Let εK be the typical event and let the bonus term Pi be set defined eq. 103 Then, the following inequality holds:
Vkuei [h++1]
[Thio ih+t1
Vk. Lihti
Vk.pe Lih+]
Pij. (8,0)
o
20
<
+
(128)
Pmiin
[N
VIJP min. (8,
where = log (5t (II A,) 12)))11) and e₁ > 0 is an absolute constant.
Proof. We begin by defining the term that we need to bound. Let's denote this term by A:
A 0 (s.a)
V [--]] (s.(a))
| h+1
+ (s.(a))
[
V
(129)
Under the high-probability event ÊKL, can directly apply the concentration inequality given in Lemma 37 This allows us to upper bound A as follows:
2
2 V
A <
+
(130)
Pmin
(Nk a) V PE min, (8,
K
where C1 0 is an absolute constant and log (S3 [I A.) H3//2/ This bound is exactly
the bonus term multiplied by constant. Therefore, based on our choice of 3 (s, a) as defined in
eq. 103, the inequality in eq. 128holde holds. This completes the proof of Lemma 30
Lemma 31 (Bound of the bonus term for KL-DRMG), Let εKL be the rypical event, the bonus term B in eq. 103 is bounded
B.h (s. a) < H
2
I
(131)
Pmin
(N
K
min
where log (53 (m A.) H2K3/2 16), and e is absolute constant.
49

---

Published as a conference paper at ICLR 2026
Proof. The proof-lines lines similar to Ghosh et al. as given in eq. 103 i.e.
2025
Lemma K.7). We recall the choice of B
(s, a) 20gH
V K
(132)
V (N a) V1 Pk min, (8, a)
where & log (S (II A.) H2 Pain (s, a) is defined in eq.
100 and cf >
is an
absolute constant.
By Lemma 38 and the union bound, holds that with probability at least ā that for all (h, a) E
[H] x S x A,
get
( s,a)
(s s, a)
ARESS (5 (,
(133)
Se22
To characterize the relation between Pi (8, a) and Pk ( a) for any (h, E [H] 8 A. we suppose-withou loss of generality-ther min,, (s, a) = P5 a) and Pmin, f (s, a)
P (s2 18 a) for some 81, 82 E S. Then, it follows that
p M a)
(81 8,
(s1
s.a)
pk
min, (8, a)
>
e²
2
Pl 8, a)
( Ph 82 8, a)
e²
P
min.h (8,
a)
Pa min Seai
(134)
S
where the inequalities (i) and (ii) follow from eq. 133 and inequality (iii) follows by eq.
102
By applying eq. 134 in eq. 132
we get
(s, a) - 20 H
1
V
9H
12
I
Pi
K
Pmin
(NH(s,)vV))P
(135)
K
This concludes the proof of Lemma 31
NE VERSION: OPTIMISTIC AND PESSIMISTIC ESTIMATION OF THE ROBUST VALUES FOR KL-DRMG.
Here we will proof the optimistic estimations are indeed upper bounds of the corresponding robust V-value and robust Q-value functions fro NE version.
Lemma 32 (Optimistic and pessimistic estimation of the robust values for KL-DRMG for NE Version), Under the event ε and by setting the bonus term 3% as in eq. 103 it holds that
gi. sPps (s, S Q (s,
Q (s, a) S 0 (s,a),
(136)
to in
(s)
Rips Vi (s),
kips Li
(s)
(s).
(137)
Proof. The proof-lines are similar (Ghosh et al. We will run a proof for each inequality outlined in Lemma 32
2025
adapted to the multi-agent case.
t.at, ,.' (s, Ineq. 1: To prove Q!aa²
<Q (s)
k.p,
50

---

Published as a conference paper at ICLR 2026
Ineq. To prove 2i (s,a) S "t a).
Assume that both eq. 136 and eq. 137 hold at the (h + 1)-th step.
Proof of Ineq. 1: We first consider robust at the h-th step. Then, by Proposition 9 Bellman Equation) and eq.
(Robust
5 we have that
Qin t.a (s, Quhh (8,
max (pplllaa))
Viieo (,++1
(s,a,
Qia
t. (s, (s
as HH.
I max
Opt (s.a)
(138)
Pii (s,a)
where the second inequality follows from the induction of vi 1
S R.p: at the h 1-th S. H. By Lemma 35 and by the definition of Ph. Phinn (s, a)
step and the fact that Q i.
given in eq. 100
we have that
vlii* s,4+1
Vilittirn
C.H
L a) (8,
o pft Ppji(ssa (s.a)
Pi (siaa)
S
Ps
pk
min, (8, a)
I
K
K
(139)
By the choice of 8h in eq. 103 and eq. 139 and applying eq.
138
we conclude that
Q
tta
(8, a) S Q (s,
(140)
Proof of Ineq. 2: By using Proposition (Robust Bellman Equation) and eq. 6 we have
that
2ui (s, a) Qit (s, a)
= max
Vkiee σ piy (s,a)
i,h+1
( pi ope (ara)
i,0+1
- (s,
Q (s;
-
(141)
v 1,+11
Vit pp] ih+1
3 (s, a), o
< max
σ pr (s,a)
-
Ope
Opth (s.a)
(142)
where the second inequality follows from the induction of Light step and the fact that Q .P:
V. pe the (h 1)
iit1
2 O. By Lemma
36
we get
[vetit]]
V m
L. Pi (Nt(s,a)
H
1hh+1
Pk & (s, a)
V K
(143)
By the choice of B,,, in eq.
103 and eq.
143 and applying in eq.
142
we conclude that
Q
t. vi
(s, < Q k.P:
(s)
(144)
51

---

Published as a conference paper at ICLR 2026
Therefore, by eq.
140 and eq.
144 we have proved that at step h, it holds that
Q ii
(s,a) I
Qi, (s, 2hx (s, a) I Qi (s,
(145)
We now assume that eq. 136 hold for h-th step. Then, by the definition of robust value function as given by robust Bellman equation (Proposition 9). eq. and NASH Equilibrium, we get
Qihh (s,a) a)
max IE Pawr/xant Qath (8, (8,
(146)
- (s) in eq.
By the definition of Vih
we get
vta= (8) max IE anrr, x
iipi
xm (116)
(147)
Sine by induction, for any (s, a), 2 (s,a) 2 0 - (s, a). As resuult, we also have V
i.h (s)
2
v-t.==.0 2,
(s), which is eq.
137 for h-th step. Similarly, we can show that
V p. i,h
(s) = E Bawat(118
@ (s, a)
@ Pi (8, a)
E
a (1x))
(0)
VT
:i (s)
(148)
i,h
where (i) is due to the fact that 1h (s, a)
< Q -ps
(s, a) and (ii) is by definition of V=* (s) as
i.h
2,h
given by Bellman equation in Proposition
CCE VERSION: OPTIMISTIC AND PESSIMISTIC ESTIMATION OF THE ROBUST VALUES FOR KL-DRMG.
Here we will proof the optimistic estimations are indeed upper bounds of the corresponding robust V-value and robust Q-value functions fro CCE version.
Lemma 33 (Optimistic and pessimistic estimation of the robust values for KL-DRMG for CCE Version). Under the event ε and by setting the bonus term 3% as in eq. 103 it holds that
Qin
t. siPe (s, S QuP
k.Pt (8,a), Quipi (s, S Q (8,a),
(149)
vtaa liss (s) R.PI (8), V (s) V sm (s).
(150)
Proof. The proof-lines are similar (Ghosh et al. 2025 adapted to the multi-agent case. We will run a proof for each inequality outlined in Lemma 33
tt (s, S 2h (s, Ineq. 1: To prove Q
Ineq. To prove Q (s, a) S " (s, a).
Assume that both eq. 149 and eq. 150 hold at the (h + 1)-th step.
Proof of Ineq. 1: We first consider robust Q at the h-th step. Then, by Proposition 9 (Robust Bellman Equation) and eq,
5 we have that
2..0% (s.
o (8, a)
Thie
=max (Ppi
(s)
p.i (s.a)
hirteipe (s, -H H
ylint sp 11ht1
- -hals,, 0). (151)
< <max (ppi(aa))
Vitt1
pr (s.a)
52

---

Published as a conference paper at ICLR 2026
where the second inequality follows from the induction of v. pP 1,/+1
Vhipt S i at the h+ 1-th
step and the fact that Q f
h < H. By Lemma 35 and by the definition of Piin, (8, a)
as given eq. 100 we have that
v
v 1,+1
CIH
L (N a) V V min,h (s, a)
Piu (s,a)
S
V
Pi
VK
(152)
By the choice of B in eq.
103 and eq.
152 and applying eq.
151
we conclude that
Q oi (8,
K.P: Qi
(s)
(153)
Proof of Ineq. 2: By using Proposition (Robust Bellman Equation) and eq. 6 have that
Qhipi a)
oh (s,
max
p ((((aa (a.a)
Vhipi Liht1]
0 ppp (t.a)
(V ii+11
(s.
I max
Op (s,aa
-ppi (s,a)
[vitit]]] vp
(154)
where the second inequality follows from the induction of kkpi step and the fact that QT, ,P:
v in iht1
the (h+ 1)
2 O. By Lemma 36
we get
1 .p:
H
L
pri (c,a)
(s.a)
iht1
Pi V
V
min. a)
(155)
K
By the choice of 8k in eq.
103 and eq. 155 and applying in eq.
154
we conclude that
Q vi (s, a) S Q k.P:
(s,
(156)
Therefore, by
153 and eq.
156 we have proved that at step h, it holds that
1. ii (s,
QhiiP (s, a),
Q.api (s, a) s Q (s,
(157)
We now assume that eq. I49 hold for h-th step. Then, by the definition of robust value function as given by robust Bellman equation (Proposition 9.. eq. g and CCE Equilibrium, get
k.ps i.h
(s)
Bawx+(-1))
Dii (s, a)
max E Bannjxtt (6 1 kips (s, (s,
(158)
By the definition of Vi (s) in eq.
we get
v
i.
1. si (s)
max R
a xm (-10))
xpt (s,
(159)
x!
53

---

Published as a conference paper at ICLR 2026
Sine by induction, for any (s, a), Quk (s.a) 2 Q Qun sifi
= (s, a). As a result, we also have V i.f
(8)
vite" (s), which is eq. 150 for h-th step. Similarly, we can show that
6,6
k.00 1.4
(s)
Bawa+((1)) (-1b)
(9,(())))) (s,
E a (-1s)
(
(6)
V .p (8)
(160)
i.h
where (i) is due the fact that 2 (s, a) I Q .pi (s, a) and (ii) is by definition of V=* (s) as
given by Bellman equation in Proposition
CE VERSION: OPTIMISTIC AND PESSIMISTIC ESTIMATION OF THE ROBUST VALUES FOR KL-DRMG.
Here we will proof the optimistic estimations are indeed upper bounds of the corresponding robust V-value and robust Q-value functions fro CE version.
Lemma 34 (Optimistic and pessimistic estimation of the robust values for KL-DRMG for CE version).
By setting the bonus term B as in eq. 103 with probability 1 6, for any (s, a, h) and [K]. it holds that
mAx Q,00** .Ps (8. S Qih (s,a); SE
Qhapi (s, a) S Q, (s.
(161)
1.4
max Vddor (8(()) S Mipi (s), Vho (s) S Vi+. Pi (8).
(162)
ΦE 1
Proof. The proof-lines are similar to (Ghosh et al. 2025) adapted to the multi-agent case. We will run a proof for each inequality outlined in Lemma 34
Ineq. 1: To prove max Qu0 sn (8, (s, dE#;
Ineq. 2: To prove 2 (s, a) S Q pi (s, a).
(s,
Assume that both eq. 161 and eq. 162 hold at the (h 1)-th step.
Proof of Ineq. 1: We first consider robust Q at the h-th step. Then, by Proposition 9 Bellman Equation) and eq. we have that
(Robust
max goon** iPi (s Qhi (s)
max 1- sp. ] NEE:
max Opfii (s.0)
pi p (s,a)
Wihtl
(s)
Q (s, H.
max a
max v .p (oEt:
max poon .ps pet,
< max
Pri (s.aa
(163)
where the second inequality follows from the induction of max Vooa* 0c
(s)
k.p
at the h + 1-th step and the fact that max Q iPs (s, a) S H. By Lemma 35 and by the
54

---

Vdor* Published as a conference paper at ICLR 2026
definition of Ph min, (s, a) as given in eq.
100 have that
pp Pp (..a)
max
doxx
iP (s)
P. (s,a)
L
max Vdonn pi (s)
in
< C
L
1 V
(164)
V (N a) v vIJPi min, (8, a)
Px
By the choice of 8k in eq.
103 and eq. 164 and applying in eq.
163
we conclude that
ΦEo; f.
max
Qdon" i (s,a) I QiA (s,a).
(165)
Proof of Ineq. 2: By using Proposition 9 (Robust Bellman Equation) and eq. 6 we have that
2%i (s, a)
=max
pi (s,a)
v v 1,h+1]
-ppii (s.0)
[1h+1]
( a), 0
-ith
v pi (,++1
x 1,++1
(s, a), of
S max
(s.a)
Pi (s,a)
Opi (+.a)
(166)
where the second inequality follows from the induction of h.p. Li,++
V at the (h + 1)-th
step and the fact that " 2 O. By Lemma
36
we get
( spc [itt]]
T .pc
cill
L Pi V (N Pk Mi (8,
p (e,a)
p (s.a)
(167)
By the choice of 3h in eq. 103 and eq. 167 and applying in eq. 166 we conclude that
Qhipi (s,a) a) s Q Pn (s,
(168)
Therefore, by eq.
165 and eq.
168 we have proved that at step h, it holds that
max D
Q (s
k.p: (s,a),
Qi:0i (s,a) S Q (s,
(169)
We now assume that eq. 161 hold for h-th step. Then, by the definition of robust value function as given by robust Bellman equation (Proposition
9. eq. g and CE Equilibrium, we get
Vkk i.k
(s) = (a-nt(is)
Q (s, a)
k.P:
max Ea-dor ΦE#;
R.P. Q (s. (s.
(170)
By the definition of max vdok sE I.A s: (8) in eq.
3 get
max Co'oo's P (s,
(s) max E (11
(171)
NEO,
des;
Since by induction, for any (s, a),
Qih (s, > max Q a)) As result, we also have
D
kki i.b
(s) 2 max ydox"ie d: (s), which is eq.
162 for h-th step. Similarly, we can show that
6E#,
yk.p (8)
Bawa+(()))
L (s, a)
E3
Bart (11s)
Q (s, a))
(6)
va
m (s),
(172)
i.
where (i) is due to the fact that Qhee (s, a) < Q
pi (s, a) and (ii) is by definition of w .p (s) as
i.
i.h
given by Bellman equation in Proposition
55

---

Published as a conference paper at ICLR 2026
G.2
AUXILIARY LEMMAS FOR KL-DRMG
Lemma 35 (Concentration of Value Function in KL-DRMG), Under the typical event Exi. as defined the following concentration bound holds with probability least
eq. 104
V 1,++1
vilictee 1,b+1
G V (N
I. a) a) min,
0 PP (s,a)
- Ppf (s,a)
(8, ms VK'
where 1 =oog
53
A3) and is an absolute constant.
Proof. This proof establishes concentration bound for the difference between the empirical and true robust value functions. We use the definition the KL-divergence operator op (s.a) [V 1.
(s.aa
1,++1
from eq. 12 and the empirical minimum probability Phin, (8, a) from eq. 100 to express this difference as supremum:
v ih+l
V -ii="1pp ih+11
T (hi()
Opp, (sxaa)
S sup ") nE(9.H/pi]
log
(pp((aa)) (expl
31)
log (pp(()a
(173)
Under the high--rohan probabbiitby event EKI. (defined in eq. 104), we apply known concentration inequality from (Wang et al. 2024d Lemma 16) bound this expression:
Vytan 1,++1
t.m c,++1
C1
L
Pil (s,aa)
(s.a))
Ps V (N a) V1 W m (8, a)²
P
(174)
This bound holds for any 7 within a fine-grained cover of the interval [0, H1 P/inn]] By applying standard covering argument, extend this bound to hold for 17 [0, H/ Pmiin. thereby concluding the proof of Lemma
Lemma 36 (Bound for DRMG-KL and the robust value function of x²*). Under event Egt. in eq. 104 and for any EQUILIBRIUM E {NASH, CE, CCE), we assume that the optimism and pessimism ieqqullities hold at (h k),,, where these inequalities can correspond any of the following cases of EQUILIBRIUM:
NE: Lemma
uusing eq.
736 and eq.
137
CCE: Lemma
33
using eq.
149 and eq.
150
CE: Lemma
34
using eq.
167 and eq.
762
Then the following bound holds:
ppa sp iit1
H
L
1
P. (s.a)
1,++1
Oppi (s.a)
Pi
(I) min (s,
+
VK'
where log (53
(TTm in Ar) H2K3/2 and e is absolute constant.
Proof. This proof establishes a concentration bound for the difference between the empirical and true robust value functions under the KL--divergence. By using the definition of the robust operator
56

---

Published as a conference paper at ICLR 2026
Pf (s.a) (V. :i) from eq. 12 and the empirical minimum probability Pee i,+11
min, (8, a) from eq. 100
we can bound the absolute difference follows:
Var .p r+++1
V 11++1
0 pol La
(x,a)
- (..(as
(s.a)
}1
sup nEIn.//pd
log E
Ept (-1ra))
expp
o
log Bpp()lna)
exp
(175)
Under the high-probability event EKt. (defined in eq. [04), and by applying known concentration inequality from [Wang et al. 2024d. Lemma 17), we can establish a uniform bound on this difference:
V pc) [it+1]
V i.h-1
C
O pri (.j.(s (s.a)
Pi V (s a) V (m) (s,
(176)
This inequality holds for any v in fine-grained cover of the interval [0, H/Pmin] We conclude the proof of Lemma 36 by using a standard covering argument to extend the bound to all v E [0, H/ Pminl.
Lemma 37 (Bounds for RMG-KL. and optimistic and pessimistic robust value estimators). Under event EKL in eq. 704 for any EQUILIBRIUM E (NASH, CE, CCE), we assume that the optimism and pessimism inequalities hold (h + k,,,, where these inequalities can correspond any of the
following cases of EQUILIBRIUM:
NE: Lemma
32
using eq. 136 and eq.
137
CCE: Lemma
33
using eq. 149 and eq.
150
.CE: Lemma
34
using eq. [67 and eq.
762.
Then the following bound holds:
max
prr (P.((a))) (a.a)
- opph (e.a)
[iiee 1/
p..
(o,a)
[int1
- Opppts.. (s.a)
pkpe (iht)
H
L V (N () Pk
Pi
min
K
where: log (53 (II A,) 12 and oj an absolute constant.
Proof. We follow the same proof lines Lemma 36 and thereby omit it.
Lemma 38 (Bound on Binomal random variable). Suppose X Binomial(n, p), where > I and p E [0, 1]. For any 8 (0, 1), we have
! )
X
inp 2 8
(177)
8 log (4)
e enp,,
np 2 log (1) in < 2 log (1)
X <
(178)
26 log (1)
hold with probability least 48.
Proof. Refer (Shi al. 2023 Lemma 8) for details.
n
57

---

Published as a conference paper at ICLR 2026
H OTHER TECHNICAL LEMMAS
Here, we present some auxiliary lemmas which are useful in the proof.
Lemma 39 (Azuma Hoeffding's Inequality). Let (Er, be a martingale with respect to the filtration (FiJiez. Assume that there are predictable processes {Ae [Ez, and [Bi with respect to (Fiheez.. Le. all t, A and B, are Fe-a--easurable, and constants to0 such that A Zt- Z Bt and Bt A I ct almost surely. Then, for all 3 > 0
C1 C2 !
2,8 Σ o
P
Zo
2 3
eexp
exp
(179)
Proof. Refer to the proof of Theorem 5.1 of (Dubhashi Panconesi 2009).
Lemma 40 (Self-bounding variance inequality (Maurer & Pontil 2009 Theorem 10)). Let XI,..., Xr be independent and identicully distributed random variables with finile variance, that is, Var(X1) < oc. Assume that Xx [0, (0,M), for every with M > O, and let
2
8 T Σ
X?
1 T
Σ
x
Then, for any E >> 0, we have
P ((ST-- v Var(X1)
25 S
exp
Ts²
2M
Proof. Refer to the proof of Lemma 7 of (Panaganti & Kalathil 2022
58


Reviews:
[{"review_id": "5i4xxKRfld", "reviewer": "Reviewer_cwx1", "summary": "The paper tackles online distributionally robust Markov games (DRMGs) without a simulator or offline dataset and proposes f-MORNAVI, an optimistic-robust, model-based meta-algorithm for general f-divergence uncertainty sets (with concrete TV and KL instantiations). It proves (i) hardness results—linear regret with support shift and √K regret without shift but still scaling with the joint action size—and (ii) first regret bounds for online DRMGs in the TV/KL cases, plus corresponding sample-complexity bounds. Algorithmically, f-MORNAVI estimates a nominal kernel online, plans via robust Bellman operators augmented with UCB-style bonuses tailored to the uncertainty geometry, and computes an equilibrium (NE/CE/CCE) at each step.", "questions": "1. Clarification of the Equilibrium Definitions\nThe definition of robust coarse correlated equilibrium (CCE) in Section 2 appears identical to the Nash equilibrium condition. Could the authors clarify whether this was intentional, and if not, provide the correct formulation of the CCE obedience constraints? If the CCE definition is corrected, would this change any of the stated regret bounds or equilibrium existence claims? A clarification of whether the theoretical guarantees hold for all equilibrium notions (NE, CE, CCE) under the same assumptions would be very helpful.\n\n2. Existence of Robust NE and Practical Computability\nThe paper defines a robust NE as a product policy, but general-sum robust games may not guarantee existence. Are there known conditions under which the robust NE considered in this paper is guaranteed to exist (e.g., convex–concave payoff structures or zero-sum cases)? How is the equilibrium computed in practice within the MORNAVI framework—via an exact solver or approximate methods? Including an explanation of computational feasibility would make the algorithmic contribution clearer.\n\n3. Clarification of the Failure-State Assumption\nThe regret bound under TV divergence relies on the failure-state assumption, which seems to restrict uncertainty to transitions that are still reachable through exploration. Could the authors formalize this assumption more explicitly and discuss its implications? What happens if this assumption is violated—does the regret bound degrade gracefully, or does the algorithm fail entirely? A sensitivity analysis or a theoretical relaxation would strengthen the argument.\n\n4. Scope of the Rectangular Uncertainty Set\nThe analysis assumes rectangular (decoupled) uncertainty sets across states and agents, which simplifies the dynamic programming recursion but limits expressiveness. Could the authors comment on whether their approach could handle non-rectangular (coupled) uncertainty sets, perhaps through approximate decomposition? Would any part of the regret proof break down under correlated uncertainties across agents?\n\n5. Regret Bound Tightness and Scaling with Joint Actions\nThe regret bounds in Theorems 2 and 3 scale with the product of action space sizes (∏Ai), which makes them impractical for even moderate numbers of agents. Could the authors clarify whether this dependence is inherent or a proof artifact? Are there potential structural assumptions (e.g., mean-field or factored game structures) that could reduce this dependence while maintaining robustness?\n\n6. Comparisons with Concurrent Work\nThe authors position MORNAVI as the first to provide online DRMG guarantees, but RONAVI (Farhat et al., 2025) and related works appear to address similar settings. Could the authors provide a more explicit comparison in terms of assumptions (e.g., oracle access, divergence type), theoretical guarantees, and computational complexity? If RONAVI uses similar optimism–robustness design principles, what distinguishes MORNAVI’s theoretical contribution?\n\n7. Confidence Interval Construction and Proof Transparency\nThe proof of optimism for the robust Q-value relies on confidence intervals that bound the uncertainty-adjusted Bellman operator. Could the authors sketch the key steps or inequalities (e.g., dual form of σ𝒫[V]) in the main text to make the logic more transparent? How do the bonus terms differ in structure between the TV and KL cases, and what intuition explains these differences?\n\n8. Empirical or Illustrative Demonstration\nEven a small-scale experiment could provide insight into how the algorithm performs under model mismatch. Could the authors include or discuss results on a simple two-player coordination or adversarial environment? Observing whether the empirical regret trend aligns with the theoretical rate would help substantiate the practical value of the theoretical development.\n\n9. Theoretical Open Questions\nThe paper concludes by raising the question of whether online DRMG algorithms can overcome the curse of multi-agency. Could the authors elaborate on potential directions—such as hierarchical decomposition, correlated equilibrium relaxation, or partial coordination—that might reduce this scaling? Are there theoretical obstacles (e.g., impossibility results) suggesting that sublinear regret without ∏Ai dependence might be unattainable?\n\n10. Expository and Structural Improvements\nThere are a few presentation issues that would benefit from revision:\n- Duplicate numbering of Theorem 1 for hardness and upper-bound results.\n- Undefined symbols (e.g., σ𝒫[V], ρmin, Pmin) at their first appearance.\n- Several long equations could use short textual interpretation lines to help readers follow the logic.\nAddressing these would significantly improve readability and make the theoretical arguments easier to follow.\n\nSummary\nThe main clarifications that could substantially change my evaluation are:\n- Correcting and explaining the CCE/CE definitions and their impact on results.\n- Providing clearer justification for key assumptions (failure states, rectangularity).\n- Offering an explicit comparison with concurrent works.\n- Demonstrating even minimal empirical validation or illustrating scalability considerations.\nThese improvements would make the contribution more transparent, the assumptions more credible, and the theoretical results easier to interpret and verify.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality\n\nThe paper addresses a relatively unexplored problem: online distributionally robust Markov games (DRMGs) without access to simulators or offline data. While the formulation itself extends concepts familiar from single-agent robust RL and generative/offline DRMG studies, applying them to the online multi-agent regime is a natural but nontrivial step. The proposed MORNAVI framework—integrating optimism for exploration with robustness against uncertainty—is conceptually consistent with prior work on optimistic robust RL, though its multi-agent adaptation and generalization to \n𝑓\nf-divergence sets give it modest originality. The contribution is incremental rather than groundbreaking but helps close an existing theoretical gap.\n\nQuality\n\nThe theoretical development is careful and technically competent. The paper provides hardness results, upper bounds, and sample-complexity analysis that align with known results in related literature. The regret guarantees for both Total Variation and KL uncertainty sets are plausible extensions of existing robust RL theory. However, the analysis follows established proof techniques (empirical Bernstein inequalities, Bellman contraction arguments, etc.) rather than introducing fundamentally new analytical tools. Some aspects—such as the correctness of the correlated equilibrium definitions and the reliance on specific assumptions like rectangularity and failure states—should be clarified or corrected to fully validate the results. Overall, the quality is solid but not exceptional.\n\nClarity\n\nThe paper’s structure is standard and logical, with a clear flow from problem motivation to algorithm design and theoretical results. Nevertheless, the writing is mathematically dense, and several sections would benefit from higher-level intuition to guide readers through technical derivations. Certain notational inconsistencies (e.g., repeated theorem numbering, unclear equilibrium notation) reduce readability. While the main ideas can be followed by experts in the field, the exposition is unlikely to be easily accessible to a broader ICLR audience without additional clarifications or illustrative examples.\n\nSignificance\n\nThe significance of the paper lies primarily in its problem setting rather than in the methodological innovation. Establishing regret bounds for online DRMGs is useful for the theory of robust multi-agent learning, but practical impact remains limited given the heavy dependence on joint action space size and the lack of empirical validation. The work reinforces the difficulty of scaling robustness in multi-agent systems but does not yet provide clear strategies to mitigate these challenges. The theoretical results are incremental but may serve as a foundation for future improvements in scalability or algorithmic design.", "weaknesses": "1. Limited Conceptual Novelty Beyond Extension\nWhile the paper presents a rigorous treatment of online Distributionally Robust Markov Games (DRMGs), its conceptual novelty is limited. The proposed MORNAVI algorithm largely repackages existing principles—namely optimism in exploration and robust Bellman operators—previously developed in single-agent robust RL (e.g., Wang & Zou, NeurIPS 2021; Dong et al., ICML 2022; Panaganti & Kalathil, ICML 2022). Extending these to the multi-agent setting is a logical next step but not a fundamentally new paradigm. The paper would benefit from a clearer articulation of what new technical difficulties arise in the multi-agent online case (beyond joint-action explosion) and how MORNAVI specifically overcomes them.\n\n2. Overstated Claims of Firstness and Theoretical Gap\nThe paper repeatedly claims to be the first to address online DRMGs with provable guarantees, yet concurrent and closely related works—such as RONAVI (Farhat et al., 2025, arXiv)—already study similar formulations with optimism–robustness integration and provide comparable regret bounds. Moreover, previous generative or oracle-based DRMG works (Shi et al., 2024; Ma et al., 2023) have already laid much of the theoretical groundwork. The authors should moderate their 'first provable guarantee' claim and explicitly position their contribution in relation to these concurrent developments.\n\n3. Incomplete or Inaccurate Definitions\nThere are important definitional inaccuracies that need correction before the theory can be considered reliable:\n- The robust coarse correlated equilibrium (CCE) definition in Section 2 is identical to the robust Nash equilibrium definition, which is incorrect.\n- The paper assumes existence of robust NE without proof. For general-sum DRMGs, NE existence is nontrivial; only CE/CCE are guaranteed.\nCorrecting these definitions and clarifying the associated assumptions would strengthen the theoretical soundness and interpretability of the results.\n\n4. Dependence on Restrictive Assumptions\nSeveral assumptions used to make the analysis tractable are strong and may limit practical relevance:\n- The rectangular uncertainty set assumption eliminates coupling across states and agents, simplifying proofs but overlooking realistic uncertainty.\n- The failure-states assumption for TV uncertainty ensures that unseen transitions are learnable, which may not hold in online exploration.\n- The algorithm presupposes centralized model updates and full observability.\nA section explicitly acknowledging these assumptions’ implications—and discussing potential relaxation strategies—would improve credibility.\n\n5. Lack of Empirical or Illustrative Validation\nAlthough the paper is theoretical, it would benefit from a minimal empirical illustration or simulation. A simple 2-player gridworld or coordination game with environmental noise could demonstrate how MORNAVI behaves in practice, whether the derived regret bounds are observable, and how robustness manifests under distribution shifts.\n\n6. Unresolved Scalability Challenge\nWhile the authors discuss the curse of multi-agency (joint action dependence), the paper stops short of offering even partial mitigation strategies. Theoretical exploration of structured policies (mean-field approximations, factored models, or correlated policies) could point toward reducing the exponential dependence on ∏Ai.\n\n7. Exposition and Structural Issues\nThe exposition can be improved in several ways:\n- Duplicate theorem numbering causes confusion.\n- Several notations (e.g., σ_𝒫[V], ρ_min, P_min) are undefined when first introduced.\n- The confidence interval construction is only in the appendix and should be summarized in the main text.\nClarifying these would improve readability and allow reviewers to verify correctness more easily.\n\nSummary of Actionable Suggestions\n1. Correct the CCE/CE definitions and restate all regret results accordingly.\n2. Clearly differentiate the paper from concurrent work like RONAVI and moderate novelty claims.\n3. Discuss the impact and realism of rectangular and failure-state assumptions.\n4. Include a small synthetic experiment to illustrate algorithm behavior.\n5. Explore scalability strategies to reduce dependence on joint action size.\n6. Fix theorem numbering, ensure consistent notation, and summarize key proof steps in the main text.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5KmtQfk4uF", "reviewer": "Reviewer_axWW", "summary": "This paper introduces f-MORNAVI, a model-based online algorithm for distributionally robust Markov games (DRMGs). The method estimates the dynamics from interaction with the environment and performs planning under uncertainty sets defined by f-divergences. It incorporates an equilibrium solver and provides regret bounds for online DRMGs, along with lower bounds that highlight inherent hardness.", "questions": "see the weaknesses section", "limitations": "", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "+ The theoretical development is clear, with high-probability regret bounds for TV and KL uncertainty sets and sample-complexity corollaries to equilibrium under the NE, CE, and CCE.\n\n+ The algorithmic design well-designed and motivated. It separates model estimation, robust optimistic planning with divergence-aware bonuses, and an equilibrium, and the mathematical treatment of support shift is interesting and well-written.", "weaknesses": "-- The paper lacks empirical validation. Although the theoretical results looks sound, there is a lack of experimental evidence that the proposed online method outperforms prior approaches or that the constants or overheads are practical. \n\n-- The practical comparison to generative or offline baselines and to out-of-distribution scenarios is unclear. It would help to quantify how the robust online procedure fares against strong non-robust or offline/generative methods on OOD tasks.\n\n-- While the theory derives sample-complexity corollaries for reaching approximate equilibrium, the lack of experiments makes it hard to assess the real-world gap between these bounds.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "udfwFz6E82", "reviewer": "Reviewer_cbht", "summary": "This paper tackles online learning in Distributionally Robust Markov Games (DRMGs) and proposes f-MORNAVI—a model-based algorithm that learns empirical transition models, constructs optimistic and pessimistic value estimates under f-divergence uncertainty, and computes equilibria (Nash/CCE/CE) at each step. The authors prove hardness results, showing that support-shift uncertainty (e.g., TV sets) yields linear regret. They also derive upper bounds for total variation and KL uncertainty, establishing near-matching sample-efficient guarantees. The work provides the first theoretical framework for online DRMGs with rigorous proofs and detailed analysis.", "questions": "- Lack of empirical validation despite practical motivation: The paper is motivated by bridging the sim-to-real gap in MARL, yet includes no experiments or case studies. This omission significantly weakens the claim that the approach improves practical robustness or connects theory and real-world performance. Would you be able to empirically show your proposed method compared with previous work in several simulation benchmarks?", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper supplies both lower bounds (separations) and matching upper bounds (for TV and KL) together. The proof structure is standard but carefully adapted to the robust multi-agent setting. \n- The paper identifies and formalizes the online DRMG problem (vs. prior offline/generative-model work) and isolates two distinct hardness phenomena (support shift and curse-of-multi-agency).", "weaknesses": "- All upper bounds and the lower bounds include the product of agent action counts. This is a severe scalability concern (exponential in number of agents if each has many actions). The paper acknowledges this as an open question but does not give practical guidance or alleviate it. This limits real-world applicability.\n- The algorithm requires solving an equilibrium (Nash/CE/CCE) in the stagewise matrix game for each state and timestep. In practice large action space and many states make these subroutines expensive. The paper needs to discuss practical computational approaches and complexity per episode.\n- The KL regret/sample complexity contains an $exp(O(H^2))$ term. For long horizons this is prohibitive; more discussion of whether this dependence is inherent (and how it scales in practice) is needed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8SYkGimvMf", "reviewer": "Reviewer_bkNi", "summary": "The paper propose a systematic and principled approach for online learning in distributionally robust Markov Games with environment uncertainty. This is done by first revealing the hardness in online DRMGs,  then proposing an online robust MARL algorithm, Multiplayer Optimistic Robust Nash Value Iteration (MORNAVI), which offers the first provable robust guarantee in the setting. The theoretical analysis demonstrates MORNAVI achieves low regret, finds the optimal robust policy and achieves high sample complexity.", "questions": "See weakness.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall the paper is well-written, a little hard to understand due to the nature of a theoretical paper but clear enough to understand given the context. The theories given are rigorious and the threat model, algorithm and proofs seems correct, but I didn't check all the proofs.\n\n1. The hardness of online DRMGs provides a clear motivation of the problem, and the contructed examples gives an intuitive thought experiment for future researchers to design their algorithms.\n\n2. The derivations on sample complexity provides a rigorious theoretical foundation for establishing the regret of existing algorithms, and shows the result achieves complexity comparable with existing works, despite operating in online settings instead of easier generative and offline settings. The complexity bound is quite tight.", "weaknesses": "1. The main weakness I belive is that current online MARL parameterized by neural networks still do not have high enough sample efficiency to support this work that learns purely online, without any offline datasets available. However, accepting this paper would greatly benefit future research on this topic.\n\n2. The paper is purely theoretical and might be designed for tabular case, instead of existing MARL using function approximations. While this is beneficial for theoretical analysis, it remains unknown how to adapt this algorithm to modern environments, such as MPE, SMAC and Multi-Agent Mujoco. This is clearly reflected in stage 1, Nominal Transition Estimation and stage 2, EQUILIBRIUM subroutine. Estimating the distribution of future states can be inaccurate in modern environments with large state space using simple empirical average, and computing the equilibrium such as CE or CCE can be hard in tasks such as SMAC, or continuous control.\n\n3. What is the algorithmic differencce between MORNAVI and existing distributional robust approach? I am not very familiar with distributionally robust MARL literature, so I assume the main difference lies in Eqn. 5 and 6, since other parts of the algorithm is not too different from existing robust MARL approach.\n\nTo solve these problems, can you provide suggestions on empirical algorithms that leverage the advantage of MORNAVI, but use  function approximations? this would greatly strengthen this paper. However, I give a rating of 6 based on the current version.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)