Robust Multi-Agent Reinforcement Learning with State Uncertainties
Authors: Sihong He
Songyang Han
Sanbao Su
Shuo Han
Shaofeng Zou
Fei Miao
Venue: Submitted to ICLR 2023 (2023)
Keywords: multi-agent reinforcement learning
robust reinforcement learning

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, 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), and introduce Robust Equilibrium as the solution concept. We conduct fundamental analysis regarding MG-SPA and give conditions under which such an 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 methods that do not consider the state uncertainty in several multi-agent environments.

Under review as a conference paper at ICLR 2023
ROBUST MULTI-AGENT REINFORCEMENT LEARNING WITH STATE UNCERTAINTIES
Anonymous authors Paper under double-blind review
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, we study the problem of MARL with state uncertainty in this work. We provide the first attempt the theoretical and empirical analysis of this challenging problem. We first model the problem as a Markov Game with state perturbation adversaries (MG-SPA), and introduce Robust Equilibrium as the solution concept. We conduct a fundamental analysis regarding MG-SPA and give conditions under which such an equilibrium exists. Then propose a robust multi-agent Q-learning (RMAQ) algorithm to find such an equilibrium, with convergence guarantees. To handle nigh-dimensional state-action space, we design 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 methods that do not consider state uncertainty in several multi-agent environments.
INTRODUCTION
agent
Xooal
ebstacle
porturbed state
O
unoertainty set
SAFE
SAFE
Reinforcement Learning (RL) recently has achieved re-
markable success in many decision-making problems, such as robotics, autonomous driving, traffic control, and game playing (Espeholt et al., 2018; (Silver et al.) [207]] Mnih al., 2015). However, in real-world applications, the agent may face state uncertainty in that accurate in- formation about the state unavailable. This uncertainty may be caused by unavoidable sensor measurement errors, noise, missing information, communication issues, and/or malicious attacks. A policy not robust to state uncertainty can result in unsafe behaviors and even catastrophic out- comes. 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 a safe (no collision) and shortest path the goal (black cross). In [ the agent can observe the true state (red ball) and choose an optimal and collision-fii 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-fres free path tangent to However, by following a, agent actually crashes into the obstacle. To avoid collision in the worst case, the true state based on the observed state. Then the robustly optimal path under state uncertainty becomes the yellow curve å" tangent to the uncertainty set, shown in Figure (c).
inlutiion when snowing trus state
sraale solution uncierta eniits
robust solution over state uncertainty
Figure Motivation of considering state uncertainty in RL.
curve a* (in red) tangent to the obstacle. In comparison,
construct state uncertainty set that contains
In single-agent RL, imperfect information about the state has been studied in the literature of partially observable Markov decision process (POMDP) (Kaelbling et al.) 1998). However, as pointed out in recent literature (Huang et al.) 2017 Kos & Songl 2017; Yu et al. (0212) Zhang al. 2020a), the conditional observation probabilities in POMDP cannot capture the worst-case

---

Under review as a conference paper at ICLR 2023
(or adversarial) scenario, and the learned policy without considering state uncertainties may fail to achieve the agent's ' goal. Similarly, the existing literature of decentralized partially observable Markov decision process (Dec-POMDP) (Olichoek et al. 2016) does not provide theoretical analysis or algorithmic tools for MARI. under worst-case state uncertainties either. Dealing with state challenging for Multi-Agent Reinforcement Learning (MARL.,
uncertainty becomes even where each agent aims to maximize its own total return during the interaction with other agents and the environment. Even one agent receives misleading state information, its action affects both its own return and the other agents' returns (Zhang et al. 2020b) and may result in catastrophic failure. To better illustrate the effect of state uncertainty in MARL, the path planning problem in Fig- ure is modified such that two agents are trying to reach their in- dividual goals without collision (a penalty or negative reward ap- plied). When the blue agent knows the true position o (the subscript denotes time, which starts from 0) of the green agent, it will get around the green agent to quickly reach its goal with- out collision. However, in Fig- ure (a), when the blue agent can only observe the perturbed position si (yellow circle) of the green agent, would choose a straight line that it thought safe (Figure (al)). which eventually leads to crash (Figure 2 (a2)). In (b)) the blue agent adopts a robust trajectory by considering state uncertainty set based on its observation. As shown in Figure (bl), there no overlap between (si, 5g) (.% 54). Since the uncertainty sets centered at si and ST (the dotted circles) include the true state of the green agent, this robust trajectory also ensures no collision between (sğ: s() or (s/r, sy.) 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 multi-agent setting where the dynamics of other agents are considered.
agent1
agent
perturbed state
X goal
X goal
uncertainty
Thought Safe
BOOM
sp
$
(a)
(a1)
(a2)
Thought Safe
SAFE
SAFE
SG
(b)
(b1)
(b2)
Figure 2: Motivation of considering state uncertainty in MARL.
In this work, we develop robust MARL framework that accounts for state uncertainty. Specifically, we model the problem of MARL with state uncertainty as Markov Game with state perturbation adversaries (MG-SPA), in which each agent is associated with state perturbation adversary. One state perturbation adversary always plays against its corresponding agent by preventing the agent from knowing the true state accurately. We analyze the MARL problem with adversarial or worst- case state perturbations. Compared to single-agen agent RL, MARL is more challenging due to the interactions among agents and the necessity of studying equilibrium policies (Nash) 1951 McKelvey & Mcl.ennnn] 1996] Slantchev]] 2008 Daskalakis al. 2009. Etessami & Yannakakis 2010). The contributions of this work are summarized as follows.
Contributions: To the best of our knowledge, this work is the first attempt to systematically characterize state uncertainties in MARL and provide both theoretical and empirical analysis. First, 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, where all players including the agents and the adversaries use policies that no one has an incentive to 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, Robust Equilibrium policy of one agent is robust to the state uncertainties. 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 convergence guarantee, and an actor-critic (RMAAC) algorithm for computing a robust equilibrium policy in an MG-SPA. Finally, we conduct experiments two-player game to validate the convergence of the proposed Q-learning method RMAQ. We show that our RMAQ and RMAAC algorithms can learn robust policies that outperform baselines under state perturbations in multi-agent environments.
2

---

