Mis-spoke or mis-lead: Achieving Robustness in Multi-Agent Communicative Reinforcement Learning

An MACRL problem can be modeled by Decentralised Partially Observable Markov Decision Process with Communication (Dec-POMDP-Com) Oliehoek et al. (2016), which is defined by a tuple $\langle\mathcal{S},\mathcal{M},\mathcal{A},\mathcal{P},R,\Upsilon,O,C,\mathcal{N},\gamma\rangle$. $\mathcal{S}$ denotes the state of the environment and $\mathcal{M}$ is the message space. Each agent $i\in\mathcal{N}:=\{1,...,N\}$ chooses an action $a_{i}\in\mathcal{A}$ at a state $\bm{s}\in\mathcal{S}$, giving rise to a joint action vector, $\bm{a}:=[a_{i}]_{i=1}^{N}\in\mathcal{A}^{N}$. $\mathcal{P}(\bm{s}^{\prime}|\bm{s},\bm{a}):\mathcal{S}\times\mathcal{A}^{N}\times\mathcal{S}\mapsto\mathcal{P}(\mathcal{S})$ is a Markovian transition function. Every agent shares the same joint reward function $R(\bm{s},\bm{a}):\mathcal{S}\times\mathcal{A}^{N}\mapsto\mathbb{R}$, and $\gamma\in[0,1)$ is the discount factor. Due to partial observability, each agent has individual partial observation $\upsilon\in\Upsilon$, according to the observation function $O(\bm{s},i):\mathcal{S}\times\mathcal{N}\mapsto\Upsilon.$ Each agent holds two policies, i.e., action policy $p_{i}(a_{i}|\tau_{i},m_{i}^{in}):\mathcal{T}\times\mathcal{M}\times\mathcal{A}\mapsto[0,1]$ and message policy $v_{i}(m_{i}^{out}|\tau_{i},m_{i}^{in}):\mathcal{T}\times\mathcal{M}\times\mathcal{M}\mapsto[0,1]$, both of which are conditioned on the action-observation history $\tau_{i}\in\mathcal{T}:=(\Upsilon\times\mathcal{A})$ and incoming messages $m_{i}^{in}$ aggregated by the communication protocol $C(m_{i}^{in}|\bm{m}^{out},i):\mathcal{M}^{|\mathcal{N}|}\times\mathcal{N}\times\mathcal{M}\mapsto[0,1]$.

In adversarial communication where there are $N_{adv}$ malicious agents, we assume that each malicious agent holds the third private adversarial policy, $\xi(\delta_{i}^{adv}|\tau_{i},m_{i}^{in},m_{i}^{out}):\mathcal{T}\times\mathcal{M}\times\mathcal{M}\times\mathcal{M}\mapsto[0,1]$, which generates adversarial message $\delta_{i}^{adv}$ based on its action-observation history $\tau_{i}$, received messages $m_{i}^{in}$ and the message $m_{i}^{out}$ intended to be sent. Malicious agents could send messages by convexly combining their original messages with adversarial messages, i.e., $m_{i}^{adv}=(1-\omega)\times m_{i}^{out}+\omega\times\delta_{i}^{adv}$, or simply summing up the messages, i.e., $m_{i}^{adv}=m_{i}^{out}+\delta_{i}^{adv}$. To reduce the likelihood of being detected, apart from the adversarial policy $\xi$, malicious agents strictly follow their former action policy and message policy, trying to behave like benign agents. Fig. 1(a) presents the overall attacking procedure. The agent $i$ (attacker) is malicious and tries to generate adversarial message $m_{i}^{adv}$ to disrupt cooperation. The adversarial message sent by agent $i$ together with normal messages sent by other agents (denoted by $\bm{m}_{-i}^{out}$) are processed by the communication protocol (algorithm-related), generating a contaminated incoming message $m_{j}^{in}$ for a benign agent $j$. From agent $j$’s perspective, under such attack, the estimated Q-values will change. If the action with the highest Q-value shifts, agent $j$ will make incorrect decisions, leading to suboptimality. To perform an effective attack in MACRL, we propose to optimize the adversarial policy $\xi$ by minimizing the joint accumulated rewards, i.e., $\min_{\xi}\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}r_{t}\right]$. We make two assumptions to make the adversarial communication problem both practical and tractable.

To defend against the attacker, as in Fig. 1(b), we propose to cascade a learnable defender to the communication protocol module. The defender performs a transformation from $m_{j}^{in}$ to $\hat{m}_{j}^{in}$ to reconstruct the contaminated messages, to avoid distributing the contaminated message $m_{j}^{in}$ directly to agent $j$. With such transformation, the benign agent $j$ can estimate the Q-value for each action more properly and reduce the probability of selecting sub-optimal actions.

To model the attack scheme in adversarial communication, we use a deep neural network (DNN) $f_{\mu}$, parameterized by $\theta_{\mu}$, to generate adversarial messages for a malicious agent. The adversarial policy $\xi$ is a multivariate Gaussian distribution whose parameters are determined by the DNN $f_{\mu}$, i.e., $\xi=\mathcal{N}(f_{\mu}(\cdot|\tau,m^{in},m^{out};\theta_{d}),\Lambda)$ where $\Lambda$ is a fixed covariance matrix. The reason of using Gaussian distribution as the prior is that it is the maximum entropy distribution under constraints of mean and variance. Each malicious agent generates adversarial messages by sampling from its adversarial policy. The optimization objective of the adversarial policy is to minimize the accumulated team rewards subject to a constraint on the distance between $m^{out}$ and $m^{adv}$. We utilize Proximal Policy Optimization (PPO) Schulman et al. (2017) to optimize the adversarial policy by maximizing the following objective:

where $\rho=\xi(\delta^{adv}|\tau,m^{in},m^{out})/\xi^{old}(\delta^{adv}|\tau,m^{in},m^{out})$, $\xi^{old}$ is the policy in the previous learning step, $\epsilon$ is the clipping ratio, and $A^{\xi}(\delta^{adv},\tau,m^{in},m^{out})$ is the advantage function. Let $e=\langle\tau,m^{in},m^{out}\rangle$ denotes the input of the value function and we define the reward of the attacker to be negative team reward, then $A^{\xi}(\delta^{adv},e)=-r+V(e^{\prime})-V(e)$ where $V$ is the value function, $e^{\prime}$ denotes the next step state, and $r$ is the immediate reward. We learn the value function $V(e)$ by minimizing $\mathbb{E}[(V(e)+\sum_{t}\gamma^{t}r_{t})^{2}]$.

We can train a DNN to model the attack scheme in adversarial communication. However, the defence of that is non-trivial because i) benign agents have no prior knowledge on which agents are malicious; ii) the malicious agents can inconsistently pretend to be cooperative or non-cooperative to avoid being detected; and iii) recovering useful information from the contaminated messages is difficult. To address these challenges, we design a two-stage message filter for the communication protocol to perform defence. The message filter works by first determining the messages that are likely to be malicious and then recovering the potential malicious messages before distributing them to the corresponding agents. As in Fig. 2, the message filter $\zeta(h_{d},g_{r})$ consists of an anomaly detector $h_{d}$ and a message reconstructor $g_{r}$. The anomaly detector, parameterized by $\theta_{d}$, outputs the probability that each incoming message needs to be recovered, i.e., $h_{d}(\cdot|m_{i}^{out};\theta_{d}):\mathcal{M}\mapsto\Psi$, where $\Psi$ denotes a binomial distribution, $m_{i}^{out}$ denotes the message sent by agent $i$. We perform sampling from the generated distributions to determine the anomaly messages $\bm{x}\sim h_{d}(\cdot|\bm{m}^{out};\theta_{d})$ ¹¹1We abuse $h_{d}(\cdot|\bm{m}^{out};\theta_{d})$ to represent that messages $m^{out}_{i}\in\bm{m}^{out}$ are fed into $h_{d}$ in batch.. Here, $\bm{x}$ is an indicator that records whether a message is predicted to be malicious or not. The predicted malicious messages $\bm{\dot{m}}$ are recovered by the reconstructor $g_{r}(\cdot|\dot{m}_{i};\theta_{r}):\mathcal{M}\mapsto\mathcal{M}$ separately. The recovered message and other normal messages are aggregated and determine the messages that each agent will receive.

The optimization objective of the message filter is to maximize the joint accumulated rewards under attack, i.e., $\max_{\zeta}\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}\tilde{r_{t}}|\xi\right]$, where $\tilde{r_{t}}$ is the team reward after performing the defending strategy. We utilize PPO to optimize the strategy. To mitigate the local optima induced by unguided exploration in large message space, we introduce a regularizer which is optimized under the guidance of the ground-truth labels of messages (whether they are malicious). For the reconstructor, we train it by minimizing the distance between the messages before and after being attacked. To improve the tolerance of the reconstructor to errors made by the detector, apart from malicious messages, we also use benign messages as training data, in which case the reconstructor is an identical mapping. Formally, the two-stage message filter is optimized by maximizing the following function:

where $\rho_{i}=h_{d}(x_{i}|m_{i};\theta_{d})/h_{d}^{old}(x_{i}|m_{i};\theta_{d})$, $A^{h_{d}}_{i}(x_{i},m_{i})$ is the advantages which are estimated similarly as in the attack, $\bm{\hat{y}}$ is the one-hot ground-truth labels of messages, $\bm{\hat{m}}$ is the messages that have not been attacked. $\beta_{1}$, $\beta_{2}$ and $\epsilon$ are hyperparameters.

Despite the defensive message filter, the effectiveness of the defence system can rapidly decrease if malicious agents are aware of the defender and adjust their attack schemes. To mitigate this, we formulate the attack-defence problem as a two-player zero-sum game (malicious agents are controlled by the attacker) and improve the performance of the defender in the worst case. We define the adversarial communication game by a tuple $\langle\Pi$, $U\rangle$, where $\Pi=\langle\Pi_{\xi},\Pi_{\zeta}\rangle$ is the joint policy space of the players ($\Pi_{\xi}$ and $\Pi_{\zeta}$ denote the policy space of the defender and the attacker respectively), $U:\Pi\mapsto\mathbb{R}^{2}$ is the utility function which is used to calculate utilities for the attacker and the defender given their joint policy $\pi=\langle\pi_{\xi},\pi_{\zeta}\rangle\in\Pi$. The utility of the defender is defined as the expected team return. The adversarial communication game is zero-sum, i.e., the utility of the defender $U_{\zeta}(\pi)$ must be the negative of the utility of the attacker $U_{\xi}(\pi)$ for $\forall\pi\in\Pi$. The solution concept of the adversarial communication game is Nash equilibrium (NE) and we can approach an NE by optimizing the following MaxMin objective:

where $\operatorname{Br}(\pi_{\zeta})$ is the best response policy of the defender, i.e., $\operatorname{Br}(\pi_{\zeta})=\arg\min_{\pi_{\xi}}U_{\zeta}(\pi_{\xi},\pi_{\zeta})$.

We propose $\mathfrak{R}$-MACRL to optimize the objective in the adversarial communication game. $\mathfrak{R}$-MACRL is developed based on Policy-Space Response Oracle (PSRO) Lanctot et al. (2017), a deep learning-based extension of the classic Double Oracle algorithm McMahan et al. (2003). The workflow of $\mathfrak{R}$-MACRL is depicted in Fig. 3. At each iteration, $\mathfrak{R}$-MACRL keeps a population (set) of policies $\Pi^{t}\subset\Pi$, e.g., $\Pi^{t}_{\zeta}=(\pi_{11},\pi_{12})$ and $\Pi^{t}_{\xi}=(\pi_{21},\pi_{22})$. We can evaluate the utility table $U(\Pi^{t})$ for the current iteration and calculate a Nash equilibrium $\pi^{t}_{*}=\langle\Delta(\Pi^{t}_{\xi}),\Delta(\Pi^{t}_{\zeta})\rangle$ for the game restricted to policies in $\Pi^{t}$ by, for example, linear programming, replicator dynamics, etc. $\Delta$ denotes the meta-strategy which is an arbitrary categorical distribution. Next, we calculate the best response policy $\operatorname{Br}(\pi^{t}_{*,-i})$ to the NE in this restricted game for each player $i$ (player $-i$ denotes the opponent of player $i$, $i\in\{\xi,\zeta\}$), e.g., $\pi_{13}=\operatorname{Br}(\pi^{t}_{*,\xi})$ and $\pi_{23}=\operatorname{Br}(\pi^{t}_{*,\zeta})$. We extend the population by adding the best response policies to the policy set: $\Pi^{t+1}_{i}=\Pi^{t}_{i}\cup\operatorname{Br}(\pi^{t}_{*,-i})$ for $i\in\{\xi,\zeta\}$. After extending the population, we complete the utility table $U(\Pi^{t+1})$ and perform the next iteration. The algorithm converges if the best response policies are already in the population. Practically, $\mathfrak{R}$-MACRL approximates the utility function $U(\cdot)$ by having each policy in the population $\Pi^{t}_{i}$ playing with each other policy in $\Pi^{t}_{-i}$ and tracking the average utilities. The approximation of the best response policies is performed by maximizing $\mathcal{J}_{\xi}(\theta_{\mu}|\pi^{t}_{*,\zeta})$ and $\mathcal{J}_{\zeta}(\theta_{d},\theta_{r}|\pi^{t}_{*,\xi})$ for the attacker and the defender, where the full expressions of the two objectives are described in Eq. 1 and Eq. 2, respectively.

The overall algorithm of $\mathfrak{R}$-MACRL is presented in Algorithm 1. We first initialize the meta-game and the mixed strategies (line 1 and line 1). Then, at each step, we train the attacker and the defender alternately by letting them best respond to their corresponding opponent (line 1). Next, the learned new policy $\pi^{t+1}_{i}$ is added to the policy set $\Pi^{t+1}_{i}$ for the two players respectively (line 1). After extending the policy set, we can check the convergence (line 1) and calculate the missing entries in $U(\Pi^{t+1})$ (line 1). Finally, we solve the new meta-game (line 1) and repeat the iteration.

MACRL methods are commonly categorized by whether they are implicit or explicit Oliehoek et al. (2016); Ahilan and Dayan (2021). In implicit communication, the actions of agents influence the observations of the other agents. Whereas in explicit communication, agents have a separate set of communication actions and exchange information via communication actions. In this paper, we focus on explicit communication because in implicit communication, to carry out an attack, the attacker’s behaviour is often bizarre, making the attack trivial and easily detectable. We consider the following three realistic types of explicit communication:

• •

  Communication with delay (CD): Communication in real world is usually not real-time. We can model this by assuming that it takes one or a few time steps for the messages being received by the targeted agents Sukhbaatar et al. (2016).

• •

  Local communication (LC): Messages sometimes cannot be broadcast to all agents due to communication distance limitations or privacy concerns. Therefore, agents need to learn to communicate locally, affecting only those agents within the same communication group Das et al. (2019); Böhmer et al. (2020).

• •

  Communication with cost or limited bandwidth (CC): Agents should avoid sending redundant messages because communication in real world is costly and communication channels often have a limited bandwidth Wang et al. (2019); Zhang et al. (2020b).

Following the above taxonomy, we select some representative state-of-the-art algorithms to perform evaluation²²2Sweeping the whole list of algorithms for each category is impossible and unnecessary since there have been a lot of algorithms proposed and algorithms in each category usually share common characteristics.. As in Table 1, we select CommNet Sukhbaatar et al. (2016), TarMAC Das et al. (2019) and NDQ Wang et al. (2019) for CD, LC and CC respectively. A brief introduction to each of the chosen algorithms is provided in Appendix A. We evaluate in the following environments, which are similar to those in the paper that first introduced the algorithms:

For each of the tasks, we first train the chosen MACRL methods to obtain the action policy and the message policy for each agent. After that, we randomly select an agent to be malicious and train its adversarial policy to examine whether MACRL methods are vulnerable to message attacks. Then we perform defence by training the message filter, during which the adversarial policy of the malicious agent is fixed but keeps working. To show that a single message filter is brittle and can be easily exploited if the attacker adapts to it, we freeze the learned message filter and retrain the adversarial policy. Finally, we integrate the message filter into the framework of $\mathfrak{R}$-MACRL and justify if $\mathfrak{R}$-MACRL is helpful to improve the robustness. All experiments are carried out with five random seeds and results are shown with a 95% confidence interval.

We first evaluate the performance of our attacking method on the three selected MACRL algorithms. Then we try to recover multi-agent coordination for the attacked algorithms by applying the message filter.

We have demonstrated that many state-of-the-art MACRL algorithms are vulnerable to message attacks, and after applying the message filter, multi-agent coordination can be recovered. In this part, we integrate the message filter into the framework of $\mathfrak{R}$-MACRL and show that the robustness of MACRL algorithms can be significantly improved with $\mathfrak{R}$-MACRL.

To examine the performance of the method in scenarios where there is more than one attacker, we conduct experiments on NDQ in two new challenge tasks: 4bane_vs_hM and $\operatorname{1o\_3r\_vs\_4r}$. In the former maps, i.e., 3bane_vs_hM and $\operatorname{1o\_2r\_vs\_4r}$, there are only three agents in the team, making multiple attackers unreasonable. To mitigate this, we create 4bane_vs_hM and $\operatorname{1o\_3r\_vs\_4r}$ based on 3bane_vs_hM and $\operatorname{1o\_2r\_vs\_4r}$ by increasing one more agent to the team. We randomly sample two agents to be malicious. According to our assumptions (agents have no knowledge about who are malicious and malicious agents cannot communicate with each other), we can directly apply the attacking method to each of the malicious agents. As shown in Fig. 7, the attackers can quickly learn effective adversarial policies with less learning steps. On the other hand, the message filter can still successfully recover multi-agent cooperation under multiple attackers, though it takes much more learning steps to converge. We further evaluate the effectiveness of $\mathfrak{R}$-MACRL on the two tasks and consistent results are observed: trained with $\mathfrak{R}$-MACRL, the agents can obtain larger expected utilities. More results on other algorithms and environments are provided in Appendix D.

We have shown that by integrating the message filter into the framework of $\mathfrak{R}$-MACRL, the robustness of MACRL algorithms can be improved. However, the performance of $\mathfrak{R}$-MACRL directly is affected by the message filter. In this part, we will take a deeper look at how the message filter works.