VAST: Value Function Factorization with Variable Agent Sub-Teams
Authors: Thomy Phan
Fabian Ritz
Lenz Belzner
Philipp Altmann
Thomas Gabor
Claudia Linnhoff-Popien
Venue: NeurIPS 2021 Poster (2021)
Keywords: Multi-Agent Learning
Reinforcement Learning
Value Function Factorization

Abstract: Value function factorization (VFF) is a popular approach to cooperative multi-agent reinforcement learning in order to learn local value functions from global rewards. However, state-of-the-art VFF is limited to a handful of agents in most domains. We hypothesize that this is due to the flat factorization scheme, where the VFF operator becomes a performance bottleneck with an increasing number of agents. Therefore, we propose VFF with variable agent sub-teams (VAST). VAST approximates a factorization for sub-teams which can be defined in an arbitrary way and vary over time, e.g., to adapt to different situations. The sub-team values are then linearly decomposed for all sub-team members. Thus, VAST can learn on a more focused and compact input representation of the original VFF operator. We evaluate VAST in three multi-agent domains and show that VAST can significantly outperform state-of-the-art VFF, when the number of agents is sufficiently large.

VAST: Value Function Factorization with Variable Agent Sub-Teame
Thomy Phan'
Fabian Ritz!
Lenz Belzner"
Philipp Altmann'
Thomas Gabor!
Claudia Linnhoff-Pope Poniien
'LMU Munich
Technische Hochschule Ingolstadt thomy wwwppphan@ifi ifi, 1mu de
Abstract
Value function factorization (VFF) is popular approach to cooperative multi- agent reinforcement learning in order learn local value functions from global rewards. However, state-of-the-ee thrt-rr VFF is limited to a handful of agents in most domains. We hypothesize that this is due to the flat factorization scheme, where the VFF operator becomes performance bottleneck with increasing number of agents. Therefore, we propose VFF with variable agent sub-teams (VAST). VAST approximates factorization for sub-teams which can be defined in an arbitrary way and vary over time, e.g., to adapt to different situations. The sub-team values are then linearly decomposed for all sub-team members. Thus, VAST can learn on a more focused and compact input representation the original VFF operator. We evaluate VAST in three multi-agent domains and show that VAST can significantly outperform state-of-the-ar VFF, when the number of agents is sufficiently large.
Introduction
Many real-world problems can be defined as cooperative multi-agent system (MAS), where multiple autonomous agents collaborate to achieve a common goal like fleet management [20] 21), industry
4.0 99 29 43 or communication networks (26] [5]) Multi-agent reinforcement learning (MARL) seems promising to realize such cooperative MAS by learning local policies for each autonomous agent S 27 37 40). Multi-agent credit assignment is an important challenge, where all agents only observe a single global reward, which makes the deduction of individual agent contributions difficult, especially in large MAS with many agents. This can lead poor policies, since is unclear which agent policy needs to adapt to what extent order to improve global MAS behavior 6 10 39].
Value function factorization (VFF) via end-to-end deep learning is popular approach to MARL in order to address the credit assignment problem [31
39 [4). A centralized value function is learned from global rewards and factorized into local value functions, which can be used to realize
32
36
coordinated local policies via multi-armed bandits 32 40 or local actor-critic learning 30 38 45
Despite the popularity of VFF, most approaches have been only evaluated in domains with a handful of agents. We hypothesize that this is due the flat factorization scheme current VFF approaches (Fig. Tap. With an increasing number of agents, the centralized VFF operator becomes a performance bottleneck, where it gets difficult to provide sufficiently informative training signal for each agent.
To alleviate this performance bottleneck problem, we propose VFF with variable agent sub-teams (VAST). Instead of directly factorizing centralized value function for each agent, VAST approximates
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

0,,1
0c.2
0r.4
OL.5
0,
0,,2
0
0r.4
OL.5
Agent
Agent
Agent
Agent
Agent
Agent
Agent
Agent 3
Agent
Agent
(: a.,1) ( (alt Qu(rea o1,4) Qolresitea)
Q.(na. a.d) Qalraa oua) Qalmis aual Qetrea on.) Qatresioea)
Σ
Σ
Clatria (.
V
(a) Flat value function factorization for N agents
(b) Factorization for K agent sub-teams
Figure I: Illustration of different value function factorization schemes using factorization operator V. (a) Flat factorization directly based local values Q: per agent DD (b) Proposed factorization based on K < N = [D] sub-team values Q which are linearly decomposed into local values Q; per sub-team member j E Ge.k S D. Each agent sub-team Gt, x is defined by an assignment strategy explained in Section
factorization for agent sub-teams which can be defined in arbitrary way and vary over time, e.g., to adapt to different situations. The sub-team values are then linearly decomposed for all sub-team members illustrated in Fig. [b Therefore, VAST can learn more focused and compact input representation of the original VFF operator. Our contributions are as follows:
We formulate VAST and show that VAST maintains decentralizability like state-of-thhe VFF given any sub-team assignment and depending on the sub-team based VFF operator.
We propose a meta-gradient approach to optimize sub-team assignments in order to adapt and improve VAST. We also briefly discuss alternative sub-team assignment strategies.
We empirically evaluate different variants of VAST in three multi-agent domains and show that VAST can significantly outperform flat state-of-the of-the-rrt VFF approaches by alleviating the performance bottleneck problem, when the number of agents is sufficiently large.
Background
We model cooperative MAS as partially observable Markov game M = (D...,A.PR where D =
is a set of agents i, S is a set of states at time step i, A (At)ee is the set of joint actions a₂ = (aL,))ED {a,,1, ...: (r,N). ((5 at) is the transition probability, = R(s,, az) E IR is the global reward, Z is a set of local observations 21,5 for each agent i, and ((st, ox) 2++1= (2411)eDD z is the subsequent joint observation. Each agent maintains local history Te, E AA)) and Tt (TI,))EE is joint history. T(a (T.) = I D ग. (a,, (r,)) is the (joint) action probability of joint policy where n. is the local policy of agent i. π can be evaluated with a value function QT (st, az)
F. [s, ar), Vs: E &S,aa, is the return with E [0. 1). The goal is to find an optimal joint policy x* (-, HeD with Q
A. where R² D r'ettc
max, Q If Q* is known, then x² can be obtained by greedily maximizing Q"
Note: Expressions of the form (ei)iez denote unordered sets, where e; mapped exactly one identifier (e.g., an agent) E I. Thus, we implicitly assume the order of agents to be irrelevant.
2.1 Independent Learning of Value Functions
Q' can be approximated independently by each agent E D using naive decentralized MARL on de.a
and Tτ, [10 18 40). These local approximations Q: ~ Q" can used to realize local polices n or actor-critic learning with Q; as critic [10]. Independent Learning (II.) offers optimal scalability w.r.t. N but violates the Markov
for each agent by using, e.g., multi-armed bandits on Q 32 40
assumption due to non-stationarity caused by simultancously learning agents [[] 36).

---

2.2 Value Function Factorization
For many problems, training usually takes place in a laboratory or in simulated environment, where global information is available. State-of-thh thee---r-th---tttt art MARL exploits this fact to approximate a centralized value function Qior ~ Q", which conditions on joint histories 7 and joint actions a, (and optionally on global states 8t). However, Que is only required during training in order to realize local policies Tr, which can be used in a decentralized way because they only condition on the local history Te.
This paradigm is known as centralized training and decentralized execution (CTDE) 10 32
36)
Que can be factorized into local value functions (Qi)iED via VFF operator y as shown in Fig. la
(T, ax) (TQ)(TTT,,
(T,N,, (t,N))
In practice, V is realized with deep neural networks, such that (Qi) can be learned end-to-end via
backpropagation by minimizing the mean squared (A) (temporal difference) error 32 36
[39]
A
VFF operator is decentralizable when satisfying the IGM (Individual-Giie Sawiiiaall-l-ll----- Global-Max) such that 36
argmax as EA (nm az) (argmax Di O1)))eD
VDN (Value Decomposition Networks)
33
formulates VDN as linear sum such that
Qua ax) = V-Dn(-) = EiED Qi(Te,ú: C,,)), which satisfies the IGM for Qua and (Qi)ee [3).
QMIX 32 formulates V Oux as a nonlinear monotonic combination of (Qi)EeD with a mixing network. The mixing network is generated by hypernetworks (12) and has nonnegative weights to satisfy the monotonicity condition 6Qm. 2 0, Vi D maintain consistency w.r.t. the IGM aQ;
32 36). Weighted QMIX further improves QMIX by weighting the transition losses w.r.t. over- and underestimation of Qie 31
QTRAN 36
avoids the additivity and monotonicity constraints of VDN and QMIX respectively by formulating the more general VOTRAN, which aims to satisfy
Σ Ed Qna (Te, ae) + VTn(TT) 0, a a LED
(3)
0, a F a
where at (ari)iED = (ar, dr,N) with az,i = argmax a., Qi (Te,s, ae and VIn((Ts)
=
maxa, E.A Quar at) - LiED Qi(Te,i, (1,s), in order to be consistent w.r.t. the IGM.
3 Related Work
MARL is a long-standing research with rapid progress towards complex domains 3
40
42
Most state-of thethetrtttttt art approaches are based on CTDE to learn Que for actor-critic learning 10 22 or VFF (31 36 39 44). VFF approaches like VDN, QMIX, and QTRAN use a flat factorization scheme, where Q is directly factorized into (Q.)eeD as illustrated in Fig. Ia We introduce a hierarchical VFF approach based on agent sub-teams which can vary over time, e.g., to adapt to different situations. With that, we can improve performance in large MAS, where flat VFF approaches could fail due to becoming a performance bottleneck.
Prior work on hierarchical MARL has mainly focused on temporal abstraction, where the MAS attempts to solve tasks based on temporal subgoals roles (4 49 We focus on VFF applied to agent sub-teams, which can be regarded as an abstraction of agents. These abstractions or sub-teams can vary over time, depending on the sub-team assignment strategy which may be chosen arbitrarily.
Approaches based on coordination graphs enrich VFF with agent relationship information and focus on pairwise interactions of agents to learn local value functions II 19). The maximization of Q scales at least quadratically w.r.t. N based on the graph structure. Our approach simplifies VFF via agent abstraction and maximizes Que with linear complexity. The abstraction is based on variable agent sub-teams, which are not restricted to pairwise interactions.
There is some prior work on sub-team assignments and agent-based hierarchization in MAS: The rela- tionship between coordination, complexity, and performance depending on predefined organizational MAS structures was studied in
8 15 34 35 (20] proposed a contextual MARL framework for
3

---

fleet management, where the spatial environment is partitioned into fixed cells with locally assigned rewards and the number of agents per cell can vary over time. [16] proposed an attention-baa based mechanism for self-interested MAS to focus on different contextual information per agent in order to approximate Q. Mean field MARL was introduced in [50], where Qi learned based on the mean field approximation of the joint action of all neighbor agents, where the definition of "neighborhood" domain dependent. Different clustering approaches for agents, communication messages, etc. w.r.t. some similarity criteria have been proposed in |5 25 46). Our approach addresses the per- formance bottleneck problem of flat VFF approaches. can be used with any sub-team assignment strategy like random assignments, clustering, meta-learning to structure the MAS dynamically while satisfying the IGM for Qior and (QikeD like flat state-of-the-ar VFF approaches [32 36 39].
Unlike [16 20 [50], our approach does not depend on predefined local rewards per agent region but automatically approximates local value functions Qi from global rewards via sub-team hased VFF.
Value Function Factorization with Variable Agent Sub-Teams (VAST)
4.1 Variable Agent Sub-Teams
We now introduce VFF with variable agent sub-teams (VAST). Given a sub-team ratio yj E [ 1], VAST divides the set of agents DD into K = [n/N] S N agent sub-teams Gt.. E Ge of division
G: = (G..I...., (.........K)) Gt,x) x at every time step L. Each agent E D is assigned to exactly one sub-team
G1 by sub-team assignment strategy X' with distribution (k)i,, Tr st), E {1...., K} such that
K
U G.,K. Each sub-team Ge, can be regarded G.,E. S D. Ge G.W 0 if + k', and k=1
as temporary agent abstraction which selects sub-team actions af, (arJ)sea. based on all
sub-team members j Gt.k- The value function Q of G1 is computed via VoN on (Q))eG..
Qi,K(TE, ((,)) (Vvo(-)= Σ Q5(Te,:a
jEG.,
Despite the simplified approximation of QC in Eq. VEDN has two important advantages over nonlin- ear variants like Vi OMI and Vi oTraN, which would also satisfy the IGM for Q and (Q)) First, the sum of VnN has no fixed input dimen- sion, thus sub-team sizes may vary over time, e.g.. to adapt to different situations. Second, VVDV does not introduce new tunable hyperparameters, thus being more efficient to use. Therefore, we defer nonlinear approximations of Qú,, future work.
Algorithm Variable Agent Sub-Teams
1: procedure VA, V,, X, X,") :)
2: Initialize parameters of V. X, (QiNED
3: K + [n
4: for episode - 1, 1 do
5: Sample 81, observe 21
6:
for time step do
7:
a ~ (a) re, 2411 t R(si, (t),((()ss))))
8:
Que approximated from (Qf,)) using a VFF operator y according Eq. !
9:
8141 ~ P(*++1| 18,, az)
10:
for sub-team h +- K do
11:
Ge. + 0
Qua(Te, a.) V(QR a.)),....
12:
for agent E D do KN X(kkli,
Qi (Te, ((k) (5)
13:
14:
Ge Gr,UU
where K = [n,] specifies the input dimension of V. The computation hierarchy of Q based on VAST according to Eq. and 5 depicted in Fig. lb With that hierarchy, (QtheD can be learned end-to-end, e.g., via backpropagation by updating w.r.t. the mean squared (A) error.
15:
Ie + (G.,,,,, Gt,k) Q (T (f.)).a.))))))) t Eq VG&k
16:
17:
Update V, (Qi)ieD with TD(A)
18:
Update X' (e.g., Eq. 6
> optional
VAST is formulated in Algorithm I where M is the MAS, V is an IGM preserving VFF operator like V VDN. V WOMI.. or VOTRAN as listed in Section 2.2 to approximate Qu from (Q,k), G. X' is sub-team assignment strategy, and ( 1] is the sub-team ratio.

---

Table 1: Characteristics of different sub-team assignment strategies X. indicates the computational overhead per time step and agent i, when invoking X' (line 13 in Algorithm or updating X' (line in Algorithm if all other parameters (e.g., 1)) are constant.
The worst case complexity
Worst case
Domain
Approach
Description
complexity
knowledge
RRando
Random assignment with (kkiii Tr,a, 8t) = K
O(1)
None
Xrixed
Fixed assignment with deterministic X'
O(1)
Agent IDs
Spatial
Espatial
Spatial clustering of agents to specify X'
O(N9),0>1
information
AMetoGradd
Meta-gradient learning of (kili, Tr.i, 88) (Fq. 6)
O(N)
Optional
specifies the degree of input space compression of V. The smaller 1), the more compact the K 1, the factorization reduces to V(EieD Qi(Tr.i, (r.z)) Larger values of 1/ enable more exploration of the input space of V but at the cost of more compute, which increases linearly w.r.t. n, Furthermore, we suggest 1
input representation of V. In the extreme case of 17 (T, at) = ( vn)
N < <> 1 for large N to alleviate the original performance bottleneck problem of V.
To show that VAST maintains decentralizabiiltyy by satisfying the IGM for Qior and (QiNED for an arbitrary sub-team assignment strategy X, we formulate and prove Theorem !
Theorem 1. Given a MAS M = (D,S,A,P.R) R, 2, Q) at time step f, where each agent i D with local value function Qi is assigned to exactly one sub-team GL Gr for sub-team based VFF according to Eq. 3 If the IGM is satisfied for a factorization of the centralized value function Quo into sub-team value functions
via VFF operator V according to Eq. then the IGM is also satisfied for Quo and (Qi)EED for each agent E
D GG,1 U... U...UG..K
Proof. The factorization of Que into (Q via satisfies the IGM. Thus, the maximization of all Q maximizes Qiee such that āe (., where ã. argmax Qme ax) and at, argmax &g e(Ai)ea Qi,k (T t,k: (.p)) The factorization of Q into (Qi) via VDN (Eq. also satisfies the IGM such that a, = (Dt,i)sEG.... where بz,; = argmax 0,, EA, Qi(Te. a.s):
Mon Eg
(Tr, (E..))e D D.G.UUU..UG.. (Tr,))ED
G.,
Therefore, the set of greedy local actions of all agents (at,))iD (a,, ax,) at maximizes Que for any sub-team assignment according to the IGM in Eq. which is ensured by the whole hierarchy of VAST as illustrated in Fig. 1b
4.2 Sub-Team Assignment Strategies
According to Theorem I VAST ensures IGM consistency w.r.t arbitrary sub-team assignments. To enable adaptation to different situations, the assignment of sub-teams per time step can be regarded as decision making problem by using a meta-policy X to select sub-team assignments conditioned on states and agent information. X can be optimized w.r.t. some meta-objective performance of VAST. J represents a high-level objective like the return Rd as defined in Section 2 or some domain specific goal which can evaluated in an outer loop, e.g., line 18 in Algorithm
further improve
We propose the meta- grata-gradien based assignment strategy or meta-policy XatnnGrad inspired by [48]
XMouarrad is approximated with parameter vector 0, which is automatically optimized via gradient ascent on the meta-objective J(O) w.r.t. to the following estimated gradient:
g A(k, Te, st) V gglog (klj,, Te,1,
(6)
where A(k, i, Te,i, = Qk. Te.i, Tr,i, 8r) - Vi, Te.i. si) is the advantage of k for sub-team G..k E G given Te. and 8t. Q estimates the (expected) performance when selecting k given i, Tr, and st. V. represents a baseline function, which can depend on i, Tr,i, and s,, for variance reduction. The concrete definitions of Q and 1/ are based on J(Ø), which should correlate with the original target of Que and can optionally integrate domain knowledge. In this paper, estimate Á(k, i, Tr, st) by
5

---

Start
Offense/ Clashing
2
2
3
2
2
Flesing
(a) Worehouse/N= 16/ (layout)
(b) Warehouse/ 16) (agents)
(c) Battle|N=80)
Figure 2: Illustration of the Warehouse/N] and the Battle[N domain. (a) Work stations (orange cells) and drop off locations (cyan cells) in Warehouse/ 16). (b) All agents (red circles) need to pick up orders of 5 items by E {1, 2, 4] at the work stations and deliver them to the corresponding drop off locations according to (a) while avoiding stalling and collisions with other agents. (c) An army of learning agents (cyan circles) has fight another army of opponent agents (gray triangles).
Eo,,eA Te(Cr,,lT,)) as,s) to the expected local value of agent with value function Qi and local policy hi to avoid any additional domain dependencies. For simplicity, we propose on-policy training of AMenaGadd Further extensions to, e.g., off-policy training or enhanced exploration are left for future work.
setting Qk,, Tr,i, st) Rg to the return and Vi,, Tr.s, Tr,,,
Table lists some alternative sub-team assignment strategies for comparison: XRandome assigns each agent to a random sub-team every time step. while Xixed permanently assigns each agent particular sub-team based on its ID. XSputial uses spatial information like coordinates to cluster agents order to form sub-teams. MeeuaGrad optimizes sub-team assignments w.r.t. some meta-objective to adapt to different situations and to further improve VAST. Xppatial and MMeaGGrad introduce additional computational overhead per time step and agent depending on N.
5
Experimental Setup
5.1 Evaluation Domains
To assess the scalability of VAST in comparison with flat VFF approaches, we focus on domains that can be easily scaled up to large numbers of agents N. Since common benchmarks like StarCraft are currently limited to N 30 agents [33), we defer an evaluation on these benchmarks future versions which support significantly more agents.
Warchouse[N] is a grid-world environment inspired by 8 43 and illustrated in Fig. 2a-b, where N agents or robots have to pick up randomly generated onlers of items by E 21,3,3, 4}, w {1...., 5} at work stations and deliver each item b., to its corresponding drop off location. where the drop off number according to Fig. 2a matches b All agents start at random work stations. After delivering all items of an order, the agent can return to any work station for a new order. All agents have a 5 field of view and are able to pick up and drop off their items if possible, move north, south, west, east, or do nothing. Agents cannot share positions or occupy obstacle cells. Delivered items and completed orders are rewarded with +1. Collisions with other agents are penalized with -0.5. At every time step, there is a time penalty of -0.01. An episode ends after 50 time steps.
Battle[N] is a grid-world environment inspired by [52) and illustrated in Fig. 2c where an army of N learning agents has to fight another army of N opponent agents, which randomly move towards and attack all learning agents in sight. Each agent initially has 3 health points (HP;). which are recovered by 0.01 each time step when 0 < HP;- < 3. An agent dead or killed when HP; All agents have 7 X 7 field of view and are able to move north, south, west, east, do nothing, or attack one opponent occupying the same cell, resulting in the attacked opponent's loss of one health point. Successful attacks and kills are rewarded with +1. Attacking a cell without any opponent is penalized with -0.1 and being hit or killed by the opponent penalized with -0.5. An episode ends after 100 time steps or when all agents of an army have been killed.

---

completed orders
10
400
VASTON)
200
WAS
VAST(
100
-20
7.50E+05
1.00E+36
2.00
5:00E104
1000
steps
steps
sleps
(a) Warehouse|4]
(b) Battle[0]]
(c) GaussianSquecze/200
Figure 3: Average training progress of VAST with v E I. VDN, V QMIx V pTTRAN) MenaGrad and
7 2 Shaded areas show the 95% confidence interval. Legend in (a) applies to all plots.
[ is single-step multi-agent resource allocation problem introduced 14], where N agents have to coordinate their actions a, E A, {0,.... 9} to find the most efficient allocation ( Ei
The system performance is defined by GS(() = Çe - and μ and
domain dependent parameters, which we μ 400 and 200.
5.2 Learning Algorithms and Training
We implemented IL, QMIX, and QTRAN baselines. For VAST, we use the notation VAST(V, X' m) with VFF operator V E (LI V VDN, V VMMIx: V QITRAN (V approximates O = Q independently). sub-team assignment strategy X'
{NRRnddom Xrised Xspariat, MMetaGrai), and sub-team ratio ') E f1:2) (Algorithm 1p. We chose 4 as minimum value for because it is the smallest possible value for Warehouse[4]. Since value-based algorithms are highly sensitive w.r.t. the exploration decay schedule, we use Q; as critic for local actor-critic learning to realize ग.; in order to evaluate all approaches on common basis 30
1
Xixxed assigns each agent i to sub-team G.,, with k = (mod K) 1. X Kypoiial uses k-means clustering on the agents' (ar, v) positiios in Warehouse/NV // and Banle[N] with K centroids. If not stated otherwise, we assume the following defaults: v v OTRAN. X XMenaGrad
38 45).
We performed training runs for each MARL algorithm and report the domain-speciie performance, i.e., the number of completed orders in Warehouse[N], the kill count in Battle[N] (kills by opponent agents are counted negatively). and the system performance in GaussianSqueeze(N) respectively.
Further details on the training setup and the experiments are specified in Appendix A. and A.2.
6 Results
6.1
Comparison of Value Function Factorization Operators for VAST
We ran VAST with different VFF operators T E [V'.. VDN, v OMIx V VOTRAN) X = XMMetaaiaa and in Warehouse[4), Batrle[2O], and GqueseanSSuueeze2000) The results are shown in Fig. All variants show steady learning progress in all domains. VAST( (rRaa) performs best in Warehouse[4] and Battle[20]. CaussianSqueezz((000] all variants perform equally well.
6.2 State-of-the-Art Comparison
We ran VAST with different sub-team ratios 77 E ( 3. V = QTRAN, and = XMeenGraad in Ware- house[4], Battle/2O, and CeussianSQueezze2000 as well in larger instances, i.e., Warehouse/ 16], Battle[80), and GaussianSqueezel 800) (medium instances are shown in Appendix A.3.1) to compare the performance with QMIX, QTRAN, and II. shown in Fig. 4 In Warehouse[4], QTRAN makes slightly faster progress than VAST(7 = }). However in Warehouse[16], both VAST variants out- perform all baselines, which perform poorly. In Battle/2O), both VAST variants slightly outperform QMIX and QTRAN, but they perform significantly better in Battle[8O). In GaussianSqueezef/ (200], all CTDE approaches perform equally well, but both VAST variants clearly outperform all baselines in CaussianSqueezee8000 VAST(1 }) initially improves faster than VAST() = 2) in most domains but in Warchouse[16] and CaussianSSueeze(8000) VAST( 1) surpasses VAST(1 = f)) over time.
7

---

completed priters
10
VASTIn 3
aill count
VASTIN ++]
200
QMIX
OTTANN
100
-20
75 Mteps
1.00
2.00E+06
5:00E104
1.00
steps
sleps
(a) Warehouse|
(b) Battle[20]
(c) GaussianSqueeze/2200
150
completed
0-
1.00
25
-75
7.50E+05
1.50E406
1:00-006
2.00E+05
5,00E404
0000+005
(d) W1rehouse[16]
(e) Battle[80]
(1) GaussianSqueeze(8000)
Figure 4: Average training progress of VAST with E ( OTRAN and XMenGGrad as well as QMIX, QTRAN, and IL. Shaded areas show the 95% confidence interval. Legend in (a) applies to all plots. The full results of the state-of-the-arr comparison are shown in Fig. 8 in Appendix A.3.1.
6.3 Comparison of Sub-Team Assignment Strategies for VAST
We ran VAST with different X' E {RRandoms Xiised Sppotaal MeetoGrad) v V VOTTAN and in Warehouse[16) Battl/80). and GuussianSqueezee/0
to compare the performance with the respective best baselines from Fig. 4 in Section 6.2 X SSputial not tested in GaussianSqueeee(000) due to the lack of spatial information. The results are shown in Fig. [5] VAST(XMennrrad) performs best in all domains. In Batrle/80), VAST(XFFue)) is competitive and "AST(X)pttiaa)) are competitive to the best baseline. In Warehouse/ 16) and GaussianSqueeze all VAST variants clearly outperform the respective best baselines.
VAST(XMencCmn)) while VAST(XRandin)
We further examined the generated sub-teams of MeeaaGrad and XSpanil at different stages in Batrle/80] by visualizing all agents of the same sub-team with the same color in Fig. 6 In the early stage (Fig.
6ab. MMenoGrad generates cyan sub-team for agents that are rather far away from the opponent army and red sub-team which is rather close to it (with some prediction noise). In the middle stage (Fig. 6b). a yellow sub-team emerges, when both armies clash, which disappears later (Fig (cc) when the opponent army is significantly decimated, thus reverting back to the cyan and red sub-teams depending on the agent positions. Nsponial simply groups agents according to their spatial distances to each other with obvious relation to the danger of the current situation shown in Fig. 6d
Since the opponent army follows an offensive strategy, most learned policies adopted defensive strategy, where all agents group and defend themselves together like in Fig. O However, in some cases, VAST learned "splitting" strategy, where the army splits into a fleeing part to reduce overall deaths and offensive part that clashes with the opponent army increase the kill count as shown Fig. 2c The generated sub-teams the splitting strategy are shown Fig. 10 Appendix A.3.3.
Although 17 = would theoretically enable AMennGraa to assign agents to K 20 different sub-teams, only a few sub-teams are actually active or non-empty as indicated in Fig. 6a and Fig. 10a-c in Appendix A.3.3. XMexaGrud learns to focus on particular sub-teams in specific situations, thus only activates certain sub-teams to adapt on demand, e.g., as indicated by the yellow sub-team in Fig. (bb]
7 Discussion
We proposed VAST to approximate value function factorizations for agent sub-teams which can be defined in an arbitrary way and vary over time, e.g., adapt to different situations. The sub-team values are then linearly decomposed for all sub-team members. VAST learns more focused
8

---

150
VAST(Eunaa
VASTi
0-
completed
3
Baseine
-25
50
-75
7.50E+05
100
16
2.00E+06
5:00E
1.00E+05
steps
simps
slmps
(a) Warehouse/
(b) Battee[0]]
(c) GaussianSqueeze(8000
Figure 5: Average training progress of VAST with X E {ARandom: Risees Sputiall MettaGrad ). POTRAN-
and lj = a as well as the respective best baselines from Fig. in Section 6.2 Shaded areas show the 95% confidence interval. Legend in (a) applies to all plots.
1
and compact input representation of the original VFF operator, thus being able to better address the multi-agent credit assignment problem in larger MAS than flat state-of-the-art VFF approaches.
Our experiments show that VAST is able to learn with different VFF operators yr to improve performance in domains, where flat VFF approaches could fail to learn meaningful factorizations. This is clearly shown for QTRAN and VAST(V @oTAN))) in the large MAS instances Warehouse/ 16], Batrle[80], and G 800] in Fig. fi-f, where VAST ØIRAN) significantly outperforms QTRAN. The poor scalability of QTRAN confrrms the findings of previous works [23] 31 44) and
shows that VAST is an effective approach to significantly improve scalability. The difference between II. and VAST(Vn)) can already be seen in the small MAS instances Warehouse[4], Battle and GaussianSQueezze2000 2200, where II. lacks stability in Fig. 4p-c, while VAST nz) improves steadily in these domains as shown in Fig. 33-c. VAST can significantly outperform flat state-of-the-ar VFF approaches like QMIX and QTRAN by alleviating the performance bottleneck problem, when the number of agents is sufficiently large shown in Fig. 4-f and Fig. 5
VAST achieves competitive superior performance with arbitrary sub-team assignment strategies X' as shown in Fig. 5 which is supported by Theorem [ XMeesCraa is an adaptive approach, which optimizes sub-team assignments to further improve VAST. In Battle[80]. MMeuaGred able to meaningfully structure the MAS according to different situations, which might be more beneficial for VAST than just relying on simple domain dependent features like agent IDs 2 10 or spatial positions 20 55) as shown in Fig. G and 10 in Appendix A.3.3. However, MeeaaGrad introduces additional computational overhead, which scales linearly per agent w.r.t. N as stated in Table Furthermore, the learning quality strongly depends on the meta-objective definition of MMetaGraa [8]
In Fig. and Fig. 4r VAST(7 = ()) itself suffers from the performance bottleneck (but to much lesser extent than flat VFF), where VAST(1 = 1t) improves more stably and surpasses VAST(1 = })) over time, However, VAST(1) = })) is superior Battle/00] and performs better the early training stages in Warehouse[16]. In Fig. 9 in Appendix A.3.2, this is indicated by more exploration through a higher sub-team division diversity. Due to the potential performance bottleneck of v and the computational scaling w.r.t. 77. we recommend VAST for large MAS with & 1) < 1 for high efficiency and performance. self-tuning mechanism for 7) would be interesting for future work.
The linear approximation of sub-team values ensures flexibility w.r.t. sub-teams and makes additional hierarchization of sub-teams obsolete, due to the associative property of additions (e.g., (a b) (c+ d) a+ ++c++)) However, this might be too restrictive for some domains. Using nonlinear variants like recurrent neural networks 7 or transformers [28 41 could further improve flexibility and performance but requires more compute and yields higher complexity due to more hyperparameters. Thus, we defer an investigation on more flexible VAST schemes to future work.
8 Potential Negative Societal Impacts
The goal of our work is to realize autonomous systems solve complex tasks at large scale in distributed way as motivated Section | To foeus completely on the potential effects of our work, we refer to [47] for general overview regarding socictal implications of deep reinforcement learning.

---

0
(a) early, MMenarrrad
(b) middle, XitenGroa
(c) late, KatenCroad
(d) carly, Aspotil
middle, Asponsl
(f) late, Esporal
Figure 6: Visualizations of the generated sub-teams of Meeaatinad with rj = and &spaial with k-means clustering using 10 centroids at different stages (early, middle, late) in Batrle/80) after training. All learning agents (round circles) of the same sub-team have the same color.
VAST is CTDE approach with centralized training regime realize decentralized policies. These policies have common objective which might include bias of central authority and can cause harm to opposing parties, e.g., via discrimination or misleading information. Since we assume VAST to be trained in a laboratory or in simulation, the trained system might exhibit unsafe behavior when being deployed into the real world due to poor generalization, e.g., by causing traffic accidents. Depending on the choice of V X, and some computational overhead is added to the original VFF approach, which can be significant when scaling up. The generated sub-teams can potentially be used to evaluate and categorize living beings w.r.t. some assignment strategy X' and objective as shown in Fig. and 10 in Appendix A.3.3, which could lead to misuse or discrimination of particular groups.
As experimentally shown in the Battle/N] domain, VAST can be misused for real combat, e.g., in autonomous weapon systems realize coordinated and distributed strategies as demonstrated in Fig. and 10 in Appendix A.3.3. MAS trained with VAST can be assumed to be resilient w.r.t. single agent failures (e.g., agent deaths in Batrle[N], which can make human intervention (e.g.. shutting down the MAS by disabling single agents) difficult. Behavioral changes of single agents due to updates, failures, or malicious attacks could lead to unexpected emergent effects like adaptive sub-team reorganizations, which can cause, e.g., traffic jams, outages of critical infrastructure, or directly harm others, depending on the quality the learned policies and the common objective.
Acknowledgments and Funding Disclosure
We thank the members of the Mobile and Distributed Systems Group at LMU Munich. This project has received funding from the Bavarian Ministry of Economic Affairs, Regional Development, and Energy under the project "Innovationszentruum Mobiles Internet".
10

---

References
[1] Wendelin Bochmer, Vitaly Kurin, and Shimon Whiteson. Deep Coordination Graphs. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 980-991. PMLR, 13-18 Jul 2020.
[2] Craig Boutilier. Planning, Learning and Coordination in Multiagent Decision Processes. In Proceedings of the 6th conference on Theoretical aspects of rationality and knowledge, pages 195-210. Morgan Kaufmann Publishers Inc., 1996.
[3] Lucian Buçoniu, Robert Babuška, and Bart De Schutter. Multi-Agent Reinforcement Learning: Overview. Innovations in Multi-Agent Systems and Applications- pages 183-221. Springer, 2010.
[4] Kathleen M Carley and Les Gasser, Computational Organization Theory. Multiagent Systems:
A Modern Approach Distributed Artificial Intelligence, pages 299-330, 1999.
[5] Santhana Chaimontree, Katie Atkinson, and Frans Coenen. A Framework for Multi-Agent Based Clustering. Autonomous Agents and Multi-Agent Systems, 25(3):425-446, 2012.
[6] Yu-han Chang, Tracey Ho, and Leslie Kaelbling. All Learning is Local: Multi-Agent Learning in Global Reward Games. Advances in Neural Information Processing Systems, 16:807-814, 2003.
[7] Kyunghyun Cho, Bart Merriënboer. Dzmitry Bahdanau, and Yoshua Bengio. On the Properties of Neural Machine Translation: SSST-8, Eighth Workshop Syntax, Semanties and Structure in Statistical Translation, pages 103-111, 2014.
Approaches. In Proceedings of
[8] Jen Jen Chung. Damjan Miklić, Lorenzo Sabattini, Kagan Tumer, and Roland Siegwart. The Impact of Agent Definitions and Interactions on Multiagent Learning for Coordination. In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems, AAMAS '1,, page 7752-1760, Richland, SC, 2019. International Foundation for Autonomous Agents and Multiagent Systems.
[9] Daniel Claes, Frans Oliehoek, Hendrik Baier, and Karl Tuyls. Decentralised Online Planning for Multi-Robot Warehouse Commissioning, In Proceedings of the 16th Conference on Autonomous Agents and Multiagent Systems, AAMAS '17, page 492-500, Richland, SC, 2017. International Foundation for Autonomous Agents and Multiagent Systems.
[10] Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual Multi-Agent Policy Gradients. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1), Apr. 2018.
[11] Jayesh K Gupta, Maxim Egorov, and Mykel Kochenderfer. Cooperative Multi-Agent Control using Deep Reinforcement Learning. In Autonomous Agents and Multiagent Systems, pages 66-83. Springer, 2017.
[12] David Ha, Andrew Dai, and Quoe V Le. Hypernetworks. In International Conference Learning Representations, 2017.
[13] Sepp Hochreiter and Jürgen Schmidhuber. Long Short- TerrtTTemmaa Memory. Neural Computation, 9(35:1735 1997.
[14] Chris HolmesParker, M Taylor, Yusen Zhan, and Kagan Tumer. Exploiting Structure and Agent-Centric Rewards to Promote Coordination in Large Multiagent Systems. In Adaptive and Learning Agents Workshop, 2014.
[15] Bryan Horling and Victor Lesser. A Survey of Multi-Agent Organizational Paradigms. The Knowledge Engineering Review, 19(4):281-316, 2004.

---

[16] Shariq Iqbal and Fei Sha. Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 2961-2970, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
Crittic for Multi-Agent Reinforcement Learning, In
[17] Guillaume J Laurent, Laëtitia Matignon, Le Fort-Piat, et The World of Independent Learners is not Markovian. International Journal of Knowledge-hased and Intelligent Engineering Systems, 15(1):55-64 64, 2011.
[18] Joel Z Leibo, Vinicius Zambaldi, Marc Lanctot, Janusz Marecki, and Thore Graepel. Multi- Agent Reinforcement Learning in Sequential Social Dilemmas. In Proceedings of the 16th Conference on Autonomous Agents and Multiagent Systems, AAMAS '17, page 464-473, Richland, SC, 2017. International Foundation for Autonomous Agents and Multiagent Systems.
[19] Sheng Li, Jayesh K Gupta, Peter Morales, Ross Allen, and Mykel J Kochenderfer. Deep Implicit Coordination Graphs for Multi-Agent Reinforcement Learning. In Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems, AAMAS '21, page 764-772, Richland, SC, 2021. International Foundation for Autonomous Agents and Multiagent Systems.
[20] Kaixiang Lin, Renyu Zhao, Zhe Xu, and Jiayu Zhou. Efficient Large-Scale Fleet Management via Multi-Agent Deep Reinforcement Learning. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. KDD '18, page 1774-1783, New York. NY, USA, 2018. Association for Computing Machinery.
[21] Jajjing Ling, Tarun Gupta, and Akshat Kumar. Reinforcement Learning for Zone Based Multiagent Pathfinding under Uncertainty. Proceedings of the International Conference on Automated Planning and Scheduling. 30(1):551-559 Jun. 2020.
[22] Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-Agent Actor-Critte Critic for Mixed Sysperative-Compttiin Environments. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[23] Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, and Shimon Whiteson. MAVEN: Multi- Agent Variational Exploration. In Advances in Neural Information Processing Systemx, vol- ume 32, Curran Associates, Inc., 2019.
[24] Rajbala Makar, Sridhar Mahadevan, and Mohammad Ghavamzadeh. Hierarchical Multi-Agent Reinforcement Learning. In Proceedings of the Fifth International Conference on Autonomous Agents, AGENTS '01, page 246-253, New York, NY, USA, 2001. Association for Computing Machinery.
[25] Elth Ogston, Benno Overeinder, Maarten Van Steen, and Frances Brazier. A Method for Decen- tralized Clustering in Large Multi-Agent Systems. In Proceedings of the Second International Joint Conference Autonomous Agents and Multiagent Systems, AAMAS '03, page 789-796. New York, NY, USA, 2003. Association for Computing Machinery.
[26] Frans Olichock and Christopher Amato. A Concise Introduction to Decentralized POMDPs, volume 1. Springer, 2016.
[27] Liviu Panait and Sean Luke. Cooperative Multi-Agent Learning: The State of the Art. Au- tonomous Agents and Multi-Agent Systems, 1133):387-434, November 2005.
[28] Emilio Parisotto, Francis Song, Jack Rae, Razvan Pascanu, Caglar Gulcehre, Siddhant Jayaku- mar, Max Jaderberg. Raphaël Lopez Kaufman, Aidan Clark, Seb Noury, Matthew Botvinick, Nicolas Heess, and Raia Hadsell. Stabilizing Transformers for Reinforcement Learning. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 7487-7498. PMLR, 13-18 Jul 2020.
12

---

[29] Thomy Phan, Lenz Belzner, Thomas Gabor, and Kyrill Schmid. Leveraging Statistical Multi- Agent Online Planning with Emergent Value Function Approximation. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS '18, page 730-738, Richland, SC, 2018. International Foundation for Autonomous Agents and Multiagent Systems.
[30] Thomy Phan, Lenz Belzner, Thomas Gabor, Andreas Sedlmeier, Fabian Ritz, and Claudia Linnhoff-Popien Resilient Multi-Agent Reinforcement Learning with Adversarial Value Decomposition. Proceedings of the AAAI Conference on Artificial Intelligence, 35(13): 1308-
11316, May 2021.
[31] Tabish Rashid, Gregory Farquhar, Bei Peng, and Shimon Whiteson. Weighted QMIX: Expand- ing Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 10199- 2020.
Curran Associates, Inc.,
[32] Tabish Rashid, Mikayel Samvelyan, Christian Schroeder. Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 4295-4304. PMLR, 10-15 Jul 2018.
[33] Mikayel Samvelyan, Tabish Rashid, Christian Schroeder de Witt, Gregory Farquhar, Nantas Nardelli, Tim GJ Rudner, Chia-Man Hung. Philip HS Torr, Jakob Foerster, and Shimon White- son. The StarCraft Multi-Agent Challenge. In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems, AAMAS '19, page 2186-2188, Richland, SC, 2019. International Foundation for Autonomous Agents and Multiagent Systems.
[34] Tuomas Sandholm, Kate Larson, Martin Andersson, Onn Shehory, and Fernando Tohmé Coalition Structure Generation with Worst Case Guarantees. Artificial Intelligence, 11 111(1):209- 238, 1999.
[35] Young-pa So and Edmund H Durfee. Designing Tree-Structured Organizations for Computa- tional Agents. Computational & Mathematical Organization Theory, 2(3):219-245, 1996.
[36] Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. QTRAN:
Learning to Factorize with Transformation for Cooperative Multi-Agent Reinforcement Learn- ing. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learn- ing Research, pages 5887-5896. PMLR, 09-15 Jun 2019.
[37] Peter Stone and Manuela Veloso. Multiagent Systems: A Survey from a Machine Learning Perspective. Autonomous Robots, 8(3):345-383, 2000.
[38] Jianyu Su, Stephen Adams, and Peter Beling. Value- Datop-Decomposition Multi-Agent Actor-Critics. Proceedings of the AAAI Conference on Artificial Intelligence, 35(13): May 2021.
[39] Peter Sunchag, Guy Lever, Audrunas Gruslys. Wojeiech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanetot, Nicolas Sonnerat, Joel Z. Leibo, Karl Tuyls, and Thore Graepel. Dettppeccomooiitionn Networks for Cooperative Multi-Agent Learning based on Team Reward. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 18, page 2085-2087 Richland, SC, 2018. International Foundation for Autonomous Agents and Multiagent Systems.
[40] Ming Tan. Multi-Agent Reinforcement Learning: Independent versus Cooperative Agents. In Proceedings of the Tenth International Conference on International Conference on Ma- chine Learning. ICML'93, page 330-337, San Francisco, CA, USA, 1993. Morgan Kaufmann Publishers Inc.
[41] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, F. ukasz Kaiser, and Illia Polosukhin. Attention is All You Need. In I. Guyon, U. V. Luxburg, Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
13

---

[42] Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaöl Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, al. Grand- master Level in StarCraft II using Multi-Agent Reinforcement Learning. Nature, pages 1-5, 2019.
[43] Qian Wan, Chonglin Gu, Sankui Sun, Mengxia Chen, Hejiao Huang, and Xiaohua Jia. Lifelong Multi-Agent Path Finding in Dynamic Environment. In 2018 1 15th International Conference on Control, Automation, Robotics and Vision (ICARCV), pages 375-882. IEEE, 2018.
[44] Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjie Zhang. QPLEX: Duplex Dueling Multi-Agent Q-Learning In International Conference on Learning Representations, 2021.
[45] Yihan Wang, Beining Han, Tonghan Wang, Heng Dong, and Chongjie Zhang. DOP: Off- Policy Multi-Agent Decomposed Policy Gradients. International Conference on Learning Representations, 2020.
[46] Xin Wen, Zheng-Jun Zha, Zilei Wang, Liansheng Zhuang, and Houqiang Li. CCNet: Cluster- Coordinated Net for Learning Multi-Agent Communication Protocols with Reinforcement Learning. In Jun Zhu and Ichiro Takeuchi, editors, Proceedings of The 10th Asian Conference on Machine Learning, volume 95 of Proceedings of Machine Learning Research, pages 582-597. PMLR, 16-16 Nov 2018.
[47] Jess Whittlestone, Kai Arulkumaran, and Matthew Crosby. The Societal Implications of Deep Reinforcement Learning. Journal of Artificial Intelligence Research, 70: 1003--00,,,,, May 2021.
[48] Zhongwen Xu, Hado P van Hasselt, and David Silver. Meta-Gradient Reinforcement Learning. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[49] Jiachen Yang. Igor Borovikov, and Hongyuan Zha. Hierarchical Cooperative Multi-Agent Rein- forcement Learning with Skill Discovery. In Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS '20, page 1566-1574, Richland, SC, 2020. International Foundation for Autonomous Agents and Multiagent Systems.
[50] Yaodong Yang, Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang. Mean Field Multi-Agent Reinforcement Learning. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 5571-5580 PMLR, 10-15 Jul 2018.
[51] Dayong Ye, Minjie Zhang, and Yun Yang. A Multi-Agent Framework for Packet Routing in Wireless Sensor Networks. Sensors, 100266000 2015.
[52] Lianmin Zheng, Jiacheng Yang. Han Cai, Ming Zhou, Weinan Zhang, Jun Wang, and Yong Yu. MAgent: A Many-Agent Reinforcement Learning Platform for Artificial Collective Intelligence. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1), Apr. 2018.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section
4 Hand
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
Section g
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? (es]] See Section and
(b) Did you include complete proofs of all theoretical results? [Yes] See complete proof below Theorem in Section
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or URL)? [Yes] Code and README are available at httttt::/ thub. com/
www..coottttt... thomyphan/ saaa/aallabbeaarrr.a
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Section J and Appendix A.I.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] All plots in Section o and Appendix A.3 display the 95% confidence intervals 30 independent random seeds.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Section [5.2 and Appendix 1.1.3. We provide the average runtime of each training run of the results in Section 6 and Appendix A.3 including hyperparameter tuning estimate the total amount of compute.
4. If you are using existing assets (e.g., code, data, models) or curating/releusing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A] We (re)immeeeetted all algorithms and environments by ourselves in order to fit our MARL interface. However, we cited all original works.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
Does not apply.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] Does not apply. Only simulated data from the domains described Section S was used.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] Does not apply. Only simulated data from the domains described in Section 5 was used.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A] Does not apply.
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A] Does not apply.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A] Does not apply.
15


Reviews:
[{"review_id": "si94QPj23nz", "reviewer": "Reviewer_t76M", "summary": "This method proposes a hierarchical decomposition for value function factorization methods which enables significantly greater scalability in terms of the number of agents.", "questions": "", "limitations": "", "rating": 5, "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": "# Strengths\n* The paper successfully addresses a significant shortcoming of a popular class of algorithms for deep MARL.\n* The scalability of the method with respect to agent quantities is particularly commendable.\n\n# Weaknesses\n* Section 4.2, on the meta-gradient method for learning $\\chi$, should be significantly expanded. Whereas the rest of the method is relatively straightforward, this part is a bit more subtle, and it would be good to read more on the motivation for and methodology behind this choice. In fact, the approach to learning $\\chi$ as described in this paper looks more like a straightforward policy gradient approach, rather than the cited meta-gradient method. The cited method is concerned with meta-learning a set of parameters that directly influence the objective function of the policy/value function; whereas, this paper is concerned with learning the parameters of $\\chi$, which can just be seen as additional parameters of the value function.\nIt's also not clear to me why $\\chi$ cannot simply be learned in an end-to-end manner where it is implemented, for example, as a differentiable sampling procedure via Gumbel-Softmax.\n* The authors do not evaluate on the StarCraft Multi-Agent Challenge [1], the standard benchmark for value function factorization-based cooperative MARL methods, nor do they compare to the most recent state-of-the-art in this field (QPLEX [2]). This omission suggests a lack of scalability to more complex non-gridworld domains.\n\n## Minor Points\n* Using $\\mathcal{D}$ to represent the set of agents is slightly confusing, as it is typically used to denote a replay buffer or dataset.\n* The methods section is a bit dense with respect to notation.\n\n# Questions/Comments\n* A recent approach, REFIL [3], proposes a method for extending QMIX to variable-sized teams via attention mechanisms as part of their approach. This may be worth looking into for future extensions of this work, such that the sub-teams may use a more expressive operator than VDN for their factorization scheme.\n* Lines 207-209 \"Since value-based algorithms are highly sensitive w.r.t. the exploration decay schedule, we completely omit exploration tuning and use $Q_i$ as critic for local actor-critic learning to realize $\\pi_i$ instead \" - this connection isn't quite clear to me. Actor-critic methods do not implicitly alleviate problems with exploration, they just deal with them differently (e.g. entropy penalty on the policies).\n\n# Overall Thoughts\nI like the main idea and motivation behind this paper, as scalability is a major concern for current MARL methods; however, I am a bit troubled by the lack of description in section 4.2. I am not very familiar with the cited meta-gradient method, and upon reading that paper, it is not clear how what is described in section 4.2 relates to that work. As such, I hope the authors can provide a more thorough explanation of this section in the rebuttal, such that I can evaluate their work more effectively.\n\n[1] Samvelyan, Mikayel, et al. \"The starcraft multi-agent challenge.\" arXiv preprint arXiv:1902.04043 (2019).\n\n[2] Wang, Jianhao, et al. \"QPLEX: Duplex Dueling Multi-Agent Q-Learning.\" International Conference on Learning Representations. 2020.\n\n[3] Iqbal, S., Witt, C. A. S. D., Peng, B., Böhmer, W., Whiteson, S., & Sha, F. Randomized Entity-wise Factorization for Multi-Agent Reinforcement Learning. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors could spend some time explaining why the approach does not scale to more complex domains (e.g. StarCraft).", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "ruSAp1Icu6B", "reviewer": "Reviewer_pyHL", "summary": "The paper introduces VAST, a framework to train decentralised MARL agents to each learn local policies from a single global reward. In contrast to VFF, where each agent calculates a local Q function which is then aggregated in a flat way into a total Q function to which Deep Q-Learning may be applied, VAST first assigns agents into variable-agent sub-teams, linearly aggregates the local Q function of each sub-team into a group Q function, and then aggregates the group function into a total Q function in the manner of VFF. The authors hypothesise that VFF underperforms with large numbers of agents due to a performance bottleneck that limits the information received by each agent, and empirically demonstrate a range of experiments where VAST achieves superior performance to flat versions of VFF when training large numbers of agents. They further discuss different ways of assigning agents to sub-teams, which may vary between time steps, and introduce an effective meta-gradient based approach.", "questions": "", "limitations": "", "rating": 7, "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": "Originality: This is a good, original work. It provides a novel variant of existing VFF techniques, building upon previous work while citing clearly.\n\nQuality: It is technically sound, and the performance of VAST is well-supported with clear experimental results. \n\nA major limitation is that there is insufficient discussion of the group ratio, and how this might be chosen. A key contribution of the work is the ability to scale VFF to larger numbers of agents, but the smallest group ratio considered is ¼, only a 4x decrease in the number of entities considered. It is likely that in settings with many agents we would want a significantly larger decrease. Eg, it would be instructive to see the case with just 2 or 3 sub-teams explored.\n\nClarity: The work is overall fairly well-written, well-organised and easy to follow. In particular, the background section was helpful and informative for putting the paper’s contribution into context. The experiments were well presented and clearly explained. A few points were unclear, as discussed below.\n\nSignificance: VAST outperforms previous approaches to VFF on MARL problems with large numbers of agents, a valuable contribution to an important problem. \n\nThe theoretical basis given for this work is shaky. The relative performance increases with larger numbers of agents, providing suggestive but not conclusive evidence for the hypothesis that this is due to a performance bottleneck. The authors should give more consideration to alternative explanations. Nevertheless, the empirical evidence for VAST is clear and persuasive.\n\nDetailed comments:\n- In 4.1 the ideal group ratio is described as $\\frac{1}{N} < \\eta \\ll N$. As $\\eta < 1 < N$, this is unclear, and $N$ should be replaced with $1$\n- The phrase “performance bottleneck” feels misleading, and when reading the abstract I interpreted the authors as arguing that VFF was computationally intractable with large numbers of agents, and that VAST would resolve this.\n- In 4.2 the discussion of the meta-gradients method for assigning teams was confusing, and could do with further detail, especially as we see that team assignment has a significant effect on performance. In particular: What does J mean, and how was this chosen? What are other reasonable choices of J, and how might this affect performance? How is $R_t$ included in calculations when this depends on the unknown future reward?\n- Theorem 1 seems correctly proven, but is rigorously stating and proving the simple statement that “as team Q functions are linear aggregations of agent Q functions, they are maximised iff agent Q functions are maximised, so the total Q function is maximised iff each agent Q function is maximised”. To aid in reader understanding, the theorem should be accompanied by a more intuitive description.\n- In Figure 6a-6c, $K=20$ yet only 2-4 groups are shown. The paper should clarify whether sub-teams are non-empty, and the impact on train time and performance of having many sub-teams with most empty vs having few sub-teams all non-empty.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss and acknowledge a range of possible negative societal problems, including use in autonomous weapons and traffic jams. I consider the most significant possible negative societal impact to be use in autonomous weapons, and would want to see a more detailed discussion of this. Eg, how often is MARL used today in autonomous weapons, and how much could this work further enable that?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "GEnZRKI1E_U", "reviewer": "Reviewer_2c76", "summary": "This paper proposes a novel value factorization method for multi-agent Q-learning based on team organization.\nTo enable automatic self-organization, this paper presents a meta-gradient-based approach to explore team structures.\nThe experiments demonstrate the proposed method can outperform baseline value factorization structures.", "questions": "", "limitations": "", "rating": 6, "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": "**Originality**: VAST is well embedded in the widely-used CTDE  paradigm, and its novelty is clearly discussed. To my knowledge, the proposed factorization method is novel.\n\n**Quality and Clarity**: The paper is well organized and easy to understand. Especially, Figure 1 is very clear and helpful to understand the proposed factorization structure.\n\n**Significance**: Overall, this paper is a good start and attempt to study team coordination in multi-agent reinforcement learning. However, I have a few technical concerns (see questions).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I am willing to increase my score if my concerns are addressed. (1) and (2) are my major concerns, and (3) is minor.\n\n(1) From my perspective, the concept of team coordination is a little bit weak in VAST. In general, VAST represents a subset of IGM factorization which focuses on individual execution. The selection of teams seems to only impact centralized training. In addition, I think it would be better to discuss some related work of coordination, such as deep coordination graph [1], and remark the differences from this paper.\n\n(2) I am not sure whether I understand section 4.2 correctly. The proposed meta-gradient-based approach seems to require on-policy training. Whether this component will limit the sample efficiency and scalability?\n\n(3) It is known that QTRAN may become unscalable in hard tasks, such as the StarCraft benchmark. It would be better to consider some more advanced techniques [2,3] and conduct more complex environments.\n\n*References*\n\n[1] Böhmer et al., Deep Coordination Graphs, ICML 2020.\n\n[2] Rashid et al., Weighted qmix: Expanding monotonic value function factorisation, NeurIPS 2020.\n\n[3] Wang et al., Qplex: Duplex dueling multi-agent q-learning, ICLR 2021.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "34Ry6d7T3bY", "reviewer": "Reviewer_bA39", "summary": "The paper takes a hierarchical approach rather than the now fairly common flat approach to factorizing joint value function for multiple agents in multi-agent reinforcement learning. Sub-team assignments can change for agents over time. Additionally, the paper explores different sub-team assignment strategies and proposes a meta-gradient based approach to optiize these assignments. The proposed method is compared against baselines that have a flat factorization on multiple grid-based domains and shown to outperform them especially as with increasing number of agents.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "**Strengths**\n\nThe paper is clearly written and the experiments are well done with results reported over 30 runs. Moreover the experiments go to about 80 coordinating agents unlike most other works in this domain. Unlike many papers, the delta difference at the end of training is quite substantial as the number of agents increases. Ablations with respect to different assignment strategies are quite useful even though they don't seem to matter always. The shared source code is fairly easy to follow as well, so kudos for that.\n\n**Weaknesses**\n\nBiggest weakness is the paper's lack of recognition of alternative value function factorizations based on ideas of coordination graphs [1,2,3]. These are not exactly flat, but can't be claimed to be hierarchical in this manner. But given the paper uses a different set of task domains than the other papers, it's difficult to infer the pros and cons of these different approaches. Nevertheless, at least some discussion is warranted. From the code it seems the assignment learning is another stochastic optimization problem that would likely become difficult with larger number of sub-teams and is not _just_ about linear scaling. That is possibly what is happening with Battle[80]. Some more discussion would be useful here. In general, the paper reports a bunch of results but doesn't try to figure out or given any intuition for why it could be happening. I understand that this is difficult and often not feasible with deep neural network based methods, but still some hypotheses would be useful!\n\n[1] W Böhmer et al. \"Deep Coordination Graphs\" https://arxiv.org/abs/1910.00091\n\n[2] S Li et al. \"Deep Implicit Coordination Graphs for Multi-agent Reinforcement Learning\" https://arxiv.org/abs/2006.11438\n\n[3] N Naderializadeh et al. \"Graph Convolutional Value Decomposition in Multi-Agent Reinforcement Learning\" https://arxiv.org/abs/2010.04740", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper goes in quite a bit detail in Sec. 8 for potential societal impact. As mentioned above an important thread from the literature is missing but otherwise the limitations are interspersed through the text.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers in most part recognise the novelty/originality of the presented approach.  The experiments, through which a strong  case is made for the scalability of the method to large number of agents, seem solid and competitive with state of the art. Some concerns raised by  Reviewer t76M about the clarity of section 4.2  on metagradient subroutine which needs to be addressed in the final version.
Decision: Accept (Poster)