Certifiably Robust Policy Learning against Adversarial Multi-Agent Communication
Authors: Yanchao Sun
Ruijie Zheng
Parisa Hassanzadeh
Yongyuan Liang
Soheil Feizi
Sumitra Ganesh
Furong Huang
Venue: ICLR 2023 poster (2023)
Keywords: certifiable robustness
reinforcement learning
multi-agent system
adversarial communication
adversarial attack

Abstract: Communication is important in many multi-agent reinforcement learning (MARL) problems for agents to share information and make good decisions. However, when deploying trained communicative agents in a real-world application where noise and potential attackers exist, the safety of communication-based policies becomes a severe issue that is underexplored. Specifically, if communication messages are manipulated by malicious attackers, agents relying on untrustworthy communication may take unsafe actions that lead to catastrophic consequences. Therefore, it is crucial to ensure that agents will not be misled by corrupted communication, while still benefiting from benign communication. In this work, we consider an environment with $N$ agents, where the attacker may arbitrarily change the communication from any $C<\frac{N-1}{2}$ agents to a victim agent. For this strong threat model, we propose a certifiable defense by constructing a message-ensemble policy that aggregates multiple randomly ablated message sets. Theoretical analysis shows that this message-ensemble policy can utilize benign communication while being certifiably robust to adversarial communication, regardless of the attacking algorithm. Experiments in multiple environments verify that our defense significantly improves the robustness of trained policies against various types of attacks.

Published as a conference paper at ICLR 2023
CERTIFIABLY ROBUST POLICY LEARNING AGAINST ADVERSARIAL MULTI-AGENT COMMUNICATION
Yanchao Sun
Ruijie Zhengi
Parisa Hassanzadeh
Yongyuan Liang?
Soheil Feizi
Sumitra Ganesh Furong Huang
f University of Maryland, College Park {yes, rzheng12, sfeizi, furongh} @umd.edu
$ +JPMrra Research {parisa (parisa. hassanzadeh, sumitra.ganesh) jpmchase.com
8 Shanghai AI Lab
cheryllLiang @ outlook.com
ABSTRACT
Communication is important in many multi- ageti reinforcement learning (MARL) problems for agents to share information and make good decisions. However, when deploying trained communicative agents in real-world application where noise and potential attackers exist, the safety of communication-basel policies becomes a severe issue that is underexplored. Specifically, if communication messages are manipulated by malicious attackers, agents relying on untrustworthy communica- tion may take unsafe actions that lead to catastrophic consequences. Therefore, it is crucial to ensure that agents will not be misled by corrupted communication, while still benefiting from benign communication. In this work, we consider an environment with N agents, where the attacker may arbitrarily change the commu- nication from any C < N-1 agents to a victim agent. For this strong threat model, we propose certifiable defense by constructing message-enseeee ensembee policy that aggregates multiple randomly ablated message sets. Theoretical analysis shows that this message-ensemblle policy can utilize benign communication while being certifiably robust to adversarial communication, regardless of the attacking algo- rithm. Experiments in multiple environments verify that our defense significantly improves the robustness of trained policies against various types of attacks.
INTRODUCTION
Neural network-based multi-agent reinforcement learning (MARL) has achieved significant advances in many real-world applications, such as autonomous driving (Shalev-Shwartz et al., [016]] [Sallab] al.) 2017). In multi-agent system, especially in a cooperative game, communication usually plays an important role. By feeding communication messages as additional inputs to the policy network, each agent can obtain more information about the environment and other agents, and thus can learn a better policy (Foerster et al.) 2016; Hausknecht] (2066) Sukhbaatar et al. 2016). However, such communication-deeeedden policy may not make safe and robust decisions when communication messages are perturbed or corrupted. For example, suppose an agent is trained in cooperative environment with benign communication, and learns trust all communication messages and utilize them. But during test time, there exists a malicious attacker perturbing some communication messages, such that this agent can be drastically misled by the false communication.
The robustness of policy against adversarial communication is crucial for the practical application of MARL. For example. when several drones execute pre-trained policies and exchange information via wireless communication, it is possible that messages get noisy in hostile enviromment, or even some malicious attacker eavesdrops on their communication and intentionally perturbs some messages to a victim agent via cyber attacks. Moreover, even if the communication channel is protected by advanced encryption algorithms, an attacker may also hack some agents and alter the messages before they sent out (e.g. hacking IoT devices that usually lack sufficient protection (Naik & Maral 2017)). Figure D shows an example of communication attacks, where the agents are trained with benign communication, but attackers may perturb the communication during the test time. The attacker may lure a well-trained agent to a dangerous location through malicious message propagation and
Part of this work was done when the first author was intern JPMorgan AI Research.

---

Published as a conference paper at ICLR 2023
Agent
Agent
Agent 2
Agent 4
hoclid 13,
Agent
TOOTE 13,-13
Agent
Agent
Agent 1gyeetm)
Agents
(a) Training time
(b) Test time (in deployment)
Figure 1: An example of test-time communication attacks in a communicative MARL system. (a) During training, agents are trained collaboratively in a safe environment, such simulated environment. (b) In deployment, agents execute pre-trained policies in the real world, where malicious attackers may modify the benign (green) messages into adversarial (red) signals to mislead some victim agent(s).
cause fatal damage. Although our paper focuses on adversarial perturbations of the communication messages, it also includes unintentional perturbations, such as misinformation due to malfunctioning sensors or communication failures; these natural perturbations are no worse than adversarial attacks.
Achieving high performance in MARL through inter-agent communication while being robust to adversarial communication is a challenging problem due to the following reasons. Challenge I: Communication attacks can be stealthy and strong. The attacker may construct a false communication that is far from the original communication, but still semantically meaningful. In the example of Figure [b] the attacker alters "Bomb" to "Gold", which can mislead the victim agent to the location of a bomb. But the victim, without seeing the groundtruth, cannot see the maliciousness from the message itself. Note that the widely-used lp threat model (Chakraborty et al. 2018) does not cover this situation. Challenge II: The attacker can even be adaptive the victim agent and significantly reduce the victim's 's total reward. For instance, for a victim agent who moves according to the average of GPS coordinates sent by others, the attacker may learn to send extreme coordinates influence the average. Challenge III: There can be more than one attacker (or an attacker can perturb more than one message at one step), such that they can collaborate to mislead victim agent.
Although adversarial attacks and defenses have been extensively studied in supervised learning MMadry al. 2018 Zhang et al. 2019) and reinforcement learning (Zhang et al. 2200bb; [Sun al. 2022),
there has been little discussion on the robustness issue against adversarial communication in MARL
problems. Some recent works (Blumenkamp Prorok 2020; Xue et al.) 2022] Mitchell al., 2020)
take the first step to investigate adversarial communications in MARL and propose several defending methods. However, these empirical defenses do not fully address the aforementioned challenges, and are not guaranteed to be robust, especially under adaptive attacks. In high-stakes applications, it is
also important to ensure robustness with theoretical guarantees and interpretations.
In this paper, we address all aforementioned challenges by proposing certifiable defense named Ablated Message Ensemble (AME), that can guarantee the performance of agents when a fraction of communication messages get arbitrarily perturbed. Inspired by the ensemble methods which are proved to be the optimal defense against poisoning attacks under the iid sample setting (Wang et al., 2022), we propose to defend by ablation and ensemble of message sets, which tackles the challenging interactive decision-make making under partially observable environments with correlated message samples. The main idea of AME is make decisions based on multiple different subsets of communication messages. Specifically, for a list of messages coming from different agents, we train a message- ablation policy that takes in a subset of messages and outputs base action. Then, we construct an message-ensene ensemmble policy by aggregating multiple base actions coming from multiple ablated message subsets. We show that when benign messages are able reach some consensus, AME aggregates the wisdom of benign messages and thus is resistant to adversarial perturbations, no matter how strong the perturbation is. In other words, AME tolerates arbitrarily strong adversarial perturbations as long as the majority of agents are benign and uniting. Levine & Feizi (2020) use similar randomized ablation idea to defend against En attacks in image classification. However, they provide high-probability guarantee for classification, which is not suitable for sequential decision-making problems, as the guaranteed probability decreases when it propagates over timesteps.
Our contributions can be summarized as below:
(1) We formulate the problem of adversarial attacks and defenses in communicative MARL (CMARL). (2) We propose novel defense method, AME, that is certifiably robust against arbitrary perturbations
2

---

Published as a conference paper at ICLR 2023
of up to C N-1 communications under mild conditions, where N is the number of agents. (3) Experiment in four multi-agent environments shows that AME obtains significantly higher reward than baseline methods under both non-adaptive and adaptive attackers.
COMMUNICATIVE MUTI-AGENT REINFORCEMENT LEARNING (CMARL)
Dec-POMDP Model. We consider a Decentralised Partially Observable Markov Decision Process (Dec-POMIPH (Oliehoek 2012 Oliehoek & Amato 2015 Das et al. 2019) which is a multi-agent generalization of the single-an single-agent POMDP models. A Dec-POMDP can be modeled as a tuple (D, Ap, OD, O, R, 7, po). D = [1,..... .N ] is the set of N agents. & the underlying state space. Ap = X AieAA is the joint action space. OD XieDO; is the joint observation space, with O being the observation emission function. P S A1 .... ...A + ((S) is the state transition functior
AN + and po is the initial state distribution.
| R : S x A1 X AN
R is the shared reward function. is the shared discount factor,
Communication Policy & in Dec-POMDP. Due to the partial observability, communication among agents is crucial for them to obtain high rewards. Consider a shared message space M, where a message m E M can be a scalar policy of agent E D, denoted as E.. generates messages based on the agent's observation and interaction history. We use Mi- to denote the message sent from agent to agent / In practice, the communication policy can be hand-coded with domain knowledge, or learned with function approximators. Note that paper focuses on how to defend against adversarial perturbations of existing communication, and our defense is independent of the underlying communication policy &,-
vector, e.g., signal of GPS coordinates. The communication
Acting Policy æ with Communication. The goal of each agent E 'D is maximize the discounted cumulative reward م y-y((t) by learning an acting policy πं When there exists communication, the policy input contains both its own interaction history, denoted by т, E r, and the communication messages m;+ := {m j S J & i}. Similar to the communication policy &. we do not make any assumption on how the acting policy π is formulated, as our defense mechanism introduced later can be plugged into any policy learning procedure.
PROBLEM SETUP: COMMUNICATION ATTACKS IN CMARL
Communication attacks in MARL has recently attracted increasing attention (Blumenkamp & Prorok 2020: Tu et al. 2021 Xue et al. 2022) with different focuses, summarized in Section In this paper, we consider a practical and strong threat model where malicious attackers can arbitrarily perturb subset of communication messages during test time.
Formulation of Communication Attack: The Threat Model. During test time, agents execute well-trained policies T.. NN. As shown in Figure [b] the attacker may perturb communication messages to mislead a specific victim agent. Without loss of generality, suppose i E D is the victim agent. For notation simplicity, we assume agent receives messages from all other agents as is common in practice, resulting in N - communication messages in total. But our defense also works for partically-connectto to C' messages can be arbitrarily perturbed at every step, among all N messages. Here C' is reflection of the attacker's 's attacking power. The victim agent has no knowledge of which messages adversarial. This type of attack is related to lo perturbations to the input (Levine & Feizi 2020). as detailed in Appendix [
communication graphs. We consider the sparse attack setup w where up
We make the following mild assumption for the attacking power.
Assumption 3.1 (Attacking Power). An attacker can arbitrarily manipulate fewer than a half of the communication messages, i.e., C < N-1
2-
This is a realistic assumption, as it takes the attacker's 's resources to hack or control each communi- cation channel. It is less likely that an attacker can change the majority of communications among agents without being detected. Note that this is a very strong threat model as the C' attacked messages can be arbitrarily perturbed based on the attacker's attacking algorithm. Compared to the commonly used fp attacks, the above threat model can work for broader applications, such as adding a patch to an image, replacing a word in a sentence, and etc.
We do not make any assumption on what attack algorithm the attacker uses, i.c., how a message is perturbed. That is, we aim to achieve generic and provable robustness under a wide range of practical
(AY))) denotes the space of probahility distributions over space X.
3

---

Published as a conference paper at ICLR 2023
scenarios. In practice, we do not require the learner to know the exact C, and having upper bound of C' suffices to obtain the guarantees we introduce in the next section.
4 PROVABLY ROBUST DEFENSE FOR CMARL
In this section, we present our defense algorithm, Ablated Message Ensemble (AME), against test-time communication attacks in CMARL. We first introduce the algorithm design in Section 4.1 then present the theoretical analysis in Section 4.2
Section 4.3 discusses an extension of AME.
4.1 ABLATED MESSAGE ENSEMBLE (AMH)
Our goal is to learn and execute robust policy for any agent in the environment, that the agent can perform well in both non-adversarial environment and an adversarial environment. To ease the illustration, we focus robustifying arbitrary agent E D, and the same defense is applicable to all other agents. We omit the agent subscript and denote the agent's observation space, action space, and interaction history space O, .A, and r, respectively.
Let m E N- denote a set of N - 1 messages received by the agent. Then, we can build an ablated message subset of m with k randomly selected messages, as defined below.
Definition 4.1 (k-Ablation Message Sample (k-Sample)). For message set m E EM and any integer 1 1 k < N - 1. define a k-abllaionn message sample (or k-sample for short), [m]] E MM. as set k randomly sampled messages from Let H4 (m(m) be the collection of all unique k-samples of m, and thus (m)) IN
We propose Ablated Message Ensemble (AME), generic defense framework that can be fused with any policy learning algorithm. Motivated by the fact that the benign messages sent from other agents usually contain overlapping information of the environment that may suggest similar decisions, the main idea of AME is to make decisions based on the consensus of the benign messages. AME has two phases: the training phase where agents trained in clean environment, and testing/defending phase where communications may be perturbed.
Algorithm 1 Training Phase of AME
Training Phase with Message-Ablation Policy म (Algorithm(I) []. During training time, the agent learns message-ablation policy म T x R A which maps its own interaction history т and random k-sample [m] Uniform( (H4 (m)) an action, where Uniform H4 (m)) is the uniform distribution over all k-samples from the message set m it receives. Here kt is user-specified hyper- parameter selected to satisfy certain conditions, as discussed in Section 4.2 The training objective is to maximize the cumulative reward based on randomly sampled k- k-samples in non-at aevessaiial environment. Any policy optimization algorithm be used for training. Although by ablating subset of messages, the message-ablattin policy may compromise some natural reward (which is typical for robust training methods), it can sig- nificantly enhance the robustness of agents when attacks exist, with our design of test-time defense mechanism introduced below.
1: Input: ablation size k
2: Initialize मं for every agent i E [N].
3: repeat
4: for i to N do
5: Receive m og and update history т
6: Randomly sample A messages and
form k-sample [m.+ilk Take action a; + fT. mlk)
7:
Update policy n; 9: end for
10: until end of training
I1: Output: म., Vi E [N]
Algorithm 2 Defending Phase of AME
1: Input: ablation size k; trained message- ablation policy f. Vi E [N].
2: repeat
3: for i- to N do
Receive m Og and update history T; 5: Take āj <- ". m.-s) as in Def. 4.2
Defending Phase with icy से (Algorithm 2). Once we obtain reason-
Ensemble Pol-
end for
7: until end of test
able message-ablation policy ît, we can execute it with ablation and aggregation during test time to defend against adversarial communication. The main idea is to collect all possible k-samples from (m)) and select action voted by the majority of those k-samlles. Specifically, we construct message-ensemble policy स : x MMN1 - A that outputs action by aggregating the base actions produced by Ω on multiple k-samples (Line 5 in Algorithm 2). The construction of the cessagg-ensemble policy depends on whether the agent's action space A is discrete continuous, which is given below by Definition 4.2
4

