Very Large Scale Multi-Agent Reinforcement Learning with Graph Attention Mean Field
Authors: Qianyue Hao
Venue: Submitted to ICLR 2023 (2023)
Keywords: Multi-agent reinforcement learning
large-scale problems
graph attention
mean field

Abstract: With recent advances in reinforcement learning, we have witnessed countless successes of intelligent agents in various domains. Especially, multi-agent reinforcement learning (MARL) is suitable for many real-world scenarios and has vast potential applications. However, typical MARL methods can only handle tens of agents, leaving scenarios with up to hundreds or even thousands of agents almost unexplored. There exist two key challenges in scaling up the number of agents: (1) agent-agent interactions are critical in multi-agent systems while the number of interactions grows quadratically with the number of agents, causing great computational complexity and difficulty in strategies-learning; (2) the strengths of interactions vary among agents and over time, making it difficult to precisely model such interactions. In this paper, we propose the Graph Attention Mean Field (GAT-MF) method, where we convert agent-agent interactions into interactions between each agent and a weighted mean field, greatly reducing the computational complexity. We mathematically prove the correctness of this conversion. We design a graph attention mechanism to automatically capture the different and time-varying strengths of interactions, ensuring the ability of our method to precisely model interactions among the agents. We conduct extensive experiments in both manual and real-world scenarios with up to more than 3000 agents, demonstrating that comparing existing MARL methods, our method reaches superior performance and 9.4 times computational efficiency.

