Learning Complex Multi-Agent Policies in Presence of an Adversary

Each agent $i\in V$ can observe it’s own state which includes it’s own position and velocity. The agent forms its own state encoding $U^{i}=f_{a}(X^{i})$ using a learnable differentiable encoder, $f_{a}$.

Each agent is also able to observe all the entities in the environment and uses a Graph Neural Network to produce a fixed size embedding $E^{i}$. Note that this embedding is independent of the number of entities present in the environment. First, an agent uses an entity encoder function $f_{e}$ to produce an entity embedding, $e^{l}_{i}=f_{e}(X^{l}_{i})$ where $X^{l}_{i}$ is the position of entity $l\in V$ with respect to agent $i$. Then the agent produces a fixed size embedding $E^{i}$ by applying dot product attention mechanism over entity embeddings. $E^{i}$ can be intuitively understood as a representation of the environment of an agent. An important characteristic of using such technique is that the produced final embedding $E^{i}$ is invariant to the number of entities present in the environment. It is also invariant to the order in which the agent observes the entities.

There can be scenarios where we have different teams of agents in the environment. In such scenarios, we also have an opponent encoder module which similarly takes in the state information of the opponent agents and produces an embedding reflecting the opponent information. Every agent uses an opponent encoder function $f_{o}$ to produce an opponent embedding $e^{o}_{i}=f_{o}(X^{o}_{i})$ where $X^{o}_{i}$ is the position of opponent $o\in V$ with respect to agent $i$. After producing an opponent encoding for all the opponents in the environment, a fixed size embedding $O^{i}$ is computed by applying dot product attention mechanisms over opponent embeddings. Similar to the environment embedding $E^{i}$, $O^{i}$ is invariant to the number of opponents in the environment and to the order in which the agent observes them.

We can have scenarios where we only have homogeneous agents operating in the environment or we can have different teams of agents in the environment. In case of homogeneous agents operating in the environment, every agent is allowed to communicate with every other agent in the environment (Figure 2). On the contrary, if we have different teams of agents in the environment then the agents are only allowed to communicate with other agents in the same team (Figure 3).

After computing its state encoding $U^{i}$, its environment encoding $E^{i}$, and an its opponent encoding $O^{i}$, an agent uses them to produce a message. It also uses them to choose how much attention it wants to pay to the messages it receives from other agents. First the agent concatenates $U^{i}$, $E^{i}$ and $O^{i}$ to produce $h^{i}$. Here, $h^{i}$ represents an agent’s understanding of its own environment.

Using $h^{i}$, Each agent produces a key $K^{i}=W_{K}h^{i}$, a value $V^{i}=W_{V}h^{i}$ and a query $Q^{i}=W_{Q}h^{i}$. It then proceeds to send the computed $V^{i}$ and $Q^{i}$ to all the other agents in the environment. It also receives $V^{j}$ and $Q^{j}$, $j\in V-\{i\}$, where $j$ is every other agent in the environment. It then uses dot product attention method to calculate the attention it needs to pay to the message of agent $j$ at every time step. This method of calculating attention and aggregating information received from other agents is described in more detail in Figure 1. After message passing, every agent updates its embedding $h^{i}$. Now each agent passes it’s hidden embedding, $h^{i}$ through another neural network which produces a distribution over the actions that the agent can take. At each time step, all the agents calculate their own action in a decentralised manner and are given a single reward for their collective set of actions. This reward is then used to train the agents using PPO [17]. One important implementation detail is that we assume that the agents in the same team share all the learnable parameters of agent state encoder network, environment state encoder network, opponent state encoder network, inter agent communication module and final policy network. This means that our work falls under the paradigm of centralised training and decentralised execution.

In the task of deception, we can have a team of N agents trying to protect high value target among N targets. The agents needs to learn to spread out to cover targets in order to confuse an observing adversary as to which of the target is the most important. There are two teams of agents in the environment:

• •

  Good Agents: They can observe all the landmarks in the environment and know which landmark is the target landmark. In our work, the good agents are collectively learning to collaborate with each other and to come up with strategies to deceive the observing adversary.

• •

  Adversary Agent: In this work, we have only presented results with one adversary agent in the environment. We have tried experiments with both learning and heuristic adversary. Basically, an adversary needs to infer the target location from the motion of the good agents. If learning, the adversary can see all the landmarks but does not know which landmark is the target landmark. If heuristic, the adversary moves towards landmark with closest good agent. In this work, results have been presented with only a heuristic adversary.

Apart form the agents in the environment, we also have landmarks as entities in the environment. The kind of landmarks in the environment are as follows:

• •

  Target Landmark: Target landmarks are the high value landmarks in the environment. The good agents in the deception environment can observe all the landmarks and know which landmark is the target landmark. Adversary agents do not know which landmarks are the target landmarks. The adversary agent needs to infer the target landmark by observing the good agents while the good agents need to come up with strategies to deceive the adversary.

• •

  Non Target Landmark : Non target landmarks are the other landmarks in the environment. Both good agents and the adversary agents can observe all the landmarks in the environment.

In this section, we describe the reward formulation which we have used for our experiments. Reward formulation in reinforcement learning should be done according to the behaviour which we want the learned agent to perform. In our case, we will describe different reward configurations and how we used them to obtain desired behaviour. The reward which we have used are based on distance and are continuous. Since the reward configuration is continuous and given at every time step, learning different behaviours becomes easier for the agents. We employed curriculum learning to make agents learn complex deceptive behaviours which is explained in more detail in the next subsection. We have described the different reward configurations used by us in more detail below:

• •

  Coverage Reward: This reward is used by the good agents to learn how to collaboratively cover all the landmarks in the environment. The agents are rewarded on the basis of the bi-partite graph distance between the graph of agents and the graph of landmarks. In other words, agents would be given a higher reward if they are successfully covering the landmarks with 1:1 matching and would be given a lower reward if they are unable to so.

• •

  Deception Reward: This is the reward which is used to actually learn deceptive behaviours. The reward given to the good agents is different than the reward given to the adversary. The good agents are rewarded on the basis of how close the adversary is to the target landmark. They are given a higher reward if the adversary is far away from target and a lower reward if it comes near the target landmark.

  The adversary’s reward configuration is exact opposite to that of the good agents. We give a higher reward to the adversary if it gets nearer to the target landmark and give it a lower reward if it’s unable to do so. Please note that this reward is only given to the adversary if it’s learning. If we use a heuristic adversary, this reward configuration is used only for good agents and the adversary is not given any reward.

We did some preliminary experiments using the deceptive reward described in the previous section. However, we noticed that the agents did not converge to any reasonable behaviour. So we propose a two step training process. We first train the good agents using the coverage reward. After they learn to cover all the landmarks with a high success rate, we gradually introduce a weighted deception reward. We observe in our experiments that the good agent assigned to the target landmark learns to stay a little away from the landmark instead of covering it in order to deceive the adversary. We performed a sensitivity analysis by varying the weights of deception and coverage and the results have been provided in the next section.

After training the good agents with the coverage reward, we train the agents with a weighted sum of deception and coverage reward. We did experiments with weights presented in Table I.

We evaluated the performance using five different metrics. These are goal selected, bipartite distance, distance threshold and distance from target landmark. These metrics and evaluation methods for good agents and the adversary agent have been explained in more detail below.

• •

  Good Agents: The following metrics have been observed and produced due to the behaviour displayed by the good agents:

  1. 1.

     Bipartite Distance: We calculate the mean bipartite distance between the good agents and the landmarks during an episode. We then calculate mean of these distances over 30 episodes. A lower mean bipartite distance would mean that the good agents are covering the targets properly.

  2. 2.

     Distance Threshold: We calculate the number of steps during an episode for which bipartite distance of good agents is within a threshold of 0.1. We then calculate mean of these steps over 30 episodes.

• •

  Adversary Agent: The following metrics have been observed and produced due to the behaviour displayed by the adversary agent:

  1. 1.

     Distance from Target: We calculate the mean of the distance between adversary and the target landmark during an episode. We then calculate mean of these distances over 30 episodes.

  2. 2.

     Distance Threshold: We calculate the number of steps during an episode for which distance of adversary from target is within a threshold distance of 0.1. We then calculate mean of these steps over 30 episodes.

We performed sensitivity analysis on 2 goods agents vs heuristic adversary and 3 good agents vs heuristic adversary. The corresponding results have been shown in Table II and Table III. We can notice that as we increase the deception reward weight in both cases, the number of times the target is selected by the adversary decreases. Also we can observe that the number of time steps for which the adversary agent comes near to the target landmark decreases with the increase in deception reward weight. All of this suggests that as we increase the weight of deception reward, the success rate of the good agents deceiving the adversary agent also increase. We also tried increasing the deception reward weight to 0.5 but in that case the good agents failed to converge to a reasonable behaviour.

One more interesting observation from the results can be that the bipartite distance between the good agents and the landmarks also increases as we increase the deception weights. This makes sense because as the deception weight increases, the good agent assigned to the target landmark in every episode learns to stay at some distance away from the target landmark. This result can be noticed visually also.

In this work, we proposed augmenting the multi-agent reinforcement learning framework proposed by [1] with an opponent encoder module for learning multi-agent policies in presence of an adversary in the environment. We performed a two step training process with different reward configuration to train a team of agents to deceive an adversary in the environment.

Only preliminary results for different reward configurations against a heuristic agent have been presented in this work. A good future direction would be to investigate other reward configurations and to perform experiments with a learning adversary. The proposed framework can also be extended to learn multi-agent policies against a team of heuristic or learning adversaries.