Robust Multi-Agent Reinforcement Learning with State Uncertainty
Authors: Sihong He
Songyang Han
Sanbao Su
Shuo Han
Shaofeng Zou
Fei Miao
Venue: Accepted by TMLR ()

Abstract: In real-world multi-agent reinforcement learning (MARL) applications, agents may not have perfect state information (e.g., due to inaccurate measurement or malicious attacks), which challenges the robustness of agents' policies. Though robustness is getting important in MARL deployment, little prior work has studied state uncertainties in MARL, neither in problem formulation nor algorithm design. Motivated by this robustness issue and the lack of corresponding studies, we study the problem of MARL with state uncertainty in this work. We provide the first attempt to the theoretical and empirical analysis of this challenging problem. We first model the problem as a Markov Game with state perturbation adversaries (MG-SPA) by introducing a set of state perturbation adversaries into a Markov Game. We then introduce robust equilibrium (RE) as the solution concept of an MG-SPA. We conduct a fundamental analysis regarding MG-SPA such as giving conditions under which such a robust equilibrium exists. Then we propose a robust multi-agent Q-learning (RMAQ) algorithm to find such an equilibrium, with convergence guarantees. To handle high-dimensional state-action space, we design a robust multi-agent actor-critic (RMAAC) algorithm based on an analytical expression of the policy gradient derived in the paper. Our experiments show that the proposed RMAQ algorithm converges to the optimal value function; our RMAAC algorithm outperforms several MARL and robust MARL methods in multiple multi-agent environments when state uncertainty is present. The source code is public on https://github.com/sihongho/robust_marl_with_state_uncertainty.

Published in Transactions on Machine Learning Research (06/2023)
Robust Multi-Agent Reinforcement Learning with State Un- certainty
Sihong He
sihong.he Wuconn.
Deportment of Computer Science and Engineering University of Connecticut
Songyang Han
songyang.han han &uccon edu
Department Computer Science and Engineering University of Connecticut
Sanbao Su
Lunbeo.su@uccom edu
Department of Computer Science and Engineering University of Connecticut
Shuo Han
hanshuo@uic.o edu
Deportment of Electricol and Computer Engineering University of Ilinoiss Chicugo
Shaofeng Zou
szou3@buufallo.o edu
Department of Electrical Enginerring University at Buffalo, The State University of New York
Fei Miao
fei.miao Caconn edu
Deportment of Computer Science and Engineering University of Connecticut
Reviewed on OpenReview: https: // openreview. net/ forum? id= CgTkapZ6GG
Abstract
In real-world multi-agent reinforcement learning (MARL) applications, agents may not have perfect state information (e-g., due to inaccurate measurement malicious attacks), which challenges the robustness of agents' policies. Though robustness is getting important in MARL deployment, little prior work has studied state uncertainties in MARL, neither in problem formulation nor algorithm design. Motivated by this robustness issuc and the lack of corresponding studies, we study the problem of MARL with stale uncertainty in this work. We provide the first attempt to the theoretical and empirical analysis of this challenging problem. We first model the problem as a Markov Game with state perturbation adversaries (MG-SPA) by introducing a set state pertur adversaries into a Markov Game. We then introduce robust equilibrium (RF) as the solution concept of MG-SPA. We conduct fundamental analysis regarding MG-SPA such giving conditions under which such a robust equilibrium exists. Then we propose a robust multi-agent Q-learning (RMAQ) algorithm to find such an equilibrium, with convergence guarantees. To handle high-dimensional state-action space, we design a robust multi-agent actor-critic (RMAAC) algorithum based on an analytical expression of the policy gradient derived the paper. Our experiments show that the proposed RMAQ algorithm converges to the optimal value function; RMAAC algorithm outperforms several MARL and robust MARL methods in multiple multi-agent environments when state uncertainty is present. The source code is public on https: btaps://gtn ttt.gttt.bb....//gg///ggg..... wtw.uu...o//iioonhhooooo com/sihhogho/rooust marl with sttssttttt_tuee uncertainty

---

Published in Transactions on Machine Learning Research (06/2023)
1 Introduction
Reinforcement Learning (RL) recently has achieved remarkable success many decision-
agent Xsoal
obstacle
perturbed state
uncertainty set
making problems, such robotics, autonomous driving, traffic control, and game playing (Espeholt et al.
SAFE
SAFE
2018 Silver et al. 2017 Muih et al. 2015 He
ct al. 2022). However, in real-world applications,
the agent may face stale uncertainly in which ac- curate information about the state is unavailable. This uncertainty may be caused by unavoidable sensor mcasurement errors, noise, missing informa- tion, communication issues, and/or malicious at- tacks. A policy not robust to state uncertainty can result in unsafe bchaviors and even catastrophic outcomes. For instance, consider the path planning problem shown in Figure where the agent (green ball) observes the position of an obstacle (red ball) through sensors and plans safe (no collision) and shortest path to the goal (black cross). Tn Fig- ure (a), the agent
BOOm!
a
a+
(a)
(b)
(c)
optimal solution when knowing true state
unsafe solution when uncertainty exists
robust solution over state uncertainty
observe the true state (red ball) and choose optimal and collision-free curve at (in red) tangent to the obstacle. In com-
Figure 1: Motivation of considering state uncertainty in singlo-agent reinforcement lcarning.
parison, when the agent can only observe the perturbed state ă (yellow ball) caused by inaccurate sensing or state perturbation adversaries (Figure (b)), it will choose a straight line ā (in blue) as the shortest and collision-free free path langent to However, by following a, the agent actually crashes into the obstacle. To avoid collision in the worst case, one can construct state uncertainty set that contains the true state based the observed state. Then the robustly optimal path under state uncertainty becomes the yellow curve ä* langent to the uncertainly set, shown in Figure (c).
In single-agent RL, imperfect information about the state has been studied in the literature of partially observable Markov decision process (POMDP) (Kaclbling et al.) 1998). However, as pointed out in recent literature (Huang et al.) 2017 Kos Song. 2017 Yu et al. 2021b Zhang et al., 2020a),, the conditional obscrvation probabilities in POMDP cannot capture the worst-case (or adversarial) scenario, and the learned policy without considering state uncertainties may fail to achieve the agent's goal. Dealing with state uncertainty becomes even more challenging for Multi-Agent Reinforcement Learning (MARL), where each agent aims to maximize its own total return during the interaction with other agents and the environment (Yan & Wang 2020b). Even if one agent receives mislcading state information, its action affects both its own return and the other agents' returns (Zhang el al. 2020b) and may result in catastrophic failure. The existing literature of decentralized partially observable Markov decision process (Dec-POMDI) (Oliehoek) ct al. 2016) docs not provide thcoretical analysis or algorithmic tools for MARL under worst-casc state uncertainties either.
To better illustrate the effect of state uncertainty in MARL, the path planning problem in Figure D modified such that two agents are trying to reach their individual goals without collision (a penalty or negative reward applied). When the blue agent knows the true position & (the subscript denotes time, which starts from 0) of the green agent, it will get around the green agent to quickly reach its goal without collision. However, in Figure (a), when the blue agent can only observe the perturbed position ag (yellow circle) of the green agent, would choose a straight line that it thought safe (Figure ( (al)), which eventually leads a crash (Figure (a2)). In Figure (b), the blue agent adopts robust trajectory by considering state uncertainty set based on its observation. As shown in Figure (b1), there is no overlap between (s/, +g) or (s), s.)). Since the uncertainly sets centered at z and oy (the dotted circles) include the true state of the green agent, this robust trajectory also ensures no collision between (sh, or (sh. The blue agent considers the interactions with the green agent to ensure no collisions at any time. Therefore, it is necessary to consider state uncertainty in a multi-agent setting where the dynamics of other agents should be considered.
2

---

Published in Transactions on Machine Learning Research (06/2023)
In this work, develop a robust MARL framework that accounts for state uncertainty. Specifically, we model the problem of MARL with state uncertainly as a Markov game with state perturbation adversaries (MG- SPA), in which each agent associ- ated with state perturbation adver- sary. One state perturbation adver- sary always plays against its correspond- ing agent by preventing the agent from knowing the true state accurately, We analyze the MARL problem with adver- sarial worst-case state perturbations. Compared to single-agent RL, MARL is more challenging due to the interac- tions among agents and the necessity of studying equilibrium policies Nash
agent
agent
perturbed state
g
X goal
uncertainty
perceivably safe
BOOM!
BOOM!
St
$
S
%
%
g
(a)
(a1)
(a2)
perceivably safe
SAFE
SAFE
SF
1951 McKelvey & McLennan 1996
(b1)
(b2)
Slantchev 2008; Daskalakis et al. 2009
Etessami Yannakakis) [2010).
The
Figure 2: Motivation of considering state uncertainty in MARL.
contributions of this work are rized as follows.
To the best of our knowledge, this work is the first attempt to systematically characterize state uncertainties MARL and provide both theoretical and empirical analysis. First, we formulate the MARL problem with state uncertainty as a Markov game with state perturbation adversaries (MG-SPA). We define the solution concept of the game as a robust equilibrium (RE), where all players including the agents and the adversaries use policies from which no one has an incentive deviate. In an MG-SPA, each agent not only aims to maximize its return when considering other agents' actions but also needs to act against all state perturbation adversaries. Therefore, a robust equilibrium policy of one agent is robust to state uncertaint Second, we study its fundamental properties and prove the existence of a robust equilibrium under certain conditions. We develop a robust multi-agent Q-learning (RMAQ) algorithm with a convergence guarantee and a robust multi-agent actor-critic (RMAAC) algorithm for handling high-dimensional state-action space. Finally, we conduct experiments a two-player game to validate the convergence of the proposed Q-learning method RMAQ. We test our RMAAC algorithm in several benchmark multi-agent environments. We show that our RMAQ and RMAAC algorithms can learn robust policies that outperform basclines under state perturbations in multi-agent environments.
Contributions:
Organization: The rest of the paper is organized as follows. The related work is presented in Section 2 In Section 3 we introduce some preliminary concepts in RL and MARL. The proposed methodology and corresponding analysis are in Section ! The proposed algorithms are in Section and experiments results are Scction d
We discuss some future work in Scction 7 In Scction N we conclude.
2 Related work
Robust Reinforcement Learning: Recent robust reinforcement learning studied different types of uncertainties, such as action uncertainties (Tsssler al.) 2019) and transition kernel uncertainties (Sinha et al. He et al. 2022). Some recent attempts at adversarial state perturbations for single-agent validated the importance of considering state uncertainty and improving the robustness of the learned policy in Deep RL (Hung et al. 2017 Lin et al.) 2017; Zhang et al. 2020a 2021 Everett et al.) 2021). The works of Zhang ct al. (2020a] 2021) formulate the state perturbation in single-agent RI as a modified Markov docision
2020 Yu et al. 2021b Hu et al.) 2020 Wang & Zou 2021 Lim & Autef 2019; Nisioti et al. 2021
process, then study the robustness of single-agent RL policies. The works of Huang al. (2017) and Lin
et al. (2017) show that adversarial state perturbation undermines the performance of neural network policies
3

---

Published in Transactions on Machine Learning Research (06/2023)
in single-agent reinforcement learning and proposes different single-agent attack strategies. In this work, we consider the more challenging problem of adversarial state perturbation for MARL, when the environment of an individual agent is non-stationary with other agents" changing policies during the training process.
Robust Multi-Agent Reinforcement Learning: There is very limited literature on the solution concept or theoretical analysis when considering adversarial stale perturbations in MARL. Other types of uncertaint ies have been investigated in the literature, such as uncertainties about training partner's type (Shen & How 2021), the other agents' policies (Li et al.] 2019 Sun et al., 2021: van der Heiden et al. 20200. and reward uncertainties (Zhang et al. 2020b/. However, the policy considered in these papers relies on the true state information. Hence, the robust MARL considered in this work is fundamentally different since the agents do not know the true state information. Dec-POMDP enables a team of agents to optimize policies with the
partial observable states (Oliehoek et al. 2016 Chen et al., 2022) The work of Lin et al. (2020) studies state perturbation in identical-interest MARL, and proposes an attack method to attack the state of one single agent in order to docrease the team reward. In contrast, we consider the worst-case scenario that the state of every agent can be perturbed by an adversary and focus on the theoretical analysis of robust MARL including the existence of optimal value function and robust equilibrium (RE). Our work provides formal definitions of the state uncertainty challenge in MARL, and derives both theoretical analysis and practical algorithms.
Game Theory and MARL: MARL shares theoretical foundations with the game theory research field and a literature review has been provided to understand MARL from a game theoretical perspective (Yang & Wang 2020a). A Markov game, sometimes called a stochastic game models the interaction between multiple agents (Owen] 2013 Littman 1994). Algorithms compute the Nash cquilibrium (NE) in Dec- POMDP (Oliehoek el al. 2016). POSG (partially observable stochastic game) and analysis assuming that NE exists (Chades et al. 2002 Hansen et al., 2004 Nair et al. 2002) have been developed in the literature without proving the conditions for the existence of NE. The main thcorctical contributions of this work include proving conditions under which the proposed MG-SPA has robust equilibrium solutions, and convergence analysis of our proposed robust multi-agent Q-learning algorithm. This is the first attempt to analyze the fundamental properties of MARL under adversarial state uncertainties.
3 Preliminary
Q-lcarning is a model-free single-agent reinforcement learning algorithm Sutton et al., 1998 The core of this method is a Bellman equation that q"(s, a) = r(s, + +7E max q (a', d'). The Bellman equation encourages a simple value iteration update which uses the weighted average of old Q-value and the new one. Q-learning learns the optimal action-value function qa a) by value itcration: (s, a) (1 -1 a)aaas a) + a [r(s, a) + E. p(s' a) maxa'eA fold(s',a') and the optimal action (=(s) = arg max qu (s. a). Deep Networs (DQN) use a neural network with parameter to approximate Q-value (Mnih al.] 2015 This allows the algorithm
handle larger state spaces. DQN minimizes the loss function defined in where of is target network that copies the parameter 0 occasionally to make training more stable. D is experience replay buffer. DQN uses experience replay, which involves storing and randomly sampling previous experiences to train the neural network, to improve the stability and efficiency of the learning procoss. The target network helps to prevent the algorithm from oscillating or diverging during training.
(()) = EE lv a(,,))))² = r() + m a''
(1)
a'EA
Actor-Crite (AC) is a single-agent reinforcement learning algorithm with two parts: actor decides which action should be taken and critic evaluates how well the actor performs (Sutton et al. 1998). The actor is parameterized by To(-(s) and iteratively updates the parameler 0 to maximize the objective function J(0) = Exrp,a - rr,,,, a;)], where t denotes a trajectory and p is the state transition probability distribution. The critic is parameterized by (s a) and evaluates actions chosen by the actor by computing the Q-value i.e. action-value function. The critic can update itself by using [ The actor updates its parameter by using the gradient: [o) Expparny [4" (8, aoVo
Vo log (a]ss))]
4

---

Published in Transactions on Machine Learning Research (06/2023)
Markov game (MG) is used to model the interaction between multiple agents (Littman 1994 A Markov game, sometimes is called stochastic game (Owen 2013) defined a tuple G (W, S, HeN, hee. p. p. where is the state space, / is set of N agents, A' is the action space of agent
i, respectively (Littman 1994 Owen 2013 by E [0. 1) is the discounting factor. We define A A x ... x A A - A(S) controlled by the current state and joint action, where A(S) represents the set of all probability distributions over the joint state space S. Each agent has reward function, SS x A At time i, agent chooses its action of according to policy x' S + A(A'). For each agent i, it attempts to maximize its expected sum of discounted rewards, i.e. its objective function Ts) E E>/= (f-Ir((8) 4)) 8, or r--1s))].
as the joint action space. The stale transition p:
4 Methodology
In this section, to solve the robust multi-agent reinforcement learning problem with state uncertainty, we first introduce the framework of the Markov game with state perturbation adversaries. We then provide characterization results for the proposed framework: Markov and history-dependerr policies, the definition of solution concept called robust equilibrium based value functions, derivation of Bellman equations, well certain conditions for the existence of a robust equilibrium and the optimal value function.
4.1 Markov Game with State Perturbation Adversaries
We use tuple G (W,M, S, (A' [B')eem (ee f.) to denote a Markov game with state perturbation adversaries (MG-SPA). In MG-SPA, we introduce an additional set of adversaries M= [i.....,.1) .N to a Markov game (MG) with an agent set W. Each agent i is associated with an adversary and can observe the true state E S without adversarial perturbation. Each adversary is associated with an action b² E B and the same state & E S that agent i has. We define the adversaries joint action B¹ .... BN At time I, adversary can manipulate the corresponding agent i's state information. Once adversary gets state 8t, it chooses an action bj according to a policy p² ABB). According to perturbation function S' adversary perturbs state to 5 [st, b)) E S. We use 3, = (.),...,33)) to denote a joint perturbed state and use the notation fst, = 8t. We denote the adversaries' joint policy p(b]s) Ili (bi(s). The definitions of agent action and agents' joint action are the same their definitions in an MG. Agent i chooses its action with 8 according to a policy N' ()()))) T': S - A(A'). We denote the agents' joint policy as T (a(s) = IhE (Ta'5""). Agents execute the agents' joint action ae, then at time + 1, the joint state s; turns to the next state $t+1 according to a transition probability function p S x A B - A(S). Each agent gets a reward according to a state- reward function rf S A B + Each adversary gets an opposite reward -ri. In an MG, the transition probability function and reward function considered as the model of the game. In an MG-SPA, the perturbation function f is also considered part of the model, ie., the model of an MG-SPA consists of f.p and hee.
as b = (b), ,.., DR E B,
Definition 4.1 (Value Functions).
TT = (vT.0.1.... ,..., , u.T.NN), gm function for short, and the action-value function, respectively. The ith element v. and q are defined as following:
(q=.p.l.... gTt..N) are defined as the state-value function or value
1 n.p. (s, E
p/ 8,01 = b, b x(115))bb by p(-18t), =
(2)
T. (s)
=
r ssa, - a x--15r), by ~ p(-(s:), 3, f(s by)
(3)
To incorporate realistic settings into our analysis, we restrict the power cach adversary, which is a common assumption for state perturbation adversaries in the RL literature (Zhang et al. 2020a 2021 Everett et al., We define perturbation constraints z Bais(le 8) C S to restrict the adversary i to perturb
2021
5

---

Published in Transactions on Machine Learning Research (06/2023)
state only to a predefined set of states. (e) is e-radius ball measured in metric dist(-.",, which is often chosen to be the I-norm distance: dist(s, 5*) = ||s- [|s-5lll 1/, We omit the subscript dist in the following context. For each agent i, it attempts to maximize its expected sum of discounted rewards, iee its objective function J's, ST, p) = E 1 ri,,, ()))ss)))s = s, a ~ π xT)(5)), & = f(s,, be). b, ~ p(-(st)] Each adversary aims to minimize the objective function of agent i and is considered as receiving an opposite reward of agent i, which also leads to a value function (s, p) for adversary i. We further define the value functions in an MG-SPA as in Definition 4.1, Then we propose robust equilibrium (RE), a NE-structured solution as our solution concept for the proposed MG-SPA framework. We formally define RE Definition 4.2
Definition 4.2 (Robust Equilibrium).
Given Markov game with state perturbation adversaries G, a joint policy d, = (Te, where Th (m), ,n.) and p. (p_,..., .Ph) is said to be in robust equilibrium, or robust equilibrium, if and only if, for any i E N, E &
w (s)) 2 pl ( 2 ol of (t)))))))s)
(4)
where -i/ - represents the indices of all agents/ agenss//dverssries except agent i/ adversary i.
As the maximin solution is also a popular solution concept in robust RL problems (Zhang et al. 2020a here, we discuss why we choose a NE-structured solution other than a maximin solution. Firstly, we aim to propose a framework that can describe and model the interactions among agents when each agent has its own interest or reward function under state perturbations, and maximin solution may not be a general solution concept for robust MARL problems. A maximin solution is natural to use when considering robustness in single-agent RL problems and identical-interes: MARL problems, but it fails to handle those MARL problems where each agent has its own interest or reward function. Secondly, the Nash equilibrium is also a commonly used robust solution concept in both single-agent RL and MARL problems (Tessler et al. 2019 Zhang et al. 2020b). Many papers have used NE as their solution concept to investigate robustness in RL problems, and to the best of our knowledge, the NE-structured solution is the only one used in robust non-iidentical-intered MARL problems (Zhang et al.) 2020b). Lastly, for finite two-agent zero-sum games, it is known that NE, minimax, and maximin solution concepts all give the same answer (Yin et al., 2010 Owen
2013)
After defining RE, we seek to characterize the optimal value (s) = (o)( " (+)) defined by (5)
max,* min v(*5* aa af " (s)) For notation convenience, we use (s) to denote p( aa ah a (s).ss) The Bellman equations an MG-SPA are in the forms of (5) and (6). The Bellman equation a recursion for expected rewards, which helps us identify or find an RE.
a, b) = as, b) + Σ p(s'ls [s, $,,,u, max min E p
T(-13) p(1ss)
(5)
S'ES
vi(ss) max min E 3²
Σ LES
als/|s,a,
p(1s)
(6)
for all i E E M, where -= ( We prove them in the following subsection. The policies in 5 and (6) are defined to be Markov policies which only input the current state. The robust equilibrium is also based on Markov policics. History-dependent policies for MARL under state perturbations may improve agents' ability to adapt to adversarial state perturbations and random sensor noise, by allowing agents to take into account past observations when making decisions. Therefore, we further discuss how the current MG-SPA frame and solution concept adapt to history-dependent policies in subsection 4.3
(p and (m), n. 12 p-.) is robust equilibrium for a.
4.2 Theoretical Analysis of MG-SPA
In this subsection, we first introduce the vector notations we used in the theoretical analysis and define a minimax operator in Defiitiin 4.3 We then introduce Assumption 4.4 which is considered in our theoretical

---

Published in Transactions on Machine Learning Research (06/2023)
analysis. Later, prove two propositions about the minimax operator and Theorem 4.7 which shows series of fundamental characteristics of an MG-SPA under Assumption 4.4 e-g-, the derivation of Bellman equations, the existence of optimal value functions and robust equilibrium.
Vector Notations: To make the analysis easy to read, we follow and extend the vector notations in Puterman (2014). Tet V denote the set of bounded real valued functions on S with component-wise partial order and norm ||o0|| := supses [s)]. Let VM denote the subspace of V of Borel measurable functions. For discrete state space, all real-valued functions are measurable that V VMr But when S is continuum, VM is proper subset of V. Let (v', , V be the set of bounded real valued functions S x ..... S, I.c. the across product of N state set and norm ||a|| = sup, ||e|||- For discrete S, let |S| denote the number of elements in S. Let r¹ denote |S]-vector, with sth component r'(s) which is the expected reward for agent under state 8. And P the [S] x [S] matrix with (s, s')th entry given by p(s'|s). We refer to ra as the reward vector of agent i, and Pa as the probability transition matrix corresponding to a joint policy d = (T,, rá + 7 is the expected lotal one-period discounted reward of agent i, obtained using the joint policy d2........ ...... and P = we denote the expected total discounted reward of agent using as oi "i=r" " Pi-ri = rá, +>Pa, +...."" +
d= (T,, p). Let z as a list of joint policy {d1.d2...
Pa Pd._, r +... Now,
define the following minimax operator which used in the rest of the paper.
Definition 4.3 (Minimax Operator).
For of E V,8 E S, we define the nonlinear operator L' on (s) by L'u((s) = max, min min {P) where d = (m-i, a 3=3 p²). We also define the operator Lo(s) (s), ... vN (s)) (s) .........M... (s)). Then L'v is a ueccor,, with sth component (s)
For discrete S and bounded r², it follows from Lemma 5.6.1 in Puterman (014)) that L'v' E V for all vf e V. Therefore Lu E V for all v e V. And in this paper, we consider the following assumptions in Markov games with state perturbation adversaries.
Assumption 4.4.
(1) Bounded rewards; |r* b]1 S M < M < oo for all E a be B, and 8 E S.
(2) Finite state and action spaces: all S, B are finâte.
(3) Stationary transition probabilily and reward functions.
(4) f(s,-) is a bijection for any fixed E S.
(5) All agents share one commoo reward funclion.
Finite state and action spaces, bounded rewards, stationary (ransition kernels, and stationary reward functions are common assumptions in both reinforcement learning and multi-agent reinforcement learning literature (Puterman 2014 Başar Olsder 1998). Additionally, the bijection property of perturbation functions implies that in a finite MG-SPA, adversaries that adopt deterministic policies provide a permutation the state space. Collaboration and coordination among agents often required in real-world scenarios to achieve common goal. In such cases, shared reward function motivate agents to work together effectively. Moreover, the assumption of a shared reward function is necessary to transform an MG-SPA into zero-sum two-agent extensive-form game in our proof. Although these assumptions do not always hold true in real-world applications, they provide good properties for an MG-SPA and enable the first attempt of theoretical analysis on an MG-SPA. The next two propositions characterize the properties of the minimax operator L and space V. We provide the proof in Appendix A.2] These contraction mapping and complete space results are used in the proof of RE existence for an MG-SPA.
Proposition 4.5 (Contraction mapping).
Suppose 0 Σ y < 1, and Assumption 4.4 holds. Then L is a contraction mapping on V.
7

---

Published in Transactions on Machine Learning Research (06/2023)
Proposition 4.6 (Complete Space). The space V a complete normed lineor space.
In Theorem 4.7 we show some fundamental characteristics of an MG-SPA. In (1), we show that an optimal value function an MG-SPA satisfies the Bellman equations by applying the Squeeze theorem [Theorem 3.3.6, Sohrab (2003)] Theorem 4.7 427 shows that the unique solution of the Bellman equation exists, a consequence of the fixed-point theorem (Smart 1980). Therefore, the optimal value function of an MG-SPA exists under Assumption 4.4 By introducing (3), characterize the relationship bet the optimal value function and robust equilibrium. However, (3) does not imply the existence of RE. To this end, in (4), we formally establish the existence of RE when the optimal value function exists. We formulate a 2N-player Extensive-form game (EFG) (Osborne & Rubinstein 1994 Von Neumann & Morgenstern 2007) based on the optimal value function such that its Nash equilibrium (NE) policy is equivalent to an RE policy of the MG-SPA.
Theorem 4.7.
Suppose 0 S y < 1 and Assumption 4-4 holds.
(1) (Solution of Bellman equation) A value function u. E V is an optimal value function if for all E N, the point-wise value function vt E V satisfies the corresponding Bellman Equation (6 i.e. v, = LU..
(2) (Eristence and uniqueness of optimal volue function) There ezists a unique U. satisfying Lu. = U.. i.c. for all illic E N, L'v, =
(3) (Robust equilibrium and oplimal value function) A joint policy d. = (TT, where n. = (m.,..., m
and p. -pp.. (p_..... , ) is robust equilibrium if and only if wdh is the optimal value function.
(4) (Ezistence of robust equilibrium) There erists mized RE for an MG-SPA.
A specifically in A.3 We provide a high-level 1. Constructing an extensive-form game that is connected to an MG-SPA. 2. Proof of Theorem 4.7 Tn the first part, we begin by constructing an extensive-form game (EFG) whose payoff function is related to the value functions of an MG-SPA (Appendix A.I.. Using the EFG as a tool, we can analyze the properties of an MG-SPA. We provide insights into solving an MG-SPA by solving a constructed EFG: a robust equilibrium (RE) of an MG-SPA can be derived from a Nash equilibrium of an EFG when the EFG's s payoff function related to the optimal value function of the MG-SPA (Lemma A.7 in Appendix). Thus, by providing conditions under which Nash equilibrium of bell-constructed EFG exists (Appendix A.1.1]. 1, we can prove the existence of an RE of the MG-SPA (Theorem 4.7 (4)(4)). The existence of an optimal value function is not yet proven and is left for the second part. In the second part, we prove Theorem 4.7 (1) by showing that for all i, there exists a v² E V such that of > Lu', then o² 2 vt, and there also exists a v E V such that v² < Lo², then v < v.. Propositions 4.5 and 4.6 enable us to use Banach Fixed-Poine Theorem (Smart 1980 to prove Theorem 4.7 (2). The proof of Theorem (3) benefits from the definitions of the optimal value function and robust equilibrium, Theorem
Proof. The full proof of Theorem 4.7 is presented in Appendix
proof sketch here. Our proof consists of two main parts:
(1) and (2). Finally, given the existence of the optimal value function and the results from the first part, we prove the existence of an RF.
Though the existence of NE in stochastic game with perfect information has been investigated (Shapley 1953 Fink 1964), it is still an open and challenging problem when players have partially observable information Hansen et al.) 2004 Yang & Wang 2020a). There is a bunch of literature developing algorithms trying to find the NE in Dec-POMDS or partially observable stochastic game (POSG), and conducting algorithm analysis assuming that NE, exists (Chades et al., 2002 Hansen et al., 2004 Nair et al.) 2002) without proving the conditions for the existence of NE. Once established the existence of RE, we design algorithms to find it. In Section 5 we first develop robust multi-agent Q-learning (RMAQ) algorithm with a convergence guarantee, then propose a robust multi-agent actor-critic (RMAAC) algorithm to handle the case with high-dimensional state-action spaces.
8

---

Published in Transactions on Machine Learning Research (06/2023)
Remark 4.8 (Heterogeneous agents and adversaries). In the above problem formulation, we assume all agents have the same type of state perturbations (share one. f), and all adversaries have the same level of perturbation power (share one e), which made the notation more concise and the analysis more tractable. However, these assumptions are sometimes unrealistic in practice since agents/ hattt//dverrrrisss may have different capabilities. To introduce heterogeneous ogents and adversaries to an MG-SPA, we let each agent i has its own perturbation function f', and each adversary' has its own perturbation power constraint e', such that 3¹ = ['(,,b) E B(e², .)). We use f(s,,) = bb,,...)),........... perturbation function. When all perturbation functions f' -) are bijective for any fixed s E S, the joint perturbation function ((,-)) is also a bijection. Assumption 4-4 (4) still holds. When constructing an eatensive-form gume, the action set for player Pl is defined as S = B (E²,s) x (e( s) x .... x...B% (e" s) instead of S = B(e,,) x.... x B(e, 8). The subsequent proofs still hold and they are not affected by the introduction of heterogeneous agents and adversaries. After extending our MG-SPA framework to handle heterogeneous agents and adversaries, we can model more complex and realistic multi-agend systems.
= to denote the joint
Remark 4.9 (A reduced case of MG-SPA: a single-agent system). When there is only one agent in the system, the MG-SPA problem reduces to a single-agent robust RL problem with state uncertainty, which has been studied in the lilerature (Zhang et al.) 2020a 2021). In this case, single-agent robust RL with state uncertainty can be seen as specific and special instonce of MG-SPA presented in this poper. However, the proposed analysis and algorithm in this paper provide a new perspective and approach to single-agent robust reinforcement learning, by explicitly modeling the odversary's 's perturbations and oplimizing the agenl's 's policy against them in game-theorelic fromework. Moreover, the presence of muutiple agents and adversories in the system can result in more compler and challenging interactions, joint actions and policies that do not present in single-agent RL problems. Our proposed MG-SPA framework allows for the modeling of a wide range of agent interactions, including cooperalive, compelilive, and mixed interactions.
4.3 History-dependent- cecceppeennet--oiicy-eee policy-based based Robust Equilibrium
It is natural and desirable to consider history-dependent policies in robust MARL with state perturbations, since the agents may not fully capture the state uncertainty from the current state information, and a policy that only depends on the current state may not be sufficient for ensuring robustness. The history-dependent policy allows agents to take into account past observations when making decisions, which helps agents better reason about the adversarics' possible strategics and intentions. This is particularly true in the case of Dec-POMDPs and POSGs, where the agent cannot fully observe the state. Therefore, we further extend the cerer-deeeett-olliieeee volicy-based robust equilibrium and discuss Theorem 4.7 under history-dependent policies in this subsection. In Section 5. we also discuss how the proposed algorithms can adapt to historical state input. We further validate that outperforms Markov-policy-base RE in Section G
above taikkoo--poicy--bseee RE to a
perer-ddeeeeeee--oll------eeeeee RE
In this subsection, we clarify the gencralization steps of extending Markov-policy-based RE to history- pependeet-policy-bbseed RE. We first introduce the definition of history-dependent policy with a finite time horizon h in an MG-SPA. We then give the formal definition of a bistory-deeendden--olliyyy---- robust equilibrium. Finally, we show that Theorem 4.7 still holds when agents and adversaries adopt history-dependent policies.
We consider an MG-SPA with time horizon h, in which adversaries and agents respectively observe the states and perturbed states in the latest h time steps and adopt history-dependent policies. More concretely, adversary can manipulate the corresponding agent i's state at time t by using a histery-dependent policy Pi (-Ism)) and agent i chooses its actions using a history-dependent policy = (-13).)). Specifically, once adversary gets the true state s, at time t, it chooses an action b; according to a history-dependen, policy P SA + A(B"), where Sh.t = (st,,.. 11) E Sh is a concatenated state consists of the latest h time steps of states. According to a perturbation function f. adversary i perturbs state st to ड = f(e, bī) E S. The adversaries' joint policy is defined as Ph (b|sk) = Ili Pi, (s)).. Agent i chooses its action of for s%., = (5) ... (6t E S₁. with probability mf (a))))..) according to a history dependent policy mř Sp. - A(At). The agents' joint policy
9

---

Published in Transactions on Machine Learning Research (06/2023)
is defined as Ty (a(55) = ILE (a' Then joint history-dependent policy d,,* (Th,, Ph.x) where N.
WA, = (Th "y Th,s) and ph.+ (Ph...... .Ph.)) is said to be in a histor-ddpendee---ppli-----sssss robust equilibrium if and only for any i E E,
( T P Al 2 ( (8) 2 (5 1 Mi 1 Di (8).
It is worth noting that the main differences between distory-dependentt wwweeddeetttooiyy-eeeee policy-based REE. and Markov-policy- based RE are the definition and notation of policies and states. A Marrov-pplicy- based RE is a special case of history-dependent-ee peeeppendenn--olly-b-sseee
RE by adopting the time horizon h We also notice that these two REs' definitions are the same if we remove the subscript. h from the concatenated stale and history-dependent policies. Therefore, in this paper, we use notations without the time horizon subscripts, ie. Markov policy and Markov-policy-based RE, to avoid redundant and complicated notations. While in this subsection, we clarify the definitions of history-dependent policy and history-dapondent-poleey Theorem 4.7 still holds when agents and adversaries use history-dependent policies in the following corollary.
RE and show that
Corollary 4.9.1. Theorem 4-7 still holds when all agents and adversaries in an MG-SPA use history- dependent policies with finite time horizon.
Proof. See Appendix A.4
Remark 4.10 (MG-SPA, Dec-POMDP, and POSG). Decentralized Partially Observable Markov Decision Process (Dec-POMPP) enables team of agents to optimize policies with partial observable states Oliehook et ol.) 2016 Nair el al.) 2002), while Partially Observable Stochastic Game (POSG) et al. (004)) is an extension of stochastic games with imperfect information that can handle partial observable states. We are inspired by them to consider history- dependent policies for our proposed MG-SPA problem. However, there are several differences between MG-SPA, Dec- Dec-POMDP and POSG. Firsl, unlike Dee-POMDP, an MG-SPA does nol restrict all agents share the same interest or reword function. The proposed MG-SPA framework is applicable for modeling different relationships between agents, including cooperative, competitive, mixed interactions. Second, neither Dec-POMDP nor POSG considers the worst-case state perturbation scenarios. In contrast, in an MG-SPA, state perturbation adversaries receive opposite rewards to the agents, which motivates them. to find the worst-case state perturbations to minimize the agents' returns. As we explained in the introduction, considering worst-cas case state perturbations is important for MARL. Third, while a Dec-POMDP or a POSG, all agents cannot observe the true state information, in an MG-SPA, adversories can access the true state and utilize it select state perturbation actions. Based on these differences in yroblem formudation, Dec-POMDP and POSG methods cannot solve the proposed MG-SPA problem.
Hansen et ol. 2004;
5
Algorithm
5.1
Robust Multi-Agent Q-learning (RMAQ) Algorithm
By solving the Bellman equation, we are able to get the optimal value function of an MG-SPA as shown in Theorem 4.7 We therefore develop value iteration (VI)-based method called robust multi-agent Q-learning (RMAQ) algorithm. Recall the Bellman equation using action-value function in (5) the optimal action-
value qu satisfies gi (s, b) == (s, a, b) + >E [Eves p(s' (iss'|s, a, b)g (s', "','a' d')b')aa' m. (-3'),, p+(-s")) As consequence, the tabular- RMAQ update can be written as below,
d (S1, 01, bx) (1 -
bi)+
(7)
ri t Σ Σ
a
where (n (.:)) is an NE policy by solving the 2N-player extensive-form game (EFG) based on payoff
function (Φ) ....... o6 ao: . - y.²). The joint policy (m ) is used in updating gt- All related definitions
10

---

Published in Transactions on Machine Learning Research (06/2023)
of the EFG (g).... ..""...""""""""""""""".. -
-4 are introduced in Appendix A.1 How to solve EFG is out of the scope of this work, algorithms to do this exist in the literature (Cermák et al. 2017: Kroer et al. 2020). Note that, in RMAQ, each agent's is policy is related to not only its own value function, but also other agents' value function. This multi- cootti-dppedenncy structure considers the interactions between agents in a game, which is different from the Q-learning in single-agent RL that considers optimizing its own value function. Meanwhile, establishing the convergence of multi-agent Q-lcarning algorithm is also a general challenge. Therefore, we try establish the convergence of (7) in Theorem 5.2] motivated from Hu & Wellman (000).. Due to space limitation, in Appendix B.1 prove that RMAQ is guaranteed to get the optimal value function
q. = (g., , by updating
:. (q"") recursively using (7) under Assumptions 5.1
Assumption 5.1.
(1) State and oction pairs have been visited infinitely often. (2) The learning rate as satisfies the following conditions: 0 S Ot < <1, Eizg of { oa; (s, (,,,,b) # (8t; Oes be), as(8, a, =0. 0. (3) An NE of the 2N- -layer EFG based on (q:, " ah -q.
.... ) exists at each iteration t.
Theorem 5.2.
Under Assumption 5.1 the sequence {gt} obtained from converges to {q-} with probability 1, which are the optimal value functions that salisfy Bellman equalions (5) for all i 1, N.
Assumption 5.1 111 is a typical ergodicity assumption used in the convergence analysis of Q-learning Littman & Szepesvári 1996 Hu & Wellman 2003 Szepesvári & Littman 1999 Qu & Wierman 2020 Sutton & Barto 1998). And for Q-lcarning algorithm design papers that the exploration property is not the main locus, this assumption is also a common assumption (Fujimoto et. al. 2019 For exploration strategies in RL
McFarlane
2018). researchers use e-greedy exploration (Gomes & KKowllzyk] 2009). UCB (Jin al. 2018
Azar et al.
2017), Thompson sampling (Russo et al. 2018 Boltzmann exploration Cesa-Bianch et al. For assumption 5.1 (3) in multi-agent Q-learning, researchers have found that the convergence is not necessarily so sensitive to the existence of NE for the stage games during training (Hu & Wellman 2003: Yang et al. 2018). In particular, under Assumption 4.4 an NE of the 2.N-player EFG exists, which has been proved Lemina A.6 in Appendix AA.1 We also provide an example in the experiment part (the two-player game) where assumptions are indeed satisfied, and our RMAQ algorithm successfully converges to an RE of the corresponding MG-SPA.
2017), etc.
5.2 Robust Multi-Agent Actor-Critic (RMAAC) Algorithm
According to the above descriptions of a tabular RMAQ algorithm, each learning agent. has to maintain N action-value functions. The total space requirement is N | |B] if |A'|| =... = |A | |B This space complexity is lincar in the number of joint states, polynomial in the number of agents' joint actions and adversaries' joint actions, and expouential in the number of agents. The computational complexity is mainly related algorithms to solve an aatensive-form game (Cermák al. 2017 Kroer et al. 2020
However, even for general-sum normal-form games, computing an NE known to be PPADDcomplete,, which is still considered difficult in game theory literature (Daskalakis al. 2009 Chen et al. 2009 Etessami &
Yannakakis 2010). These properties of the RMAQ algorithm motivate us to develop an actor-critic method to handle hign-dimensional space-action spaces, which can incorporate function approximation into the update KKnda & Tsitsiklis 1999).
We consider each agent i's policy n² is parameterized as Thi for i E W, and the adversary's policy o is parameterized as Pai. We denote 0 = (0-,... 0NV) as the concatenation of all agents' policy parameters, w has the similar definition. For simplicity, we omit the subscript 6, wi, since the parameters can be identified by the names of policies. Then the value function (s(s) under policy (a, satisfies
(s) = Eawxxbru Σ plslss, a 5 (i
(8)
LEES
11

---

Published in Transactions on Machine Learning Research (06/2023)
We establish the general policy gradient with respect to the parameter 8, in the following theorem. Then we propose our robust multi-agent actor-critic algorithm (RMAAC) which adopts a centralized-trainiggg decentralizeed-execatii algorithm structure in MARL literature (Lowe et al. 2017 Foerster et al. 2018
Theorem 5.3 (Policy Gradient in RMAAC for MG-SPA). For each agent i E N and adversory i M, the policy gradients of the objective J'(O,w) w) with respect to the parameter 0, w are:
(0,) = ((a [4 (s a, V log x (a (a'13')]
(9)
(0,)) = R((aa)))pis ( (s, w log (6² (s) + reg)
(10)
where reg- = Poloog X (a" (
Proof. See details in Appendix B.2.1
We put the pseudo-code of RMAAC in Appendix B.2.3
Remark 5.4 (eeester-ddependeent Policy). RMAAC can calculate history-dependent policies by using recent observations as the policy input. For example, DQN (Mnih et al., [2015] maps history-action pairs scalor estimates of Q-value. It uses the history (4 most recent frames) of the states and the action as the inputs of the neural network.
6 Experiment
We aim to answer the following questions through experiments: (1) Can RMAQ algorithm find RE? (2) Are RE policies robust to state uncertainties? (3) Does RMAAC algorithm outperform other MARL and robust MARL algorithms in terms of robustness? The host machine used in our experiments is server configured with AMD Ryzen Threadripper 2990WX 32-core processors and four Quadro RTX 6000 GPUs. All experiments are performed on Python 3.5.4, Gym 0.10.5, Numpy 1.14.5, Tensorflow 1.8.0, and CUDA 9.0. rrouust marl, with state caatte_uncettaitty
Our code is public on
6.1 Robust Multi-Agent Q-learning (RMAQ)
We show the performance of the proposed RMAQ algorithm by applying it to two-player game. We first introduce the designed two-player game. Then, to answer the first and second questions, we investigate the convergence of this algorithm and compare the performance of robust equilibrium policics with other agents' policies under different advessrries policies.
Two-player game: For the game in Figure 3 two players have the same action space A = {0, 1] and state space S {80, 81}. The two players get the same positive rewards when they choose the same ac- tion under state so or choose different actions under state 81. The state does not change until these two players get positive reward. Possible Nash equilib- rium (NE) in this game can be कं (mt mf) that player always chooses action 1, player 2 chooses action 1 under state so and action 0 under state s1i or π = (ml) m²) that player 1 always chooses action 0, player 2 chooses action 0 under state 8o and action under state 81. When using the NE policy, these two players always get the same positive rewards. The optimal discounted state value of this game is of (s) = 1/(1 -7) for all E S,i (1,2), 7 is the reward discounted rate. We set 7 0.99, then (s) 100.
a a
al # a r
a = a² r 0
SO
$1
a' # a² =
Figure 3: Two-player game: each player has two states and the same action set with size 2. Under state 80, two players get the same reward 1 when they choose the same action. At state 81, two players get the same reward 1 when they choose different actions. One state switches to another state only when two players get reward.
12

---

Published in Transactions on Machine Learning Research (06/2023)
MG-SPA formulation for the two-player game: According to the definition of MG-SPA, we add two adversaries, one for each player to perturb the state and get a negative reward of the player. They have the same action space B = {0, 1}, where 0 means do not disturb, 1 means perturb the observed state to another one. Sometimes no perturbation would be a good choice for adversaries. For example, when the true state is B0, players are using æi, if adversary does not perturb player I's observation, player 1 will still select action 1. While adversary 2 changes player 2's observation to state 81, player 2 will choose action 0 which is not the same player I's action 1. Thus, players always fail the game and get no rewards. A robust equilibrium for MG-SPA would be d (#t,, #3 p1. P.) that each player chooses actions with equal probability and do adversaries. The optimal discounted state value of corresponding MG-SPA is (s) 1/2(1 7) for all E i, E 2 when players use robust equilibrium (RE) policies. We use = 0.99, then ū (s) 50. For more explanations of this two-player game and corresponding MG-SPA formulation, please see Appendix C.1
Implementing RMAQ on the two-player game: We initialize q' (s, a, b) = q² a, b) = 0 for all 8, a, After obscrving the current state, adversarics choose their actions to perturb the agents' state. Then players execute their actions based on the perturbed state information. They then observe the next state and rewards. Then every agent updates its according to (7). In the next state, all agents repeat the process above. The training stops after 7500 steps. When updating the Q-values, the agent applics NE policy from the eetensive-form game based on g"".
Training results: After 7000 steps of training, we find that agents' Q-values stabilize at certain values. Since the dimension of q is a bit high as Q E 3R compare the optimal state value 8.
Total Discounted Rewards
discounted rewards
and the total discounted rewards in Table M The
value of the total discounted reward converges to the optimal state value of the corresponding MG-SPA. This two-player game experiment result validates the convergence of our R.AQ method and the answer
RE
NE
to the first question is 'Yes..
10
BS
Testing results: We further test well-trained RE policy when 'strong' adversaries exist. 'Strong' adversary means its probability of modifying play- ers' observations is larger than the probability of no perturbations in the state information. We make two players play the game using different poli- cies for 1000 steps under different adversaries. The accumulated rewards and total discounted rewards are calculated. We use the robust equilibrium (of the MG-SPA), the Nash equilibrium (of the original game), and a baseline policy (two players use deter- ministic policies) and report the result in Figure 4 The vertical axis the accumulated/ cruumllaedd/discouttee discounted re-
0.45
550
06
0.7
0.75
08
085
0.9
0.5
attack probability
Total Rewards
500
total rewards
400
300
RE
NE
ward, and the horizon axis is the probability that the adversary will attack/ attack/perturb perturb the state. And we let these two adversaries share the same policy. We can see as the probability increase, the accumulated and discounted rewards of RE players are stable but those rewards of NE players and baseline players keep decreasing. These experimental results show that the REE. policy is robust to state uncertainties. It turns out the answer to the second question "Yes" well.
100
BS
0.5
0.55
06
775
80
50
09-
0.5
attack probability
Figure 4: RE policy outperforms other policies in terms
of total discounted rewards and total accumulated re- wards when strong state uncertainties exist.
Discussion:
Even for general-sum normal-form games, computing NE is known to be PPAD-complete, which is still considered difficult in game theory literature (Conitzer & Sandholm 2002 Etessami & Yannakakis
13

---

Published in Transactions on Machine Learning Research (06/2023)
Table 1: Convergence Values of Total Discounted Rewards when Training Ends
v ('()
(50)
v ('1)
(51)
(10)
(5))
(11)
(5)
value 49.99
49.99
49.99
49.99
50.00
50.00
50.00
50.00
2010).
Therefore, we do not anticipate that the RMAQ algorithu can scale to very large MARL problems. In the next subsection, we show RMAAC with function approximation can handle large-scale MARL problems.
6.2 Robust Multi-Agent Actor-Critic (RMAAC)
To answer the third question, we compare our RMAAC algorithm with two benchmark MARL algorithms: MADDPG
(Lowe et al. 2017) which does not consider robustness, (Li et al. 2019). a robust MARL algorithm
and M3DDPG (attps:// com/ htdmm/taaaddddddddaddaaaap which considers uncertainties from opponents' policies altering. M3DDPG utilizes adversarial learning to train robust policies. We run experiments in several benchmark multi-agent scenarios, based the multi-agent partiele environments (MPE) (Lowe et al. 2017). The hyper-parameters used to train RMAAC and the baseline algorithms are summarized in Appendix C.2.2. Table
Experiment procedure: We first train agents' policies using RMAAC, MADDPG and M3DDPG, respectively. For our RMAAC algorithm, we set the constraint parameter = 0.5. And we choose two types of perturbation functions to validate the robustness of trained policies under different MG-SPA models. The first one is the linear noise format that bs) random noise b² generated by adversary to the true state 8. And f2 b²) == & + Gaussian(b', E), where the adversary i's action b is the mean of the Gaussian distribution. And Σ is the covariance, we set it as I, i.e an identity matrix. We call it Gaussian noise format. These two formats f1, f2 are commonly used in adversarial training (Creswell al. 2018: Zhang et al. 2020a 2021). Then we test the well-trained policies in the optimally disturbed enviromment (injected noise is produced by those adversaries trained with RMAAC algorithm). The testing step is chosen 10000 and each episode contains 25 steps. All hyperparameters used in experiments for RMAAC, MADDPG and M3DDPG are attached in Appendix C.2.2 Note that since the rewards are defined as negative values in the used multi-agent environments, we add the same bascline (100) to rewards for making them positive. Then it's easier to observe the lesting results and make comparisons. Those used MPE scenarios are Cooperative communication (CC), Cooperative navigation (CN), Physical deception (PD), Predator prey (PP) and Keep away (KA). The first two scenarios are cooperative games, the others are mixed games. To investigate the algorithm performance in more complicated situations, we also run experiments in scenario with more agents, which is called Predator prey+ (PP+). More details of these games are in Appendix C.2.1
+ b', i.c. the perturbed state s² is caleulated by adding a
In Figure 5 and Table 2 we report the mean episode testing rewards and variance of 10000 steps testing rewards, respectively. We will use mean rewards and variance for short in the following experimental report and explanations. In the table and figure, we use RM, M3, MA for abbreviations of RMAAC, M3DDPG and MADDPG, respectively. In Figure 5 the left. five figures are mean rewards under the linear noise format fI, the right ones are under the Gaussian noise format f2. Under the optimally disturbed environment, agents with RMAAC policies get the highest mean rewards in almost all scenarios matter what noise format is used. The only exception is in Keep away under linear noise. However, our RMAAC still achieves the highest rewards when testing in Keep away under Gaussian noise. In Figure 7 we show the comparison results in a complicated scenario with a larger number of agents and RMAAC policies are trained
Experiment results:
Lineer Noiee 25.5 165
2055
Linear
Linear
Gaussian Noise 2y
Gaussian Noie an
102 Gaussian Neise
Gaussion Nose
9L Gausstan Noiso
Hean Eptodd Testig Sewards
8M
131
Mean Epioode lesting Howords ds 2
Hewn Eproode Testing Rewards
Mean Epiood Resting Rewords
505.
MA
42.5
36.3
204.5
03.0
99.6
306.0
Weeen Eppounte Ted
62.0
Hewe Eyonnd erg
62.3
x
Mean Eproodt Testing
90.23
394.5
83.0
2019
a0.r3
09.50
Mean
10.5
32.5
202.5
72.
CD
32.8
CN
302.8
PD
68.0
KA
PP
CC
CN
300
PD
KA
06.00
PP
Figure 5: RMAAC outperforms baseline MARL algorithms in terms of mean episode testing rewards under different perturbation functions in most MPE scenarios.
14

---

Published in Transactions on Machine Learning Research (06/2023)
Cleaned Env
Cleaned Env
Cleaned Env
Cleaned Env
Cleaned Env
100.0
120
RM1
RM1
RM1
RMI
RM1
Mean Episode Testing Rewards
RM2
Mean Episode Testing Rewards
RM2
Mean Episode Testing Rewards
RM2
Mean Episode Testing Rewards
97.5
RM2
Mean Episode Testing Rewards
110
RM2
112
MB
MA
MA
MA
95.0
MA
100
MA
92.5
90
108
50
106
45
104
85.0
75-
82.5
70
100
80.0
40
CC
CN
PD
KA
PP
Figure 6: Comparison of mean episode lesting rewards using different algorithms and different perturbation functions, under cleaned environments.
with the Gaussian noise format f2- As we can see that the RMAAC policies get the highest reward when testing under optimally perturbed environments, cleaned and randomly perturbed environments. Higher rewards mean agents are performing better. It turns out RMAAC policies outperform the other two baseline algorithms when there exist worst-case state uncertainties. In Table 2 the left three columns report the variance under the linear noise format fI, and the right ones are under the Gaussian noise formal /2- RM1 denotes our RMAAC policy trained with the linear noise format f1, RM2 denotes our RMAAC policy trained with the Gaussian noise format f2. The variance is used to evaluate the stability of the trained policies, the robustness to system randomness. Because the testing experiments are done in the same environments that initialized by different random seeds. We get the lowest variance in most scenarios under these two different perturbation formats. Therefore, our RMAAC algorithm is also more robust to the system randomness, compared with the basclines. In summary, our answer to the third question is YYes!.
that, by using RMAAC algorithm, the agents
Interesting results when testing under lighter perturbations and cleaned environments: We also pro- vide the testing results under cleaned en- viromment (accurate state information be attained) and randomly disturbed environment (injecting standard Gaussian noise into agents' obscrvations). In Fig- ures and we respectively show the comparison of mean episode testing re- wards under cleaned environment and randomly disturbed environment by us- ing 4 different methods: RM1 denotes our RMAAC policy trained with the lin- car noise format f1, RM2 denotes our RMAAC policy trained with the Gaussian noisc format f2, MA denotes MADDPG, M3 denotes M3DDPG. We can see that only in the Predator prey scenario, method outperforms others under cleaned environment. In Figure can see that our method outperforms others in the Cooperative communication, Keep away and Predator prey scenarios, and achieves similar performance as others in the Cooperative navigation scenario under a randomly perturbed environment.
Optimally Perturbed Env
Cleaned Env
Rangomly Perturbed Env
RM
RM
RM
Mean Episode Testing Rewards
86
Mean Episode Testing Rewards
Mean Episode Testing Rewards
84.0
MA
MA
MA
87
83.5
86
83.0
86
85
82.5
84-
82.0
83
81.5
82
82
83.0
80
80
80.0
PP+
PP+
PP+
Figure RMAAC outperforms baseline MARL algorithms in terms of mean episode testing rewards in complicated scenarios with a larger number of agents of MPF.
This kind of performance also happens robust optimization [Beyer & Sendhoff 2007 Boyd & Vandenberghe 2004) and distributionally robust optimization (Delage & Ye 2010 Rahimian & Mchrotra, 2019 Miao et al, 2021
He et al.] 2020 2023) where the robust solutions outperform other non-robust. solutions in the worst-case
15

---

Published in Transactions on Machine Learning Research (06/2023)
Randomly Perturbed Randomly Perturbed Env
Randomly Perturbed Env Ragdomly Perturbed Env Randomly Perturbed Env
Mean Episode Testing Rewards
90
RM1
RMZ
Mean Episode Testing Rewards
48
RMI
Mean Episode Testing Rewards
RML
RM2
Mean Episode Testing Rewards
RM1
RM4
Meant Episode Testing Rewards
110
RM1
85
MB
MB
108
MS
M3
M3
46
MA
89
MA
100
MA
80-
106
88
90
75-
42-
104
80
70-
86
102
65
30-
CC
CN
PD
KA
PP
Figure 8: Comparison of mean episode testing rewards using different algorithms and different perturbation
functions, under randomly perturbed environments.
Table 2: Variance of Testing Rewards under optimal perturbed environment
Perturbation function
Linear noise Ji
Gaussian noise /2
Algorithms
RM1
M3
MA
R.M2
M3
MA
Cooperative communication (CC)
1.007
1.311
1.292
0.872
1.012
0.976
Cooperative navigation (CN)
0.322
0.357
0.351
0.322
0.349
0.359
Physical deception (PD)
0.225
0.218
0.217
0.244
0.161
0.252
Keep away (KA)
0.161
0.168
0.175
0.161
0.17
0.167
Predator prey (PP)
3.213
0.161
3.671
2.304
2.711
2.811
scenario. Similarly, for single-agent RL with state perturbations, robust policies perform better compared with baselines under state perturbations (Zhang et al.) 2020b). However, there exists a trade-off between optimizing the average performance and the worst-case performance for robust solutions in general, and the robust solutions may get relatively poor performance compared with other non-robust. solutions when there is no uncertainty or perturbation in the environment even in a single agent RL problem (Zhang et al.) 2020b4. Improving the robustness of the trained policy may sacrifice the performance of the decisions when perturbations uncertainties do not happen. That's why RMAAC policies only beat all baselines in one scenario when the state uncertainty is climinated. However, for many real-world systems, we can not assume that agents always have accurate information about the states. Hence, improving the robustness of the policies is very important for MARL as we explained in the introduction. It is worth noting that our RMAAC policies also work well in environments with random perturbations instead of only the worst-case perturbations. As shown in Fig. g the performance of our RMAAC policies outperforms the basclines in most scenarios when random noise is introduced into the state.
More experimental results and explanations are provided in Appendix C.2
A Allaiion study: We conducted ablation studies for RMAAC algorithm. We first study the performance of RMAAC when it is used to train history-dependent policies. Other than using the current information as the input of the policy neural network, we also use history information in the latest three time steps, i.c. h = In Table g we show the mean and variance of mean episode rewards in 10 runs. We use the same hypee-parameters in training history-dependent policies as training Markov policies. We can that in
Table 3: Means and Variances of Mean Episode Rewards using Different Polices
Scenarios
History-dependent policy
Markov policy
Cooperative communication (CC)
-52.83 1.51
-54.75 3.03
Cooperative navigation (CN)
-208.19 + 1.68
-210.41 + 1.13
Physical deception (PD)
7.72 = 0.33
5.71 = 0.19
Keep away (KA)
-20.69 + 0.09
-21.18 + 0.14
Predator prey (PP)
7.10 + 0.17
6.116 + 0.24
16

---

Published in Transactions on Machine Learning Research (06/2023)
all five scenarios, history-dependent policies outperform Markov policies. Besides, investigate how the robustness performance of RMAAC is affected by varying variances of Gaussian noise format. Σ and the constraint parameter e. We also investigate the performance of RMAAC under other types of attacks. Please check the experimental sctups and results of these ablation studics in Appendix C.3
7 Discussion
Our proposed method provides foundation for modeling robust agents' interactions in multi-agent reinforce- ment learning with state uncertainly, and training policies robust to stale uncertainlies in MARL. However, there are still several urgent and promising problems to solve in this field.
First, exploring hetcrogencous agent modeling is an important research direction in robust MARL. Training a team of heterogeneous agents to learn robust control policies presents unique challenges, as agents may have different capabilities, knowledge, and objectives that can lead to conflicts and coordination problems (Lin et al. 2021). State uncertainty can exacerbate the impact of these differences, as agents may not be able to accurately estimate the state of the environment predict the behavior of other agents. All of these factors make modeling heterogeneous agents in the presence of state uncertainty a challenging problem.
Second, investigating methods for handling continuous state and action spaces can benefit both general MARL problems and our proposed method. While discretization is a commonly used approach for dealing with continuous spaces, is not always an optimal method for handling high-dimensional continuous spaces, espocially when state uncertainty is present. Adversarial state perturbation may disrupt the contimuity on the continuous state space, which can lead difficulties in finding globally optimal solutions using general discrete methods. This is because continuous spaces have infinite possible values, and discretization methods may not be able to accurately represent the underlying continuous structure. When state perturbation occurs, it may lead to more extreme values, which can result in the loss of important information. We will investigate more on methods for continuous state and action space robust MARL in the future.
8 Conclusion
We study the problem of multi-agent reinforcement learning with state uncertainties in this work. We model the problem as Markov game with state perturbation adversaries (MG-SPA), where each agent aims to find out a policy to maximize its own total discounted reward and cach associated adversary aims to minimize that. This problem is challenging with little prior work on theoretical analysis or algorithm design. We provide the first attempt at theoretical analysis and algorithm design for MARL. under worst-case state uncertainties. We first introduce robust equilibrium as the solution concept for MG-SPA, and prove conditions under which such an equilibrium exists. Then we propose a robust multi-agent Q-learning algorithm (RMAQ) find such an equilibrium, with convergence guarantees under certain conditions. We also derive the policy gradients and design robust multi-agent actor-critic (RMAAC) algorithm to handle the more general high-dimensional state-action space MARL problems.. We also conduct experiments that validate our methods.
Acknowledgments
Sihong He, Songyang Han, Sanbao Su and Fei Miao are supported by the National Science Foundation under Grants CNS- 1952099,,,6, CMMI-1932250, and CNS-2047354 grants. Shaofeng Zou is supported by the National Science Foundation under Grants CCF-2106560, and CCF-2007783.
This material is based upon work supported under the AI Research Institutes program by National Science Foundation and the Institute of Education Sciences, U.S. Department of Education through Award # 2229873 National AI Institute for Exceptional Education. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation, the Institute of Education Sciences, or the U.S. Department, of Education.
17

---

Published in Transactions on Machine Learning Research (06/2023)
References
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pp. 263 272. PMLR, 2017.
Tamer Başar and Geert Jan Olsder. Dynamic noncooperative game theory. SIAM, 1998.
Hans- Hans-Georg Beyer and Beruhard Sendhoff. Robust optimization a comprehensive survey. Computer methods in applied mechanics and engineering, 396(33-34):3190 3218, 2007.
Stephen Boyd and Lieven Vandenberghe. Conver Optimization. Cambridge University Press, USA, 2004. ISBN 0521833787.
Jifí Cermák, Branislav Bošansky, and Viliam Lisy. An algorithm for constructing and solving imperfect recall abstractions of large extensive-form games. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, pp. 936-942, 942, 2017.
Nicolò Cesa-Bianchi, Claudio Gentile, Gábor Lugosi, and Gergely Neu. Boltzmann exploration done right. Advances in neural information processing systems, 30, 2017.
Iadine Chades, Bruno Scherrer, and François Charpillet. A hcuristic approach for solving decentralized-ponde Assessment on the pursuit problem. In Proceedings of the 2002 ACM symposium on Ayplied compuling, pp- 57-62, 2002.
Xi Chen, Xiaotie Deng, and Shang-Hua. Teng. Settling the complexity of computing two-player nash equilibria. Journal of the ACM (JACM), 56(3):1 57, 2009.
Xinning Chen, Xuan Liu, Canhui Luo, and Jiangjin Yin. Robust multi-agent reinforcement learning for noisy environments. Peer-to-Peer Networking and Applications, 15(2):1045-1056 2022.
Vincent Conitzer and Tuomas Sandholm. Complexity results about nash equilibria. ar Xiu preprint cs/0205074, 2002.
Antonia Creswell, Tom White, Vincent Dumoulin, Kai Arulkumaran, Biswa Sengupta, and Anil A Bharath. Generative adversarial networks: An overview. IEEE Signal Processing Magazine, 35(1):53-65, 65, 2018.
Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitrion. The complexity of computing a nash equilibrium, SIAM Journal on Computing, 39(1):19552))) 259, 2009.
Erick Delage and Yinyu Ye. Distributionally robust optimization under moment uncertainty with application data-driven problems. Operations Research, 58(3):595 -125099--61666 2010. doi: 10.1287/0prc.10000077
Jay L Devore, Kenneth N Berk, and Matthew A Carlton. Modern mathematical statistics with applications, volume 285. Springer, 2012.
Rosemary Emery-Montemerlo, Geoff Gordon, Jeff Schneider, and Sebastian Thrun. Approximate solutions for partially observable stochastic games with common payoffs. In Proceealings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, 2004. AAMAS 2004., pp. 136 143. IEEE, 2004.
Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Vlad Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, et al. Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures. In ICML, pp. 1407-1416. PMLR, 2018.
Kousha Etessami and Mihalis Yannakakis. On the complexity of nash equilibria and other fixed points. SIAM Journal on Computing, 39(6):2531 2597, 2010.
Michael Everett, Björn Lütjens, and Jonathan P How. Certifiable robustness to adversarial state uncertainty in deep reinforcement learning. IEFF Transactions on Neural Networks and Learning Systems, 2021.
18

---

Published in Transactions on Machine Learning Research (06/2023)
Arlington M Fink. Equilibrium in stochastic n-person game. Journal of science of the hiroshima university, series oi (mathemalics), 28(1):89-98) 93, 1964.
Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Coun- terfactual multi-agent policy gradients. In Proceedings of the AAAT conference on artificial intelligence, volume 32, 2018.
Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. In International conference on machine learning, pp. 2052 2062. PMLR, 2019.
Eduardo Rodrigues Gomes and Ryszard Kowalezyk. Dynamic analysis of multiagent q-learning with epsilon- greedy exploration. In ICML '09: Proceedings of the 26th international Conference on Machine Learning, volume 47, 2009.
Eric A Hansen, Daniel S Bernstein, and Shlomo Zilberstein. Dynamic programming for partially observable stochastic games. In AAAL, volume 4, pp. 709-7717100 2004.
Sihong He, Lynn Pepin, Guang Wang, Desheng Zhang, and Fei Miao. Data-driven distributionally robust electric vehicle balancing for mobillty-on-demand systems under demand and supply uncertainties. In 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 2165-2172. IEEE, 2020.
Sihong He, Yue Wang, Shuo Han, Shaofeng Zou, and Fei Miao. A robust and constrained multi-agent reinforcement learning framework for electric vehicle amod systems. arviv preprinl arXiv:2209.088: 2022.
Sihong He, Zhili Zhang, Shuo Han, Lynn Pepin, Guang Wang, Desheng Zhang, John A Stankovic, and Fei Miao. Data-driven distributionally robust electric vehicle balancing for autonomous mobility-on-deman systems under demand and supply uncertainties. IEEE Transactions on Intelligent Transportation Systems, 2023.
Junling Hu and Michael P Wellman. Nash q-learning for general-sum stochastic games. Journal of machine learning research, 4(Nov): 1069, 2003.
Yizheng Hu, Kun Shao, Dong Li, HAO Jianye, Wulong Liu, Yaodong Yang, Jun Wang, and Zhanxing Zhu. Robust multi-agent reinforcement learning driven by correlated equilibrium. 2020.
Sandy Huang, Nicolas Papernot, Ian Goodfellow, Yan Duan, and Pieter Abbeel. Adversarial attacks on neural network policies. arXiv preprint arXiv: 102..0220000 02284, 2017.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. q-leanning provably efficient?
Advances in neural information processing systems, 31, 2018
Leslie Pack Kaelbling, Michael L. Littman, and Anthony R. Cassandra. Plamning and acting in partially observable stochastic domains. Artificial Intelligence 101(1):99 134, 1998. ISSN 0004-3702. doi: https: (0tp://00000/000010000000000/)00 p11/S00043772980022x
URL htttp:://m/tt https://www.eiiencediaee
Vijay Konda and John Tsitsiklis. Actor-critic algorithms. Advances in neural information processing systems, 12, 1999.
Jernej Kos and Dawn Xiaodong Song. Delving into adversarial attacks on deep policies. ArXiv, abs/ 1105506652, 2017.
Christian Kroer, Kevin Waugh, Fatma Kiliç-Karzan and Tuomas Sandholm. Faster algorithms for extensive- form game solving via improved smoothing functions. Mathematical Programming, 179(1):385-417, 2020.
Mu Li, Tong Zhang, Yuqiang Chen, and Alexander J Smola. Efficient mini-batch training for stochastic optimization. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and dala mining, pp. 661-670, 2014.
19

---

Published in Transactions on Machine Learning Research (06/2023)
Shihmi Li, Yi Wu, Xinyue Cui, Honghua Dong, Fei Fang, and Stuart Russell. Robust multi-agent reinforcement learning via minimax deep deterministic policy gradient. In Proceedings of the AAAT Conference Arlificial Intelligence, volume 33, pp. 4213 4220, 2019.
Shiau Hong Lim and Arnaud Autef. Kernel-based reinforcement learning in robust markov decision processes. In International Conference on Machine Learning, pp.
PMLR, 2019.
Chendi Lin, Wenhao Luo, and Katia Sycara. Online connoctivity-awarc dynamic deployment for hetorogencous multi-robot systems. 2021 IEEE International Conference on Robolics and Automation (ICRA), pp- IEEE, 2021.
Jieyu Lin, Kristina Dzeparoska, Sai Qian Zhang, Alberto Leon-Garcia, and Nicolas Papernot. On the robustness of cooperative multi-agent reinforcement learning. In 2020 IEEE Security and Privacy Workshops (SPW), pp. 62-68. IEEE, 2020.
Yen-Chen Lin, Zhang-Wa Wei Hong, Yuan-Hong Liao, Meng-Li Shih, Ming- Yu Liu, and Min Sun. Tactics of adversarial atlack on deep reinforcement learning agents. In Proceedings of the 26th International Joinl Conference on Arlificial Intelligence, IJCAT'17, pp. 3756-3762. AAAT Press, 2017. ISBN 9780999241103,
Michael L Littman. Markov games as a framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pp. 157 163. Elsevier, 1994.
Michael L Littman and Csaba Szepesvári. A generalized reinforeement-leariing model: Convergence and applications. In ICML, volume 96, pp. 310-318. Citesoer, 1996.
Ryan Lowe, Yi I Wu, Aviv Tamar, Jean Harb, OpenAl Picter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-compelttie environments. Advances in neural information processing systems, 30, 2017.
Roger McFarlane. survey of exploration strategies in reinforcement learning. McGill Universily, 2018.
Richard D McKelvey and Andrew McLennan. Computation of equilibria in finite games. Handbook of computational economics, 1:87-142, 1996.
Fei Miao, Sihong He, Lynn Pepin, Shuo Han, Abdeltawab Hendawi, Mohamed E Khalefa, John A Stankovic, and George Pappas. Data-driven distributionally robust optimization for vehiele balancing of mobility-on- demand systems. ACM Transactions on Cyber-Physical Systems, 5(2):1 27, 2021.
Volodymyr Mnih, Koray Kavukcuoglu, et al. Human-level control through deep reinforcement learning. nature, 51877440):522 533, 2015.
Facundo Mémoli. Some properties of gronor-hausdorff distances. Discrete & Computational Geometry, pp. 1-25, 2012. ISSN 0179-5376. URL http://dx. doi 000000000000//000444-00--0000000 10.1007/s004544 012-9406-8.
R Nair, M Tambe, M Yokoo, D Pynadath, and S Marsella. Towards computing optimal policies for decentralized pomdps. In Notes of the 2002 AAAI Workshop on Game Theoretic and Decision Theoretic Agents, 2002.
John Nash. Non-cooperative games. Annals of mathematics, pp. 286-295, 1951.
Eleni Nisioti, Daan Bloembergen, and Michael Kaisers. Robust multi-agent lelaarning in cooperative games with adversaries. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
Frans A Oliehoek, Christopher Amato, et al. A concise introduction decentralized POMDPs, volume Springer, 2016.
Martin Osborne and Ariel Rubinstein. A course in game theory. MIT press, 1994.
Guillermo Owen. Game theory. Emerald Group Publishing, 2013.
20

---

Published in Transactions on Machine Learning Research (06/2023)
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programmingg. John Wiley & Sons, 2014.
Guannan Qu and Adam Wierman. Finite-time analysis of asynchronous stochastic approximation and q-learning. In Conference on Learning Theory, pp. 3105- PMLR, 2020.
Hamed Rahimian and Sanjay Mehrotra. Distributionally robust optimization: A review. arXiv preprint arXiv:1908.0500 2019.
Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, lan Osband, Zheng Wen, et A tutorial on thompson sampling. Foundalions and Trendso in Machine Lewrning, 11(1):1-00 96, 2018.
Burkhard C Schipper. Kuhn's theorem for extensive games with unawareness. Available at SSRN 3063853, 2017.
Lloyd Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(1)):1095 1100, 1953.
Macheng Shen and Jonathan P How. Robust opponent modeling via adversarial ensemble reinforcement learning. In Proceedings of the International Conference Automated Planning and Scheduling, volume 31, pp. 578-587, 2021.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, al. Mastering the game of go without human knowledge. nature, 550(7676) 359, 2017.
Aman Sinha, Matthew O O'Kelly, et al. Formulazero: Distributionally robust online adaptation via offline population synthesis. In ICML, pp. 8992 9004. PMLR, 2020.
B Slantchev. Game thoory: Perfect equilibria in extensive form games. UCSD script, 2008
David Roger Smart. Fized point theorems, volume 66. Cup Archive, 1980.
Houshang H Sohrab. Basic real analysis, volume 231. Springer, 2003.
Chuangchuang Sun, Dong-Ki Kim, and Jonathan P How. Romax: Certifiably robust deep multiagent reinforcement learning via convex relaxation. arXiv preprinl "xXi::219.066990 2021.
Richard S Sutton and Andrew G Barto. Reinforcement learning: an introduction mit press. Combridge, MA, 22447, 1998.
Richard S Sutton, Andrew G Barto, et al. Introduction reinforcement learning, volume 135. MIT press Cambridge, 1998.
Csaba Szepesvári and Michael L Littman. A unified analysis of value-function based reinforeement-leamiing algorithms. Newral compulation, 11(8):2017 2060, 1999.
Chen Tesslor, Yonathan Efroni, and Shie Mannor. Action robust reinforcement learning and applications in continuous control. In International Conference Machine Learning, pp. 6215 6224. PMLR, 2019.
Tessa van der Heiden, C Salge, Efstratios Gavves, and H van Hoof. Robust multi-agent reinforeement learning with social empowerment for coordination and communication. arXiv preprint arXiv:2012.0820 2020.
John Von Neumann and Oskar Morgenstern, Theory of games and economic behavior. In Theory of games and economic behavior. Princcton university press, 2007.
Yue Wang and Shaofeng Zou. Online robust reinforcement learning with model uncertainty, Advances in Neural Information Processing Systems, 34:7193 7206, 2021.
Yaodong Yang and Jun Wang. An overview of multi-agent reinforcement learning from game theoretical perspective. ArXio, h0s/2011000555 2020a.
21

---

Published in Transactions on Machine Learning Research (06/2023)
Yaodong Yang and Jun Wang. An overview of multi-agent reinforcement learning from game theoretical perspective. arXiv preprint or orXi::2011.0000 1000011.00000 1.00583, 2020b.
Yaodong Yang, Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang. Mean field multi-agent reinforcement learning. In International conference on machine learning, pp- 5571-5580. PMLR, 2018.
Zhengyu Yin, Dmytro Korzhyk, Christopher Kiekintveld, Vincent Conitzer, and Milind Tambe. Stackelberg vs. nash security games: interchangeability, equivalence, and uniqueness. In AAMAS, volume 10, pp. 6, 2010.
Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of ppo in cooperative, multi-agent games. arXiv preprinl wXXiv:2103.01955, 2021a.
Jing Yu, Clement Gehring, Florian Schäfer, and Animashree Anandkumar. Robust reinforcement learning: A constrained game-theorelic approach. In Learning for Dynamics and Control, pp. 1242-1253 PMLR, 2021b.
Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Mingyan Liu, Duane Boning, and Cho-Jui Hsieh. Robust deep reinforcement learning against adversarial perturbations state obscrvations. Advances in Neural Information Processing Syslems, 33:21024 21037, 2020a.
Huan Zhang, Hongge Chen, Duane Boning, and Cho-Jui Hsieh. Robust reinforcement learning on state observations with learned optimal adversary. arXie preprint arXiv:2101.08/ 08..0. 2021.
Kaiqing Zhang, Tao Sun, Yunzhe Tao, Sahika Gene, Sunil Mallya, and Tamer Basar. Robust multi-agent reinforcement learning with model uncertainty. Advances in Neural Information Processing Systems, 33: 10571 10583, 2020b.
22

---

Published in Transactions on Machine Learning Research (06/2023)
Appendix for " "Robust Multi-Agent Reinforcement Learning with State Uncertainty"
There are three sections in the appendix: section A for theoretical proof, section B for algorithms, and section
C for experiments.
A Theory
In this section, we give the full proof of all propositions and theorems in the theoretical analysis of an MG-SPA.
In section A.1 we construct an exlensive-form game (EFG) Başar & Olsder 1998 Osborne & Rubinstein
1994
Von Neumann & Morgenstern 2007) whose payoff function is related to value functions of an MG-SPA.
We then give certain conditions under which, a Nash equilibrium for the constructed EFG exists. In section
we prove the propositions and 4.6 In section
A.3 we give the full proof of Theorem 4.7 In section
prove Corollary 1.9.1 that Theorem applies to history-dependent- cewendeenttt-oiy--hee policy-based RF well.
To make the appendix self-contained, re-show the vector notations and assumptions we have presented in
section 4.2 Readers can also skip the repeated text and directly go to section A.1
We follow and extend the vector notations in Puterman (2014). Let V denote the set of bounded real valued functions on S with component-win partial order and norm || := supses (s)). Let VM denote the subspace of V of Borel measurable functions. For discrete state space, all real-valued functions are measurable that = Vas. But when S continuum, VM is a proper subset of V. Let v (u',...,," E V be the set of bounded real valued functions S x.... S, i.c. the across product of N state set and norm ||^|| :- supy || ||- We also define the set Q and Q in a similar style such that g² E &Q.e Q.
For discrete S, let [S] denote the number of elements in S. Let r denote a |S]-vector, with sth component r*()) which is the expected reward for agent under state And P the |S| x [S] matrix with (8, 8'th entry given by p(s'ls). We refer to rý as the reward vector of agent i, and Pa as the probability transition matrix corresponding to a joint policy d = (π, rá + yPad is the expected total one-period discounted reward of agent i, obtained using the joint policy d (T..)). Let 2 as a list of joint policy {d1, dy..... and
p0 I, we denote the expected total discounted reward agent using z as v 2 "d, +yPa, +... +>"=1 Pa, ... Pon_i ri, +.... Now, we define the following minimax operator which is used the rest of the paper.
Definition A.1 (Minimax Operator, same as definition 4.3)
For of E V, S, (P), where d = (s), ... I (s)). Then o is a [S)-wector, with sth component (s)
define the nonlinear operator It on v'(s) by Tir((s) = max, min min ..²). We also define the operator Lo(s) L() , , (s))
For discrete S and bounded r², it follows from Lemma 5.6.1 in Puterman 2014) that L'v E V for all vf V. Therefore Lv E V for all V. And in this paper, we consider the following assumptions in Markov games with state perturbation adversaries.
Assumption A.2 (Same assumption 4.4
(1) Bounded rewards; (r' a, 6) < M < M < oo for all E a A, be B and s E S.
(2) Finite state and action spaces: all S, A B are finûte.
(3) Stationary transition probability and reward functions.
(4) f(s.-) is a bijection for any fixed s = S.
(5) All agents share one common reward function.
23

---

Published in Transactions on Machine Learning Research (06/2023)
A.1 Extensive-form game
P1
$1
S $1$1
P2
a
a A
a
a A
Figure 9: team extensive-form game
An extensive-forny game (EFG) Başar & Olsder 1998 Osborne & Rubinstein 1994 Von Neumann &
Morgenstern 2007) basically involves a tree structure with several nodes and branches, providing an explicit. description of the order of players and the information available each player at the time of his decision.
Look at Figure 9] EFG involves from the top of the tree to the tip of one of its branches. And centralized nature player (P1) has |S] alternatives (branches) to choose from, whereas centralized agent (P2) has |A] alternatives, and the order of play is that the centralized nature player acts before the centralized agent does. The set A is the same as the agents' joint action set in an MG-SPA, set is set of perturbed states constrained by a constrained parameter e. At the end of lower branches, some numbers will be given. These numbers represent the playoffs to the centralized agent (or oquivalently, losses incurred the centralized nature player) if the corresponding paths are selected by the players. We give the formal definition of EFG will use in the proof and the main text follows:
, Definition A.3. An eatensive-foma game based on (v ... U.N. -ut,... ,., -...,, under E S is a finite free structure with:
1. A player P1 has action set 5 Bie, 8) x x B(e, with a typical element designed as 8. And P1 moves first.
2. Another player P2 has an action set A, with a typical element designed as a. And P2 which moves after P1.
3. A specific verter indicating the starting point of the game.
4. A payoff function gs (,(3,a) assigns a real rumber to each terminal vector of the tree. Player
(g) a).... ..... ................................ ge (5, a)) where g²(3,u) r's a, (5,,),)5+(()) +
Σ. ff PI gets (3, while player P2 gets g,)
5. A partition of the nodes of the tree into two player sets (to be denoted by Ño and N2 for P1 and P2, respectively).
6. A sub-partition of each player set No into information set {rg such that the same number of immediate branches emanates from every node belonging to the same information set, and no node follows another node in the same information set.
Note that fbb == f(s.b) (f(s,b',, b() the vector version of the perturbation function f in an MG-SPA. Since in an MG-SPA, a) ('ss, a.b) +E p(s'ls, a, (s)) for all 1,... NN, (3, fa (8)) well. We can also (q' ....... .g -t ,.. ") to denote extensive-
24

---

Published in Transactions on Machine Learning Research (06/2023)
form game based on (u', , respectively in the following definition.
Then we define the behavioral strategies for P1 and P2,
Definition A.4. (Behavioral strategy) Let I't denote the class of all information sets of Pi, with a typical element designed as nf'. Let U. denote the set of alternatives of Pi at the nodes belonging to the information set n²' Define U === -UY where the union is over Tf' E I'. Let Yp denote the set of all probability distributions on Upi, where the latter the set of all alternatives of P1 at the nodes belonging to the information set n'. Analogoushy, let Zna denote the set of all probability distributions on U- Further define Y ==upp Up yn, 7 = Up Zap. Then, a behavioral strategy X for P1 is a mapping from the class of all his information sets I' into Y, assigning that M(r²) E Yn for each n² E rt. A typical behavioral stralegy X for P2 is defined, analogously, a restricted mapping from 12 into Z. The set of all behavioral strategies for Pi is called his behavioral strategy set, and it is denoted by r
element in Y for each set in I', such
The information available to the centralized agent (P2) at the time of his play is indicated on the tree diagram in Figure g by dotted lines enclosing an area (i.e. the information set) including the relevant nodes. This means the centralized agent is in a position to know exactly how the centralized nature player acts. In this
case, a strategy for the centralized agent is a mapping from the collection of his information sets into the set of his actions.
And the behavioral strategy À for P1 is a mapping from his information sets and action space into probability simplex, i.e. A(āls) is the probability of choosing 8 given Similarly, the behavioral strategy X for P2 is x(a(3), i.e. the probability of choosing action when á is given. Note that every behavioral strategy is mixed strategy. We then give the definition of Nash equilibrium in behavioral strategies for EFG.
Definition A.5. (Nash equilibrium in behavioral stralegies) A pair of stralegies {). E E X. E [2] is said to constitute a Nash equilibrium in behavioral strategies if the following inequalities are satisfied that for all = I,... ,,, 1 x E 12, SES:
J' (x.
(11)
where J², x) the expected payoff i.e. Exx(gl] when P1 takes X, P2 takes X, A(5(s) = - (s1sss x(al3) = II 3*
In the following parts as well as the main text, when we mention a Nash equilibrium for an EFG, it refers Nash equilibrium in behavioral strategies. How to solve an EFG is out of our scope since it has been investigated in much literature (Başar & Olsder 1998 Schipper 2017 Slantchev] 2008). And policies X
and x" can be attained through the marginal probabilities calculation with chain rules (Devore et al. 2012
Mémoli 2012).
A.1.1 Existence of NE for an EFG
In Lemma A.6.
we give conditions (partial items of Assumption 4.4 under which an NE of the EFG based -...... Nv exists.
on (v),
Lemma A.6. Suppose 0² =.... = N.,, and S, A are finite. An NE (Ar, of the EFG based on (ul....,uu - ..., N) erists.
Proof. Since š is a subset of S, is finite when S is finite. When w = ... v and Š, A are finite, an EFG based on (u',.... N. -o?,...... ~ degenerates to a zero-sum two-person extensive-fone form game with finite strategies and perfect recall. Thus, an NE of this EFG exists (Başar & Olsder 1998 Schipper 2017
Slantchey 2008).
The following Lemma A.7 provides insights into solving an MG-SPA by solving a constructed EFG.
25

---

Published in Transactions on Machine Learning Research (06/2023)
Lemma A.7. Suppose f is a bijection when s is fized and an NE (x+, exists for on EFG (v',..,,
- We define joint policy (T" NE (Da:Xo) where P. (b|s) (3 fa(b)]s), (a fa(b) Xx (al3). Then the joint policy (T)
vA, , -
the joint policy implied from the
satisfics L'v (s) = r (T) (s) + + Exs P( (s') for all s S
Proof.
The NE of the extensive-form game (Az, X+) implies that for all -1 S have
J() 2 (Ae, X)),,,
where = f. E. p(s' a, f/ (
X(-Is), a x(-13) according to Definition A.5 Let b denote fo ($), because f is bijection when is fixed, f.(b) = (f,('))...,..((b)))) is bijection, and the inverse function (8) (Jz (3*), (3*),.. ... ~5- exists and is a bijection as well, then we have
x.) =E
r (s, a, 1 (B)) + Eu A1 x-()
EB
r (s, 6) + -uttsabtt(0)--AA1000)-------
r (s, + Σ p( 2
=B
Similarly, we have
J((),)) =E (s,
x2(1))
J(A,x=)= E (ss,,a + ())
T.(13)
where ,".p" pp are corresponding policics implied from behavioral stratogics x, 2, respectively. Recall the definition of the minimax operalor of L'))(s), we have, for all S,
() r'm p:) (8) + Σ Por (8')))))
e'ES
Based on the proof, we also denote (TT) as an NE policy for the EFG (ot.... V. -v² convenience, instead of calling it the joint policy derived from NE for the EFG (vl (vl.... N -bl, No.
NN for
We can get a corollary from Lemma A.7 that when optimal value functions of an MG-SPA exist, we are able to get a joint policy that satisfies the Bellman equations of the MG-SPA by computing an NE for a constructed EFG (....... .. -u. ... -u Later in Thcorem 4.7 we show that a joint policy that satisfics the Bellman equations of an MG-SPA in a robust equilibrium under Assumption 4.4 Therefore, Lemma
A.7 provides insights into solving an MG-SPA by solving a corresponding EFG.
In the following proof, we aim to prove the existence of optimal value functions for an MG-SPA under Assumption 4.4
26

---

Published in Transactions on Machine Learning Research (06/2023)
A.2 Proof of two propositions
Proposition A.8 (Contraction mapping, same as proposition 4.5 in the main text.). Suppose 0 2 < and Assumption 4.4 hold. Then L is contraction mapping on V.
Proof. Let u and v be in V. Given Assumption 4.4 these two EFGs ,u',... ,u,, N - uu .... -2 N)
( v., -v";" .... : --=") both have least one mixed Nash equilibrium according to Lemma A.6 And let (Th, and P.) be two Nash equilibriums for these two games, respectively. According Lemma A.7 have the following equations hold for all S,
L'v'(s) = (2 (5) + Σ P(
s'ES
L'u'(s) = (m (8) +7 Σ ((
s'ES
Then we have
o (1))0)(8)+7 +,
P(my (s S L'v0 L S ST (sz (7)
Σ (s
s'ES
$EE
((r (8) +y
Σ
P(oz (y (s'ls) S (s) S | (x))))) + Σ (6)))))()))))
s'ES
s'ES
since (T p and pt) are derived from the Nash equilibriur of the EFG (v and (T , p and (TT, p²)) are also derived from the Nash equilibrium of the EFG (u u ut N We assume that (s) (s), then we have
< LB (s)
(o + [(rrsooo6(()))u(ss) s'SS
(s) +7 ((rrnac661ss000 s'ES
$ Σ (s (s' (1 (s(') s'ES
< >l1|e* w''ll
Repeating this argument in the case that ('v S L'o implies that [s)=*(s) L' (s)]l S yllb* u'll
for all 8 E S, i.e. L is contraction mapping V. Recall that ||i|| = sup, || then we have
[L Lul| = sup || - Dw'll $ r ssup l| ul'l = =>/10- full-
L is a contraction mapping on V.
Proposition A.9 (Complete Space, same as proposition 4.6 in the main text.). V a complete normed linear space.
Proof. Recall that denote the set of bounded real-valued functions on S ... x S, Lee. the cross product of N state set with component-wer wise partial order and norm ||a|| := sup.es sup, (s)).. Since V closed under addition and scalar multiplication and is endowed with norm, it is normed linear space. Since every Cauchy sequence contains limit point in V, V is complete space.
J
27

---

Published in Transactions on Machine Learning Research (06/2023)
A.3 Proof of Theorem 4.7
In this section, our goal is lo prove Theorem 4.7 We first prove (1) the optimal value function of an MG-SPA satisfies the Bellman equation by applying the Squeeze theorem [Theorem 3.3.6, Sohrab (2003) in A.3.
Then we prove that a unique solution of the Bellman equation cxists using fixed-point theorem Smart 1980 in A.3.2 Thereby, the existence of the optimal value function gets proved. By introducing (3), we characterize the relationship between the optimal value function and robust equilibrium. The proof of (3) can be found in A.3.3 However, (3) does not imply the existence of an RE. To this end, in (4), we formally establish the existence of RE when the optimal value function exists. We formulate 2N-player Extensive-form game (EFG) (Osborne & Rubinstein 1994: Von Neumann & Morgenstern 2007 based on the optimal value function such that its Nash equilibrium (NE) is equivalent to an RE of the MG-SPA. The details are in A.3.
Theorem A.10 (Same as theorem 4.7 the main text).
Suppose 0 S y < 1 and Assumption holds.
(1) (Solution of Bellman equation) A value function v. E V is an optimal value function if for all i N, the point-wise value function vt, E V salisfies the corresponding Bellman Equation 16, iee. U, = Lu
(2) (Existence and uniqueness of optimal value fanction) There ezists a unique v. E V satisfyying Lue = Co. i.e. for all i E EN, L'v,
= v...
(3) (Robust equilíbrium and optimal value function) A joint policy d. (MT, where n. (mr m. and p- = (pi..... , ) robust equilibrium if and only if vd- is the optimal value function.
(4) (Existence of robust equilibrium) There evists a mized RE for on MG-SPA.
A.3.1 (1) Solution of Bellman equation
Proof. First, we prove that if there exists v² E such that v² > Lo then o² > of. of Lo implies of 2 max min fr + PPpp r + yPa' where d= (x"-- _ ud ;P= -p=- :p.')) is Nash equilibrium for the EFG == (u² ....... V -,, ,... ). We omit the superscript for convenience when there is no confusion. We choose list of policy i.e.
where dj (म my, .²².). Then we have
J¹ rd + Pa, 0² 2 rá, + Py (r', + uPp = ra + + r., + Pa
By induction, it follows that, for n 2 1,
ス rd + Pd r + +... 1m.. - Pa, ... Pa + + pm
x
0' v/ 2 7" " PT Σ n" ppyp
pl Tdd11
(12)
Since 11 "r"P"o'll olll $ | and 7 E [0, 1), for e > 0, we can find a sufficiently large n such that
ce/2 2 p 2 cce/2
(13)
where e denotes a vector of I's. And as a result of Assumption 4.4 (.4(1).
(1), we have
8
Me
2 plr d++1 > 1 7-7
(14)
Then we have
- o5(ss 2
(15)
28

---

Published in Transactions on Machine Learning Research (06/2023)
for all E S and O. Let all dj the same, since was arbitrary, we have
o²(s) 2 max min (s) (s)
(16)
Then we prove that if there exists a of E V such that vs Σ Lu then vf S v.. For arbitrary 6 > there exists joint policy d' = (T, m p.i, p²) and a list of policy = (d' .... such that
v¹ S r'v + tPax' te
- PPPPa r
(I 7 Par) -1 "yy + (1-1)) 7) oy + (1 7)- lec
$ v + (1 -7) ce
The equality holds because the Theorem 6.1.1 in Puterman 2014
Since e was arbitrary, we have
0² S v2
(17)
So if there exists of E V such that of L' i.e. o' S L'v' and of 2 L'v', we have of = v i.e. if of satisfies the Bellman equation, of is an optimal value function.
A.3.2 (2) Existence optimal value function
Proof. Proposition 4.5 and 4.6 establish that V is complete normed lincar space and L is contraction mapping, so that the hypothesis of Banach Fixed-Point Theorem are satisfied (Smart 1980). Therefore there exists a unique solution u. V to Lu = v. From (1), we know if satisfies the Bellman equation, it is an optimal value function. Therefore, the existence of the optimal value function proved.
A.3.3 (3) robust equilibrium and optimal value function
Proof. robust equilibrium - Optimal value function.
Suppose d' is robust equilibrium. Then yd = From (2), it follows that pd satisfies Lo Thus pd is the optimal value function.
(ii) Optimal value function > robust equilibrium.
Suppose nd is the optimal value function, i.e., =dd" The proof of (1) implies that pd u²; so d' is in robust equilibrium.
A.3.4 (4) Existence of robust equilibrium
Proof. From (2), we know that there exists a solution v, E V to the Bellman equation Lu = v. Now, we consider an EFG based on (ud,... v.Y, ...,... -w:²). Under Assumption 4.4 we can get an NE policy (TT",, ) ) by solving the EFG as a consequence of Lemma A.6 According to Lemma A.7 (TT pp")) satisfies
L'o = p:-)
- ) + Po (51)))))))))) stES
for all s S. According to (3), (TT ,p")) ) robust equilibrium.
29

---

Published in Transactions on Machine Learning Research (06/2023)
A.4 Proof of Corollary 4.9.1
Corollary A.10.1 (Same Corollary 4.9.1..
Theorem 4.7 still holds when all agents and adversaries in an MG-SPA use history-dependeer policies with a finite time horizon.
Proof. From subsection 4.3 can find the main difference wetneen histooryceeeemdem//poolyyy-sssss RE and Markor-policy-basee RE are the definitions and notations of policies and states. To prove Theorem 4.7 we construct an EFG based on the current state 8t. Similarly, to prove Corollary 4.9.1 we construct an EFG based on the concatenated stales 8h,t and 8/ -4-1,t-1 that includes the current state 8, and historical state information St-1,''. $t- ,
Notice that h is a finite number. Hence, the concatenated state space is still finite. We now construct another extensive-form game in which a centralized nature player (P1) has |S] alternatives (branches) to choose from, whereas centralized agent (P2) has |A] alternatives, and the order of play is that the centralized nature player acts before the centralized agent does. The set A is the same as the agents' joint action set in an MG-SPA, set is set of perturbed states constrained by a constrained parameter
Definition A.11. An extensive-form game based (v',...,,) , - under concatenated slates 8h,t = (st. 8t-h+1) E Sn. and 88,t-1 (St-1, bt)++ E Sh-1 is finile tree structure wilh:
1. A player Pl has action set $ = B(e, 8) x B(e, with a typicol element designed as 8. And P1 moves first.
2. Another player P2 has on action A, with a typical element designed as a. And P2 which moves after P1.
3. A specific verter indicating the starting point of the game.
4. A payoff function ( a) (g) a)), , (5, a)) where 8= =8 is the first element of Es p(s'la, (z)) assigns a real number to each terminal vector of the tree. Player P1 gets (9,(3,) a) while player P2 gets go(3,a).
Sh,t, $= 5, E $, g)( (s, (6))
5. A partition of the nodes of the tree into two player sets (to be denoted by Ñ and 2 for P1 and P2, respectively).
6. A sub-partition of each player set N into information set { such that the same number of immediate branches emanates from every node belonging to the same information set, and no mode follows another node in the same information set.
The definitions of behavioral strategy and Nash equilibrium keep the same. Then the behavioral strategy X for P1 is mapping from his information sets and action space into probability simplex, i.c. X(5|sh, (st,-.. ... ())) is the probability of choosing 5 given 8h.t- Similarly, the behavioral strategy x for P2 is i.e. the probability of choosing action when š4,6 is given.
X(a) = (3, " -
Now let us check the correctness Lemma A.6 when EFG is constructed following Definition A.11
We can
find that 5, finite state space for any finite time horizon since S₁ a product topology on finite spaces. Then Lemma A.6 still holds because the EFG degenerates to zero-sum two-person extensive- game with finite strategies and perfect recall.
A.7 We re-write it in Lemina A.12 in which the behavioral strategy x(a)ōn.)) and Then let us check Lemina (Z)8)))) are used. The proof of Lemma A.12 is similar to that of Lemma A.7
30

---

Published in Transactions on Machine Learning Research (06/2023)
Lemma A.12. Suppose f is bijection when 8 is fixed and an NE (Na,Xa) crists for EFG vb, NE (A.:X.), where (bbbs)) = A. fa(b)]sn), T. (a & -(-b+)))= (a(a) Then the joint policy (T2,, p.)) satisfies L'v'(s) pT) + P(r
(v',... , ,.",... --" We define joint policy (T=)p%) as the joint policy implied from the
for all
Proof. The NE of the fxtensive-form game (1,, implies that for all i 1, NE S we have
J(), 2 (A., J ()),
where J'(2, f, + E. a, ( X(1Isa), x(-1an] according to Defi-
nition A.5. Let denote (5), because is a bijection when fixed, [a(b) (J.(b)). ... sa(b²)) is a bijection, and the inverse function f=(($) (f. (3t) ... 1 exists and bijection well, then we have
Jr (A)) =R
(s, (s, (s,a, (100:)0)-00 (x(()n)
r (s, Xww.aaaaabbe)---000aa0aa01110000 Bl-
as) -00llaaatt(0----000
Similarly, we have
J'(A,,)) E
r' (s, pplslss. (s') p(((ssn) a x"(13))
J'Ax,a)=BB =E r's a, Ep(s'ls, a, b)b p0 (3(()s)) ~ (1(155))
where x². p" are corresponding policies implied from behavioral stratogics X. X, respectively, Recall the definition of the minimax operator of (s)) we have, for all S
(''((s) = rlme (s) + Σ (s
Proposition 4.6 still holds when agents and adversaries adopt history-dependent policies since we do not require Markov policies in the proof. Propositions 4.5 also holds which can be proved by utilizing the properties of NE for FFGs defined in Definition A.11 Specifically, in the proof, we use FFGs defined
Definition A.1I instead of Definition A.3 The subsequent proof of Propositions 4.5 keeps the same.
Then in the proof of Theorem the EFGs used in the proof are replaced by Definition A.11 The definition of the minimax operator does not constrain the type of policies. The propertics of the minimax operator be continually used well. The main body of proof keeps the same. Theorem 4.7 still holds when agents and adversaries adopt history-dependent policies.
we are able to continue utilize Propositions 4.6 and 1.5 Similarly,
31

---

Published in Transactions on Machine Learning Research (06/2023)
B
Algorithm
B.1 Robust multi-agent Q-learning (RMAQ)
In this section, we prove the convergence of RMAQ under certain conditions. First, let's recall the convergence theorem and certain assumptions.
Assumption B.1 (Same as assumption 5.1
(1) State and action pairs have been visited infinitely often. (2) The learning rate a, satisfies the following conditions: 0 S 0s < 1, E1z0 of S oo; if (s, a, b) + (8t, at, at, be), ar ar = O. (3) An NE of the EFG based on (g..... o/ q -
crists at each iteration t.
Theorem B.2 (Same theorem 5.2
Under Assumption B. the sequence {aet obtained from [8 converges to {q.} with probability 1, which are the optimal action-valte functions that satisfy Bellman equations (5) for all i 1, N.
1411 (a,,)b,) bb) = - (x)g a,, b,)+
(18)
0441.b441)) bet1)
rt + Σ
Σ
T. (b0
IE 111EB
Proof.
Define the operator
Tg. = T(y " , = (T ... g where the operator T defined as
below:
b) = = E Σ क (61))) (s'
(19)
d'EAYEB
for N, where (n p.*) is the tuple of Nash equilibrium policies for the EFG based on (gl: ... qf ..... q obtained from 18). Because of proposition B.3 and proposition B.4 the Lemma
in Hu & Wellman (2033
Corollary in Szepesvári & Littman [999 tell that 9t-1 (1 0z ) + a,Tq qu
converges to with probability 1.
Proposition B.3 (Contraction mapping).
Tq: T.NN contraction mapping.
Proof. We omit the subscript / when there is no confusion. Assume T'p² 2 T''', we have
5 T T
Σ Σ
25 2(d
Σ
EEEAEE
d'EAVEB
Σ Σ
Σ Σ
59
d'EANEB
d'EAVER
S9 S -g'll.
(20)
Repeating the case T < g" implies that 7 is contraction mapping such that 1T''p* - - S ~ for all p', q² E Q. Recall that 1p dll sup, I| - q²ll
[Tp Tall sup || p² T q0 S sup U|p' - q'll 71pp g gll
T' is contraction mapping such that 1Tp Tall S >lpp all for all p. E Q
32

---

Published in Transactions on Machine Learning Research (06/2023)
Proposition B.4 (A condition of Lemma in Hu & Wellman (2003) also Corollary 5 in Szepesvári & Littman 1999
q. TTq.
(21)
Proof.
E [[T =E r(s,,,,))+ +2 E Σ
d'EAMER
= as, +2 Σ p(s'ss,a,b)
Σ Σ
(01 d',
8'E8
d'EABEB
as,
(22)
Therefore q. [.]
33

---

Published in Transactions on Machine Learning Research (06/2023)
B.2 Robust multi-agent actor-critic (RMAAC)
In this section, we first give the details of policy gradients proof in MG-SPA and then list the Pseudo code of RMAAC.
B.2.1 Proof of policy gradients
Recall the policy gradient in RMAAC for MG-SPA in the following:
Theorem B.5 (Policy gradient in RMAAC for MG-SPA, same as the theorem 5.3). For each agent
i E N and adversary i E M, the policy gradients of the objective J6 w) with respect to the parameter 0, w are:
V (B, -(s.aM)p(a..) [q (s a, V log x [3]]
(23)
V (0,)) -E(s.aM))((r.)) (8 (s, b)l wi log (b) + regl]
(24)
where reg- = g. a' x (a 8 Vb. Vv
Proof. We first start with the derivative of the state value function on 0::
V (s)
o
ΣΣ (s
A
ΣΣ aEA BEB
x(d3))(()))) rls, a b)(" (::0)))++++++))) ((
Σ
V
b) (((B))p(b(s) v. Σ p(ss'sss a0)
(25)
We use 60h (s) to denote EaEA (aree/Vaa
a, b)]. We use pT - x, k) to denote the probability of transition from state to state z with agents' joint policy π and adversaries joint policy p after k steps. For example, p= s, k = 0) 1 and p= + s = 1) Eaes EeEB 7 ((b)))(( a, b). In the following proof, we sometimes use the superscript instead of i to denote adversary when there no confusion. Then we have:
(s)
+
Σ Σ
(als))p(bis)
Ep(s'ls p(s'|s, a, ()) YES ()
bEB
ΣΣX Σ
A bEB S'ES
(x) +
p (s 8 1
EES
(8) + Σ
p T- + 8111)
g (s') + Σ p 1 + ,,,1)
1) V) Ve
E5
*"ES
TT (s + x. k) (x)
(26)
#ES k=0
34

---

Published in Transactions on Machine Learning Research (06/2023)
By plugging in V Exxes Ex=o P= + >z, k), (x) into the objective function ()) we get the following results:
V0,)( = (oL
p (81 - s, k,k) (s)
#ES == k=
- (() (s)
Let v(() = Σ
pai s, 2, (8)
#ES
k=
Σ ((s)
Σ
Eoes 1(()) Do: (s)
7ss)
SES
.ES
(7s)
1000
Σ n(x)
is constant
#ES SES (18)
$ES
Σ Σ
d (s) (s))
Lhet (=))
77s))
E.es
SES ((s))
#ES 0E
(al((
ΣE Σe
(s)
p(bls)q T. (s,aa
T(a(3)
#ES DE A NEB
(q ( (ss.,))))((m.
V (a'133)
(27)
Now we calculate the derivative of the state value function on w':
V Twittisspss) (s)
=V.
ΣΣ (103)))0))))0"070000000 DEEBEB
(s,a, (28)
We let (5)(s)) (s)= ELEB ( and
ddw' (s) EoEA EBEB (u a)) Similar to (s) we have:
V (wiplitioss)
(8) +
ΣΣ
x(c()))(bls) E, seS ((ab3)p(Ussppe1lss....). (oo
REA bEB
Σ
AEA DEB EES
(5) + Σ F (s VV
S'ES
-00² (s) + 000 (5) + Σ 1 (s + +1,1) 1 (6)) (5)+ + Σ (s - 8", ,,, 1)V (8
EEES
T. + k3) (s)
(8)+ + (s))
(29)
2ES 0 0=
35

---

Published in Transactions on Machine Learning Research (06/2023)
By plugging in Vurot EvES ER=O x, k))l// (s) d= we can get the following results:
(s)] (d)
into the objective function J' w),
V (0, (wr0tF(((1))
(81 - 8,k) 16600 (8) +0) (s)
sES 0==
(s) [v: (ao
sES A.SEEAAEE BEB
-B(saN))p(Tp)))
(1 V No.f(s, p(1l))
-B(RaM)~M(MM)))
<a 36)
Vg. log b')
(30)
B.2.2 Policy gradients for deterministic polices
Theorem B.6 (Policy gradients for deterministic polices in RMAAC for MG-SPA). For each agent E and adversary E M using deterministic policies, the policy gradients of the objective J Ji(A, (.)) with respect to the parumeler 0, w are:
T
VO. = T 1=1
by) (o) Va
(31)
T
Vo.J((0,w) = T Σ
V be) + trgg Vaip'(ss) (
(32)
1=1
where reg or
Proof. Note that we here parameterize all policies n' pp as deterministic policies. Then we have:
V oz J' w) Es-p(n..)
Von
Egnpir.e)
vnng(ss.o.)VVnx(((1
(33)
Vie J' w) Esnp(n.))
[=,g(ss,
Bgppiree)
V (a uM (F)
I( (6) ('))s) Vy
Esmp(n.e)
V Vw.p's [ (8, a. + reg]]
(34)
where reg-
V Va-q'
a, b)V go Vz (s) When the actors updated in mini-batch fashion respectively.
Mnih
al.
2015
Li et al.
2014
9 and 10 approximate 33 and 34
B.2.3
Pseudo code of RMAAC
We provide the Pseudo code of RMAAC with deterministic policies in Algorithm The stochastic policy version RMAAC is similar Algorithm| | but uses different policy gradients.
36

---

Published in Transactions on Machine Learning Research (06/2023)
Algorithm 1: RMAAC with deterministic policies
Randomly initialize the critic network (s(s, a, bln'), ), the actor network n' T-16'"), and the adversary network ('("ww") for agent i. Initialize target networks q", ,";
for each episode do
Initialize a random process N for action exploration;
Receive initial state s; for each time slep do
For each adversary i, select action b' (s() .V' w.r.t the current policy and exploration.
Compute the perturbed state 3 = f(, b*). Execute actions a' = x(5)) + / and observe the
reward (r" "") and the new state information s' and store(s, a, b, s,r, in replay buffer D. Set s' + for agent i-1 to n do Sample a random minibatch of K samples (8k; ak, by, rk. s(.) from D;
7
8
Set v = rí + 7 oh, (b)) (a)la==m (B))
9
Update critic by minimizing the loss L = R Ex [ (sk ax bn)l
10
11
for each iteration step do
Update actor I' (-10t) and adversary p'((lw)) using the following gradients
12
+aa Oi + 0i + aa 1 En Va ( V.: ax, bx) where af = (8%),, ; bf = p((sx);
13
K
wt + w-- 0bb Ex (s)p((s)) [Vrn't (SK, wk. by) reg] where ( (3)), ab = =3)), by p'(ss);
reg = Vojg ('kk ag, by) V sj
15
end end
16
Update all larget networks: 6² + r0 + (1 7)0", w + Tw² + (1 T)W"
17
18
end
19
end
37

---

Published in Transactions on Machine Learning Research (06/2023)
C Experiments
C.1 Robust multi-agent Q-learning (RMAQ)
In this section, we first introduce the designed two-player game in that the reward function and transition probability function are formally defined. The MG-SPA based on the two-player game also further explained. Then we show more experimental results about the proposed robust multi-agent Q-learning (RMAQ) algorithm, such as the training process of the RMAQ algorithm in terms of the total discounted rewards.
C.1.1 Two-player game
a' a² r =
a' # a² r r= 0
O a' a² r = 0
SO
$
a * a r =
Figure 10: Two-player game: each player has two states and the same action set with size 2. Under state 8o: two players get the same reward I when they choose the same action. At state 81, two players get the same reward I when they choose different actions. One state switches to another state only when two players get a reward, ie. two players always stay in the current state until they get the reward.
Look Figure 10 (same as Figure 3 in the main text.), this how we run the designed two-player game. The reward function and transition probability function p are defined as follows.
These two players get the same rewards all the time, i.e. they share reward function
1, a and s 8g
1, a * a² and s = 81
r' r'(s,a',
(35)
0. a' + aa,and and s =
0, a' a², and
The state does not change until these two players get positive reward. So the transition probability function p
L, a a², and so
0, a a² and so
at * a² and so
1. a # a² and s so
a(sils,a'dd
p(sols,at, ,,²)
(36)
1, at a² and s = s1
0, al = d² and s = $1
0, a + a², and =
1. al 4 a² and s S1
Possible Nash Equilibrium can be पं = (mt, mt) or nं (m} mz) where
1, 1, and s0
1, 2 1, and
0, a 0, and so
0, a 0, and S0
(a) =
(a>13)
(37)
1, a = 1, and s = $1
0, a² 1, and s $1
0, a² = 0, and s =
1, a² = 0, and 8
0, = l,a =
0, a 0, and 8 =
1. a and so 7 (a?ls) =
1, 2 1, 80
(s) =
(38)
0, a and & 81
1, a 0, and s 81
1. a = 0, and s = $1
0. a = 1, and & = 81
38

---

Published in Transactions on Machine Learning Research (06/2023)
NE 7i means player 1 always selects action 1, player 2 selects action under state sy and action 0 under state NE z2 means player 1 always selects action 0, player 2 selects action 0 under state so and action 0 under state $1-
According to the definition of MG-SPA, we add two adversaries for each player to perturb the player's observations. And adversaries get negative rewards of players. We let adversaries share a same action space B² 1² {0,1), where 0 means do not disturb, means change the observation to the opposite one. Therefore, the perturbed function f in this MG-SPA is defined as:
[ b = 0) 80
f(s1, b = 0)
(39)
M(0,, b= = 1) =81
f(s),b 1) 80
Obviously, is a bijective function when s is given. And the constraint parameter e = |||||, where ||||| == max |s s' ve,ees Lee. no constraints for adversaries' power.
A Robust Equilibrium (RE) of this MG-SPA would be d'
(ā #2 Pt, P2), where
(3 0.5,
E
#2((21s)) = 0.5,
Vs 8 S ss S Ys e S
(40)
(.(1')s) 0.5,
(b(b)))) 0.5,
C.1.2 Training procedure
In Figure [1 we show the total discounted rewards in the function of training episodes. We set the learning
rate as 0.1 and train our RMAQ algorithm for 400 episodes. And each episode contains 25 training steps. We the total discounted rewards converges to 50, i.e. the optimal value in the MG-SPA, after about 280 episodes or 7000 steps.
Total Discounted Rewards when Training
values
20
100
150
200
training episodes
Figure 11: The total discounted rewards converge to the optimal value after about 280 training episodes.
39

---

Published in Transactions on Machine Learning Research (06/2023)
C.2 Robust multi-agent actor-critic (RMAAC)
In this section, we first briefly introduce the multi-agent environments use in our experiments. Then we provide more experimental results and explanations, such as the testing results under a cleaned environment (accurate state information can be attained) and a randomly perturbed environment (injecting standard Gaussian noise in agents' observations). In the last subsection, we list all ieper-parametens we used in the experiments, as well as the baseline source code.
C.2.1 Multi-agent environments
predator
predator
agent 2
agent
"blue"
x
agent 2
X
4
predator 3
agent 3
"red"
x
(a)
agent
(b)
(c)
prey
agent 1
agent 2
speaker
agent
"blue"
adversary
agent 2
x
X
listener
x
adversary
(d)
(e)
Figure 12: Illusrationns of the experimental scenarios and some games we consider, including a) Cooperative communication b) Cooperative navigation c) Predalor prey d) Keep away e) Physical deception Navigate communication
Cooperative communication (CC): This is a cooperative game. There are 2 agents and 3 landmarks of different colors. Each agent wants to get to their target landmark, which is known only by other agents. The reward is collective. So agents have to learn to communicate the goal of the other agent, and navigate their landmark.
Cooperative navigation (CN): This is cooperative game. There are 3 agents and 3 landmarks. Agents are rewarded based on how far any agent is from each landmark. Agents are penalized if they collide with other agents. So, agents have to learn to cover all the landmarks while avoiding collisions.
Physical deception (PD): This mixed cooperative and competitive task. There are 2 collaborative agents, landmarks, and adversary. Both the collaborative agents and the adversary want to reach the target, but only collaborative agents know the correct target. The collaborative agents should learn a policy cover all landmarks that the adversary does not know which one is the true target.
Keep away (KA): This is competitive task. There is 1 agent, 1 adversary, and 1 landmark. The agent knows the position of the target landmark and wants to reach it. The adversary is rewarded if it is close to the landmark, and the agent is far from the landmark. The adversary should learn to push the agent away from the landmark.
Predator prey (PP): This is a mixed game known as predator-prcy. Prey agents (green) are faster and want to avoid being hit by adversaries (red). Predators are slower and want hit good agents. Obstacles (large black circles) block the way.
40

---

Published in Transactions on Machine Learning Research (06/2023)
Navigate communication (NC): This is cooperative game that is similar to Cooperative communccttion. There are 2 agents and 3 landmarks of different colors. An agent is the 'speaker' that does not move but observes the goal of another agent. Another agent is the listener that cannot speak, but must navigate to the correct landmark.
Predator prey+ (PP+): This is an extension of the Predator prey environment by adding more agents. There preys, 6 adversaries, and 4 landmarks. Prey agents are faster and want avoid being hit by adversaries. Predators slower and want to hit good agents. Obstacles block the way.
C.2.2 Experiments hyper-panee parammeerreee
we show all hyper- parerpaaamsterss we use to train our policics and baselines. We also provide our source code in the supplementary material. The source code of M3DDPG (Li et al. 2019) and MADDPG Lowe et al. (017)) accept the MIT License which allows any person obtaining them to deal in the code without restriction, including without limitation the rights to use, copy, modify, etc. More information about
In Table 1
this license refers to https: htops://gthi //t:://gttttt thub. com/ openai/maddpg and https://github: con//addaiidodd//33dgg
Table Hyper-parameters
Parameter
RMAAC
M3DDPG
MADDPG
optimizer
Adam
Adam
Adam
learning rate
0.01
0.01
0.01
adversarial learning rate discount factor
0.005
/
/
0.95
0.95
0.95
replay buffer size number of hidden layers activation function
106
106
106
2
2
Relu
Relu
Relu
number of hidden unites per layer
64
64
64
number of samples per minibatch
1024
1024
1024
target network update coefficient iteration steps
0.01
0.01
0.01
20
20
20
constraint parameter episodes in training
0.5
/
/
10k
10k
10k
time steps in episode
25
25
25
C.2.3 More testing results
In this subsection, we provide more testing results under a cleaned environment (accurate state information can be attained) and randomly disturbed environment (injecting standard Gaussian noise into agents' observations).
As we have reported the comparison of mean episode testing rewards under a cleaned environment by using 4 different methods in the main manuscript (Figures 6 and S]. we further report the variance of testing results in the appendix. In Table 5 different environment settings. Our method has the lowest variance three of the five scenarios. Notice that RM1 denotes our RMAAC policy trained with the lincar noise format f1, RM2 denotes our RMAAC policy trained with the Gaussian noise format f2, MA denotes MADDPG bettps//giithul htttss///gihaab..ccoppppas///e/s cwwm/ppeaaa///mmappppppppppppppp M3 denotes M3DDPG hhttps://githii com/ hoomm/daaddddd///ddddgg
and G we also report the variances testing rewards in different scenarios under
MAPPO is a multi-agent reinforcement learning algorithm that performs well in cooperative multi-agent set- tings Yu et al. 2021a). We use MP lo denote MAPPO (https://github httaaa/o...oaa.baaaaaarrr///rrro
Figure 13] we compare its performance with our RMAAC algorithm in two cooperative scenarios of MPE. The details of scenarios such as Cooperative navigation, Navigate communication can be found in the last section. We can see that under the optimally perturbed environment, RMAAC outperforms MAPPO in all scenarios. Additionally, the reason we included MAPPO in the Appendix but not in the main text.
41

---

Published in Transactions on Machine Learning Research (06/2023)
is that the current source code provider of MAPPO only provides instructions and codes for using it in cooperative environments. However, to validate our proposed method in different settings, we carefully selected experimental environments to include different game types: cooperative, competitive, and mixed. Due to the lack of MAPPO source codes implementation in competitive and mixed environments, if we were to include the experimental results of MAPPO in the main text, it could disrupt the inlegrity and uniformity of the experiment section in the main text. Therefore, we included them the appendix as supplementary content.
In Figure and Table environments in the complicated scenario with a large number of agents between different algorithms. We adopt the Gaussian noise format in training RMAAC polices. We can see our method has the lowest variance under two three environments and has the highest rewards under all environments.
compare the mean episode testing rewards and variances under different
Table 5: Variance of testing rewards under cleaned environment
Algorithms
RM with fi
RM with
M3
MA
Cooperative communication (CC)
0.383
0.376
0.295
0.328
Cooperative navigation (CN)
0.413
0.361
0.416
0.376
Physical deception (PD)
0.175
0.165
0.133
0.143
Keep away (KA)
0.137
0.134
0.17
0.145
Predator prey (PP)
5.139
1.450
4.681
4.725
Table Variance of testing rewards under randomly perturbed environment
Algorithms
RM with fi
RM with f2
M3
MA
Cooperative communication (CC)
0.592
0.547
1.187
0.937
Cooperative navigation (CN)
0.336
0)33
0.328
0.321
Physical deception (PD)
0.222
0.292
0.209
0.184
Keep away (KA)
0.155
0.155
0.166
0.161
Predator prey (PP)
4.629
2.752
3.644
2.9
Table 7: Variance of testing rewards under different environments in Predator prey+-
Algorithm
RM
M3
MA
Optimally Perturbed Env
4.199
4.046
3.924
Randomly Perturbed Env
4.664
5.774
6.191
Cleaned Env
3.928
5.521
6.006
42

---

Published in Transactions on Machine Learning Research (06/2023)
Gaussian Noise
Gassian Noise
50
RM
Mean Episode Testing Rewards
MP
Mean Episode Testing Rewards
MP
82
80
35
78
76
25
74
72
15
70
68
CN
NC
Figure 13: Comparison of mcan cpisode testing rewards using MAPPO and RMAAC under optimally
perturbed environments. RMAAC outperforms MAPPO in all cooperative scenarios under optimally
perturbed environments.
Optimally Perturbed Env
Cleaned Env
Randomly Perturbed Env
90
84.3
Mean Episode Testing Rewards
88
Mean Episode Testing Rewards
Mcan Episode Testing Rewards
84.0
87
83.5
86
83.0
84
83
81.5
82
82
81.0
81
80.5
80
80
80.0
PP+
PP+
PP+
Figure 14: Comparison of mean episode testing rewards using different algorithms under different environments in Prodator prey+. RMAAC outperforms all MARL bascline algorithms in the complicated multi-agent scenario.
C.3 Ablation Study for RMAAC
In this subsection, we first investigate the effect using different values constraint parameters e in the implementation of the RMAAC algorithm, then the effect of using different values of variance a., Finally, we study the performance of the RMAAC algorithm under other types of attacks.
C.3.1 Training Results Using Linear Noise with Different Constraint Parameters
Training Setup: In this subsection, we train several RMAAC policies using linear noise format as the state perturbation function, i.e. fi( s + b². The constraint parameter respectively as 0.01, 0.050,00000 0.1, 0.5, and 2, given other hyper-parameters unchanged. Other used hyper-parameters can be found in Table 4
Training Results: In Figure 15 16 and 17 we show the training process in three sccnarios: Cooperative communication (CC), Cooperative navigation (CN), Predator Prey (PP), respectively. The y-axis denotes the mean episode reward of the agents and the x-axis denotes the training episodes.
From these figures, we can see that, in general, the smaller the used variance, the higher the mean episode rewards RMAAC can achieve. However, RMAAC has different sensitivities the value of variance = 2, the RMAAC policies have the lowest mean episode rewards in all
different scenarios. When
43

---

Published in Transactions on Machine Learning Research (06/2023)
three scenarios. Nevertheless, when the smallest constraint parameter 0.01, the trained RMAAC policies do not achieve the highest mean episode rewards in all three scenarios. In these three scenarios, it is clear to see the performance of RMAAC using = 0.5 is better than or similar to the performance of RMAAC using < = 1, and better than the performance of RMAAC using c = 2, i.c. Performance(c = 0.5) 2 Performance(e = 1) Performance( = 2). The performance of the RMAAC policies is close when the constraint parameters are less or equal to than 0.1.
C.3.2 Testing Results Using Linear Noise with Different Constraint Parameters
In this subsection, we test well-trained RMAAC policies in perturbed environments where adversaries adopt. linear noise format and different constraint parameters.
The tested policy Test trained with the linear noise format fs() = b², constraint parameter is 0.5, where B² = Plese (s]c 0.5). The policy Prest is adversary i's policy which is trained with Trest in RMAAC, for all i = I..... .N. We use Ptest to denote the joint policy of adversaries which is used in the testing. In summary. we test agents' joint policy Tesst racemario (5) when adversaries adopt the joint policy 0.01, 0.05, 0.1, 0.5, 0.1, 1,2, scenario Cooperative communication (CC), Cooperative
Testing Sctup:
Plest aecenario (s]c), and navigation (CN), Predator Prey (PP), respectively. The testing is conducted over 400 episodes, and cach episode has 25 time steps.
19 and 20 we compare the performance of RMAAC, M3DDPG, and MADDPG in sccnarios CC, CN, and PP with diffcrent values constraint paramcters. MADDPG is a MARL baseline algorithm. M3DDPG is a robust MARL baseline algorithm. The y-axis denotes the mean episode reward of the agents.
Testing Results:
In Figures 18
From these figures, and robust MARL policies in terms of mean episode testing rewards under the attacks of linear noise format. with different constraint parameters c. Our proposed RMAAC algorithm is robust to the state information attacks of linear noise format with different constraint parameters.
see that in all three scenarios, our RMAAC policies outperform the bascline MARL
C.3.3 Training Results Using Gaussian Noise with Different Variance
Training Setup:
In this subsection, train several RMAAC policies using Gaussian noise format as the state s+N((', perturbation function, i.e. f2(s, = .)). The variance is respectively set 0.001, 0.05, 0.5, 1,2 and 3, given other hyper-parameters unchanged. Other used hyper-parameters can be found in Table 4
Training Results:
In Figure 21 22 and 23 we show the training process of RMAAC in three scenarios:
Cooperative communication (CC), Cooperative navigation (CN), Predator Prey (PP). The y-axis denotes the mean episode rewards of the agents and the x-axis denotes the training episodes.
From the figures, can that, in general, the smaller the value of variance used, the higher the mean episode rewards RMAAC can achieve. However, RMAAC has different sensitivities to the value of variance in different scenarios. When we use o = 3, the RMAAC policies have the lowest mean episode rewards in all three scenarios. Nevertheless, when we use the smallest magnitude 0.001, the trained RMAAC policies do not always achieve the highost mean episode rewards. In these three sconarios, it clear to see the performance of RMAAC using o = is better than or close to that of using a = 2, and better than that of using = 3, i.e. Performance(r = 1) 2 Performance(r 2) > Performance(c 3). The performance of the RMAAC policies is close when the constraint parameters are less than or equal to 0.5.
C.3.4 Testing Results Using Gaussian Noise with Different Variance
In this subsection, we test well-trained RMAAC policies in perturbed environments where adversaries adopt Gaussian noise format and different variances.
Testing Setup: The lested policy Trest is trained with Gaussian noise format f2(5, + 1), constraint parameter 0.5, where b² = (ile = 0.5). p is adversary i's policy which is trained with Wess in RMAAC, for all i 1.... N. We use Ptest denote the joint policy of adversaries. In summary, scenario (sle 0.5) and test. agents' joint policy nest ecenario when adversaries adopt the joint policy p
44

---

Published in Transactions on Machine Learning Research (06/2023)
Canperation
moen episoot reweerd
Figure 15: We train RMAAC policies using different values of constraint parameters in the scenario Cooperative Communication. In general, the smaller the constraint parameter used, the higher the mean episode rewards RMAAC can achieve.
Cooperative Navigation
mean episode Foweord
(-00)
(=p05
(epl
Cep5
[+1
Figure 16: We train RMAAC policies using different values of constraint parameters in the scenario Cooperative Navigation. In general, the smaller the constraint parameter is used, the higher the mean episode rewards RMAAC can achieve.
Prey
egisode
episode/k)
Figure 17: We train RMAAC policies using different values of constraint parameters the scenario Predator- Prey. In general, the smaller the constraint parameter is used, the higher the mean episode rewards RMAAC can achieve.
Gaussian noise format f2(s, + .), where a 0.001, 0.05, 0.1, 0.5, 1,2,3, scenario = Cooperative communication (CC), Cooperative navigation (CN), Predator Prey (PP). The testing is conducted over 400 episodes, and each episode has 25 time steps.
45

---

Published in Transactions on Machine Learning Research (06/2023)
Testing Results: In Figures 24
25 and 26 respectively compare the performance of RMAAC, M3DDPG,
and MADDPG in scenarios Cooperative communication, Cooperative navigation and Predator Prey with different values of constraint parameters. MADDPG is MARL baseline algorithm. M3DDPG is a robust MARL bascline algorithm. The y-axis denotes the mcan episode reward of the agents.
From these figures, we can see that in all three scenarios with all different values of constraint parameters, our RMAAC policies outperform the MARL and robust MARL baseline policies in terms of mean episode rewards under the attacks of Gaussian noise format with different variance. Our proposed RMAAC algorithm is robust to the state information attacks of Gaussian noise format with different values of variance.
C.3.5 Testing Results under Different State Perturbation Functions
In this subsoction, we test the well-trained RMAAC policies in perturbed environments where adversaries adopt different noise formats and policies.
Testing Setup: The tested agents' joint policy Wrest is trained with Gaussian noise format f2( + Gaussian(b",, o 1), constraint parameter 0.5, where b² ( 0.5). Prest is adversary i's policy which is trained with Frest in RMAAC, for all 7 = i.... .N We Ptest to denote the joint policy of adversaries. In summary, we test agents' joint policy recenario when adversaries adopt the joint policy Piest ( 0.5), in three scenarios scenario = Cooperative communcattin (CC), Cooperative navigation (CN), Predator Prey (PP), under non-optimal Gaussian format fa, Uniform noise format f4, fixed Gaussian noise format fa and Laplace noise format fe, respectively. These noise formats are defined in the following:
fs(s,b') + Gaussian(b ('a where b²= Phooon- Pnom-optimall optimal (sle),
f4(s, b¹) s + fni (-c, +c),
Js(s, b²) = 8 + Gaussian (0, 1);
fe(s, b²) + Laplace(b), 1) where b²= (s):;
(41)
where Phon- Pnon-optimal is non-optimal policy of adversary i. phon Phon-optimal is randomly chasen from the training process. As we can that fa and fe are independent of the optimal joint policy of adversaries, but fa and So are not. The testing is conducted over 400 episodes, and each episode has 25 time steps.
Testing Results:
29 we compare the performance of RMAAC, M3DDPG and MADDPG in sconarios Cooperative communication, Cooperative navigation and Predator Prey under different noise formats, respectively. MADDPG is a MARL baseline algorithm. M3DDPG is a robust MARL baseline algorithm. The y-axis denotes the mean episode reward of the agents.
In Figures 27 28 and
As see from these figuros, most of the time, our RMAAC policy outperforms the MARL (MADDPG) and robust MARL (M3DDPG) baseline policies. In Cooperative communication and Predator Prey, under all 4 different noise formats, RMAAC policies achieve the highest mean episode rewards. In Cooperative navigation, RMAAC policies have the highest mean episode rewards when the non-optimal Gaussian noise format and Laplace noise format are used. The only exception happens in Cooperative navigation when the Uniform noise format and fixed Gaussian noise format are used. However, we can find that the performance of RMAAC policies is close to that of the baseline policies in terms of mean episode testing rewards. In general, our RMAAC algorithm is robust different types of state information attacks.
46

---

Published in Transactions on Machine Learning Research (06/2023)
RM
RM
RM
RM
90-
90-
Episode Testing Rewardd
MA
Mean Episade Testing Rewards
NA
Mean Episode Testing Rewards
85
MA
Mean Episodee Testing Rewardds
MX
Mean Episode Testing Rewards
Ma
MA
70-
73
83-
85
85
Episode lesting
60-
70
75-
-5
60
65
70-
70-
CC
CC
CC
CC
CC
CC
Figure 18: We test the performance of RMAAC(RM), MADDPG(MA), and M3DDPG policies under the attack of linear noise format when using different values of constraint parameters in the scenario Cooperative Communication. RM denotes our robust MARL algorithm, i.. RMAAC. MA denotes MADDPG, MARL baseline algorithm. M3 denotes M3DDPG, a robust. MARL baseline algorithm. Our RMAAC algorithm outperforms baseline algorithms in terms of mean episode testing rewards under all situations using different. values of constraint parameters.
-- 0.5
E
0.01
-
0.005
0.001
Moan Episode Testing Rewards
RM
Mean Episode Testing Rewards
15
RM
Mcan Episode Testing Remards
RM
AM
RM
Episode Teating Rewards
15.0
RM
92.5
42.5
42.5
M3
40.0
30
Testing
40.0
40.0
37.5
37.5
37.5
35.0
35.0
22.5
32.5
20
30.0
27.5
15-
27.5
27.5
Figure 19: We test the performance of RMAAC(RM), MADDPG(MA), and M3DDPG(M3) policies under the attack of linear noise format when using different values of constraint. parameters in the scenario Cooperative Navigation. RM denotes our robust MARL algorithm, ie. RMAAC. MA denotes MADDPG, MARL baseline algorithm. M3 denotes M3DDPG, robust MARL baseline algorithm. Our RMAAC algorithm outperforms baseline algorithms in terms of mean episode testing rewards under all situations using different values of constraint parameters.
0.5
E
0.01
0.005
108
0.001
Mean Episode lesting Rewards
BM
Mean Episodl Texting Rewards
RM
Mean Episode Testing Rewards
104.0
RM
Mean Episode Testing Rewards
RM
Meon Episode Testing Rewards
RM
Meen Episade Testing Rewards
RM
102.0
2077
207
1.0
101.5
203.0
306-
101.0
102.5
105
1.55
305
98
100.0
304
104-
07
99.5
101.3
99.0
103
101.0
PP
PP
PP
PP
PP
PP
Figure 20: We test the performance of RMAAC(RM), MADDPG(MA), and M3DDPG(MB3 policies under the attack of linear noise format when using different values of constraint parameters in the scenario Predator- Prra.. RM denotes our robust MARL algorithm, i.c. RMAAC. MA denotes MADDPG, MARL baseline algorithm. M3 denotes M3DDPG, robust. MARL baseline algorithm. Our RMAAC algorit hum outperforms baseline algorithms in terms of mean episode testing rewards under all situations using different values of constraint parameters.
47

---

Published in Transactions on Machine Learning Research (06/2023)
Cooperaliee
meat espoodde rewerd
p00l
(006eek)
Figure 21: We train RMAAC policies using different values of variance in the scenario Cooperative Commu- nication. In general, the smaller the variance is used, the higher the mean episode rewards RMAAC can achieve.
Cooperetive Nevigation
mete soloeet reswrrd
var-p0ot
var
vor+3
ep (oloooekk)
Figure 22: We train RMAAC policies using diffcrent values of variance in the scenario Cooperative Navigation. In general, the smaller the variance is used, the higher the mean episode rewards RMAAC can achieve.
Predator-Prey
epicode
var-p001
ver=p05
vermpl
var+2
var+3
Figure 23: We train RMAAC policies using different values of variance in the scenario Predator-Prey. In general, the smaller the variance is used, the higher the mean episode rewards RMAAC can achieve.
48

---

Published in Transactions on Machine Learning Research (06/2023)
var 3
var 2
var
var
0.5
var
0.1
var
0.05
var
0.001
75
MA
Mean Episode Testing Rewards
MA
Mean Episode Testing Rewards
MA
RM
Mean Episode Testing Rewards
80
MA
Mean Episode Testing Rewards wwwards
MA
Mean Episode Testing Rewards
80
MX
RM
Mean Episode Testing Rewards
MA
70
75
75
75
75
Mean Episode Testing
70
65
70
70-
20-
70
70
es
60
65
65
65
85
55
60-
60
60
CC
CC
CC
Figure 24: We Lest the performance of RMAAC(RM)) MADDPG(MA), and M3DDPG(MB) policies under the attacks of Gaussian noise format with different variances in the scenario Cooperative Communication. RM denotes our robust MARL algorithm, i.c. RMAAC. MA denotes MADDPG, a. MARL bascline algorithm. M3 denotes M3DDPG, robust MARL baseline algorithm. Our RMAAC algorithm outperforms baseline algorithms in terms of mean episode testing rewards under all Gaussian noise formats with different variances.
0.5
0.1
0.05
0.001
Mean Episode Testing Rewards
35
IM
Mean Episode Testing Rewards
RM M3
Mean Episode Testing Rtewards
RM
Mean Episode Testing Rewards
RM
Mean Episode Testing Rewards
40
MA
RM
40
RM
MA
Mean Episode Testing Rewards
AM
25
M4
M3
M3
35
35
35
35
Mean Episode Testing
30
30-
30
30
30
30
25
25
25
25
25
20
20-
20
20
CN
CN
CN
CN
Figure 25: We test the performance of RMAAC(RM)), MADDPG(MA)) and M3DDPG(M3) policies under the attacks of Gaussian noise format with different variances in the scenario Cooperative Navigation. RM denotes our robust MARL algorithm, i.c. RMAAC. MA denotes MADDPG, MART baseline algorithm. M3 denotes M3DDPG, robust MARL baseline algorithm. Our RMAAC algorithm outperforms baseline algorithms in terms of mean episode testing rewards under all Gaussian noise formats with different variances.
Mean Episode Testing Rewards
103.0
RM
Mean Episode Testing Rewards
:03.0
RM
Mean Episode Testing Rewardss
RM
Mean Episode Testing Rewards
103.5
RM
Mean Episade Testing Rewardss
103.5
RM
Mean Episode Testing Rewards
103.5
RM
Mean Episode Testing Rewards
103.5
RM
M3
M3
M3
M3
M3
M3
M3
103.0
103
103.0
103.0
102.0
102.5
102.5
102.5
:02.0
102.5
101.5
102.0
:01.5
102.0
102.0
101.5
100.5
101.5
101
101.5
301.5
101.0
PP
Figure 26: We test the performance of RMAAC(RM), MADDPG(MA), and M3DDPG(M33 policies under the attacks of Gaussian noise format with different variances the scenario Predator-Prey. RM denotes our robust MARL algorithm, i.e. RMAAC. MA denotes MADDPG, a MARL baseline algorithm. M3 denotes M3DDPG, robust MARL baseline algorithm. Our RMAAC algorithm outperforms baseline algorithns in terms of mean episode testing rewards under all Gaussian noise formats with different variances.
49

---

Published in Transactions on Machine Learning Research (06/2023)
Non-optimal
Uniform
Fixed Gaussian
Laplace
85
RM
50
RM
Mean Episode Testing Rewards
MA
90
MA
M3
MB
M3
50
MS
75-
75
70-
70
75
65
55
70
.00 60
CC
CC
CC
CC
Figure 27: We lest the performance of RMAAC(RM), MADDPG(MA), and M3DDPG(M3) policies under the attacks of different noise formats in the scenario Cooperative Communication. RM denotes our robust MARL algorithm, i.e. RMAAC. MA denotes MADDPG, a MARL baseline algorithm. M3 denotes M3DDPG,
a robust MARL baseline algorithm. Our RMAAC algorithm outperforms baseline algorithms in terms of mean episode testing rewards under all kinds of attacks.
Non-optimal
Uniform
Gaussian
Laplace
Mean Episode Testing Rewardss
40
RM
55.0
RM
52.5
RM
40
RM
M3
MB
M3
M3
50.0
47.5
45.0
30
45.0
42.5
40.0
31.5
35.0
20
32.5
Figure 28: We Lest the performance of RMAAC policies under the atlacks of different noise formats in the scenario Cooperative Navigation. RM denotes our robust MARL algorithm, ie. RMAAC. MA denotes MADDPG, a MARL bascline algorithm. M3 denotes M3DDPG, a robust MARL bascline algorithm. Our RMAAC algorithm either outperforms rewards under all kinds of attacks.
close to baseline algorithms in terms of mean episode testing
Non-optimal
Uniform
Fixed Gaussian
Laplace
Mean Episode Testing Rewards
112.
120
112.5
RM
110.0
MA
MA
MA
M3
M3
M3
M3
107.5
115
107.5
105.0
102.5
102.5
105
100.0
1.00
97.5
1000
95.0
92.5
95
85
92.5
Figure 29: We test the performance of RMAAC policies under the attacks of different noise formats in the scenario Predator-Prey. RM denotes our robust MARL algorithm, i.e. RMAAC. MA denotes MADDPG, MARL baseline algorithm. M3 denotes M3DDPG, robust MARL baseline algorithm. Our RMAAC algorithm outperforms baseline algorithms in terms of mean episode testing rewards under all kinds of attacks.
50


Reviews:
[{"review_id": "nqYOmhCJc3", "reviewer": "Reviewer_VChK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The work  nicely motivates and addresses the issue of state uncertainty in multi-agent reinforcement learning, focusing on the challenge of learning robust behaviours when faced with adversely tampered states. \n-  The work provides a problem formulation, solution concept and algorithmic design for this setting, all in all a well-rounded contribution \n\nWeaknesses:\n- My main concern regards how appropriate the selected formalism is for this setting, namely the MG-SPA, where the perturbations are modelled using a functional form. While I understand that this choice allows one to stand on more 'solid' theoretical grounds, I believe that this setting warrants and can benefit from frameworks such as Dec-POMDPs or POSGs (especially after observing the results on including the history-based policies). In order to amend this issue, perhaps a short discussion, or remark should be included. \n- Secondly, in order to improve the clarity and flow of this work, I think Section 4.3 can benefit from a better context or connection with the rest of the paper, as it currently appears disconnected from the rest.\n- As far as I can tell, there is an inconsistent use of baselines (for RMAAC): M3DDPG, MADDPG, MAPPO (present only on the Appendix?). Can you motivate the current setup and why not all the baselines are present in the evaluation? \n- I also missed the connection between some of the assumptions and the theoretical results, example Assumption 4.4 (5), or a direct discussion on their necessity.\n- I would additionally suggest a discussion on the restriction or necessity of deterministic versus stochastic policies (I only find one mention, on page 9, on parametrizing the policies as deterministic ones).\n- Finally, as far as I know, there is no page limit for the submission (as currently mentioned on page 12), so improving and expanding the evaluation will strengthen and improve the work.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work formalises and analyses the setting of learning in multi-agent systems under imperfect or adversely tampered state information. It introduces the framework of Markov Games with state perturbation adversaries (MG-SPA), together with robust equilibrium (RE) as a solution concept. It then also proposes two algorithmic contributions: robust multi-agent Q-learning (RMAQ), with convergence guarantees, as well as robust multi-agent actor-critic (RMAAC) for high-dimensional state-action spaces.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Assumption 4.4 - more clear formatting (perhaps each assumption on a new line)\n- A better connection/explanation on motivating the necessary assumptions for the theoretical analysis and results\n- Additional discussions regarding the chosen formalism and policy types\n- Additional context around the idea of history-based policies \n- I also find it interesting to include in the main text the results and discussion on the performance of robust MARL approaches in worst-case settings and their potential degradation under lighter perturbations (pages 33, 34)\n- Can you clarify how RMAAC is trained for the results in table 2 and figure 6, it is trained under the corresponding f?\n- Could you provide a list of empirical assumptions required for training RMAAC, as well as parameters, eg: f, epsilon?\n- If possible, would it be possible to add proof sketches/intuitions in the main text of the paper, to improve flow and readability?\n\nMinor remarks: \n- page 3 \"where all players (...) use policies that no one has an incentive to deviate\" $\\rightarrow$ from which no one has...\n- page 7 Section 4.3 \"agent $i$ choose its actions\" $\\rightarrow$ chooses\n- page 12 \"In a summary\" $\\rightarrow$ In summary\n- page 25 \"We re-write Lemma it in Lemma....\" $\\rightarrow$ re-write it in ....\n", "broader_impact_concerns": "Robustness in MARL is a valuable contribution for potentially sensible application domains, but perhaps a Broader Impact Statement is not required yet at this stage of development.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "XYUxwpNbXm", "reviewer": "Reviewer_6cE4", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n\n- This paper addresses an important and challenging problem in multi-agent reinforcement learning, which is the robustness of agents' policies in the presence of state uncertainties. \n\n- The authors provide a theoretical framework for analyzing the problem and proposes two algorithms, RMAQ and RMAAC, to find robust equilibria. \n\n- The experiments show that the proposed algorithms outperform several existing MARL methods in several multi-agent environments. The paper also provides insights into solving an MG-SPA by solving a corresponding EFG, which may be useful for future research.\n\nCons:\n\n- The paper does not consider the case where agents have different levels of sensing capabilities or different types of sensing errors. \n\n- It also assumes that the state perturbation adversaries have complete knowledge of the agents' policies, which may not be realistic in some scenarios. \n\n- Additionally, the paper focuses on discrete state and action spaces, and it may not be directly applicable to continuous state and action spaces. \n\n- Finally, the experiments are limited to a few specific environments, and it would be interesting to see how the proposed algorithms perform in other scenarios.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The contributions of this paper are:\n\n- Introducing the problem of multi-agent reinforcement learning (MARL) with state uncertainty caused by inaccurate sensing or state perturbation adversaries.\n\n- Modeling the problem as a Markov Game with state perturbation adversaries (MG-SPA) and proposing robust equilibrium (RE) as the solution concept.\n\n- Conducting a fundamental analysis of MG-SPA and giving conditions under which such an equilibrium exists.\n\n- Proposing a robust multi-agent Q-learning (RMAQ) algorithm to find such an equilibrium, with convergence guarantees.\n\n- Designing a robust multi-agent actor-critic (RMAAC) algorithm based on an analytical expression of the policy gradient derived in the paper to handle high-dimensional state-action space.\n\n- Showing through experiments that the proposed RMAQ algorithm converges to the optimal value function and the RMAAC algorithm outperforms several MARL methods that do not consider state uncertainty in several multi-agent environments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Overall, I am satisfied with this paper. Maybe the authors address my concerns about the weakness of this paper.", "broader_impact_concerns": "I think there is no related ethical concerns about this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "IYMIBiBLz0", "reviewer": "Reviewer_BAPE", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Strengths \n\n1. This is an interesting problem, where its single-agent counterpart has been studied extensively. It is important to see some difference arising up in the multi-agent settings.\n\n2. The whole framework seems complete with well-motivated theoretical results, leading to practical algorithms.\n\n- Weaknesses\n\n1. For a robustness problem, it is not quite reasonable to consider a Nash equilibrium as a solution concept. Since what we usually care about is a robust victim, which is weaker than a Nash when minmax is not equal to maxmin. In my opinion, the condition for the maxmin to exist is much milder than the Nash to exist. \n\n2. Following the first point, It seems only mixed robust NE is proved to exist. However, it seems the algorithm still tries to find a pure NE? In other words, in algorithmic design, we should hope to get a mixture of policy instead of a single policy? On the other hand, why not relax the solution concept to maxmin? If the current algorithm works for NE, we could hope it still works for maxmin.\n\n3. When the system has only one agent and one adversary, what would the current analysis and algorithm reduce to? Does it lead to something we already know about single-agent robust RL or something still new to people? Some discussions or remarks will be quite helpful.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper investigates the problem of robust MARL under potential adversarial perturbations on the state space. To analyze this problem, a model MG-SPA is built and a robust equilibrium is proposed as the solution concept. Furthermore, the paper provides some structural results on the existence of the equilibrium and a convergent algorithm based on Q-learning. To scale to high-dimensional continuous problems, an empirical actor-critic style algorithm is also proposed. Empirical results also verify the effectiveness of the algorithm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Make the notation more clear. For example, in the beginning, the policy uses only the state as input. Later on, the policy receives the history as input. Please make the difference clear to readers.\n\n2. Discussion on the reduced case, where there is only one agent is very beneficial.\n", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper address the important problem of robustness in multiagent reinforcement learning (MARL). Uncertainty in the environment is modelled as "state perturbation adversaries": agents that can see the full state and can take actions that corrupt the observation of the state for the other players. 

All the reviewers agree toward accepting this paper for TMLR with no outstanding criticisms, other than a minor comment that authors should take all the reviewer feedback into account when updating the paper.

The authors were quite responsive in their discussions with reviewers and have updated the paper as a result of the feedback received. However, the authors should double-check that every comment is addressed before submitting the camera-ready final copy.

Decision: Accept (poster)