Under review as a conference paper at ICLR 2023
VERY LARGE SCALE MULTI-AGENT REINFORCEMENT LEARNING WITH GRAPH ATTENTION MEAN FIELD
Anonymous authors Paper under double-blind review
ABSTRACT
With recent advances in reinforcement learning, we have witnessed countless suc- cesses of intelligent agents various domains. Especially, multi-agent reinforce- ment learning (MARL) is suitable for many real-world scenarios and has vast potential applications. However, typical MARL, methods can only handle tens of agents, leaving scenarios with up to hundreds or even thousands of agents almost unexplored. There exist two key challenges in scaling up the number agents: critical in multi-agent systems while the number interactions grows quadratically with the number of agents, causing great com- putational complexity and difficulty in strategies learning,,,nnn (2) the strengths of in- teractions vary among agents and over time, making it difficult to precisely model such interactions. In this paper, we propose the Graph Attention Mean Field (GAT- MF) method, where we convert agent-agent interactions into interactions between each agent and weighted mean field, greatly reducing the computational com- plexity. We mathematically prove the correctness of this conversion. We design a graph attention mechanism automatically capture the different and time evrying strengths of interactions, ensuring the ability of our method to precisely model in- teractions among the agents. We conduct extensive experiments in both manual and real-world scenarios with up to more than 3000 agents, demonstrating that comparing existing MARL methods, our method reaches superior performance and 9.4 times computational efficiency.
(1) agent-agent interactions
INTRODUCTION
In recent years, rapid progress in reinforcement learning (RL) has largely facilitated humans' decision-making in complex situations. In various domains such as game playing (Silver et al. 2017 Ye et al. 2021), robotics (Sinha et al. 2022 Brunke et al. (022), public health (Bastani al. 2021 Hao et al. 2021: 2022). and even nuclear fusion system (Degrave et al. 2022). RL algorithms and applications keep emerging. Most of the successful RL works focus single-agent scenar- ios, while in the real world, it is normal that a system consists of multiple agents, and interactions among the agents are of vital importance. Therefore, multi-agent reinforcement learning (MARL) has especially wide applications and developments in corresponding methods are called for.
In fact, previous researchers have done plentiful works on MARL, For example, MADDPG (Lowe et al. (2017) outperforms single-agent DDPG in experiments with various goals, a series of studies such QMIX (Rashid et al., 2018 AlphaStar (Vinyals et al. (019) and MAPPO (Yu et al. 2021 keep surpassing human professional players and refreshing the score on the Starcraft game. which a typical MARL benchmark. Also, there are various social and industrial applications of MARL methods in traffic signal control (Wang et al. (2221b), power distribution management (Wang et al.) 2021a), cloud computing (Balla al., (021). ). etc. However, existing studies typically only consider no more than tens of agents, while methods dealing with scenarios with up to hundreds or even thousands agents remain almost unexplored.
Despite scenarios with hundreds or thousands of agents are common in the real world, there ist two key challenges in scaling up the number of agents in MARL methods. (1) Large number of agent-agent interactions. In multi-agent systems, the agents naturally interact with each other all the time. and such interactions are critical for the system dynamic. Therefore, besides simple agent-environment interactions, MARL methods must take the agent-agent interactions into

---

Under review as a conference paper at ICLR 2023
sideration to reach good performance. However, the number of agent-agent interactions increases quadratically following O(N²) as the number of agents grows to N, which greatly adds to the com- putational complexity and difficulty for the agents to learn efficient strategies. (2) Varying strengths of agent-agent interactions. Due to the intrinsic dynamism of real-world scenarios, the strengths of interactions not only vary among each pair of agents but also vary over time, making it difficult to precisely model all the agent-agent interactions. If we manually set the interaction strength of each pair of agents according to prior knowledge of certain scenario, it requires repeated manual work when we want to train models to solve problems in different scenarios. On the other hand, it almost impossible to do such manual work when the number of agents is large.
In view of these challenges, we propose Graph Attention Mean Field (GAT-MF) method to largely scale up the number of agents in MARI.. First, to solve the problem of the unaffordably large number of agent-agent interactions, we develop the previous study of unweighted Mean Field (Yang et al.) 2018] into a weighted one. We prove the mathematical correctness of converting interactions among the agents into the interactions between each agent and a corresponding field, which is obtained through a weighted average over the raw agent-agent interactions. By such conversion, the number of agent-field interactions only increases linearly following (N) with N agents, which greatly reduces the computational complexity and difficulty in learning efficient strategies. Also, such con- version keeps the information of different interaction strengths among agents in the weights, which is discarded in the unweighted mean field. Second, to automatically capture the varying strengths of interactions. i.c., the weights in calculating the equivalent field, we model the relations among the agents into a graph where each node represents one agent. We design a graph attention mechanism to dynamically learn and calculate the different and time-varying interaction strengths among the agents, which requires neither prior knowledge of the system nor manual work. Third, we evaluate our GAT-MF method in (1) grid-world manual scenario with 100 agents (see Section (5) and (2) a real-world metropolitan scenario with more than 3000 agents, which is built according to real-world data (see Section (). The results show that the proposed method outperforms the existing MARL methods in both scenarios and prove its ability in scaling up to scenarios with large number of agents. Besides, the results also indicate that our method reaches high computational efficiency, taking only 41.5% GPU memory and reaching up 9.4 times training speed.
In summary, the main contributions of this work include:
We prove the mathematical correctness of converting agent-agent interactions in multi- agent systems into the interactions between the agent and a weighted mean field. By do- ing so, we greatly reduce the computational complexity and difficulty in learning efficient strategies and make it possible to scale up to scenarios with a very large number of agents.
We design graph attention mechanism automatically capture the varying strengths of the agent-agent interactions, ensuring that our method can precisely model these interac- tions without prior knowledge of the strengths of the interactions in the scenario.
We conduct extensive experiments in both manual grid-world scenario and real-world metropolitan scenario with up to more than 3000 agents. The results demonstrate that comparing the typical MARL methods, our method achieves superior performance in both scenarios and obtains 9.4 times computational efficiency.
2 RELATED WORKS
Large Scale Task with RL. Many previous studies focus solving large-scale tasks with RL. One common approach is to aggregate the large number of natural units into a relatively small number of clusters and control each cluster with one agent (Wang et al.) 2021b] Qiu et al. 2021 Hao al.) 2022). Another kind of methods decompose the raw vast action space into a hierarchiee one accord- ing to prior knowledge of the targeted scenario, simplifying the decision-making process (Hao et al., 2021 Ma et al. 2021: Ren et al., 2021). Other researchers combine human experts' solutions to aid the RL agent to learn more efficient strategies in large-scale scenarios (Qu et al. 2019 Li et al.) 2022 Hao et al. 2022). Although these works achieve success in their targeted scenarios, the man- ual techniques of unit aggregation, action space decomposition, or experts' solution collection are largely problem specific and require strong prior knowledge of the scenarios. In contrast, our method provides a direct MARL approach, requiring neither manual techniques nor prior knowledge, and thus is able to easily train models for solving problems in different scenarios.
2

---

Under review as a conference paper at ICLR 2023
Relation among Agents
CTDE
Unweighted MF
GAT-MP
Mean
Mean
Concatenate
Unweighted Average Dimension, Low Precision
Weighted Average
High Dimension, High Precision
Dimension, High Precision
Discard Varying Strengths
Keep Varying Strengths
Block
Critic
cmm
Action Vector
[. Targeted Agent
Environment
Agent
Agent- Interaction nzz Mean Field Vector
Figure 1: Comparison among existing MARL methods and our proposed method. (A) Example of multi-agent scenario in a metropolitan where each block corresponds to one agent and the relations among adjacent blocks lead to agent-agent interactions. (B) Limitation of the CTDE methods, i.e, high dimension of the concatenated input vector of the critic. (C) Limitation of the unweighted MF, i.c., losing precision on modeling agent-agent interactions using unweighted average. (D) Key design of our proposed GAT-MF method, reducing the dimension while keeping the precision.
Multi-agent Reinforcement Learning (MARL). There exist abundant works on MARL and here we illustrate the differences among various MARL methods with an example in a metropolitan in Figure The main approaches of recently popular MARL solutions can be roughly summarized into two categories, one is value decomposition (VD) and the other is centralized training with decentralized exccution (CTDE). VD methods factorize the joint Q-function into certain function of the local Q-function of each agent in order to reduce the complexity. VDN (Sunehag et al. 2017) uses additive function, QMIX chooses monotonic function (Rashid et al.) (018)) and QTRAN extends it into a more general function (Son et al.] 2019). However, it is not easy to factorize the joint Q-function into hundreds or even thousands of terms, limiting the scalability of such methods on a large number of agents. On the other hand, CTDE methods such as MADDPG (Lowe et al., 2017. COMA (Foerster et 2018) and MAPPO (Yu al., 202T) design decentralized actor and centralized critic (or value function), where the latter one only works during the training process. Since the centralized critic (or value function) requires concatenating the vectors of local states and actions from all agents together as its input to obtain the information on agent-agent interactions, obvious that when the number of agents large, the concatenated vector will be extremely high in dimension, making the training process hard (Figure BB). In contrast, due to our special design, our proposed method can scale up to scenarios with more than 3000 agents and keeps high computational efficiency at the same time.
Mean Field (MF) MARL. In order to reduce the unaffordable high vector dimension in CTDE methods mentioned above and scale up the number of agents, special technique named Mean Field (MF) (Yang et al., 2018) is proposed. It approximates the concatenation of actions with the unweighted average of these actions, namely mean field. RL algorithms with MF technique have been successfully applied in domains such as ridesharing order dispatching (Li et al. 2019), mobile networks management (Shi al. 2020) and unmanned aerial vehicles (UAVs) control (Chen al., 2020). Nevertheless, such approximation regards interactions among all agents equally and dis- cards the varying strengths of these interactions, losing precision in modeling the complex relations among the agents (Figure [T]. In this paper, we develop the MF method into GAT-MF, in which we design a variant of graph attention mechanism to automatically capture the varying strengths of agent-agent interactions and calculate weighted average of the actions according to their strengths. Therefore, we are able to reduce the vector dimensions, scale up the number of agents, and keep precise modeling of the relations among the agents at the same time (Figure
PRELIMINARIES
Markoy Decision Processes (MDPs). In this paper, we mainly discuss our method consid- ering multi-agent version of Markov Decision Processes (MDPs), which can be defined by
3

---

Under review as a conference paper at ICLR 2023
(n, S, P, R. y), where denotes the total number of agents. The global state ($1, Sn) consists of local state of each agent. The possibility distribution of initial state is given by D(S), where ((S) is collection of possibility distribution over the state space S. The joint action a = (01 (a1...., an) E A consists of local action of each agent and is produced by the policy mo S D(A), with D(A) being collection of possibility distribution over the state space A. Te is parameterized with 0 = (01,.., 0a) and local action of each agent is produced by тT, (s). The state transition probability and the one-step reward given the current state and the joint action are defined by P: S x A + D(S) and R S x A + R correspondingly. The global one-step reward is the sum of local one-step rewards from each agent, i.e., R(s, a) E, r(s,, 0z), and the long-temn discounted reward from to is defined by discount factor following:
RID
7 R(s', a'),
t=to
where T is the max length of an episode and E [0,
Q-Learning and Deep Q-Network (DQN). Q-Learning (Watkins & Dayan 1992 is one of the basic RL methods, which learns efficient policy in MDPs through an off-policy manner. It aims at finding value function Q (s, a. for policy we:
nh s, a) E s' a = a'1 E. (R(s,a) + y.a''mo 1 (s', a')l,
(2)
where the recursive form is Bellman Equation. In practical training algorithms, this value function is obtained by minimizing the loss function which is designed with greedy thinking:
=) = R +-yymax a'
('s''a')),
(3)
where B is the replay buffer collecting experiences (s, a, R, s') from agent-environeennee and Q' is the target version of Q, whose parameters are synchronized from Q with delay. After obtaining the optimal value function Q" a), the optimal policy " is obtained in a greedy way: (arg max Q² (B)a)s 1. a
interactions
(4)
Deep Q-Network (DQN) (Mnih et al. 2013) keeps the same mathematical essence as Q-learning but approaches the optimal value function (s,ss, a) with a deep neural network, being able to represent more complex environmental situations and thus can solve problems in more scenarios.
Policy Gradient (PG) and Deep Deterministic Policy Gradient (DDPG) Algorithms. Since argmaza is used in obtaining the optimal policy in Q-Learning and DQN, they are only practi- cal scenarios where the action space A is discrete. In order to solve problems with continuous action spaces, Policy Gradient (PG) methods are proposed (Sutton al.) 1999). In major group of deep PG methods, besides the value function network, the policy πe is also approached by a neural network and directly calculates the action given s. These methods keep training the value network in similar way as L-Lernnig but without greed:
E B.e.,, a) - ,)²}, y= '''''',,,,
(5)
while optimizing the policy network to maximize the episode return, following the gradient:
V Ea-we Ve log TT(aa
In practice, similar to the value network Q, the policy network лe also has target copy with delayed parameters synchronization. Deep Deterministic Policy Gradient (DDPG) (Silver et al. 2014) is a special variant of PG methods where the policy converted from possibility distribution over the action space to a deterministic action. In the DDPG training process, a small random disturbance is added to the deterministic action, helping the agent explore the potential action space. In this work, we mainly combine our proposed GAT-MF method with the original MADDPG algorithm (Lowe) al. 2017), which is a multi-agent version DDPG.
METHODS
4.1 OVERVIEW
First, we briefly introduce the improvement of our GAT-ME methods comparing the previous un- weighted MF (Yang al. 2018). As we showed in Section 2 and Figure 3 & C, unweighted MF
4

---

Under review as a conference paper at ICLR 2023
uses the following approximation on the value function of CTDE when considering agent j as:
Q(s,a) ~ ag,,, a
[
Σ
ak
KEN?
where / denotes the neighboring agents of agent j. However, such an unweighted average neglects the fact that the strengths of agent-agent interactions vary among different agent pairs and over time. Therefore, intuitively, we can improve the approximation into a weighted average to maintain such varying strengths. Moreover, besides reducing the dimension of a, can reduce the dimension of with similar technique, further reducing the computational complexity. Generally, we propose the following approximation of the value function of CTDE when considering agent j:
Q(8, a) ~ Bj, ū5), W
1
Σ RENT
with aR. 8j
1 W
Σ KEND
with Sk: W₁ = Σ with
(8)
kEN
where witk is the weight between agent j and k. reflecting the strength of interaction between them. the other hand, in order to make it able apply our method to PG algorithms with actor-critic structures, also design similar weighted average approximation to reduce the computational complexity of policy function, i.c., the actor, as follow:
(8) ~ TI (83,889) 8J
Σ kENS
with
8k
U₁ =
Σ with kENS
JJ
where whth is the corresponding weight between agent j and k.
Next, we will mathematically prove why this approximation holds in Section 4.2 and illustrate how automatically capture the weights [w>k] and [u/h] and implement such approximation in prac- tical MARL training algorithm in Section 4.3
4.2 MATHEMATICAL PROOF
Here prove why the intuitive approximation of the weighted average the value function holds.
Theory 1 (Weighted MF Approximation). When considering agent the centralized value function Q(s, a) can be approximated by Q(s,,
Proof. Since
āj
Σ
witk aks W
Σ S
(10)
W
KEN:
REN:
we regard each a², o,, E N to be the sum of āj and a small fluctuation as:
ag āj + 8ack, and similarly, we have:
with 8azk
Σ
max - - ā ā = 0, (11)
W,
W
KEAS
KEAS
1
Sp 3, + dayk:
w tk ōijk O.
(12)
Wj
RENS
Following the expansion in the MF study Yangg et al.) 2018), we have:
Q(s, a)
w Q( Sky aj, ax) = W
Σ
w Qss, 3, + 885u, aj, ā + dazx). (13)
W,
KENS
REV
We denote Q(35, Kj, aj, uz) as Qo and expand each term in the sum according to Taylor's formula:
1
with 1Q V3, Qo òssk + Va, Qo
dayk =
W
KENS
=Qo Vg, Qo
With
Jukk&s sK Va, Qu
Σ
wik pukkaajk
Σ
witk O,k
wojk
W,
W
W
KENS
KENS
KEN'
-0+0++0-
1
Σ
w Ojk x Q Q(55. Kyy
W
kENSs
(14)
5

---

Under review as a conference paper at ICLR 2023
Hence, the centralized value function Q(s, a) can be approximated with Q( 83, ag. k,) where the error within second order small terms.
4.3
IMPLEMENTATION DETAILS
A
B
C
State Vector
MeAn
Q Network
2
Vector
Inner Product
22
K Vector
Mean
K Network
Mean
Н
Graph of the Agents
Neighbors of +
Weighted Average
Agent
Actor Q/K Network
Actor
Action Vector
Actor Q/K Vector
Critic
State Vector
Critic Q/K Network
Targeted Agent
Agent-Agent Interaction
Critic Q/K Vector
Figure 2: Implementation details of the GAT-MF method. (A) Modelling the adjacency among the agents into graph, where each agent has its state vector and action vector. (B) Process of calculating the weights [u=*), [w]*] through graph attention. (C) Using the obtained weights calculate the weighted MF vectors to be the inputs of the actor and critic.
Having proved the correctness of weighted MF approximation, we show how to implement such theory into a practical MARL algorithm Figure 2 We mainly consider scenarios where the agents have fixed relative positions and therefore we can model the adjacency among them into graph G (Figure 1). In order to obtain the weights [w>k] and [u=*], which can reflect the varying strengths of interactions among each agent and its neighbors, we design variant of graph attention (GAT) mechanism to automatically learn them.
In detail, each agent is assigned with a pair of query (Q) networks Q Q and key (K) networks Ky, XCC with learnable parameters, which respectively correspond to the actor and critic. In each time step, Q 22, XC2, K22 take in the current local state vector sj and produce pair of Q vectors dú. of and pair of K vectors kg, kg, which all have the same dimension. Then, we calculate the weights through the inner product of the corresponding Q and K vectors (Figure 2B), as:
wit =
(15)
By this mechanism, we obtain the agent-pair-specific and time-varying weights, reflecting the strengths of agent-agent interactions. Finally, we weigh the state and action vectors by the weights and calculate the MF vectors, which then used the inputs of the actor and critic (Figure[p) The parameters of Q! Qi Kj. KJ are updated along with the actor and critic networks, and we also apply the technique of target network with delayed parameters synchronization to them.
We combine our GAT-MF method with the original MADDPG algorithm and show the siep-by-step training algorithm in Appendix A Considering the homogeneity among the agents, the network parameters are shared among the agents, reducing memory consumption. We will first evaluate our method in a grid-world task with 100 agents and provide some straightforward visualizations of the leameed policies in Section 5 We will then extend the experiment into real-world task with more than 3000 agents Section fully verifying the ability of our method to scale up to scenarios with very large number of agents. Our experiments
implemented with Py Porch and the source codes and data for reproducibility are posted into supplementary materials and also at an anonymous repository httpt:tt///t/ https:://ithub. wwt.hh.w.......oeeaaamaeeeeee wwube ew Large- Seaggee--a""" Sca MARA

---

Under review as a conference paper at ICLR 2023
A
Retummo 000
B
Returm0.22
C
Numberr Minds
Diamonds
SAC
MAGOPS
66
Episode
Average
Numbe
DDPG
SAC
MADDPG
MAPPO MP
GAT
de
103
Number of Interations (M)
Figure 3: Experimental settings and results in the grid world. (A) An initialized example of the grid world with randomly located diamonds and uniformly distributed miners. (B) The return after 10 steps of random actions. (C) Training curves of the proposed GAT-ME, the baselines, and the ablation study. (D) Best performance each method.
EXPERIMENT 1: WORLD TASK
5.1 EXPERIMENTAL SETTINGS
First, we start with a diamonds-seeking task in a manual grid world consisting of 10x 10 grids with loop boundaries and the grids correspond to 100 agents in total. We show randomly initialized example of the grid word in Figure 3A. Initially, there are two diamond veins buried in two random grids (blue markers in the figure) and the density of diamonds over the world, which is denoted by the contour lines, follows Gaussian distributions centered at the two grids. There also miners uniformly distributed over the grids, whose number is denoted by the background color. The total number of obtained diamonds is calculated by summing up the product of the number of diamonds and miners at each grid and the return is defined by how many more diamonds are obtained than initialization. In each time step, 10% of the miners from each grid move to one of its neighbors, and the task of the agents is to give the exact numbers of miners to each of the four neighbors to efficiently redistribute the miners and get as many diamonds as possible. We show the distribution of miners and the return after 10 steps of random movements in Figure 3 as an example.
5.2 PERFORMANCE EVALUATION
As we mentioned in Section we mainly combine our proposed GAT-MF with the MADDPG algorithm and train the model. We set the local state sj grid j to be a five-dimensional vector consisting of the densities of diamonds at the center and the four corners of the grid. The local one-step reward r is set to be the difference its neighbors before and after the step. During the training, we set 10 steps to be one episode and randomly reinitialize the grid world after each episode. We compare the performance of our method with various baseline RL algorithms, which are listed follows:
the number of obtained diamonds by the grid and
Global agent methods: In this group of baselines, we apply widely used single-agent RL methods including DDPG (Silver et al., 2014), PPO (Schulman et al., 2017) and SAC (Haarnoja et al. 2018) to the task. We consider the single-agent to be global one, which takes the global state from all grids and gives the joint action a of all grids in the form of a concatenated high dimensional vector.
. CTDE MARL methods: In this group of baselines, we apply original versions of MAD- DPG (Lwwe et al. 2017) and MAPPO (Yu et al. 2021). which are popular CTDE methods.
Specially, we further design the following ablation study to verify the vital role of our GAT design:
Ablation study, w/o GAT: We substitute the proposed GAT-MF with the unweighted MF method as we described in Section 4.1 while keeping the rest parts identical.
We show the training curves over 100M agent-environment interactions in Figure 3C and extract the best performance of each method in Figure The results illustrate the superior performance of our method with a large margin. The ablation version of our method, i.c., the MF, ranks second, proving the validity of the mean field approximation and the large improvement of method comparing
7

---

Under review as a conference paper at ICLR 2023
verifies the key role of our GAT design. Though MAPPO, of the SOTA MARL methods, ranks third, all global agent methods and CTDE MARL methods perform badly due to the high complexity caused by the high dimensional vectors. This again stresses the necessity of using the mean-field approximation to reduce the dimension when the number of agents is large.
5.3 VISUALIZATIONS THE LEARNED POLICY
A
Reiturn225
Return-50
B
Return=6
Return
Mineers
Attention
Figure 4: Visualizations of the learned policies. (A) The distribution of miners after applying the policy from a trained GAT-MF model for 5 and 10 steps. (B) The distribution of miners after applying the policy from trained DDPG model for 10 steps. (C) The distribution of miners after applying the policy from a trained MAPPO model for 10 steps. (D) The learned attentions of some actors at the first step from a trained GAT-MF model.
To help understand what the agents learned through training with our method, here we provide some visualizations of the learned policies. In Figure we show the distribution of miners after applying the policy from trained GAT-MF model for 5 and 10 steps. From these we find the agents have learned reasonable policy, quickly making the miners gather at grids with the most diamonds, e.g., the left-upper corner in the shown example. On the other hand, we show in Figure 4B & C the distribution of miners after applying policies from trained DDPG model and trained MAPPO model for 10 steps, which are respective representatives of global agent methods and CTDE MARL methods. The DDPG policy tends be like random movements and the MAPPO policy tends to only do very slight movements. We show more visualizations of policies from models trained via other baseline methods Appendix [ and find none of them help the agents learn efficient policy. Once again, we verify the advantage of our proposed method over the existing ones.
We also visualize the learned attentions of some actors the first step from a trained GAT-MF model in Figure AD. We find the attentions vary among the agents and reasonably. the agents tend to pay larger attention the neighboring agents which are in grids with more diamonds. We show more visualizations of the attentions in Appendix [Cadd from all these results, we can verify the validity of the GAT design in capturing the varying strengths of agent-agent interactions.
6 EXPERIMENT 2: REAL-WORLD METROPOLITAN TASK
A
Best Episade Retur
GPU Memeory (MB)
34.50
-290
20000
33tte
8
puve Average Episode
100322
sccon
39:75
12530
ning
4ccco
19930
MADIPS
-032
20000
33:25
33:00
DDPG
PPO
SAC
MADDPG
MAPPO
MF-
GAT-MF
MADOPG
MAPPO
GAT-MF
MADOPG
MAPPO
GAT-MP
-85 5-84 0-83.5
Longitude
-20520
Number of Interations (M)
200
400
033 E00 1000 1926
Figure 5: Experimental settings and results in the real world. (A) The map of Atlanta, where each block is one unit in the vaccine-allocation task and corresponds to one agent. (B) Training curves of the proposed GAT-ME, the baselines, and the ablation study. (C) Best performance of each method. (D) Computational efficiency comparison.
8

---

Under review as a conference paper at ICLR 2023
6.1 EXPERIMENTAL SETTINGS
In order to verify the ability of our method to scale up to scenarios with a larger number of agents, conduct another experiment on the real-world task of COVID-19 vaccine allocation. During the pandemic of COV,D-19, people in metropolis with high population density and frequent population mobility suffer a high risk of infection (Stier et al. 2020). However, vaccines, one of the most important medical resources, are in shortage during the early stage of COVID-19. Therefore, in order to minimize the overall infections, finding an efficient strategy to allocate the limited vaccines to the key population group, e.g., the elders or the health workers, in the metropolis is of vital importance. Previous researchers have built a precise simulator with real-world data to infer the total infections with different vaccine-allocatio strategies (Chen et al.) 2022). We conduct our experiments based on the simulator in Atlanta, where there are 3130 blocks, corresponding to 3130 agents (Figure (5A).. People in each block have different age structures, time- varying moving and contacting patterns, and thus have complex time-varying risks of infection. The task of the agents is to find an efficient way allocate the limited vaccines among the blocks each time step, reduce the local risk of infection in certain key blocks, and thus minimize the overall infections, which is opposite the return. We show a more detailed background of this experiment in Appendix D
6.2 PERFORMANCE AND COMPUTATIONAL EFFICIENCY
During the training, we set 24 hours one step and an episode consists of 63 steps (9 weeks). The local state 8y at block j consists of the current number of susceptible, infected, and dead people in this block and we set the one-step reward to be opposite to the number of newly infected people in the step. We compare the performance of our method with the same baselines and ablation study in Section 5.2 setting the available number of vaccines identical among our method and the baselines.
We show the smoothed training curves over more than 1.2B agent-environment interactions in Fig- 3 and summarize the best performance of each method in Figure 5C. The results illustrate that in this larger scenario with thousands of agents, all the baseline methods failed to learn useful strate- gies and their performance even worse than randomly initialized model. In contrast, our method reaches a good performance rapidly and converges stably, proving its superior performance again. On the other hand, the unweighted MF method still ranks second, which again verifies the validity of the mean field approximation and the key role of our GAT design.
We compare the computational efficiency FigureBp. The results show that with the GAT-MF design, which greatly reduces the input dimen- sion of the actor and critic, our method is 9.4x and 7.3x faster than MADDPG and MAPPO, train- ing with the same number of agent-environment interactions. Besides, our method takes only 41.5% and 80.8% of GPU memory comparing MADDPG and MAPPO. In a nutshell, our method works especially well in this scenario where there is much larger number of agents, not only reaching superior performance but also greatly reducing the training time and GPU memory consumption.
of of our method with the two CTDE MARL methods in
7 CONCLUSIONS
In this paper, we aimed at scaling up the number of agents in MARL algorithms and proposed the GAT-MF method. We first intuitively analyzed its advantages over the existing CTDE methods and the unweighted MF method and then mathematically proved its correctness. We implemented the mathematical theory into practical MARL algorithm through the graph attention mechanism and conducted extensive experiments in both manual and real-world scenarios with up to more than 3000 agents. All the results indicated the superior performance and high computational efficiency of our method. Because of the advantages of our method, it has great potential to be applied in solving various real-world large-scale problems.
One main limitation of our method is that the GAT mechanism requires the agents to have fixed relative positions and thus the adjacency among them can be modeled as a static graph. However, in some scenarios, the agents keep moving and one possible solution for this is to extend the static graph in this paper into dynamic one and modify the GAT mechanism to work on dynamic graphs. We leave this as potential direction for future work.
Test NVIDIA A100 GPU

---

Under review as a conference paper at ICLR 2023
REFERENCES
Husamelddin AM Balla, Chen Guang Sheng, and Weipeng Jing. Reliability-aware task scheduling in cloud computing using multi-agent reinforcement learning algorithm and neural fitted q. Int. Arab J. Inf. Technol. 18(1):36-47, 2021.
Hamsa Bastani, Kimon Drakopoulos, Vishal Gupta, Ioannis Vlachogiannis, Christos Hadji- cristodoulou, Pagona Lagiou, Gkikas Magiorkinis, Dimitrios Paraskevis, and Sotirios Tsiodras. Efficient and targeted covid-19 border testing via reinforcement learning. Nature, 599(7883);
108-113, 2021.
Lukas Brunke, Melissa Greeff, Adam W Hall, Zhaocong Yuan, Siqi Zhou, Jacopo Panerati, and Angela Schoellig. Safe learning in robotics: From learning- -bsed control to safe reinforcement learning. Anmual Review of Control, Robotics, and Autonomous Systems, 3:411-444 2022.
Serina Chang, Emma Pierson, Pang Wei Koh, Jaline Gerardin, Beth Redbird, David Grusky, and Jure Leskovec. Mobility network models of covid-19 explain inequities and inform reopening. Nature, 589(7840):82 87, 2021a.
Serina Chang, Mandy L Wilson, Bryan Lewis, Zakaria Mehrab, Komal K Dudakiya, Emma Pierson, Pang Wei Koh, Jaline Gerardin, Beth Redbird, David Grusky, et al. Supporting covid-19 19 policy response with large-scale mobility-basse based modeling. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery Data Mining, pp. 2632-2642, 2021b.
Dezhi Chen, Qi Qi, Zirui Zhuang, Jingyu Wang, Jianxin Liao, and Zhu Han. Mean field deep reinforcement learning for fair and efficient uav control. IEEE Internet of Things Journal, 8(2): 813-828, 2020.
Lin Chen, Fengli Xu, Zhenyu Han, Kun Tang, Pan Hui. James Evans, and Yong Li. Strategic covid-19 vaccine distribution simultaneously elevate social utility and equity. Nature Human Behaviour, pp. 1-12, 2022.
Jonas Degrave, Federico Felici, Jonas Buchli, Michael Neunert, Brendan Tracey, Francesco Carpanese, Timo Ewalds, Roland Hafner, Abbas Abdolmaleki, Diego de Las Casas, et al. Mag- netic control of tokamak plasmas through deep reinforcement learning. Nature, 602(7897):414- 419, 2022.
Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishck Gupta, Pieter Abbeel, et al. Soft actor-critic algorithms and appli- cations. arXiv preprint ar21v:1812.05905, 2018.
Qianyue Hao, Fengli Xu, Lin Chen, Pan Hui, and Yong Li. Hierarchical reinforcement learning for scarce medical resource allocation with imperfect information. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 2955-2963, 2021.
Qianyue Hao, Wenzhen Huang, Fengli Xu, Kun Tang, and Yong Li. Reinforcement learning hances the experts: Large-scale covid-19 vaceine allocation with multi-factor contact network. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 4684 4694, 2022.
Jingbo Li, Xingjun Zhang, Jia Wei, Zeyu Ji, and Zheng Wei. Garlsched: Generative adversarial deep reinforcement learning task scheduling optimization for large-scale high performance computing systems. Future Generation Computer Systems, 2022.
Minne Li, Zhiwei Qin, Yan Jiao, Yaodong Yang, Jun Wang, Chenxi Wang, Guobin Wu, and Jieping Ye. Efficient ridesharing order dispatching with mean field multi-agent reinforcement learning. In The world wide web conference, pp. 983-994, 2019.
10

---

Under review as a conference paper at ICLR 2023
Ryan Lowe, Yi I Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi- agent actor-critic for mixed coperative-compettivy environments. Advances in neural informa- fion processing systems, 30, 2017.
Yi Ma, Xiaotian Hao, Jianye Hao, Jiawen Lu, Xing Liu, Tong Xialiang, Mingxuan Yuan, Zhigang Li, Jie Tang, and Zhaopeng Meng. A hierarchical reinforcement learning based optimization frame- work for large-scale dynamic pickup and delivery problems. Advances in Neural Information Processing Systems, 34:23609-236200 2021.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprini arXiv: 13225600, 2013.
Dawei Qiu, Yujian Ye, Dimitrios Papadaskalopoulos, and Goran Strbac. Scalable coordinated man- agement of peer-to-peer energy trading: A multi-cluster deep reinforcement learning approach. Applied Energy, 292:116940, 2021.
Shuhui Qu, Jie Wang, and Juergen Jasperneite. Dynamic scheduling in modern processing systems using expert-guided distributed reinforcement learning. In 2019 24th IEEE International Confer- ence on Emerging Technologies and Factory Automation (ETFA), pp. 459 466. IEEE, 2019.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforce- ment learning. In International conference on machine learning, pp. 4295-4304. PMLR, 2018.
Tao Ren, Jianwei Niu, Bin Dai, Xuefeng Liu, Zheyuan Hu, Mingliang Xu, and Mohsen Guizani. Enabling efficient scheduling large-scale uav-assisted mobile-edge computing via hierarchical reinforcement learning. IEEE Internet of Things Journal, 9(10):7095-7199, 2021.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 2017.
Dian Shi, Hao Gao, Li Wang, Miao Pan, Zhu Han, and H Vincent Poor. Mean field game guided deep reinforcement learning for task placement in cooperative multiaccess edge computing, IEEE Internet of Things Journal, 7(10):9330- 9340, 2020.
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In International conference machine learning, pp- 387-395. PMLR, 2014.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 550(7676):34--35, 2017.
Samarth Sinha, Ajay Mandlekar, and Animesh Garg. S4rl: for offline reinforcement learning in robotics. In Conference on Robot Learning, pp. 907-917. PMLR, 2022.
Surprisingly simple self-supervision
Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. In Interna- tional conference on machine learning, pp. 5887-5896. PMLR, 2019.
Andrew Stier, Mare G Berman, and Luis Bettencourt. Covid-19 attack rate increases with city size. arXiv preprini 2tti::2003//07760 2020.
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojeiech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z Leibo, Karl Tuyls, et al. value-decommosittonn networks for cooperative multi-agent learning. arXiv preprint arXiv: / 1706.05266 2017.
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
11

---

Under review as a conference paper at ICLR 2023
Oriol Vinyals, Igor Babuschkin, Wojciech M Czamecki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David Н Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning, Nature, 575(7782)3350-33) 2019.
Jianhong Wang, Wangkun Xu, Yunjie Gu, Wenbin Song, and Tim C Green. Multi-agent reinforce- ment learning for active voltage control on power distribution networks. Advances in Neural Information Processing Systems,
2021a.
Tong Wang. Jiahua Cao, and Azhar Hussain. Adaptive traffic signal control for large-scale scenario with cooperative group-based multi-agent reinforcement learning. Transportation research part C: emerging technologies, 125:103046, 2021b.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3):279-292, 1992.
Yaodong Yang. Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang. Mean field multi- agent reinforcement learning. International conference on machine learning, pp. 5571-5580. PMLR, 2018.
Weirui Ye, Shaohuai Liu, Thanard Kurutach, Pieter Abbeel, and Yang Gao. Mastering atari games with limited data, Advances in Neural Information Processing Systems, 34:25476-25488, 2021.
Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu, The surprising effectiveness of ppo in cooperative, multi-agent games. arXiv preprint arXiv:2103.01955, 2021.
12

---

Under review as a conference paper at ICLR 2023
A TRAINING ALGORITHM
Here we show the step-by-ster training algorithm in Algorithm
Algorithm Multi-agent Training with GAT-MF
Require: Number of agents number of training episodes M, model update interval I, reward discount factor ty
Ensure: The trained multi-agent model
1:
Initialize actor networks R, initialize query (Q) networks Qa: Qa and key (K) networks Ka, Kes
the parameters
shared among the agents
2: Initialize the critic network Q
3: Copy т. Qa Qe, Ka, K., and get the corresponding target networks t, Ea. Se, Ka,
4: Copy Q and get the corresponding target network Q
5: Initialize the experience replay buffer B
6: for episode= = to M do
7: Initialize a random process N for action exploration
8: Initialize the environment and obtain the initial state 8 (s1, E S
9: fort to max- max-episode-lengiee do
10:
Calculate the Q vectors and K vectors of each agent:
de (s)), de (s(),,, K = (s)))
ky Ko);s)
11:
for j to do
Calculate the GAT weights for agent through the Q vectors and vectors: u/h (
1TTh kh & E N Calculate the local action with noise through GAT-ME: 0j (s3, 85) N, 8j U, ΣKENS wkk U, = KEAD wit
13:
end for
15:
Execute the joint action s' (s',..., ( E and the local one-step rewards (ri...,, rw)) R
(A1,...,,,, E A in the environment, observe the next state
16:
Store (s, a. r, 8²) into B reach the update interval then Sample random batch of experiences (s, a, r, s') from B
17:
18:
19:
for j= to n do
20:
Set yı = rj + (Q( , 8),, if àg') where as = +s/,, 8)), à=' = (af "'f',....da an'))
8/ the GAT-MF vector of s' with weights from de 2x(x)) and k!N² Ka(
3) the GAT-MF vector of s' with weights from de (s())) and i (c(
ay is the GAT-ME vector of à' with weights from oe and kgv2
Calculate Lj (yj - (s 5, ag, ā;))
8, is the GAT-MF vector of with weights from d! = =c(s)) and k. = Kc(SNN)
ā the GAT-MF vector of a with weights from gf and R-1"
22:
Calculate Jn- =Q(s), 8,, a3. ag) where af = T(, 83), a (af, an))
8, is the GAT-MF vector s with weights from df = (a))) and k.d" (a(ss))
ā; is the GAT-MF vector of a with weights from of 2o(s,) and h.V' Ko(sNs) end't for Update parameters of Q, Qe, Ke. minimizing L= -=E,1, Lj Update parameters of n, Qa; Kgg maximizing J E,
23:
24:
25:
26:
Update + ②., 2., Kr,, Kr, from parameters of n, 2., 2a, Ko. Kc via soft replace
27:
Update Q from parameters of Q via soft replace end if
29:
end for
30:
end for
31:
return The train models for execution π, Qay K.
13

---

Under review as a conference paper at ICLR 2023
B NUMERICAL RESULTS FOR THE BAR PLOTS
In this section, we provide numerical results the bar plots in Figure and Figure The numerical results of the bar plot in Figure BP shown in Table I
Table I: Numerical results of the bar plot in Figure 3p
Group
Method
Best Episode Return
DDPG
4.827
Global agent methods
PPO
1.846
SAC
1.934
MADDPG
0,841
CTDE MARL methods
MAPPO
7.359
Ablation study Our method
MF
9.156
GAT-MF
57.370
The numerical results of the bar plot in Figure 5C are shown in Table 2
Table 2: Numerical results of the bar plot in Figure
Group
Method
Best Episode Return
DDPG
-9127.401
Global agent methods
PPO
-9185.278
SAC
-9293.688
MADDPG
-9023.012
CTDE MARL methods
MAPPO
-9013.738
Ablation study Our method
MF
-6572.228
GAT-MF
-5162.126
The numerical results of the bar plots in Figure 5D are shown in Table
Table 3: Numerical results of the bar plot in Figure 5D
Method
Training Time (s)
GPU Memory (MB)
MADDPG 94041
53553
MAPPO
73208
27687
GAT-MF
9980
22379
14

---

Under review as a conference paper at ICLR 2023
C VISUALIZATIONS OF THE LEARNED POLICY IN EXPERIMENT 1
In this section, we provide more visualizations of the learned policy with different methods in ex- periment 1. We show the distribution of miners after applying the policy from a trained GAT-MF model, a trained ablation model, a trained MAPPO model, a trained MADDPG model, a trained SAC model, a trained PPO model, and a trained DDPG model for 1, 3, 5, 8, and 10 steps in Fig- ure/ō O We also visualize the learned attentions of some more actors at the first step from a trained GAT-MF model in Figure 7
D DETAILED BACKGROUND OF EXPERIMENT 2
In this section, we introduce more details of the background of the real-world vaccines-allocation experiment. The long-lasting global pandemic spreading of COVID-19 has caused countless damage to the social economy and people's s daily life. With the aim of better understanding the pandemic spreading dynamics, there exist many works modeling and simulating the COVID-19 pandemic spreading with various mathematical models and data sources (Chang et al. 2021a b Chen et al.) 2022). In this paper, we mainly conduct our experiments based on the Behavior and Demography informed epidemic model (BD model) (Chen et al., 2022), which is an improved version of the meta-population model (Chang al. 2021a).
In general, the BD model simulates the pandemic spreading inside the metropolitan statistical areas (MSA with the smallest unit of census block groups (CBG)) and points of interest (PO )- Typically, there are thousands of CBGs and more than ten thousand of POIs within one MSA. The BD model divides the pandemic spreading process into two parts, i.e., Intra-CBCC transmissions Inter-CBG transmissions, and models them respectively. For the Intra-CBG transmissions, it main- tains a local Susceptible-Expe Expolled---p-------e Exposed-Infecteed Remevvdd (SEIR) model in each CBG, where S denotes susceptible, E denotes exposed, denotes infected and R denotes removed. There is proportion of infected cases become reported cases and the proportion is decided by the testing capability. Only reported cases are observable while the rest of the infected cases are not observable. There are proportion of removed cases turn out to be deaths according to the infection fatality rate (IFR) in each CBG while others turn out to recover. As is known to us, the death rate is strongly related to age and thus the IFR is estimated by the population age structure of each CBG and age-specified death risks. On the other hand, the BD-model mainly models the Inter-CBG transmissions part based on the population mobility and contact network among CBGs and POIs. Inter-CBC transmissions hap- pen when susceptible individuals from certain CBG encounter infected individuals from another CBG when visiting a POI. The transmission probability varies among the POIs, which is positively related to people's average dwelling time a certain POI and is inversely proportional to the POI's floor space, reflecting the population density in such POI. The effect of vaccines on the transmission process is modeled as an equivalent reduction in the infection rate, which means the probability for susceptible individuals in certain CBG to be infected and turn into an exposed case in contact with infected individuals reduces proportionally to the percentage of vaccinated individuals in such CBG. We assume that an individual will obtain 100% immunity after one dose of vaccine injection for simplification this paper while the real-world situations of two-injection vaccines and < 100% immunity can be modeled with no essential difference by simply changing the parameters.
The required data of population mobility, i.c., how people from each CBG visit each POI and en- counter people from other CBGs, are originally captured by previous researchers from the Safe- Graph open date and are available online") [d (Chang et al. 2021a). In the study of BD-model, the researchers further process the data into suitable form to feed into the simulator. They have verified the accuracy of the BD model by comparing the simulation results by computers with the reported real-world situations. Results show that the model can reflect the real-world pandemic spreading situations precisely and thus we can conduct experiments based on it with confidence.
'Regions with relatively high population density and close economic ties throughout the area. 'The smallest geographical unit for which the bureau publishes sample data. *Specific locations that someone may find useful or interesting.
ht http:::/wwwwwwwwww//eeee wwg.aph.epppppccccmm com/
https://ccvidweeee wtw.sttttoodddd......
15

---

Under review as a conference paper at ICLR 2023
Retum==500 5.05
Return=15 15, 14
Retum=225 24
Retum=40.33
Return550.4
Number of Wanner
Bammo of
Retum=0.01
Retum=00.04
Retur=0.077
Retum=0.11
Retum=0,13
Number ME metts
Retum=1138
9.32
Nummoo Diamonds
Number of Mireers
Retum=0.00
Retum=0.00 00
Retur=00.00
Retum=0.00
Retum=0.00 0.00
Number Diamonos
Number Mirerrs
Return 0.45
Retum=1.78 1.78
Retum=0.75
Retum=2.38
Retum=2.66
Number of Mimerrs
Retum=1.14
Retum=2.94
Retur=é.55
Retum=5:36
Retum=4.45
Number Minneess
Retum=0.62
Retum= 1.87
Retum=3.122
Retum=4. .99
Retum=6.2
Number of Minners
Figure More visualizations of the learned policies. (A)-(G) The distribution of miners after applying the policy from trained GAT-MF model, a trained ablation model, trained MAPPO model, trained MADDPG model, a trained SAC model, a trained PPO model, and trained DDPG model for 1, 3, 5, 8, and 10 steps, from left-top to right-bottom, correspondingly.
16

---

Under review as a conference paper at ICLR 2023
0.5
1.65
1.30
0.4
Attention
1.20
0.3
1.05
0.90
0.75
0.45
0.0
0.30
0.5
1.65
1.50
0.4
135
er Daamo
Attention
1.20
0.3
1.05
0.90
0.75
0.45
0.0
0.30
Figure 7: More visualizations of the learned policies. The learned attentions of some more actors at first step from trained GAT-MF model. Since one panel cannot hold the attentions of all actors, show the attentions of four actors in each panel.
17


