{'fraction_non_alphanumeric': 0.030969862101957197, 'fraction_numerical': 0.011377108508912414, 'mean_word_length': 4.843461351482742, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Learning Multi-Agent Coordination through Connectivity-driven Communication

In artificial multi-agent systems, the ability to learn collaborative policies is predicated upon the agents' communication skills: they must be able to encode the information received from the environment and learn how to share it with other agents as required by the task at hand. We present a deep reinforcement learning approach, Connectivity Driven Communication (CDC), that facilitates the emergence of multi-agent collaborative behaviour only through experience. The agents are modelled as nodes of a weighted graph whose state-dependent edges encode pair-wise messages that can be exchanged. We introduce a graph-dependent attention mechanisms that controls how the agents' incoming messages are weighted. This mechanism takes into full account the current state of the system as represented by the graph, and builds upon a diffusion process that captures how the information flows on the graph. The graph topology is not assumed to be known a priori, but depends dynamically on the agents' observations, and is learnt concurrently with the attention mechanism and policy in an end-to-end fashion. Our empirical results show that CDC is able to learn effective collaborative policies and can over-perform competing learning algorithms on cooperative navigation tasks.


Introduction
In reinforcement learning (RL), an agent learns to take sequential decisions by mapping its observations of the world to actions using a reward as feedback signal [1]. In the last few years, deep artificial neural networks [2,3] have been leveraged to improve the learning ability of RL algorithms in a number of ways, e.g. as policy function approximators to map observations to actions and to learn informative data representations. The resulting deep reinforcement learning algorithms (DRL) have recently achieved unprecedented performance in single-agent tasks, e.g. in playing Go [4] and Atari games [5,6].
Multi-agent reinforcement learning (MARL) extends RL to problems characterized by the interplay of multiple agents operating in a shared environment. This is a scenario that is typical of many real-world applications including robot navigation [7], autonomous vehicles coordination [8], traffic management [9], and supply chain management [10]. Compared to single-agent systems, MARL presents additional layers of complexity. When multiple learners interact with each other, the environment becomes highly non-stationary from the point of view of each individual actor [11]. Moreover, credit assignment [12], which is the ability to determine how the actions of each individual agent impact on the overall system performance, becomes particularly difficult [13][14][15].
We are interested in systems involving agents that autonomously learn how to collaborate in order to achieve a shared outcome. When multiple agents are expected to develop a cooperative behaviour, an important need emerges: an adequate communication protocol must be established to support the level of coordination that is necessary to solve the task. The fact that communication plays a critical role in achieving synchronization in multi-agent systems has been extensively documented [16][17][18][19][20][21][22][23]. Building upon this evidence, a number of multi-agent DRL algorithms (MADRL) have been developed lately which try to facilitate the spontaneous emergence of communication strategies during training. In particular, significant efforts have gone into the development of attention mechanisms for filtering out irrelevant information [24][25][26][27][28][29][30] (see also Section 4).
In this paper we introduce a MADRL algorithm for cooperative multiagent tasks. Our approach relies on learning a state-dependent communication graph whose topology controls what information should be exchanged within the system and how this information should be distributed across agents. As such, the communication graph plays a dual role. First, it represents how every pair of agents jointly encodes their observations to form local messages to be shared with others. Secondly, it controls a mechanism by which local messages are propagated through the network to form agent-specific information content that is ultimately used to make decisions. As we will demonstrate, this approach supports the emergence of a collaborative decision making policy. The core idea we intend to exploit is that, given any particular state of the environment, the graph topology should be self-adapting to support the most efficient information flow. This raises the question: how should efficiency be measured?
Our proposed approach, connectivity-driven communication (CDC), is inspired by the process of heat transference in a graph, and specifically the heat kernel (HK). The HK describes the effect of applying a heat source to a network and observing the diffusion process over time. As such, it can be used to characterise the way in which the information flows across nodes. The HK has been used in a number of different application domains where there is a need to characterise the topology of graph, e.g. in 3D object recognition [31] and neuroimaging [32,33]. Various metrics obtained from the HK have been used to organise the intrinsic geometry of a network over multiple-scales by capturing local and global shapes' in relation to a node via a time parameter. The HK also incorporates a concept of node influence as measured by heat propagation in a network, which can be exploited to characterise how efficiently the information propagates between any pair of nodes. To the best of our knowledge, this is the first time that the HK has been used to develop an end-to-end learnable attention mechanism enabling multi-agent cooperation.
Our approach relies on an actor-critic paradigm [34][35][36] and is intended to extend the centralized-learning with decentralized-execution (CLDE) framework [20,37]. In CDC, all the observations from each agent are assumed known only during the training phase whilst during execution each agent makes autonomous decisions using only their own information. The entire model is learned end-to-end supported by the fact that the heat-kernel is a differentiable operator allowing the gradients to flow throughout the architecture. The performance of CDC has been evaluated against alternative methods on four cooperative navigation tasks. Our experimental evidence demonstrates that CDC is capable of outperforming other relevant state-of-the-art algorithms. In addition, we analyse the communication patterns discovered by the agents to illustrate how interpretable topological structures can emerge in different scenarios.
The structure of this work is as follows. In Section 2 we discuss related state-of-the-art MADRL methods focusing on cooperating systems with communication mechanisms. In Section 3 we provide the details of the proposed CDC algorithm. Experimental results are then provided in Section 4. Finally, in Section 5, we discuss the benefits and potential limitations of the proposed methodology with a view on further improvements in future work.

Related Work
Multi-agent systems have been widely studied in a number of different domains, such as machine learning [38], game theory [39] and distributed systems [40]. Recent advances in deep reinforcement learning have allowed multi-agent systems capable of autonomous decision-making [41][42][43] improving tabular-based solutions [44]. In this section, we briefly review recent developments in MADRL with a focus on communication strategies that have been proposed to improve cooperation.

Centralised learning with decentralised execution
When multiple learners interact with each other, the environment becomes non-stationary from the perspective of individual agents which results in increased training instability [45,46]. An approach that has proved particularly effective consists of training the agents assuming centralised access to the entire system's information whilst executing the policies in a decentralised manner (CLDE) [20,23,29,37,47,48]. During training, a critic module has access to information related to other agents, i.e. their actions and observations. MADDPG [37], for example, extends DDPG [35] in this fashion: each agent has a centralised critic providing feedback to the actors, which decide what actions to take. A variant of this approach has recently been proposed to deal with partially observable environments through the use of recurrent neural networks [49,50]. In [48], a centralised critic is used to estimate the Q-function whilst decentralised actors optimise the agents' policies. In [51], an action-value critic network coordinates decentralised policy networks for a fleet management problem.

Communication methods
Communication has always played a crucial role in facilitating synchronization and coordination [52][53][54][55][56]. Some of the recent MADRL approaches facilitate the emergence of novel communication protocols through communication mechanisms. For example, in CommNet [21], the hidden states of an agent' neural network are first averaged and then used jointly with the agent's own observations to decide what action to take. Similarly, in [57], communication is enabled by connecting agents' policies through a bidirectional recurrent neural network that can produce higher-level information to be shared. In IC3Net [22], a gating mechanism decides whether to allow or block access to other agents' hidden states.
Other approaches have introduced explicit communication mechanisms that can be learnt from experience. For instance, in RIAL [20], each agent learns a simple encoding that is transferred over a differentiable channel and allows the gradient of the Q-function to flow; this enables an agent's feedback to take into account the exchanged information. In our previous work, [23], the agents are equipped with a memory device allowing them to write and read signals to be shared within the system. The communication mechanism we propose in this paper is also explicit; messages are signals that must be shared within the system in order to maximize the shared rewards and serve no other purpose.

Attention mechanisms to support communication
In a collaborative decision making context, attention mechanisms are used to selectively identify relevant information coming from the environment and other agents that should be prioritised to infer better policies. For example, in [24], the agents first encode their observations to produce messages; then an attention unit, implemented as a recurrent neural network (RNN), probabilistically controls which incoming messages are used as inputs for the action selection network. The CommNet algorithm [21] has been extended using a multi-agent predictive modeling approach [27] which captures the locality of interactions and improves performance by determining which agents will share information. In the IS algorithm [58] the agents predict their future trajectories, and these predictions are utilised by an attention mechanism module to compose a message determining the next actions to take. The TarMac algorithm [28] instead leverages the signature-based attention model originally proposed in [59]. Here, each agent receives the messages broadcasted by others and produces a query that helps select what information to keep and what to discard. The latter approach is closely related to the work proposed in this paper; ours agents also aggregate information coming from different sources in order to maximise their final reward.

Diffusion processes on graphs
Spectral graph theory allows to relate the properties of a graph to its spectrum by analysing its associated eigenvectors and eigenvalues [60][61][62]. The heat kernel falls in this category; it is a powerful and well-studied operator allowing to study certain properties of a graph by solving the heat diffusion equation. The HK is determined by exponentiating the graph's Laplacian eigensystem [63] over time. The resulting features can be used to study the graph's topology and have been utilised across different applications whereby graphs are naturally occurring data structures; e.g. the HK has been used for community detection [64], data manifold extraction [65], network classification [33] and image smoothing [31] amongst others. In recent work, the HK has been adopted to extend graph convolutional networks [66] and define edge structures supporting convolutional operators [67]. In this work, we use the HK to characterise the state-dependent topology of a multi-agent communication network and learn how the information should flow within the network.

Graph-based communication mechanisms
Graph structures provides a natural framework for modelling interactions in RL domains [68][69][70]. Lately, Graph Neural Networks (GNNs) have also been adopted to learn useful graph representations in cooperative multi-agent systems [71][72][73][74][75]. For example, graphs have been used to model spatio-temporal dependencies within episodes for traffic light control [76], and to infer a multi-agent connectivity structure which, once processed by a GNN, generates the features required to decide what action to take [77][78][79]. Heterogeneous graph attention networks [80] have been introduced to learn efficient and diverse communication models for coordinating heterogeneous agents. Graph convolutional networks capturing multi-agent interactions have also been combined with a counterfactual policy gradient algorithm to deal with the credit assignment problem [81].
GNNs have also supported the development of multi-stage attention mechanisms. For instance, [26] describe a two-stage approach whereby multi-agent interactions are first determined, and their importance is then estimated to generate actions. In GraphComm [82], the agents share their encoded observations over a multi-step communication process; at each step a GNN processes a graph and generates signals for the subsequent communication round. This multi-round process is designed to increase the length of the communication mechanism and favour a longer range exchange of information. The MAGIC algorithm [83] consists of a scheduled learning when to communicate and whom to address messages to, and a message processor to process communication signals; both components have been implemented using GNNs and the entire architecture is learned end-to-end. In our proposed model, the attention mechanism depends on how the encoded information exchanged amongst the agents flows within the graph; the graph topology itself depends on the encoded observations and the heat kernel is used as a topology-dependent feature to control the agent's communication. The process of encoding the observations, inferring the graph topology, and learning the attention mechanism are all coupled with the aim to learn an optimal policy.

Problem setting
We consider Markov Games, partially observable extension of Markov decision processes [84] involving N interacting agents. We use S to denote the set of environmental states; O i and A i indicate the sets of all possible observations and actions for the i th agent, with i ∈ 1, . . . N , respectively. The agent-specific (private) observations at time t are denoted by o t i ∈ O i , and each action a t i ∈ A i is deterministically determined by a mapping, µ θi : O i → A i , which is parametrised by θ i . A transition function T : S × A 1 × A 2 × · · · × A N describes the stochastic behaviour of the environment. Each agent receives a reward, defined as a function of states and actions r i : S × A 1 × A 2 × · · · × A N → R and learns a policy that maximises the expected discounted future rewards over a period of T time steps, is the discounted sum of future rewards, where γ ∈ [0, 1] is the discount factor.

Learning the dynamic communication graph
We model each agent as the node of a time-depending, undirected (and unknown) weighted graph, G t = (V, S t ), where V is a set of N nodes and S t is an N × N matrix of edge weights. Each S t (u, v) = S t (v, u) = s t u,v quantifies the degree of communication or connectivity strength between a given pair of agents, u and v. Specifically, we assume that each s t u,v ∈ [0, 1] with values close to 1 indicating strong connectivities, and to 0 a lack of connectivity.
In our formulation, each s t u,v is not known a priori. Instead, each one of these connectivities is assumed to be a time-dependent parameter that varies as a function of the current state of the environment. This is done through the following two-step process. First, given a pair of agents, u and v, their private observations at time-step t are encoded to form a local message, where ϕ θ c is a non-linear mapping modelled as a neural network with parameter θ c . Each local message is then encoded non-linearly to produce the corresponding connectivity weight, where ϕ θ s is a neural network parameterised by θ s and σ is the sigmoid function.

Learning a time-dependent attention mechanism
Once the time-dependent connectivities in Eq. 2 are estimated, the communication graph G t is fully specified. Given this graph, our aim is to characterise the relative contribution of each node to the overall flow of information over the entire network, and let these contributions define a attention mechanism controlling what messages are being exchanged. The resulting attention mechanism should be differentiable with respect to the network parameters to ensure that, during backpropagation, all the gradients correctly flow throughout the architecture to enable end-to-end training.
Our observation is that a diffusion process over graphs can be deployed to quantify how the information flows across all agents for any given communication graph, G t . The information flowing process is conceptualised as the amount of energy that propagates throughout the network [85]. Specifically, we deploy the heat diffusion process: we mimic the process of applying a source of heat over a network and observe how it varies as a function of time. In our context, the heat transfer patterns reflect how efficiently the information propagates at time t.
First, we introduce a diagonal matrix D(u) of dimension N × N with diagonal elements given by Each such element provides a measure of strength of node u. The Laplacian of the communication graph G is given by and its normalised version is defined aŝ The differential equation describing the heat diffusion process over time p [60,86] is defined as where H(p) is the fundamental solution representing the energy flowing through the network at time p. To avoid confusion, the environment time-step is denoted by t whilst p indicates the time variable related to the diffusion process. For each pair of nodes u and v, the corresponding heat kernel entry is given by where H(p) u,v quantifies the amount of heat that started in u and reached v at time p, φ i represents the i th eigenvector, φ = (φ 1 , . . . , φ N ) is a matrix with the corresponding eigenvectors as columns and Λ = diag(λ 1 , . . . , λ V ) is a diagonal matrix formed by the eigenvalues of S ordered by increasing magnitude.
In practice, Eq. (4) is approximated using Padé approximant [87], A useful property of H(p) is that it is differentiable with respect to neural network parameters that define the Laplacian. This allows us to train an architecture where all the relevant quantities are estimated end-to-end via backpropagation. Additional details are provided in Section 3.4.
We leverage this information to develop an attention mechanism that identifies the most important messages within the system, given the current graph topology. First, for every pair of nodes, we identify the critical time pointp at which the heat transfer drops by a pre-determined percentage δ and becomes stable, i.e. for each pair of u and v, we identify that critical valuep(u, v) such that In practice, the search of these critical values is carried out over a uniform grid of points. Once these critical time points are identified, we use them to evaluate the HK values, and arrange them into an N × N matrix, which is used to define a multi-agent message-passing mechanism. Specifically, the final information content (or message) for an agent u is determined by a linear combination of the local messages received from all other agents, where the HK values are used to weight the importance of the incoming messages. Finally, the agent's action depends deterministically by its message, where ϕ θ p u is a neural network with parameters θ p u . A lack of communication between a pair of agents results when no stable HK values can be found. In such cases, for a pair of agents (u, v), the corresponding entry in H t u,v will be zero hence no value ofp(u, v) satisfies Eq. 5.

Heat kernel: additional details and an illustration
The heat kernel is a technique from spectral geometry [63], and is a fundamental solution of the heat equation: Given a graph G defined on n vertices, the normalized LaplacianL, acting on functions with Neumann boundary conditions [88], is associated with the rate of heat dissipation.L can be written aŝ where I i is the projection onto the i th eigenfunction φ i . For a given time p ≥ 0, the heat kernel H(p) is defined as a n × n matrix: Eq. 9 represents an analytical solution to Eq. 8. Furthermore, the heat kernel H(t) for a graph G with eigenfunctions θ i satisfies The proof follows from the fact that In this work the heat kernel is used to introduce a mechanism for the selection of important edges in a network to support communication between nodes. In this context, the importance of an edge is determined by both its weight and the role it plays to allow agents to exchange information correctly in the network structure. Figure 2 illustrates the advantages of selecting edges through the heat kernel features over a naive thresholding approach. The heat diffusion considers the edge weights as well as their relevance within the graph structure, e.g. edge connecting two communities.
An illustration of two edge selection methods. Starting from graph (a), we want to remove the less relevant edges. The relevance of an edge is measured considering both its weight and structural role in allowing information to pass through the network. The edge connecting nodes 0 and 5, despite its relatively low weight (0.3), has an important structural role as it serves as bridge connecting two communities hence allowing the information to propagate throughout the entire network. In (b), removing edges with smaller weights (e.g. all those falling below the 40th percentile of the edge weight distribution) results in the loss of the bridge. In (c), edges are selected based on the heat kernel weights, which recognise the importance of the bridge.

Reinforcement learning algorithm
In this section, we describe how the reinforcement learning algorithm is trained in an end-to-end fashion. We extend the actor-critic framework [34] in which an actor produces actions and a critic provides feedback on the actors' moves. In our architecture, multiple actors, one per each agent, receive feedback from a single, centralised critic.
In the standard DDPG algorithm [35,36], the actor µ θ : O → A and the critic Q µ θ : O × A → R are parametrised by neural networks with the aim to maximize the expected return, where θ is the set of parameters that characterise the return. The gradient ∇ θ J(θ) required to update the parameter vector θ is calculated as follows, whilst Q µ θ is obtained by minimizing the following loss, Here, Q µ θ is a target critic whose parameters are only periodically updated with the parameters of Q µ θ , which is utilised to stabilize the training. Our developments follow the CLDE paradigm [20,37,47]. The critics are employed during learning, but otherwise only the actor and communication modules are used at test time. At training time, a centralised critic uses the observations and actions of all the agents to produce the Q values. In order to make the critic unique for all the agents and keep the number of parameters constant, we approximate our Q function with a recurrent neural network (RNN). We treat the observation/action pairs as a sequence, where z t i and z t i−1 are the hidden state produced for the i th and i − 1 th agent, respectively. Upon all the observation and action pairs from all the N agents are available, we use the last hidden state z t N to produce the Q-value: where ϕ is a neural network with parameters θ Q . The parameters of the i th agent are adjusted to maximize the objective function J(θ i ) = E[R i ] following the direction of the gradient J(θ i ), where x = (o t 1 , . . . , o t N , a t 1 , . . . , a t N ) and Q minimizes the temporal difference error, i.e.
The differentiability of the heat kernel operator allows the gradient in Eq. (11) to be evaluated. Since the actions are modelled by a neural network parametrised θ u in Eq. (7), we have that and from Eq.(6) the gradient is whilst the gradients of the HK values are which is a composition of differentiable operations. Algorithm 1 summarises the learning algorithm; the proposed architecture is presented in Figure 1.

Environments
The performance of CDC has been assessed in four different environments. Three of them are commonly used swarm robotic benchmarks: Navigation Control, Formation Control and Line Control [89][90][91]. A fourth one, Pack Control, has been added to study a more challenging task. All the environments have been tested using the Multi-Agent Particle Environment [37,92], which allows agents to move around in two-dimensional spaces with discretised action spaces. In Navigation Control there are N agents and N fixed landmarks. The agents must move closer to all landmarks whilst avoiding collisions. Landmarks Algorithm 1 CDC 1: Inizialise actor (µ θ1 , . . . , µ θ N ) and critic networks (Q θ1 , . . . , Q θ N ) 2: Inizialise actor target networks (µ θ1 , . . . , µ θ N ) and critic target networks (Q θ1 , . . . , Q θ N ) 3: Inizialise replay buffer D 4: for episode = 1 to E do for t = 1 to T do 7: Generate C t (Eq. 1) and S t (Eq. 2) 8: for p = 1 to P do where y = r i + γQ(o , a )| a k =µ θ k (m k ) 25: in which m k is global message computed using target networks 26: Update actor according to the policy gradient: are not assigned to particular agents, and the agents are rewarded for minimizing the distances between their positions and the landmarks' positions. Each agent can observe the position of all the landmarks and other agents. In Formation Control there are N agents and only one landmark. In this scenario, the agents must navigate in order to form a polygonal geometric shape, whose shape is defined by the N agents, and centred around the landmark. The agents' objective is to minimize the distances between their locations and the positions required to form the expected shape. Each agent can observe the landmark only. Line Control is very similar to Formation Control with the difference that the agents must navigate in order to position themselves along the straight line connecting the two landmarks. Finally in Dynamic Pack Control there are N agents, of which two are leaders and N − 2 are members, and one landmark. The objective of this task is to simulate a pack behaviour, where agents have to navigate to reach the landmark. Once a landmark is occupied, it moves to a different location. The landmark location is accessible only to the leaders, while the members are blind, i.e. they can only see their current location. Typical agent configurations arising from each environment we use here are reported in Figure 3. For each environment we have tested two versions with different number of agents: a basic one focusing on solving the designed task when 3 − 4 agents are involved, and a scalable one to show the ability to succeed with 8 − 10 agents. The performance of competing MADRL algorithms has been assessed using a number of metrics: the reward, which quantifies how well a task has been solved (the higher the better); the distance, which indicates the amount of navigation carried out by the agents to solve the task (the lower the better); the number of collisions, which shows the ability to avoid collisions (the lower the better); the time required to solve the task (the lower the better); the success rate, defined as the number of times an algorithm has solved a task over the total number of attempts; and caught targets, which refers to the number of landmarks that the pack managed to reach. Illustrative videos showing CDC in action on the above environments can be found online 1 .

Implementation details and experimental setup
For our experiments, we use neural networks with two hidden layers (64 each) to implement the graph generation modules (Eq. 2, 1) and the action selector in Eq. 7. The RNN described in Equation 10 is implemented as a long-short term memory (LSTM) network [93] with 64 units for the hidden state.
We use the Adam optimizer [94] with a learning rate of 10 −3 for critic and 10 −4 for policies. Similarly to [76,91], we set θ 1 = θ 2 = · · · = θ N in order to make the model invariant to the number of agents. The reward discount factor is set to 0.95, the size of the replay buffer to 10 6 , and the batch size to 1, 024. At each iteration, we calculate the heat kernel over a finite grid of P = 300 time points, with a threshold for getting stable values set to s = 0.05. This value has been determined experimentally (see Table 4). The number of time steps for episode, T , is set to 50 for all the environments, except for Navigation Control where is set to 25. For Formation Control, Line Control and Pack Control the number E of episodes is set to is set to 50, 000 for the basic versions (30, 000 for scalable versions), while for Navigation Control is set to 100, 000 (30, 000 for scalable versions).
All network parameters are updated every time 100 new samples are added to the replay buffer. Soft updates with target networks use τ = 0.01. We adopt the low-variance gradient estimator Gumbel-Softmax for discrete actions in order to allow the back-propagation to work properly with categorical variable, which can truncate the gradient's flow. All the presented results are produced by running every experiment 5 times with different seeds (1,2001,4001,6001,8001) in order to avoid that a particular choice of the seed can significantly condition the final performance. Python 3.6.6 [95] with PyTorch 0.4.1 [96] is used as framework for machine learning and automatic differentiable computing. NetworkX 2.2 [97] has been used for graph analysis. Computations were mainly performed using Intel(R) Xeon(R) CPU E5-2650 v3 at 2.30GHz as CPU and GeForce GTX TITAN X as GPU. With this

Main results
We have compared CDC against several different baselines, each one representing a different way to approach the MA coordination problem: independent DDPG [35,36], MADDPG [37], CommNet [21], MAAC [29], ST-MARL [76], When2Com [98] and TarMAC [28] and Intention Sharing (IS 2 ) [58]. Independent DDPG provides the simplest baseline in that each agent works independently to solve the task. In MADDPG each agent has its own critic with access to combined observations and actions from all agents during learning. CommNet implements an explicit form of communication; the policies are implemented through a large neural network with some components of the networks shared across all the agents and others agent-specific. At every timestep each agent's action depends on the local observation, and on the average of all other policies (neural network hidden states), used as messages. MAAC is a state-of-the art method in which an attention mechanism guides the critics to select the information to be shared with the actors. ST-MARL uses a graph neural network to capture the spatio-temporal dependency of the observations and facilitate cooperation. Unlike our approach, the graph edges here represents the time-depending agents' relationships, and capture the spatial and temporal dependencies amongst agents. When2Com utilises an attentional model to compute pairwise similarities between the agents' observation encodings, which results in a fully connected graph that is subsequently sparsified by a thresholding operation. Afterwards, each agent uses the remaining similarities scores to weight its neighbor observations before producing its action. TarMac is a framework where the agents broadcast their messages and then select whom to communicate to by aggregating the received communications together through an attention mechanism. In IS [58] the agents generate their future intentions by simulating their trajectory and then an attention model aggregate this information together to share it with the others. Differently from the methods above, CDC utilises graph structures to support the formation of communication connectivities and then use the heat kernel, as an alternative form of attention mechanism, to allow to each agent to aggregate the messages coming from the others.  In Table 2 we provide a summary of selected features for each MADRL algorithm used in this work. First, we have indicated whether the communication is implicit or explicit. The former refers to the ability to share information without sending explicit messages, i.e. communication is inherited from a certain behaviour rather than being deliberately shared [99]; studies have shown that this approach is used by both animals and humans [100][101][102] and has discussed in a number of multi-agent reinforcement learning works [21,22,28,57,77,103,104]. Explicit communication assumes the existence of a specific mechanism deliberatively introduced to share information within the system; this is considered to be the most common form of human communication [105,106] and has also been widely explored in the context of reinforcement learning [20,23,58,98]. This categorization can help interpret the performance achieved in certain environments, such as Dynamic Pack Control, where explicit communication is more beneficial.

Type of communication
We also report on how the information is aggregated amongst agents, whether the algorithm relies on a graph-based architecture, and whether the communication content is delayed, i.e. it only utilised in the future but does not affect the current actions. For example, in TarMac, each message is broadcasted and utilised by the agents in the next step, while in MAAC and MADDPG the communication happens through the critics and affect future actions once the policy parameters get updated. Table 1 summarises the experimental results obtained from all algorithms across all the environments. The metric values are obtained by executing the best model (chosen according to the best average reward returned during training) for an additional 100 episodes. We repeated each experiment using 5 different seeds, and each entry of Table 1  It can be noted that CDC outperforms all the competitors on all four environments on all the metrics. In Navigation Control (N = 3), the task is solved by minimizing the overall distance travelled and the number of collisions, with an improvement over MAAC. In Formation Control (N = 4), the best performance is also achieved by CDC, which always succeeded in half of time compared to MAAC.
When the number of agents is increased, and the level of difficulty is significantly higher, all the baselines fail to complete the task whilst CDC still maintains excellent performance with a success rate of 0.99. In Line Control, both scenarios (N = 4 and N = 10) are efficiently solved by CDC with higher success rate and less time compared to MAAC, while all other algorithms fail. For Dynamic Pack Control, amongst the competitors, only CommNet does not fail. In this environment, only the leaders can see the point of interest, hence the other agents must learn how to communicate with them. In this case, CDC also outperforms CommNet on both the number of targets that are being caught and travelled distance. Overall, it can be noted that the gains in performance achieved by CDC, compared to other methods, significantly increase when increasing the number of agents.
Learning curves for all the environments, averaged over five runs, are shown in Figure 4. Here it can be noticed that CDC reaches the highest reward overall. The Dynamic Pack Control task is particularly interesting as only three methods are capable of solving it, CommNet, IS and CDC, and all of them implement explicit communication mechanisms. The high variance associated with CDC and CommNet in Dynamic Pack Control can be explained by the fact that, when a landmark is reached by all the agents, the environment returns a higher reward. These are the only two methods capable of solving the task, and lower variance is associated to other methods that perform poorly. The performance of CDC when varying the number of agents at execution time is investigated (see Appendix, Section A).

Communication analysis
In this section, we provide a qualitative evaluation of the communication patterns and associated topological structures that have emerged using CDC on the four environments. Figure 5 and 6 show the communication networks G t H evolving over time at a given episode during execution: black circles represent the landmarks, blue circles indicate the normal agents, and the red circles are the leaders. Their coordinates within the two-dimensional area indicate the navigation trajectories. The lines connecting pairs of agents represent the time-varying edge weights, H t . Each H t u,v element quantifies the amount of diffused heat between the two nodes. As expected, different patterns emerge in different environments; see Figure  5 and Figure 6. For instance, in Formation Control, the dynamic graphs are dense in the early stages of the episodes, and become sparser later on when the formation is found. The degree of topological adjustment observed over time indicate initial bursts of communication activity at the beginning of an episode; towards the end the communication, this seems to have stabilised and consists of messages shared only across neighbours, which seems to be sufficient to maintain the polygonal shape. A different situation can be observed in Dynamic Pack Control; see Figure 6(f). Here, there is an intense communication activity between leaders and members at an early stage, and the emerging topology approximates a bipartite graph between red and blue nodes. This is an expected and plausible pattern, given the nature of this environment; the leaders need to share information with the members, which otherwise would not know be able to locate the landmarks.
In addition to the above qualitative interpretation based on graph topologies, we can also quantify the emergence of different communication patterns by looking at changes in the statistics of the degree centrality (i.e. the number of connections of each agent) over time. Specifically, we compare the statistics attained at the beginning and end of an episode using the connectivity graph generated by CDC. Table 3 shows the mean and variance of the centrality degree, across all nodes, for each environment. Changes in variance, for instance, may indicate the formation of clusters. Here it can be noted that in Navigation Control, Line Control and Formation Control, the variance is significantly lower at the end of the episodes; this is expected since the best strategy in such tasks consists of spreading the number of connections across all nodes. A different pattern emerges in Dynamic Pack Control where the formation of clusters is necessary since the workers need to connect with the leaders. These clusters are also visible in Figure 6 (f).

Average Degree Centrality Environment
Beginning of episode End of episode Navigation Control N = 10 1.  Table 3: Mean and standard deviation for the centrality degree calculated using the connectivity graphs generated by CDC. Metrics are calculated utilising the graph produced in the first (beginning) and last step (end) of the episodes at execution time. Further appreciation for the role played by the heat kernel in driving the communication strategy can be gained by observing Figure 7 which provides visualisations for all the environments. On the left, the connection weights are visualised using a circular layout. Here the nodes represent agents, and the size of each node is proportional to the node's eigenvector centrality. The eigenvector centrality is a popular graph spectral measure [107], utilised to determine the influence of a node considering both its adjacent connections and the importance of its neighbouring node. This measure is calculated using the stable heat diffused values averaged over an episode, i.e. H u,v = ( T t=1 H t u,v )/T . The resulting graph structure reflects the overall communication patterns emerged while solving the given tasks. On the right, we visualise the squared N × N matrix of averaged pairwise diffusion values as a heatmap (red values are higher). It can be noted that, in Pack Control, two communities of agents are formed, each one with a leader. Here, as expected, leaders appear to be influential nodes (red nodes), and the heatmap shows that the connections between individual members and leaders are very strong. A different pattern emerges instead in Formation Control, where there is no evidence of communities since all nodes are connected to nearly form a circular shape. The corresponding heatmap shows the heat kernel values connecting neighbouring agents tend to assume higher values compared to more distant agents.

Ablation studies
We have carried out a number of studies to assess the relative importance of each new component contributing to CDC. First, we investigate the relative merits of the heat kernel over two alternative and simpler information propagation mechanisms: (a) a global average approach, where the observations of all other agents are averaged and provided to the agent to inform its action, and (b) the nearest neighbours approach, where only the observations of the agent's two nearest neighbours are averaged. For each one of these two mechanisms, we compare a version using our proposed critic (Section 3.5), which uses a recurrent architecture (specifically an LSTM), and a version using a traditional critic, i.e. based on a feed-forward neural network. To better characterise the benefits of a recurrent network, we have also investigated an LSTM-based version of MADDPG. In addition, we have implemented a version of CDC that use a softmax attention, i.e. the heat kernel connectivity weights have been replaced by a softmax function. To ensure a fair comparison, only the necessary architectural changes have been carried out in order to keep the modelling capacity across different versions comparable.
In Figure 8, it can be noted that the proposed CDC using the heat kernel achieves the highest performance by a significant margin. The other modified versions of CDC, with and without LSTM, also outperform the simpler communication methods. There is evidence to suggest that averaging local information coming from the nearest neighbours is a better strategy compared to using a global average; the latter cannot discard unnecessary information and results in nosier embeddings and worse communication. Overall, we have observed that the LSTM-based critic is beneficial compared to the simpler alternative. This is an expected result because, by design, the LSTM's hidden state filters out irrelevant information content from the sequence of inputs. Another observed finding is that the order of the agents does not affect the final performance of the model. This is explained by the fact that each of LSTM-based critics observe the entire sequence of observations and actions before producing the feedback to return. Furthermore, the softmax version of CDC has been found to be less performant that the original CDC thus confirming the important role played by the heat kernel in aggregating the messages across the communication network.
In order to choose an appropriate threshold for the heat kernel equation (see Eq. 5) we have run a set of experiments whereby we monitor how the success rate behaves using different parameter values. Table 4 reports on the performance of CDC on Formation Control when the threshold parameter s varies over a grid of possible values. In turn, this threshold determines whether the heat kernel values are stable or not. The best performance is obtained using s = 0.05, which is the value used in all our experiments. To select the specific thresholds reported in Table 4, we tried a range of values suggested in related works [33,108].

Conclusions
In this work, we have presented a novel approach to deep multi-agent reinforcement learning that models agents as nodes of a state-dependent graph, and uses the overall topology of the graph to facilitate communication and cooperation. The inter-agent communication patterns are represented by a connectivity graph that is used to decide which messages should be shared with others, how often, and with whom. A key novelty of this approach is represented by the fact that the graph topology is inferred directly from observations and is utilised as an attention mechanism guiding the agents throughout the sequential decision process. Unlike other recently proposed architectures that rely on graph convolutional networks to extract features, but we make use of a graph diffusion process to simulate how the information propagates over the communication network and is aggregated. Our experimental results on four different environments have demonstrated that, compared to other state-of-the-art baselines, CDC can achieve superior performance on navigation tasks of increasing complexity, and remarkably so when the number of agents increases. We have also found that visualising the graphs learnt by the agents can shed some light on the role played by the diffusion process in mediating the communication strategy that ultimately yields highly rewarding policies. The current LSTM-based critic could potentially be replaced by a graph neural network equipped with an attention mechanism capable of tailoring individual feedback according to the agents' needs. This work represents an initial attempt to leverage well-known graphtheoretical properties in the context of a multi-agent communication strategy, and paves the way for future exploration along related directions. For instance, further constraints could be imposed on the graph edges to regulate the overall communication process, e.g. using a notion of flow conservation [109]. Further investigations could be directed towards the effects of adopting a decentralised critic modelling the communication content together with the agents' state-action values to provide a richer individual feedback.
Supplementary information. Supplementary material is provided in the Appendix as suggested by the provided template.

Statements and Declarations
Funding GM acknowledges support from a UKRI AI Turing Acceleration Fellowship (EPSRC EP/V024868/1).  Table A1: Comparison of DDPG and CDC on Dynamic Pack Control. Both algorithms were trained with 4 agents and tested with 3-8. The performance metric used here is the distance of the the farthest agent to the landmark.
We tested whether CDC is capable of handling a different number of agents at test time. Table A1 shows how the performance of DDPG and CDC compares when they are both trained using 4 learners, but 3-8 agents are used at test time. We report on the maximum distance between the farthest agent and the landmark, which is invariant to the number of agents. It can be noted that CDC can handle systems with a varying number of agents, outperforming DDPG and keeping the final performance competitive with other methods that have been trained with a larger number of agents (see Table 1).