Under review as a conference paper at ICLR 2023
2 RELATED WORK
Robust Reinforcement Learning: Recent robust reinforcement learning studied different types
of uncertainties, such as action uncertainties (Tessler et al. 2019) and transition kernel uncertain-
ties (Sinha et al. 2020; Yu et al.] 202Tb; Hu et al.] 2020: Wang & Zou 2021; Lim & Autef [019
Nisioti et al. [202]] [e et al. (022). Some recent attempts about adversarial state perturbations for
single-agent validated the importance of considering state uncertainty and improving the robustness of
the learned policy in Deep RL. (Huang et al.
2017 Lin et al. 2017 Zhang et al. 2020a 2021 Everett
et al.] (021). The works of Zhang et al. (2020a] 2021) formulate the state perturbation in single agent RL as a modified Markov decision process, then study the robustness of single agent RL policies. The works of Huang et al. (0177) and Lin et al. (2017) show that adversarial state perturbation undermines the performance of neural network policies in single agent reinforcement learning and proposes different single agent attack strategies. In this work, 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 for the solution concept or theoretical analysis when considering adversarial state perturbations in MARL. Other types of uncertainties have been investigated in the literature, such as uncertainties about training
partner's type (Shen & How 202T) and the other agents' policies (Li et al. 2019 Sun al.) 202 van der Heiden et al.) (020). and reward uncertainties (Zhang et al. 2020b). The policy considered in these papers relies on the current 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 team of agents to optimize policies with the partial observable states (Oliehoek et al.) 2016 Chen et al., 2022). The work Lin et al. (2020) studies state perturbation in cooperative MARL, and proposes an attack method to attack the state of one single agent in order to decrease 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 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 MARI, and derives both theoretical analysis and practical algorithms.
Game Theory and MARL: MARL shares theoretical foundations with game theory research field and literature review has been provided to understand MARL from a game theoretical per- spective (Yang& & Wang 2020). A Markov game, sometimes called a stochastic game models the interaction between multiple agents (Owen) 2013 Littman| 1994). Algorithms to compute the Nash Equilibrium (NE) in Nash Q-learning (Hu & Wellman 2003), Dec-POMDP Oliehook al. 2016) or POSG (partially observable stochastic game) and analysis assuming that NE exists (Chades et al.
2002. Hansen et al. 2004 Nair et al., (202) have been developed in the literature without proving the conditions for the existence of NE. The main theoretical contributions of this work include proving conditions under which the proposed MG-SPA has Robust Equilibrium solutions, and convergence analysis of our proposed robust Q-learning algorithm. This is the first attempts to analyze fundamental properties of MARL under adversarial state uncertainties.
METHODOLOGY
3.1 MARKOV GAME WITH STATE PERTURBATION ADVERSARIES (MG-SPA)
fr' p, 2). where N/ is a set of N agents, St and A' are the state space, action space of agent i, respectively (Littman 1994 Owen 2013).7 . [0. 1) is the discounting factor. S = S x... x S is the joint state space. A
Preliminary: A Markov Game (MG) G is defined as (W, (5' heN, ;
x X AN is the joint action space. The state transition p : S x A + A(S) is 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 a reward function, r' : S x A + R. At time I, agent i chooses its action of according to policy xं: S + A(A*). The agents' joint policy IEN x' S - 35-A0 A(A).
Notations:
We use a tuple G == (N, M, (S JieN, (A' hEM. hee.....f to denote a Markov game with state perturbation adversaries (MG-SPA). In an MG-SPA, we introduce an additional set of adversaries M (i.... .... .N to a Markov game (MG) with an agent N. Each agent i is associated with an adversary and a true state s E S if without adversarial perturbation. Each adversary 7 is associated with action D E Bd and the same state st E S agent i. We
3

---

Under review as a conference paper at ICLR 2023
define the adversaries' joint action as b = (b'....bb)) b...,b) E B, B B¹ x ..... B At time t, adversary i can manipulate the corresponding agent i's state. Once adversary gets state si, it chooses an action by according to policy p² : + A(Bi). According to a perturbation function f. adversary i perturbs state si to 5 = f(t, bt) E S". Here we define the adversaries' joint policy ITiM p² S + (B)). The definitions of agent action and agents' joint action are the same as their definitions in MG. Agent i chooses its action oj with 8; according to policy x' (8)) x² S + ((A)). Agents execute the agents' joint action dz, then at time ++ 1, the joint state 8, turns to the next state 1 according a transition probability function p S' Ax B + (S)) Each agent gets a reward according a state-wise reward function ri AxAx + R. Each adversary gets an opposite reward -r:. In an MG, the transition probability function and reward function are considered as the model of the game. In an MG-SPA, the perturbation function f is also considered as part of the model, i.e., the model of an MG-SPA is consisted of f. and {r' Jew.- To incorporate realistic settings into our analysis, we restrict the power of each adversary. which is a common assumption for state perturbation adversaries in the RL literature (Zhang et al. [020a;] 2021 Everett et al. (021).
We define perturbation constraints St E Bdist st) S' to restrict the adversary i to perturb a state only to a predefined set of states. (e, 8*) c-radius ball measured in metric (), which 8-11-- We omit the subscript dist in the following context. For each agent i, it attempts to maximize its expected sum of discounted rewards, 5, a x--(5e), b p(-|s))] Each adversary i aims to minimize the objective function of agent i and is considered as receiving an opposite reward of agent i, which also leads value function -T p) for adversary i. We further define the value functions in an MG-SPA as follows:
often chosen to be the 1-norm distance: dist(s² (sat -=)===== = ||s
i.c. its objective function J' (TT, p) = IE |Σ -i=
ae, 6e)s1 (1)])(
Definition 3.1. (Value Functions) VTP are defined the state-value function or value function for short, and the action-value function, respectively. The ith element w and quipi are defined as qr (s, a.a) (s. =
(UTTPA , gT = (qT:P. ....p,..... ,....
.gT
1-1r211s = s,as 01 a, b,a x-116)),b. ~ p(-1ss), 86 f(s) (.. b)).
s1 = 5, x-115)),b, ~ 3/ = { respectively.
We name an equilibrium for an MG-SPA as a Robust Equilibrium (RE) and define it as follows:
Definition 3.2. (Robust Equilibrium) Given a Markov game with state perturbation adversaries G. joint policy de = (Te, p.) where T. = [ [m]...... ..) and p. = (p). ... ....) is said to be in robust equilibrium, or a robust equilibrium, if and only if. for any i N,, E S, " mi . ()))(s)) Z
"..i..ee +...(..))))())))) o(t.",=* " ...))is)) for all n¹ and p', where -i/ - represents the indices of all agents/udversaries except agent iJadversary i.
We seek to characterize the optimal value vx(s) = (s), ... v.((s)) defined by (s) = max, min,a ufx f," p. (s)). For notation convenience, we use (s)) to denote
yf ( o (s)). The Bellman Equations of an MG-SPA are in the forms of (I and (2) The Bellman Equation recursion for expected rewards, which helps us identifying or finding an RE,
( a, b) = - +y Σ *'ES
p(s'|s, (ssls,,e a, max min E 1g d''',''',,, b')aa ~ x(-13), 6' ~ p(-1s)]
(1)
(s( = max min E
Σ ES
p(s' (s a, rut )| _(-1)),,bbb-- ~ p(-ss) (2)
for all é E N, where क = (M prove them in the following subsection.
(p' : p.. are in robust equilibrium for G. We
3.2 THEORETICAL ANALYSIS OF MG-SPA
Vector Notations: To make the analysis easy to read, we follow and extend the vector notations in Puterman 22014). Let V denote the set of bounded real valued functions S with component wise partial order and norm ||e²]| || := sup.es |ur (s)). Let VMr denote the subspace of V of Borel measurable functions. For discrete state space, all real-valued functions are measurable so that V Vas. But
4

---

Under review as a conference paper at ICLR 2023
when S is continuum, Vas is proper subset of V. Let u real valued functions on S x x.. x S. i.c the across product of N state set and norm || := sup, || I| For discrete S, let |S| denote the number of elements in S. Let r denote a |S| -vector,, with sth component (s)) which the expected reward for agent under state s. And P the |S| [S] matrix with (s, s t) entry given by p(s'ls). We refer to r'd as the reward vector of agent i, and Pa as the probability transition matrix corresponding to a joint policy d = (T. p). r PPau is the expected total one-period discounted reward of agent obtained using the joint policy d (T. p). Let 2 as a list of joint policy {d1 d2......
(u'.... ,,", E V be the set of bounded
... and P = I, we denote the expected total discounted reward of agent using as 2i = Ex= P - Now, we define the following minimax operator which is used in the rest of the paper.
rá, + y rág +... + 7 "= Pdj ... Pd.-: ri. + +...
Definition 3.3. (Minimax Operator) For v' E V E S. we define the nonlinear operator on (s) by (s) == max,* min, pi pirr + (s)) where d === (m. - p=' We also define the operator Lu(s) = (s), ... N (s)) = ())) ,I,Nu' (s)). Then L'vd is a |S]-vector, with sth component L' (s).
For discrete S and bounded r", it follows from Lemma 5.6.1 1 in Puterman 2014)) that L've V for all v' E V. Therefore Lu E V for all E V. And in this paper, we consider the following assumptions in Markov games with state perturbation adversaries.
Assumption 3.4. (1) Bounded rewards; (s' a, b)l S M < M for all i E a A and E S. (2) Finite state and action spaces; all 5 A B are finite. (3) Stationary transition probability and reward functions. (4) f is bijection when sf is fixed. (5) All agents share one common reward function.
The next two propositions characterize the properties of the minimax operator L and space V. They have been proved in Appendix A.2
Proposition 3.5. (Contraction mapping) Suppose 0 S < 1, and Assumption 3.4 holds. Then L is contraction mapping on V.
Proposition 3.6. (Complete Space) V is complete normed linear space.
In Theorem 3.7 we show the fundamental theoretical analysis of an MG-SPA. In (1), we show that an optimal value function of an MG-SPA satisfies the Bellman Equations by applying the Squeeze theorem [Theorem 3.3.6, |Sohrab [003)]] Theorem 3.7 (2) 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 3.4 By introducing (3), we characterize the relationship between the optimal value function and Robust Equilibrium. 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 2.N-player Extensive- (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 full proof of Theorem 3.7 is in Appendix A.3
game
Theorem 3.7. Suppose 0 S < and Assumption 3.4 holds.
(I) (Solution of Bellman Equation) A value function v. V is optimal value function for all i E N, the point-wise value function v. E satisfies the corresponding Bellman Equation ② i.e. v Ti't for all i E N.
(2) (Existence and uniqueness of optimal value function) There exists a unique v. E V satisfying Lc. -v,, L.e. for all i N, L'vl vy-
(3) (Robust Equilibrium (RE) and optimal value function) A joint policy d, = (T P.). where
n. = (xt.....,TN)) and pa = (p] .px ), is robust equilibrium if and only if d is the optimal value function.
(4) (Existence of Robust Equilibrium) There exists mixed RE for MG-SPA.
Though the existence of NE in a stochastic game with perfect information has been investigated
(Nash 1951: Wald 1945), it is still open and challenging problem when players have no global
state or partially observable information (Hansen et al. 2004 Yang & Wang 2020). There is a bunch of literature developing algorithms trying find the NE in DecMPOMMP or partially observable
5

---

Under review as a conference paper at ICLR 2023
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 existence of NE. Once established the existence of RE, design algorithms find it. We first develop robust multi-agent Q-learning (RMAQ) algorithm with convergence guarantee. We then propose a robust multi-agent actor-critic (RMAAC) algorithm handle the case with high-dimensional state-action spaces.
3.3 ROBUST 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 3.7. We therefore develop value iteration (VI)-based method called robust multi-agent Q- Q-learning (RMAQ) algorithm. Recall the Bellman equation using action-value function in ( the optimal action-value qu satisfies (s, := r'(s, a,
yIE [Eyes S b) (s', a', D/)la' ~ (-15"),, ~ p.(+ss)] As consequence, the tabular- setting RMAQ update can be written as below,
4 (st, at, bi) = (1 - cu (x))) bi)+
(3)
ré( ar, +y
Σ
Σ
*
acti, be+1)
at IEA ER
where (T2,,5 P²,,) an NE policy by solving the 2N-player Extensive-form game (EFG) based on a
payoff function (g) ,.. -
g.)) The joint policy (m",,>"", (, is used in updating dt- All
related definitions of the EFG (at to solve an EFG is out of the scope of this work, algorithms to do this exist in the literature (Cermák cet al. 2017 Kroer et al. 2020). Note that, in RMAQ. each agent's policy is related to not only its own value function, but also other agents' value function. This multi-dependency structure considers the interactions between agents in game, which is different from the the Q-learnigg in single-agem RL that considers optimizing its value function. Meanwhile, establishing the convergence of multi- agent Q-learning algorithm is also a general challenge. Therefore, we try to establish the convergence of (3) in Theorem 3.9 motivated from Hu & Wellman (2003). Due space limitation, in Appendix B.2 we prove that RMAQ is guaranteed to get the optimal value function q. = (g..... .g.""" by
li 4/. ... -qt" - are introduced in Appendix A. How
updating qi (9l: ........ a recursively using (3) under Assumptions 3.8
Assumption 3.8. (1) State and action pairs have been visited infinitely often. (2) The learning rate a, satisfies the following conditions: 0 I O4 < 1, Ei of S 0o; if (8, a, b) F (st. ar be).
ar(s, a. b) = 0. (3) An NE of the 2N -N-player EFG based on (g) .g"" - each teration 1.
af exists at
Theorem 3.9. Under Assumption 3.8 the sequence } obtained from 3 converges to {q-} with probability which are the optimal action-value functions funnctioo that satisfy Bellman equations 1 for all i= 1= N..
Assumption (1) is 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-learning algorithm design papers that the exploration
property is not the main focus, this assumption is also common assumption (Fujimoto et al.) 2019).
For exploration strategies in RL (McFarlane 20188), researchers use e-greedy exploration (Gomes &
Kowalczyk 2009). UCB (Jin et 20188 Azar al. 2017). Thompson sampling (Russo et al. 2018).
Boltzmann exploration (Cesa-Bianchi et al. 2017). 7) etc. And for assumption (388)(3), researchers have found that the convergence
necessarily so sensitive to the existence of NE for the stage games during training (Hu & Wellman 2003 Yang et 2018). In particular, under Assumption 3.4 an NE of the 2.N-paayer EFG exists, which has been proved in Lemma A.6 in Appendix A We also provide an example in the experiment part (the two-player game) where assumptions are indeed satisfied, and our RMAQ algorithm successfully converges the RE of the corresponding MG-SPA,
3.4 ROBUST MULTI-AGENT ACTOR-CRITIC (RMAAC) ALGORITIIM
According to the above descriptions of a tabular RMAQ algorithm, each learning agent has to maintain N action-value functions. The total space requirement N || N | if |
....- |B*). This space complexity is linear in the number of joint states, polynomial in the number of agents' joint actions and adversaries' joint actions, and exponential in the number of agents. The computational complexity is mainly related to algorithms to solve Extensive-form
|A [B'|

---

Under review as a conference paper at ICLR 2023
game (Cermák al. 2017 Kroer et al. 2020 However, for general-sum normal-form games, computing an NE is known to be PPAD complete, which is still considered difficult in game theory literature (askkllaiis 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 high-dimensional space-action spaces. Because actor-critic methods incorporate function approximation into the update (Konda & Tsitsiklis 1999).
We consider each agent i's policy x' is parameterized mai for i E N, and the adversary's policy p² is parameterized as Pwr We denote 0 (0), ... A%) as the concatenation of agents' policy parameters, w has the similar definition. For simplicity, we omit the subscript 0, Wi. since the parameters can be identified by the names of policies. Note that we here parameterize all policies r as deterministic policies. Then the value function (s()) under policy (T,, p) satisfies
(s) = Baww,brup
Σ a, ()r a,s,,,),)))))))) yu (. WES
(4)
We establish the general policy gradient with respect to the parameter 0, in the following theorem. Then we propose our robust multi-agent actor-critic algorithm (RMAAC) which adopts centralized- training cecenttraaizdd-excuutt
algorithm structure in MARL literature (Li et al. 2019 Lowe et al.)
2017
Foerster et al. 2018). We put the pseudo-code of RMAAC in Appendix B.2.2
Theorem 3.10. (Policy Gradient in RMAAC for MG-SPA), For each agent E N and adversary i M, the policy gradients of the objective J' J'(0, w) with respect to the parameter 0, w are:
T
Va.j(0, = T
Vaig' (*t, a, V (=)
(0,w) = T Σ
1
Vorg (e, reg] Vei (st) (f)))))))=))
(5)
where reg- = v v V. an by) (T)
Proof. Taking gradient with respect to 0², w for all both sides of 4 yields the results. See details in Appendix I
a' A
a²
-00
4 EXPERIMENT
4.1 ROBUST
Q-LEARNING (RMAQ)
Figure 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 51, two play- ers get same reward 1 when they choose different actions. One state switches to another state only when two players get reward, i.e. two players always stay in the current state until they get reward.
y=
We show the performance of the proposed RMAQ algo- rithm by applying it to two-player game. We first intro- duce the designed two-player game. Then we investigate the convergence of this algorithm and compare the per- formance of the Robust Equilibrium policies with other agents' policies under different adversaries' policies.
Two-player game:
For the game in Figure 3 two players have the same action space A {0, }} and state space S = {Su, $1 The two players get the same positive rewards when they choose the same action under state 8o or choose different actions under state s1. The state does not change until these two players get positive reward. Possible Nash Equilibrium (NE) in this game can be πं = (x1 mf) that player always chooses action 1, player 2 chooses action under state 8o and action under state $1; πे (TT), =3) that player always chooses action 0, player chooses action 0 under state So and action under state $1. 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 s E S, i {1,2). 7 is the reward discounted rate. We set = 0.99, then vi (s) = 100.
According to the definition of MG-SPA, add two adversaries, state and get negative reward of the player. They have a same action space B {0, 1), where means do not disturb, 1 means change the observation to another one. Some times no perturbation
for each player to perturb the
7

---

Under review as a conference paper at ICLR 2023
would be good choice for adversaries. For example, when the true state is su, players using Tf. if adversary 1 does not perturb player I's observation, player will still select action 1. While adversary 2 changes player 2's observation to state $1, player 2 will choose action 0 which is not same to player I's action 1. Thus, players always fail the game and get no rewards. A Robust Equilibrium for MG-SPA would be d. = (# R2. p2) that each player chooses actions with equal probability and so do adversaries. The optimal discounted state value of corresponding MG-SPA is (s) = 11/2(1 --7 7) for all 8 E S, i E {1,2) 2} when players use Robust Equilibrium (RE) policies. We use 7 0.99, then (s) 50. More explanations of this two-player game refer to Appendix C.1
The learning process for RE: We initialize q' a, b) = q² a,s,,,)) b) 0 for all a, b. After observing the current state, adversaries 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 q according to (3) In the next state, all agents repeat the process above. The training stops after 7500 steps. When updating the Q-values, the agent applies NE policy from the Extensive-form game based on (q', ,2" -q'; -q²).
Experiment results: After 7000 steps of training, we find that agents' Q-values stabilize at certain values, though the dimension of q is a bit high as q E R We compare the optimal state value ü, and the total discounted rewards in Table I The value of the total discounted reward converges the optimal state value of the corresponding MG-SPA. This two-player game experiment result validates the convergence of our RMAQ method. We compare the RE policy with other agents' policies under different adversaries' policies in Appendix C.T This is to verify the robustness of RE policies.
Even for general-sum normal-form games, computing NE is known be PPAD- complete, which is still considered difficult in game theory literature (Conitzer & Sandholm 2002 Etessami & Yannakakis 2010). Therefore, we do not anticipate that the RMAQ algorithm can scale to very large MARL problems. In the next experimental subsection, we show RMAAC with function approximation can handle large-scale MARL problems.
Discussion:
4.2 ROBUST MULTI-AGENT ACTOR -CROTIC (RMAAC)
orginate
"eggimily
We compare our RMAAC algorithm with MAD- DPG (Lowe et al. 2017). which does not consider robustness, and M3DDPG (Li et al. 2019), where robustness is considered with respective to the oppo- nents' policies altering. We run experiments in sev- eral benchmark multi-agent environments, based on the multi-agent partiele environments (MPE) (Lowe) et al.) 2017). The host machine adopted in our ex- periments server configured with AMD Ryzen Threadripper 2990WX 32-core processors and four Quadro RTX 6000 GPUs. Our experiments are per- formed on Python 3.5.4, Gym 0.10.5, Numpy 1.14.5,
Veen teding Rewadds
B
434
3
Meac Edtadd
Edtrodh
e
2 13
PP
PP
Figure 4: Comparison of episode mean test- ing rewards using different algorithm in com- plicated scenarios with a larger number of agents of MPE. Tensorflow 1.8.0, and CUDA 9.0.
Experiment procedure: We first train agents' policies using RMAAC, MADDPG and M3DDPG, respectively. For our RMAAC algorithm, set the constraint parameter 0.5. And 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 fi (s+ b)) := s' + b", i.e. the perturbed state g is calculated by adding a random noise b² generated by adversary to the true state s And fa(s", (²) := st + Gaussian(B (b², Σ), where the adversary i' action b² is the mean of the Gaussian distribution. And E is the covariance, we set it as I, i.e. an identity matrix. We call it Gaussian
Linorr Hoise
Lisoo Helist
Litor Noi5s
Lege Me5a
Liboa More
Gaussiin Noke
Coussiion Hosse
Dassiaan Coussion Mase
Gausskor
304
100
Pesan Cplacd Teeinng
$0.25
Veen pponte
201
Moar
00
2033
PO
ON
KA
Figure 5: Comparison of episode mean testing rewards using different algorithms and different perturbation functions in MPE.
8

---

Under review as a conference paper at ICLR 2023
Table I: Convergence Values of Total Discounted Rewards when Training Ends
2² (50)
v²
($1)
(=(11)
0. (50)
(5
(s1)
(5
value
49.99
49.99
49.99
49.99
50.00
50.00
50.00
50.00
Table 2: Variance of testing rewards
Perturbation function
Linear noise fi
Gaussian noise fz
Algorithms
RM
M3
MA
RM
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.225
0.252
Keep away (KA)
0.161
0.168
0.175
0.167
0.17
0.167
Predator prey (PP)
3.213
2.812
3.671
2.304
2.711
2.811
noise format. These two formats f1: f2 are commonly used in adversarial training (Creswell et al. 2018; Zhang et al. 2020a; 2021). Then we test the well-trained policies in the optimally disturbed environment (injected noise is produced by those adversaries trained with RMAAC algorithm). The testing step is chosen as 10000 and each episode contains 24 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 baseline (100) to rewards for making them positive. Then it's easier to observe the testing 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 situation, we also run experiments in a scenario with more agents, which is called Predator prey+ (PP+). More details of these games are in Append C.2.1
Experiment results: In Figure and Table 2, we report the episode mean 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 RMM, M3, MA for abbreviations of RMAAC, M3DDPG and MADDPG, respectively. In Figure [ the left five figures are mean rewards under the linear noise format f1, 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 no matter what noise format is used. The only exception is when using in Keep away under linear noise. However, our RMAAC still achieves the highest rewards when testing in Keep away under Gaussian noise. In Figure 4 we show the comparison results in complicated scenario with larger number of agents. The policies trained with RMAAC get highest reward when testing under optimally perturbed environments. Higher rewards mean agents are performing better. It turns out RMAAC policies are more robust to the worst-case state uncertainty than other two baselines, In Table 2 linear noise format f1. and the right ones are under the Gaussian noise format f2. The variance is used to evaluate the stability of the trained policies, i.e. the robustness to system randomness. Because the testing experiments are done in the same environments that are initialized by different random seeds. We can see that, by using our RMAAC method, the agents can get the lowest variance in most of scenarios under these two different perturbation formats. Therefore, our RMAAC algorithm is also more robust to the system randomness, compared with the baselines. Due to the page limits, more experiment results and explanations are in Appendix C.2
the left three columns report the variance under the
5 CONCLUSION
We study the problem of multi-agent reinforcement learning with state uncertainties in this work. We model the problem as a 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 each associated adversary aims to minimize the reward. This problem is challenging with little prior work on theoreti- cal analysis or algorithm design. We provide the first attempt of 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 multi-agent& Q-learning algorithm (RMAQ) to 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 high-dimensional state-action space MARL problems. We also conduct experiments which validate our methods.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Mohammad Gheshlaghi Azar, lan Osband, and Rémi Munos. Minimax regret bounds for rein- forcement 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- methods applied mechanics and engineering, 196(33-34):3190, 1901-911, 2007.
Hans-Georg Georg Beyer and Bernhard Sendhoff. Robust optimization-a comprehensive survey. Computer
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, USA, 2004. ISBN 0521833787.
Jifí Čermák, Branislav Bošansky, and Viliam Lisy. An algorithm for constructing and solving imper- feet recall abstractions of large extensive-form games. In Proceedings of the 26th International Joint Conference Artificial Intelligence, pp. 936-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.
ladine Chades, Bruno Scherrer, and François Charpillet. A heuristic approach for solving decentrralized-pomdp:: Assessment the pursuit problem. In Proceedings of the 2002 ACM symposium on Applied computing, 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): 2022.
Vincent Conitzer and Tuomas Sandholm. Complexity results about nash equilibria. arXiv preprint cx/0205074, 2002.
Antonia Creswell, Tom White, Vincent Dumoulin, Kai Arulkumaran, Biswa Sengupta, and Anil Bharath. Generative adversarial networks: An overview. IEEE Signal Processing Magazine, 35(1): 53-65, 2018
Constantinos Daskalakis, Paul Goldberg, and Christos H Papadimitriou. The complexity of computing nash equilibrium. SIAM Journal Computing, 39(1): 195-299,,,999 2009.
Erick Delage and Yinyu Yc. Distributionally robust optimization under moment uncertainty with application to data-driven problems. Operations Research, 58(3):595-612, 2010. doi: 10.1287/ 1090.1090.
Jay L Devore, Kenneth N Berk, and Matthew A Carlton. Modern mathematical statistics with applications, volume 285. Springer, 2012.
Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Vlad Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, al. Impala: Scalable distributed deep-rl with importance weighted actor 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 -597, 2010.
Michael Everett, Björ Lütjens, and Jonathan P How. Certifiable robustness to adversarial state uncertainty in deep reinforcement learning. IEEE Transactions Neural Networks and Learning Systems, 2021.
Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Proceedings of the AAAI conference 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. 2062-2062. PMLR, 2019.
10

---

Under review as a conference paper at ICLR 2023
Eduardo Rodrigues Gomes and Ryszard Kowalczyk. Dynamic analysis of multiagent q-learning with exploration. 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 AAAI, volume 4, pp. 709-715, 2004.
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. arXiv preprint 0tt1::2209.08230. 2022.
Junling Hu and Michael Wellman. Nash q-learning for general-sum stochastic games. Journal of machine learning research, 4(Nov)::039-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 Picter Abbeel. Adversarial attacks on neural network policies. arXiv preprint arXiv://02.0220 2017.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is q-learning provably efficient? Advances in neural information processing systems, 31, 2018.
Leslie Pack Kaelbling, Michael L.. Littman, and Anthony R. Cassandra. Planning and acting in partially observable stochastic domains. Artificial Intelligence, 101(1):99-134, 1998. ISSN 0004-3702. doi: http:://ooooggloo///66oo0o444110 sciencedirect httpa//eee...teeeeeeeeeeeec///tp
URL https: //www
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, 2017.
Christian Kroer, Kevin Waugh, Fatma Kalinç-Karzunn 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. Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 661-670, 2014.
Shihui Li, Yi Wu, Xinyue Cui, Honghua Dong, Fei Fang, and Stuart Russell. Robust multi-agent reinforcement learning via minimax deep deterministic policy gradient. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4213 4213-4220, 2019.
Shiau Hong Lim and Arnaud Autef. Kernel-based reinforcement learning in robust markov decision processes. In International Conference Machine Learning, pp. 3973-3981. PMLR, 2019.
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- Wei Hong, Yuan- Liao, Meng-Li Shih, Ming- Yu Liu, and Min Sun. Tactics of adversarial attack on deep reinforcement learning agents. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, IJCAI'17, pp. 3756-3762. AAAI 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 Littman and Csaba Szepesvári. A generalized reinforcement-leanee learninngt-eeeinggggeee model: Convergence and applications. In JCML, volume 96, pp. 310-318. Citeseer, 1996.
11

---

Under review as a conference paper at ICLR 2023
Ryan Lowe, Yi I Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed coppeaaivv-compeetiie environments. Advances in neural information processing systems, 30, 2017.
Roger McFarlane. A survey of exploration strategies in reinforcement learning. McGill University. 2018.
Richard McKelvey and Andrew McLennan. Computation of equilibria in finite games. Handdoook of computational economics, 1:87-142, 1996.
Volodymyr Mnih, Koray Kavukcuoglu, et al. Human-level control through deep reinforcement
learning. nature, 518(7540):529-5333 2015.
Facundo Mémoli. Some properties of gromov-hausdort distances. Discrete & Computational Geometry, pp. 1-25, 2012. ISSN 0179-5376. URL http://dx doi, wtt..ooo.ooo.110777777// 400454-012-94055
10.10077s004544-122444444
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 q g-learning 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 to decentralized POMDPs, volume 1. Springer, 2016.
Martin Osborne and Ariel Rubinstein. course in gume theory. MIT press, 1994.
Guillermo Owen. Game theory. Emerald Group Publishing, 2013.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Guannan Qu and Adam Wierman. Finite-time analysis of asynchronous stochastic approximation and g-learning. Conference on Learning Theory, pp. 3185-3205. PMLR, 2020.
Hamed Rahimian and Sanjay Mehrotra. Distributionally robust optimization: A review. arXiv preprint arXiv: 0tt.//908...5555 2019.
Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Osband, Zheng Wen, al. A tutorial on thompson sampling. Foundations and Trends@ in Machine Learning, 11(1):1-9,, 2018.
Burkhard C Schipper. Kuhn's 's theorem for extensive games with unawareness. Available at SSRN 3063853, 2017.
Macheng Shen and Jonathan P How. Robust opponent modeling via adversarial ensemble rein- forcement learning. Proceedings of the International Conference on Automated Planning and Scheduling, volume 31, pp. 578 578-587, 2021.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of without human knowledge. nature, 550(7676):354 359, 2017.
Aman Sinha, Matthew O' O'Kelly, et al. Formulazero: Distributionally robust online adaptation via offline population synthesis. ICML, pp. 9992-9004. PMLR, 2020.
Slantchev. Game theory: Perfect equilibria in extensive form games. UCSD script, 2008.
David Roger Smart. Fixed point theorems, volume 66. Cup Archive, 1980.
Houshang H Sohrab. Basic real analysis, volume 231. Springer, 2003.
12

---

Under review as a conference paper at ICLR 2023
Chuangchuang Sun, Dong-Ki Ki Kim, and Jonathan How. Romax: Certifiably robust deep multiagent reinforcement learning via convex relaxation. arXiv preprint arXiv:2109.06795, 2021.
Richard S Sutton and Andrew G Barto. Reinforcement learning: an introduction mit press. Cambridge, MA, 22447, 1998.
Csaba Szepesvári and Michael Littman. A unified analysis of value-function-baat reinforcement- learning algorithms. Neural computation, 11()):2017-2000, 1999.
Chen Tessler, Yonathan Efroni, and Shie Mannor. Action robust reinforcement learning and applica- tions in continuous control. In International Conference on Machine Learning, pp. 0215-6224
PMLR, 2019.
Tessa van der Heiden, C Salge, Efstratios Gavves, and H van Hoof. Robust multi-agent reinforce- ment learning with social empowerment for coordination and communication. arXiv preprint arXiv:2012.08255. 2020.
John Von Neumann and Oskar Morgenstemn. Theory of games and economic behavior. In Theory of games and economic behuvior. Princeton university press, 2007.
Abraham Wald. Generalization of theorem by neumann concerning Annals of Mathematics, pp. 281-286, 1945.
person games.
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. ArXiv, 0as/2011.00558. 2020.
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.
Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of ppo in cooperative, multi-agent games. arXiv preprint arXiv:2103.01955, 202
Jing Yu, Clement Gehring, Florian Schäfer, and Animashree Anandkumar. Robust reinforcement learning: A constrained game-theoretic approach. Learning for Dynamics and Control, pp. 1242-1254. 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 on state observations. Advances in Neural Information Processing Systems, 13:21024-21033 2020a.
Huan Zhang, Hongge Chen, Duane Boning, and Cho-Jui Hsieh. Robust reinforcement learning on state observations with learned optimal adversary. arXiv preprint 20Xi::2001.08552 2021.
Kaiqing Zhang, Tao Sun, Yunzhe Tao, Sahika Genc, Sunil Mallya, and Tamer Basar. Robust multi- agent reinforcement learning with model uncertainty. Advances in Neural Information Processing 2020b.
Systems,
13

---

Under review as a conference paper at ICLR 2023
Supplementary Material for "Robust Multi-Agent Reinforcement Learning with State Uncertainty"
A THEORY
In this section, we give the full proof of the all propositions and theorems in the theoretical analysis of an MG-SPA.
Osborne & Rubinstein, 1994 Von Neumann Morgenstern 2007) whose payoff function is related to value functions of an MG-SPA. And, we give certain conditions under which, Nash Equilibrium for the constructed EFG exists, In section A.2
In section A.1 we construct an extensive-form game (EFG) (Bşarr & Olsder 1998
we prove the propositions 3.5 and 3.6
section we
give the full proof of Theorem
To make the supplemental material self-contained, we re-show the vector notations and assumptions we have presented in section 3.2 Readers can also skip the repeated text and go directly to section A.1
follow and extend the vector notations in Puterman (2014). Let V denote the set of bounded real valued funetions S with component wise partial order and norm || := supses [s'(s) Let Var denote the subspace of V of Borel measurable functions. For discrete state space, all real- real-valued functions measurable so that V VM. But when S is continuum, Var is proper subset of V. w²) ) E V be the set of bounded real valued functions on x ... x S, i.e. the across
Let v = (v",... ... product of N state and norm ||w|| sup, ||e||. I|. We also define the set and Q in similar style such that g² Q E Q.
For discrete S, let |S] denote the number of elements in S. Let rf denote |S] -vector, with sth component (s) which the expected reward for agent under state 8. And P the |S|] [S] matrix with (s, '')th entry given by p(s'(s) We refer to r as the reward vector of agent i, and Pa as the probability transition matrix corresponding to a joint policy d = (a, p). r pPad is the expected total one-period discounted reward of agent i, obtained using the joint policy = (T. p). Let & as list of joint policy {d), d2. ... and p I, we denote the expected total discounted reward of agent using as i. = Σ 1 p- 1r
rá, + Pa, Parrá, +... x- Pa, ... Pa., ri. +....
Now, we define the following minimax operator which is used in the rest of the paper.
Definition A.1. (Minimax Operator, same as definition 3.3) For E VV8 S, we define the nonlin- ear operator It' on (s)) by (f) == max,i min [ra Pav) where d == ( pT ,²). We also define the operator Lu(s) L(v (s). (s).... (s)) (L' ()(()))) (s). ... L N (s)). Then L' is a -vecto,, with sth component (s).
For discrete S and bounded r², it follows from Lemma 5.6. in Puterman 2014) that L'v V for all v' E V. Therefore Lu 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 as assumption 3.4
(1) Bounded rewards; (s, < M M for all N, a E A, be B and s S.
(2) Finite state and action spaces; all S A' B are finite.
(3) Stationary transition probability and reward functions.
(4) f a bijection when st is fixed.
(5) All agents share one common reward function.
A.1 EXTENSIVE-FORM GAME
An extensive-for form game (EFG) Başar & Olsder 1998 Osbore & Rubinstein 1994 Von Neumann
& Morgenstem) 2007) basically involves a tree structure with several nodes and branches, providing an explicit description of the order of players and the information available to each player at the time of his decision.
14

---

Under review as a conference paper at ICLR 2023
P1
$
$ SS
P2
a1
a IA
a
a A
Figure 6: team extensive-form game
Look at Figure 6 an EFG involves from the top of the tree to the tip of one of its branches. And centralized nature player (PI) has |Š| alternatives (branches) to choose from, whereas a 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 same as the agents' joint action set an MG-SPA, set S is set of perturbed state constrained by constrained parameter c. At the end of lower branches, some numbers will be given. These numbers represent the playoffs to the centralized agent (or equivalently, losses incurred to the centralized nature player) if the corresponding paths are selected by the players. We give the formal definition of an EFG we will use in the proof and the main text as follows:
Definition A.3. An extensive-form game based on (u',..- V.N. - - under E S is finite tree structure with:
1. A player P1 has action set Š = B(e,s) = B(c,s') x ... x Ble, s( with typical element designed as &. And P1 moves first,
2. Another player P2 has a action set A, with a typical element designed as a. And P2 which moves after P1,
3. specific vertex indicating the starting point of the game,
4. a payoff function (5 a) (g) a).... -h (š, a)) where (5( a) = r'( a, fz) Ev p(s (0, f. (3))e' assigns real number to each terminal vector of the tree. Player P1 gets (9, a) while player P2 gets ga (3, a).
5. a partition of the nodes of the tree into two player sets (to be denoted by N2 and N2 for PI and P2, respectively),
6. sub- sub-partition of each player set No into information set {n) )- 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 (b) == =(sssb b) = [f(s",b8 ...................... ...,.. .(.N 6%) ) is the vector version of the perturbation function f in an MG-SPA. Since in an MG-SPA, (s(s, a, = (s, a, Eg p(s')s, a, b)v" (s') for all i = 1.... N. g. (5, a) g' gs, f= (3)) well. We can also use (q) .... .q" -g- - ) to denote an extensive-form game based on (u',.. .....,,. " - -..,.... behavioral strategies for P1 and P2, respectively in the following definition.
N). Then we define the
Definition A.4. (Behavioral strutegy) Let I' denote the class of all information sets of Pi, with typical element designed as n². Let Us xt denote the set of alternatives of Pi at the nodes belonging to the information set n².. Define U = UUB where the union is over 1f² E It. Let Yu: denote the set of all probability distributions on U,,, where the latter is the set of all alternatives of P1 at the nodes belonging to the information set r Analogousty, let Zna denote the set of all probability distributions on UZz,. Further define Y = Up Up Z = Up Znp. Then, a behavioral strategy X for P1 is mapping from the class of all his information sety 1 into Y, assigning one element in Y for
15

---

Under review as a conference paper at ICLR 2023
each set in I', such that X(n') Yop for each n/' E II. A rypical behavioral strategy x x. P2 is defined, analogously, restricted mapping from I into Z. The set of all behavioral strategies for Pi is called his behavioral strategy set, and it is denoted by I".
The information available to the centralized agent (P2) at the time of his play is indicated on the tree diagram in 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 Pl is a mapping from his information sets and action space into probability simplex, i.c. X(ā)s) s) is the probability of choosing ă given s. Similarly, the behavioral strategy X for P2 is x(a [8), i.e the probability of choosing action a when š is given. Note that every behavioral strategy is mixed strategy. We then give the definition of Nash Equilibrium in behavioral strategies for an EFG.
Definition A.5. (Nash Equilibrium in behavioral strategies) A pair of strategies {Aa ET' Xx r is said to constitute a Nash Equilibrium in behavioral strategies if the following inequalities are satisfied that for all i = N, X E TL, x 82,
J' .x..xxx,x)) 2 J X- xxxx59) J'
(6)
where J²(A, x) is the expected payoff iee. - -xx10 when P1 takes X, P2 takes X x(((s) Ix=1x'(8 r[als) = =
In the following parts well as the main text, when we mention a Nash Equilibrium for an EFG, it refers to a Nash Equilibrium in behavioral strategies. How to solve an EFG is out of our scope since it has been investigated in many literature (Başar & Olsder 1998 Schipper 2017] Slantchev] 2008). And the single policies A and x² can be attained through the marginal probabilities calculation with chain rules (Devore et al. 2012 Mémoli 2012).
Lemma A.6. Suppose (v) .o,NN -u0 -U'. N exists.
N.N. and S, A are finite. An NE (Ae: of the EFG based on
Proof. Since S is subset of S, S is finite when S is finite. When v² are finite, an EFG based on (vi,... ....,,,, _ - ) degenerates to a zero-sum two-person extensive-fome game with finite strategies and perfect recall. Thus, an NE of this EFG exists (Başar & Olsder 1998 Schipper 2017 Slantchev| 2008).
v., and S, A
Lemma A.7. Suppose f is a bijection when s² is fixed for all i --li=1 =i,,.... 1,..., N. For an EFG (ul,... ..N. -v! -v..... -u") with NE (xx.X.), we call a joint policy (m". as the joint policy implied from the NE X.). where (b(s) = (. = fa(b)ss), ... (al3 = fa(b))= = =x.(a()) The
joint policy (x%, p.) satisfies (s) ((rs,s) (8) + > Pis ( (8'(s)0 (8') for all E S.
Proof. The NE of the extensive-form game (A.,x.) implies that for all i == 1, N,SESSA T1. X E 2 we have
J'(A,x)) 2 J' xx), 2 J((),,)))
where ('(A,x) -Ep' & a, f- + (i))
X(-1s), x(-13)
according to Definition A.5 Let b denote f- (3), because is a bijection when of is fixed
for all = 1.... N, fa(b) = (b),,, ............ .fx (b))) is a bijection, and the inverse function f. (3) = (5*), .f (5 exists and a bijection as well, then we have
-A,,,..)) =E
r as, (3)) Σ
- xx(13)
E
r () + p(s'ls, [ubllaaaaae((0000-0000000000 (-15-(0))
E
r (s, a, b) + Σ 0161
16

---

Under review as a conference paper at ICLR 2023
Similarly, we have
-A,,,, =)= R
r (s, + Σ
-A((Axx)) = E
(((,,, + Edldlo, a,,l,,,,, p² (-16) (-(3)))
Recall the definition of the minimax operator of (s), we have, for all Es
L'v'(s) ri pt) (8) + ?
Σ s'ES
(G
Based on the proof, we also denote (m", p=) as an NE policy for the EFG (ul,... v. -v?, ) for convenience, instead of calling the joint policy derived from an NE for the EFG (ut,-.. v -u --
A.2 PROOF OF TWO PROPOSITIONS
Proposition A.8. (Contraction mapping, same as proposition 3.5 in the main text.) Suppose 0 S and Assumption 3.4 hold. Then L is a contraction mapping on V.
Proof. Let u and v be in V. Given Assumption 3.4 these two EFGs (u' ................................ (u'..... V -v²
- ) both have at least one mixed Nash Equilibrium according to Lemma A.6 And let (T p.) and (x", p²) be two Nash Equilibrium for these two games, respectively. According to Lemma A.7 we have the following equations hold for all E S.
..... -.r....
('oo(s) = (arr,r)) (8) +
(s ( (s'(s)) (s))
Σ #'ES
L'u'(s) or (5) +
Σ
P(rr (s'1s)u
Then have (s)) (8) +
Σ
P( Po (5'1)) ('))(s) s r (1) + Σ (=)))))))
S'ES
d'ES
(1)) (s) +7 Σ P(az (s((s) (s') s L'u S (()))))))) + (s (s)(
s'ES
since (Th and (T" p.) are derived from the Nash Equilibrium of the EFG
(u',... V. -ui,... -u ), and (m p²) and (m" also derived from the Nash Equilibrium
of the EFG (u',... W. u -u We assume that L'v((s) S L'u((s), then we have
S (s) - (s)
(1) + Σ (0 - - (orr)op)(()) (or
eEES
59 Σ (s (s') - v'(s
RES
< <>||0" w'll
Repeating this argument in the case that L' L'u'(s) I L'oo implies that
[|L'v'(s) L' n² [s)) < 7/|b - w'll
for s S, i.c. L' is a contraction mapping on V. Recall that [|ø|] = sup, || then we have
Le LuI| sup // L'w'l || < 7 sup I|ll - =w'll = 7/1c u|]
;
)
a contraction mapping on V.
17

---

Under review as a conference paper at ICLR 2023
Proposition A.9. (Complete Space, same as proposition 3.6 in the main text.) V is complete normed linear space.
Proof. Recall that V denote the set of bounded real valued functions on S ..... x i.c the across product of N state set with component-wiss partial order and norm ||||| := supses sup, |e (s)). Since V is closed under addition and scalar multiplication and endowed with norm, it is normed linear space, Since every Cauchy sequence contains a limit point in V. V is complete space.
A.3 PROOF OF THEOREM 3.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.I Then we prove that a unique solution of the Bellman Equation exists 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 2.V-player Extensive- form game (EFG) (Osborne Rubinstein 1994. Von Neumann & Morgenstern (007) 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 AA.344
In this section, our goal to prove Theorem 3.7
Theorem A.10. (Same theorem the main text.) Suppose 0 Y and Assumption 3.4
holds.
(I) (Solution of Bellman Equation) A value function v, V is optimal value function if for all i E N, the point-wise value function v., E satisfies the corresponding Bellman Equation 2 i.e. r 12' for all i E N.
(2) (Existence and uniqueness of optimal value function) There exists a unique v. E V satisfying Le,- Uv, Lee. for all i N, L'vl vi-
(3) (Robust Equilibrium (RE) and optimal value function) joint policy d, = (T P.). where
n. (mi.....,, and pa = (p_, .N) ), is robust equilibrium if and only if od is the optimal value function.
(4) (Existence of Robust Equilibrium) There exists mixed RE for an MG-SPA.
A.3.1 (1) SOLUTION OF BELLMAN EQUATION
Proof. First, we prove that if there exists a E V such that 0² > Lo then of 2 vf. o² > Lo implies o' 2 max min[r" + PPu' = =
+yaa', where d = (x=-,,, T p .P "p:")) is Nash Equilibrium for the EFG v (v² ,... N. --0,, -v.). We omit the superscript for convenience when there no confusion. We choose list of policy i.e. = (d1,d2,...) where d, = (TT m) PT , Then we have
o' 2 rá, + Pa, o² rá, + PP, (rá, + +PPa = =ră 7PParrá + 7 Paj
By induction, it follows that, for 2 1,
2 d1 P
Pap rd
7 n- .PP,, rd. + + p
0' - 2 2 7" P 0²
pl 2
t=n
Since "|> u S 1 and 7 E [0, 1), for > O, we can find a sufficiently large n such that
te/2 2 " pm 2 -Ee/2
(8)
where denotes vector of I's. And as result of Assumption 3.4 (1), we have
P!r Pi 22 2 Me
Σ
(9)
1-7
18

---

Under review as a conference paper at ICLR 2023
Then we have
- (1(()) 2 -e
(10)
for all 8 E and > 0. Let all d, the same, since e was arbitrary, we have
(s) 2 max min v (s) = (s)
(11)
Then we prove that if there exists a of E V such that of S Lo then v² S vt. For arbitrary there exists joint policy d' = (T, m P. p¹) and a list of policy = (d' d' ..) such that
v¹ S Pa' +e
(T-PPa)o' r
s 7 Pa' )ar)-1r - + (1- =0 +1 7)
$ v + (1 7)
The equality holds because the Theorem 6.1.1 in Puterman (014). Since e was arbitrary, we have
(12)
So if there exists a vf E such that o² of i.e. o² L and v² 2 L'v we have of w i.e.
if of satisfies the Bellman Equation, of is an optimal value function.
A.3.2 (2) EXISTENCE OF OPTIMAL VALUE FUNCTION
Proof. Proposition 3.5 and 3.6 establish that V is a complete normed linear space and L contraction mapping, so that the hypothesis of Banach Fixed-Point Theorem are satisfied (Smart 1980). Therefore there exists a unique solution v, E V Lu v. From (1), we know if v, satisfies the Bellman Equation, it is an optimal value function. Therefore, the existence of the optimal value function is proved.
A.3.3 (3) ROBUST EQUILIBRIUM AND OPTIMAL VALUE FUNCTION
Proof. Robust Equilibrium Optimal value function.
Suppose d" is robust equilibrium. Then od = From (2), it follows that od satisfies Lu Thus gd is the optimal value function.
(ii) Optimal value function - Robust Equilibrium.
Suppose od the optimal value function, i.e., Lyd" = "d" The proof of (1) implies that ad so d' is in robust equilibrium.
A.3.4 (4) EXISTENCE OF ROBUST EQUILIBRIUM
Proof. From (2), we know that there exists solution E V to Bellman Equation Le v. Now, N ). Under Assumption 3.4 we can get an NE
consider an EFG based on (u ... N - -
policy ( -p+)) by solving the EFG as consequence of Lemma A.6 According to Lemma A.7 (T= p²-) satisfies
L'v((s) = ((a (s) (8)+ + Pa (271
s'ES
for all s S. According to (3), ,-') is Robust Equilibrium.
19

---

Under review as a conference paper at ICLR 2023
B ALGORITHM
B.1 ROBUST MULTI-AGENT Q-LEARNING (RMAQ)
In this section, prove the convergence of RMAQ under certain conditions. First, let's recall the convergence theorem and certain assumptions.
Assumption B.1. (Same as assumption 3.8) (1) State and action pairs have been visited infinitely often. (2) The learning rate 04 satisfies the following conditions: S at < 1, Σ120 of S oc; if
(s, b) & (st, Qe, b.), on(s, = 0. (3) An NE of the EFG based on (q..... .. , -.......
exists each iteration
Theorem B.2. (Same as theorem 3.9
Under Assumption B.1 the sequence {qe obtained from
converges } with probability 1, which are the optimal action-value functions that satisfy
Be Bellman equations ① for all i 1 , N.
d ar, bx)= = (s)
(13)
al) +y Σ Σ
( (1 (641)) (er
ai
b
Proof. Define the operator Tq: = T(g.. , = (T* ... g where the operator T is defined as below:
b) = +2+7 +7 Σ Σ
T 3a' (a'l8') (1 d'
(14)
d'EAVEB
for i E N, where (T p is the tuple of Nash Equilibrium policies for the EFG based on (g..... gi -4
of obtained from (3). Because of proposition B.3 and proposition B.4
the Lemma 8 in Hu & Wellman (2003) or Corollary in [Szepesvári & Littman (9999 tell that 0++1 (1 at + a,T'g g, converges to q. with probability
Proposition B.3, (contraction mapping) Tq: = (f) ... N .NNgNN is a contraction mapping.
Proof. We omit the subscript when there is no confusion. Assume T'pp 2 T''', we have
0 T' p' q'
Σ Σ
:5(d'
ΣΣ
d'EANEB
d'EAVEB
Σ Σ A1
Σ Σ 2((11))2((00)000)
d'EADEB
REAVEE
Sy ST/lp' -'ll.
(15)
Repeating the case T''p' < T implies that 7 is contraction mapping such that ||T'p' T' >llp' - q"1 for all p¹, q¹ E Q. Recall that |p all = sup, ||p] - q'll
s
[TP - Tall = sup 1T'
T T S sup Ipp' - qill = > - al1
T' is contraction mapping such that |Tp - Tall s >1pp q for all p. Q
Proposition B.4. (a condition of Lemma 8 in Hu & Wellman 2003 also Corollary 5 in Szepesvári Littman 1999))
== = ETg.
(16)
20

---

Under review as a conference paper at ICLR 2023
Proof.
R r² + Σ
Σ
a' M'n brin
= + y Σ p(s'|s,
Σ
s'E8
d'EAKEB
= 2 (s,
(17)
Therefore g. [T
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 follows:
Theorem B.5. (Policy Gradient in RMAAC for MG-SPA, same the theorem 3.10 For each agent and adversary i 1, N, the policy gradients of the objective J' w) with respect to the parameter 0, are:
((,,W 1
Σ
Va:q' (st, a, Vo (()))))))))(
(18)
T
Σ
Vo.q'( ar, bi) + reg]
(19)
where reg = Vb (s) V. ar b,) \
Proof.
V Jo (0,,)) Bampirtes
Von'(s,
V\ (3'),
(20)
J', = EAMPtEN.S
(wig'(s,a,
-ESMPETiP
Varg'ss,
(6' wi ( + V, p'
[V Vo.gg (s, b) + reg]]
(21)
where reg- Vaig (8, a,
V) 2
(( BA). When the actors are updated in mini-batch
fashion (Mnih et al. 2015 Li et al.
2014). 18 and 19 approximate 20 and (21) respectively. O
B.2.2 PSEUDO CODE OF RMAAC
We provide the Pseudo code of RMMAC in Algorithm
21

---

Under review as a conference paper at ICLR 2023
Algorithm 1: RMAAC
Randomly initialize the critic network (s, a, 6/7"), the actor network n' (s" and the adversary network p' (s*|w*) for agent i. Initialize target networks q", x² p²: for each episode do Initialize random process N for action exploration;
Receive initial state s;
for each time step do
For each adversary i, select action 6' = p's") + W w.r.t the current policy and
exploration. Compute the perturbed state g² = [(s 1t). Execute actions
a' π (33) + and observe the reward r (r' ..... r") and the new state information s' and store(s, a, b, 5, s') in replay buffer D. Set s' + for agent i=/ to do
Sample random minibatch of K samples (sk, ak, bk, The s/,) from D; Set v/ = ri + 70" (5%,, (4)lag- =((3))) -x(())))
Update critic by minimizing the loss L = * Ex [vL ( an, bx))
for each iteration step do
Update actor TI' (-100) and adversary of (-Iw²) using the following gradients
0 +- 0² Oaa K ΣB ( "o'gg((s (Sk, as, by) where of x' x5%))
6% = p'(ss)
w¹ t- w -ob Σx Veip' (st) (o. (5R, ax, bu) + reg] where
reg Voz o² (sk: ab. bu) V r' (3)). of = (3)). bj. (s
15
end end
16
Update all target networks: 0² + 70t + (1 - T)0", wt + Tw" + (1 T)W".
17
18
end
end
22

---

Under review as a conference paper at ICLR 2023
C EXPERIMENTS
C.I ROBUST MULTI-AGENT Q-LEARNING (RMAQ)
In this section, we first further introduce the designed two-player game that the reward function, transition probability function are formally defined. The MG-SPA based on the two-player game is also further explained. Then we show more experimental results about the proposed robust multi- agent Q-learning (RMAQ) algorithm, including the training process of the RMAQ algorithm in terms of the total discounted rewards, the comparison of testing total discounted rewards when using different policies with different adversaries.
C.I.1 TWO-PLAYER GAME
a' = a² ==
a # a 0
a = a² r 0
SO
S
# a =
Figure 7: Two-player game: each player has states and the same action with size 2. Under state so, two players get the same reward when they choose the same action. At state 81, two players get same reward 1 when they choose different actions. One switches to another state only when two players get reward, i.c. two players always stay in the current state until they get reward.
Look at Figure 7 run. The reward function r and transition probability function are defined in follows.
(same as Figure in the main context.), this is how the designed two-plas wwoplayerr game
3
These two players get same rewards all the time, i.e. they share reward function r.
1, a² = aa, and 80
1, a' * a², and $1
r' (s.aa
=
0, a² + a² and 80
(22)
0, a a² and 31
The state does not change until these two players get positive reward. So the transition probability function is
a = a², and s = 80
0, a' = a² and s 8p
0, a' 4 a², and
1. a + a² and s
1, a = a², and s = p(so|s,a' al,,,a',a" a??
0. al = a² and s
0, a + a² and
1. al + a² and
(23)
Possible Nash Equilibrium can be πi (m] mi) nh (TT), T3) where
1, a 1, and 80
1, a² 1, and 80
0, a 0, and so
0, a² 0, and Su
(aals))
(24)
1, 1, and s 81
0, a² 1, and 81
0, = 0, and s = $1
1, a = 0, and 5 = $1
0, a 1, and so
0, a 0, and 50
1, 0, and & so
1, 2 1, and $p
(a(())))
(a)
(25)
0, = 1, and s = $1
1, a = 0, and = 81
1. = 0, and s = $1
0, a = 1, and s = 81
23

---

Under review as a conference paper at ICLR 2023
NE γi means player always selects action 1, player selects action 1 under state so and action 0 under state $1. NE z2 means player always selects action 0, player 2 selects action under state 80 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 same action space B' = B = f0, 1]. where 0 means do not disturb, means change the observation to the opposite one. Therefore, the perturbed function in this MG-SPA defined
(s0, b = 0)
M(s,, = 0) = 81
(26)
f(00, b = 1)
f(81,b== = 1) 80
Obviously, f is bijective function when 8f is given. And the constraint parameter = ||5||, where ||||| max [s s' s'sss i.e. no constraints for adversaries' power.
Robust Equilibrium (RE) of this MG-SPA would d'
(w m, pr, P2), where
(s = 0.5,
vs E S
(2(d))s) 0.5,
Vs E S
(27)
(b(1sss) -0.5, (b9))s 0.5, Vs E S
Vs E S
C.1.2 TRAINING PROCEDURE
In Figure 8 we show the total discounted rewards in the function of training episodes. We set learning rate as 0. and train our RMAQ algorithm for 400 episodes. And each episode contains 25 training steps. We can the total discounted rewards converges to 50, i.c the optimal value in the MG-SPA, after about 280 episodes or 7000 steps.
Total Discounted Rewards when Training
values
30
10
50
100
150
200
250
300
350
400
training episodes
Figure 8: The total discounted rewards converges to the optimal value after about 280 training episodes.
C.1.3 TESTING COMPARISON
We further test well-trained RE policy when 'strong' adversaries exists. 'Strong' adversary means its probability of modifying agents' observations is larger than the probability of no perturbations in state information. We make two agents play the game using 3 different policies for 1000 steps under different adversaries. And the accumulated rewards, total discounted rewards are calculated. We use the Robust Equilibrium (of the MG-SPA), the Nash Equilibrium (of the original game) and baseline policy and report the result in Figure 9 The vertical axis is the accumulated/discounnet reward, and the horizon axis is the probability that the adversary will attack/perturb the state. And we let these two adversaries share same policy. We see the probability increase, the accumulated and
24

---

Under review as a conference paper at ICLR 2023
discounted rewards of RE agents are stable but those rewards of NE agents and baseline agents keep decreasing. This experiment is to validate the necessity of RE policy which is not only robust to the worst-case adversarial state uncertainties, but also robust to some worse but note the worst cases.
Total Discounted Rewards
Total Rewards
discounted rewards
total rewards
40
400
300
RE
RE
NE
NE
20
100
BS
0.55
05
0.5
0.
0.5
01
075
0.5
0.65
05
06
0.65
0.7
0.5
09
0.5
attack probability
attack probability
Figure 9: RE policy outperforms other polices in terms total discounted rewards and total accumu-
lated rewards when strong adversaries exist.
25

---

Under review as a conference paper at ICLR 2023
C.2 ROBUST MULTI-AGENT ACTOR-CRITER (RMAAC)
In this section, we first briefly introduce the multi-agent environments we use in our experiments. Then provide more experimental results and explanations, such as the testing results under 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 hyper- parameters we used in the experiments, as well as the baseline source code.
C.2.1
MULTI-AGENT ENVIRONMENTS
agent 2
agent 1
predator
predator 2
"blue"
agent
predator
"red"
agent
(a)
agent
(b)
(c)
prey
agent
agent 2
speaker
agent
"blue"
adversary
agent 2
x
+ ?_...
listener
X
adversary
(d)
(e)
Figure 10: Illustrations of the experimental scenarios and some games we consider, including a)
Cooperative communication b) Cooperative navigation c) Predator prey Keep away e) Physical deception f) Navigate communication
Cooperative communication (CC): This is a cooperative game. There are 2 agents and landmarks of different colors. Each agent wants get their target landmark, which known only by other agent. Reward is collective. So agents have to learn to communicate the goal of the other agent, and navigate their landmark.
Cooperative naviga navigation (CN): This is cooperative game. There are 3 agents and 3 landmarks. Agents rewarded based how far any agent is from each landmark. Agents are penalized they collide with other agents. So, agents have to learn to cover all the landmarks while avoiding collisions.
Physical deception (PD): This is mixed cooperative and competitive task. There are collaborative agents, 2 landmarks, and 1 adversary. Both the collaborative agents and the adversary want reach the target, but only collaborative agents know the correct target. The collaborative agents should learn policy to cover all landmarks so that the adversary does not know which one the true target.
Keep away (KA): This is competitive task. There is I agent, adversary, and landmark. The agent knows the position the target landmark and wants to reach it. Adversary is rewarded if is close to the landmark, and if the agent is far from the landmark. Adversary should learn to push agent away from the landmark.
Predator prey (PP): This is mixed game known predator-prey. Prey agents (green) are faster and want to avoid being hit by adversaries (red). Predator are slower and want to hit good agents. Obstacles (large black circles) block the way.
Navigate communication (NC): This is a cooperative game which is similar to Cooperative communication. There are 2 agents and landmarks of different colors. A agent is the 'speaker' that does not move but observes goal of other agent. Another agent is the listener that cannot speak, but must navigate correct landmark.
26

---

Under review as a conference paper at ICLR 2023
Predator prey+ (PP+): This is extension of the Predator prey environment by adding more agents. There are 2 preys, 6 adversaries, and 4 landmarks, Prey agents are faster and want to avoid being hit by adversaries. Predator slower and want to hit good agents. Obstacles block the way.
C.2.2 EXPERIMENTS SAPER-PARAMETERS
In Table we show all hyper- parameters we use to train our policies and baselines. We also provide our source code in the supplementary material. The source code of M3DDPG (Li al., 2019) and MADDPG (Lowe et al. 2017) 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 this license refers to https: http///gttttuuueeeeeee cww/openalaooooooooooooooe...... h/aadppg and https://g com/ wttp//aaaaaccddd/d/mnmmmmaooa
Table 3: 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 number of hidden unites per layer number of samples per minibatch
106
106
106
2
2
2
Relu
Relu
Relu
64
64
64
1024
1024
1024
target network update coefficient iteration steps
0.01
0.01
0.01
20
20
20
constraint parameter episodes in training time steps in episode
0.5
/
10k
10k
10k
25
25
25
C.2.3 MORE TESTING RESULTS
In this subsection, we provide the testing results under cleaned environment (accurate state informa- tion can be attained) and randomly disturbed environment (injecting standard Gaussian noise into agents' observations).
In Figure II we show the comparison of mean episode testing rewards under cleaned environment by using 4 different methods, RMI denotes our RMAAC policy trained with the linear noise format f1. RM2 denotes our RMAAC policy trained with the Gaussian noise format S2, MA denotes com/ wpwnai/madddp...oooooppppoeoooop M3 denotes M3DDPG (hitps:// We can see only in the Predator prey scenario, our method outperforms others under cleaned environment. In Figure 12
MADDPG (https:
github. com/ http:///aaaaaddddddd////aaaaaaap /
method outperforms others in the Cooperative communication, Keep away and Predator prey scenarios, and achieves similar performance as others the Cooperative navigation scenario under randomly perturbed environment. In Table 5 we also report the variances of testing rewards in different scenarios under different environment settings. Our method has lower variance in three of five scenarios.
This kind of performance also happens in robust optimization (Beyer & Sendhoff 2007 Boyd Vandenberghe, (2044) and distributionally robust optimization (Delage & Yel 2010 Rahimian & Mehrotra (2099) that the robust solution outperforms other non-robust solutions
worst-case scenario. Similarly, for single-agent RL with state perturbations, robust policies perform better compared with baselines under state perturbations Zhang et al. (2020b). But 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 single agent RL problem Zhang et al. (020b). Improving the robustness of the trained policy may sacrifice the performance of the decisions when the perturbations or uncertainties do not happen. That's why our RMAAC policies only beat all baselines in one scenario when the state uncertainty is eliminated. However, for many real-world systems
27

---

Under review as a conference paper at ICLR 2023
Cleaned Env
Cleaned Env
Cleaned Env
Cleaned Env
Cleaned Env
100.0
Mean Epicode Testing Rewards
05
Mean Episode Testing Rewards
RM1
Mean Episodo Testing Rewards
97.5
RM1
Mean Episode Testing Rewards
110
NJ
MJ
MA
MA
MA
95.0
MA
100
M4
30
110
92.5
90
a5
90.0
80
80
50
Mean Episode
106
87.5
70
45-
104
75
82.5
30
70
83.0
40
GC
CN
PD
KA
PP
Figure 11: Comparison of episode mean testing rewards using different algorithms and different perturbation functions, under cleaned environments.
Randomly
Randomly
Repdomly Perturbed Ragdomly Perturbed
Randomly
Mean Epicode Testing Rewards
90
Mean Episode Testing Rewards
RM2
RML
Mean Epicode Testing Rewards
Meen Episode Testing Rewards
Mean Episode Testing Rewards
RM2
M3
MS
MB 1A
85
MA
MA
MA
MA
1266
88
1.4
87
5
60
100
Figure 12: Comparison of episode mean testing rewards using different algorithms and different perturbation functions, under randomly perturbed environments.
can not assume the agents always have accurate information of the states. Hence, improving the robustness of the policies is very important for MARL explained in the introduction of this work. It is worth noting that our RMAAC policies also work well in environments with random perturbations instead of worst-case perturbations. As shown Fig. 12 the performance of our RMAAC policies outperforms the basclines in most scenarios when random noise is introduced into the state.
MAPPO is a multi-agen reinforcement learning algorithm which performs well in cooperative multi-agent settings (Yu al. 2021a). We use MP denote MAPPO (https: //::::///iii qithubtthuu. com/ cy )- In Figure 13 we compare its performance with our RMAAC algorithm two cooperative scenarios of MPE. The details of scenarios such as Cooperative navigation, Navigate communication
marlbenchmarde
be found in the last section. We see that under the optimally perturbed environment, RMAAC outperforms MAPPO all scenarios.
In Figure 14 and Table 6 we compare the episode mean testing rewards and variances under different environments the complicated scenario with a large number of agents between different algorithms. method has lower
We adopt Gaussian noise format in training RMAAC polices. We can variance under two of three environments and has the highest rewards under all environments.
Table Variance of testing rewards under cleaned environment
Algorithms
RM with
RM with fz
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
28

---

Under review as a conference paper at ICLR 2023
Table 5: Variance of testing rewards under randomly perturbed environment
Algorithms
RM with /i
RM with /2
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
Gaussian Noise
Gassian Noise
50
RM
84
RM
Mean Episode Testing Rewards
Mean Episode Testing Rewards
45
MP
MP
40
80
35
78
30
76
25
74
20
70
CN
NC
Figure 13: Comparison of episode mean testing rewards using MAPPO and RMAAC under optimally perturbed environments.
Optimally Perturbed Env
Cleaned Env
Rangomly Perturbed Env
89
90
RM
RM
RM
Mean Episode Testing Rewards
88
M3
Mean Episode Testing Rewards
M3
Mean Episode Testing Rewards
84.0
M3
87
MA
88
MA
83.5
MA
86
83.0
86
85
82.5
84
83
81.5
82
82
81.0
81
80.5
80
80
80.0
PP+
PP+
PP+
Figure 14: Comparison of episode mean testing rewards using different algorithms under different environments in Predator prey+.
Table 6: 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
29

---

Under review as a conference paper at ICLR 2023
C.2.4 TRAINING RESULTS USING LINEAR NOISE WITH DIFFERENT CONSTRAINT PARAMETERS
Training Sctup: In this subsection, we train several RMAAC policies using linear noise format as the state perturbation function, i.c. fi (1s', 66) st + b The constraint parameter is respectively set as unchanged. Other used seper-paraeetess
0.01, 0.05, 0.1, 0.5, 1 and 2, given other
can be found in Table X
Training Results: In Figure 15
16 and we show the training process in three scenarios:
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 episode rewards RMAAC can achieve. However, RMAAC has different sensitivities to the value of variance in different scenarios. When
see that, in general. the smaller the used variance, the higher the mean
c 2, the RMAAC policies have the lowest mean episode rewards in all three scenarios. Nevertheless, when we use 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 = 2, i.e. Performance(s = 0.5) 2 Performance(e = 1) > Performance(e = 2). The performance the RMAAC policies is close when the constraint parameters are less or equal to than 0.1.
C.2.5 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 Teest is trained with the linear noise format (1(s (²) s + 6i, constraint parameter is 0.5, where 1/ Plest (s*le 0.5). The policy Plest is adversary i's policy which is trained with teest in RMAAC, for all i I..... N. We use Pteat to denote the joint policy of adversaries which is used in the testing. In summary, we test agents' joint policy Tisemarion when adversaries adopt the joint policy Piest accenorio (s|c), and = 0.01, 0.05, 0.1, 0.5, 1, 1, scenario Cooperative communication (CC), Cooperative navigation (CN), Predator Prey (PP), respectively. The testing conducted over 400 episodes, which each episode has 25 time-steps.
Testing Setup:
20 we compare the performance of RMAAC, M3DDPG, and MADDPG in scenarios CC, CN, and PP with different values of constraint parameters. MADDPG 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 19 anndd22
From these figures, we can see that in all three scenarios, our RMAAC policies outperform the baseline MARL 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.
C.2.6 TRAINING RESULTS USING GAUSSIAN NOISE WITH DIFFERENT VARIANCE
Training Setup: In this subsection, we train several RMAAC policies using Gaussian noise format as the state perturbation function, i.e. [2(+", b²) = + Nb'',, .). The variance a is respectively set as 0.001, 0.05, 0. 0.5, 1, 2 and 3, given other hyper-parameterrs unchanged. Other used hyper- parameters can be found in Table 3
Training Results: In Figure 21 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 reward of the agents and the x-axis denotes the training episodes.
From the figures we can see that, in general, the smaller the value of variance is used, the higher the mean episode rewards RMAAC can achieve. However, RMAAC has different sensitivities to the value variance in different scenarios. When we use a = 3, the RMAAC policies have the lowest mean episode rewards in all three scenarios. Nevertheless, when use the smallest magnitude 0.001,
30

---

Under review as a conference paper at ICLR 2023
the trained RMAAAC policies do not always achieve the highest mean episode rewards. In these three scenarios, it clear to see the performance of RMAAC using о = 1 is better than or close to that of using 2, and better than that of using = 3, i.. Performance(r Performance(a = 3). The performance of the RMAAC policies is close when the constraint parameters are less than equal to 0.5.
1) 2 Performance(o 2)
C.2.7 TESTING RESULTS USING GAUSSIAN NOISE WITH DIFFERENT VARIANCE
In this subsection, we test adopt Gaussian noise format and different variances.
RMAAC policies in perturbed environments where adversaries
Testing Setup: The tested policy Ftest is trained with Gaussian noise format fa(s", of N 1), constraint parameter is 0.5, where 6² Prest(" policy which trained with Test in RMAAC, for all i 1, .N. We use Ptest denote the joint policy of adversaries. In summary, we test agents' joint policy Iiest masenorio when adversaries adopt the joint policy Pieet pccenorio (s|c 0.5) and Gaussian noise format f2(s", b²) = N(b o),
0.5). p¹ is adversary i's
where o = 0.001, 0.05, 0.5, 3 1, 2, 3, scenario = Cooperative communication (CC), Cooperative navigation (CN), Predator Prey (PP). The testing is conducted over 400 episodes, which each episode has 25 time-steps.
Testing Results: In Figures 24
25 and 26 we 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 a MARL baseline algorithm. M3DDPG is a robust MARI. baseline algorithm. The y-axis denotes the mean 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 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 Gaussian noise format with different values of variance.
C.2.8 TESTING RESULTS UNDER DIFFERENT STATE PERTURBATION FUNCTIONS
In this subsection, we test the well-trained RMAAC policies in perturbed environments where adversaries adopt different noise formats and policies.
The tested agents' joint policy teest is trained with Gaussian noise format f2(8", bi) + Gaussian(b', = 1), constraint parameter is 0.5, where = Prese = 0.5). Pleat is adversary i's policy which is trained with Trest in RMAAC, for all = 1, 1.... .N. We use Prest to denote the joint policy of adversaries. In summary, we test agents' joint policy Test necenoria when adversaries adopt the joint policy pecenario (|cc = 0.5), in three scenarios scenario Cooperative communication (CC), Cooperative navigation (CN), Predator Prey (PP), under non-optimal Gaussian format fa. Uniform noise format S4. fixed Gaussian noise format fs and Laplace noise format fo. respectively. These noise formats are defined the following:
Testing Setup:
fa(s), 6) = Gaussian(( where 6² optimatt(s
/4(8", 18) = 5¹ -Uniform(-et --e +e),
fa(s), 18)
GGaussian(O.11 1),
fa(s), b3) = s¹ Laplace(b',, 1) where bi (
(28)
where / Pnon- is non-optimal policy of adversary 7. phon Phon- Pnon-optimal the training process. As we
optimal is randomly chosen from that fs and fs are independent of the optimal joint policy of adversaries, but fa and fe are not. The testing is conducted over 400 episodes, which each episode has 25 time-steps.
Testing Results: In Figures 27 28 and we compare the performance of RMAAC, M3DDPG and MADDPG in scenarios Cooperative communication, Cooperative navigation and Predator Prey under
31

---

Under review as a conference paper at ICLR 2023
4 different noise formats, respectively. MADDPG is a MARL baseline algorithm. M3DDPG is robust MARL baseline algorithm. The y-axis denotes the mean episode reward of the agents.
As can from these figures, most of the time, our RMAAC policy outperforms the MARL (MADDPG) and robust MARL (M3DDPG) baseline policies. Cooperative communication and Predator Prey, under all 4 different noise formats, R.MAAC 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 exceptions happen in Cooperative navigation when Uniform noise format and fixed Gaussian noise format are used. However, we can find that the performance of RMAAC policies close to that of the baseline policies in terms of mean episode testing rewards. In general, our RMAAC algorithm is robust to different types of state information attacks.
32

---

Under review as a conference paper at ICLR 2023
Cooperative Communication
mean spicode reward
C+2
Figure 15: We train RMAAC policies using different values of constraint parameters in the scenario Cooperative Communication. general, the smaller the constraint parameter used, the higher the mean episode rewards RMAAC can achieve.
Cooperative Navigation
rresi sopoode rewerd
kmp01
C+2
egisadelk)
Figure 16: We train RMAAC policies using different values of constraint parameters in the scenario Cooperative Navigation. general, the smaller constraint parameter is used, the higher the mean episode rewards RMAAC can achieve.
Predator:Prey
mean reward
C+2
caisadelk)
Figure 17: We train RMAAC policies using different values of constraint parameters in the scenario Predator-Pre Prey. In general, the smaller the constraint parameter is used, the higher the mean episode rewards RMAAC can achieve.
33

---

Under review as a conference paper at ICLR 2023
Moan Episode Testing Rewards
75
RM
Mean Episode Tlesting Rewards
80
RM
Mean Episode Testing Rewards
as
RM
Mean Episode Testing Rewards
90
RM
90
RM
Mean Episode Testing Rewards
RM
70-
MD
N5
Moan Episode Testing
65-
80
80
60-
65
95
75
53-
60
70
70
50
CC
CC
CC
CC
CC
Figure 18: We test the performance of RMAAC(RM), MADDPG(MA), and M3DDPG(M3) under the attack of linear noise format when using different values of constraint parameters in the scenario Cooperative Communication. RM denotes 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 terms of mean episode testing rewards under all situations using different values of constraint parameters.
policies
0.5
0.01
0.005
0.001
Meon Episode Testing Rewards
RM
Mean Episode Testing Rewards
Episode Testing Rewards
40
Episode Testing Rowards
45.0
Mean Episode Testing Rewards
45.0-
NA
RM
Mean Episode Testing Rewards
45.0
30-
M3
42.5
42.5
N3
M3
-35-
40.0
40.0
25
37.5
37.5
37.5
35.0
15.0
32.5
25
32.5
15
30.0
15
20
27.5
27.5
CN
CN
CN
CN
Figure 19: We test the performance of RMAAA(RMM), 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, i.e. 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.
2
0.5
0.01
0.005
0.001
108
Mean Episode Testing Rewards
101
M3
MA
RM
Mean Episode Testing Rewards
102.0
MB
MM
RM
Mean Episode Testing Rewards
104.0
103.5
M3
MA
RM
Mean Episode Testing Rewards
307
MM
M3
RM
Mean Episode Testing Rewards
107
M3
MA
RM
Mean Episode Testing Rewards
107
RM
M3
MA
100
1015
103.0
106
106
101.0
99
100.5
102.5
105
105
105
100.0
102.0
104
104
99.5
101.5
99.0
103
103
96
PP
PP
PP
PP
PP
PP
Figure 20: We test the performance of RMAAC(RM), MADDPG(MA), and M3DDPG(M33) policies under the attack of linear noise format when using different values of constraint parameters in the scenario Predator-Prey. RM denotes 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 terms of mean episode testing rewards under all situations using different values of constraint parameters.
34

---

Under review as a conference paper at ICLR 2023
Cooperative Communication
meen episcds rewerd
v00
-0
verual
ver=25
eaisadalk]
Figure 21: We train RMAAC policies using different values variance the scenario Cooperative Communication. In general, the smaller the variance is used, the higher the mean episode rewards RMAAC can achieve.
Cooperative Navigation
resh chootee deedeeeee rewarrd
0000
vorw
egisadel()
Figure 22: We train RMAAC policies using different values of variance in the scenario Cooperative Navigation. general, the smaller the variance used, the higher the mean episode rewards RMAAC can achieve.
Predator:Prey
mosi opiozde
ver-5001
vorw2
caisaselk)
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.
35

---

Under review as a conference paper at ICLR 2023
0.5
0.0
0.05
0.001
Episodo lesting Rewards
RM
Mean Episade Tessiing Rewards
Mean Episode Testing Rewards
Mean Episade Testing Rewards
RM
Mean Episade lesting Rewards
80
Mean Episode Testing Reward
Rewaa ds
Moan Eploads Testing Rewards
60
3
-0
-0
-0-
60
65
65
55
80
66
Figure 24: We test the performance of RMAAC(RM), MADDPG(MA), and M3DDPG(M33) policies under the attacks of Gaussian noise format with different variances 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 Gaussian noise formats with different variances.
40
Mean Episode lesting Hewards
Mean Episode Testing Rewards
Tocting Rewards
Rewards
Mean Epsede Testing flewrrds
10
20
30-
25
25-
25-
20
20
Mran
Mcan
20
20 20
20
CN
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.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 Gaussian noise formats with different variances.
103.5
103.5
Mean Episode Testing Rewards
302.5
Mean Epicode Tasting Rewards
Mean Episode Testing Rewards
100.0
Mean Episode Testing Dewards
Eptoode Rewards
Rewards
Mean Episode Testing Rewards
103.5
103.0
103.0
103.0
203.0-
102.0
100
102.5
802.5
301.5
102.0
201.0
102.0
102.0
102.0
102.0
300.5
301.0
301.5
100.5
101.5
303.5
101.0
PP
PP
PP
PP
PP
PP
Figure 26: We test the performance of RRMAAC(MM), MADDPG(MA), and M3DDPG(M3) policies under the attacks of Gaussian noise format with different variances in the scenario Predator-Pres 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.
36

---

Under review as a conference paper at ICLR 2023
Non-optimal
Uniform
Fixed Gaussian
Laplace
85
RM
RM
RM
RM
Mean Episode Testing Rewards
90
MA
MA
MA
M3
MB
80
M3
80
85
75-
80
75
70-
70-
75
70
65-
65
70 65
60
60
CC
CC
CC
CC
Figure 27: We test 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.c. RMAAC. MA denotes MADDPG, a MARL baseline algorithm. M3 denotes M3DDPG, robust MARL baseline algorithm. Our RMAAC algorithm outperforms baseline algorithms terms of mean episode testing rewards under all kinds of attacks.
Non-optimal
Uniform
Fixed Gaussian
Laplace
55.0
52.5
RM
RM
RM
40
RM
Mean Episode Testing Rewards
40
MA
52.5
MA
50.0
MA
MA
M3
M3
M3
M3
50.0
35
35
45.0
30
30
45.0
42.5
40.0
25
40.0
37.5
35.0
20
35.0
32.5
CN
CN
CN
CN
Figure 28: We test the performance of RMAAC policies under the attacks of different noise formats in the scenario Cooperative Navigation. RM denotes our robust MARL algorithm, i.c. RMAAC. MA denotes MADDPG, MARL baseline algorithm. algorithm. Our RMAAC algorithm either outperforms is close to baseline algorithms in terms of mean episode testing rewards under all kinds of attacks.
denotes M3DDPG, a robust MARL baseline
Non-optimal
Uniform
Fixed Gaussian
Laplace
112.5
RM
120
RM
RM
112.5
Mean Episode Testing Rewards
110.0
M3
MA
M3
MA
115
MA
M3
110.0
M3
MA
107.5
115
107.5
105.0
105.0
110
102.5
102.5
105
100.0
105
100.0
97.5
100
100
95.0
95.0
95
95
92.5
PP
PP
PP
PP
Figure 29: We test the performance of RMAAC policies under the attacks of different noise formats in the scenario Predator-Pree 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 al algorithms in terms of mean episode testing rewards under all kinds of attacks.
37


Reviews:
[{"review_id": "kirjLUgYSv", "reviewer": "Reviewer_wL7B", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of multi-agent RL under state uncertainty, by formulating the state uncertainties as an adversary and formulating the problem into a Markov game. Sufficient conditions are established under which an equilibrium exists for such a Markov game. Furthermore, both a value-based method and a policy-based method are proposed in search of such an equilibrium. Numerical experiments are also conducted to demonstrate the effectiveness of the proposed methods.", "summary_of_the_review": "This paper provides a rigorous formulation to a problem (MARL with state uncertainties) that is gaining interest in recent literature. The proposed Q-learning type method, although not scalable in its current form, does come with convergence guarantees. The proposed actor-critic type method enjoys favorable empirical performances. I believe this paper contains enough original contributions to this field. ", "strength_and_weaknesses": "Strength: \n\nI appreciate the paper's effort in modeling the state uncertainties as part of the Markov game and proving the existence of the equilibrium before proposing algorithms to find it. The motivation for studying state uncertainties is also clear and well articulated. Though the methods itself do not come with finite-time guarantees, having asymptotic convergence looks good enough for this challenging problem, and the empirical evidence provided in Section 4 looks convincing. I also appreciate the author's effort in highlighting important core arguments before presenting the main theorems in Section 3.2. \n\nWeakness:\n\nThere are some assumptions being posed with concrete context provided to the reader. For example, in Assumption 3.11, the last condition is posed without any explanation on why this is needed for the convergence of the RMAQ method. It is not immediate to me why this condition relates to the convergence of the Q-learning type method. \n\nMinor Comment:\nCan the author comment on the per-iteration complexity of implementing the RMAQ method? Specifically, how does it scale with the number of agents in the system (does it suffer from the exponential blow-up in the state-action space)? ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "hwXL1BxLBT", "reviewer": "Reviewer_dBqZ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper considers multi-agent RL setting where agents' observations are corrupted at test-time. The paper proposes a novel optimization framework that models adversarial perturbations on agents' observations as additional players in the underlying Markov game. The authors provide characterization results for the considered framework, deriving a version of Bellman conditions for this framework, as well as a sufficient conditions for the existence of a robust equilibrium. They further propose two algorithms for finding equilibrium policies, based on Q-learning and actor-critic approaches, and experimentally test their efficacy in standard MARL environments. ", "summary_of_the_review": "The paper explores a novel MARL setting, and reports a set of results that is of potential interest to researcher working on robust RL. On the flip side, the current submission could benefit from additional discussion points that would clearly explain why more general settings are not needed in this setting. The current set of results, although looking promising, could be extended. The clarity of the paper could be improved as well.", "strength_and_weaknesses": "Arguably, the main strength of the paper is that it studies what appears to be a novel setting - robustness to perturbations of agents' observations in MARL. The results include a theoretical characterization of the formal setting, algorithmic approaches for deriving equilibrium policies, and experimental validation of the proposed algorithms. In other words, the paper contains a rather complete set of results for this framework. Having said that, I have several concerns about the following submission, listed below:   \n- First, it is not clear to me whether this optimization framework leads to optimally robust policies. More specifically, considering only stochastic stationary policies, as assumed in the preliminaries, may not suffice in this case. Namely, an agent/victim decides on its actions based on corrupted observations, which are correlated across time since adversarial perturbations have a bounded budget and have a functional form. Hence, agents can benefit from having history-dependent policies, e.g., form a belief about the underlying state. Due to this, it is also not clear that the equilibrium notion in Def 3.2 is the right solution concept - shouldn't agent be deciding based on their beliefs about the underlying state, and if so, why is it important to consider a robust version of MPE (Markov perfect equilibrium)? \n- Some parts of the formal setting/characterization results may not be precise enough. I tried to check some of the results, but the notation is quite confusing. I give examples in the next section. Some of the results are also not clear to me. E.g., in the proof of Prop. 3.5., I didn't follow why the 3rd equation is due to the NE of the corresponding EFG - why  are $\\pi_*^v$ and $\\rho_*^v$ important for this inequality and why does the inequality hold if we have $v^i = [1, 1, 1, ..]$ and $u^i = [0, 0, 0, ...]$? \n- I'm puzzled by potential implications of Theorem 3.8 and Theorem 3.9. Wouldn't they imply that there always exists an RE? If $v^*$ always exists and given Theorem 3.9, can't we  find an equilibrium by solving the EFG corresponding to $v^*$? If yes, why is Theorem 3.10 important since it covers very specific case of the setting? If not, how does the algorithm from section 3.3 work? It would be helpful to have an additional discussion that compares the theoretical aspects of this work to those from Hu & Wellman (2003), including the assumption needed for convergence (e.g., assumption 3.11c this work vs assumption 3 from Hu & Wellman (2003)). \n- Robustness in this paper is measured against adversarial perturbations that have a specific form, given via function $f$. I'm wondering whether the corresponding robust policies generalize across different functions $f$. Judging by Fig. 12, they don't appear to be consistently better than the baselines. In practice, we presumable wouldn't know the exact form of adversarial perturbations that will occur at test-time, so it would be good to include results that show performance under noise models which were not used in training. Furthermore, why weren't policies that optimally disturb the environment trained for each algorithm separately (keeping these algorithms fixed)? It seems that the current adversarial perturbation policies may favor RMAAC, especially if an equilibrium point was not reached in the training phase. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "LdALvfJmsL", "reviewer": "Reviewer_qQaj", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper develops a robust MARL framework that considers state uncertainty. The paper first formulates the MARL problem with state uncertainty as MG-SPA and develops theoretical contributions, including the new solution concept of Robust equilibrium and the equilibrium's existence. Then, based on the Bellman equations of MG-SPA, the Q-learning method (RMAQ) and actor-critic method (RMAAC) are developed. Finally, evaluations in the two-player game and MPE show robust performance against the adversaries' perturbations. ", "summary_of_the_review": "Overall, I have a positive evaluation of this paper because the paper formalizes state uncertainties as MG-SPA and develops its theoretical and practical contributions. However, I have a concern regarding the absence of robust MARL baselines, and I will make a final decision on the recommendation after the authors' response.", "strength_and_weaknesses": "**Strengths:**\n1. This paper develops important theoretical contributions based on MG-SPA. \n2. The algorithms are also developed in a principled way based on MG-SPA, and RMAAC shows the scalability. \n3. The paper is generally well-written and conveys the methods clearly. \n\n**Weakness:**\nBecause this paper's contribution focuses on robustness, adding robust MARL baselines in the evaluations would strengthen the paper.\n\n\n**Questions:**\n1. In Section 3.1, using the same notation $i$ for the adversary can be confusing compared to the agent $i$. Following the consistency, what about using $\\tilde{i}$ for the adversary?\n2. Which perturbation behaviors did adversaries learn in the MPE experiments (i.e., the amount of noise in the linear and Gaussian noise formats)?\n3. How is the robustness performance affected by varying $\\epsilon$?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "CTB7AnuyXBu", "reviewer": "Reviewer_QZNZ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work investigates the robustness of MARL under state uncertainty. The authors try to formally define the state uncertainty problem and provide a theoretical analysis. Based on the state uncertainty formulation, two algorithms (RMAQ and RMAAC) are designed to improve the robustness of MARL where there is state uncertainty.", "summary_of_the_review": "This work is overall interesting as it is looking at an important problem to improve the robustness of MARL. I think further improving the evaluation section of this work can improve its quality. See above for more details.", "strength_and_weaknesses": "Strength:\n- The authors provide a theoretical analysis of the MARL state uncertainty problem, which provides a theoretical base for the two designed algorithms. \n\nQuestions and concerns:\n- In the evaluation section, it seems the results are based on a fixed mean and variance of the gaussian noise. How does the proposed algorithm perform under magnitude of perturbation compared to other algorithms?\n- In the evaluation section, the attack policy seems only be the one trained with RMAAC, how does the algorithm perform under other types of attacked proposed in the existing literature?\n- This might be within the scope of the work, but is it possible that the proposed algorithms find a Robust Equilibrium that is sub-optimal (e.g. if the problem has multiple RE)? \n- What happens if the team only receive one single team reward at each time step? Can the current formulation still work?\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject