Defending Against Unknown Corrupted Agents: Reinforcement Learning of Adversarially Robust Nash Equilibria
Authors: Andi Nika
Jonathan Nöther
Adish Singla
Goran Radanovic
Venue: Accepted by TMLR ()

Abstract: We consider a Multi-agent Reinforcement Learning (MARL) setting, in which an attacker can arbitrarily corrupt any subset of up to $k$ out of $n$ agents at deployment. Our goal is to design agents that are robust against such an attack, by accounting for the presence of corrupted agents at test time. To that end, we introduce a novel solution concept, the Adversarially Robust Nash Equilibrium (ARNEQ),   and provide theoretical proof of its existence in general-sum Markov games. Furthermore, we introduce a proof-of-concept model-based approach to computing it and theoretically prove its convergence under standard assumptions. We also present a practical approach called Adversarially Robust Training (ART), an independent learning algorithm based on stochastic gradient descent ascent. Our experiments in both cooperative and mixed cooperative-competitive environments demonstrate ART's effectiveness and practical value in enhancing MARL resilience against adversarial behavior.

Published in Transactions on Machine Learning Research (08/2024)
Defending Against Unknown Corrupted Agents: Reinforcement Learning of Adversarially Robust Nash Equilibria
Andi Nika Mar Planck Institute for Software Systems
ondinika @mpi-sus ews.ory
Jonathan Nöther
Sffonootosttuuduu---sutt de
University of Soarland & Max Planck Institute for Software Systems
Adish Singla
adishs@mpi-sus.
Mar Planck Institute for Software Systems
Goran Radanović
gradanovic @wwpeesss..pppss.moom
Maa Planck Institute for Software Systems
Reviewed on OpenReview: https: // openreview. id= ad=aggylifflll
Abstract
We consider Multi-agent Reinforcement Learning (MARL) setting, in which an attacker arbitrarily corrupt any subset of up to k out of n agents at deployment. Our goal is to design agents that are robust against such attack, by accounting for the presence of corrupted agents at test time. To that end, we introduce a novel solution concept, the Adversarially Robust Nash Equilibrium (ARNEQ), and provide theoretical proof of its existence in general-sum Markov games. Furthermore, we introduce proof-of-concept model-basod approach to computing it and theoretically prove its convergence under standard assumptions. We also present practical approach called Adversarially Robust Training (ART), independent. learning algorithm based stochastic gradient descent. ascent. Our experiments in both cooperative and mixed cooperative-competttiee environments demonstrate ART's effectiveness and practical value in enhancing MARL resilience against adversarial behavior.
1 Introduction
The growing prevalence of automated systems has facilitated fertile ground for implementing the celebrated multi-agent reinforcement learning (MARL) framework to solve a wide range of important problems. Prominent examples include finance (Shavandi & Khedmati, 2022; Lee et al., 2007), sensor networks (Cortes et al., 2004; Choi et al., 2009), autonomous vehicles (Shalev-Shward Shwartz et al., 2016; Zhou et al., 2020; Palanisany, 2020) and gaming (Vinyals et al., 2019; Perolat et al., 2022).
One of the main underlying assumptions of this practical framework has been the inherently rational and selfish nature of the learning agents, according to which their sole objective is to optimize their utilities, assumption stemming from game theory (Osborne & Rubinstein, 1994) and economics since the time of Smith (1776). Indeed, the overwhelming majority of MARL successes have been made by algorithms that are designed to optimize their objectives.
However, this assumption has been challenged by different lines of rescarch, only sporadically the past, but increasingly more in recent years. For example, Chen al. (2023) study the problem of robustness of distributed RI. systems against Byzanline atlacks, where fraction of agents report. fake data to

---

Published in Transactions on Machine Learning Research (08/2024)
Attacker selects up to k policies
Attacker modifies
Policies are deployed
Robust training
Robust policies
selected policies
Attack-defense interaction is depicted. First, the agents are trained without any adversarial threat. Then, the attacker observes all the trained policies of the agents and arbitrarily picks any up to of them. Once the chosen policies are arbilrarily perturbed, they are deployed. Our goal is to train policies that remain robust under attack.
Figure 1:
the center. Another line of research, which has gained a lot of popularity recently, studies the problem of adversarial policies in MARL (Guo et al., 2021), where an agent faces an adversarial opponent trained in a zero-sum Markov game regime. Eliaz (2002) considers the problem of implementing games with potentially faulty agents, that is, agents who do not necessarily aim at optimizing their utilities but might behave erratically due to some system malfunction. Furthermore, Babaioff et al. (2007) consider congestion games with malicious players and study the game-theoretic properties of such games.
The shared underlying insight among these various lines of work is that in reality, certain agents could exhibit unpredictable behavior, stemming from system malfunctions or unanticipated adversarial objectives. This insight is further evidenced in various safety-critical applications of MARL, where the presence of such agents might seriously deteriorate their performance. For example, traffic management (Kuyer et al., 2008) and autonomous driving systems, some agents, be it autonomous or human, might cause traffic jams or fatal accidents due to their erratic behavior, while in distributed energy systems (Roesch et al., 2020) they might compromise the stability and reliability of the power grid.
Be that as it may, the aforementioned previous work lacks a simultaneously practical and conceptually general treatment of the problem of malicious agents in multi-agent systems. While Eliaz (2002) proposes an interesting solution concept, that a faulty-tolerant Nash equilibrium, their focus is on the implementation problem, not a lcarning one, so the question of efficiently computing such an equilibrium left open. The line of work initiated by Gleave et al. (2020) on adversarial policies focuses on two-player games, and their considerations are mostly from the attack's perspective. Chen et al. (2023) consider distributed RL systems, where agents share the same goal, while Babaioff et al. (2007) study the properties of a specific class of games with malicious players, with fixed identities.
Motivated by the above shortcomings, we are interested in providing a formulation of the problem that captures a general attack model. In particular, we are interested in a model that: (i) involves n-player Markov games; (ii) the attacker can manipulate any up to out of n trained policies; (ii) the attacker can arbitrarily modify the controlled policies. Our aim is to find efficient defense that takes into account such attack model and serves
robust training procedure for the learning agents.
To that end, we formulate a general-sum Markov game with n players, whereby an attacker is given access to all agents' policies at test-time, previously trained on a clean environment. The attacker then arbitrarily picks and perturbs any up to h < n of them, at which point all policics are deployed. Ultimately, we are interested in devising a robust. training procedure that accounts for the polential allack at lest time and can serve as defense against it. The attack-defense model described in Figure Below we describe our main contributions.
First, in the same spirit as (Eliaz, 2002; Zhang et al., 2020), we introduce a new notion of equilibrium, the k-Adversarially Robust Nash Equilibrium (ARNEQ), designed to be robust against the worst-case arbitrary perturbations of any ls out of n policies, and show its existence in general-sum Markov games.
Second, we proposc model-based procodure to compute such a strategy and show that it converges to an ARNEQ under standard assumptions on the game structure.
Third, molivated by gradient-based decentralized methods in Markov games, we propose Adversarially Robust Training (ART) for MARL, an efficient gradient- based learning algorithm, that can be run independently among all players at training time.
Finally, we provide extensive experiments on both cooperative and mixed environments that showcase the efficiency of ART as a robust defense. Our results show that ART converges to stable joint strategy and is able to substantially improve performance, which can be clearly observed in our qualitative results.
2

---

Published in Transactions on Machine Learning Research (08/2024)
1.1 Other Related Work
1.1.1 Attacks and defenses in (MA)RL.
Adversarial attacks on RL systems have been extensively studied in recent years (Kiourti et al., 2020; Lin et al., 2017; Huang et al., 2017; Mohammadi et al., 2023; Sun et al., 2020a;b). The main types of these attacks include training-tine time attacks (Rakhsha et al., 2020; Xu ct al., 2021), test-time attacks (Behzadan & Munir, 2017; Huang et al., 2017; Kos & Song, 2017; Sun et al., 2020a), and backdoor atlacks (Kiourti et al., 2020; Wang et al., 2021; Yang et al., 2019), where the adversarial perturbations happen at the environment level. More recently, however, there has boen a growing interest in the so-called adversarial policies in (MA) R (Gleave et al., 2020; Guo et al., 2021; Liu el al., 2022; Wang et al., 2023; Mohammadi et al., 2023; Li et al., 2019) where attackers assume the identity of an agent, and thus attack by inducing natural observations. Our work belongs to this class of attack type, but generalizes the framework of adversarial policies in MARL for general n-player games and focuses on the defense front. Various types of defenses have been proposed against test-time attacks (Zhang et al., 2020; Pattanaik et al., 2017; Zhang et al., 2021a; Wu et al., 2021), )) training-timi attacks (Banihashem et al., 2023; Kumar et al., 2021; Lykouris et al., 2021; Wu et al., 2022; Nika et al., 2023; Zhang al., 2021a; 2022) and backdoor attacks (Bharti el al., 2022). When it comes to adversarial policies, previous work has mainly focused on heuristic defenses against them. For two-player zero-sum Markov games, Gleave et al. (2020) propose sequential fine-tuning procedures against various adversaries, which seems to robustify the trained policies against such adversaries, but not against a more general attack. Furthermore, apart from issues such as catastrophic forgetting and myopic robustness against a specific class of adversaries, the aforementioned defense strategy becomes combinatorially expensive in n-player Markov games. If the identities of the controlled agents and the objectives of the attacker were known, then natural solution concept. would be the Nash equilibrium (NE) strategy of the new game. In our setting, this information is not given. As a consequence, the problem is no longer standard Markov game, and thus there is no NE defined in its solution space. Recently Liu et al. (2023) consider the problem of defense in the two-player regime with one adversarial policy and take a game-theoretic approach. They define a new game with modified utilities and then solve the game as if it were a zero-sum game. We generalize their setting and study the defense problem against any up to out of n adversarial policies in MARL. As we mentioned earlier, this formulation renders the classical NE notion inappropriate. Thus, a new solution concept is necessary.
1.1.2 Robust (MA)RL.
Another line of research related to our work is that of robustness in (MA)RL under model uncertainty (Wang & Zou, 2021; Zhang et al., 2020; Russel et al., 2020; Mankowitz et al., 2018). In this line of work, the focus is on designing algorithms that learn under worst-case environment assumptions. Instead, we consider the robustness against the worst-case subset of adversarial policies at test time. A recent work from Li et al. (2023) studies a similar problem to ours. They consider defenses against unknown Byzantine attacks in a cooperative rogime. However, they take a different approach to the defense problem. They capture the uncertainty about the adversaries as uncertainty in transitions, which are characterized by types, thus taking a Bayesian game approach, while allowing only for one adversary. We take a dircet robust approach on each individual agent while allowing for more general attack of up to k adversaries. Furthermore, their notion of robust equilibrium pertains to only one joint adversarial policy, while our robust equilibrium associates each robust policy with a specific joint adversarial strategy. This substantially changes the setting since we are, in effect, solving n games simultaneously.
1.1.3 Markov games.
We formalize our study using the notion of Markov games (Shapley, 1953). Our goal is to design decentralized robust training procedures. There has been a lot of research in the past decade on model-based raltzed (Hu & Wellman, 2003) and model-free decentralized methods of computing the celebrated Nash equilibrium of such games (Daskalakis et al., 2020; Leonardos et al., 2021; Ding et al., 2022: Zeng et al., 2022; Giannou et al., 2022; Zhang et al., 2021b; Wang & Zou, 2022; Wei et al., 2021). However, all efficient methods are proposed for particular types of Markov games, such as zero-sum or potential Markov games. The notion of
3

---

Published in Transactions on Machine Learning Research (08/2024)
robust Markov games has also been previously considered. For instance, Aghassi & Bertsimas (2006) propose the notion of ex-post equilibrium to handle payoff uncertainty in normal form games, Kardeg et al. (2011) consider robust Markov games with model uncertainty. In contrast, our notion of uncertainty is related to adversarial policies. Finally, Kalogiannis et al. (2023) consider cooperative Markov games with a fixed adversary. Our work differs from them in that we consider a general-sum Markov game seiting and assume the presence of unknown adversarial policies. This substantially changes the nature of the game since the agents cannot cooperatively team up against the adversaries.
2 Problem Formulation
In this section, we first. introduce the relevant notation, then give the necessary background of the problem, after which we formally introduce our problem.
Notation. As usual (:-)) will denote the inner product between two vectors from the same vector space, [r] denotes the set of natural numbers up to and including n. We denote by |I-II the Euclidean norm and by (XX) the set of probability simplices on the set X.
2.1 Preliminaries
Let 9 = (N, x .... x R P.,P,,7 p.) ) be Markov game. Here N = [n] represents the set of n players, S denotes the state space with cardinality S, A == A x An is the joint action space with A; denoting the action space of player with cardinality A,. The reward of player i is a function of the state and joint action, i... R2 S A + [0, 1]. The transition kernel is given by P S A - A(S), with P(s'(s,a) denoting the probability that the game transitions into state s' given that joint action a is taken in state s. The discount factor is denoted by 7 E [0, 1), and μ A(S) denotes the initial state distribution. Finally, we will denote by Nr the set of subsets of cardinality
greater than l of N (i), and we let Ω A(V)).
Stationary policies are mappings from states to distributions over actions. Formally, we let n, : S - A(A,) be a stationary policy for player i, lying in the policy space II, Moreover, we denote by II = II, x.... x II, the joint policy space of all players, with elements denoted by т. In Sections 4 and 5, we will consider neural policy classes. Given action a, policy π and a set K E NN we define ak = (a;)iek and a_ = (az)iek for action a and Ā = (Ty)jeK and m-K = (Tz))ęK for policy x.
The value function represents the expected discounted cumulative reward of a given player with respect to given joint policy, starting from given state. Formally, given policy E 1l and state E S, the value function with respect to player is given by (T( = E - > ("Ra(s,, az) 80 = 8, P where the sequence so. ag, $1, a..... denotes the traversed state-action tuples when the initial state is s, actions are taken using and the transitions follow P. Furthermore, let (T)) Eg- [V" [V](==] denote the value function with respect to the initial state distribution. The value function satisfies the Bellman equation:
(=(())
En(s) m(s) ΣII (BV)s.) SES REAjEN
(1)
with B representing the Bellman operator acting on Vi, defined as (BV))ss = as) +7 (P(s Vi(T)), where VI()) denotes the S-dimensional vector with values VT((T) and P(s, a) denotes the S-dimensional vector with entries P(s'|s,a) a), for all s' E S. Next, we formally define the notion of a Nash equilibrium.
Definition 1 A joint policy x²" is said to be a Nash equilibrium (NE) strategy if no player can be better off by deviating from it. Pormally, we have V!((T)) 2 Vi" (7), x",, for all n. E II, and i N. Here nh, denoles the joint policy of the players other than
Further, joint strategy n² is said to be an c-approrimate NE strategy if (1") V"(a,, e, for all 7े E II; and i E N. If an NE joint stralegy is stochastic, it is said to be mized NE stralegy.
Fink (1964) showed that mixed NE strategy always exists in any given n-player Markov game.
4

---

Published in Transactions on Machine Learning Research (08/2024)
2.2 Attack Model
As already described in Section 1, we consider lest-time allacks, whereby an attacker is allowed access to all n trained policies and can arbitrarily pick and manipulate any up to l < n of them. It's important to highlight that the attacker's ability to select any subset of trained policies adds an additional layer of complexity to the defense problem. Any information about the attack is necessary to obtain an efficient defense against it. In our setting, the learning agents are unaware of who among them will be attacked at test time, and so, do not know priori which agents to treat as adversarial.
2.3 Defense Objective
Our focus this paper is on the defense front In particular, we are interested in devising training procedures that take into account the potential future threat deployment. At training time, there is no attack present. The only information the agents have about the attack is the parameter k and its realization at test time. Thus, our aim is to propose training procedure for each individual agent, taking into account this parameter, and the fact that any other agent may behave adversarially towards it. In the next section, we will introduce a new solution concept that is designed to capture the nature of the attack and provide such a robust defense.
3 Theoretical Results
In this section, we first formulate our solution concept, namely, the adversarially robust Nash equilibrium. Then, we show its existence in general-sum Markov games. Finally, we provide a model-basod approach to its computation and prove ils convergence.
3.1 The Adversarially Robust Nash Equilibrium
In this section we introduce our solution concept which is tailored to our attack model and defense objective. Our goal here is to provide the agents with a defense strategy that they can use independently of the other agents. Similar robust MARL with model uncortainty (Zhang et al., 2020), we consider robustness MARL under allack uncertainly. The best that player can do with the given information is to solve the worst-case problem, i.e. to be robust against the worst-case attacker (in terms of the agents under attack and the objectives). To that end, we propose the Adversarially Robust Nash Equilibrium (ARNEQ), defined as follows.
Definition 2 A joint policy मt is said to be an ARNEQ if there erist S-dimensional vectors Vi,.... Vi such that, for every player i E N and state E S we have
(-|s) arg max min min EKown mcell: wrel Gtl
[T((asl)) (ayls) II (VVl))
aEA
jEK
(gKU(s)
where we denole by 7t the joint adversarial policy (7)) with respect to player i, where 7H EI,, for each i, and Ω A(N)).
Before procoed any further, it is important to point out that this notion of equilibrium does not correspond to that in zero-sum Markov games, even adversarial team Markov games. In fact, the game induced by the defensive behavior of the agents is not even a static game which all agents share with each other. To see this, consider the following example.
Example 1 Let n = 3 and = 1. When computing an ARNEQ, each agent has to consider its worst-case adversory. Suppose that the worst-case case adversary of agent 1 may be agent 2, while the worst-car case adversary of agent 2 may be agent 3. So agent and agent 2 are not playing the same game, since the benign agents and worst-case adversarial agents for each of them are different.
We will first show that such an equilibrium always exists in general-sum Markov games. We defer the proof of the result the Appendix (see the Supplementary Material).
5

---

Published in Transactions on Machine Learning Research (08/2024)
Theorem Let be finite generol-sum Markou game with n players, that is, suppose max S, oc, where A = max Ai, and let k < n. Assume that on arbilrary subset of al most k players use arbilrarily modified utilities, and assume that the mized strategies of all players lie in compact sets. Then, an ARNEQ, as in Definition 2, erists.
The next natural question is how to find such an equilibrium. In the next section, we will focus on devising a madel-based centralized approach to computing an ARNEQ and prove its convergence.
3.2 Adversarially Robust Nash Q-Learning
Nash Q-Learning (Hu & Wellman, 2003) is a model-based approach to finding the Nash equilibrium of a Markov game. Essentially, each player maintains estimates the Q-values of every player* and then computes the Nash equilibrium of the stage game. The Q-values are then updated based on the outcome of applying the so-called Nash operator (analogous to the Bellman operator for Markov games) the current Q-values. This method leverages celebrated result from Filar & Vrieze (2012) which links the value functions that correspond to the Nash equilibrium of the entire Markov game with those corresponding to each individual stage game, which will be defined later.
First, we need to define an operator that is appropriate for our sctting and satisfics the recursive property analogous to the Bellman operator. Based on Definition 2, we define the following update sequence, for any E N,, state S and 2
Vit1(6 (8) max min
Ex
Σ n. (=aa|ss)== (/ LEEA
we
# R'ElL;
where Æ' denotes the joint benign policy computed at step l. Similarly, we define the Bellman backup for the Q-values with respect to an ARNEQ policy म", for any state-action tuple (s, a), as follows, for given learning rates 0₂ E 1):
(s, R,(s,)) +7 P(d'ss,
Σ T- (d<Kk(() (dx1 (4 La'EA
e'ES
"))"))x where w/ and # are the adversarial counterparts of the ARNEQ policy of player i, and 7 At this point, need to introduce another relevant definition instantiation of the ARNEQ for a stage game defined in terms of the Q-values only for given state. Our procedure will itcratively compute it for each encountered stale.
Fir state E S. Given the Q-values as),,a,, for all i E N and a A, the joint tuple (T,, H) wusiee is said to be a stage ARNEQ with respect to state s if, for every E N, we have
Definition 3
[T ( ai wi) E arg max min FiE
E Ex-e! ween, EL,
LEE
Now we are ready formulate the update rule for our procedure as follows:
Qt ++| (st, ar) = (1 - ((r) + at (Ri ar) ) 7ARNEQ (d((s44)))
(2)
where
ARNEQ(Q = Exaw!
Lo'EA
We will player and agent interchangeably.

---

Published in Transactions on Machine Learning Research (08/2024)
Here, dg denoles the joint action laken at time step in state 8, by all the agents, म' denotes the stage game ARNEQ joint policy computed with values (Qo)ew with adversarial counterparts (wi, Nee.
with ((((41))
Before stating the main result of this section, we first state the assumptions under which holds. They are standard in similar model-basee approaches equilibrium computation (Zhang al., 2020; Hu & Wellman, 2003; Yang et al., 2018).
Assumption 1 Each state and action tuple has been visited infinitely often.
Assumption 2 The rates ag satisfy, for every t 0:
S a4 1, Eiz1 au = dc and Eiz0 af < co.
a, 0 for any (s, a) (st, a.), that is, we only update the Q-values corresponding to traversed state-octions.
Assumption 3 For each stage game, one of the following conditions holds:
A stage ARNEQ is also global optimum, that is, for any E N and (-11),, we have
E [Kow
Σ
Enna(an (a_ (5) (ax (ax
Ex
LEEA
LaEA
for any x EI, #' II and wi E Ωi.
A given player's payoff is increased other benvgnn players or ils allacker deviale, that is, for any E N have
E Exout
Σ x (ox (s.
Exaus LaEA
+((a:(s)
LacA
for all n' E I1, स' E Il and w/ E Ωz.
Now we ready to state the result. Its full proof is deferred to the Appendix (see the Supplementary Material).
Theorem Under Assumptions 1, and 3 (formally stated in the Appendix), the Adversarially Robust Nash Q-Learning procedure as given in Equation equation 2 converges to Qú, for every player i N.
Proof sketch. The main ingredient of the proof is utilizing a previous result from (Hu & Wellman, 2003) which states that, if Assumptions and 2 hold, and given operator the Q-functions is contraction, then the procedure described above converges to an equilibrium. So the only thing to prove is that the ARNEQ operator is a contraction. We use Assumption 3 to that end, by separately considering both cases of the assumption. With this, all the conditions of the utilized result are satisfied, and thus we conclude convergence to an ARNEQ.
This result completes the theoretical characterization of our problem. Although the proposed procedure is simple and intuitive, with the crucial benefit of satisfying strong theoretical guarantees, there are also several unfortunate drawbacks associated with it. First, note that the update rule given in Equation equation 2 requires knowledge of the equilibrium policies of the benign agents in every itcration, which in turn requires knowledge of the Q-values of all agents, from every agent's point of view. This is downside that all centralized, value-based algorithms in MARL, such as Nash Q-Learning, share. Second, even knowledge of the Q-values of all agents can be guaranteed, the problem of computing a Nash equilibrium from given utilities in general-sum Markov game is known be computationally hard (Daskalakis et al., 2009). Finally, the theoretical guarantees of the proposed method heavily rely the stated assumptions. Such assumptions
7

---

Published in Transactions on Machine Learning Research (08/2024)
may not always be satisfied in practice, where the irregularities in the individual utilities do not need to satisfy saddle point or global optima conditions. Motivated by the above, our next goal is thus to find a more practical and efficient approach to finding ARNEQ policies. In the next section, we introduce a model-frec gradicnt- gradient-based algorithm that is able to empirically provide an efficient defonse in varions MARL environments.
4 Adversarially Robust Training for MARL
In this section, we propose an independent learning algorithm, Adversarially Robust Training (ART) for MARL, a gradient-based method that uses a two-timescale update rule, designed to provide a practically efficient defense against unknown adversarial policies.
Our robust notion of equilibrium imposes specific training stratogy. Note that the adversarial policies that complement an ARNEQ strategy profile are not necessarily identical across different players. Thus, each player, apart from computing its policy, also needs to compute its own set of adversarial agents and their associated adversarial policies. Thus, three different components need to be Icarned independently. Since each individual problem is max min problem, it is natural to consider the Gradient Descent Ascent (GDA) learning paradigm (Lin et al., 2020). This method has been widely used in the context of Markow games and has been shown to converge to equilibria in more structured regimes (Daskalakis et al., 2020).
Recall from the previous section that W/, He and से denote the adversarial subset selection policy, the benign policy, and adversarial joint policy with respect agent i, respectively. We parametrize them 0,, 0; and 0', respectively. Based on these definitions, we define the loss with respect to given adversarial subset selection policy Wi, dependent joint policy ग and adversarial policy H', as
C,(0.,0,0) Ex Ex-er(0)) V (T- (
Based on this definition, and the fact that we can write the above loss an inner product, we have
ve,c.(0.,000) = V/
where (T(O), denotes the Em. ((m") dimeensionl vector with entries VT"(T= ((0K))(0 (Ok)), for K E N,
The loss, with respect to player i, of the adversarial policy म' depending on w; and म is similarly defined. However, the gradient here is with respect to 0'. Note that, for each component j of the adversarial policy स the gradient Vg (0,, 0, 8*) is proportional subsets K that do not contain j an adversarial component, the gradient becomes
ΣK.KENAJEK V""==xxOOX x),, 2 (0x)), since for those
Our learning protocol proceeds follows. In every round 2 1, player i E A maintains three gradient updates, one for the adversarial subset parameters 0f one for the adversarial policy parameters 0+. and one for its own benign policy paramcters 8. Furthermore, we set the same learning rate nA for both (0))) and (0))) since they both comprise the adversarial component of the problem.
At the beginning of the round, player i collects samples of subsets from the adversarial subset selection policy of the previous round w/-+. In order to perform the gradient updates of round 4, player needs to collect several roll-outs. We denote by V., 0, i' the gradient estimate used for the updates based on the collected roll-outs.
The pseudocode of the described method is given in Algorithm 1.
5 Experimental Results
We evaluate policies trained using ART in two cooperative environments and one environment where the agents do not have aligned utilities. More specifically, we consider the Spread multi-agent-particle environment (Towe
8

---

Published in Transactions on Machine Learning Research (08/2024)
Algorithm ART for MARL (for player i)
Input: Number of potential adversarics k; accuracy parameter c > 0; learning rates VA and l/: number of episodes T. Initialize: 0. 0,0 0, 0j00 0, for all i e N, j #i.
1: for t 1,2...... ., T do:
Sample adversarial subsets from w of-
+ 0:-- 11 oo 01-11 (pi-11)
0,+0,-1 + 118 V 0,
Li 0 0 0
for E N do:
0/' - 0,1-1 , ;
Ci (0% 00,0"-1, ",,001,,00 0r.t11)
6:
7: end for
8: end for
et al., 2017), cooperative multi-agen agent extension of the MuJoCo Ant environment (Todorov et al., 2012), and the cooperative Pursuit environment (Gupta et al., 2017). For detailed descriptions and parameters of the environments, see the Appendix (in the Supplementary Material).
Environment
A Agorith
No Adversary
Adversary
Adversaries
Adversaries
Naive
-34.0 1.9
-493.2 11.2
-480.8 16.1
Independent
Fixed-K(k=1)
-142.8 1 24.5
2771. 1 31.0
290.. 1 36.6
NA
Spread
ART(k=1)
-123.4 11.7
199. 13.3
-442.0 33.4
ART(k=2)
-14.00 15.1
2014411.7
213.6
Naive
327.5 = 48.9
48.9
2.2 10.7
Ant
Fixed-K(k=1)
229.0 + 30.0
29.5 + 14.8
NA
NA
ART(k=1)
181.9 25.4
1 6.7
Naive
40.7
34.4
32.3 1.9
-2.0 +: 2.3
Fixed-K(k=1)
37.6 + 2.8
35.7 4.1
30.9 + 2.8
8.5 2.7
Fixed-K(k=2)
29.2 10.5
26.3 10.3
25.7 2..7
17.1
Pursuit
Fixed-K(k=4)
25.89 1 7.24
23.82 7.50
16.97 1 8.12
6.21 1 6.27
ART(k=1)
47.3 1.3
50.6 + 1.8
48.1 + 1.9
26.0 1: 4.3
ART(k=2)
42.6 3.7
37.4 1.7
36.4 2.4
21.0
ART(k=4)
35.6 1.64-43
32.8 1.5
34.0 1.6
19.3 1
Table I: Comparison of ART with the proposed baselines. Fixed-K(k-2) for Independent Spread is omitted,
is equivalent
to ARI(K=2). We report the mean and the standard error of the total reward achieved by agent under attack over five runs with different seeds. In each run, we first train the benign agents and then train adversaries to minimize the total reward of one of the benign agents, considered to be victim.
For Independent Spread, report the worst-case total reward, where the minimum is taken all possible victims and their adversaries. Since Ant and Pursuit cooperative and symmetric environments, consider attacker that controls specific subeet of agents with cardinality while the remaining agents victims who have reports total reward these agents. Note that, for Ant, we only consider k 1, since an adversary that controls more agents can lift ant up, denying any forward movement.
reward function. The table
5.1 Baselines
We compare the effectiveness of ART with Naive Training, where no adversarial agents are present during the training phase. This provides a baseline for evaluating the resilience of robustly trained agents compared to conventional techniques. Additionally, we introduce the Fixed-K training baseline where the subset of agents controlled by the adversary is fixed during the training process. We aim signify the importance of training with the worst-case subset of adversaries. Both baselines are trained with the same hyperparameters ART, ensuring fair comparison across the board.

---

Published in Transactions on Machine Learning Research (08/2024)
Figure 2: Consecutive snapshots of agents under attack by one adversary in the Independent Spread enviromment: first represents Naive Training and second represents ART(k=1). The green circle corresponds the agent under attack, red to the adversary, blue to the benign agent not under attack, the black star is the target landmark of the attacked agent, and the black circles are the target landmarks other agents. Naively trained agents do not avoid other agents and allow the adversary to infer the position of their landmark, resulting in the adversary blocking it. Agents trained with ART choose longer route to their destination, which avoids adversarial agents, and maintain distance around their landmark, which does not allow the adversary to infer its exact location.
ZAAA
Figure Consecutive snapshots of agents under attack in the Aut environment: first row represents naive training and second row represents ART(k=1). The dotted red line in Ant serves stationary reference point. Naively trained agents struggle to move forward when under attack. Robustly trained ones are able to move forward when one leg is corrupted.
5.2 Implementation Details
To train robust neural policies, we implemented ART as described in Algorithm Both the adversarial and benign policies are updated using the PPO (Schulman al., 2017) implementation of the ray library (Moritz et al., 2018). The adversarial subset selection model w, as described in Section is implemented using pytorch (Paszke et al., 2019) and utilizes REINFORCE (Sutton et al., 1999) update rulcs. To allow training with more data, used additionally generated trajectories. Hyperparameters were selected according to the fine-tuned examples provided in the ray library, except for the learning rate of benign agents, which is set to be half the learning rate adversarial agents. This lcads to aggressively updated adversaries, while still ensuring convergence a reasonable time. All used hyperparameters can found in the Appendix (see the Supplementary Material).
5.3 Empirical Analysis
Quantitative analysis. To evaluate the robustness the obtained agents, we fixed the benign policies and trained new adversarics from scratch that use the same hyperparameters. We used the latter to test if the robust policies generalize new attackers. Table reports the test-time results of ART and both baselines. We observe that in all environments, ART consistently outperforms Naive Training when under
10

---

Published in Transactions on Machine Learning Research (08/2024)
Figure 4: Consecutive snapshots of agents under attack by adversaries in the Pursuit environment: the first row a result of Naive Training and the second is result of ART(k=1). For better visibility, zoomed in the of interest (indicated by the red dotted area). A full version can be found in the Appendix (see the Supplementary Material). Red circles correspond to adversarial agents, green to benign agents, and blue to evaders, the orange boxes to the field of view of agents. Yellow arrows show the movement of the adversary in the upper row and benign agents in the lower row. Naively trained agents expect cooperation, leading agents being easily fooled. The adversary moves upward instead of left, resulting in the prey not being captured. Agents trained with ART learned to effectively avoid contact with other agents, until they arrive at a specific location. This technique ensures that every group of agents, there are always enough benign agents present to fully surround prey.
10
-5-
Spread(k=1)
Spread(k=2)
Ant(k=1)
Pursuit(k=1)
Pursult(k=2)
Pursuit(k=4)
Figure 5: Achievable increase in the performance of a single agent, i.e., victim, after we train the benign agents and adversaries described in Table 1. We consider one fixed victim agent and different runs with different seeds. each we train the benign policies until convergence using ART. Afterward, select one agent and train adversary attacking the selected agent. Then, training the selected agent continued for 5% of the original number of training steps, while keeping all other policies fixed. Depicted is the difference between the performance of the the players have converged to an ARNEQ, then further training a given agent when the rest of the players keep playing fixed strategies should not imply increased performance for this player. Otherwise, this would mean there is room for improvement which would violate the very condition of an equilibrium. Note that, average, performance tends to stay the same, except for some small oscillations which are due to the stochasticity of deep RL methods. This suggests that players are close to an ARNEQ.
improved policy and the original performance.
attack. Fixed-K training results in a more robust policy than naive training, but the benign agents tend to overfit to the adversaries present during training, resulting in worse performance when under attack by different adversarial agents. The importance of anticipating the correct number of adversaries during the training procedure is cnvironment-speciff.. In Independent Spread, optimal performance of ART is achieved if the number of adversaries during training matches their number at deployment time. In pursuit, training with a smaller number adversaries yields better performance in all scenarios. We conjecture that this may be due to the hardness of training with a larger number of adversarial agents. In the Independent Spread and Ant environment the resilience against adversarial attacks of ART and Fixed-K comes at the cost of decreased performance in clean environment. Tn Pursuit, adversarial training is beneficial even when there
11

---

Published in Transactions on Machine Learning Research (08/2024)
is no attack. This can, in part, be explained by examining the behavior of the trained agents, which we discuss in the qualitative analysis.
Qualitative analysis. Next, we analyze how the behavior of agents trained with ART differs from naive training in the examined environments. For Independent Spread, Figure 2 shows that agents trained using ART opt for longer routes, strategically avoiding potential adversaries. This behavior explains the observed difference in performance when comparing ART and naive training in clean and adversarial environments. For Ant, Figure 3 depicts the ability of ART to train agents that are able move the ant forward even if one leg is acting maliciously. As can be seen in the figure, we do not learn such robust policy with Naive Training. For Pursuit, Figure 4 depicts that agents trained using ART meet up at specific point at the beginning of the episode. This strategic rendezvous not only allows them to navigate the environment in a trusted group, enabling them to bypass interactions with adversaries but seems to contribule to improved performance even when not under attack.
Convergence. Finally, we aim to evaluate the convergence of ART by analyzing the achievable increase in performance of single agent. A small increase signifies the approxinate convergence of ART to an ARNEQ. Figure 5 depicts this increase in performance for all evaluated environments and differing numbers of adversaries. As the achieved improvement is small, this suggests that we approach ARNEQ.
6 Concluding Discussion
We considered the problem of defending against unknown adversarial policies in general-sum Markov games. We proposed a novel solution concept, namely, the adversarially robust Nash equilibrium (ARNEQ). Further, we provided a theoretical characterization of our solution concept and analyzed a centralized method for computing it. We also proposed practical decentralized algorithm to compute an ARNEQ and empirically demonstrated its efficiency across three different environments.
On the experimental front, our paper provides comprehensive results in three different multi-agent reinforce- ment learning environments, all of which showcase the benefit of using our defense algorithm at training, Conducting further experiments on more challenging environments with more agents would provide further insight into the efficiency of our method. The nature of our algorithm necessitates the simultaneous computa- tion of as many estimates as there are players, for each individual player. Thus, it would be interesting to see how scalable our method is for large games. Here, approaches such as mean-field multi-agent reinforcement learning might provide essential tools.
On the theoretical front, we provided characterization results for convergence in centralized setting of our model. A key open question that is left in the paper is whether we can restrict the attack model so that we are able to provide theoretical convergence guarantees on independent gradient-based based learning methods in more structured regimes. For instance, in Markov potential games, it is known that independent learning converges to an approximate Nash equilibrium due to a common potential function for all players. Under our attack model, this game structure is damaged, since the players constantly update their estimates of utilities for the other players training time which are different from the original utilities of the underlying game. Thus, a natural rescarch question would be: we utilize the underlying potential function, and characterize the quantity of deviation of the modified value functions from their original values using this potential function? Addressing such question is an interesting future research direction.
Acknowledgments
This research was, in part, funded by the Deutsche Forschungseemeinsccaatt (DFG, German Research Foundation) - projectt number 467367360.
References
Michele Aghassi and Dimitris Bertsimas, Robust Game Theory. Mothematical programming, 107(1-2):231-21)) 2006.
12

---

Published in Transactions on Machine Learning Research (08/2024)
Moshe Babaioff, Robert Kleinberg, and Christos H Papadimitrion. Congestion Games with Malicious Players. In ACM, 2007.
Kiarash Banihashem, Adish Singla, and Goran Radanovic. Defense Against. Reward Poisoning Atlakk Reinforcement Learning. TMLR, 2023.
Vahid Behzadan and Arslan Munir. Whatever does not Kill Deep Reinforcement Learning, Makes it Stronger. CoRR, 4b8/1712.09344, 2017.
Shubham Bharti, Xuezhou Zhang, Adish Singla, and Jerry Zhu. Provable Defense against Backdoor Policies in Reinforcement Learning. In NewrIPS, 2022.
Yiding Chen, Xuezhou Zhang, Kaiqing Zhang, Mengdi Wang, and Xiaojin Zhu. Syzantine-Robust Online and Offline Distributed Reinforcement, Learning. In ICML, 2023.
Jongeun Choi, Songhwai Oh, and Roberto Horowitz. Distributed Learning and Cooperative Control for Multi-agent Systems. Automatica, 45, 2009.
Jorge Cortes, Sonia Martinez, Timur Karatas, and Francesco Bullo. Coverage Control for Mobile Sensing Networks. IEEE Transactions on robotics and Automation, 20, 2004.
Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitrion. The Complexity of Computing Nash Equilibrium. Communiiattion of the ACM, 52, 2009.
Constantinos Daskalakis, Dylan Foster, and Noah Golowich. Independent Policy Gradient Methods for Competitive Reinforcement Learning. In NeurIPS, 2020.
Dongsheng Ding, Chen-Yu Yu Wei, Kaiqing Zhang, and Mihailo Jovanovic. Independent Policy Gradient for Large-scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-agnostic Convergence. In ICML, 2022.
Kfir Eliaz. Fault Tolerant Implementation. The Review of Economic Studies, 69, 2002.
Jerzy A Filar and Koos Vrieze. Competitive Markow Decision Processes. Springer Science & Business Media, 2012.
Arlington M Fink. Equilibrium in Stochastic n-person Game. Journal of Science of the Hiroshima University, 28, 1964.
Angeliki Giannou, Kyriakos Lotidis, Panayotis Mertikopoulos, and Emmanouil- Vasileios Vlatakis- Gkaragkounis. On the Convergence of Policy Gradient Methods to Nash Equilibria in General Stochastic Games. In NewrIPS, 2022.
Adam Gleave, Michael Dennis, Cody Wild, Neel Kant, Sergey Levine, and Stuart Russell. Adversarial Policies: Attacking Deep Reinforcement Learning, In ICLR, 2020.
Wenbo Guo, Xian Wu, Sui Huang, and Xinyu Xing. Adversarial Policy Learning in Two-player Competitive Games. In ICML, 2021.
Jayesh K Gupta, Maxim Egorov, and Mykel Kochenderfer. Cooperative Multi-agent Control Using Deep Reinforcement Learning. In ICAAMS, 2017.
Junling Hu and Michael P Wellman. Nash Q-learning for General-sum Stochastic Games. JMLLR, 4, 2003.
Sandy Huang, Nicolas Papernot, lan Goodfellow, Yan Duan, and Pieter Abbeel. Adversarial Attacks on Neural Network Policies. In ICLR Workshop, 2017.
Fivos Kalogiannis, Joannis Anagnostides, Ioannis Panageas, Emmanouil-Vasiln Vasilcios Tatakis-Gkaragkoniis Vaggos Chatziafratis, and Stelios Stavroulakis. Efficiently Computing Nash Equilibria in Adversarial Team Markov Games In ICLR, 2023.
13

---

Published in Transactions on Machine Learning Research (08/2024)
Erim Kardeg, Fernando Ordóñeez, and Randolph W Hall. Discounted Robust Stochastic Games and an Application to Queueing Control. Operalions Research, 59, 2011.
Panagiola Kiourti, Kacper Wardega, Susmit Jha, and Wenchao Li. Trojdrl: Evaluation of Backdoor Atlacks on Deep Reinforcement Learning. In ACM/TEEE (DAC), 2020.
Jernej Kos and Dawn Song. Delving into Adversarial Attacks on Deep Policies. CoRR, abs/1705.06452. 2017.
Aounon Kumar, Alexander Levine, and Soheil Feizi. Policy Smoothing for Provably Robust Reinforcement Learning. CoRR, abs/2210.11422) 2021.
Lior Kuyer, Shimon Whiteson, Bram Bakker, and Nikos Vlassis. Multi-agent Reinforcement Learning for Urban Trafic Control using Coordination Graphs. In ECML PKDD, 2008.
Jac Won Lee, Jonghun Park, O Jangmin, Jongwoo Lec, and Euyscok Hong. A Multi-agent Approach Q-Learning for Daily Stock Trading. IEEE Transactions on Systems, 37, 2007.
Stefanos Leonardos, Will Overman, Ioannis Panageas, and Georgios Piliouras. Global Convergence of Multi-agent Policy Gradient in Markov Potential Games. CoRR, abs/2106.01 01999, 2021.
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 AAAI, 2019.
Simin Li, Jun Guo, Jinggiao Xiu, Xini Yu, Jiakai Wang, Aishan Liu, Yaodong Yang, and Xianglong Liu. Byzantine Robust Cooperative Multi-agent Reinforcement Learning as a Bayesian Game CoRR, abs/2305.1 12872, 2023.
Tianyi Lin, Chi Jin, and Michael Jordan. On Gradient Descent Ascent for Nonconves-coneare Minimax Problems. In JCML, 2020.
Yen-Chen Lin, Zhang-Wei Hong, Yuan-Hong Liao, Meng-Ti Shih, Ming- Yu Liu, and Min Sun. Tactics of Adversarial Attack on Deep Reinforcement Learning Agents. IJCAI, 2017.
Qinghua Liu, Yuanhao Wang, and Chi Jin. Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limits. In /CML, 2022.
Xiangyu Liu, Souradip Chakraborty, Yanchao Sun, and Furong Huang. Rethinking Adversarial Policies: A Generalized Attack Formulation and Provable Defense in Multi-agent RT. CoRR, abs/ hbs/2305.11342. 2023.
Ryan Lowe, Yi I Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent Actor-critic for Mixed Cooperativo-competiiv Environments. In NewrIPS, 2017.
Thodoris Lykouris, Max Simchowitz, Alex Slivkins, and Wen Sun. Corruption-robust Exploration in Episodic Reinforcement Learning. In COLT, 2021.
Daniel Mankowitz, Timothy Mann, Picrre-Luc Bacon, Doina Precup, and Shic Mannor. Learning Robust. Options. In AAAI, 2018.
Mohammad Mohammadi, Jonathan Nöther, Debmalya Mandal, Adish Singla, and Goran Radanovic. Implicit Poisoning Attacks in T Two--gent Reinforcement Learning: Adversarial Policies for Training-time Attacks. In AAMAS, 2023.
Philipp Moritz, Robert Nishihara, Stephanie Wang, Alexey Tumanov, Richard Liaw, Fric Liang, Melih Flibol, Zongheng Yang, William Paul, Michael Jordan, et al. Ray: A Distributed Framework for Emerging Al Applications. CoRR, abs/1712 1tss/7722.0588) 2018.
Andi Nika, Adish Singla, and Goran Radanovic, Online Defense Strategies for Reinforcement Learning Against Adaptive Reward Poisoning. In AISTATS, 2023.
Martin Osborne and Ariel Rubinstein. A Course in Game Theory. MIT press, 1994.
14

---

Published in Transactions on Machine Learning Research (08/2024)
Praveen Palanisamy. Multi-agent Connected Autonomous Driving using Deep Reinforcement Learning. In IJCNN, 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An Imperative Style, High-performance Deep Learning Library. In NewrIPS. 2019.
Anay Pattanaik, Zhenyi Tang, Shujjing Liu, Gautham Bommannan, and Girish Chowdhary, Robust Deep Reinforcement Learning with Adversarial Attacks. CoRR, abs/ abs/1712.03632, 2017.
Bei Peng, Tabish Rashid, Christian Schroeder de Witt, Pierro-Alexande Kamienny, Philip Torr, Wendelin Böhmer, and Shimon Whiteson. Facmac: Factored Multi-agent Centralised Policy Gradients. NewrIPS, 2021.
Julien Perolat, Bart De Vylder, Daniel Hennes, Eugene Tarasso, Florian Strub, Vincent Boer, Paul Muller, Jerome T Connor, Neil Burch, Thomas Anthony, al. Mastering the Game of Stratego with Model-free Multingent Reinforcement Learning. Science, 378, 2022.
Amin Rakhsha, Goran Radanovic, Rati Devidze, Xiaojin Zhu, and Adish Singla. Policy Teaching via Environment poisoning: Training-time Adversarial Attacks Against Reinforcement Learning. In ICML, 2020.
Martin Roesch, Christian Linder, Roland Zimmermann, Andreas Rudolf, Andrea Hohmann, and Gunther Reinhart. Smart Grid for Industry using Multi-agent Reinforcement Learning. Applied Sciences, 10, 2020.
Reazul Hasan Russel, Mouhacine Benosman, and Jeroen Van Baar. Robust Constrained-MDDS: Soft- Constrained Robust. Policy Oplimization under Model Uncertainty. CoRR, abs/2010.04870, 2020.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal Policy Optimization Algorithms. CoRR, 0bs/1707.06344 2017.
Shai Shalev-Shwartz, Shaked Shammah,, and Amnon Shashua. Safe, Multi-agent, Reinforcement Learning for Autonomous Driving. CoRR, abs/1610.03295, 2016.
Lloyd S Shapley. Stochastic Games. Proceedings of the National Academy of Sciences, 3991011009 1953.
Ali Shavandi and Majid Khedmati. A Multi-agent Deep Reinforcement Learning Framework for Algorithmic Trading in Financial Markets. Expert Systems with Applications, 208, 2022.
Adam Smith. An Inquiry into the Nature and Causes of the Wealth of Nations: Volume One. 1776.
Jianwen Sun, Tianwei Zhang, Xiaofei Xie, Lei Ma, Yan Zheng, Kangjie Chen, and Yang Liu. Stealthy and Efficientt Adversarial Attacks against Deep Reinforcement Learning. Tn AAAT, 2020a.
Yanchao Sun, Da Huo, and Furong Huang, Vulnerability-wware Poisoning Mechanism for Online RL with Unknown Dynamics. In ICLR, 2020b.
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy Gradient Methods for Reinforcement Learning with Function Approxination. NewrIPS, 1999.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A Physics Engine for Model-based Control. In TEFE/RSJ, 2012.
Oriol Vinyals, Tgor Babuschkin, Wojeiech M Czarnecki, Michaöl Mathieu, Andrew Dudzik, Junyoung Chung, David Н Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster Level in Starcraft 11 using Multi-agent Reinforcement Learning. Nature, 575, 2019.
Tony Tong Wang, Adam Gleave, Tom Tseng, Kellin Pelrine, Nora Belrose, Joseph Miller, Michael D Dennis, Yawen Duan, Viktor Pogrebniak, Sergey Levine, al. Adversarial Policies Beat Superhuman Go Als. In ICML, 2023.
15

---

Published in Transactions on Machine Learning Research (08/2024)
Yue Wang and Shaofeng Zou. Online Robust Reinforcement Learning with Model Uncertainty. In NearIPS, 2021.
Yue Wang and Shaoteng Zou. Policy Gradient Method for Robust Reinforcement Learning. In ICML, 2022.
Yue Wang, Esha Sarkar, Wenging Li, Michail Maniatakos, and Saif Eddin Jabari. Stop-and-go: Exploring Backdoor Attacks on Deep Reinforcement, Learning-based Traffic Congestion Control Systems. TEFF Transactions on Information Forensics and Security, 16, 2021.
Chen-Yu Wei, Chung-Wor Wei Lee, Mengxiao Zhang, and Haipeng Luo. Last-iterate Convergence of Decentralized Optimistic Gradient Descent/ Ascent in Infinite-hoizoon Competitive Markov Games, In COLT, 2021.
Fan Wu, Linyi Li, Zijian Huang, Yevgeniy Vorobeychik, Ding Zhao, and Bo Li. CROP: Certifying Robust
Policies for Reinforcement Learning through Functional Smoothing. CoRR, abs/2106.0928) 09299,, 2021.
Fan Wu, Linyi Li, Chejian Xu, Huan Zhang, Bhavya Kailkhura, Krishnaram Kenthapadi, Ding Zhao, and
Bo Li. COРA: Certifying Robust Policies for Ofllne Reinforcement Learning against Poisoning Attacks. CoRR, abs/22 0////2203.8339. 2022.
Hang Xu, Rundong Wang, Lev Raizman, and Zinovi Rabinovich. Transferable Environment Poisoning:
Training-tiin time Attack on Reinforcement Learning. In ICAAMS, 2021.
Yaodong Yang, Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang. Mean Field Multi-agent Reinforcement Learning. In ICML, 2018.
Zhaoyuan Yang, Naresh lyer, Johan Reimann, and Nurali Virani. Design of Intentional Backdoors in Sequential Models. CoRR, abs1902.09972, 2019.
Sihan Zeng, Thinh Doan, and Justin Romberg. Regularized Gradient Descent Ascent for Two-player Zero-sum Markov Games. In NewrIPS, 2022.
Huan Zhang, Hongge Chen, Duane Boning, and Cho-Jui Hsich. Robust Reinforcement Learning on State Observations with Learned Optimal Adversary. CoRR, abs/2101.08452, 2021a.
Kaiqing Zhang, Tao Sun, Yunzhe Tao, Sahika Gene, Sunil Mallya, and Tamer Basar. Robust Multi-agent Reinforcement Learning with Model Uncertainty. In NewrIPS, 2020.
Runyu Zhang, Zhaolin Ren, and Na Li. Gradient Play in Stochastic Games: Stationary Points, Convergence, and Sample Complexity. CoRR, abs/2106.00198, 2021b.
Xuezhou Zhang, Yiding Chen, Xiaojin Zhu, and Wen Sun. Corruption-robust Offline Reinforcement Learning. In AISTATS, 2022.
Ming Zhou, Jun Luo, Julian Villela, Yaodong Yang, David Rusu, Jiayu Miao, Weinan Zhang, Montgomery Alban, Iman Fadakar, Zheng Chen, Aurora Chongxi Huang, Ying Wen, Kimia Hassanzadeh, Daniel Graves, Dong Chen, Zhengbang Zhu, Nhat M. Nguyen, Mohamed Elsayed, Kun Shao, Sanjeevan Ahilan, Baokuan Zhang, Jiannan Wu, Zhengang Fu, Kasra Rezace, Peyman Yadmellat, Mohsen Rohani, Nicolas Perez Nieves, Yihan Ni, Seyedershad Banijamali, Alexander Cowen-Rivers, Zheng Tian, Daniel Palenicek, Haitham Bou- A Ammar, Hongbo Zhang, Wulong Liu, Jianye Hao, and Jun Wang. SMARTS: Scalable Multi-agent Reinforcement Learning Training School for Autonomous Driving. CoRR, abs/2010.09776, 2020.
16

---

Published in Transactions on Machine Learning Research (08/2024)
Appendix
Table of Contents
A Proof of Existence (Theorem 1)
17
A.1 Auxiliary Results
17
A.2 The Proof of Theorem
21
B Proof of Convergence of Adversarially Robust Nash Q-Learning (Theorem 2)
C Experiments: Environments
24
C.1 Independent Spread
21
C.2 Multi-Agent Aut
25
C.3 Pursuit
25
D Experiments: Hyperparameters
25
Experiments: Computing Infrastructure
F Experiments: Runtime
26
A Proof of Existence (Theorem 1)
For the existence proof, we will use the Kakutani's fixed point Theorem. This result has been classically used proving the existence of Nash equilibria various types of Markov games. Tt requires the careful construction of a set-valued function whose fixed point would represent the equilibrium of the game of interest. Once the construction made, the theorem states (hat, such function satisfies some technical conditions, then the existence of its fixed point is guaranteed, thus effectively proving the existence of an equilibrium of the game. This will be our approach in the following. First, we will prove some auxiliary results related to properties such as contraction, continuity, and convexity. Then, we will construct a set-valued function whose fixed point would represent an ARNEQ and further show that it satisfies the technical conditions of Kakutani's fixed point theorem.
A.1 Auxiliary Results
In this section we prove some auxiliary results which will be needed in the proof Theorem
We will the following definitions only for this section. Fix an arbitrary state and player i. Let a denote benign policy n:(-1s) of player i at state 8, and let y denote the joint policy x=s(-1s) of the rest of the benign players. Moreover, let zi denote strategy Wi, but only applied on state s. We also denote by X' the policy space A(A,) and by y the joint policy space X)z;A(A;). Note that we do not assume action spaces that depend on the state. Let Z = X x y denote the whole policy space II.
adversarial joint policy f.(-ls) and w denote the randomized
Now, given a vector of value functions (V") in some compact value function space V1 ... x Vn, let define, for each player E N and state E S, the function
I ( 2ig wt, Vt)= Ear fatt [R(s,a) + (P(ss)))
Next, let us define
v5 V4)
min min ft (of. 2g. V+)
17

---

Published in Transactions on Machine Learning Research (08/2024)
and
v (vT' Vo
max 0 (1 v. V*).
o exex
Note that, the spaces X, V; and Q2 are compact spaces (closed and bounded) as policy spaces. Our first result shows that the mapping & is contraction mapping on the value function spaces.
Given joint policy æ, let 22 :V + V, be such that, for each i,s we have vz(V) = (V. V.)) Then, the mapping v a contraction mapping.
Lemma 1
Proof:
Let V,U E V. Fix a player i and state s. Note that we have
wid (U= -
max o v5 vo - max &i (1 Uo UT) BEE
aEE
10 Us V') - C V5 U*)
min min f (o,, U w/, V*)
min min ft (T,, y. (, se af wfe
RE En,
S I (Th Uo 2 Rs v fb V. 1 Uti
(R(s, a) + (P a), v\)) (R(s..)) (()(s))))))()(()()+)))))))))) (P((s.))))))
Ba
G S>|lv'
1 l (P(s, V U
where for the first inequality, we let Ty be the maximizer of ( V*), for the second inequality we let (%, w)) be the minimizer of fi (7), y, , wg, U*) and for the last inequality we use Hölder.
Next, we will show that there exists unique robust value vector of the above mapping, a result that follows from Banach's contraction theorem which we state below.
Theorem 3 (Banach's Contraction Mapping Theorem) Let (V,ll-I) be a complete metric space and let dh V + V be a contraction mapping. Then there exists a unique fixed point of the function vb.
Lemma 2 For any given joint policy x, player E N and state 8 S S, there exists unique value veclor V such that
V = max min min fi (r yo 24, wt, Vi) = (v afeN efeY wiEn:
Note that, the fact that the metric space 1l is complete, since V is compact, together with Lemma 1 above, implies the desired result as consequence of Banach's contraction mapping point theorem (Theorem 3).
Proof:
Now we need to show that our functions fi are cquicontinuous. First, let define the following norm jointly policies and value functions. Given joint policies x and y, and value functions V and U, for every state and player let
d ((x,, V\), (va, U')
| - veal + max iEN.
max
V #ES
Ui]
where va denotes the joint policy vector for state 8, #ta denotes the probability of player i taking action a A₁ in state 8, while V denotes the value of state for player i with respect to value vector V.
Lemma 3 Fir s S and player i. Given e > 0, there erists ō(e) > 0, such that, if for any p (I,, Vi) and q (ye, U)) we have d(p.g) < 5(e), then, for all 21 E y and w E Pi have
[S sh Vt) fu,,, 2 w Ut) <e.
18

---

Published in Transactions on Machine Learning Research (08/2024)
First, note that, since rewards are in the unit interval, value functions bounded by 1/(1 -7). Letting p (x:, V) and (Us, U), we have
Proof:
(a zas wa, vi) (y = way U³) [R(s,a) + (P(s,a), v*)] - (a (7(ss))+
(are (wt)
< EK mani
EI DEAGER
II tg
(R(s,a)+ + (P)
son
say
EI aEAJEK
II IgK
+ (P(s. I (
s0y
ΣI
sa; II lgK
d (R(s,a) + (P
JEK
E aEAjEK-
2 say
II lgK-
Vea. (R(s,a) + (P(s.))))))
II
20aj
II
Il
Year
a)
REA JEK
lgK"
lgk
+イ Σ
II
II
II IgK*
(P(s,a))Vi)
200
acA
JEK
IEK'
II JEK*
say II lEK-
Ysaa
(iss,a),v--U""
aEAA
II
II IgK
fif
Meas
Zeaj
sar
ysar
uEA JEK'
IEK*
acA
JEK
IEK
IęK
+ Σ
II
Ji 880y
II IgK
Via. ||V
-U'll
aEA
JEK
Σ AEA
II JEK
II IEK
x 801
II Yeay KgK
+7A" VIV - U'
where the second inequality follows from Hölder's inequality, where K denotes the set that maximizes the difference inside the absolute value; for the third inequality we have just used an algebraic artifice, adding and subtracting term related y and V and then rearranging: the third incquality uses the fact that the rewards are in the unit. interval, and Hölder's inequality.
Now, let us define
(1 (1- min(e, 1} (c) 2(2n-k Am and 52(e) min 1)
271""
Moreover, let ai = via, 2 Assume that la < min(f8 {2()), and V - - < (c),
for any player i E N,, state E S and action a E A. For the first. term on the right-hand-side of the last. equality above, we have
L aEA
II
II KEK-
II
Ysaa
JEK
1 K-
19

---

Published in Transactions on Machine Learning Research (08/2024)
ΣI BEAJEK
2s ssag
E
II IME
assaa
II mgMO
Usa
MCM 1M121
ΣI
Σ
II MEM
5,0m
1 BEAJEK
MCM |M111
1 E
2,00m
MEAMCMKK [
$2
where the first inequality follows from the algebracc identily
Rー
n- II
) MEMO
III
II
Σ
II a sam
yaam aggam
Yeam
yeam
MCN 1M21
the second incquality follows from the fact that the product of numbers in the unit interval is no greater than I; the third inequality uses a similar argument on the policies zia, and the rest the differences a'am. except
am' so where we note that ar are also the unit interval; the last incquality follows by definition of 61
On the other hand, note that we also have
AA" 1|v 1ill 2
by definition of (e).. Thus, we obtain that
(1,, 2 wh, Vt) f. 2y wz))
2 =c.
Next, will state the following lemmas, which will be the rest of the necessary ingredients for the existence proof. We omit their proofs, since they follow the same lines as in (Kardeş et al., 2011; Fink, 1964). First, let us define the unique best response for player i as
イのrー) Vi V max min min fr UT' w 2f, V').
at
Lemma 4
The function o', (2', y Vt) is continuous in all its variables, for all i E N and E S.
Proof:
The result immediately follows from the fact that the pointwise minimum of a family of equicontinuous
functions is continuous.
Lemma 5
The function (x yo Vi) is concave in xy for a fixed u and Vi.
Proof:
The result immediately follows by definition of $5.
Lemma 6 The function (/ Vt) continuous in y Furthermore, the set (155 V'VVV' is bounded]
is equicontinuous.
Proof:
The result follows from Lemma 3 above and Lemma 3 in (Fink, 1964).
Lemma 7 If the sequence y -in goes to y and (5 goes to V as goes to co, then
T)( V
20

---

Published in Transactions on Machine Learning Research (08/2024)
Proof: Observe that
IV vi [v)] S VV - (1 + (m))))
h.) -v,','" r: [m) + |i r: vi(u, vD]
for every n 2 L, E N and
S. Now note that VV=- bm)l 0 and ( -:((=,m) v (y viyl 7 0, as n + wo, by assumption. Moreover, Lemnna 6 implies
that [T - (y= (i))) = (1. :. - -05', (y - 0, as n 7 co. Hence, [V (2(ymm + O, as + 00.
A.2 The Proof of Theorem 1
In this section, we will conclude the proof of Theorem 1. In order to do that, will make use of the famous Kakutani's fixed point theorem which we state below. First, let us define the notion of upper semi-continuous functions, which is a precondition of this result.
Definition 4 A correspondence k : Z + 2 is said to be upper semicontinuous if yn E <(Zx), for all 2 1, lim In and lim,-to Vn y imply that x(x).
With this, we can now state Kakutani's fixed point theorem.
Theorem (Kakulani's fixed point theorem) If 2 is a closed, bounded and conver set in a Euclidean space, and K is an upper semicontinuous correspondence mapping Z into the family of closed conver subsets of Z, then there erists Z such that x = x(x).
We will construct a correspondence that satisfies the conditions of the theorem, and show that its fixed point is an equilibrium point. The correspondence we need is the following:
<(x) = 3: v. E arg max ol V*), V max o (' v"), VV, agex
ufEx
In the previous section, we have shown that the functions of satisfy continuity. We will further show that the defined set function x satisfies the conditions of Kakutani's theorem. Let us first restate Theorem for convenience, and then proceed to its proof.
Let G be a finite game with n players and let < n. Assume that an arbitrary subset of at most players use arbitrarily modified utilities, and assume that the mixed strategies of all plagers lie in compact sets. Also, assume that, for each player E N,, the sets Q are compact. Then, a k-ARNEQ, as given in Definition 2 erists.
Statement
We will use the same argument in the proof of Theorem 4 of (Kardey et al., 2011). We repeat the argument here with our notation for completion.
Proof:
Given i E s E S, Lemma 4 shows that the function (1 v, V*) is continuous in all of its variables. This, together with the fact that its domain is compact, implies that of achieves its maximum, that is arg ea (u,, x5 Vi) of D. On the other hand, Theorem implies that V = max (%(2%, v. vi). Thus, we have that x(x) # 0, by definition of above.
Next, show that n(x)) is convex set. Suppose that u,w k(x), for some (ut,..., ,u',..., u²) and (u'...., U)) Then, for any y E Z, N and s E S, we have, by definition of x(x), that
V - - V') 0'(0,,
for any y/ Z. Thus, for any A E (0, 1], i E E S, and by concavity of di (vi. V'), we have
" V²) < V = X0 x.' V + (1 2)0 V*) - 05 (Quu, + (1 2
21

---

Published in Transactions on Machine Learning Research (08/2024)
V
which implies that Aug + (1 Ajug k(x). Thus, the image of is convex.
Next, will show that is upper semicontinuous. To that end, suppose that x" and y" - y, and that v" E x(("), for n 2 1. Note that Tf(x,"")) V² since x in + x x=, as a subsequence of (æ")n21- Using the triangle inequality, we obtain
10 (v.. V9) - v-l
- 0/ (v 2, V)
Φ (vt 2, 2.t - (1 (x)) + 0 (vt ,,," ,,,"""
-V
= - (yes ,5 v*)
of (u x. x-imm -/ -.n) + [ im)) V +0 as n + 00
Thus, V2 = (' 2, V*). Lemma also implies that r/ +) 1)= = V. Thus, we obtain
V = (''. v2) (z) max w
Therefore, n(x), which is what we needed, in order to prove that is upper semicontinuuus. The fact that <(x:) is closed set for any E X' follows by definition of upper semicontinuity. Thus, satisfies the conditions of Theorem 4, which implies that its fixed point exists, that is, there exists joint policies x = (x',..., x²) and value functions V ,..., V"), such that, for any E N and s E S, we have
x arg max min min E E w El, egey
(R(s,a) + (P((s,))))
and
V max min min E Bavaj of sta +7 og wgen ejyy
Thus, ARNEQ of G exists.
B Proof of Convergence of Adversarially Robust Nash Q-Learning (Theorem 2)
In this section, we will formally prove that the Nash Q-Learning approach to Adversarially Robust Training convergence to ARNEQ under certain technical assumptions. We first define some necessary additional notions and then state the assumptions.
Given t 2 1, let (s)())) denote the stage game at state s, where x((s) matrix of player i comprised of the Q-value estimates at time t. Recall that stage game ARNEQ (+I(s,s, (*)(()(()))))))))))))()) w=)s) wf)iE for state is defined as the joint policy that satisfies, for each i, the following:
is the game
( *+1ss, E arg max min BRoun nllll wie e'e
Σ (((asss) II TT(ayls) II [T(alss) IEK
DEA
We restate Assumption 3 for convenience.
Statement 2 For each stage gome at time t and state E S, one of the following conditions holds.
AA stage ARNEQ also a global oplimum, that is, for any E N and (-11),, we have
< (s) (axls) (a)
E Exaw!
> EKnws
LaEAA
Laed
for any स E IT, 7' E Ih and wi Ωt.
22

---

Published in Transactions on Machine Learning Research (08/2024)
A given player's payoff is increased if other benign plagers its attacker deviate, that is, for any E N we have
E EK
Σ (a= (ax (ss.,)) <
EKwu!
Auluaaaruuuunngl--oooooooooaaaaa LaEA
+((aals))
LaEd
for all n' ET, R'' E TT_; and wf E ΩQ.
Given that Assumptions 1, 2 and hold, we can proceed with our argument. We will prove the following result.
Lemma 8 For every player and round t, and for any given stage game matrix of Q-values Q((s), let
B Q + an operator on the Q-value function space Q defined as
B, = a) () KB
Σ (H L'EAA
for any given (s,a)-tuph atuple Then, By is contvaction operalor with respect to the Lo norm.
In order prove the above lemma, we will make use of the following standard result on pseudo-contractions.
Lemma 9 (Lemma of Hu Wellman (2003)) Assume that o satisfy Assumption 2 and that the mapping B Q satisfies the following condition: there exists a number 0 < < and a sequence "i 2 connerying to zero with probabilily such that
1 - B'Q < 7 11Q - +
for all Q E Q and Q such that Q" = =E(''Q") then the iteration defined by
Q++1 (1 ax)). + a.
converges to Q" with probability 1.
Now we are ready prove Lemma 8. In order do so, we need to show that its conditions are satisfied for our setting.
Proof: Let (Qi)ien and (Q)En be two given sets of Q-value functions. Denote by (5,, 75, wiliE and (T,, 7' wi)eE their corresponding ARNEQ policies, respectively. Let (s, a) be given state-action tuple and suppose we have
If the first part of Assumption holds, then have
0 < (8,,(8, - ()))(s
7
E Kmass
Σ
T k (4
E Exmus
Σ H' (1 (s)
L''A
La'EA
57
E K K
Σ
Σ
L''AA
La'AA
Σ (d' (Q,(s,,')) - c((3,aa))
=7 7 E EK
La'EA
S max KEN,
Th T (a'x (Q -
(Q,(s,
23

---

Published in Transactions on Machine Learning Research (08/2024)
Symax max a'EA
- - [()
<> p: D.
If the second part of Assumption 3 holds, then, instead we have
0 (s - (s,
EK mi
Σ
EKnu!
Σ
L'EA
La'EA
$ Y BK Knu mi.
[=<
Exwuw
La'AA
LO'EA
$ Y BKwu
Σ
1s) ( ())
Le'EA
Ex Exmay may!
LO'EA
Σ T((ails)T' ((dx)))'=<od<x>>>>) & (dx(s) ((((s,a')<(((sdd)))
Y
KEN:
a'EA
(i(8,aa) - c((),a))
S max d'Ed
$ 0 0f l.
where the second inequality follows from the equilibrium definition with respect to player i's policy and the third incquality follows by the second part of Assumption 3.
A similar argument is used for the case when we have
B,Q,(s,0) < { (.).
Since the chosen (s, a)-tuple was arbitrary, we conclude that
|300.-
1500.BB,011 -,e so|10, -
Thus, have shown that the operator B, is contraction. Recall that this operator has O fixed point. Furthermore, the rates ai, t 2 1, satisfy the requirements of Lemma 9. Hence, the result of Theorem 2 follows.
C Experiments: Environments
C.1
Independent Spread
This environment modifies the Spread environment from Lowe et al. (2017) in such way, that all agents pursue an individual goal, instcad of cooperating toward one shared objective. Each agent strives to reduce the distance to a landmark that. is designated to them while simultaneously avoiding collisions with other agents. Therefore, the reward of each agent consists of the negative Ly-distance to their designated landmark, coupled with a large penalty of for colliding with agents. Agents observe their position, as well as the relative position of their designated landmark and all peer agents. The action space consists of no-action well increasing the velocity in one of four directions.
24

---

Published in Transactions on Machine Learning Research (08/2024)
Figure 6: Full version of Figure 4 (zoomed out).
C.2
Multi-Agent Ant
We consider cooperative multi-agent extension of the MuJoCo Ant environment (Todorov et al., 2012) as proposed in Peng et al. (2021). Agents control one leg of the ant, and need to cooperate with the other legs maximize the distance traveled forward, while maintaining balance. Consoquentially, each agent receives shared reward, which consists of the forward momentum compared to the preceding frame and small incentive of 0.1 reward for not falling contact, as the adversary could easily exploit this reward function without actually impacting the ant 's objective and there is defence mechanism for the other agents. Agents observe the position and orientation of all joints and can apply torque to the joint between the torso and upper leg and between the upper and lower leg of the leg they control.
We removed the penalty for large actions and high external
C.3 Pursuit
We finally consider the cooperative Pursuit environment Gupta el al. (2017). Each agent assumes the role of one of the eight pursuers aiming to catch 30 randomly moving evaders. Evaders are captured if they are enclosed on all sides by pursuers walls. Pursuers receive the reward of for every successful capture, well urgency reward of -0.1 every time step there is still prey left to be captured. Observations consist of all pursuers, evaders, and walls within 7x7 grid around the agent. The available actions are staying at the current position or moving one field to the left, right, up, or down.
Experiments: Hyperparameters
Hyperparameters for the PPO algorithm for all environments given in Table 7.
25

---

Published in Transactions on Machine Learning Research (08/2024)
Hyperparameter
Value for Spread
Value for Ant
Value for Pursuit
Total timesteps
800K
13M
10M
Batch size
4000
65536
5000
Minibatch size
128
4096
500
Epochs per update
30
30
30
Learning rate
0.0003
5 10
5 10
Discount Factor 7
0.99
0.99
0.99
Clipping parameter A
0.3
0.2
0.3
Advantage estimation discount À
1.0
0.95
0.95
Entropy coefficient
0.0
0.0
0.01
Value function loss coefficient.
1.0
0.5
1.0
Figure 7: Hyperparameters for Spread, Ant, and Pursuit
E
Experiments: Computing Infrastructure
Computing infrastructure for the Independent. Spread and Pursuit environment:
GPU; None
CPU: Intel Xeon E5-2667 v2
Memory: 256GBB DDR3, 1866 MHz, ECC
Operating System: Debian
The computing infrastructure the Ant environment:
GPU: V100 Nvidia Tesla GPU 32GB
CPU: Intel Xeon Gold 6134M
Memory: 768GB, DDR4 2666MT/ss, ECC
Operating System: Debian
F
Experiments: Runtime
Runtime for all algorithms and environments are given in Table 8.
Algorithm
Runtime for Spread
Runtime for Ant
Runtime for Pursuit
Independent Learning
27m28s
1h45m58s
10h6m
fixed-k
22m366
1846m48s
10h9m
ART
34m38s
1h50m24s
10h55m59s
Figure 8: Runtime of algorithms for Spread, Ant and Pursuit
26


Reviews:
[{"review_id": "jZzXRXgSkB", "reviewer": "Reviewer_aM2t", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I will keep strength and weaknesses concise and simply provide an overview. Please find more detailed questions in the requested changes.\n\nStrengths:\nFirst, the writing quality is good and the paper reads nicely. The notation style  is intuitive and the pseudocode provided facilitates understanding. Second, the author provide rigorous proofs for their theoretical contributions. They provide a proof of existence for their Adversarially Robust Nash Equilibrium (ARNEQ) under reasonable conditions. They also provide an interesting model-based method and a proof of convergence towards an ARNEQ for the model-based method. While the reviewer did not find any glaring mistakes in the proof, due to limited experience with such proofs, the reviewer cannot confirm with high certainty that there wouldn't be any errors. Questions regarding the proofs will be laid out in the requested changes.\nA third strength is the proposal of a model-free method called Adversarially Robust Training (ART), that is algorithmically more convenient to compute in contrast to their proposed model-based method. The authors provide sufficient empirical evidence that ART learns policies distinct from Naive Learning that improve performance over the baseline statistically significantly over 5 seeds. The submission is relevant to TMLR and most claims are clear, convincing and accurate with a few exceptions.\n\nWeaknesses: \nThe following section is meant to summarize where the reviewer thinks the paper could be improved the most. Detailed Questions and requested changes will be laid out in Requested Changes.\n\n First and foremost, the connection between the ARNEQ and ART is not sufficiently motivated. The transition from Section 3 to Section 4 simply states that the proposed model-based method is computationally infeasible and then a model-free method is proposed. While the objective function make intuitive sense, this transition could be improved through more theoretical or empirical results, or simply more clarification in writing. Second, and less importantly, some steps in the proofs of existence are hard to follow for an audience that is less experienced with such proofs. For example, can you motivate why you use Kakutani's fixed point theorem? Kakutani's fixed point theorem requires the definition of a semicontinuous correspondence. Does this assumption exclude any reasonable settings that the reader should be aware of? etc.\n\nThird, Section 4 and 5 could benefit from some clarifications, which I will lay out later.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose an interesting \"Adversarially Robust Nash Equilibrium\" (ARNEQ). They describe a realistic setting for adversarial attacks in Multi-Agent Reinforcement Learning and state how the ARNEQ is a useful notion of robustness in this setting. They position their work well with related work and their contributions are clearly stated. They provide an extensive proof of existence for ARNEQs in their specific setting. Furthermore, they present a model-based algorithm which provably finds ARNEQs. Next, they provide a model-free algorithm that intuitively should approximate ARNEQs. The authors demonstrate that the model-free method learns distinct policies from their reasonable baselines in three distinct, sufficiently high-dimensional environments. The ARNEQ and the model-free method are well motivated and simple, which adds to their potential impact on and relevancy for the field of adversarial attacks in Multi-Agent RL.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Questions and Requested Changes (RC):\n- *RC1 for proofs*: The proofs could benefit for more specific motivations at each step. Ideally, the authors would point out, when reasonable, if there are any relevant consequences for any assumption they make. For example, why does a correspondence need to be semicontinuous? The recommendation would not change, as the proofs, if correct, seem sufficiently detailed for a more knowledgable audience. Providing more details would simply make the proofs more understandable for a less knowledgable audience, which would also facilitate future work.\n\n- *RC2: For Section 4*: I believe it would be very helpful if the authors could clarify the consequences of using a model-free method as opposed to their previous model-based method. At the moment it is unclear if any of the convergences transfer or if any other connection can be made between the method in Section 3 and Section 4. They appear completely disconnected except for the intuitively similar objective functions. I believe the connection between Section 3 and 4 could be strengthened with different changes. First, the authors could simply state that any previous convergence guarantees do not hold anymore and it's not given that this method approaches an ARNEQ. Second, they could show that, in theory, ART still approximately converges to an ARNEQ (which they later claim empirically in Section 5.3.Convergence). Third, they could implement the method in Section 3 in a simpler environment, where it's computationally feasible to compute the model-based method, and provide empirical evidence that ART converges to the same equilibrium. Such a clarification would have an affect on securing a recommendation for acceptance.\n- *Question for Algorithm 1*: Why do we optimize wrt $\\theta^t_i$ and not $\\theta^(t-1)_i$ in Line 4 and 6? In a similar vein, if we already have a model of the opponent, why shouldn't we update our parameters $\\bar{\\theta}^{t-1}$ with respect to the parameter that the opponent will have in the next step $\\widehat{\\theta}_j^{i, t}$? Why would I update with respect to $t-1$?  For example, first you could update $\\widehat{\\theta}_j^{i, t}\\leftarrow \\mathcal{L}(\\theta_i^t, \\bar{\\theta}^{t-1}, \\widehat{\\theta}^{i, t-1})$ and then $\\bar{\\theta}^{t} \\leftarrow \\mathcal{L}(\\theta_i^t, \\bar{\\theta}^{t-1}, \\widehat{\\theta}^{i, t})$. That way you can approximate a best response to the update of the opponent will have. See Opponent Shaping research, especially LOLA [1] and LOQA [2], for related work. While I do not think the current version is incorrect, I think the authors could better motivate why we optimize with respect to $\\theta^t_i$ but not with respect to $\\widehat{\\theta}_j^{i, t}$, which would improve the paper.\n- *Question for Table 1*:   Why is (Fixed-k=2) == (ART-k=2). Doesn't (Fixed-k=2) always train against two adversaries and (ART-k=2) samples adversaries between $[1,2]$ as $\\Omega_i=\\Delta\\left(\\mathcal{N}_i\\right)$ and $\\mathcal{N_i}$ is the set of subsets of cardinality no greater than $k$. An answer to this question would probably also clarify some confusion for later questions and would affect in securing the recommendation.\n- *Question for Section  5.3.Quantitative Analysis*: In the current version, the explanation for Pursuit is unsatisfying, though sufficient for acceptance. If it was hardness of training, wouldn't you expect Fixed-k=1 to perform better in the 4 adversary case than Fixed-k=2 or Fixed-k=4? It seems that the argument \"hardness of training\" could always apply and is thus not particularly insightful. Could you argue that k=1 might be the optimal adversarial policy $\\theta$? But shouldn't $\\theta$ in ART-k=4 learn that? In general, given that there are many pursuers agents, it is unintuitive why there is a discrepancy between Fixed-k=1 and ART-k=1. Maybe the authors could clarify?\n- *Question for Section 5.3.Quantitative Analysis*: When the authors state \"In Independent Spread, optimal performance of ART is achieved if the number of adversaries during training matches their number at deployment time\", do they mean \"maximum number of adversaries during training\"?, since, to the best of my understanding, the number of actual adversaries is determined by $\\theta$ and changes across training steps in ART-k.\n- *Question for Section 5.3.Convergence*: Could the authors clarify what they mean by \"A small increase signifies the approximate convergence of ART to an ARNEQ.\"? First, it is unclear why ART would converge even approximately to an ARNEQ, as this hasn't been shown theoretically to the best of my understanding. Second, could the authors clarify what they mean by \"Depicted is the difference between the performance of the improved policy and the original performance.\" When they say \"original performance\", do they mean the performance of the originally benign-trained victim policy against the other benign policies or the benign victim policy against the adversarially trained policies? If it's the former, couldn't you argue that even a decrease in performance signifies converges to an ARNEQ?\n- *RC3 for Section 5.3.Convergence*: In general, it feels insufficient to say that this experimental setup has anything to do with the ARNEQ. The authors could clarify how this is connected to the ARNEQ more specifically. Otherwise, to strengthen the claim that ART converges to an ARNEQ, it would be much more convincing if you had an environment where the method from Section 3 is feasible to compute and compare ART with the method from Section 3, which would greatly improve the papers results and improve the connection between Section 3 and Section 4. To repeat, I find it sufficient to say \"we introduce a model-free gradient-based algorithm\nthat is able to empirically provide an efficient defense in various MARL environments.\", which the authors do in Section 3. I find the evidence insufficient to say that \"As the achieved improvement is small, this suggests that we approach an ARNEQ.\". Even if ART does not approximate ARNEQs, I find the algorithm, empirical evaluation and general motivation interesting for the TMLR audience.\n\n[1] Foerster, Jakob N., et al. \"Learning with opponent-learning awareness.\" arXiv preprint arXiv:1709.04326 (2017).\n[2] Aghajohari, Milad, et al. \"LOQA: Learning with Opponent Q-Learning Awareness.\" arXiv preprint arXiv:2405.01035 (2024).", "broader_impact_concerns": "I do not think that the current work requires a broader impact statement", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "jG0uysGfog", "reviewer": "Reviewer_MAs3", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The paper considers a very natural and well-motivated problem, as described above. Variants of that problem have already received attention in prior research, but to the best of my knowledge the problem has not been treated in this generality before. The paper does a great job at discussing related work, and I did not find any notable omissions. The story and the results of the paper are quite complete and compelling, and take an important step towards building tools to tackle adversarial corruptions in MARL. All results appear to be sound, and I did not detect any notable issues. The paper is also very well written and organized. I overall believe that the paper makes a concrete contribution on an important problem, and therefore deserves to be accepted for presentation.\n\nWeaknesses: On the negative side, the paper has arguably a limited technical contribution, and although the results are new, it heavily relies on known techniques and results. Moreover, the main algorithm used in the experiments does not have theoretical guarantees of convergence; nonetheless, this is to be expected as even computing Nash equilibria is known to be a hard problem. On that note, one suggestion for future work would be to follow the approach of the recent paper \"Approximating Nash Equilibria in Normal-Form Games via Unbiased Stochastic Optimization\" (presented at ICLR 2024). Finally, it would be interesting to see more experiments in the regime where k and n are much larger, but I understand that this could require different techniques and it is left for future work.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers a multiagent reinforcement learning (MARL) setting in which an adversary can arbitrarily corrupt a subset of the agents' policies at test time. To tackle such cases, the authors introduce a new solution concept, called adversarially robust Nash equilibrium (ARNEQ). They prove that ARNEQ always exists, and they provide a model-based algorithm that computes an ARNEQ. Moreover, in light of the impracticality of the previous algorithm, they also propose a more practical independent learning algorithm based on stochastic gradient descent, albeit with no theoretical guarantees. Experiments on standard benchmarks demonstrate the value of the proposed method in addressing adversarial corruptions in MARL.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I have the following comments, none of which is critical for securing acceptance.\n\n- The citation style is often used incorrectly. For example, in Section 1.1.1, it should read \"Adversarial attacks on RL systems have been extensively studied in recent years (Kiourti et al. (2020))\" instead of \"Adversarial attacks on RL systems have been extensively studied in recent years Kiourti et al. (2020)...\" Namely, use parentheses when it is not part of the sentence.\n- I am a bit confused as to the interpretation of Assumption 3, which does not seem standard. It would be nice if the authors can elaborate more on that. Also, the first bullet in Assumption 3 has to be explained further in the main body as it is not clear at all what it means.\n- There is a missing period (“.”) at the last displayed equation in page 23.", "broader_impact_concerns": "I do not have any concerns on the ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "UfEQBlenM7", "reviewer": "Reviewer_hWsb", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Producing tractable and useful equilibrium concepts for multiplayer environments is difficult, and robustness to unexpected interest is of interest a broad community, so a robust multiplayer equilibrium concept for Markov games seems like a contribution that could be of interest to a range of readers. The NN-based algorithm does not introduce a lot of extra complication on top of an existing multiplayer algorithm, making it worth trying in situations where robustness might be a concern.\n\nOne thing that might be missing is an argument for the form of attack being reasonable -- plausible use cases where this would be the right kind of attack to expect. As noted in the experiments looking at performance with no attack, there is a cost to defending against an attack that might not happen, and a not quite paranoid assumption that \"some number of agents might all collude to maximally impact my value with no respect to their own utility\" could be quite pessimistic in some environments.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors introduce ARNEQ, a equilibrium concept for multiplayer games, where each agent i is robust to adversarial opponent strategies that are trying to reduce i's utility rather than maximizing their own utility. The authors provide an argument for existence, and an impractical algorithm for finding it. Inspired by those two things, the authors also provide a practical NN-based algorithm, where an ARNEQ would be a globally optimal solution. The paper has experiments on a few domains using the ARNEQ adversary attacks, showing the algorithm produces a policy with higher value under attack than a baseline of independent PPO.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "“In our setting, this information is not given. As a consequence, there is no fixed game to be solved and thus, no well-defined NE.”\nPossibly just say something like “As a consequence, the problem is no longer a Markov game, and the solution is not a NE in that space.”  It is no longer a Markov game, but it’s not so obvious there’s no fixed game within a larger class of games, especially if you break the assumption that all states are reachable in a single episode: e.g., something like a POMDP that uniformly mixes over starting states that determine which agent the adversary is targeting, then let the adversary choose what agents to replace, then follow the original game dynamics except the controlled agents actions are ignored in favor of the adversary actions.\n\nSection 5.2 Figure 5: This measurement seems like it's measuring something slightly different than ARNEQ convergence: once the adversary is fixed, the player is free to drift further away from a robust policy because the adversary is no longer tracking and responding to that new behavior. The non-trivial decrease when all other agents and the adversary are fixed is puzzling, and possibly mildly concerning.\nLeaving aside the decrease in value after further traning, I think it’s reasonable to say low values in Figure 5 do indicate convergence as they’re upper bounds – the true increase in ARNEQ value for an agent should be less than leaving the adversary fixed, because the true value is a minimum over all adversary choices. I also think that extra step of indirection should be stated.\n\n\n------ Some smaller issues for clarity ------\n\n“this formulation renders the classical NE notion obsolete”  obsolete -> inappropriate?\n\nSection 3.2: V bar, Q bar*, ARNEQ: these all have very similar terms in the sum, but are all written slightly differently. It seems worth the effort to have a more consistent choice throughout, rather than shuffling terms and grouping them differently.\n\nFor Q bar* and ARNEQ, and the recursive update for ARNEQ after equation 2, I found the removal of min omega, pi hat from the equation and treating them as given to be less clear.\n\nSection 4, adversary loss on omega: add a general description in plain language. Something like \"the loss for the adversary to agent i is agent i's ARNEQ value\"?\n\nSection 4, adversary loss on pi hat: if it requires three lines to explain the difference from the loss on omega, the actual equation should also be included\n\nSection 5.2 “Agents trained with ART learned to meet at a specific rendezvous point unknown to the adversary”   Unknown because the adversary was not fully trained? Shouldn't the adversary be able to work out that rendezvous point, given access to (data describing) the agent policies?", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers agree that the paper is acceptable.
Decision: Accept (poster)