Title: STRUCTURAL MULTI-AGENT LEARNING

Abstract: In this paper, we propose a multi-agent learning framework to model communication in complex multi-agent systems. Most existing multi-agent reinforcement learning methods require agents to exchange information with the environment or global manager to achieve effective and efficient interaction. We model the multi-agent system with an online adaptive graph where all agents communicate with each other through the edges. We update the graph network with a relation system which takes the current graph network and the hidden variable of agents as input. Messages and rewards are shared through the graph network. Finally, we optimize the whole system via the policy gradient algorithm. Experimental results of several multi-agent systems show the efficiency of the proposed method and its strength compared to existing methods in cooperative scenarios.

1. INTRODUCTION:

Reinforcement learning (Shu & Tian, 2018) has been making significant progress in many applications, including playing video games (Mnih et al., 2013; Silver et al., 2016) , text generation (Guo; Li et al., 2016) , and robotic controls (Tedrake et al., 2004; Levine et al., 2016) . These signs of improvement in single-agent learning have enabled agents to deal with tasks in high dimensional spaces. Under this circumstance, agents can fulfill their goals by modeling the environment as a whole (Doya et al., 2002) . However, numerous applications are concerned with the interaction of multiple agents (Matignon et al., 2012; Mordatch & Abbeel, 2018; Leibo et al., 2017) . The relationships between agents are complicated as the cooperation (Peng et al., 2017; Olfati-Saber et al., 2007) and competition (Zheng et al., 2018) with each other bring uncertainty and complexity. The ideas of deep reinforcement learning have been explored for multi-agent systems (Lowe et al., 2017) . Unfortunately, conventional reinforcement learning approaches such as Q-Learning or policy gradient with independently learning agents are poorly suited to multi-agent environments (Matignon et al., 2012) .

Most existing multi-agent learning methods focus on collaboration among learning agents. In some multi-agent systems, success has been made by introducing a centralized controller (Shu & Tian, 2018; Hong et al., 2018) . When the agent number increases, researchers reduce computational complexity by approximating the average effect from the overall population or neighboring agents (Yang et al., 2018) . Others develop methods that enable agents to learn to coordinate on their own (Morcos et al., 2018; Sukhbaatar et al., 2017; Perolat et al., 2017) . These methods, however, fail to characterize systems of diverse agents as a whole and can hardly reveal the relationship between agents without any prior information. Besides such challenges, a general dilemma lies in that none of the existing algorithms deals with indefinite numbers of agents, which is a typical attribute of most dynamic systems.

In this work, we propose a general multi-agent learning structure(SMAL) to address these challenges. As shown in Figure 1 , we tackle multi-agent reinforcement learning under a setting where each agent is directly interacting with a finite set of other agents. Through a chain of direct interactions, we interconnect any pair of agents globally. Unlike the agents that only have access to local information, we update their policies by considering communications with each other. Each agent has a latent variable that stands for its role in the whole system. The hidden variables of every pair of agents model the online adaptive graph network that stores the relations.

The online graph explicitly demonstrates the connections between agents by the weights of edges and informs agents with whom they should collaborate. Edges of positive weight indicate that the

Frame t Frame t+1:

A 1

EQUATION

Figure 1 : The main framework of the proposed Structural Multi-Agent Learning. Given the states of the multi-agent system at frame t, all agents communicate with each other through the edges rather than upload messages to the environment or global manager to achieve effective and efficient interaction. Then each agent makes a decision according to the current state and received messages. Finally, we update the graph network with a relation system which takes the current graph network and the hidden variables as inputs.

two agents should work together while a negative one suggests that they are competitors. As we use a relation network to infer edges between agents, the graph is adaptive even if the agent number fluctuates. Agents can only communicate with those adjacent on the graph, and their messages are propagated to connected agents. For highly complex systems with numerous agents, we reduce the complexity of the graph network by limiting global communication and control cost. Finally, We empirically show the success of our approach compared to existing methods in various cooperative scenarios, where agents can discover optimal coordination strategies.

The main contributions of this paper are:

(1)We propose a general framework for multi-agent learning that models the relationships between agents with a graph network.

(2)The messages and rewards are shared through the graph to achieve efficient cooperation.

2. RELATED WORK:

Multi-agent reinforcement learning. Self-agent reinforcement learning algorithms have achieved significant success in several applications. However, it's difficult to adapt these methods to multiagent systems (Matignon et al., 2012) . As the environments are non-stationary, independent-learning policy gradient methods perform poorly (Lowe et al., 2017) . Under cooperative settings, a centralized critic is proved effective (Shu & Tian, 2018; Hong et al., 2018) . Other methods encourage cooperation via the sharing of policy parameters (Gupta et al., 2017) . The graph in our work is a variant of a centralized controller for the messages between agents. The difference lies in that the policies of agents are learned separately.

Communication in multi-agent systems. Reinforcement learning provides a way to study how communication emerges in multi-agent systems. Pioneering work by Jakob (Foerster et al., 2016) is considered as a first attempt at learning communication and language with deep learning approaches. Under cooperative settings, some communication architectures (Cao et al., 2018; Das et al., 2018; Kluge, 1983; Singh et al., 2018; Sukhbaatar et al., 2016) allow agents to achieve targeted and profitable communication. Several approaches (Choi et al., 2018; Lazaridou et al., 2018; Bogin et al., 2018) train agents to learn from raw pixel data and communicate through discrete symbols. Social influences can also be interpreted as a kind of communication (Jaques et al., 2019) . Other frameworks use early and curiosity-driven developments to build a unified model of speech and tool (Oudeyer & Smith, 2016; Foerster et al., 2016) . Unlike prior approaches for targeted communications, we propose a structural communication system for agents to exchange messages with their targets through a graph.

Relational forward models. Relational reasoning has received considerable attention in recent years, and researchers attempt to predict the forward dynamics of multi-agent systems with a rich relational structure (Zheng et al., 2016) . Deep learning models that operate on the graph have been developed to provide insights into the relational structures behind the data. Relational forward model (Tacchetti et al., 2018) based on graph network (Battaglia et al., 2018) embeds RFM modules inside agents and updates the graph network with supervised learning. Their model takes the state of the environment as input and outputs either an action prediction for each agent or a prediction of the cumulative reward each agent will receive. The graph in our framework can be defined as a relational forward model and is updated by policy gradient flows.

3. BACKGROUND:

Multi-agent Markov games. In this paper, we consider multi-agent partially observable Markov games (Littman, 1994) . Under multi-agent settings, a Markov game can be defined by xS, T , A, γy. Given environment state s t P S, each agent chooses an action a t P A. The actions of all agents are combined as a joint action a t " " a 0 t , . . . a N t ‰ , producting the next state s t`1 according to the transition function T ps t`1 |a t , s t q. Each agent also receives a reward rps t , a t q and the target is to maximize its accumulated expected return R i " ř T t"0 γ t r t i ps t , a t q, where γ is the discount factor and T is the time horizon. As the environment is partially observable, every agent chooses its action based on observation o t rather than s t .

Policy gradient algorithms. Policy gradient methods (Sutton et al., 2000) directly update the parameters of policies by computing the gradients of value functions. Given the objective: Jpθq " E τ "p θ pτ q rrpτ qs, where r and τ refer to rewards and trajectories, the gradient of the policiy can be written as:

∇ θ Jpθq " E τ "p θ pτ q «˜T ÿ t"1 ∇ θ log π θ pa t |s t q ¸˜T ÿ t"1 r ps t , a t q ¸ff (1)

Here π θ pa t |s t q is the policy, s t and a t are states and actions. The advantage of equation 1 is that we don't need any prior knowledge about initial distribution or environment. However, the gradient estimates are of high variance. Under multi-agent settings, an agents reward usually depends on the actions of other agents, which leads to more fluctuations in the estimation process.

Graph neural network. Graph neural networks (GNN) (Defferrard et al., 2016) extended existing neural networks for processing the data represented in graph domains. GNNs can be categorized as spectral approaches and non-spectral approaches. Non-spectral methods define convolutions directly on the graph, operating on spatially close neighbors. Spectral approaches work with a spectral representation of the graphs. The convolution operation is defined in the Fourier domain by computing the decomposition of the graph Laplacian (Zhou et al., 2018) . The operation can be defined as the multiplication of a signal x P R N (a scalar for each node) with a filter g θ " diagpθq:

EQUATION

)

where U is the matrix of eigenvectors of the normalized graph Laplacian L(Chung & Graham, 1997).

4. APPROACH:

In this section, we will detail the proposed structural multi-agent learning method. We first define the structure of a multi-agent system with the graph network and the interactions between agents.

Then we provide the optimization process of the whole framework.

4.1. STRUCTURAL MULTI-AGENT MODELING:

Given a multi-agent system tA, Gu with N agents, where A i is the i-th agent, and G " tvpA i , A j q P r´1, 1su is the graph that represents the relations between agents(Note that A and a refers to agents and actions respectively). Positive, negative and zero weight of the graph v ij " vpA i , A j q means A i , A j are cooperative, competitive and independent.

Each agent can communicate with the agents adjacent on the graph directly, and the message of itself can propagate through the edges to connected agents. Thanks to the graph neural network, the agent A i can get the encoded messengers at pt ´d `1q-th frame of neighbors whose order is d. Specifically, when d " 1, it means that agents can receive instant messages from adjacent neighbors, while messages from farther agents are propagated through frames.

4.1.1. COOPERATIVE:

First, we talk about cooperative settings. In this case, the edges of the graph v ij P r0, 1s. For a single agent A i , it takes its observation, its hidden variable and messages from other agents as inputs to generate action according to policy π. We also exploit a model f to predict its hidden variable and messages to be sent to other agents. For different agents, the dimensions of messages must be the same to communicate with each other. We have:

EQUATION

Here o t is the observation, h t is the hidden variable, m t is the message sent to other agents and a t is the action. In equation 5, m jt is the message given by agent j at time t, so m ´t is treated as a sum of reweighted messages from other agents. We omit the subscript i for clarity. For the graph G " tvpA i , A j qu, we use a relation network φ to infer the edge between each pair of agents, which is defined as follows:

G t`1 " v ij " φph it , h jt , ψpG t qq (6)

Where ψ is a graph neural network which encodes the current graph G t into vectors as the global representation of current multi-agent system.

To adjust the whole graph network needs to traverse all possible active edges of the current multiagent system, which might cost lots of computation when the multi-agent system scale is relatively large. Since the relationship between agents might not change frequently, we can update the graph network interval T frame or when the number of agents changes to reduce the cost of graph network adjustment.

4.1.2. COMPETITIVE:

Under competitive settings, the edges of the graph v ij P r´1, 1s. We can change equation 5 as follows:

EQUATION

In this way, the messages from partners are considered valuable, while messages from competitors are ignored. As competitive environments are totally different from cooperative scenarios, we mainly focus on cooperative settings in our experiments and leave further discussions of competitive settings to Appendix.

4.2. OPTIMIZATION:

Different from traditional multi-agent learning methods, we consider the actions of the single agent and the whole interaction network at the same time. The whole formulation of the proposed method contains two parts: 

Where J 1 is the individual loss and J 2 is the structural loss. We use λ to balance those two part. The individual loss J 1 is defined by the rewards of a single agent. In a multi-agent system, the purpose of each agent is to enlarge the reward of itself and its collaborators. So the policy gradient part need to consider the reward of its neighbor. We define the individual loss J 1 for every agent as following:

J 1 " ´E rπpa t |o t , h t , m ´tqpRps t , a t q `R´t qs (9)

R ´t " 1 1 `řN j‰i v ij N ÿ j‰i v ij Rps jt , a jt q (10)

Where Rps t , a t q is the reward for a single agent, and R ´t is the shared reward from adjacent agents. The structural loss J 2 " E rLpG t`1 qs of our method aims to minimize the global communication and control cost. In our method LpG t`1 q is defined as following:

LpG t`1 q " ÿ i,j I v‰0 pv ij q (11)

Where Ip¨q is the indicator function. With this loss, we can control the sparseness of the graph. In large scale systems, we want to reduce unnecessary communications between agents.

Finally, we use the stochastic sub-gradient descent algorithm to update those neural networks with learning rate ρ. Here θ refers to the parameters for policy π and predictor f of every agent.

EQUATION

)

Algorithm 1 summarizes the detailed procedure of our proposed SMAL method. 

5. EXPERIMENTS:



5.1. ENVIRONMENTS:

We conducted experiments on three multi-agent domains: Waterworld, Multi-Walker, and Multi-Ant (Gupta et al., 2017) . All the three tasks are continuous control problems with partial observation in which agents should cooperate to fulfill a certain goal. We provide details of each environment below.

Waterworld. Waterworld is a type of pursuit problem in the continuous domain. The environment is based on the single-agent Waterworld domain used by (Ho et al., 2016) . In this task, agents need to cooperate to capture moving food targets while avoiding poison targets. The agents move around by applying a two-dimensional force. They will receive a positive reward for achieving a food target and a negative reward for capturing a poisoned target. The observation and action spaces are all continuous. Figure 2a shows an example of four agents moving for food.

Multi-Walker. Multi-Walker is a control locomotion task based on the BipedalWalker environment from OpenAI gym (Brockman et al., 2016) . The environment contains multiple bipedal walkers that can actuate the joints in each of their legs. At the start of each simulation, a large package is placed on top of the walkers. The walkers must learn how to move forward and to coordinate with other agents to keep the bag balanced while navigating complex terrain. Each agent receives a positive reward for carrying the package forward, a negative reward for falling and dropping the package. Figure 2b shows the scene of four walkers.

Multi-Ant. The multi-ant domain is a 3D locomotion task based on the robot models in (Schulman et al., 2015b) . In this domain, each leg of the ant is a separate agent. Legs can sense their positions and velocities as well as those of their neighbors. Each leg is controlled by applying torque to its two joints. The legs should cooperate with neighbors to help the ant move forward as quickly as possible. The robot in Figure 2c is an ant with ten legs.

5.2. RESULTS AND ANALYSIS:

Comparison with state-of-the-art methods. For comparison, we choose four baselines: Multi-agent Deep Deterministic Policy Gradient(MADDPG) (Lowe et al., 2017) , Centralized MADDPG(C-MADDPG), Individualized Controlled Continuous Communication Model(IC3Net) (Singh et al., 2018) and Trust Region Policy Optimization(TRPO) (Schulman et al., 2015a) to compare with our method: Structural Multi-agent learning(SMAL). Among them, MAD-DPG learns coordinated behavior via centralized critics and uncentralized executors, while Centralized MADDPG exploits joint observation and action to train a centralized critic and a centralized actor. IC3Net is an efficient method that learns profitable communication by controlling continuous communication with a gating mechanism. TRPO is an effective single-agent reinforcement learning methods. We list the details for the implementation and comparison in the Appendix.

We plot the learning curves for various approaches in Figure 3 . The curves show that our method (SMAL) can reach high rewards in early episodes and the optimal policies perform better than the We observed that the agents trained by our method tend to keep close with other agents near them more frequently. In the Multi-Walker domain, the walkers learn to carry the package forward without letting it fall by the messages from the other three walkers. In the Multi-ant case, the legs learn to avoid collision with each other. The histogram in Figure 4 is the normalized agent reward(divided by the return of SMAL) in all three domains, which shows that our method can be generalized to these systems. Our method surpasses MADDPG in all three environments, indicating that the graph network is a better supervisor than the centralized critic. Also, out method outperforms IC3Net, which focuses on efficient communication and doesn't include a reward sharing mechanism. Compared to Centralized MADDPG, which trains the whole system jointly and optimizes the total reward directly, our method achieves a near-optimal result.

Ablation studies. To verify the effectiveness of sharing messages and rewards in our method, we create two baselines that only allow agents to share either messages or rewards. To clarify how messages and shared rewards help with the collaboration between agents, we evaluate their effectiveness in the three domains. Trade-off between communication costs and Performance. To investigate the loss defined in equation 8(J " J 1 `λJ 2 ), we alter the parameter λ to adjust the sparseness of the graph. When λ " 0, the graph learned by SMAL is fully connected regardless of the communication cost. When we increase λ, we limit the communication between agents. All the experiments above are carried out with λ " 0 to achieve complete cooperation.

Figure 5 reveals the relationship between communication costs and agents' performance. When communication is limited, agents that should be collaborators are forced to be independent. Losing potential opportunities for cooperation leads to less total rewards. How to achieve best cooperation with limited communication is an interesting problem for future work.

Effect of the graph. To further analyze the effect of the graph in our SMAL method, we visualize how graph changes in a certain episode. We use λ " 1 to ensure some agents are independent. Figure 6 demonstrates the transformation of the graph inferred during one episode on Waterworld with four agents. Wider edges in the plot refer to larger weights of messages between the agents. If there's no edge between two vertices, the edge inferred is zero. The above row shows the real situation of agents in Waterworld. We examine the case in the middle of Figure 6 . As agent 1 and 4 are around agent 2, they are more likely to cooperate to capture the food targets. In contrary, agent 3 is far away from other agents, so it keeps a distant connection.

The graph we infer is consistent with this situation as the edges between agent 1,2,4 are wider, while the edges between agent 3 and other agents are narrower. The experimental results point out that introducing a graph network to manage the message flows and share rewards leads to better cooperation. Quantitive improvements contributed to the graph are shown in table 2. In the second experiment, all the weights in the graph are set as one. Agents directly receive the messages from other agents and take their mean vector as the input message. With the graph to model the proportion of messages and rewards, the agents choose their actions more intelligently.

6. CONCLUSIONS AND FUTURE WORK:

In this paper, we have proposed a structural multi-agent learning framework. We tackle multiagent reinforcement learning under a setting where each agent is directly interacting with a finite set of other agents. Through a chain of direct interactions, any pair of agents are interconnected globally. The messages and rewards are shared through the global graph. Experimental results on several multi-agent systems show the efficiency of the proposed method and its strength compared to existing methods in cooperative scenarios. We also show that messages and rewards are both necessary for collaboration.

For competitive settings, agents should learn to generate unique messages to inform their partners or cheat their opponents. Also, when the agent number dynamically changes, the initialization or removal of agents remains investigation. For many-agent systems, the stability and computational complexity should be taken into consideration. We leave these investigations to future work. How to apply the proposed method to real group analysis, like multi-object tracking, group action recognition, and autonomous driving, is an exciting future research direction.

:



Figures and Tables:

Figure 2: Illustrations of the experimental environment and continuous tasks we consider. Agent numbers of the three environments above are respectively 4, 4 and 10.

Figure 3: Total agent rewards on Waterworld Figure 4: Comparison of normalized agent score

Figure 5: Trade-off between communication costs and performance, the number of edges decreases when λ increases. We choose ten values of λ for every environment.

Figure 6: Graph inference

Algorithm 1: SMAL Input: Training environment E, parameters: λ, T , learning rate ρ, total iterative number Γ, and convergence error ε. Output: Parameters: θ, ψ, φ.

Table content: <table><tr><td>Initialize θ, ψ, φ;</td></tr><tr><td>for t " 1, 2, ¨¨¨, Γ do</td></tr><tr><td>for Every agent A i do</td></tr><tr><td>Receive observations o t from E;</td></tr><tr><td>Generate message m t and send it to its neighbor;</td></tr><tr><td>Receive messages m ´t from its neighbor;</td></tr><tr><td>Generate action a t ;</td></tr><tr><td>Interactive with E according to a t and obtain o t`1 ;</td></tr><tr><td>end</td></tr><tr><td>if MOD(t,T)= 0 then</td></tr><tr><td>for A i , A j P S do</td></tr><tr><td>Calculate v ij according to (6);</td></tr><tr><td>end</td></tr><tr><td>Update current graph G;</td></tr><tr><td>end</td></tr><tr><td>Compute J t using (8);</td></tr><tr><td>if t ě 1 and |J t ´Jt´1 | ă ε then</td></tr><tr><td>go to Return.</td></tr><tr><td>end</td></tr><tr><td>Update θ, ψ, φ according to (12);</td></tr><tr><td>end</td></tr><tr><td>Return: θ, ψ, φ.</td></tr></table>

Ablation studies for messages and shared rewardsTable1shows how shared messages and rewards lead agents to cooperate with others. The model with only messages is made by removing the second term of equation 10. Meanwhile, the model that only shares rewards is by setting messages as zero. When agents aren't allowed to share messages and rewards, SMAL degenerates to a self-agent reinforcement learning method. The results demonstrate that the transmission of signals and rewards are both necessary for agents to achieve thorough consociation. These results further show that if rewards of other agents are taken into consideration, policy gradient methods can learn suboptimal policies for overall returns.

Table content: <table><tr><td>Method</td><td colspan="3">Environments(Total Rewards)</td></tr><tr><td colspan="4">Shared Messages Shared Rewards Waterworld Multi-walker Multi-ant</td></tr><tr><td colspan="2">ˆˆ472.33</td><td>30.64</td><td>67.29</td></tr><tr><td/><td>ˆ660.10</td><td>52.82</td><td>106.21</td></tr><tr><td>ˆ</td><td>625.59</td><td>48.76</td><td>90.80</td></tr><tr><td/><td>812.45</td><td>70.68</td><td>126.11</td></tr></table>

Ablation study of graph

Table content: <table><tr><td>Method</td><td/><td>Total Reward(λ " 0)</td><td/></tr><tr><td colspan="4">Environment Waterworld Multi-walker Multi-ant</td></tr><tr><td>Graph</td><td>812.45</td><td>70.68</td><td>126.11</td></tr><tr><td>Mean</td><td>636.92</td><td>59.34</td><td>115.70</td></tr></table>

Peer review (iclr2020):
This paper proposes a new way to perform multi-agent reinforcement learning via using a graph neural network like method to pass messages from agents. They show performance improvements over baseline techniques such as TRPO, DDPG, and also multi-agent algorithm MADDPG. The problem is very interesting and I do like the experimental domains such as multi-walker. However, the experimental results lack comparison against a simple baseline and it is unclear how the proposed SMAL algorithm would perform against basic multi-agent RL techniques. There are also various inaccurate or debatable claims in the paper. In the first paragraph, the authors state that single-agent RL learns to fulfill goals without modeling the behaviors of others. This is clearly not the case as the most basic model-free approaches such as DQN agents may indeed learn to model other’s behaviors inside their policy networks. A basic centralized multi-agent system would have action spaces N times A where A is the action space of a single agent. Learning would take observations from all agents and act jointly and in a coordinated manner (both centralized actor and centralized critic). This system however is not scalable to a large number of agents. However, it is still a good baseline to compare against. For example. How would a centralized multi-agent DDPG system work on multi-walker? e.g. with dimensions 4*24 ? I think it would be surprising if SMAL would be better than this baseline, what are authors thoughts/views on this? First paragraph of page 2 suggest that SMAL is able to learn +ve and -ve weights to suggest whether an agents are collaborators or competitors. However, from sections 4.1.1 and 4.1.2, it appears that those bounds on v_ij are actually set by hand. Positive/negatives weights on an edge is hardly a good indicator of collaboration/competition. I do not see a relationship between the two. Typically, collaboration or competition arise out of the reward function, e.g. whether it is a zero-sum game or a general-sum game. In addition, the claim in 4.1.2 that it is ok to zero-out messages from ‘competitors’ are dubious. Why would it not be beneficial to infer additional information from messages of other adversarial agents?