---

Published as a conference paper at ICLR 2023
Definition 4.2 (Message-FF) MessaggeEEnemmble Policy). For message-ablaatin policy āt with observation history T and received message set m, define the mnesagge-nssmmle policy as
T(T, m) argmax >
(m))E [ [m]x) = =a],
if A is discrete, and (1)
Median (T, [m]x) [] E H4 (m));
if A is continuous.
Therefore, the message-ensemble policy मे takes the action suggested by the consensus of all samples (majority vote in a discrete action space, and coordinate- wise median for continuous action space). Different from model-ensemble methods (Kurutach et al. 2018 Harutyunyan et al. 2014) that learn multiple network models, network f. Therefore, the training process does not require extra computations. We will show the next section that, with some mild conditions, से under adversarial communications works similarly as the message-ablation policy स under all-benign communications.
the ensemble of messages, and only train single policy
4.2 ROBUSTNESS CERTIFICATES OF AME
In this section, theoretically analyze the robustness of AME. During test time, at any step, let be the interaction history, Meeignn be the unperturbed benign message set, and M&dv be the perturbed message set. Note that mbenign and madv both have N 1 messages while they differ by up to C messages. With the above notation, we define a set of actions rendered by purely benign k-samples in Definition 4.3 As the agent using well-trained message-ablation policy is likely to take these actions non-adversarial environment, they can be regarded as "good" actions to take.
Definition 4.3 (Benign Action Set Abenigu). For the execution of the message-ablation policy it at any step, define Abeniga C A as set of actions that î may select under benign k-samples.
Abenign == U "mhoniinl l Eu (mannggh) { [mbenig]*)]]
(3)
Our robustness certificates based the intuition that the consensus of ablated messages is henign, under the condition that a consensus exists among benign messages. Next, we present the action certificates and reward certificates for discrete and continuous actions, respectively.
4.2.1 ROBUSTNESS CERTIHCATES FOR DISCRETE ACTION SPACE
We first characterize the condition for the existence of consensus. Intuitively, the following condition ensures that the action resulted by majority vote stands for the consensus of benign messages.
Condition 4.4 (Dominating Benign Votes). Denote the highest number of votes among all actions given message set m Umax (m) = max.s. >/ [m] EH, (Ha(mm) [[, [m]&] a] satisfies
(N (N=11) 1 N
N
11-1- =:
Umax (m)
Uadvs
(4)
k
where Uady is the number of votes that adversarial messages may affect (the number of k-samples that contain at least one adversarial message).
Remarks. (1) This condition ensures the consensus has more votes than the votes that adversarial messages are involved in. Therefore, when से takes an action, there must exist some purely-benigi k-samples voting for this action. (2) This condition is easy to satisfy when C < N as (N-1) x
(N (N-1-C), 1111-9... (3) This condition can be casily checked during execution given an upper bound of C.
The following theorem suggests that under the above condition. the ensemble policy ग always takes benign actions suggested by benign message combinations, no matter whether attacks exist.
Theorem 4.5 (Action Certificate for Discrete Action Space). For perturbed message set madvs if Condition 4.4 holds, the ensemble policy ग in Equation (I) produces benign actions under Madv?
(Fr,)) Abenign.
Then, further derive reward certificate introduced below.
Reward Certificate for Discrete Action Space When Condition 4.4 holds, the message-ensemble policy ñ's action in every step falls into a benign action set, and thus its cumulative reward under adversarial communccatinns is also guaranteed to be no lower than the worst natural reward the base policy Ωt can get under random benign message subsets. Therefore, adversarial communication under Assumption 3.1 cannot drop the reward of any agent trained with AME. The formal reward certificate is shown in Corollary C.T in Appendix C.1
5

---

Published as a conference paper at ICLR 2023
4.2.2 ROBUSTNESS CERTIFICATES FOR CONTINUOUS ACTION SPACE
For continuous action space, the following condition is needed, which can always be satisfied by the proper selection of ablation size k. Condition 4.6 (Dominating Benign Samples). The ablation size k of AME satisfies
(-11->
N
1
(6)
k
k
Remarks. (1) For the message set adv that has up to C adversarial messages, this condition implies that among all k-samples from madv, there are more purely benign k-samples than k-samples that contain adversarial messages. (2) Under Assumption 3.1 this condition always has solutions for k.
(3) With an upper bound of C. one can choose k as the largest solution to Equation
(6
Theorem 4.7 (Action Certificate for Continuous Action Space). Under Condition 4.6 the action
a
Madv) generated by the ensemble policy т defined in Equation 2 satisfies
E Range(A) == {a v1 S 1 < L, -g, ā E Abenign s.r a <a
(7)
Theoretically, Range(AAeniga)) is a set of actions that are coordinate-wise bounded by base actions resulted from purely benign k-samples. In many practical problems, it is reasonable to assume that actions in Range(AAennggu) are relatively safe, especially when benign actions in Abenigu are concentrated. For instance, if benign message combinations have suggested driving at 40 mph or driving at 50 mph, then driving at 45 mph is also safe. More interpretations are in Appendix C.2 The above guarantee also leads bounded gap between natural reward and attacked reward.
Reward Certificate for Continuous Action Space. We can show that the difference between the cumulative reward of the message-ensemble policy ă under adversarial communications and the natural reward of स is no larger than 23+7VmaxcP. where Viax is the maximal value of the agent, and ÉR. Ep are constants measuring the smoothness of environment dynamics wrt Range(Abeniig)) formally defined in Appendix C.2 When the environment dynamics smooth (agents do not immediately fail due to a single mistake) and the benign messages achieve consensus (Range(Abenngg)) concentrated), then en and cp are small, and does not suffer from drastic reward drop.
I-?
4.2.3 INTERPRETATION OF CONDITIONS AND HYPERPARAMETER
How to Select Ablation Size k: Trade-off' between Performance and Robustness. The ablation size k is an important hyperparameter for the guarantees hold. In general, smaller & can tolerate a larger C, and smaller C' can be defended by a wider range of k. as theoretically analyzed in Appendix F However, smaller l: restricts the power of information sharing, as the message-ablation policy can access fewer messages in one step. Therefore, the value of k: is related to the intrinsic trade-off between robustness and natural performance (Tsipras et al. 2019 Zhang et al.) 2019), which suggests that secking high natural performance may hurt robustness, and achieving strong robustness may sacrifice some natural performance. In practice, one can also train several message-ablation ablation policies with different k's during training, and later adaptively select message-ablan abblatio policy to construct a message-end eensmblle policy during execution (decrease if higher robustness is needed).
Worst- Adversaries. Condition 4.4 and Condition 4.6 consider the worst-case scenario when the adversarial messages collaborate to dominate the consensus, which is intrinsically harsh for the victim - if the victim fails identify filter out the adversarial messages, its performance arbitrarily bad in the worst case. In contrast, although AME sacrifices some natural performance, its worst-case performance can be guaranteed. When these conditions do not hold, our algorithm can still achieve strong robustness under sub-optimal attacks, as verified in experiments.
be
Information Redundancy Leads to Higher Robustness. Intuitively, AME prefers benign messages to contain certain amount of redundant information (consensus), which is similar to multi-factor authentication in security-critical applications. This allows AME to tolerate arbitrary perturbations without assumptions such as a bounded -n-mo More importantly, AME provides way to establish and utilize such consensus, by explicitly setting and checking the required conditions.
4.3 SCALING UP: ENSEMBLE WITH PARTTAL SAMPLES
So far we have discussed the proposed AME defense and the constructed ensemble policy that aggregates all (N=)) number of k-samples out of N - messages. However, if N is large, sampling
all (N-1) combinations of message subsets could be expensive. In this case, smaller number of

---

Published as a conference paper at ICLR 2023
k-samples can be used. That is, given sample size 0 D S () randomly select D number of k-samples from Ha (m) (without replacement), and then we aggregate the message-ablation policy's 's decisions on selected k-samples. In this way, we define a partial-sample version of the ensemble policy, namely D D-ensemble policy 7D In this case, the robustness guarantee holds with high probability that increases as D gets larger. For example, in a continuous action space, we show that Equation holds with probability least
E (()())
PD
(8)
(
Formal definitions and full theoretical analysis of this partial-sample variant of AME are in Ap- pendix Our experiments show that AME works well with a relatively small D.
RELATED WORK
Certifiable Defenses. For more reliable application of deep learning. many approaches have been developed certify the performance of neural networks, including semidefinite programming- based
defenses (Raghunathan et al. 2018 b), convex relaxation of neural networks (Gowal et al. 2019
Zhang et al., 2018; Wong & Kolter 2018
Zhang et al., 2020a; Gowal et al., 2018), randomized
smoothing of a classifier (Cohen et al. 2019 Hayes 2020), etc. Most existing works focus on the lp
threat model where the perturbation is small in Ep norm, while we consider different and practical
threat model as discussed in Section 2
Adversarial Robustness of RL Agents. Appendix A introduces existing adversarial attacks on single-agent and multi-agent problems. To improve the robustness of agents, adversarial training (i.e., introducing adversarial agents to the system during training (Pinto et al. [017 Phan et al.
2021 Zhang et al., |021 [Sun et al. 2022)) and network regularization (Zhang et al. 2020b; Shen
et al. 2020 Oikarinen et al. 2021 are empirically shown to be effective under lp attacks, although such robustness is not theoretically guaranteed. In an effort to certify RL agents' robustness, some approaches (Lütjens et al.
2020 Zhang et al., 2020b] Oikarinen et al.)
2021 Fischer et al. 2019)
apply network certification tools to bound the Q networks. Kumar et al.
2021 and Wu et al.
2022
apply randomized smoothing (Cohen et al. 2019) to RL for provable robustness.
Adversarial Attacks and Defenses in CMARL. Appendix Ai literature of learning effective
communication among agents (Foerster et al.) 2016 Sukhbaatar et al.. 2016: Das et al.) 2019). Note that the focus of this paper is defending against adversarial perturbations on existing communications, which is orthogonal to the concrete communication strategy. Recently, the existence of adversarial communication in MARL has attracted increasing attention. [Blumenkamp & Prorok (2020) show that in a cooperative game, communication policies of some self-interest agents can hurt other agents' performance. To achieve robust communication, |Mtcchel al. (2020) adopt a Gaussian Process-based probabilistic model to compute the posterior probabilities that whether each partner is truthful. TTu et al.) (202T) investigate the vulnerability of multi-agent autonomous systems against lp communication attacks on vision tasks. Xue et al. (2022) propose to learn anomaly detector and a message reconstructor to recover the true messages, and train two populations of defenders and attackers to improve the generalizability of defense. But in our formulation, the attacker may arbitrarily replace the messages so that recovering the true message is infeasible.
To the best of our knowledge, our AME is the first certifiable defense in MARL against communication attacks. Moreover, we consider a strong threat model where up to half of the communication messages can be arbitrarily corrupted, capturing many realistic types of attacks.
6 EMPIRICAL STUDY
In this section, we verify the robustness of our AME in multiple different CMARL environments against various communication attack algorithms. Then, conduct hyperparameter tests for the ablation size and the sample size D (for the variant of AME introduced in Section 4.3)
Environments. To evaluate the effectiveness of AME, we consider the following four environments that cover various environment and communication settings.
FoodCollector (discrete/continuous action, pre-defined communication): N 9 agents with different colors search for foods with the same colors. Agents use their limited-range sensors to observe the surrounding objects, while communicating with each other share their recently observed
7

---

Published as a conference paper at ICLR 2023
food locations. The action space can be either discrete (9 moving directions and 1 no-move action), or continuous (2-dimensional vector denoting acceleration). Agents are penalized for having leftover foods at every step, they seek to find all foods as fast as possible.
InventoryManager (continuous action, pre-defined communication): N = 10 cooperative distributor agents carry inventory for 3 products. There are 300 buyers sharing underlying demand distribution. At every step, each buyer requests products from a randomly selected distributor. Then, each distributor agent observes random demand requests, takes restocking actions to adjust its own inventory, and communicates with others by sending its demand observations. Distributors are penalized for mismatches between their inventory and the demands.
MARL-MNIST (discrete action, learned communication (Mousavi et al. 2019): N = 9 agents aim to classify images in MNIST within a limited time horizon. At every step, each agent observes a patch of the image, and can take an action to move to an adjacent patch. Agents are allowed to
exchange information (encoded local beliefs) with other agents to update their own beliefs.
Traffic Junction (discrete action, learned communication) (Sukhbaatar et al. 2016); NN = 10 cars move along potentially intersecting routes on one or more road junctions. Each car has a limited visibility but is free communicate with all other cars. The goal is pass the road without collision.
The detailed description and policy implementation for each task are in Appendix E. and E.2
Based on the same policy learning paradigm for each environment, we compare AME with two defense baselines: (1) (Vanilla): vanilla training without defense, which learns a policy based on all benign messages. (2) (AT) adversarial training as in Zhang et al. (202I), which alternately trains an adaptive RL attacker and an agent. During training and defending, we set the ablation size AME as k
Baselines.
the largest solution to Equation 66) for C = 2. For AT, we train the agent against C' ==2 2 learned adversaries. More implementation details are provided in Appendix E.2
Evaluation Metries. To evaluate the effectiveness of our defense strategy, we test the performance of the trained policies under no attack and under various values of C' (for simplicity, we refer to C' as the number of adversaries). Different from previous work (Blumenkamp adversarial agent disrupts all the other agents, we consider the case where the attacker deliberately misleads a selected victim, which could evaluate the robustness of the victim under the harshest attacks. We report the victim's 's local reward under the following two types of attack methods:
Prorok| 2020) where the
(1) Heuristic attack that perturbs messages based on heuristics. In FoodCollector, MARL-MNIST and Traffic Junction, we consider randomly generated messages within the valid range of communication messages. Note that this is already a strong attack since a random message could be arbitrarily far from the original message. For InventoryManager where messages have clear physical meanings (demand of buyers), we consider 3 realistic attacks: Perm-Attack, Swap-Atrack, Flip-Attack, which permute, swap or flip the demand observations. respectively, as detailed in Appendix [E..2]]
(2) Learned adaptive attack that learns the strongest/wors adversarial communication with an RL algorithm to minimize the victim's reward (a white-box box attacker which knows the victim's reward). The learned attack can strategically mislead the victim. As shown in prior works (Zhang et al. 2020b
FoodCollector
Inventory Manager
MARL-MNIST
TrafficJJunctin
Heuristic Atfack
No
Cil
Oil
Aaaee C=
C Ow
Learned Aduplive Attack
FoodCollector
InventoryManager
MARL-MNIST
TrafticJunction
Vontss n Own
-o Vendaa Yoalls
Breee
Phokkn
Figure 2: Rewards of our AME and baselines in all environments, under no attacker and varying numbers of adversaries for adaptive and various non-adaptive attacks. The dashed red lines stand for the average performance of nom-communecative agent. Results averaged over 5 random seeds. Our AME outperforms all bascline methods in all tasks, and stays robust for varying number of adversaries (denoted by C).
8

---

Published as a conference paper at ICLR 2023
2021 Sun et al. 2022). the theoretically optimal attack (which minimizes the victim's 's reward) can be formed as an RL problem and learned by RL algorithms. Therefore, we can regard this attack as a worst-case attack for the victim agents. More details are in Appendix
Experiment Results. The major results are shown in Figure 2 where we present the discrete-action FoodCollector, and use Swap-Attack the heuristic attack for InventoryManager More results including continuous-action FoodCollector and other heuristic attacks for InventoryManager are put in Appendix E.3 We can see that the rewards of Vanilla and AT drastically drop under attacks. Under strong adaptive attackers, Vanilla and AT sometimes perform worse than a non-communicativ agent shown by dashed red lines, which suggests that communication can be double-edged sword. Although AT is usually effective for Ep attacks (Zhang et al. 202I), we find that AT does not achieve better robustness than Vanilla, since it can not adapt to arbitrary perturbations to several messages. (More analysis of AT is in Appendix (E.3.5) In contrast, AME can utilize benign communication well while being robust to adversarial communication.
We use k = 2 for our AME, which in theory provides performance guarantees against up to C' = 2 adversaries for N = 9 and N = 10. We can see that the reward of AME under C = 1 or C = is similar to its reward under attack, matching our theoretical analysis. Even under 3 adversaries where the theoretical guarantees no longer hold, AME still obtains superior performance compared to Vanilla and AT. Therefore, AME makes agents robust under varying numbers of adversaries.
Discussion on Allation Size k We demon- strate AME's natural reward and attacked reward in discrete-action FoodCollector under C' = 2 adversaries with all possible values of k ranging from to N - 1 in Figure (left). Results in other environments are similar and are put in Appendix E.3.4] The green curve shows that the natural performance of AME. increases as gets larger, where & 1 is the most conservative version of AME, and & = N - degenerates to the vanilla policy without message ablation. It is intuitive because a larger it allows the agent to gather more information from others. Although larger k is beneficial in clean environment, gathering information without defense makes the agent more vulnerable to communication attacks. The red and blue curves show that the reward of agents decreases under attacks when l gets larger, especially when attacks are adaptive. Therefore, increasing ablation size trades off robustness for natural performance, matching the analysis in Section 4.2.3] As the largest solution to Equation (6) in Condition (.6, ablation size k 2 achieves good balance between performance and robustness. Even when k >> 2 which breaks Condition 4.6 AME is still more robust than baselines, showing the flexibility of AME.
Hos
Amick
Figure 3: Natural and rohust performance AME with various values of (left) ablation size k and (right) sample size D, in discrete-actios FoodCollector under C' = 2.
Discussion on for Sample Size D We evaluate the partial-sample variant of AME introduced in Section 4.3 with D varying from (N-)) (ensemble of all message combinations) to I (randomly take one k-sample), under k = 2 and C 2. Figure Bright) demonstrates the performance of different D's in discrete-action FoodCollector and Appendix F.3 shows results in other environments. As D goes down, AME obtains lower reward under attackers, but it is still significantly more robust than baseline methods. Note that D = is equivalent to executing the message-ablation policy without ensemble, which robust to heuristic attacks but less robust to adaptive attacks than the original AME, verifying the effectiveness of message ensemble.
7 CONCLUSION AND DISCUSSION
This paper proposes a defense framework AME, which is certifiably robust against multiple arbitrarily perturbed adversarial communication messages, for any existing communication protocol. Our pro- posed ablation and ensemble method can be extended to robustify other decision makers which takes in multiple
information sources. The limitation of AME is the requirement of several conditions. Although these conditions can be quantified and checked in practice, our future work aims to relax these conditions, or to learn a communication policy satisfying these conditions. AME utilizes the information redundancy of communication, which can be achieved by the learning of a communication policy in many tasks, as an extension of the current method.

---

Published as a conference paper at ICLR 2023
8 REPRODUCIBILITY STATEMENT
Our implementation of the AME algorithm and the FoodCollector environment are available at http://hhhbbboooo/uuummuuuauange amme.iit
ACKNOWLEDGEMENTS
This work is supported by JPMorgan Chase & Co., National Science Foundation NSF-IIS-FAI Award 2147276, Office Naval Research, Defense Advanced Research Projects Agency Guaranteeing AI Robustness against Deception (GARD), and Adobe, Capital One and JP Morgan faculty fellowships.
Disclaimer This paper was prepared for informational purposes in part by the Artificial Intelligence Research group of JPMorgan Chase & Coand its affiliates ("JP Morgan"), and is not a product of the Research Department JP Morgan. JP Morgan makes no representation and warranty whatsoever and disclaims all liability, for the completeness, accuracy or reliability of the information contained herein. This document is not intended as investment research or investment advice, or recommendation, offer or solicitation for the purchase or sale of any security, financial instrument, financial product or service, or to be used any way for evaluating the merits of participating in any transaction, and shall not constitute solicitation under any jurisdiction or to any person, if such solicitation under such jurisdiction or to such person would be unlawful.
REFERENCES
Joshua Achiam. Spinning Up in Deep Reinforcement Learning. 2018.
Vahid Behzadan and Arslan Munir. Vulnerability of deep reinforcement learning policy induction attacks. In International Conference on Machine Learning and Data Mining in Pattern Recognition, pp. 262-275. Springer, 2017.
Samuel Berrien. MARLClassification 2019.
Marl classification.
https://gtthbb.com Ipsseoo
Jan Blumenkamp and Amanda Prorok. The emergence of adversarial communication in multi-agent reinforcement learning, 2020.
Anirban Chakraborty, Manaar Alam, Vishal Dey, Anupam Chattopadhyay, and Debdeep Mukhopad- hyay. Adversarial attacks and defences: A survey, arXiv preprint arXiv: 2018.
Po-Wei Chou, Daniel Maturana, and Sebastian Scherer. Improving stochastic policy gradients in continuous control with deep reinforcement learning using the beta distribution. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 834-843 843. PMLR, 06-11 Aug 2017. hammmll
URL httetps://prrcceeiinge
m www..prsssvvvv
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference Machine Learning, pp. 1310-1320. PMLR, 2019.
Abhishek Das, Théophile Gervet, Joshua Romoff, Dhruv Batra, Devi Parikh, Mike Rabbat, and Joelle Pineau. Tarmac: Targeted multi-agent communication. In International Conference Machine Learning, pp. 1538-1546. PMLR, 2019.
Mare Fischer, Matthew Mirman, Steven Stalder, and Martin Vechev, Online robustness training for 2019.
deep reinforcement learning, arXiv preprint
Jakob Foerster, Ioannis Alexandros Assacl, Nando De Freitas. and Shimon Whiteson. Learning to communicate with deep multi-agent reinforcement learning. Advances neural information processing systems, 29, 2016.
Adam Gleave, Michael Dennis, Cody Wild, Neel Kant, Sergey Levine, and Stuart Russell. Adversarial policies: Attacking deep reinforcement learning. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa. Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL
net. htt.://neee/eooooomooooooooo////
10

---

Published as a conference paper at ICLR 2023
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. On the effectivenesss interval bound propagation for training verifiably robust models. arXiv preprint arXiv: 18X.:1110011271: 2018.
Sven Gowal, Krishnamurthy Dj Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovie, Timothy Mann, and Pushmeet Kohli. Scalable verified training for provably robust image classification. In Proceedings of the IEEE/CVF International Conference Computer Vision, pp. 4842 4851, 2019.
Anna Harutyunyan, Tim Brys, Peter Vrancx, and Ann Nowé. Off-policy shaping ensembles in reinforcement learning. CoRR, abs/1405.5335 2014. http: http::::taxx....r//////oo/
5358
Matthew John Hausknecht. Cooperation and communication in multiagent deep reinforcement learning. PhD thesis, 2016.
Jamie Hayes. Extensions and limitations of randomized smoothing for robustness guarantees. In Proceedings of the IEFE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pp. 786-787, 2020.
Sandy Huang, Nicolas Papernot, Ian Goodfellow, Yan Duan, and Picter Abbeel. Adversarial attacks neural network policies. arXiv preprint arXiv: 02284, 2017.
Yunhan Huang and Quanyan Zhu, Deceptive reinforcement learning under adversarial manipulations cost signals. In International Conference Decision and Game Theory for Security, pp. 217-237. Springer, 2019.
Jiechuan Jiang and Zongging Lu. Learning attentional communication for multi-agent cooperation. Advances in neural information processing systems, 31, 2018.
Woojun Kim, Jongeui Park, and Youngchul Sung. Communication in multi-agent reinforcement learning: Intention sharing. In International Conference on Learning Representations, 2021. URL
https: /ettps://epenreeee
net www.rooruuuuureee 2dR9twy
Ezgi Korkmaz. Investigating vulnerabilities of deep neural policies. In Cassio de Campos and Marloes H. Maathuis (eds.), Proceedings of the Seieeth-eeenth Conference Uncer- tainty in Artificial Intelligence, volume 161 of Proceedings of Machine Learning Research, pp. 1661-1670 PMLR, 27-30 Jul 2021. URL htttps://prceeedinnngg mll. wttpp//gw..........eeeeee..e wwwps/vvsll..
korkmaz21a wtt.mmaazlaahha.... html
Ezgi Korkmaz. Deep reinforcement learning policies learn shared adversarial features across mdps. Proceedings of the AAAI Conference on Artificial Intelligence, 36(7):7229 7238, Jun. 2022. doi: 10. 1609/aaai. v36i7. 20684. URL https::/ojs. wttp:///...........././/./.ee.e. wwcpieexxpppppaaaee
http:///wwweepppp////aarrre Tamp/AAAT/asaa
view view/20684 20644
Ezgi Korkmaz. Adversarial robust deep reinforcement learning requires redefining robustness.
Proceedings of the AAAI Conference on Artificial Intelligence, 2023.
Aounon Kumar, Alexander Levine, and Soheil Feizi. Policy smoothing for provably robust reinforce- ment learning. arXiv preprint arXiv:2 1420, 2021.
Thanard Kurutach, Ignasi Clavera, Yan Duan, Aviv Tamar, and Pieter Abbeel. Model-ensemble trust-region policy optimization. In International Conference on Learning Representations, 2018. URL http:httss///openeee
net./ femee/ffrrntt id= nbwRZ)
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- based learning applied to document recognition. Proceedings of the IEEE, (6)12)2227 22224, 1998.
Alexander Levine and Soheil Feizi. Robustness certificates for sparse adversarial attacks by random- ized ablation. Proceedings the AAAI Conference Artificial Intelligence, 34(04))4585-455 4593, Apr. 2020. doi: 10. 10.6609aaaii 13.160%/aaii.344444.... v34044.588. URL httpt:::/ //op:::///s...///////////sssssss aaai.
php/
AAAT CAAT/article/v/e 5888

---

Published as a conference paper at ICLR 2023
Yongyuan Liang. Yanchao Sun, Ruijie Zheng, and Furong Huang. Efficient adversarial training without attackingg corst-case-aware robust reinforcement learning. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL httptttt////peeeeeeteee
www.:neetfoormee forum? d=y-Elhto@l-----
net/
Xiangyu Liu, Souradip Chakraborty, and Furong Huang. Controllable attack and improved adver- sarial training in multi-agent reinforcement learning. In Workshop on Trustworthy and Socially Responsible Machine Learning, NeurIPS 2022, 2022. URL http:::s//ppeeeeeeee.r.o
Eorum?id=25Fc- EEUSE
Yen-Cheng Liu, Junjiao Tian, Cai Ma, Nathan Glaser, Chia-Was Wen Kuo, and Zsolt Kira. Who2com: Collaborative perception via learnable handshake communication. In 2020 IEEE International Conference on Robotics and Automation (ICRA), pp. 6876-6883. IEEE, 2020.
Bjöm Lütjens, Michael Everett, and Jonathan How. Certified adversarial robustness for deep reinforcement learning. In Conference Robot Learning, pp. 1328-1337. PMLR, 2020.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. To- wards deep learning models resistant adversarial attacks. In International Conference on Learn- ing Representations, 2018.
net forum 21
Rupert Mitchell, Jan Blumenkamp, and Amanda Prorok. Gaussian process based message filtering for robust multi-agent cooperation in the presence of adversarial communication, 2020.
Hossein K Mousavi, Mohammadreza Nazari, Martin Takáč, and Nader Motee. Multi-agent image classification via reinforcement learning. In 2019 JEEE/RS/ International Conference on Intelligent Robots and Systems (IROS), pp. 5020-5027. IEEF, 2019.
Swapnil Naik and Vikas Maral. Cyber security - iot. In 2017 2nd IEEE International Conference on Recent Trends in Electronics. Information Communication Technology (RTEICT), pp. 764-767, 2017. doi: 10. 1109//TTETTT21177855511117
Tuomas Oikarinen, Wang Zhang, Alexandre Megretski, Luca Daniel, and Tsui-Wei Weng. Robust deep reinforcement learning through adversarial loss. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL
https://openrevz net coorum?id=eaA
Frans Olichock. Decentralized pomdps. In Reinforcement Learning, pp. 471-503. Springer, 2012.
Frans Olichock and Christopher Amato. concise introduction to decentralized pomdps, 2015.
Thomy Phan, Lenz Belzner, Thomas Gabor, Andreas Sedlmeier, Fabian Ritz, and Claudia Linnhoff- Popien. Resilient multi-agent reinforcement learning with adversarial value decomposition. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 1 11308-11316, 2021.
Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial rein- forcement learning. In International Conference on Machine Learning, pp. 2817-2826. PMLR, 2017.
Antonin Raffin, Ashley Hill, Adam Gleave, Anssi Kanervisto, Maximilian Ernestus, and Noah Dormann. Stable-basllines: Reliable reinforcement learning implementations. Journal of Machine Learning Research, 22(268):1-8, 2021. URL ///p//////lll.ooor//ppsrs//////
20-1364: html
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial examples. arXiv preprint arXiv:1801.09344 2018a.
Aditi Raghunathan, Jacob Steinhardt, and Percy S Liang. Semidefinite relaxations for certifying robustness to adversarial examples. Advances in Neural Information Processing Systems, 31, 2018b.
Amin Rakhsha, Goran Radanovic, Rati Devidze, Xiaojin Zhu, and Adish Singla. Policy teaching via environment poisoning: Training-time time adversarial attacks against reinforcement learning. In International Conference Machine Learning, pp. 7974-7984, 2020.
12

---

Published as a conference paper at ICLR 2023
Murtaza Rangwala and Ryan Williams. Learning multi-agent communication through structured attentive reasoning. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. sociates, Inc., 2020. URL Faa6449998c111755332288888888888
Curran As- neuri ps. cc wctpppppr///2//1111.11
Tabish Rashid, Mikayel Samvelyan, Christian Schröder de Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. QMIX: monotonic value function factorisation for deep multi-agent reinforcement learning. In International Conference on Machine Learning.. 2018.
Ahmad EL Sallab, Mohammed Abdou, Etienne Perot, and Senthil Yogamani. Deep reinforcement learning framework for autonomous driving. Electronic Imaging, 2017(19) 2017.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 1771v:1707.06347, 2017.
Shai Shalev-Shward Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv:1610.03295, 2016
Qianli Shen, Yan Li, Haoming Jiang, Zhaoran Wang, and Tuo Zhao. Deep reinforcement learning with robust and smooth policy. In International Conference on Machine Learning, pp. 8707-8718. PMLR, 2020.
Amanpreet Singh, Tushar Jain, and Sainbayar Sukhbaatar. Individualized controlled continuous communication model for multiagent cooperative and competitive tasks. In International Confer- ence on Learning Representations, 2019. URL httpt::/ htttps::/openreview. net forum?ide kye7kkCgK7
Sainbayar Sukhbaatar, Rob Fergus, et al. Learning multiagent communication with backpropagation. Advances in neural information processing systems, 29:2244-2252, 2016.
Yanchao Sun, Da Huo, and Furong Huang. Vulnerability- poisoning mechanism for online rl with unknown dynamics. In International Conference Learning Representations, 2021.
Yanchao Sun, Ruijie Zheng, Yongyuan Liang, and Furong Huang. Who the strongest enemy? towards optimal and efficient evasion attacks in deep RI. In International Conference Learning Representations, 2022. /ttthhttss//oppeeeeeee
net. wott://oorrmmmdddM22e.......
J. K Terry, Benjamin Black, Nathaniel Grammel, Mario Jayakumar, Ananth Hari, Ryan Sulivan, Luis Santos, Rodrigo Perez, Caroline Horsch, Clemens Dieffendahl, Niall L Williams, Yashas Lokesh, Ryan Sullivan, and Praveen Ravi. Pettingzoo: Gym for multi-agent reinforcement learning. arXiv preprint arXiv:2009.144 14471, 2020.
Chen Tessler, Yonathan Efroni, and Shie Mannor. Action robust reinforcement learning and applica- tions in continuous control. In International Conference on Machine Learning, pp.
PMLR, 2019.
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Tumner, and Aleksander Madry. Ro- bustness may be odds with accuracy. In International Conference on Learning Representations, 2019. URL https: /ttp///wwwwwweneeeeeeee www.ee//ooommmmmmmm htt.ee/eooorrraa-aSyaaa3aa-----
James Tu, Tsunhsuan Wang. Jingkang Wang, Sivabalan Manivasagam, Mengye Ren, and Raquel Urtasun. Adversarial attacks on multi-agent communication. Proceedings of the IEEE/CVF International Conference Computer Vision (ICCV), pp. 7768-7777, October 2021.
Wenxiao Wang, Alexander Levine, and Soheil Feizi. Lethal dose conjecture on data poisoning. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https:t/////m http://pppppeeee.eee/ee/ www.enee//eeeeeee forum?
i id=PYnSpt.3 jAz
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pp. 2286-5295.. PMLR, 2018.
13

---

Published as a conference paper at ICLR 2023
Fan Wu, Linyi Li, Zijian Huang, Yevgeniy Vorobeychik, Ding Zhao, and Bo Li. Crop: Certifying bust policies for reinforcement learning through functional smoothing. International Conference Learning Representations, 2022.
Wanqi Xue, Wei Qiu, Bo An, Zinovi Rabinovich, Svetlana Obraztsova, and Chai Kiat Yeo. Mis-spoke or mis-lead: Achieving robustness in multi-agent communicative reinforcement learning. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS '22 pp. 1418-1426, Richland. SC, 2022. International Foundation for Autonomous Agents and Multiagent Systems. ISBN 9781450392136,
Lei Yuan, Jianhao Wang, Fuxiang Zhang, Chenghe Wang. ZongZhang Zhang, Yang Yu, and Chongjie Zhang. Multi-agent incentive communication via decentralized teammate modeling. Proceedings of the AAAI Conference on Artificial Intelligence, 36(9):9466 9474, Jun. 2022. doi: 10.1609/ aaai 1369..2117.. /Rthtttss://os.
21179
Hongyang Zhang. Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. International Conference on Machine Learning, pp. 7472-7482. PMLR, 2019.
Huan Zhang, Tsui-Wei Weng, Pin-Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. In Proceedings of the 32nd International Conference Neural Information Processing Systems, NIPS' 18, pp. 4944-4953 Red Hook, NY, USA, 2018. Curran Associates Inc.
Huan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li, Duane Boning, and Cho-Jui Hsich. Towards stable and efficient training of verifiably robust neural networks. In International Conference on Learning Representations, 2020a. URL /tttpss:/
het//forun.1dd-Ssuk.LMMMM
Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Mingyan Liu, Duane Boning, and Cho-Jui Hsieh. Robust deep reinforcement learning against adversarial perturbations on state observations. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 21024-21033 Curran Associates, Inc., 2020b.
Huan Zhang, Hongge Chen, Duane Boning, and Cho-Jui Hsieh. Robust reinforcement learning on state observations with learned optimal adversary. In International Conference on Learning Representations, 2021.
14

---