Reviews:
[{"review_id": "dfuj4_4P-1", "reviewer": "Reviewer_T6mP", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes to change the mean-field approximation of the Q function proposed by Yang et al., 2018 into a function that takes the weighted average of the neighbors’ actions rather than the simple average.  Weights measure the degree of interaction between an agent and its neighbors. These are computed at every timestep using an attention mechanism so that the weights can adapt to the current context. The method is shown to outperform the baselines in a grid world scenario and a more complex environment that simulates the problem of vaccine allocation during COVID-19.\n", "summary_of_the_review": "Overall, I think this paper is not ready for publication. My suggestion to the authors is to relax some of their claims (listing the result in Section 4.2 as a contribution is not appropriate in my opinion), try to position this work better in the literature, and add more baselines to the experiments so as to really demonstrate the benefits of the method.", "strength_and_weaknesses": "### Strengths\n\nThe paper is clearly written and the idea of modeling the strength of interaction between agents with an attention mechanism is interesting. The two environments used are \n\n### Weaknesses\n\nI don’t think it is fair to list the result in Section 4.2 (Weighted MF Approximation) as one of the main contributions of this paper. This is just a minor modification of the result from Yang et al., 2018 that includes the weights and whose proof follows trivially from the original result.  \n\nThe paper is not well-positioned in the literature. There are many missing references to relevant papers. This makes it very hard to properly assess the novelty of this work. A few of these papers are listed below:\n\n * Guestrin et al., 2002. Coordinated Reinforcement Learning.\n * Nair et al., 2005. Networked Distributed POMDPs: A Synthesis of Distributed Constraint Optimization and POMDPs.\n * Peter Sunehag et al., 2018. Value-Decomposition networks for cooperative multi-agent learning based on team reward.\n * Bohmer et al., 2020. Deep Coordination Graphs.\n *Oliehoek et al., 2021. A sufficient Statistic for Influence in Structured Multiagent Environments.\n\nIf I’m not mistaken the critics in MADDPG and MAPPO take as input the global state and the actions of all the other agents. If this is the case, the experiments are missing two baselines that I believe the method should be compared against:\n * A policy and value function that condition only on the pivot agent’s local states such as independent q-learning (Tan, 1993). This is meant to show that the neighbors' information is important and that the weighted mean-field approximation is really needed.\n * A policy and value function that condition on the pivot agent’s local states, and the neighbor agents’ actions and local states. This is meant to show that feeding the weighted mean-field approximation is more effective than just feeding the neighbors’ local states and actions.\n\n (Tan, 1993) MultiAgent Reinforcement Learning Independent vs Cooperative Agents.\n\n**Other questions/suggestions**\n\nIs the GAT learned end-to-end using the reward signal?\n\nAs far as I can see, the two environments are Dec-POMDPs since the agents’ receive only their own local states and the neighbors’ local states. In general, these are not Markovian. Don’t you need to condition the policy and value function on the action-observation history? Also, why does the policy condition on the neighbors’ local states but not their actions?\n\nI didn’t find any information about the experimental setup: number of random seeds, hyperparameter configurations… Are the results reported in Figures 3 and 5 averaged over different trials?\n\nThe paper states that the method requires the agents to have fixed relative positions. Is this the case in the grid-world task? Aren’t the miners moving independently?\n\n**Minor mistakes/typos**\n\nSpecify how the actions are represented. Are they one-hot encoding vectors? \n\nI believe the agent’s subscript is missing in equations (8) and (9). $Q_j(s,a)$ and $\\pi_j(s)$.\n\nIn Section 5.1 when you say “Gaussian distributions centered at the two grids” do you mean centered at the two “cells” that contain the diamond veins?\n\nIn Figure 3. Why do the contours show two peaks at (0,0) and at (9,9)? Aren’t there just two Gaussians centered at the diamond veins?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "QSG_nEkjRNG", "reviewer": "Reviewer_vFJW", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies multi-agent problems with a very large number of agents. In the past, such problems have been tackled using a combination of reinforcement learning and mean field approximations. This approach is valid provided the interactions between the players are homogeneous in the sense that every player interacts roughly in the same way with all the other players. Here, the authors consider a problem in which the interactions have some network structure, meaning that each agent may interact more with some agents rather than some others. To address this aspect, they propose to use graph attention networks. They first explain how to rewrite the Q-function using local information, then they design a graph attention mechanism and finally they conduct experiments on two examples, with up to thousands of agents. ", "summary_of_the_review": "I would recommend clarifying the comparison with the existing literature (so that we understand better the algorithmic contribution) and the theoretical contribution.", "strength_and_weaknesses": "Strength: (1) The beginning of the paper (motivations and part of the literature review) is quite clear. (2) The experiments show that the method can be used for a relatively large number of agents (a few thousands).\n\nWeaknesses: \n(1) References: It seems that there are already several papers on multi-agent problems using graph attention mechanism, such as (to cite just one example but I do not know if this is the most relevant one):\nMulti-Agent Game Abstraction via Graph Attention Neural Network, Liu et al., AAAI’20\nFurthermore, there is a growing literature on mean-field reinforcement learning or reinforcement learning for mean field games, whose goal is precisely to tackle games with a very large number of players. Given the similarities in key-words and goals, it could be relevant to mention the existence of this literature and the main similarities or differences. \n\n(2) Although (Yang et al., 2018) is very related to your work, I would recommend clarifying that the notion of solution is quite different. They consider a Nash equilibrium whereas you focus on a joint optimization problem. \n\n(3) “Theory 1” (“Theorem 1”?): In its current form, it is hard to get any insight from this result or to check its correctness. Indeed, any function “can be approximated” (to some degree) by any other function. Could you please make it more precise? It would be nice to provide a quantitative statement, and to spell out clearly the assumptions (e.g., on the Q function).\n\nTypos and minor questions:\nPage 3 and 4: In the model, what are the assumptions on the state and action space? Are they finite? If not, are they compact?\nPage 4: “possibility distribution” → “probability distribution”, “collection of possibility distribution” → “collection of possibility distributions”\nPage 5: “Theory 1” → “Theorem 1”\nPage 6: formula (15): Why are these “time-varying weights”?\nPage 7: “the rest parts” → “the other parts” \nPage 8: Figure 4: Is it correct that the DDPG method yields a higher reward than the GAT-MF method? Could you comment on this please?\nPage 9: Section 6.2: How is computed the “1.2B” in the expression “1.2B agent-environment interactions”?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "EcYa3ka5qOY", "reviewer": "Reviewer_cg8c", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper develops a multi-agent algorithm suitable for handling a large number of agents by means of the mean-field approximation.", "summary_of_the_review": "The paper develops a multi-agent algorithm suitable for handling a large number of agents by means of the mean-field approximation. The major contribution is utilising an attention mechanism to quality the strength of interactions. This is a very natural approach and likely to be beneficial. \n\nMy major concern is about empirical evaluation. The grid world environment, as far as I understood, does not include any form of interaction. Doesn't it factorise into $100$ of completely independent environments? \n\nQuestions and comments:\n - Is the methods for cooperative/mixed/competitive MARL?\n - I do not quite understand the statement of 'Theory 1'. What does it mean 'approximated'?\n - I am not sure what $\\mathcal{N}_j$  are used in the experiments. Can the authors clarify that?\n - The graph on Fig 3 is hard to read. Also, \"Best episode return\" is a somewhat unusual metric.\n - The method seems not very stable. It is not unusual for MARL trainings; however, the paper would benefit from some discussion or more experiments with this regard.", "strength_and_weaknesses": "Strength:\n- an interesting and important problem\n- natural approach\n\nWeaknesses\n- poor empirical evolution", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject