Breaking the Curse of Multiagency in Robust Multi-Agent Reinforcement Learning
Authors: Laixi Shi
Jingchu Gai
Eric Mazumdar
Yuejie Chi
Adam Wierman
Venue: ICML 2025 poster (2025)
Keywords: multi-agent reinforcement learning
robust Markov games
game theory
distribution shift
behavioral economics
Primary area: reinforcement_learning->multiagent
TL;DR: We propose a new class of robust Markov games and propose the first provable algorithm to break the curse of multiagency of the sample complexity for solving robust Markov games, regardless of the uncertainty set formulation.

Abstract: Standard multi-agent reinforcement learning (MARL) algorithms are vulnerable to sim-to-real gaps. To address this, distributionally robust Markov games (RMGs) have been proposed to enhance robustness in MARL by optimizing the worst-case performance when game dynamics shift within a prescribed uncertainty set. RMGs remains under-explored, from reasonable problem formulation to the development of sample-efficient algorithms. Two notorious and open challenges are the formulation of the uncertainty set and whether the corresponding RMGs can overcome the curse of multiagency,  where the sample complexity scales exponentially with the number of agents. In this work, we propose a natural class of RMGs inspired by behavioral economics, where each agent's uncertainty set is shaped by both the environment and the integrated behavior of other agents. We first establish the well-posedness of this class of RMGs by proving the existence of game-theoretic solutions such as robust Nash equilibria and coarse correlated equilibria (CCE). Assuming access to a generative model, we then introduce a sample-efficient algorithm for learning the CCE whose sample complexity scales polynomially with all relevant parameters. To the best of our knowledge, this is the first algorithm to break the curse of multiagency for RMGs, regardless of the uncertainty set formulation.

Breaking the Curse of Multiagency in Robust Multi-Agent Reinforcement Learning
Laixi Shi
Jingchu Gai *2
Eric Mazumdar
Yuejie Chi Adam Wierman
Abstract
1 Introduction
A flurry of problems naturally involve decision-making among multiple players, whether human, artificial intel- ligence, or both, with strategic objectives. Multi-agent reinforcement learning (MARL) serves as a powerful frame- work to address these challenges, demonstrating potential in various applications such as social dilemmas (Leibo et al., 2017; Baker, 2020; Zhang et al., 2024), autonomous driving (Lillicrap et al., 2015), robotics (Kober al., 2013; Rusu et al., 2017), and games (Mnih al., 2015; Vinyals et al., 2019). Despite the recent success of standard MARL, its transition from prototypes to reliable production is hindered by robustness concerns due to the complexity and variability of both the real-world environment and human behaviors. Specifically, environmental uncertainty can arise from sim- to-real gaps (Tobin al., 2017), unexpected disturbance (Pinto et al., 2017), system noise, and adversarial attacks (Mahmood al., 2018); agents' behaviors are subject to unknown bounded rationality and variability (Tversky & Kahneman, 1974). The solution learned at training can fail catastrophically when faced with slightly shifted MARL problem during deployment, resulting in a significant drop in overall outcomes and each agent's individual payoff (Balaji et al., 2019; Zhang et al., 2020a; Zeng al., 2022: Yeh et al., 2021; Shi et al., 2024b; Slumbers et al., 2023).
Standard multi-agent reinforcement learning (MARL) algorithms are vulnerable sim-to-real gaps. To address this, distributionally robust Markov games (RMGs) have been proposed to enhance robustness in MARL by optimizing the worst-case performance when game dynamics shift within prescribed uncertainty set. RMGs remains under-explored, from reasonable prob- lem formulation to the development of sample- efficient algorithms. Two notorious and open chal- lenges are the formulation of the uncertainty set and whether the corresponding RMGs can over- come the curse of multiagency, where the sample complexity scales exponentially with the number of agents. In this work, we propose a natural class of RMGs inspired by behavioral economics, where each agent's 's uncertainty set is shaped by both the environment and the integrated behav- ior of other agents. We first establish the well- posedness of this class of RMGs by proving the existence of game-theoretic solutions such as ro- bust Nash equilibria and coarse correlated equilib- ria (CCE). Assuming access to generative model, we then introduce sample-efficient algorithm for learning the CCE whose sample complexity scales polynomially with all relevant parameters. To the best of our knowledge, this is the first algo- rithm to break the curse of multiagency for RMGs, regardless of the uncertainty set formulation.
To address robustness challenges, a promising and flexi- ble framework is (distributionallyy) robust Markov games (RMGs) (Littman, 1994; Shapley, 1953). It is a robust coun- terpart to the common playground of standard MARL prob- lems Markov games (MGs) (Zhang al., 2020c; Kardey et al., 2011), 1). In standard MGs, agents consider (competi- tive) personal objectives and simultaneously interact with each other within shared unknown environment. The goal is to learn some rationally optimal solution concepts called equilibria, which are joint strategies/policies of agents that all of them stick with rationally with other agents fixed; for instance, Nash equilibria (NE) (Nash, 1951; Shapley, 1953), correlated equilibria (CE), and coarse correlated equi- libria (CCE) (Aumann, 1987; Moulin & Vial, 1978). To promote robustness, RMGs differ from standard MGs by defining each agent's payoff (objective) as its worst-case performance when the dynamics of the game shift within a
"qqual contribution 'Department of Electrical and Computer Engineering, Johns Hopkins University, MD, USA Machine Learning Department, Carnegie Mellon University. PA. USA 'Department of Computing Mathematical Sciences, California Institute of Technology, CA, USA 'Department of Statistics and Data Science, Yale University, CT, USA. Correspondence to: Laixi Shi <chilaiii @ gmail.com>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Breaking the Curse of Multiagency in Robust MARL
prescribed uncertainty set centered around a nominal envi- ronment.
ple complexity no more than
H M A
1.1 Open challenges of robust MARL
Construction of realistic uncertainty sets. The family of RMGs is rich class of problems because of the flexi- bility in constructing the uncertainty sets to capture differ- ent uncertainty considerations. The uncertainty sets preva- lent in current approaches are constructed under the (s, a)- rectangularity condition, yielding each agent's objective as the expectation over the independent risk-aware outcome on each joint action of other agents' strategies. While obser- vations from behavioral economics (Friedman & Mauers- berger, 2022; Sandomirskiy et al., 2024; Goeree et al., 2005; Mazumdar et al., 2024) reveal that, to handle other players' uncertainty, people often use a risk-aware metric outside of the expected outcome of other players' joint policy, rather than flipping the expectation and the risk metric as that of (s, rectangullartt condition. To account for realistic human pacision-making
up to logarithmic factors, which depends only on the sum of individual actions, rather than the number of joint actions.
The persistent curse of multiagency robust MARL. The development of provable sample-efficient algo- rithms for RMGs is largely underexplored, with only a few recent studies (Zhang et al., 2020c; Kardeş et al., 2011; Ma et al., 2023; Blanchet et al., 2023; Shi et al., 2024b). Focusing on a class of RMGs with uncertainty sets satisfying the (s, a) rretanguularit condition, ex- isting works all suffer from the curse of multiagency, significantly limiting their scalability. For example, us- ing the total variation (TV) distance the divergence function, Shi et al. (2024b) relying non-adaptive sampling, finds an E-approximate robust CCE with a sample complexity no more than
are motivated to develop new classes of RMGs that foster robust solutions for practical MARL problems.
H - A; min {H, Ô
H, minigign o, })
(2)
up to logarithmic factors, where o; E [0, is the uncertainty level for the i-th agent. As result, the sample size requirement becomes prohibitive when the number of agents is large. Consequently, there is a significant desire to explore paths that could break through the curse of multiagency in RMGs, which is much more involved than its standard counterpart due to complicated non-linearity introduced by planning for worst-case performances.
The curse of multiagency. Sample efficiency is a crucial challenge for solving MARL due to the limited availability of data relative to the high dimensionality of the problem. In MARL, agents strive learn through interactions with an unknown environment (Silver et al., 2016; Vinyals al., 2019; Achiam et al., 2023; Yang et al., 2025) that is of- ten extremely large-scale, while data acquisition can be prohibitively limited by high costs and stakes. As such, a notable scalability challenge is the the curse of multiagency the sample complexity requirement scales exponentially with the number of agents (induced by the exponentially growing size of the joint action space). This issue has been recognized and studied in extensive MARL problems (Song et al., 2021; Rubinstein, 2017). but remains unresolved for robust MARI.. We concentrate on finite-horizon multi- player general-sum Markov games, with a widely-used data collection mechanism - generative model (Kearns& & Singh, 1999), where the number of agents is n, the episode length H, the size of the state space is S. and the size of the i-th agent's 's action space is A,, for S i < n.
Given these two challenges of uncertainty set construction and the curse of multiagency, it raises an open question:
Can we design RMGs with realistic uncertainty sets that come with sample complexity guarantees breaking the curse of multiagency?
1.2 Contributions
Inspired by behavioral economics, we propose new class of RMGs with a fictitious uncertainty set that explicitly models environmental uncertainties from the perspective of realistic human players, making it suitable for complex real- world scenarios. We begin by verifying the game-theoretie properties of the proposed class of RMGs to ensure the ex- istence of robust variants of well-known standard equilibria notions, robust NE and robust CCE. Next, due to the gen- eral intractability of learning NE, we focus on designing algorithms that can provably overcome the curse of multia- gency in learning an approximate robust CCE, referring to
Breaking the curse of multiagency in standard MARL. A line of pioneering work (Jin et al., 2021; Bai & Jin, 2020; Song et al., 2021; Li et al., 2023) has recently in- troduced new suite of algorithms using adaptive sam- pling that provably break the curse of multiagency in standard MGs. In particular, to find an e-approximate CCE, Li al. (2023) requires a minimax-optimal sam-
2

---

Breaking the Curse of Multiagency in Robust MARL
Algorithm
Uncertainty set
Equilibria
Sample complexity
РºMPO
(8, a) -rectangularity
robust NE
8 (TT== Ai) H²/E²
(Blanchet et al., 2024)
DR-NVI (Shi et al., 2024b)
SH A min H, minreten
(s, a) rectangularity
robust NE/CE/CCE
Robust-Q-FTRL (this work)
fictitious
S# Eisisn Ai min H, minisisn
robust CCE
(8, 0.) -rectanguulaitty
Table We show all the existing sample complexity results within the general context of robust Markov games (RMGs) to put our work into perspective, on finding an e-approximate equilibrium in finite-horizon multi-agent general-sum robust MG, omitting logarithmic factors. Our result the only algorithm that breaks the curse of multiagency regardless of the RMG formulations.
a joint policy where no agent can improve their benefit by more than E through rational deviations.. Specifically, for sampling mechanisms to explore the unknown environment, we assume access a generative model that can only draw samples from the nominal environment (Shi et al., 2024b). The main contributions are summarized as follows.
our knowledge, this is the first algorithm to break the curse of multiagency in sample complexity of RMGs regardless of the uncertainty set definition, which can provably find an e-approximate robust CCE using a sample size that is polynomial all salient parameters. Table provides detailed summary of all existing sample complexity results in robust MARL', where our results show significantly data efficiency with linear dependency on the size of each agent's 's action space, which absent from prior works (Blanchet et al., 2024; Shi et al., 2024b). To achieve this, we utilize adaptive sampling and online adversarial learning tools, coupled by a tailored design and amalysis for robust MARL due to the nonlinearity of the robust value function, which contrasts with the linear payoff functions in standard MARL with respect to the transition kernel.
We introduce a new class of robust Markov games us- ing fictitious uncertainty sets with others-integrated (s, rertreaatnyl condition (see Section 2.2 for de- tails), which is not only realistic viewpoint observed from behavioral economics, but also natural adapta- tion from robust single-agent RL to robust MARL. The uncertainty set for each agent i can be decomposed into independent subsets over each state and its own ac- tion tuple (s, az), where each subset is a "ball" around the expected nominal transition determined by other agents' policies and the nominal transition kernel, distance function p. and the radius/uncertainty level d; We verify several essential facts of this class of RMGs:: the existence of the desired equilibrium robust NE and robust CCE for this new class of RMGs using game-theoretical tools such as fixed-point theorem; the existence of best-response policies and robust Bellman equations.
Notation. In this paper, we denote [T] == 21, for any positive integer T > 0. We define A(S) as the simplex over a set S. For any policy π and function Q(+) defined over a domain B, the variance of Q under a is given by Var=(Q) = Eaes (a))Q((a) [Q] We define = [r[s, a)I(s.))ESxA E SA as any vec- tor that represents values for each state-action pair, and x = [a(ss, (r(s,,4)lee..)es d))cc.....E E RSA, as any vector repre- senting agent-wise state-action values. Similarly, we de- note x = [=(s)]aes as any vector representing values for each state. For X' = (S, (Ar H, (as)ie]m): / H), let f(x) = (g)()) denote that there exists a universal con- stant C1 such that f S Cig. Furthermore, the notation o()) is defined similarly to O(-) but hides logarithmic fac- tors.
We consider the total variation (TV) distance the distance metric for uncertainty sets due to its popu- larity in both theory (Panaganti & Kalathil, 2022; Shi et al., 2023; Blanchet et al., 2023; Shi et al., 2024b) and practice (Pan et al., 2023; Lee et al., 2021; Szita et al., 2003). Focusing on the proposed RMGs with fictitious uncertainty sets, we design Robust- Q-FRLL that can provably find e-approximate robust CCE with high probability, as long as the sample size exceeds
δ SH -i= A min { [1, mini sign 0.
1
(3)
'Note that, since we focus on new class of RMGs, the sample complexity results in this work cannot be directly compared to those in prior studies. However, we provide summary in Table I of existing sample complexity results for general RMGs, regardless of the uncertainty set formulation, for reference.
up to logarithmic factors, where o, E (0, is the uncertainty level for the i-th agent. To the best of
3

---

Breaking the Curse of Multiagency in Robust MARL
2 Preliminaries
for all (h, 8,) E [H] S x A,
In this section, we begin with some background on multi- agent general-sum standard Markov games (MGs) in finite- horizon settings, followed by a general framework of robust variant of standard MGs distributionally robust Markov games.
H
V. (s) =0x
Fii ( (t, ar) | ssh =3
H
Q (s, (s,a)= = :B)
> t=h
Ta,e ai) 1 8b = 8, a/. = a
(4)
2.1 Standard Markov games
In this context, the expectation is calculated over the tra- jectory {(s,, Jssss produced by following the joint policy π under the transition kernel P.
A finite-horizon multi-agent general-sum Markov game (MG) can be characterized by the tuple
Mg = (ASs P.r, H.
2.2 Distributionally robust Markov games
This setup features n agents each striving to maximize their individual long-term cumulative rewards within a shared environment. At each time step, all agents observe the same state over the state space S {1..... ,S} within the shared environment. For each agent i (i [m)), A; {I.... ] denotes its action space containing A, possible actions. The joint action space for all agents (resp. the subset excluding the i-th agent) is defined as A = A x x An, (resp. A = |1 Aj for any i E [n). We use the notation a E A (resp. a_; E A-;) to denote a joint action profile involving all agents (resp. all except the i-th agent). In addition, the probability transition kernel p (PhiiSHHH with each Pa= : S x A + A(S), describes the dynamics of the game: (x 8, a) is the probability of transitioning from state s E S to state s' E S at time step h when agents choose the joint action profile a E A. The reward function of the game is r = (rsaahsism.ssss with each riAh S x A + [o, 1] normalized to the unit interval. For any hi, s, a) E [n] x [H] x Sx A, (s, a) represents the immediate reward received by the i-th agent in state s when the joint action profile a is taken. Lastly, H >>000 0 represents the horizon length.
A general distributionally robust Markov game (RMG) is represented by the tuple
R.G - (8, (Attisisn (U, (P": (')sss I3.
Here, S, [AAiisssn F, H are defined in the same manner as those in standard MGs (see Section 2.1). RMGs differ from standard MGs: for each agent i (1 < i S n), the transition kernel is not fixed but can vary within its own prescribed uncertainty set u (P", determined by (possibly the cur- rent policy and) a nominal kernel p0 H x S x A + A(S) that represents a reference (such as the training environ- ment). The shape and the size of the uncertainty set (Pg.(P"))) ()) are further specified by a divergence function and the uncertainty levels {asheet)) serving as the "distance" metric and the radius respectively.
Various choices of the divergence function have been consid- ered in the literature of robust RL, including but not limited to f fddivergence (such as total variation, x² divergence, and Kullback-Leibler (KL) divergence) (Yang et al., 2022: Zhou et al., 2021; Shi & Chi, 2024; Lu et al., 2024; Wang et al., 2024) and Wasserstein distance (Xu et al., 2023). Adopting uncertainty sets with different structures leads to distinct RMGs, as they address distinct types of uncertainty and game-theoree theoretical solutions. This paper focuses variabil- ity in environmental dynamics (transition kernels), though uncertainty in agents' reward functions could also be con- sidered similarly but is omitted for brevity.
Markov policies and value functions. In this work, we concentrate on Markov policies that the action selection rule depends only on the current state s, independent from previ- ous trajectory. Namely, the i-th (i E [n]) agent chooses ac- tions according to ग. { S + A(A,) H. Here, Ti (a s)) represents the probability of selecting action a E A, in state at time step h. As such, the joint Markov policy of all agents can be denoted as π = (TI...., TT): x [A] + ((A), i.e., given any s E S and h E [M], the joint action profile a E A of all agents is chosen following the distribution Tx ()) (TI,A, T2,...., (-11)) E
Robust value functions and best-response policies. For any RMG, each agent seeks maximize its worst-case per- formance in the presence of other agents' behaviors despite perturbations in the environment dynamics, as long as the kernel transitions remain within its prescribed uncertainty set. Mathematically, given any joint policy л : SS x [H] + ((A), the worst-case performance of any agent: is char- acterized by the robust value function ViJ and the robust Q-function Q for all (i, h, 8, ai) E [m] x [H) x S x A..
A(4).
To continue, for any given joint policy and transition kernel P of a Mg, the i-th agent's long-term cumulative reward can be characterized by the value function V.
V (s) = 4.
inf
VT.P (s)
S + R (resp. Q-function Q : S A + R.) as below:
PE
4.
4

---

Breaking the Curse of Multiagency in Robust MARL
Qih (,, =
inf (PO
Q. (s, oz).
(5)
& Vial, 1978; Aumann, 1987) if it holds that for all (i,
[n]
S
Note that different from (4), here the Q-function for any i-th agent is defined only over its own action a; A, rather than the joint action A.
V CCE
(()
max N (((
a 4,1
x
(s).
(9)
This correlated policy xC can also be viewed as a distribu- tion & over the product policy space since each joint action a can be seen as a deterministic product policy. Careful readers may note that the definition (9) of CCE in standard MGs is in a different form from the one (8) in RMGs, as the latter does not include the expectation operator Ex with respect to the policy distribution ( over the value function. We emphasize that the definition with the expectation oper- ator outside of the value (or cost) function with respect to a distribution of product pure strategies in (8) is a natural for- mulation originating from game theory (Moulin et al., 2014; Moulin & Vial, 1978). In standard MARL and previous robust MARL studies, the definition in (9) is typically used because (9) and (8) are identical in those situations, as the expectation operator and the corresponding value functions are linear with respect to the joint policy, allowing them to be interchanged (Li et al., 2023; Shi et al., 2024b).
To continue, we denote T- as the policy for all agents except for the i-th agent. By optimizing the i-th agent's policy T.= : S x [H] + (AA) (independent from π-1), we define the maximum of the robust value function as
Y (s)
4.4
max S(
V inf #/ (A) PEU,
max
i.h
(6)
for all (i, h. E [n] x
x S. The policy that achieves the maximum of the robust value function for all (i, h, 8) E [n] x [M] x S is called a robust best-response policy.
[
Solution concepts for robust Markov games. In view of the conflicting objectives between agents, establishing equilibrium becomes the goal of solving RMGs. As such, we introduce two kinds of solution concepts robust NE and robust CCE - robust variants of standard NE and CCE (usually considered standard MGs) specified to the form of RMGss.
3 Robust Markov Games with Fictitious Uncertainty Sets
Given the definition of general RMGs, a natural question arises: what kinds of uncertainty sets should we consider to achieve the desired robustness in our solutions? To address this, we focus on class of RMGs characterized by a type of natural yet realistic uncertainty sets inspired from behavioral economics. More discussions of this class of games provided momentarily.
Robust NE. A product policy π Tı x x... TT
S x H + I A(A,) is said to be a robust NE if
V.,0i (s) = V. (s) v(s,)) E x [n]. (7) 1,1
Given the strategies of the other agents x _... when each agent wants to optimize its worst-case performance when the environment and other agents' policy stay within its own uncertainty set Ug (Po, TT, robust NE means that no player can benefit by unilaterally diverg- ing from its present strategy.
3.1 A novel uncertainty set definition in RMGs
We propose new class of uncertainty sets, named fictitious uncertainty sets, which count in the uncertainty induced by both the environment and other agents' behaviors in an integrated manner. Before introducing the uncertainty sets, we provide some auxiliary notations as below. We denote vector of any transition kernel P S x + A(S) or pa SSSAA A(8) respectively as: for all (s, a) SxA,
Robust CCE, distribution over the joint product pol- icy & = (5x (Er]e)]H] 5 x [H] + A(]Iig()) (AA))) is said to be robust CCE if it holds that for all (i. 8) E [m] S.
Emng [V. 2 E [V(T--"((s)] (8)
Ph.s. == P. s, s,a) R
Pu Pl P s, RIXS.
(10)
Considering all agents follow the policy drawn from the distribution ç, i.e., (s) ~ (s) for all (s, h) E S x [H), when the distribution of all agents but the i-th agent's policy is fixed as the marginal distribution of ç, robust CCE indicates that no agent can benefit from deviating from its current policy.
For any (possibly correlated) joint Markov policy (defined in Section 2.1) π S [M] + A(A), we define the ex- pected nominal transition kemel conditioned on the situa- tion that the i-th agent chooses some action a; E A, and other agents play according to the conditional policy (i.e., a TT (- az)) given E S and a, as below; for all (h, a,) E [ x x A
Note that, for standard MGs, CCE is defined as a possibly
correlated joint policy CCE, S (H] + A(A) (Moulin
Pd ;
F Ea-as s.a.) pp [Pb,
h,s.a,
5

---

Breaking the Curse of Multiagency in Robust MARL
Ta(a;, a-i 88) (t,b(as s) [PR.n.]]
the uncertainty sets with (s, -rrectangullrrt con- dition (Ma et al., 2023; Blanchet al., 2023; Shi et al., 2024b) studied in prior works. Hence, the proposed uncertainty set modeling is realistic and predictive of human decision-making behaviors from behavioral eco- nomics.
(11)
a. :EA:
Armed with the above definitions, now we are in a posi- tion to define the fictitious uncertainty sets, which satisfy a others-integrarte (s, recttecctngyyl condition.
Definition 3.1. For any joint policy ι .S x [H] + A(A), divergence function p: : (SS) x (SS) + IR and acces- sible uncertainty levels a; 2 0 for all i E [ni, the ficti- tious uncertainty sets (4g m kE(n) satisfy the others- integrated (s, a,) -eeetaaannyll condition: for all E [n] and (h, 8, 0z) E [H] x S Ai.
A natural adaptation from single-agent robust RL. When agents follow some joint policy π : 8 x [M] + (AA,, fixing other agents' policy T- from the per- spective of each individual agent i, RMGs with our pro- posed (s, as) reettaggggyy condition will degrade to a single-agent robust RL problem with the widely used (s, 0, (e.e)-rrettagularrtyy condition in the single-agent lit- erature (lyengar, 2005; Zhou et al., 2021). Namely, from any agent i's viewpoint, in a RMG, it deals with a "fictitious" player that can not only manipulate the environmental dynamics but also other players' policy
Ug,(PO, ,t) .)) 3 u (P i Ug (Ph.....) = {P E A(S): : p(P, Pi.zi S [ (12)
Phisias)) s.t.
where @ represents the Cartesian product.
In words, conditioned on a fixed joint policy æ. the uncer- tainty set TT) for each i-th agent can be decomposed into a Cartesian product of subsets over each state and agent- action pair (s, o,). Each uncertainty subset Ug: (ar, over (s, a,) is defined as a "ball" around a reference the expected nominal transition kernel Pi conditioned on both transition kernel and agents' joint policy x.
3.2 Properties of RMGs with fictitious uncertainty set
Throughout the paper, we focus on the class of R.MGs with the above proposed fictitious uncertainty sets, denoted as R.MGin and abbreviated as fictitious RMGs in the remain- ing of the paper. In this section, we present key facts about fictitious RMGss related to best-response policies, equilibria, and the corresponding one-step lookahead robust Bellman equations. The proof' can be found in the full version (Shi et al., 2024a).
Further discussions of fictitious uncertainty set. Here, we discuss the proposed fictitious uncertainty sets, focusing on their practical implications, properties, and relation to prior works. Prior works on RMGs typically focused on a type of uncertainty sets with (s, a) rectaanglllyr condition (Ma et al., 2023; Blanchet al., 2023; Shi al., 2024b). This class of uncertainty sets decouples the uncertainty into independent subsets for each state-joint action pair (s. a), accounting for the uncertainty induced by other agents sepa- rately and independently, mathematically defined as
First, we introduce the following lemma, which verifies the existence of a robust best-response policy that achieves the maximum robust value function (cf. (6)) in any R.M
Lemma 3.2. For any i E [n], given π-5 S x [H] + A(A.). there exists at least one policy मे : S x [H] +
(AA) for the i-th agent that can simultaneously attain
Vi V=*x*=_.0((s) (s) = V (=*"=,."*(s)) for all S and h [H]. We refer this policy as the robust best-response policy.
ug: (P") = -0' (Ph.e.a): where
Ug (Ph, = (Pr.s.a E A(S): p(Ph. Ph S so.).
Existence of robust NE and robust CCE. Fictitious RMGs can be viewed as hierarchical games with + nS E A, agents. This includes the original n agents and n additional sets of S ""= A, independent adversaries, each determining the worst-case transitions for one agent over state plus agent-wise-action pair. Considering the solution concepts robust NE and robust CCE intro- duced in Section 2.2, the following theorem verifies the existence of them for any fictitious RMGs using Kakutani's fixed-point theorem (Kakutani, 1941), focusing on robust NE firstly.
Realistic and predictive of human decisions in com- parisons to prior works. Observed from experimental data of behavioral economics, in many games consid- ering agents' randomness (Friedman & Mauersberger, 2022; Goeree et al., 2005; Sandomirskiy et al., 2024), people address other players' uncertainty in an inte- grated manner as a risk metric outside of their expected outcomes (e.g., Risk(E...er_..) IV... stead of in a separate manner as expectation of the risk metric over outcomes of each joint action (namely, Risk 3. (a;, ))). Here, the former one which is more realistic- corresponds to our ficti- tious uncertainty set, while the latter one corresponds
W (a., a.))))), in-
Theorem 3.3 (Existence of robust NE). For any R.G = (S, (Athsisn (4g: (PP..)))ss >)issn r, H} with an un- certainty set defined in Definition 3.1, there exists at least one robust NE.
E...Er_,
6

---

Breaking the Curse of Multiagency in Robust MARL
Analogous to standard Markov games, since {robust NE] C (robust CCE), Theorem 3.3 indicates the existence of ro- bust CCEs directly. The class of fictitious RMGs feature robust counterpart of the Bellman equation - robust Bell- man equation, which is detailed in the full version (Shi et al., 2024a).
- -
[VT [s)] } S.
(14)
Armed with a generative model of the nominal environ- ment, the goal becomes learning robust CCE using as few samples from the simulator as possible.
4.2 Algorithm design
4 Sample-Efiicient Learning: Algorithm and Theory
With the sampling mechanism over a generative model in hand, we propose an algorithm called Robust-Q-FTRL, to learn an e-robust CCE in a sample-efficient manner. The complete procedure is summarized in Algorithm 2. Robust- Q-FTRL draws inspiration from Q-FTRL developed in the standard MG literature (Li al., 2022), but empowers tai- lored designs for learning in fictitious RMGs to achieve a robust equilibrium and to tackle statistical challenges arising from agents' nonlinear worst-case objectives.
In this section, we focus on designing sample-efficient al- gorithms for solving fictitious RMGs when agents need to collect data by interacting with the unknown shared environ- ment in order to learn the equilibria. To proceed, we shall first specify the data collection mechanism and the diver- gence function for the uncertainty set. Then we propose sample-efficient algorithm Robust-Q-FTRL that leverages tailored adaptive sampling strategy to break the curse of multiagency for solving fictitious RMGs.
Constructing the empirical model via N-sample estima- tion. For each time step h, we denote Tř as the current learning policy of the i-th agent before the beginning of the k-th iteration for any k E [K]. And we denote the joint product policy as म = (mf ... Th,n). During each iter- ation k. for each agent E [m], we require to generate N independent samples from the generative model over each (s, az) S x Ar obtain empirical model, detailed in Algorithm 1. It includes empirical reward function represented by rêt E RRS and transition kernels denoted by P RSA,X Note that different from standard MGs, we need to generate N samples instead of sample per iter- ation to handle the additional statistical challenges induced by the non-linear objective of agents (N will be specified in Theorem 4.
4.1 Problem setting and goal
Recall that the uncertainty sets are constructed by specifying a divergence function / and the uncertainty level to control its shape and size. In this work, we focus on using the TV distance as the divergence function p for the uncertainty set, following Szita et al. (2003); Lee et al. (2021); Pan et al. (2023); Shi et al. (2023; 2024b), defined by
VP, E AS): PTv PTv (P,PP) = 2 |P P'Il- (13)
For convenience, throughout the paper, we abbreviate (.: = Ug, (.) when there is no ambiguity.
Estimating robust Q-function of the current policy n We denote Vi,A E R as the estimation of the i-th agent's robust value function at time step h. For any agent i, with the empirical reward function ri, empirical kernel P and the estimated robust value function V V4,b+1 at the next step in hand, the robust Q Q-function {9",, of current policy T. can be estimated as: for all (i, h, s,a,) E [na] x [H] x S A,,
Data collection mechanism: a generative model. We assume the agents interact with the environment through a generative model (simulator) (Kearns& & Singh, 1999), which is a widely used sampling mechanism in both single- agent RL and MARL (Zhang et al., 2020b; Li al., 2022). Specifically, at any time step h, we can collect an arbitrary number of independent samples from any state and joint action tuple (s, a)= E S x A, generated based on the true nominal transition kernel p0: sh.s. ~
C., (s, az) = (s, (8,0;) +
inf PEPP (Ahaa))
PV P4 (15)
i.ddd
P- (,,ssaa a) for
i i= 1,2.....
Unlike the linear function w.r.t. Pl in standard MGs, (15) lacks a closed form and introduces an additional inner op- timization problem. Solving (15) directly computation- ally challenging due to the need to optimize over an S- dimensional probability simplex, with complexity growing exponentially with the state space size S. Fortumately, by applying strong duality, we can solve (15) equivalently via its dual problem with tractable computation (lyengar, 2005):
Goal. Consider any fictitious RMGs R.Mg {S, (Ai (P::)))sssin H}. In practice, learning exact robust equilibria is computa- tionally challenging and may not be necessary, instead in this work, we focus on finding an approximate robust CCE (defined in (8)). Namely, distribution E == hhene [H] S + A(T]rem ((A.)) is said to be an e-robust CCE if
gaPccE(S) == max .ES.ISiSn
(Erng [Vi11 (VA (s)]
max (i, = =s) ac(min, (e), [.))

---

Breaking the Curse of Multiagency in Robust MARL
{ (Pth [Vanta] oi (a min o'
V [inti (6)) }. (16)
This is a widely used adaptive sampling and learning proce- dure for MARL problems.
where [V], denotes the clipped version of any vector V E R determined by some level a 2 O, namely,
After completing K iterations for time step h, we final- ize the robust value function estimation by setting it to its confidence upper bound, incorporating carefully de- signed optimistic bonus terms {Bi,} as: for all (i, h, s) [n] [H] S,
(la(s) = a, V(+),
is) > a,
(17)
otherwise.
log²( KS E d
The above two modules are key components of Robust-Q- FTRL, serving for constructing nonlinear robust objectives in the online learning process and ensuring the desired sta- tistical accuracy.
(.,((s) 1b1
KH
K
K ok A=1
(Varat (s,)),))) + H
(20)
Overall pipeline of Robust-Q-FTAL With these mod- ules in place, we introduce Robust-Q-FTRL, which fol- lows similar online learning procedure as Q-FTRL for standard MGs (Li et al., 2022). The complete procedure summarized in Algorithm/ 2. We denote Q E RSA, as the estimated robust Q-function of the equilibrium for the i-th agent at the k-th iteration of time step h. To begin with, Robust-Q- Q-FTRL initialize the robust value function, robust Q-function Vi,H+i(s)
where & denotes some absolute constant, ō (0, 1) is the high probability threshold, Finally, after the recursive learn- ing process ends for all time steps h = H, H - 1, ,I,, we output distribution of product policy & = {Ex he(H over all the policies {* = =x x... occurs during the process that defined (e_,)))e(HH))e((
v(h, k)) E [M] x [K]:
Cx(T)) = ar.
(21)
2º,,, (s, a;) = 0, and the policy ni, (a: s) 1/A, for all (i,s) E [n] S. Then subsequently from the final time step h H to h 1, for each step h, a K iterations online learning process will be executed. At each k-th iteration, given current policy = The as described above, an empirical model (fr",, Jiefm and {P,t, bxem)) is constructed by N N-sample estimation (ef. Al- gorithm 1). Then the robust Q-function {een of the current policy of is estimated by (16).
4.3 Theoretical guarantees
In this section, we provide the theoretical guarantees for the sample complexity of our proposed algorithm Robust-Q- FTRL, shown as below:
Theorem 4.1 (Upper bound). Using the TV un- certainty set defined in (13). Consider any (0,1) and any fictitious RMGs RMG (8, (Ahiiis (P))))))sss
8
with os (0, for all E [n]. For any S /min {H, minisisn Algorithm 2 can output an e-robust CCE E. i.e.
Now we are ready to specify the loss objective and proceed the online learning procedure. With the current one-step (1
update ). we update the Q-estimate as Q au a + auain Here, } is series of rescaled linear learning rates with some 2 24, for all & E [K]:
gapcce(E) S
with probability at least 8, as long as
Ca log K
a6
1 - 1 + Ca log K
C2 H2 N2
min minisisn
H K2
C 2
2
if0 < k < K az [1 as),
at
(18)
(22)
an
k n
Here C1 is some universal large enough constant. Namely, it is sufficient if the total number of samples acquired in the learning process obeys
Let the Q-estimate be the online learning loss objective at this moment, we apply the Reeoo-the-Reguulriiee----- strategy "Shalev-Shwartz 2012; Li et al., 2022) to update the corresponding policy as below:
Nal = HKNS Σ A
Igisn
d++ Thh exp (Tx+1 (i,
2 24
Ai min H, min
(as [s) Enr oxp (T++10 O f, (s,
with M++1 = log K asll"
k k= 1,2,....
Before we jump into more discussions of the above theorem, in addition, we introduce the information -ttmaatio--thoorttic minimax lower bound for this problem as well.
(19)
8

---

Breaking the Curse of Multiagency in Robust MARL
Lower bound for learning in fictitious RMGs. Consid- ering the instances of fictitious RMGs that the action space for all the agents except the i-th agent contains only a single action, i.e., A₁ = for all j # i. As such, all the agents j * i will take a fixed action and the game reduces to a single-agent robust MDP with (s, a) rrectangularrt condi- tion (Zhou et al., 2021). So the goal of finding the robust equilibrium - robust NE/CCE also degrades to finding the optimal policy of the i-th agent. Invoking the results from Shi et al. (2024b, Theorem 2), the lower bound for the class of fictitious RMGs is achieved directly: consider any tuple {S. {A. Jisisn foihin H) obeying o; E (0, 1 - c1] 1 being any small enough positive constant,
robust MGs with (s, recttnnggll uncertainty sets (Ma al., 2023; Blanchet et al., 2023; Shi et al., 2024b). However, the state-of-the-art sample complex- ity (SSIITE min {
(Shi et al., 2024b) still suffers from the curse of multiagency with an exponential dependency on the number of agents when all agents have equal action spaces, which uses nonadaptive sampling. Our work circumvents the curse of multiagency by the introduction of a new class of fictitious RMGs in- spired from behavioral economics, together with resorting to a tailored adaptive sampling and online learning proce- dure, providing fresh perspective to learning practical- meaningful RMGs.
H, minisisn
with 0 < 0 Σ 1
and > 16 log 2. Let
Technical insights. For sample complexity analysis, while previous works have addressed the curse of multi- agency in sequential games like standard Markov games (MGs) and Markov potential games, these methods are not directly applicable to RMGs. Prior approaches assume linear relationship between the value function and the tran- sition kemel, allowing statistical errors across K iterations to cancel out. However, in RMGs, the robust value function, due to its distributionally robust requirement, is highly non- linear and often lacks a closed form, making it impossible to linearly aggregate statistical errors. To tackle the nonlinear challenges in RMGs, we design variance-styl bonus term through non-trivial decomposition and control of auxiliary statistical errors caused by nonlinearity, resulting in a tight upper bound on regret during the online learning process.
# o S 2
(23)
otherwise
We can construct a set of fictitious RMGs M (R.MGi))een) such that for any dataset generated from the nominal environment with in total Nall inde- pendent samples over all state-action pairs, we have inf, max Raa EM
if [ |RRM (gaPccE(E) > E) 2 8
C2SH3 maxiejm) A; min H, min og
Nall S
(24)
Here, the infimum is taken over all estimators E. RRMM denotes the probability when the game is R.Mg for all RMG E M, and C2 some small enough constant.
5 Conclusion
Robustness in MARL presents greater challenges than in single-agent RL due to the strategic interactions between agents in a game-theoretic setting. This work proposes new class of RMGs with fictitious uncertainty sets that naturally extends from robust single-agent RL and addresses more realistic problems considering human features where each agent considers the uncertainty of others in an integrated manner. We then propose Robust-Q-FTRL, the first algorithm break the curse of multiagency in RMGs regardless of the uncertainty set definitions, with sample complexity scaling polynomially with all key parameters. This opens up new research directions in MARI, such as uncertainty set selection and construction.
Armed with both the upper bound (Theorem 4.1) and lower bound in (24), we are now ready to discuss the implications of our sample complexity results.
Breaking the curse of multiagency in the sample com- plexity for RMGs. Theorem 4.1 demonstrates that for any fictitious RMGs, Robust-Q-FTRL algorithm finds e-robust CCE when the total number of samples exceeds
SH Eisisn Ai min H,
δ
1
min sinn o.
To the best of our knowledge, Robust-Q-FTRL with the above sample complexity is the first algorithm for RMGs breaking the curse of multiagency, regardless of the types of uncertainty sets. Our sample complexity depends linearly on the sum of each agent's ' actions Σm= A, rather than their product I A:-making the algorithm highly scalable as the number of agents increases.
Acknowledgements
The work of Y. Chi is supported in part by the grants NSF CCF-2106778 and CNS-2148212, and by funds from federal agency and industry partners as specified in the Resilient & Intelligent NextG Systems (RINGS) program. The work of L. Shi is supported in part by the Resnick Institute and Computing, Data, and Society Postdoctoral Fellowship at
Comparisons with prior works. Prior works fo- cus on learning equilibria for a different kind of

---

Breaking the Curse of Multiagency in Robust MARL
California Institute of Technology. The work of E. Mazum- dar is supported in part from NSF-22401 10. The work of A.
Blanchet, J., Lu, M., Zhang, T., and Zhong, H. Double pessimism is provably efficient for distributionally robust offline reinforcement learning; Generic algorithm and robust partial coverage. Advances in Neural Information Processing Systems, 36, 2024.
Wierman is supported in part from the NSF through CNS- 2146814, CPS- CPS-2136197, CNS-2106403, NGSDI-2100648.
Impact Statement
Clavier, P., Shi, L., Le Pennec, E.,, Mazumdar, E., Wierman, A., and Geist, M. Near-optimal distributionally robust re- inforcement learning with general 1pp norms. Advances in Neural Information Processing Systems, 37:1750-1810, 2024.
This paper presents work whose goal advance the field of game theory and its interaction with artificial intelligence. There are many potential societal consequences of our work, such as serving as reference for public policy and economics, none which we feel must be specifically highlighted here.
Cui, Q. Zhang. K., and Du, S. Breaking the curse of multiagents in large state space: RI in markov games with independent linear function approximation. In The Thirty Sixth Annual Conference on Learning Theory, pp. 2651-2652. PMLR, 2023.
References
Achiam, J., Adler, S., Agarwal, S., Ahmad, L., Akkaya, I., Aleman, F. L., Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S., al. Gpt-4 technical report. arXiv preprint 3.Xiv:2303.087744. 2023.
Daskalakis, C.,, Golowich, N., and Zhang, K. The complex- ity of markov equilibrium in stochastic games. In The Thirty Sixth Annual Conference on Learning Theory, pp. PMLR, 2023.
Aumann, R. J. Correlated equilibrium as an expression of Bayesian rationality. Econometrica: Journal of the Econometric Society, pp. 1-18, 1987.
Duchi, J. and Namkoong. H. Learning models with uni- form performance via distributionally robust optimization. arXiv preprint wrxivv1811008773: 2018.
Badrinath, K. P. and Kalathil, D. Robust reinforcement learning using least squares policy iteration with provable performance guarantees. International Conference on Machine Learning, pp. 511-520. PMLR, 2021.
Friedman, E. and Mauersberger, F. Quantal response equilib- rium with symmetry: Representation and applications. In Proceedings of the 23rd ACM Conference on Economics and Computation, pp. 240-241, 2022.
Bai, Y. and Jin, C. Provable self-play algorithms for compet- itive reinforcement learning. In International Conference on Machine Learning, pp. 551-560. PMLR, 2020.
Gao, R. Finite-sample guarantees for wasserstein distri- butionally robust optimization: Breaking the curse of dimensionality. arXiv preprint arXiv:2009.04388 2020.
Baker, B. Emergent reciprocity and team formation from randomized uncertain social preferences. Advances in neural information processing systems, 13:199 2020.
Goeree, K., Holt, C. A., and Palfrey, T. R. Regular quantal response equilibrium. Experimental economics, 8:347- 367, 2005.
Balaji, B., Mallya, S., Genc, S., Gupta, S., Dirac, L., Khare, V., Roy, G., Sun, T., Tao, Y., Townsend, B., et al. Deep- racer: Educational autonomous racing platform for exper- imentation with sim2real reinforcement learning. arXiv preprint arXiv: /. 1.0162,, 2019.
Han, S., Su, S., He, S., Han, S., Yang, H., and Miao, F. What is the solution for state adversarial multi-agent re- inforcement learning? arXiv preprint arXiv:2212.02775. 2022.
Bertsimas, D., Gupta, V., and Kallus, N. Data-driven robust optimization. Mathematical Programming, (27(2):235- 292, 2018.
Iyengar, G. N. Robust dynamic programming. Mathematics of Operations Research, 30(2):257-280, 2005.
Jin, C., Liu, Q. Wang, Y., and Yu, T. V-learning-a sim- ple, efficient, decentralized algorithm for multiagent RL. arXiv preprint arXiv:2/ 14555, 2021.
Blanchet, J. and Murthy, K. Quantifying distributional model risk via optimal transport. Mathematics of Opera- tions Research, (4(2):565-600 2019.
Kakutani, S. A generalization of brouwer's fixed point theorem. 1941.
Blanchet, J., Lu, M., Zhang, T., and Zhong, H. Double pessimism is provably efficient for distributionally robust offline reinforcement learning: Generic algorithm and robust partial coverage. arXiv preprint arXiv:2305.0065 2023.
Kannan, S. S., Venkatesh, V. L., and Min, B.-C. Smart-LLM: Smart multi-agent robot task planning using large lan- guage models. arXiv preprint arXiv:2309. 10062, 2023.
10

---

Breaking the Curse of Multiagency in Robust MARL
Kardeş, E., Ordóñez, F., and Hall, R. W. Discounted robust stochastic games and application to queueing control. Operations research, 59(2)365-382, 2011.
Mahmood, A. R., Korenkevych, D., Vasan, G., Ma, W., and Bergstra, Benchmarking reinforcement learning algorithms on real-world robots. In Conference robot learning. pp. 561-591. PMLR, 2018.
Kearns, M. J. and Singh, S. P. Finite-sample convergence rates for Q-learning and indirect algorithms. In Advances in neural information processing systems, pp. 996-1002, 1999.
Mazumdar, E., Panaganti, K., and Shi, L. Tractable equilib- rium computation in markov games through risk aversion. arXiv preprini arXiv:2406. 14156, 2024.
Kober, J., Bagnell, J. A., and Peters, J. Reinforcement learning in robotics: A survey, The International Journal of Robotics Research, 32(11):1238- 1274, 2013.
McMahan, J., Artiglio, G., and Xie, Q. Roping in uncer- tainty: Robustness and regularization in markov games. arXiv preprint arXiv:2406. 08847, 2024.
Lee, J., Jeon, W., Lee, B., Pineau, J., and Kim, K.-E. Op- tidice: Offline policy optimization via stationary distribu- tion correction estimation. In International Conference on Machine Learning. pp. 6120-6133 PMLR, 2021.
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Ve- ness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., and Ostrovski, G. Human-level control through deep reinforcement learning. Nature, 518(7540):
529-533, 2015.
Leibo, J. Z., Zambaldi, V., Lanctot, M., Marecki, J., and Graepel, Multi-agent reinforcement learning in sequen- tial social dilemmas. arXiv preprint vrXiv:1702.0300 2017.
Moulin, H. and Vial, J.-P. Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory, 7(3):201-22) 22111 1978.
Li, G., Chi, Y., Wei, Y., and Chen, Y. Minimax-optimal multi-agent RL in Markov games with a generative model. Advances in Neural Information Processing Systems, 35: 15353-15367, 2022.
Moulin, H., Ray, I., and Gupta, S. Coarse correlated equilibria in abatement game. Technical report, Cardiff Economics Working Papers, 2014.
Li, G., Yan, Y., Chen, Y., and Fan, J. Minimax-optimal reward-and reward-agnostic agnostic exploration in reinforcement learning. arXiv preprint arXiv:2304.077777 2023.
Nash, Non-cooperative games. Annals of mathematics, pp. 28862955, 1951.
Nilim, A. and El Ghaoui, L. Robust control of Markov decision processes with uncertain transition matrices. Op- erations Research, 53(5):780-798. 2005.
Li, S., Wu, Y., Cui, X., Dong. H., Fang, F., and Russell, S. Robust multi-agent reinforcement learning via minimax deep deterministic policy gradient. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp.
Pan, Y., Chen, Y., and Lin, Adjustable robust reinforce- ment learning for online 3d bin packing. arXiv preprint arXiv:2310.04323, 2023.
4213 4220, 2019.
Lillicrap, T. P., Hunt, J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D. Continuous control with deep reinforcement learning. arXiv preprint arXiv:1509.088 0ww.1/599900991.222 2015.
Panaganti, K. and Kalathil, D. Sample complexity of ro- bust reinforcement learning with a generative model. In International Conference on Artificial Intelligence and Statistics, pp. 9582-9602. PMLR, 2022.
Littman, M. I.. Markov games framework for multi- agent reinforcement learning. In Machine learning pro- ceedings 1994, pp. 157-163. Elsevier, 1994.
Pinto, L., Davidson, J., Sukthankar, R., and Gupta, A. Robust adversarial reinforcement learning. In Interna- tional Conference on Machine Learning, pp. 2817-2826. PMLR, 2017.
Lu, M., Zhong, H., Zhang, T., and Blanchet, J. Distribu- tionally robust reinforcement learning with interactive data collection: Fundamental hardness and near-optimal algorithm. arXiv preprint arXiv:2404.035788 2024.
Rahimian, H. and Mehrotra, S. Distributionally robust op- timization: review. arXiv preprint 10t.:::99000666.. 2019.
Ma. S., Chen, Z., Zou. S., and Zhou, Y. Decentralized robust v-learning for solving markov games with model uncertainty. Journal of Machine Learning Research, 24 (371):1-40, 2023.
Rubinstein, A. Settling the complexity of computing ap- proximate two-player nash equilirria. ACM SIGecom Exchanges, 15(2):45 2017.

---

Breaking the Curse of Multiagency in Robust MARL
Rusu, A. A., Večerík, M., Rothörl, T., Heess, N., Pascanu, R., and Hadsell, R. Sim-to-real robot learning from pixels with progressive nets. In Conference robot learning, pp. 262-270. PMLR, 2017.
Tobin, J., Fong, R., Ray, A., Schneider, J., Zaremba, W., and Abbeel, P. Domain randomization for transferring deep neural networks from simulation to the real world. In 2017 IEEE/RSJ international conference on intelligent robots and systems (IROS), pp- 23-30. IEFE, 2017.
Sandomirskiy, F., Sung, P. H.,, Tamuz, O., and Wincelberg, B. Narrow framing and risk in games. 2024.
Tversky, A. and Kahneman, D. Judgment under uncertainty: Heuristics and biases: Biases in judgments reveal some heuristics of thinking under uncertainty. science, 185 (557):1124-11333 1974.
Shalev-Shwartz. S. Online learning and online convex opti- mization. Foundations and Trends@ in Machine Learning, 1(2):107-194, 2012.
Vial, D., Shakkottai, S., and Srikant, R. Robust multi-agent bandits over undirected graphs. Proceedings of the ACM Measurement and Analysis of Computing Systems, 6 (3):1-57, 2022.
Shapley, L. S. Stochastic games. Proceedings of the national academy of sciences, 39(10):095-1100, 1953.
Shi, I.. and Chi, Y. Distributionally robust model- offline reinforcement learning with near-optimal sample complexity. Journal of Machine Learning Research, 25 (200):1-91, 2024.
Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M.. Dudzik, A., Chung, J., Choi, D. H., Powell, R., Ewalds, T., Georgiev, P., et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575 (7782)350033) 354000355222000 2019.
Shi, L., Li, G., Wei, Y., Chen, Y., Geist, M., and Chi, Y. The curious price of distributional robustness reinforcement learning with generative model. In Proceedings of the 37th International Conference on Neural Information Processing Systems. pp. 79903-79917, 2023.
Wang. H., Shi, I.,, and Chi, Y. Sample complexity of offline distributionally robust linear Markov decision processes. arXiv preprint arXiv:2403. 12946, 2024.
Shi, L., Gai, J., Mazumdar, E., Chi, Y., and Wierman, A. Breaking the curse of multiagency in robust multi-agent reinforcement learning. arXiv preprint 209.0 2024a.
Wang. Y., Liu, Q.. Bai, Y., and Jin, C. Breaking the curse of multiagency: Provably efficient decentralized multi-agent RL with function approximation. In The Thirty Sixth Annual Conference on Learning Theory, pp. 2793-2848. PMLR, 2023.
Shi, I.., Mazumdar, E., Chi, Y., and Wierman, A. Sample- efficient robust multi-agent reinforcement learning in the face of environmental uncertainty. In Forty-firsl Interna- tional Conference on Machine Learning, 2024b.
Wu, Y., McMahan, J., Zhu, X., and Xie, Q. Data poisoning to fake nash equilibria for markov games. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 15979-15987, 2024.
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
Xu, Z., Panaganti, K., and Kalathil, D. Improved sample complexity bounds for distributionally robust reinforce- ment learning. arXiv preprint SXXi:23033007883 2023.
Yang, T., Dai, B., Xiao, L., and Chi, Y. Incentivize without bonus: Provably efficient model-based online multi-agent RL for markov games. arXiv preprint 2900025000007800 2025.
Slumbers, O., Mguni, D. H., Blumberg, S. B., Mcaleer, S. M., Yang, Y., and Wang, J. A game-theoretic frame- work for managing risk in multi-agent systems. In Inter- national Conference on Machine Learning, pp. 32059- 32087. PMLR, 2023.
Yang. W., Zhang, L., and Zhang. Z. Toward theoretical un- derstandings of robust Markov decision processes: Sam- ple complexity and asymptotics. The Annals of Statistics, 50(6))3223-322 2022.
Song, Z., Mei, S., and Bai, Y. When can we learn general- sum Markov games with large number of players sample-efficiently? arXiv preprint 10.04:2 2021.
Yeh, C., Meng, C.,, Wang, S., Driscoll, A., Rozi, E., Liu, P., Lee, J., Burke, M., Lobell, D. B., and Ermon, S. Sus- tainbench: Benchmarks for monitoring the sustainable development goals with machine learning. arXiv preprint a.X0v:2111.0724, 2021.
Szita, I., Takács, B., and Lorinez, A. e-mdps: Learning in varying environments. Journal of Machine Learning Research, 3(1), 2003.
12

---

Breaking the Curse of Multiagency in Robust MARL
Zeng, L.., Qiu, D., and Sun, M. Resilience enhancement of multi-agent reinforcement learning-basee demand re- sponse against adversarial attacks. Applied Energy, 324: 119688, 2022.
Zhang, H., Chen, H., Xiao, C., Li, B., Liu, M., Boning, D., and Hsieh, C.-J. Robust deep reinforcement learning against adversarial perturbations state observations. Advances in Neural Information Processing Systems, 33: 21024-21037, 2020a.
Zhang. H., Chen, H., Boning, D., and Hsieh, C.-J. Robust reinforcement learning state observations with Iearned optimal adversary. arXiv preprint PrXiv:2101.0845: 2021.
Zhang, K., Kakade, S., Basar, T., and Yang, L. Model- based multi-agent RL in zero-sum Markov games with near-optimal sample complexity. Advances in Neural Information Processing Systems, 33:1166-1178, 2020b.
Zhang. K., Sun, T., Tao, Gene, S., Mallya, S., and Basar, T. Robust agget reinforcement learning with model uncertainty. Advances in neural information processing systems, 33:1057 1-10583, 2020c.
Zhang. R., Shamma, J., and Li, N. Equilibrium selection for multi-agent reinforcement learning: A unified framework.
arXiv preprint arXiv:2406.0888 2024.
Zhou, and Liu, G. Robustness testing for multi-agent reinforcement learning: State perturbations on critical agents. arXiv preprint arXiv:2306.061.66 2023.
Zhou, Z., Bai. Q., Zhou, Z., Qiu, L., Blanchet, J., and Glynn, P. samile regret bound for distributionally robust offline tabular reinforcement learning. In International Conference Artificial Intelligence and Statistics, pp- 3331-3339. PMLR, 2021.
13

---

Breaking the Curse of Multiagency in Robust MARL
Algorithm N N-sample est on TT = Jejn),
1: Initialization: the reward F= 0 RSA,, and the transition model P = 0 E RSAA
2: for (s, E S x A, do
3: fort = 2, .N do
4: Sample a' (s,a,) (s,(s, constructed by independent actions drawn from policy:
az(s,a)) a:) ind (3)( (i i) and az(s, 02) O2.
(25)
5: Sample from the generative model:
(s,(), (z) = rt.n(s,a'(s,aa)) s3 (1,
(26)
6: end for
7: Set f(s, a:) = N EIE(N] rin ai) and P( t EnENN 1,82.0 = =
8: end for
9: Return: empirical model (f, P).
A Related works
Breaking curse of multiagency for standard Markov games. Breaking the curse of multiagency is a major and preva- lent challenge in sequential games. In standard multi-agent general-sum MGs, it has been shown that learning a Nash equilibrium requires an exponential sample complexity (Song et al., 2021; Rubinstein, 2017; Bai & Jin, 2020). How- ever, for other types of equilibria, such CE and CCE, many works have successfully broken the curse of multiagency. Specifically, for finite-horizon general-sum MGs in the tabular setting with finite state and action spaces, Jin et al. (2021) developed the V-learning algorithm for learning CE and CCE with the sample complexity of Ó(H ((max:e(m) A,)3/c²) and Õ(H1S S max A,/="), respectively; Daskalakis et al. (2023) achieved a sample complexity of Ö(H 5 max A./e²) for learning a CCE. Beyond tabular settings, Wang et al. (2023) and Cui et al. (2023) extended these results to linear func- tion approximation, achieving sample complexities of (dd H (max;e[n) A&) /e²) and O(H10d'' log (max,e(m) A.) /c*), respectively, where d is the dimension of the linear features. For Markov potential games, subelass of MGs, Song et al. (2021) provided centralized algorithm that learns NE with a sample complexity of Ö(H* S maxie|m] As/e²).
Finite-sample analysis for distributionally robust Markov games. Robust Markov games under environmental uncer- tainty are largely underexplored, with only few provable algorithms (Zhang et al., 2020a; Kardeş et al., 2011; Ma et al., 2023; Blanchet et al., 2023; Shi et al., 2024b). Existing sample complexity analyses all suffer from the daunting curse of mul- tiagency issues, or impose an extremely restricted uncertainty level that can fail to deliver the desired robustness (Ma et al., 2023; Blanchet et al., 2024; Shi al., 2024b). Specifically, they all consider a class of RMGs with the (s, reectanggll condition, where the uncertainty sets for each agent can be decomposed into independent sets over each (s, a) pair. Shi al. (2024b) considered the generative model with an uncertainty set measured by the TV distance, Blanchet et al. (2023) treated different sampling mechanism with offline data for both the TV distance and KL divergence. In addition, Ma et al. (2023) required the uncertainty level be much smaller than the accuracy-level and an pustance-dependee
parameter (i.c., Puin } for all i E [n]). This can thus fail to maintain the desired robustness, especially when the accuracy
0i S. max 3 H requirement is high (i.e., e + 0) or the RMG has small minimal positive transition probabilities (i.e., Puin -> 0).
Robust MARL. Standard MARL algorithms may overfit the training environment and could fail dramatically due to the perturbations and variability of both agents' behaviors and the shared environment, leading to performance drop and large deviation from the equilibrium. To address this, this work considers robust variant of MARL adopting the distributionally robust optimization (DRO) framework that has primarily been investigated in supervised learning (Rahimian & Mchrotra, 2019; Gao, 2020; Bertsimas et al., 2018; Duchi & Namkoong, 2018; Blanchet & Murthy, 2019) and has attracted a lot of attention in promoting robustness in single-agent RL (Nilim& & El Ghaoui, 2005; Iyengar, 2005; Badrinath & Kalathil, 2021; Zhou et al., 2021; Shi & Chi, 2024; Wang et al., 2024; Shi et al., 2023; Clavier et al., 2024). Beyond the RMG framework considered in this work, recent research has advanced the robustness of MARL algorithms from various perspectives, including resilience to uncertainties or attacks on states (Han et al., 2022: Zhou & Liu, 2023), the type of agents (Zhang et al., 2021), other agents' policies (Li et al., 2019; Kannan et al., 2023), offline data poisoning (Wu et al., 2024; McMahan
14

---

Breaking the Curse of Multiagency in Robust MARL
Algorithm 2 Robust-Q-FTRL
1: Input: learning rates { and {Nk41h number of iterations K per time step, and number of samples N per iteration.
2: Initialization: +1, (s, 0 and ( [s) 1/A, for all [n] and then all (h, 8, a.)
[H] X 8 x Ar
3: // start recursive learning process.
4: for = H, H - 1, 1.... do
5: for k = 1,2, ... K do
6: for 1.2....... do
7:
//costruuct empirical models and estimate current robust Q-function (.,. N- N-sample estimation ( bitn)) i, h.). (Algorithm 1)
8:
9:
Estimate robust Q-function d of current o according to (16).
online learning procedure
Update the Q-estimate Q (1 ork Q aughn and apply FTRL:
exp (Tk+ Q2 a:))
v(s,a,) E ESx Ar:
bel k+l i
(a: (8) En exp (nx 1 a'))
(27)
12:
end for
13:
end for
14:
set the final robust value estimate at time step h.
15:
for = 1,2, ... y do
16:
For all E set (s) to be the optimistic bonus term (20) and
K
(s)(s) = min
K
( (.s), (. + Bsn(s), H - h 11
(28)
17: end for
18: end for
19: Output: set of policies { = (Tti, x ... x Tn,h) (ee.),)ej]Keeee and a distribution = (En over them. For any
time step h, En is the distribution over { [K]K]] so that En (=t) = a
et al., 2024), and nonstationary environment (Szita et al., 2003). A recent review can be found Vial et al. (2022).
15


Reviews:
[{"review_id": "FP1iqb06CK", "reviewer": "Reviewer_5hU2", "summary": "This paper addresses the robustness issue in MARL by proposing a novel approach based on fictitious uncertainty sets. The main contributions are as follows:\n1. The authors define a new type of uncertainty set, which incorporates both environmental uncertainty and the behavior of other agents. Then they prove the existence of robust NE and CCE under it.\n2. They also design a sample-efficient algorithm, Robust-Q-FTRL. The algorithm leverages tailored adaptive sampling strategy to find an approximate robust CCE, just with polynomial sample complexity.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for recognizing and appreciating our contributions, both in terms of the problem formulation and the technical results. This acknowledgment is extremely rewarding!\n\n### 1. How does this work perform in real-world MARL tasks, and are there existing practical applications?\n\nThanks for pointing out this essential point! Definitely, practical usefulness is the main motivation behind our problem formulation and the proposed fictitious uncertainty set. Currently, two promising classes of applications emerge from this work, providing exciting future research directions:\n* **Understanding human preferences regarding risk and robustness under uncertainty**: A classical finding in behavioral economics is that humans are typically risk-averse and prefer robustness when facing uncertainty stemming from other players or the environment [1]. Applying our algorithms to real-world human data could help predict individual risk preferences and facilitate the design of personalized decision-making strategies for users.\n* **Improving robustness in safety-critical applications.** As mentioned in the introduction, numerous safety-critical scenarios can benefit from our proposed framework to identify optimal solutions for multi-agent interactions, such as financial markets, social dilemmas, autonomous driving, and human-robot interactions. Various experimental scenarios include  autonomous driving simulations in CARLA, financial analysis using Kaggle datasets, and other datasets in Hugging Face, as well as real-world experiements for human-robot interactions with the humanoid robot Unitree G1.\n\nIn this work, we focus on taking an initial step toward developing a clear and realistic formulation and framework for players in multi-agent systems. As the reviewer suggested and recognized, the next step is to apply this framework to diverse practical scenarios.\n\n### 2. Further experiments to verify the effectiveness of the algorithm.\n\nThank you very much for this valuable suggestion! In this work, we focus on taking an initial step toward developing a clear and realistic formulation and framework for players in multi-agent systems. As the reviewer suggested, further experimental validation of both the proposed problem formulation and the corresponding algorithms would be highly valuable across diverse application scenarios. In the future, we are considering several such scenarios, including autonomous driving simulations in CARLA or real-world experiements for human-robot interactions with the humanoid robot Unitree G1.\n\n### 3. Discussions on the computational complexity of Robust-Q-FTRL\n\nWe sincerely thank the reviewer for this valuable suggestion. In summary, the computational complexity of our proposed Robust-Q-FTRL algorithm is similar to that of the current state-of-the art algorithm for standard MARL presented in [2]. Specifically, Robust-Q-FTRL converges within $K=O(\\frac{H^3}{\\epsilon^2})$ iterations, with each iteration requiring computational complexity $O(HS\\log(S)\\sum_{i}A_i)$, which is nearly linear with respect to the size of the state and action spaces. As the reviewer suggested, we will incorporate this detailed discussion following the introduction of our main result, Theorem 4.1.\n\n\n### 4. An extra period at the end of page 2, line 97\nThank you for pointing this out. We have removed the extra period and will thoroughly polish the entire manuscript again in the revised version.\n\n> [1] Goeree, Jacob K., Charles A. Holt, and Thomas R. Palfrey. \"Risk averse behavior in generalized matching pennies games.\" Games and Economic Behavior 45.1 (2003): 97-113. \\\n    [2] Li, Gen, et al. \"Minimax-optimal multi-agent RL in Markov games with a generative model.\" Advances in Neural Information Processing Systems 35 (2022): 15353-15367.", "claims_and_evidence": "All claims made in the submission are well-supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "This paper uses sample complexity as its evaluation criteria to describe the effectiveness of the algorithm, and it’s meaningful.", "theoretical_claims": "No obvious errors were found, but further validation is still required.", "experimental_designs_or_analyses": "There is no experiment, but comprehensive theoretical proofs, including the definition of the fictitious uncertainty set, the existence of robust NE and CCE, and the sample complexity analysis of the Robust-Q-FTRL.", "relation_to_broader_scientific_literature": "It can open up new research directions in MARL, such as uncertainty set selection and construction.", "essential_references_not_discussed": "No other works related.", "other_strengths_and_weaknesses": "Strengths:\n1. Inspired by behavioral economics, the proposed fictitious uncertainty set integrates environmental uncertainty and the behavior of other agents, better reflecting real-world human decision-making, demonstrating significant innovation.\n2. The authors provide rigorous proofs for the existence of robust NE and CCE, along with detailed sample complexity analysis, offering solid theoretical support.\n3. The Robust-Q-FTRL is the first algorithm with sample complexity scaling polynomially with all key parameters in RMGs, significantly improving scalability. This may open up new research directions in related area.\n4. The paper is well-organized, with a clear presentation of the research background and preliminary knowledge. And the logical flow is rigorous, making it friendly to reader and easy to follow.\nWeaknesses:\n1. The paper lacks experiments or simulations to verify the effectiveness of the algorithm. While the theoretical contributions are notable, the absence of empirical evidence makes it difficult to fully assess its practical applicability.\n2. There is no detailed discussion on computational complexity. Although the sample complexity is optimized, the algorithm's computational complexity may be still high, especially in large state and action spaces.", "other_comments_or_suggestions": "In Section 1.2, the sentence \"... through rational deviations..\" (page 2, line 97) appears to have an extra period at the end, which should be removed for consistency.", "questions_for_authors": "I believe this is an excellent paper and I have only one question:\nQ1: How does this work perform in real-world MARL tasks? Are there any practical applications that have already been implemented?\nThis question does not affect my overall evaluation of the paper.", "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": "SyFXIxF7vn", "reviewer": "Reviewer_mEkj", "summary": "The paper proposes a robust multi-agent reinforcement learning framework based on a new fictitious uncertainty set. It proves the existence of robust Nash equilibria and coarse correlated equilibria then introduce a novel algorithm, Robust-Q-FTRL, which adaptively samples from a nominal generative model and solves a dual-optimization problem to estimate robust Q-values. Robust-Q-FTRL breaks the curse of multiagency and thus improves scalability compared to prior methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the careful reading of the paper and the insightful and valuable feedback.\n\n### 1. Additional experiments verifying the effectiveness of Robust-Q-FTRL against baseline methods could be beneficial.\n\nThank you very much for this valuable suggestion! As the reviewer rightly observed, in this work, we focus on taking an initial step toward developing a clear and realistic formulation and framework for players in multi-agent systems under uncertainty. Towards this, we introduce a fictitious uncertainty set inspired by behavioral economics, establish the existence of Nash equilibria (as well as CCE and CE) and propose an algorithm with theoretical guarantees. As the reviewer suggested, further experimental validation of both the proposed formulation and the proposed algorithm with comparison to baseline across diverse application scenarios would be highly valuable. In the future, we are considering several such scenarios, including autonomous driving simulations in CARLA or real-world experiements for human-robot interactions with the humanoid robot Unitree G1.\n\n### 2. Can some of the assumptions in Robust-Q-FTRL be relaxed to make it applicable to deep MARL?\n\nThank you for raising this valuable point! Both assumptions underlying Robust-Q-FTRL can be relaxed to better align with practical deep MARL settings, which are truly interesting future directions. Specifically:\n* **Relaxation of data collection through a generative model:** Our theoretical findings have the potential to extend to more practical data collection scenarios commonly used in deep MARL, such as online or offline settings. Exploring these extensions represents an interesting direction, which introduces additional challenges—particularly in online settings, which inherently pose difficulties in terms of statistical estimation and sample efficiency [2].\n* **Relaxation of the tabular Markov game formulation for MARL problems:** We believe our current results in tabular cases provide a strong foundation for exploring more general scenarios involving function approximation. This aligns closely with deep MARL, where neural networks are typically employed to approximate policies and Q/V-value functions. Nevertheless, adapting our approach to general robust MARL problems (e.g., robust linear MARL) will require distinct problem formulations—an open research area with no existing solutions to the best of our knowledge. Moreover, algorithm design and theoretical analysis frameworks would necessitate different assumptions, such as linearization conditions for linear function approximation [1] and realizability or low-rank structural assumptions for general function approximation.\n\n> [1] Yuanhao Wang, Qinghua Liu, Yu Bai, and Chi Jin. \"Breaking the curse of multiagency: Provably efficient decentralized multi-agent rl with function approximation.\" COLT 2023. \\\n    [2] Lu, Miao, et al. \"Distributionally robust reinforcement learning with interactive data collection: Fundamental hardness and near-optimal algorithm.\" arXiv preprint arXiv:2404.03578 (2024).", "claims_and_evidence": "The paper’s claims that it breaks the curse of multiagency is supported by sample complexity guarantees.", "methods_and_evaluation_criteria": "The paper is mainly theoretical and it makes sense to compare time complexity with those of the existing uncertainty-set-based baselines.", "theoretical_claims": "I did not do a detailed verification of the proofs for the theoretical claims. However, the arguments presented appear logically sound based on the provided explanations.", "experimental_designs_or_analyses": "There are no experiments.", "relation_to_broader_scientific_literature": "Breaking the curse of multi-agency is a longstanding challenge in multi-agent RL, where exponential blow-up of joint actions severely hinders scalability. This paper aligns with recent theoretical efforts to provide polynomial sample complexity for robust MARL. It contributes to ongoing work on designing algorithms that offers strong theoretical guarantees of efficiency.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths:\n\n- Breaking the curse of multi-agency is an important problem in MARL.\n- The sample complexity bounds surpass those of existing baselines.\n\nWeakness:\n\n- The paper lacks empirical experiments, so the method’s practical performance remains uncertain.", "other_comments_or_suggestions": "It would be better if the authors could empirically compare the convergence rate of Robust-Q-FTRL with the baselines.", "questions_for_authors": "- Can some of the assumptions in Robust-Q-FTRL be relaxed to make it applicable to deep MARL?", "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": "p9yjVOvQPk", "reviewer": "Reviewer_TP9Q", "summary": "The paper consider the problem of strategic interactions in uncertain environments; namely, robust Markov games (MGs). Robust Markov games are the multi-agent extension of Markov decision processes. The authors consider MGs where the transition kernel, i.e., the dynamics governing state transition, drift from some nominal value within a given uncertainty set; i.e., players might be trained on a game with a particular transition kernel, but when they deploy their policies, they do so on a game with slightly shifted transition kernel.\n\nThe goal of each agent is to compute policies that unilaterally perform well under the worst-case shift of the game's parameters (rewards and transitions). This objective gives rise to the notion of robust equilibria (robust Nash equilibrium, robust coarse-correlated equilibrium).\n\nThe authors contribute:\n1) a new assumption on the uncertainty sets, *fictitious* uncertainty sets that depend on the s-and-action pair of each agent. They do not depend on the joint-action of all players\n2) an algorithm with provable guarantees that converges to a robust coarse-correlated equilibrium in games that satisfy the latter assumption. \n\nThe sample and iteration complexity is polynomial in the natural parameters of the game and break the curse of multiagency. I.e., the dependence is on the sum of the size of individual action spaces and not the product.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### 1. \"The proposed algorithm is the first to overcome the curse of multiagency in RMGs, irrespective of the uncertainty set types.\" Is it due to an additional assumption?\nOur work breaks the curse of multiagency **through two key innovations: the introduction of a new class of fictitious RMGs and a new algorithm**. Both elements are essential. While the algorithm addresses a specific type of RMGs—the proposed fictitious RMGs—it is also the first to break the curse within the broader class of RMGs, as no prior work has achieved this, even for other subclasses of RMGs. Specifically,\n* **Novel and Realistic Assumption Inspired by Behavioral Economics** General RMGs are computationally intractable to solve, which leads to the widely used rectangularity assumptions. We didn't add addtional assumption, but replace the state-joint-action rectangular assumption used in prior work by a realistic rectangular assumption inspired by human behavior in behavioral economics. While this fictitious uncertainty set helps break the curse of multiagency, its primary purpose is to realistically model human behavior.\n* **Tailored Algorithm for Breaking the Curse of Multiagency.** Breaking the curse of multiagency in our proposed RMGs is more challenging than in standard MGs due to the nonlinearity of the robust value function, unlike the linear payoff functions in standard MARL. To address this, Algorithm 1 uses tailored sampling methods to handle nonlinearity and integrates them with a customized online learning algorithm.\n\n\n### 2. Is it \"impossible\" to break the curse for state-joint-action rectangular sets?\n* **Possibly Impossible, but a decisive conclusion for this is hard.** We agree with the reviewer's intuition that it may be impossible. Prior work shows an exponential sample complexity lower bound for computing Nash in general-sum games [2](http://arxiv.org/abs/1606.04550). However, no work has established a lower bound for computing CCE/CE in any type of game. This remains a very open question and area in game theory and a promising direction for future research.\n* We emphasize that the proposed fictitious uncertainty set is inspired by how human behavior is observed in reality through behavioral economics, not because the state-joint-action approach from prior works is infeasible, prompting a simpler alternative.\n\n### 3. Can other assumption lead to polynomial sample complexity results and make sense?\nA \"reasonable\" uncertainty set should ensure the well-posedness of the problem --- guaranteeing the existence of equilibria (e.g., Nash). This presents challenges in problem formulation (assumptions), requiring both a well-posed uncertainty set and feasible algorithms with polynomial sample complexity to compute the corresponding equilibria, which may involve trade-offs between the two. For example, $s$-rectangular uncertainty sets may ensure polynomial sample complexity but fail to guarantee Nash equilibrium, making them less desirable. Exploring other uncertainty sets that ensure well-posedness and allow tractable algorithm presents exciting opportunities for both game theory and MARL community.\n\n### 4. Get better convergence rates if use optimistic FTRL [Syrgkanis et al. 2015]?\nA brief answer, based on the authors' intuition, is no. The non-linear payoff functions in RMGs create a dilemma between the statistical complexity of estimating the transition kernel and the regret from online adversarial learning algorithms (e.g., FTRL and optimistic FTRL). The current bottleneck lies in the statistical complexity of estimating the transition kernel. Since we already use a state-of-the-art online learning algorithm with optimal sample complexity in standard MARL [1](http://arxiv.org/abs/2208.10458), switching to optimistic FTRL is unlikely to improve the results further.\n\n\n### 5. Others:\n* Adding detailed comparison between the proposed set and prior works.\n    * As the reviewer suggested, we will certainly include a more detailed comparison in the appendix of the revised version.\n* The reviewer is correct that the cartesian product in Equation (9) is over all $h,s,a_i$ for any $i$-th agent.\n* 289 to 305: Why does the value function take actions as arguments?\n    * Here, $V$ represents a general payoff function that naturally depends on all agents' actions, not the value function. We will revise $V$ to a different notation, $u$, to avoid ambiguity.\n* 306 to 317: Will $(s,\\textbf{a})$-rectangular degrade to single-agent $(s,a)$-rectangular RMDP in case other agents remain fixed?\n    * No, it does not degrade to $(s,a)$-rectangular RMDPs. Since even if other agents' policies $\\pi_{-i}$ are fixed but **stochastic**, their selected joint actions $\\textbf{a}\\_{-i}$ will vary, leading to corresponding uncertainty sets around each joint action $\\textbf{a}\\_{-i}$. As a result, other agents cannot be treated as a fixed part of the environment, preventing the model from simplifying to the single-agent $(s,a)$-rectangular case.", "claims_and_evidence": "In general, the authors clearly support their claims with formal proofs. One of the parts that is slightly confusing is when they note *\"To the best of our knowledge, Robust-Q-FTRL with the above sample complexity is the first algorithm for RMGs breaking the curse of multiagency, regardless of the types of uncertainty sets.\"*\n\nYes, their algorithm breaks the curse of multiagency but this is due to the additional assumption. They convincingly argue that this is a reasonable assumption, nevertheless, the claim that the algorithm breaks the curse of multiagency in RMG is imprecise.", "methods_and_evaluation_criteria": "The methods used to support the claims where mathematical formal reasoning.", "theoretical_claims": "I went over the proof of theorem 3.1 in the appendix which proves the existence of robust NEs which also implies the existence of robust CCEs.\n\nI also went the main parts of the proof of theorem 4.1 (main contribution of the paper) and believe that it is correct.", "experimental_designs_or_analyses": "I check the the validity of mathematical arguments.", "relation_to_broader_scientific_literature": "The authors seem to cite most relevant work in MARL and robust MDPs and robust MGs. They even connect their assumptions to economic theory which I really appreciate as the assumption seems well-founded.", "essential_references_not_discussed": "I do not know the area of robust MGs and MDPs very well so I do not know whether they are missing some crucial reference.", "other_strengths_and_weaknesses": "* One of the weakness of the writing. I struggled understanding their definitions and how their fictitious uncertainty sets compare with previous assumptions. It required opening the cited papers to understand that. Since the authors are introducing a new assumption, in my opinion, they should take the time to carry out an explicit comparison between their assumption and the state-joint-action rectangular uncertainty set assumption. (I.e., the most similar assumption to theirs.)\n\n* There seems to be a gap in the understanding of the complexity of solving RMGs. Is it perhaps impossible to break it for state-joint-action rectangular uncertainty sets? Answering in the positive would strengthen the necessity of this paper assumption\n\n* The claim that the curse of multiagency is surpassed is true but only thanks to this assumption.", "other_comments_or_suggestions": "Equatoin 9: There is no description what a the cartesian product is over. I am guessing all $h,s,a$.\n\n289 to 305: left col. notation $V_{i,h}^{\\pi, P}(a_i, \\bm{a}_{-i})$ is confusing. Why does the value function take actions as arguments?\n\n306 to 317: is it not the case for $(s,\\bm{a})$-rectangular to degrade to $(s,a)$-rectangularity condition in case other agents remain fixed?", "questions_for_authors": "* Is it impossible to break the curse of multiagency for state-joint-action rectangular uncertainty sets?\n* What are other assumption that can lead to polynomial sample complexity results and make sense?\n* Would you be able to get better convergence rates if you used optimistic ftrl [Syrgkanis et al. 2015]?\n\nSyrgkanis, V., Agarwal, A., Luo, H. and Schapire, R.E., 2015. Fast convergence of regularized learning in games. Advances in Neural Information Processing Systems.", "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": "vpXuNaTmjF", "reviewer": "Reviewer_Wjwo", "summary": "This paper studies the problem of multi-player general-sum robust Markov games (RMGs). Via proposing a new robustness measure called fictitious uncertainty set that centers at $(s,a_i)$ instead of $(s,\\mathbf a)$, the authors break the curse of multi-agents (i.e., the dependency is $\\sum_{i=1}^n \\lvert A_i\\rvert$ rather than $\\prod_{i=1}^n \\lvert A_i\\rvert$) for the first time in RMGs.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Q1. The idea of fictitious uncertainty set looks interesting, can it be useful somewhere else.\n\nFictitious uncertainty sets, inspired by behavioral economics, hold significant value in game theory and behavioral economics and have several meaningful applications:\n\n* **Understanding human preferences regarding risk and robustness under uncertainty**: Humans are generally risk-averse and prefer robustness under uncertainty [1](https://dl.acm.org/doi/10.1145/3490486.3538351) [2](https://arxiv.org/html/2502.11243v1) [3](https://link.springer.com/article/10.1007/s10683-005-5374-7), whose behaviors correspond to our fictitious uncertainty set, rather than the $(s,\\mathbf{a})$-rectangular uncertainty set used in prior works. Applying our framework to real-world human data could help predict individual risk preferences and facilitate the design of personalized decision-making strategies for users.\n* **Improving robustness in safety-critical applications.** As mentioned in the introduction, numerous safety-critical scenarios can benefit from our proposed framework to identify optimal solutions for multi-agent interactions, such as financial markets, social dilemmas, autonomous driving, and human-robot interactions.\n\n### 2. Further improve the presentation.\n\nWe sincerely thank you for your valuable suggestion regarding the writing. In the revised version of our work, we have moved part of the background information to the Appendix and included the algorithm description in the main text.\n\n### 3. The convergence rate\n\nWe acknowledge that the $O(\\epsilon^{-4})$ convergence rate may seem suboptimal but note that rate $O(\\epsilon^{-4})$ or $O(\\epsilon^{-3})$ are common in MARL literature, as seen in [4](https://arxiv.org/pdf/2302.03673) and [5](https://arxiv.org/pdf/2204.03991). As the first to break the curse of dimensionality in RMGs, we see great value in further improvements and plan to explore ways to accelerate the algorithm in future work.\n\n### 4. The relationship of this work to linear MG works\n* Is the idea of assuming $(s,a_i)$ structures around instead of $(s, \\textbf{a})$ similar to the independent linear function approximation in linear MGs?\n\n    **The proposed $(s,a_i)$ plays a fundamentally different role in robust MGs compared to the methods used in non-robust linear MGs..**\n\n    1. **Different problems and challenges: Nonlinearity in Robust MGs.** Robust MGs pose additional challenges compared to non-robust MGs due to the nonlinearity of the robust value function, unlike the linear payoff functions in non-robust MARL, which fundamentally alters the problem structure and solution methods.\n    2. **Inspired by game theory and behavioral economics.** The $(s,a_i)$ structure is considered for two key reasons: 1) Capturing human behavior in reality inspired by behavioral economics, **both $(s,a_i)$-rectangular structures and $s$-rectangular structures ($\\otimes\\_{s\\in \\mathcal{S}} \\mathcal{U}\\_\\rho^{\\sigma_i}(\\mathbb{E}\\_{\\mathbf{a} \\sim \\pi_h} P\\_{h, s, \\mathbf{a}})$) can predict human behavior**, but $(s, \\textbf{a})$ fails to do so; 2) We ultimately choose to consider the $(s,a_i)$ structure instead of the $s$-structure because, the $(s,a_i)$-rectangular set makes Nash (also CCE and CE) is guaranteed to exist, whereas this is not the case for the $s$-rectangular set.\n    3. **Distinct techniques for breaking the curse of dimensionality in $(s,a_i)$ structures** A direct indication is that our techniques developed for $(s,a_i)$ structures also apply to $(s)$-uncertainty set, whereas no corresponding result exists for non-robust linear MG.\n\n\n* How does your model technically break the curse of multi-agency compared to prior work?\n\n    A concise answer is that it allows for the decomposition of the non-linear payoff function in robust MGs. The key reason why the $(s, a_i)$ structure helps break the curse of dimensionality lies in its role within the Bellman equation:\n    $$\n    V^{\\pi}\\_{i,h}(s) = \\mathbb{E}\\_{\\mathbf{a} \\sim \\pi_h(s)}[r\\_{i,h}(s, \\mathbf{a})] + \\mathbb{E}\\_{a_i \\sim \\pi_{i,h}(s)} \\left[ \\inf\\_{\\mathcal{U}\\_{\\rho}^{\\sigma_i} \\left(P^{\\pi_{-i}}\\_{h,s,a_i} \\right)} P V^{\\pi}\\_{i,h+1} \\right],\n    $$\n    $V^{\\pi}\\_{i,h}$ becomes a linear function with respect to the $i^{th}$ agent's policy $\\pi_{i,h}$. This property also holds for the $(s)$-uncertainty set but not for the $(s, \\mathbf{a})$ uncertainty set used in prior works. Consequently, we can leverage concentration inequalities to control the gap between the estimated and true value functions, effectively breaking the curse of dimensionality for $(s, a_i)$ and $(s)$ uncertainty sets, but not for $(s, \\mathbf{a})$.", "claims_and_evidence": "There is no proof sketch in the main text, making it pretty hard to justify the main insight in Theorem 4. I trust the authors out of good faith.", "methods_and_evaluation_criteria": "The models and metrics are standard and fair.", "theoretical_claims": "Didn't check the proof as there is no concise sketch in the main text or the appendices.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The idea of fictitious uncertainty set looks interesting, but the authors didn't discuss a lot (and whether it can be useful somewhere else). Also, see the Questions for a series of recent similar ideas in (non-robust) Linear MGs; I'm not sure whether they're relevant enough, but they look a bit similar.", "essential_references_not_discussed": "I feel the discussion is pretty complete. See Questions part for several recent papers in (non-robust) linear MGs that I'm not sure whether relevant enough.", "other_strengths_and_weaknesses": "As mentioned earlier, the presentation can be improved: There is too much background information, making the room for algorithms, discussions of technical contributions, and proof sketch very limited. Looks like the main text could be polished to make slightly more room (e.g., math equations in Theorem 4.1 are spaced in an luxury way), but I still suggest the authors to move more background information into the appendices for the ease of reading. \n\nThe convergence $O(\\epsilon^{-4})$ is slow, but it's fine as it's the first to break curse of multi-agencies.\n\nThe assumption of generative model is also non-desirable, but it's also fine since it's also presented in previous works on RMG.", "other_comments_or_suggestions": "See below.", "questions_for_authors": "In the recent literature of breaking the curse of multi-agents in Linear Markov Games (non-robust) ones, a similar idea of \"independent linear approximation\", which essentially assumes that Q-functions are linear as $Q(s,a_i)=\\theta^T \\phi(s,a_i)$ instead of the previous \"global linear approximation\" scheme that $Q(s,\\mathbf a)=\\theta^T \\phi(s,\\mathbf a)$. See below for a series of such paper, the first two are concurrent and the last two are concurrent:\n\n1. Qiwen Cui, Kaiqing Zhang, and Simon Du. \"Breaking the curse of multiagents in a large state space: Rl in markov games with independent linear function approximation.\" COLT 2023.\n2. Yuanhao Wang, Qinghua Liu, Yu Bai, and Chi Jin. \"Breaking the curse of multiagency: Provably efficient decentralized multi-agent rl with function approximation.\" COLT 2023.\n3. Junyi Fan, Yuxuan Han, Jialin Zeng, Jian-Feng Cai, Yang Wang, Yang Xiang, and Jiheng Zhang. \"Rl in markov games with independent function approximation: Improved sample complexity bound under the local access model.\" AISTATS 2024.\n4. Yan Dai, Qiwen Cui, and Simon Du. \"Refined sample complexity for markov games with independent linear function approximation.\" COLT 2024.\n\n**Question**:\n1. Is your idea of assuming structures around $(s,a_i)$ instead of $(s,\\mathbf a)$ similar to the independent linear function approximation above?\n2. Could you sketch how your model (compared to the previous $(s,\\mathbf a)$ one) helps you to break the curse of multi-agency in a more technical way?\n\n**Remark.** The current rating assumes all the proofs 1) are correct, and 2) do not contain significant technical innovations that can be of independent interest. Feel free to correct me if I am missing something.", "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:

Meta-review: All reviewers agree that the paper has an interesting contribution and should be accepted.
Decision: Accept (poster)