Published as a conference paper at ICLR 2023
Appendix: Certifiably Robust Policy Learning against Adversarial Multi-Agent Communication
A ADDITIONAL RELATED WORK
Communication in MARL Communication is crucial in solving collaborative MARL problems. There are many existing studies learning communication protocols across multiple agents. Foerster al. 2016) are the first to learn differentiable communication protocols that end-to-end trainable across agents. Another work by SSkkhbaaatar et al. (2016) proposes an efficient centralized learning algorithm which learns a large feed-forward neural network to map inputs of all agents to their actions. Attention mechanisms are also proven to be effective in learning communication (Jiang & Lu 2018 Rangwala & Williams 2020). Some recent works (Yuan et al., 2022, Kim et al. 2021) propose new communication schemes that models other agents' actions or intentions. It is also important to communicate selectively, since some communication may be less informative unnecessarily expensive. To tackle this challenge, Das al. (2019) propose attention mechanism for agents to adaptively select which other agents to send messages to. [Liu et al.) (2020) introduce handshaking procedure so that the agents communicate only when needed. This paper proposes a certifiably robust algorithm against perturbations on communications, which orthogonal to the concrete communication strategy. Our AME can be combined with the above communication MARL methods to improve their robustness.
coimmuattion-nvvarinn
Other Attacks in RL and MARL Adversarial attacks and defenses in RL systems have recently attracted more and more attention, and are considered in many different scenarios. The majority of related work on adversarial RL focuses on directly attacking a victim by perturbing its observa-
tions (Huang et al.) 2017; Oikarinen et al.) 2021 /Zhang et al. 2020b Sun et al. 2002: Korkmaz
2021 2022 2023; Liang et 2022 or actions (Tessler et al. 2019 Pinto et al. 2017). However, an attacker may not have direct access to the specific victim's observation
action. In this case,
indirect attacks via other agents can be an alternative. Gleave et al. (2020); Liu et al. (2022) propose to attack the victim by changing the other agent's actions. Therefore, even if the victim agent has well-protected sensors, the attacker can still influence it by manipulating other under-protected agents. But the intermediary agent whose actions altered will obtain sub-optimal reward, which makes the attack noticeable and less stealthy. In contrast, we consider the scenario where an attacker alters the communication messages sent from some other agents the victim without changing the behaviors of these agents. In this case, it is relatively hard for the victim to identify the attacks.
Training time attacks, or poisoning (Behzadan & Munir 2017 Huang & Zhu| 2019 Rakhsha et al., 2020; (Sun et al. (222)) propose to manipulate the training data such that the agent learns bad or target policy, different from evasion attacks that deprave a well-trained policy. Investigation on how training- wraning-time communication perturbations influence the learned policies would be an interesting future direction.
B ALGORITHM PSEUDOCODE
Algorithm and Algorithm demonstrate the procedures of AME in training and defending phases, respectively.
C ADDITIONAL THEORETICAL DEFINITIONS AND ANALYSIS
Relation between Communication Attack and to Observation Attack The communication threat model described in Section is analogous constrained to attack policy inputs. When agent é is attacked, the input space of its acting policy म; is X, := T, x MM-1, Therefore, when C. communication messages corrupted, the original input 2; gets perturbed to ž, Let d be the dimension of communication message, then x; and ã; differ by up to dC' dimensions, which is similar an lo attack constrained in certain dimensions.
15

---

Published as a conference paper at ICLR 2023
Algorithm 3 Training Phase of AME
1: Input: ablation size &
2: Initialize for every agent E [N].
3: repeat
4: for to . do
5: Receive a list of messages m. get local observation and update interaction history T. Cnuform(HH((mm--)
6: Randomly sample [m-+
7: Take action based on and the k-sample [m:-i]k> i.e. # (m:+
8: Update the replay buffer and policy R,
9: end for
10: until end of training
11: Output: message-ablation policy #; Vi [N]
Algorithm 4 Defending Phase of AME
1: Input: ablation size k; trained message-ablation policy #., Vi E [NV]
2: repeat
3: io .N do
4: Receive a list of messages m.-i with most C' malicious messages, get local observation
Og and update interaction history T
5: Take 0; f- 7,(r,, m..,), where n. is the message-ensemble policy defined with क by
Equation [ for discrete A,, and Equation (2) for continuous Ad
6: end for
7: until end of test
C.I ADDITIONAL ANALYSIS OF AME IN DISCRETE ACTION SPACE
Reward Certificate Theorem 4.5 justifies that under sufficient majority votes, the message- ensemble policy मे ignores the malicious messages in madv and executes a benign action that benign message combinations, identified. It is important to note that, when the message-ensemble policy ग selects an action a, there must exist least one purely benign k-sample that let the message-ablation policy â produce Therefore, as long as स can obtain high reward with randomly selected benign k-samples, ß can also obtain high reward with ablated adversarial communication due its design.
is suggested by
when the malicious messages are not
Specifically, we consider a specific agent with message-ablation policy á and message-ensemble policy मे (suppose other agents are executing fixed policies). Let .M N-1
M be an attack algorithm that perturbs at most C messages in message set. Let Ç ~ Z(P. f) be trajectory of policy a under no attack, i.e., Ç (o m (0) (0)), ,(()) (!), (!) a (0)) (O)..... (Recall that message-ablation policy क takes in random size-k subset of (t) and outputs action a!).) When there exists attack with v, let &u ((P, म; v) be a trajectory of policy under communication attacks, i.e., G, (o zmm (m), (0) (()) (1), v(m())) (0)) ,,(O), ...).. For any trajectory Ç, let r(C) be the discounted cumulative reward of this trajectory.
With the above notations, we propose the following reward certificate.
Corollary C.1 (Reward Certificate for Discrete Action Space). When Condition 4 holds at every step of execution, the cumulative reward of ensemble policy f defined in Equation 1 under adversarial communication is lower than the lowest cumulative reward that the ablation policy î can obtain with randomly selected k-samples under no attacks, i.e.
min (u~Z(PP
r(Sx) 2 min r((),
(9)
{~2(PP
for any attacker satisfying Assumption 3.1 (C N-1).
16

---

Published as a conference paper at ICLR 2023
Remarks. (1) The certificate holds for any attack algorithm with C' < 2 (2) The message- ablation policy क has extra randomness from the sampling of k-samples. That is, at every step, म takes uniformly randomly selected k-sample from Hy (m). Therefore, the min in the RHS considers the worst-case message sampling in the clean environment without attacks. Since गे always takes actions selected by some purely-benign message combinations, the trajectory generated by मे can also be produced by the message-ablation policy. (3) Note that the RHS (ming-Z((P.t r(()) can be approximately estimated by executing म during training time, so that the test-time performance of is guaranteed to be no lower than this value, even if there are up to C' corrupted messages at every step.
Appendix
D provides detailed proofs for the above theoretical results.
C.2 ADDITIONAL ANALYSIS OF AME IN CONTINUOUS ACTION SPACE
Note that Theorem 4.7 certifies that the selected action is in a set of actions that are close to benign actions ) ) but does not make any assumption this set. Next we interpret this result in details.
How to Understand Range(AAbenign) coordinate-wisg bounded by base actions resulted from purely benign k-samples. In many practical problems, it is reasonable to assume that actions in Range(Abeeiig are relatively safe, especially when benign actions in Abenign are concentrated. The following examples illustrate some scenarios where actions in Range(Abenign)) are relatively good.
Theoretically,
) is a set of actions that are
1. If the action denotes the price a seller sells its product in a market, and the communication messages are the transaction signals in an information pool, then (ange(A) is a price range that is determined based on purely benign messages. Therefore, the seller will set a reasonable price without being influenced by malicious message.
2. If the action denotes the driving speed, and benign message combinations have suggested driving at 40 mph or driving 50 mph, then driving at 45 mph is also safe.
3. If the action is a vector denoting movements of all joints of robot (as in many MuJoCo tasks), and two slightly different joint movements are suggested by two benign message combinations, then an action that does not exceed the range of the two benign movements at every joint is likely to be safe as well.
The above examples show by intuition why the message-ensemble policy can be regarded relatively robust policy. However, in extreme cases where there exists "caveat" in Range(Abeeiggu) taking an action in this set may also be unsafe. To quantify the influence of Range(Aneniggh on the long-term reward, we next analyze the cumulative reward of the message-ensemble policy in the continuous-action case.
How Does Range(Abenign) Lead to A Reward Certificate? Different from the discrete-action case, the message-ensemble policy स in continuous action space may take actions not in Abenign such that it generates trajectories not seen by the message-ablation policy â. However, since the action of से is guaranteed to stay in Range(Abeniggu) we can bound the difference between the value of गे and the value of नt, and how large the different is depends on some properties of (abie(Ab
Concretely, Let R and P be the reward function and transition probability function of the current agent when the other agents execute fixed policies. So R(s, a) is the immediate reward of taking action a at state s, and P(s') ss, a) is the probability of transitioning to state s' from by taking action (Note that is the underlying state which may not be observed by the agent.)
Definition C.2 (Dynamics Discrepancy of ft). A message-ablation policy ā called CR.Cp- cricp-ddsere if ER Ep are the smallest values such that for any E S and the corresponding benign action set Abeniga we have Van, 02 E Range( )
RR(s 01) R(s, S cn.
(10)
/ 1(5))), P(s'|s, S Cpp
(11)
17

---

Published as a conference paper at ICLR 2023
Remarks. (1) Equation [11
is equivalent to that the total variance distance between P(-]s, a1) and P(-|s, d2) is less than or equal to Ep/2. /2. (2) For any environment with bounded reward, eg and ep always exist.
C.2 characterizes how different the local dynamics actions in Range(Abenitn are, over all possible states. If Range(Abeniga) is small and the environment is relatively smooth, then taking different actions within this range will not result in very different future rewards. The theorem below shows a reward certificate for the message-ensemble policy w.
Definition
Theorem C.3 (Reward Certificate for Continuous Action Space). Let (*)s) be the clean value (discounted cumulative reward) of it starting from state s under attack; let V (s) be the value of गt starting from state s under attack algorithm v, where v satisfies Assumption 3.1 let k be an ablation size satisfying Condition 4.6 If is ER. ER.Ep-discrepan,, then for any state S, we have
CR ++77VVmae VV
min V (s) 2 ($)
(12)
1-9
where Viaxx == sup,, [s)
Remarks. (1) The certificate holds for any attack algorithm v with C < N (2) E and ep are small, then the performance of message-nnsmbble policy मे under attacks is similar to the performance of the message-ablation policy स under no attack.
It is important to note that ER and ep intrinsic properties of ft, independent of the attacker. Therefore, one can approximately measure ER and Ep during training. Similar to Condition [4.4 required for discrete action space, the gap between the attacked reward of т and the natural reward of á depends on how well the benign messages are reaching a consensus. (Smaller сд and cp imply that the actions in Abenign relatively concentrated and the environment dynamics relatively smooth.)
Moreover, can optimize स during training such that en and 6 small possible, to further improve the robustness guarantee of न.. This can be a future extension of this work.
Technical proofs of all theoretical results can be found in Appendix D
C.3 EXTENSION OF AME WITH PARTIAL SAMPLES
AME can be extended to partial-sample version, where the ensemble policy is constructed by D instead of (N-1) samples. Let (m, be subset of H4 (m) that contains D random k-samples from He Hm))). Then the D-ensemble policy up is defined as
As motivated in Section 4.3
#D m) argmax
Σ
1|f(o, [m]a] a).
(13)
for a discrete action space, and D m) Median (f,, [m]s))(m] (
(14)
for a continuous action space.
In the partial-sample version of AME, we can still provide high-probability robustness guarantees.
For notation simplicity, let m1 = NN-
n2 = ("- C- Define the majority vote as
Umax (m) max aEA
Σ [m]
1 [(( [m]x) a).
(15)
The following theorem shows general guarantee for D-ensemble policy in discrete action space.
Theorem C.4 (General Action Guarantee for Discrete Action Space). Given arbitrary sample size 0 < D (N (N-1), for the D-ensemble policy Ho defined in Equation (13). Equation (5) holds
deterministically if the majority vote Vmnax (Madv) ) > Th 112. Otherwise it holds with probubility at least
Manax (mady) --1 mm) mm--2)) (m²)
PD
(16)
713
Note that Theorem 4.5 is a special case of Theorem C.4 since it assumes Umax (madv) > nı 712-
Theorem C.5 below further shows the theoretical result for continuous action space.
18

---

Published as a conference paper at ICLR 2023
Theorem C.5 (General Action Guarantee for Continuous Action Space). Given arbitrary sample
size 0 < D (N for the Deensemble policy RD defined in Equation 14 with ablation size
satisfying Condition 4.6 Equation 7 holds with probability at least
pn Σド= (2)) DD3) =1))
(17)
where D = L1 +.
The larger D is, the higher the probability po is, the more likely that the message-ensemble policy
selects action in Bange(Abennin ). In Theorem C.5 when D (M=²). the probability pD is 1 and
the result matches Theorem 4.7
Technical proofs of all theoretical results can be found in Appendix D
D TECHNICAL PROOFS
For the simplicity of the proof, we make the following definition.
Definition D.1. (Purely Benign k-sample and contaminated k-sample) A k-sample [m]; E HA (m) is purely benign if every message [m] k comes from a benign agent and is unperturbed. k-sample [m]a E H4 (m) is contaminated if there exists some message in [m]j that is perturbed.
t be the total number of k-samples from a message Note that the total number of purely benign k-samples is n2 (N-C-1). and the
For notation simplicity, let n1 =
total number of contaminated k-samples is nı 122 = NN 11-1) (N-C-1).
D.1 PROOFS IN DISCRETE ACTION SPACE
Action Certificates We first prove the action certificates in the discrete action. For notation simplicity, slightly abuse notation and use Umax to denote Umax (Madv). Note that Theorem 4.5 special case of Theorem C.4 (Umax n1 - 722 and (N (N-1) so we first prove the general version Theorem and then Theorem 4.5 holds as result.
Proof of Theorem C.4 and Theorem 4.5 The majority voted action à is benign action, i.e., ā
Abeniga. if the ablation policy म renders action à for at least one purely benign k-sample. If Umax n2 n2. since n, n2 is exactly the total number of contaminated k-samples, then it is guaranteed that there is at least one purely benign k-sample for which á renders à. Thus, à E Abenign- and Theorem 4.5 holds.
On the other hand, if Umax S n1 n2, then in order for to be in Abenigu- among the Umax k-samples resulting in ā there can most Umax - contaminated k-samples. There are m2
Σ)=0 ("I (1==22)
n2 such combinations terms of the sampling of D, and the total number of D
combinations (R1) Therefore, get Equation 16
Reward Certificate.
Next, following Theorem
4.5
proceed prove the reward certificate.
Proof of Corollary C.1 Based on the definition of benign action set Abenign ा selects an action if and only if there exists purely benign k-sample [m]; E H₂ (m) such that the message-ablation policy t selects 7 = (7, [m]&). Therefore, for any trajectory generated by under attacks, there is (2) ... that renders the same cumulative reward trajectory of a with a list of k-samples [m]]]] [m][{) under no attack.
19

---

Published as a conference paper at ICLR 2023
D.2 PROOFS IN CONTINUOUS ACTION SPACE
Action Certificate. Similar to the discrete- anccrete-attionee case, we first prove Theorem C Theorem 4.7 as a special case of Theorem C.5
and then prove
Proof of Theorem C.5 To understand the intuition of element-wise median operation in continuous
action space, let us first start with an intuitive example: consider arbitrary numbers Ti, 25, if we already know 3 of them T1, 22, Iz. then it is certain that min(21, 22, x3) < Median(I1, ... Ts) .I5)) S max(x1, 22, æ3). Therefore, when purely benign k-samples form the majority (Condition 4.6). the
element-wise median action falls into the range of actions produced by safe messages.
To be more general, in a continuous action space, à E (anig((be is equivalent to the condition that out of the D sampled k- k-samples, purely benign k-samples make up the majority. There are
Σ}= ((j) (") D-j such combinations terms of the sampling of D, where D [ + 1. Once
again the total number of combinations is (")). Therefore, we get Equation 17
Proof of Theorem 4.7 The proof of Theorem 4.7 follows as a special case of Theorem
C.5 when
D D= (xx (1-1) = ny. In this case, the only non-zero term left in the numerator of pp (m2) k
R2
(m2) (m1 (m)=12)
1n1-22/ 1 (we need n2 and n1 n2 2 n1
keep the numerator from vanishing.
which implies j = n2, which is no lower than D since n2 m1/2 due to Condition 4.6 Hence we have pD
Reward Certificate.
Next, we derive the reward guarantee for the continuous-action case.
We let P(aass; σ) be the probability of the message-ablation policy Å taking action at state s, where can be either the message-ablation policy म the message-ensemble policy स. Note that this is a conditional probability function, and the policy does not necessarily observe
Proof of Theorem C,3
Without loss of generality, let v" be the optimal attacking algorithm that minimizes V.F Let As denote the range of benign action state s induced by the current message-ablation policy म. Then we have
V V*(s) - - (s)
sup SES
A(s.a)+ + Pis'ls, (s))) - E P(a
R(s, R( P(s' P(s')s, P(sl:+t0))
sup sES
(a
M(saa)) +7 P(51)s,a)) R((, -7 a2(
P(s P(8115.02)
sup sup sES A,,
S sup sup sES a.E.
(R(s,a1) -
sup anea " P( (18)8)001V" - P(6'ls, (3
/ P( P(s / P(s'ls, P(s'ls, (s')ds"
<E + sus sup #E8 EAA
/ P( Pl5l)s.a)) P(s'is, (s')ds'
< ER + suu sup sES EAA
/ (Iolls, /
a2) (s
+ysup sup sES aL,a
V$ (s) v*(s) V (6) +7 t ((6 P(6)))
ER + sup SES
< ER + 7 sup
y V*(s) 1 (6) +7Vmaxep.
SES
(18)
20

---

Published as a conference paper at ICLR 2023
By solving for the recurrence relation over sup,es V*(() -V, (s)
we obtain
+ VVmax
sup
(*(
(19)
SES
which leads to the desired relation in Theorem C,3
E EXPERIMENT DETAILS AND ADDITIONAL RESULTS
E.1 ENVIRONMENT DESCRIPTION
E.I.I FOODCOLLECTOR
The FoodCollector environment is 2D particle world adapted from the WaterWorld task in PettingZoo (Terry et al. 2020), shown by Figure colors, and N foods with colors corresponding the N agents. Agents are rewarded when eating foods with the same color. A big round obstacle is located the center of the map, which the agent cannot go through. There some poisons (shown as black dots) in the environment, and the agents get penalized whenever they touch the poison. Each agent has 6 sensors that detect the objects around it, including the poisons and the colored foods. The game is episodic, with horizon set to be 200. In the beginning of each episode, the agents, foods and poisons randomly generated in the world.
There are N agents with different
Figure 4: FoodCollector vironment. For figure readability. only show 3 agents colored as red/green/blue. In experiments, there are agents.
State Observation Each the sensors can detect the fol- lowing values when the corresponding element is within the sensor's range (the corresponding dimensions are O's if nothing detected);
(1) (if detects a food) the distance to food (real- (real-valued);
(2) (if detects food) the color of the food (one-hot);
(3) (if detects an obstacle) the distance to the obstacle (real-valued);
(4) detects the boundary) the distance the boundary (real-valued);
(5) (if detects another agent) the distance to another agent (real-valued).
The observation of an agent includes an agent-identifier (one-hot encoding), its own location (2D coordinates), its velocity, two flags of colliding with its food and colliding with poison, and the above sensory inputs. Therefore, the observation space is (7N + 30)-dimensione vector space.
Agent Action The action space be either discrete continuuu. For the discrete version, there are 9 actions including 8 moving directions (north, northwest, west, southwest, south, southeast, east, northeast) and no-move action. For the continuous version, the action is acceleration decision, denoted a 2- 2-dimensional real-valued vector, with each coordinate taking values in [-0.01, 0.01].
Reward Function At every step, each agent will receives a negative reward -0.5 it has not eaten all its food. In addition, it receives extra -1 reward if it collides with a poison. Therefore, every agent is expected explore the environment and eat all food fast possible. The team reward is calculated by the average of all agents' local rewards. Note that the agents' actions do not affect each other, because they have different target foods collect. Agents collaborate only via communication introduced below.
Communication Protocol Due to the limited sensory range, every agent can only see the objects around and thus only partially observes the world. Therefore, communication among agents can help them find their foods much faster. Since our focus defend against adversarially per-
.50
-00
Communcaaton
Communsiattoo
Conmanicttoon
No Commanicaton
Digtrete action space
(b) Continuous action space
Figure 5: FoodCollector: Reward of agents trained by PPO with
communication without communication. Black dashed line

---

Published as a conference paper at ICLR 2023
turbed communications, first de- fine valid and beneficial communica- tion protocol, where agent sends message to a receiver once it observes food with the receiver's color. For example, if a red agent encounters blue food, it can then send a message to the blue agent so that the blue agent knows where to find its food. To re- member the up-to-date communication, every agent maintains list of most recent N - messages sent from other N agents. message contains the sender's current location and the relative distance to the food (recorded by the sensors), which are bounded between -1 and 1. Therefore, message is a 8-dimensional vector, and each agent's communication list has 8(N - 1) dimensions in total.
During training with communication, we concatenate the observation and the communication list of the agent MLP-basee policy, compared to the nom-ommmunee where the policy only takes in local observations. More implementation details are in Appendix As verified in Figure communication does help the agent obtain much higher reward in both discrete action and continuous action cases, which suggests that the agents tend to rely heavily on the communication messages for finding their food.
Communication Gain
E.1.2 INVENTORY MANAGER
The InventoryyMnager environment is inventory management setup, where N 10 cooperative
heterogeneous distributors carry inventory for M = 3 products. A population of B = 300 buyers request product from randomly selected distributor agent according
demand distribution
p= p Par]- We denote the demand realization for distributor i with dj = [d........ d4 dr. Distributor agents manage their inventory by restocking products through interacting with the buyers. The game is episodic with horizon set to 50. At the beginning of each episode, a realization of the demand distribution p is randomly generated and the distributors' inventory for each product randomly initialized from [0, $1, where & is the expected number of buyers per distributor. The distributor agents are penalized for mismatch between their inventory and the demand for product, and they aim restock enough units of a product at each step to prevent insufficient inventory without accruing a surplus at the end of each step.
State Observation A distributor agent's observation includes its inventory for each product, and the products that were requested by buyers during the previous step. The observation space is a -i-diinnsionaa vector.
Agent Action Distributors manage their inventory by restocking new units of each product or discarding part of the leftover inventory at the beginning of each step. Hence, agents take both positive and negative actions denoted by an M M-dimensional vector, and the action space can be either discrete continuous. In experiments, we continuous actions assuming that products divisible and distributors can restock and hold fractions of a product unit.
During each step, agent i's reward is defined r; - max (1, +,, 0) d. 122 where I; denotes the agents initial inventory vector, and a, denotes the inventory restock vector from action policy 5;. Note that the agents' actions do not affect each other. Agents collaborate only via communication introduced below.
Reward Function
Communication Protocol Distributors learn the demand distri- bution and optimize their inventory by interacting with their own customers (i.e., portion of buyers that request a product from that distributor). Distributors would benefit from sharing their observed demands with each other, so that they could estimate the demand distribution more accurately for managing inventory. At the end of each step, a distributor communicates an M -ddimensional vector reporting its observed demands to all other agents. In the case of ad- versarial communications, this message may differ from the agents' truly observed demands.
Reoad
Commurccaion
Demmunication
Figure 6: PrventoryManagee Reward of agents trained with communication v.s. without com- munication.
22

---

Published as a conference paper at ICLR 2023
Communication Gain During training with communication, mes- sages received from all other agents are concatenated to the agent's observation, which is used to train MLP-basee policy, compared to the non-communicative case where the policy is trained using only local observations. As observed from Figure O communication helps agents obtain higher rewards since they are able to manage their inventory based on the overall demands observed across the population of buyers rather than their local observation. Results are reported by averaging rewards corresponding 5 experiments run with different training seeds.
E.1.3 MARL-MNIST
We use the environment setup proposed by Mousavi et al. Mousavi al. (2019), where agents collaboratively classify an unknown image by their observations and inter-agent communication. More specifically, we use N agents in the MNIST dataset of handwritten digits (LeCun et al. 1998). The dataset consists of 60,000 training images and 10,000 testing images, where each image has 28 x 28 pixels. There are rredeeteminedd spatial configuration. At every step, each agent observes local 5 5 patch, performs some local data processing, and shares the result with neighboring agents (we use a fully connected communication graph). With given observation and communication, each agent outputs an action in {Up, Down, Left, Right]. By each movement, the agent is translated in the desired direction by pixels. In the end of an episode, agents make predictions, and all of them are rewarded by -prediction loss.
steps in an episode. In the beginning, all agents start from a
E.1.4 TRAFFIC JUNCTION
We use the same environment setup as the one in (Singh et al. 2019). this environment, N cars enter junction from all entry points with given probability Purr- The maximum number of cars at any given time the junction limited. Cars can take two actions at each time-step, gas and brake respectively. At every step, each agent observes its previous action, route identifier, and vector specifying the sum of one-hot vectors for all objects present at that agent's 's location. A collision occurs when two occurs. In addition, to prevent traffic jams, for each time step when the agent is in the junction, it will get a negative reward of -0.01. The horizon of the environment is set be 60. We use the hardest. environment setup as in (Singh et al.] (2019), where we have 10 cars, the vision is set to zero, and the horizon of the environment is set to 80.
the same location, and the agent will get -10 reward if collision
E.2 IMPLEMENTATION DETAILS
E.2.1 FOODCOLLECTOR
Implementation of Trainer In our experiments, (Schulman et al. (017) algorithm to train all agents (with parameter sharing among agents) as well as the attackers. Specifically, we adapt from the elegant OpenAI Spinning Up (Achiam) (018) Implementation for PPO training algorithm. On top of the Spinning Up PPO implementation. we also keep track of the rumning average and standard deviation of the observation and normalize the observation. All experiments are conducted on NVIDIA GeForce RTX 2080 Ti GPUs.
the Proximal Policy Optimization (PPO)
For the policy network, we use a multi-layer perceptron (MLP) with two hidden layers of size 64. For discrete action space, a categorical output distribution is used. For continuous action space, since the valid action bounded within a small range [-0.01,0.01) we parameterize the policy as a Beta distribution, which has been proposed in previous works to better solve reinforcement learning problems with bounded actions (Chou et al. 2017). In particular, we parameterize the Beta distribution by ag and 3g. such that a log(1 + e f(a=h:
and 8 log(1 + efo())) + 1 is added to make sure that B 2 1). Then, <(ass) f( a, 3), where 0.01, and f(x; 8) = r(o+t)) network, also use MLP with two hidden layers of size 64.
[[] 20 0-1
1 is the density function of the Beta Distribution. For the value
In terms of other hyperparameters used in the experiments, we use a learning rate of 0.0003 for the policy network, and learning rate of 0.001 is used for the value network. We use the Adam
23

---

Published as a conference paper at ICLR 2023
optimizer with 31 = 0.99 and 32 0.999. For every training epoch, the PPO agent interacts with the environment for 4000 steps, and it is trained for 500 epochs in our experiments.
Attacker An attacker maps its observation the malicious communication messages that it will send to the victim agent. Thus, the action space of the attacker is the communication space of a benign agent, which is bounded between -1 and 1.
Heuristic Attacker We implement a fast and naive attacking method for the adversary. At every dimension, the naive attacker randomly picks or-1 its action, and then sends the perturbed message which consists entirely of or to the victim agent.
Adaptive RL Attacker We use the PPO algorithm to train the attacker, where we set the reward of the attacker to be the negative reward of the victim. The attacker uses Gaussian policy, where the action clipped to be in the valid communication range. The network architecture and all other hyperparameter settings follow the exact same from the clean agent training.
Implementation of Baselines
Vanilla Learning For Vanilla method, we train shared policy network to map observations
and communication actions.
Adversarial Training (AT) For adversarial training, alternate between the training of attacker and the training of the victim agent. Both the victim and attackers are trained by switch the training, where we either fix the trained
PPO. For every 200 training epochs, victim and train the attacker for the victim or fix the trained attacker and train the victim under attack. We continue this process for 10 iterations.
Note that the messages are symmetric (of the same format), we shuffle the messages before feeding them into the policy network for both Vanilla and AT, to reduce the bias caused by agent order. We find that shuffling the messages helps the agent converge much faster (50% fewer total steps). Note that AME randomly selects k-samples and thus messages are also shuffled.
E.2.2 INVENTORY
Implementation of Trainer As in the FoodCollector experiments, we use the PPO algorithm to train all agent action policy as well as adversarial agent communication policies. We use the same Gaussian
MLP-based policy and value networks as the FoodCollector but parameterize the policy distribution. The PPO agent interacts with the enviromment for 50 steps, and it is trained for 10000 episodes. The learning rate set to be 0.0003 for the policy network, and 0.001 for the value network.
The attacker uses its observations to communicate malicious messages to victim distribu- tors, and its action space is the communication space of a benign agent. We consider the following non-adaptive and adaptive attackers:
Attacker
Heuristic Attackers: The attacker's goal is to harm the victim agent by misreporting its observed demands that the victim distributor under-estimates over-estimates the re- stocking of products. In our experiments, we evaluate the effectiveness of defense strategies against the following attack strategies:
Perm-Attack: The communication message is random permutation of the true demand vector observed by the attacker.
Swap-Attack: In order to construct a communication vector as different as possible from its observed demand, the attacker reports the most requested products the least request ones and vice versa. Therefore, the highest demand among the products is interchanged with the lowest demand, the second highest demand is interchanged with the second lowest demand and so forth.
Attack: Adversary modifies its observed demand d, by mirroring it with respect to 17 37 Σnn dej. such that products demanded less than r) are reported as being requested more, and conversely, highly demanded products are reported as less popular. Adaptive Attacker: The attacker communication policy trained using the PPO algorithm, and its reward is set the negative reward of the victim agent. The attacker uses
24

---

Published as a conference paper at ICLR 2023
Gaussian policy with softmax activation in the output layer to learn adversarial probability distribution across products, which is then scaled by the total observed demands Σド=1 dif construct the communication message.
Implementation of Baselines
Vanilla Learning: In the vanilla training method with no defense mechanism against adver- sarial communication, we train shared policy network using agents' local observations and their received communication messages.
Adversarial Training (AT): We alternate between training the agent action policy and the victim communication policy, both using PPO. For the first iteration we train the policies for 10000 episodes, and then use 1000 episodes for 5 additional training alteration iterations for both the action policy and the adversarial communication policy. For more efficient adversarial training, we first shuffle the received communication messages before feeding them into the policy network. Consequently, the trained policy treats communications received from different agents in a similar manner, and we are able to only train the policy with a fixed set of adversarial agents rather than training the network all possible combinations of adversarial agents.
For Vanilla and AT, we do not shuffle the communication messages being input to the policy, we did not observe improved convergence, as the FoodCollector environment.
E.2.3 MARL-MNIST
We use the same network architecture and hyprrparameter setting Mousavi et al. Mousavi et al. (2019), which are implemented in Berrien (2019).
Concretely, every step, the input of every agent contains 3 components: (1) an encoded observation with two convolutional layers followed by vectorization and fully connected layer; (2) the average of all communication messages from other agents; (3) position encoding computed by feeding the current position into a single linear layer. These 3 components are concatenated and passed two independent LSTM modules, one is for an acting policy, another is for a message generator. In the end of an episode, every agent uses its final cell state to generate prediction using 2-layer MLP. Then we take the average of the output logits of all agents, and use a softmax function to obtain the final probabilistic label prediction. The reward is the opposite number of the L. difference between the prediction and the one-hot encoding of true image label.
Network Architecture
Hyperparameters In our experiments, we follow the default hyperparameter setting in Berrien (2019). We use N agents. The size of LSTM belief state is 128. The hidden layers have size 160. The message size is set to be 32. The state encoding has size 8. We use an Adam optimizer with learning rate 1c-3. We train the agents in the MNIST dataset for 40 epochs.
Attackers Since the communication messages learned by neural networks, we perturb the C' messages received by each agent. To make sure that the messages are not obviously detectable, we clip every dimension of the perturbed message into the range of 13, 3]. The non-adaptive attacker randomly generates a new message. The adaptive attacker learns a new message generator based on its own belief state, which is trained with learning rate 1e-3 for 50 epochs.
E.2.4 TRAFFIC JUNCTION
To lear the agents' policy and communication protocol on traffic junctions, we follow exactly the implementation of (Singh al. 2019).
Network Architecture In particular, the policy of the j-th agent in IC3Net takes the form of:
9 (+1
(h)))
h 1+1 j
(e(o)) + eg. 1y,
1
C Σ htt
of
N
377
of = (ht)
25

---

Published as a conference paper at ICLR 2023
Here, 93 is binary action that specifies whether the agent j should communicate with other agents, and so it acts as a gating function when calculating the communication messages c++ fo()) is simple network containing soft-max layer for 2 actions (communicate not) top of linear layer with non-linearity. is an encoder of the agent's s observation and C' is a linear transformation matrix for transforming gated average hidden state to communication tensor that has the same size as the observation encoding.
Hyperparameter The encoder is linear layer of size 128, and (-) is also linear layer of size 128. The LSTM module is two layers with hidden size 128, and the policy head æ is linear layer with output size equal to the number of actions.
Attacker We perturb the C messages received by each agent. To make sure that the messages obviously detectable, clip every dimension of the perturbed message into the range of [-0.5, 0.5]. The non-adaptive attacker randomly generates a new message containing either -0.5 or 0.5. For the adaptive attacker, is trained with recurrent PPO through et al. 2021) for 500,000 steps.
(Raflin
E.3
ADDITIONAL RESULTS
E.3.1
FULL RESULTT OF FOODCOLLECTOR
Figure 7 below shows the results of both discrete-action FoodCollector and continuous-action FoodCollector.
FoodCollector
FoodCcell
FoodCollector
Collectoo
Vanda
AMB (heno
-
No Ancker 0-11
6-2
No Anaaeer C-1
C-
0-2
No Aetddrr 61-11
17-22
No Arader G. 0-2
(a) Disc. & Heuristic
(b) Disc. & Adaptive
(c) Cont. & Heuristic
(d) Cont. & Adaptive
Figure 7: Rewards our AME and baselines FoodCollector, under no attacker and varying numbers of adversaries for adaptive and heuristic (random message) attacks.
Additional Results on Discrete-action Food- Collector with QMIX AME a generic defense approach that be used for any RL/MARL learning algorithm. In Figure 8 we show the results of AME combined with MARL algorithm QMIX (Rashid et al.) (018)) in the discrete-action FoodCollector environment (QMIX does not work for continuous actions so not applicable in continuous-action Food- Collector and InventoryManageer) Compared to the vanilla QMIX algorithm, QMIX+AME achieves much higher robustness and stable per- formance under various numbers adversaries.
-40
(a) Discrete Heuristic
(b) Discrete & Adaptive
Figure Reward comparison between original QMIX QMIX combined with our AME FoodCollector with discrete action space, under no attacker or non- adaptive/adaptive attacks under varying numbers of ad- versaries. For AME, the ablation size k is set
E.3.2 FULL RESULTS INVENTORY
Figure 9 below shows the results of anventoryManager under adaptive attacks and several heuristic attacks.
E.3.3 FULL RESULTS OF MARL-MNIST
Figure 10 demonstrates the robust performance of the MARL algorithm proposed by Mousavi et al. (2099) with our AME defense or baseline defenses (Vanilla and AT). We set N = 9 and is = 2 for all experiments. Under learned adaptive attackers, the original MARI classifier (Vanilla) (Mousavi
26

---

Published as a conference paper at ICLR 2023
Iuventory Manager
IavenforyMunager
InveneeryManngge
Iuventory Manager
Yoads
Yodk
AME
AMA
Owl
No.
6:42
Old
Artdeer
No Frnder Call
(a) Adaptive Attack
(b) Perm-Attack
(c) Attac-
(d) Flip-Attack
Figure 9: Rewards of our AME and baselines in Inventory InventoryManager under no attacker and varying numbers of adversaries for adaptive and various heuristic attacks.
et al. 2019) without AME suffers from significant performance drop in terms of both precision and recall. Defending with adversarial training (AT) does not achieve good robustness, either. But AME considerably improves the robustness of agents across different numbers of attackers.
Under random attacks, we find that the original MARL classifier (Mousavi et al. 2019) is moderately robust when a few communication signals are randomly perturbed. However, when noise exists in AME still achieves high performance when C' = 6 communication messages are corrupted, even the
many communication channels (e.g. C 6). the performance decreases lot. In contrast,
guarantee of ablation size k only holds for C < 2. Therefore, we again emphasize the the theoretical guarantee considers the worst-case strong attack, while under a relatively weak attack, we can achieve better robustness beyond what the theory suggests.
MARL-MNIST
MARI-MNIST
MARL-MNIST
MARI-MNIST
Vada
2 4MF-D
AT
-an AT
6.55
07
A4
(a) Adaptive Attack
(b) Adaptive Attack
(c) Hcuristic Attack
(d) Hcuristic Attack
Figure 10: (MARL-MNIST): Precision and recall of MARL classification on MNIST without or with AME,
under learned adaptive attacks and non non-adaptive random attacks. All results are averaged over random sceds.
E.3.4 ADDITIONAL. RESULTS OF HYPERPARAMETER TEST
In addition to Figure 3 we also provide the plot for hyper-parameter tests in discretc-action FoodCol- lector and InventoryManager in Figure] [1 below.
do Faoe Attck
Arack
Beand Pree
Six
Ab Abaam
(a) FoodCollector
(b) InventoryManager
(c) FoodCollector
(d) InventoryManager
Figure 11: Hyper-papn parameter tests of ablation size & and sample size D. We show how natural reward and attacked performance change with (a) various A in contimuous-action FoodCollector, (b) various 1) in continuous- action FondCollcctor, (c) various k in InventoryMannger, and (d) various 1) in InventoryManager. Dashed green lines refer to the performance of Vanilla agent under attacks.
27

---

Published as a conference paper at ICLR 2023
E.3.5 INTERPRETATION OF ADVERSARIAL TRAINING
As we observed in Figure 2 adversarial training (AT) does not improve the robustness of the agent in both discrete and continuous action space, although AT achieves good robustness againt l, attacks in vision tasks (Madry et al. 2018 Zhang et al. 2019), and against observation attacks (Zhang et al.)
2021; Sun al. [2022] and action attacks (Pinto et al.) 2017) in RL. We hypothesize that it due to (I) the large number of total agents, (2) the uncertainty of adversarial message channels, and (3) the relatively large perturbation length. To be more specific, in related works (Pinto et al. 2017 Zhang et al.] 2021 [Sun et al., 2022), an agent and an attacker are alternately trained, during which the agent learns to adapt to the learned attacker. However, the threat model we consider, there are C' out of N messages significantly perturbed, which it is hard for the agent to adapt to attacks during alternate training.
F ADDITIONAL. DISCUSSION ON THE CHOICE OF ABLATION SIZE k
Our AME defensive mechanism proposed in Section requires an extra hyperparameter: the ablation size k. (The sample size D is only for the partial-sample variant introduced in Section[4.3 not needed in the original form of AME.) In this section, we discuss the selection of in practice. We start by discussing the relationship between & and the required theoretical conditions.
(For Continuous Action Space) Condition 4.6 and k
We first decompose Equation
(6 as below.
N
C
1
N N-1
(20)
2
(N - 1 CY!
(N - 1)!
(21)
(N 1 C k)Ik!
2(N
k)Ik!
(N 1)--1).... (N C)
1> 2(N h- 1). (N k C)
(22)
Therefore, Equation 6 is equivalent to
1
(N - 1)...... - 2 (N 11) (N C)
(23)
When & 1, the above inequality becomes
1
(N - 2) (N - CN - C - --1)
- (N 1)(N -2....
(24)
2
1
(N - C - 1) (N 1)
(25)
2
1 (N 1) > C,
(26)
which holds under Assumption 3.1 tion 4.6
Therefore, k is always feasible solution for Condi-
Then, when C is fixed and & goes up from I, the LHS of Equation 23 goes down while the RHS
does not change. Therefore, for a given number of agents (N) and a fixed number of adversaries (C), there exists an integer Kg such that any S ko satisfies Condition 4.6 In practice, if we have an estimate of the number of adversarial messages that we would like to defend against, then we could choose the maximum satisfying Equation (6).
On the other hand, when & is fixed, there exists Co such that any C < Co can let Equation (3)
hold, Therefore, if C unknown, for any selection of k, Equation (23 can justify the maximum number of adversaries for the current selection.
we can see the interdependence between three parameters: total number of agents N. number of adversaries C, and the ablation size k. In Figure 12 we visualize their relationship by fixing one variable at a time. From these figures, we can see an obvious trade-off between and k if there more adversaries, & has to be set smaller. But when C is small, e.g. C = 1, k can be relatively large, so the agent does not need to compromise much natural performance to achieve robustness.
From Equation (2),
28

---

Published as a conference paper at ICLR 2023
Mosimure sumber comitaieeeeee....mmm.. cominnll--nnneeeeee Sen
Masinam Centled Alution
3 Agcrss)
N (25 Agenss
TOL Agenss
Ablation Size
Abbeisn
Ablation Sine
Seen Sinck
Masinann Cla sfeee Mitllle
14-
Attadero 212 Atader)))
3153 Attadees
30
N (30 Agenss)
Abiitio Size 2 =
8
5
6-
14
10
16
25
30
5
10
13 20
Number Attackers
Nunbbrr
Number
(a) C' vs. &
(b) N vs. C'
(c) N vs. &
Figure 12: Relationship between the total number of agents N, number of attackers C, and ablation size (a): Maximum certifiable ablation size & under diffcrent number of attackers. (b); Maximum defensible number of attackers C' with different total number of agents N. (c): Maximum certifiable ablation size & with different total number of agents N.
II. (For Discrete Action Space) Condition 4.4 and &
Different from Condition 4.6 which is independent of the environment, Condition 4.4 required in discrete action space is related to the environment and the communication quality. Intuitively, Condition 4.4 can be satisfied the benign messages can reach some "consensus", i.e., there enough purely benign k-samples voting for the same action. This can be achieved when the environment is relatively deterministic (e.g., there is a certainly optimal direction to go). Fortunately, Condition 4.4 can be checked during training time, and we can train the message-ablation policy and the communication policy to increase Umax as much as possible.
On the other hand, Condition 4.4 4.4 is also related the selection of ablation size The ratio of contaminated votes is
(N-1)
and it is easy show that this rate increases as k when N 1 Therefore, when is smaller, it is relatively easier to satisfy Condition 4.4 as the adversarial messages can take over a smaller proportion of the total number of votes.
Balances between Natural Performance and Robustness The above analysis shows that a smaller k makes the agent more robust, while the natural performance may be sacrificed the message- ablation policy makes decisions based on less benign information. Such trade-off between natural performance and robustness is common in the literature of adversarial learning (Tsipras et al. 2019] Zhang et al. 2019). Note that AME randomize the message ablation process at every step, such that important messages are less likely be missed, as communication from every agent usually does not drastically change over time. Our experimental results in Section show that the robustness gain of AME is much greater than the compromise in natural performance in all tested domains.
How to Select in Practice? In practice, we suggest setting k: to be the largest integer satisfying Equation (6). If higher robustness is needed, then can be further decreased. If robustness is not the major concern while higher natural performance is required, one can increase k. Note that if N AME degenerates to the original vanilla policy without defense.
What If Conditions Are Not Satisfied? Even if Condition 4.6 and Condition 4.4 are not satisfied, the agent can still be robust under attacks as verified in our experiments (AME with k still achieves relatively robust performance under C' = 3 which exceeds the theoretically largest number of certifiable adversaries). Because these conditions are needed for the certificates which consider the theoretically worst-case attacks. However, in practice, attacker has restricted power and knowledge (e.g., does not know the victim policy/reward, and does not know the environment dynamics as prior), and is likely to be even weaker than the learned adaptive white-box attacker use in experiments. As a result, even if larger & may break the conditions, it can still improve the empirical robustness of agent in practice. Our Figure and Figure 1T where AME maintains good empirical performance for almost all choices of k < 1. (K policy without defense.)
1 is the original vanilla
Extension: Adaptive Defense with Different i's Moreover, to allow higher flexibility, one can train multiple message-ablation policies with different selections of k's during training. Then,
29

---

Published as a conference paper at ICLR 2023
adaptive strategy be used in test time. For example, if Umax is too small, can use larger with the corresponding trained pessage-ablationn policy.
Extension: Gaining both Natural Performance and Robustness by Attack Detection From the analysis of the relation between N, C' and k. we can see that when the number of adversaries is large, the corresponding ablation size l is supposed to be smaller. This is reasonable because a more conservative defense needed against a stronger attacker. But if we can identify some adversarial messages and rule them out before message ablation and ensemble, we can still defend with guarantees using a relatively large k. For example, if we have identified c adversarial messages, then we only need deal with the remaining By Equation (6). larger l can be used compared to defending C' advvrsarial messages out of N messages. We also provide an adversary detection algorithm in Appendix Gusing a similar idea of AME.
c adversarial messages out of
c messages.
G DISCUSSION: DETECTING MALICIOUS MESSAGES WITH ABLATION
As discussed in Appendix F to defend against a larger C, one has to choose relatively small k for certifiable performance. However, Figure suggests that a small also sacrifices the natural performance of the agent to obtain higher robustness. This is known as the trade-off between robustness and accuracy (Tsipras et al., 2019; Zhang et al. 2019). Can we achieve better robustness while not sacrificing much natural performance, obtain higher natural reward while not losing robustness?
We point out that with our proposed AME defense, it is possible to choose a larger l than what required by Condition (.6iiiooo446//iiee with- sacrificing robust performance by identifying the malicious messages beforehand. The idea is to detect the adversarial messages and to rule them before message ablation and ensemble, during the test time.
-10
Action Blas
We hypothesize that given well-trained victim policy, ma- licious messages tend to mislead the victim agent to take an action that is "far away" from a "good" action that the vie- tim is supposed to take. To verify this hypothesis, we first train message-ablation policy क with k Then for every communication message that another agent j sends, we compute the action a, that the victim policy ni; chooses based on all message subsets containing message my+s, i.c. aj = (T,, my-ss) (note that &o = 1 so only takes in message at time). We then define the action bias as B3 = |a, - Median (ax) N |11- Based on our hypothesis, an agent which has been hacked by attackers should induce significantly larger action bias since they trying mislead the victim to take a completely different action. Here, we execute the policy of two hacked agents together with six other good agents for twenty episodes and calculate the average action bias for each agent. As shown in in Figure 13] the agents hacked by attackers indeed induce larger action bias compared to other benign agents, which suggests the effectiveness of identifying the malicious messages by action bias.
2
Adv1Ad22
83
85
for agent i.
Attacker identification based on action bias 2g.- Adv1 and Adv2 stands for two agents hacked by the attacker. B1 up to B6 stands for six other benign agents.
Figure 13:
After filtering out messages, one could compute the required & by Equation equation 6 based on C - e malicious messages and N - - e total messages, which can larger than the largest induced by C' malicious messages out of N - total messages. For example, if N = 30, C = 3, then the largest satisfying Equation equation 6 5, but when adversarial message is filtered out, the largest k that can defend against the remaining 2 adversarial messages is 8. Although the adversary identification is not theoretically guaranteed to be accurate, Figure 13 demonstrates the effectiveness of the adversarial message detection, which, combined with AME with larger k has the potential to achieve high natural performance and strong robustness in practice.
30


Reviews:
[{"review_id": "pC_cPmGG6d", "reviewer": "Reviewer_BxRb", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This manuscript introduces a new setting in multi-agent reinforcement learning with communication, where the communication could be attacked in several ways. The message could be alternated, the agents who send the messages could be hacked, and such attacks could happen in multiple places and could be adaptive to the receiver agent. To address this, the manuscript proposes a pretty much *general* solution, which is based on a message aggregation strategy. It basically guarantees that the receiver receives multiple messages and works on the ensemble of them, in a way that if some messages are attacked in some way, the aggregation still gives the close-to-true value. The manuscript claims that if the number of attacked messages is less than half then the action is to some extent \"safe\". The manuscript also did some simulations.\n\nThe method is a consensus-based aggregator, which trains a base policy that uses $k$ out of $n$ messages from the sender agents. At test time $k$ messages are sampled from all messages to compute the output and this process is repeated for multiple times. The median of the outputs is used as the final output. This method is quite intuitive.", "summary_of_the_review": "A manuscript that investigates a novel and relevant setting. The results are decent yet limited to certain settings. I would say, this manuscript is borderline.", "strength_and_weaknesses": "Pro:\n\n1. The manuscript investigates an interesting problem and the problem is indeed relevant in a variety of applications.\n\n2. The authors have spent an effort to illustrate the proposed method from multiple aspects, including some theoretical derivation, some simulations, and the intuition underlying the method.\n\n3. Experiments are conducted in multiple tasks.\n\nCons:\n\n1. The guarantee of the \"certifiable robustness\" is very general and is not strong enough. I'm wondering if certain bounds on robustness and utility could be proved in concrete examples.\n\n2. The setting that an agent receives $n$ messages is not realistic in many tasks, like SMAC. It is unlikely that all messages from $n$ agents are (equally) useful so in practice an attack on an important message could do more damage than the paper guaranteed. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "VeZWOzp19h", "reviewer": "Reviewer_drA6", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies communication attack in multi-agent reinforcement learning. They provide a defense by constructing a message-ensemble policy that aggregates multiple message sets. THey showed the effectiveness of their algorithm theoretically and practically.", "summary_of_the_review": "This paper studies communication attack in multi-agent reinforcement learning. They provide a defense by constructing a message-ensemble policy that aggregates multiple message sets. THey showed the effectiveness of their algorithm theoretically and practically.", "strength_and_weaknesses": "1)Author motivates the subject from a theoretical and practical point of view. \n2)In the introduction, the author reviewed the previous works carefully. \n3)the author successfully addressed the issue and recommended the algorithms.\n 4)The authors successfully provide simulation results for their algorithm. \n5)The proof is mathematically correct.\n6) the paper is well-written.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Rg0ecYCeBAk", "reviewer": "Reviewer_iqJ1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers adversarial robustness in the communicative multi-agent reinforcement learning setting (CMARL), where $N$ agents communicate with each other.\nAt each step, an agent observes (their part) of the environment, receives messages from the other $N-1$ agents, and proposes an action.\nThe thread model considered in this paper assumes that for an (arbitrary) individual agent up to $C \\leq \\frac{N-1}{2}$ of the received messages can be arbitrarily changed. This setting is formalized and a certifiable defense, AME, for it is proposed.\n\nAME utilizes a random ablation approach, as proposed in [1]: the action is determined as the aggregate over the output of an arbitrary underlying policy evaluated on $D$ randomly sampled subsets of the received messages.\nEach subset is of size $k \\leq N-1$, where the parameter $k$ controls a trade-off between high robustness ($k$ low) and high performance ($k=N-1$; the standard underlying algorithm). The aggregation operation depends on whether continuous or discrete actions are considered.\n\nAME is evaluated in different CMARL environments, where AME (usually) reduces the performance when no adversary is present.\nHowever, in case an adversary is present AME indeed outperforms standard and adversarial trianing. \n\n[1] Robustness certificates for sparse adversarial attacks by randomized ablation, Alexander Levine and Soheil Feizi, AAAI20\n", "summary_of_the_review": "The paper studies an important problem -- communication robustness in CMARL -- and proposes a simple yet effective and well-founded defense. The paper is (largely) well-written and easy to follow.\n\nI thus recommend acceptance.\n\n\n", "strength_and_weaknesses": "**Strengths:**\n- Strong and relevant attacker model.\n- Simple, well-motivated certifiable defense.\n- Mathematical details appear to be sound.\n- Thorough evaluation.\n\n**Weaknesses:**\n- The paper does not discuss the robustness certificate in depth (although the appendix does). Generally, I feel, the paper might benefit from including more from appendices B and C in the main paper (at the cost of shortening some other discussion).\n- While the evaluation is thorough, Section 6 was hard to follow (as it required a lot of going back and forth between multiple paragraphs and Figure 3).\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster