VAST: Value Function Factorization with Variable Agent Sub-Teams
Year: 2021

Abstract:
Value function factorization (VFF) is a popular approach to cooperative multiagent 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.

heading: 1 Introduction
text: 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 [9, 29, 43], or communication networks [26, 51]. Multi-agent reinforcement learning (MARL) seems promising to realize such cooperative MAS by learning local policies for each autonomous agent [3, 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 to poor policies, since it is unclear which agent policy needs to adapt to what extent in order to improve global MAS behavior [6, 10, 39].
Value function factorization (VFF) via end-to-end deep learning is a popular approach to MARL in order to address the credit assignment problem [31, 32, 36, 39, 44]. A centralized value function is learned from global rewards and factorized into local value functions, which can be used to realize 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 to the flat factorization scheme of current VFF approaches (Fig. 1a). 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 a centralized value function for each agent, VAST approximates
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
a factorization for agent 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 as illustrated in Fig. 1b. Therefore, VAST can learn on a 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-the-art 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-art VFF approaches by alleviating the performance bottleneck problem, when the number of agents is sufficiently large.

heading: 2 Background
text: We model cooperative MAS as partially observable Markov game M = 〈D,S,A,P,R,Z,Ω〉, where D = {1, ..., N} is a set of agents i, S is a set of states st at time step t, A = 〈Ai〉i∈D is the set of joint actions at = 〈at,i〉i∈D = 〈at,1, ..., at,N 〉, P(st+1|st, at) is the transition probability, rt = R(st, at) ∈ R is the global reward, Z is a set of local observations zt,i for each agent i, and Ω(st, at) = zt+1 = 〈zt+1,i〉i∈D ∈ ZN is the subsequent joint observation. Each agent i maintains a local history τt,i ∈ (Z×Ai)t and τt = 〈τt,i〉i∈D is the joint history. π(at|τt) = ∏ i∈D πi(at,i|τt,i) is the (joint) action probability of joint policy π, where πi is the local policy of agent i. π can be evaluated with a value function Qπ(st, at) = Eπ[Rt|st, at],∀st ∈ S,∀at ∈ A, where Rt = ∑∞ c=0 γ
crt+c is the return with γ ∈ [0, 1). The goal is to find an optimal joint policy π∗ = 〈π∗i 〉i∈D with Qπ ∗ = Q∗ = maxπQ π . If Q∗ is known, then π∗ can be obtained by greedily maximizing Q∗.
Note: Expressions of the form 〈ei〉i∈I denote unordered sets, where ei is mapped to exactly one identifier (e.g., an agent) i ∈ I. Thus, we implicitly assume the order of agents to be irrelevant.

heading: 2.1 Independent Learning of Value Functions
text: Q∗ can be approximated independently by each agent i ∈ D using naive decentralized MARL on at,i and τt,i [10, 18, 40]. These local approximations Qi ∼ Q∗ can be used to realize local polices πi for each agent i by using, e.g., multi-armed bandits on Qi [32, 40] or actor-critic learning with Qi as critic [10]. Independent Learning (IL) offers optimal scalability w.r.t. N but violates the Markov assumption due to non-stationarity caused by simultaneously learning agents [17, 36].

heading: 2.2 Value Function Factorization
text: For many problems, training usually takes place in a laboratory or in a simulated environment, where global information is available. State-of-the-art MARL exploits this fact to approximate a centralized value function Qtot ∼ Q∗, which conditions on joint histories τt and joint actions at (and optionally on global states st). However, Qtot is only required during training in order to realize local policies πi, which can be used in a decentralized way because they only condition on the local history τt,i. This paradigm is known as centralized training and decentralized execution (CTDE) [10, 32, 36].
Qtot can be factorized into local value functions 〈Qi〉i∈D via a VFF operator Ψ as shown in Fig. 1a:
Qtot(τt, at) = Ψ(Q1(τt,1, at,1), ..., QN (τt,N , at,N )) (1)
In practice, Ψ is realized with deep neural networks, such that 〈Qi〉i∈D can be learned end-to-end via backpropagation by minimizing the mean squared TD(λ) (temporal difference) error [32, 36, 39]. A VFF operator Ψ is decentralizable when satisfying the IGM (Individual-Global-Max) such that [36]:
argmaxat∈AQtot(τt, at) = 〈argmaxat,i∈AiQi(τt,i, at,i)〉i∈D (2)
VDN (Value Decomposition Networks) [39] formulates ΨVDN as linear sum such that Qtot(τt, at) = ΨVDN(·) = ∑ i∈D Qi(τt,i, at,i), which satisfies the IGM for Qtot and 〈Qi〉i∈D [36].
QMIX [32] formulates ΨQMIX as a nonlinear monotonic combination of 〈Qi〉i∈D with a mixing network. The mixing network is generated by hypernetworks [12] and has nonnegative weights to satisfy the monotonicity condition δQtotδQi ≥ 0,∀i ∈ D to maintain consistency w.r.t. the IGM [32, 36]. Weighted QMIX further improves QMIX by weighting the transition losses w.r.t. over- and underestimation of Qtot [31]
QTRAN [36] avoids the additivity and monotonicity constraints of VDN and QMIX respectively by formulating the more general ΨQTRAN, which aims to satisfy∑
i∈D Qi(τt,i, at,i)−Qtot(τt,at) + Vtot(τt) = { = 0,at = at ≥ 0,at 6= at
(3)
where at = 〈at,i〉i∈D = 〈at,1, ..., at,N 〉 with at,i = argmaxat,i∈AiQi(τt,i, at,i) and Vtot(τt) = maxat∈AQtot(τt, at)− ∑ i∈D Qi(τt,i, at,i), in order to be consistent w.r.t. the IGM.

heading: 3 Related Work
text: MARL is a long-standing research area with rapid progress towards complex domains [3, 11, 40, 42]. Most state-of-the-art approaches are based on CTDE to learn Qtot for actor-critic learning [10, 22] or VFF [31, 32, 36, 39, 44]. VFF approaches like VDN, QMIX, and QTRAN use a flat factorization scheme, where Qtot is directly factorized into 〈Qi〉i∈D as illustrated in Fig. 1a. 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 or roles [24, 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 [1, 19]. The maximization of Qtot scales at least quadratically w.r.t. N based on the graph structure. Our approach simplifies VFF via agent abstraction and maximizes Qtot 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 relationship between coordination, complexity, and performance depending on predefined organizational MAS structures was studied in [4, 8, 15, 34, 35]. [20] proposed a contextual MARL framework for
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-based mechanism for self-interested MAS to focus on different contextual information per agent in order to approximate Qi. Mean field MARL was introduced in [50], where Qi is learned based on the mean field approximation of the joint action of all neighbor agents, where the definition of "neighborhood" is 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 performance bottleneck problem of flat VFF approaches. It can be used with any sub-team assignment strategy like random assignments, clustering, or meta-learning to structure the MAS dynamically while satisfying the IGM for Qtot and 〈Qi〉i∈D like flat state-of-the-art VFF approaches [32, 36, 39]. Unlike [16, 20, 50], our approach does not depend on predefined local rewards per agent or region but automatically approximates local value functions Qi from global rewards via sub-team based VFF.

heading: 4 Value Function Factorization with Variable Agent Sub-Teams (VAST)

heading: 4.1 Variable Agent Sub-Teams
text: We now introduce VFF with variable agent sub-teams (VAST). Given a sub-team ratio η ∈ [ 1N ; 1], VAST divides the set of agents D into K = dηNe ≤ N agent sub-teams Gt,k ∈ Gt of division Gt = 〈Gt,1, ..., Gt,K〉 at every time step t. Each agent i ∈ D is assigned to exactly one sub-team Gt,k by a sub-team assignment strategy X with distribution X (k|i, τt,i, st), k ∈ {1, ...,K} such that
Gt,k ⊆ D, Gt,k ∩ Gt,k′ = ∅ if k 6= k′, and D = K⋃ k=1 Gt,k. Each sub-team Gt,k can be regarded as temporary agent abstraction which selects sub-team actions aGt,k = 〈at,j〉j∈Gt,k based on all sub-team members j ∈ Gt,k. The value function QGt,k of Gt,k is computed via ΨVDN on 〈Qj〉j∈Gt,k :
QGt,k(τ G t,k, a G t,k) = ΨVDN(·) = ∑ j∈Gt,k Qj(τt,j , at,j) (4)
Algorithm 1 Variable Agent Sub-Teams 1: procedure VAST(M,Ψ,X , η) 2: Initialize parameters of Ψ, X , 〈Qi〉i∈D 3: K ← dηNe 4: for episode x← 1, T do 5: Sample s1, observe z1 6: for time step t do 7: at ∼ π(at|τt) 8: rt, zt+1 ← R(st, at),Ω(st, at) 9: st+1 ∼ P(st+1|st, at) 10: for sub-team k ← 1,K do 11: Gt,k ← {} 12: for agent i ∈ D do 13: k ∼ X (k|i, τt,i, st) 14: Gt,k ← Gt,k ∪ {i} 15: Gt ← 〈Gt,1, ..., Gt,K〉 16: QGt,k(τ G t,k, a G t,k)← Eq.4,∀Gt,k 17: Update Ψ, 〈Qi〉i∈D with TD(λ) 18: Update X (e.g., Eq. 6) . optional
Despite the simplified approximation ofQGt,k in Eq. 4, ΨVDN has two important advantages over nonlinear variants like ΨQMIX and ΨQTRAN, which would also satisfy the IGM for QGt,k and 〈Qj〉j∈Gt,k : First, the sum of ΨVDN has no fixed input dimension, thus sub-team sizes may vary over time, e.g., to adapt to different situations. Second, ΨVDN does not introduce new tunable hyperparameters, thus being more efficient to use. Therefore, we defer nonlinear approximations of QGt,k to future work.
Qtot is approximated from 〈QGt,k〉Gt,k∈Gt using a VFF operator Ψ according to Eq. 1:
Qtot(τt, at) =
Ψ(QGt,1(τ G t,1, a G t,1), ..., Q G t,K(τ G t,K , a G t,K)) (5)
where K = dηNe specifies the input dimension of Ψ. The computation hierarchy of Qtot based on VAST according to Eq. 4 and 5 is depicted in Fig. 1b. With that hierarchy, 〈Qi〉i∈D can be learned end-to-end, e.g., via backpropagation by updating Ψ w.r.t. the mean squared TD(λ) error.
VAST is formulated in Algorithm 1, where M is the MAS, Ψ is an IGM preserving VFF operator like ΨVDN, ΨQMIX, or ΨQTRAN as listed in Section 2.2 to approximate Qtot from 〈QGt,k〉Gt,k∈Gt , X is
a sub-team assignment strategy, and η ∈ [ 1N ; 1] is the sub-team ratio.
η specifies the degree of input space compression of Ψ. The smaller η, the more compact the input representation of Ψ. In the extreme case of η = 1N ⇒ K = 1, the factorization reduces to Qtot(τt, at) = Ψ(ΨVDN(·)) = Ψ( ∑ i∈D Qi(τt,i, at,i)). Larger values of η enable more exploration of the input space of Ψ but at the cost of more compute, which increases linearly w.r.t. η. Furthermore, we suggest 1N < η 1 for large N to alleviate the original performance bottleneck problem of Ψ. To show that VAST maintains decentralizability by satisfying the IGM for Qtot and 〈Qi〉i∈D for an arbitrary sub-team assignment strategy X , we formulate and prove Theorem 1: Theorem 1. Given a MAS M = 〈D,S,A,P,R,Z,Ω〉 at time step t, where each agent i ∈ D with local value function Qi is assigned to exactly one sub-team Gt,k ∈ Gt for sub-team based VFF according to Eq. 4: If the IGM is satisfied for a factorization of the centralized value function Qtot into sub-team value functions 〈QGt,k〉Gt,k∈Gt via a VFF operator Ψ according to Eq. 5, then the IGM is also satisfied for Qtot and 〈Qi〉i∈D for each agent i ∈ D = Gt,1 ∪ ... ∪Gt,K .
Proof. The factorization of Qtot into 〈QGt,k〉Gt,k∈Gt via Ψ satisfies the IGM. Thus, the maximization of all QGt,k maximizes Qtot such that at = 〈aGt,k〉Gt,k∈Gt , where at = argmaxat∈AQtot(τt, at) and aGt,k = argmaxaGt,k∈〈Ai〉i∈Gt,kQ G t,k(τ G t,k, a G t,k). The factorization of Q G t,k into 〈Qi〉i∈Gt,k via ΨVDN (Eq. 4) also satisfies the IGM such that aGt,k = 〈at,i〉i∈Gt,k , where at,i = argmaxat,i∈AiQi(τt,i, at,i):
at Ψ = 〈aGt,k〉Gt,k∈Gt ΨVDN,Eq.4 = 〈〈at,i〉i∈Gt,k〉Gt,k∈Gt D=Gt,1∪...∪Gt,K = 〈at,i〉i∈D
Therefore, the set of greedy local actions of all agents 〈at,i〉i∈D = 〈at,1, ..., at,N 〉 = at maximizes Qtot for any sub-team assignment according to the IGM in Eq. 2 which is ensured by the whole hierarchy of VAST as illustrated in Fig. 1b.

heading: 4.2 Sub-Team Assignment Strategies
text: According to Theorem 1, 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 a 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 J to further improve performance of VAST. J represents a high-level objective like the return Rt as defined in Section 2 or some domain specific goal which can be evaluated in an outer loop, e.g., line 18 in Algorithm 1.
We propose the meta-gradient based assignment strategy or meta-policy XMetaGrad inspired by [48]. XMetaGrad is approximated with parameter vector θ, which is automatically optimized via gradient ascent on the meta-objective J(θ) w.r.t. to the following estimated gradient:
g = Â(k, i, τt,i, st)∇θlogXMetaGrad(k|i, τt,i, st) (6)
where Â(k, i, τt,i, st) = Q̂(k, i, τt,i, st)− V̂ (i, τt,i, st) is the advantage of k for sub-team Gt,k ∈ Gt given i, τt,i, and st. Q̂ estimates the (expected) performance when selecting k given i, τt,i, and st. V̂ represents a baseline function, which can depend on i, τt,i, and st, for variance reduction. The concrete definitions of Q̂ and V̂ are based on J(θ), which should correlate with the original target of Qtot and can optionally integrate domain knowledge. In this paper, we estimate Â(k, i, τt,i, st) by
setting Q̂(k, i, τt,i, st) = Rt to the return and V̂ (i, τt,i, st) = ∑ at,i∈Ai πi(at,i|τt,i)Qi(τt,i, at,i) to the expected local value of agent i with value function Qi and local policy πi to avoid any additional domain dependencies. For simplicity, we propose on-policy training of XMetaGrad. Further extensions to, e.g., off-policy training or enhanced exploration are left for future work.
Table 1 lists some alternative sub-team assignment strategies for comparison: XRandom assigns each agent to a random sub-team at every time step, while XFixed permanently assigns each agent to a particular sub-team based on its ID. XSpatial uses spatial information like coordinates to cluster agents in order to form sub-teams. XMetaGrad optimizes sub-team assignments w.r.t. some meta-objective to adapt to different situations and to further improve VAST. XSpatial and XMetaGrad introduce additional computational overhead per time step and agent depending on N .

heading: 5 Experimental Setup

heading: 5.1 Evaluation Domains
text: 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 to future versions which support significantly more agents.
Warehouse[N] is a grid-world environment inspired by [8, 9, 43] and illustrated in Fig. 2a-b, where N agents or robots have to pick up randomly generated orders of 5 items bw ∈ {1, 2, 3, 4}, w ∈ {1, ..., 5} at work stations and deliver each item bw to its corresponding drop off location, where the drop off number according to Fig. 2a matches bw. 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× 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 i initially has 3 health points (HPi), which are recovered by 0.01 at each time step when 0 < HPi < 3. An agent i is dead or killed when HPi = 0. All agents have a 7 × 7 field of view and are able to move north, south, west, east, do nothing, or attack one opponent if 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 is penalized with -0.5. An episode ends after 100 time steps or when all agents of an army have been killed.
GaussianSqueeze[N] is a single-step multi-agent resource allocation problem introduced in [14], where N agents have to coordinate their actions at,i ∈ Ai = {0, ..., 9} to find the most efficient
allocation ζ = ∑N i=1 at,i. The system performance is defined by GS(ζ) = ζe −(ζ−µ)2
σ2 and µ and σ are domain dependent parameters, which we set to µ = 400 and σ = 200.

heading: 5.2 Learning Algorithms and Training
text: We implemented IL, QMIX, and QTRAN as baselines. For VAST, we use the notation VAST(Ψ,X , η) with VFF operator Ψ ∈ {ΨIL,ΨVDN,ΨQMIX,ΨQTRAN} (ΨIL approximatesQGt,k = Qtot independently), sub-team assignment strategy X ∈ {XRandom,XFixed,XSpatial,XMetaGrad}, and sub-team ratio η ∈ { 14 , 1 2} (Algorithm 1). We chose 1 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 Qi as critic for local actor-critic learning to realize πi in order to evaluate all approaches on a common basis [30, 38, 45]. XFixed assigns each agent i to sub-team Gt,k with k = i (mod K) + 1. XSpatial uses k-means clustering on the agents’ (x, y)-positions in Warehouse[N] and Battle[N] with K 2 centroids. If not stated otherwise, we assume the following defaults: Ψ = ΨQTRAN, X = XMetaGrad.
We performed 30 training runs for each MARL algorithm and report the domain-specific 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.1 and A.2.

heading: 6 Results

heading: 6.1 Comparison of Value Function Factorization Operators for VAST
text: We ran VAST with different VFF operators Ψ ∈ {ΨIL,ΨVDN,ΨQMIX,ΨQTRAN}, X = XMetaGrad, and η = 12 in Warehouse[4], Battle[20], and GaussianSqueeze[200]. The results are shown in Fig. 3. All variants show steady learning progress in all domains. VAST(ΨQTRAN) performs best in Warehouse[4] and Battle[20]. In GaussianSqueeze[200], all variants perform equally well.

heading: 6.2 State-of-the-Art Comparison
text: We ran VAST with different sub-team ratios η ∈ { 14 , 1 2}, Ψ = ΨQTRAN, and X = XMetaGrad in Warehouse[4], Battle[20], and GaussianSqueeze[200] as well as in larger instances, i.e., Warehouse[16], Battle[80], and GaussianSqueeze[800] (medium instances are shown in Appendix A.3.1) to compare the performance with QMIX, QTRAN, and IL as shown in Fig. 4. In Warehouse[4], QTRAN makes slightly faster progress than VAST(η = 12 ). However in Warehouse[16], both VAST variants outperform all baselines, which perform poorly. In Battle[20], both VAST variants slightly outperform QMIX and QTRAN, but they perform significantly better in Battle[80]. In GaussianSqueeze[200], all CTDE approaches perform equally well, but both VAST variants clearly outperform all baselines in GaussianSqueeze[800]. VAST(η = 12 ) initially improves faster than VAST(η = 1 4 ) in most domains but in Warehouse[16] and GaussianSqueeze[800], VAST(η = 14 ) surpasses VAST(η = 1 2 ) over time.

heading: 6.3 Comparison of Sub-Team Assignment Strategies for VAST
text: We ran VAST with different X ∈ {XRandom,XFixed,XSpatial,XMetaGrad}, Ψ = ΨQTRAN, and η = 14 in Warehouse[16], Battle[80], and GaussianSqueeze[800] to compare the performance with the respective best baselines from Fig. 4 in Section 6.2. XSpatial was not tested in GaussianSqueeze[800], due to the lack of spatial information. The results are shown in Fig. 5. VAST(XMetaGrad) performs best in all domains. In Battle[80], VAST(XFixed) is competitive to VAST(XMetaGrad) while VAST(XRandom) and VAST(XSpatial) are competitive to the best baseline. In Warehouse[16] and GaussianSqueeze[800], all VAST variants clearly outperform the respective best baselines.
We further examined the generated sub-teams of XMetaGrad and XSpatial at different stages in Battle[80] by visualizing all agents of the same sub-team with the same color in Fig. 6. In the early stage (Fig. 6a), XMetaGrad generates a cyan sub-team for agents that are rather far away from the opponent army and a 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 6c), when the opponent army is significantly decimated, thus reverting back to the cyan and red sub-teams depending on the agent positions. XSpatial simply groups agents according to their spatial distances to each other with no obvious relation to the danger of the current situation as shown in Fig. 6d-f.
Since the opponent army follows an offensive strategy, most learned policies adopted a defensive strategy, where all agents group and defend themselves together like in Fig. 6. However, in some cases, VAST learned a "splitting" strategy, where the army splits into a fleeing part to reduce overall deaths and an offensive part that clashes with the opponent army to increase the kill count as shown in Fig. 2c. The generated sub-teams of the splitting strategy are shown in Fig. 10 in Appendix A.3.3.
Although η = 14 would theoretically enable XMetaGrad 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-c and Fig. 10a-c in Appendix A.3.3. XMetaGrad 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. 6b.

heading: 7 Discussion
text: 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., to adapt to different situations. The sub-team values are then linearly decomposed for all sub-team members. VAST learns on a more focused
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 Ψ to improve performance in domains, where flat VFF approaches could fail to learn meaningful factorizations. This is clearly shown for QTRAN and VAST(ΨQTRAN) in the large MAS instances Warehouse[16], Battle[80], and GaussianSqueeze[800] in Fig. 4d-f, where VAST(ΨQTRAN) significantly outperforms QTRAN. The poor scalability of QTRAN confirms the findings of previous works [23, 31, 44] and shows that VAST is an effective approach to significantly improve scalability. The difference between IL and VAST(ΨIL) can already be seen in the small MAS instances Warehouse[4], Battle[20] and GaussianSqueeze[200], where IL lacks stability in Fig. 4a-c, while VAST(ΨIL) improves steadily in these domains as shown in Fig. 3a-c. VAST can significantly outperform flat state-of-the-art VFF approaches like QMIX and QTRAN by alleviating the performance bottleneck problem, when the number of agents is sufficiently large as shown in Fig. 4d-f and Fig. 5.
VAST achieves competitive or superior performance with arbitrary sub-team assignment strategies X as shown in Fig. 5, which is supported by Theorem 1. XMetaGrad is an adaptive approach, which optimizes sub-team assignments to further improve VAST. In Battle[80], XMetaGrad is 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, 50] as shown in Fig. 6 and 10 in Appendix A.3.3. However, XMetaGrad introduces additional computational overhead, which scales linearly per agent w.r.t. N as stated in Table 1. Furthermore, the learning quality strongly depends on the meta-objective definition of XMetaGrad [48]. In Fig. 4d and Fig. 4f, VAST(η = 12 ) itself suffers from the performance bottleneck (but to a much lesser extent than flat VFF), where VAST(η = 14 ) improves more stably and surpasses VAST(η = 1 2 ) over time. However, VAST(η = 12 ) is superior in Battle[80] and performs better in 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 Ψ and the computational scaling w.r.t. η, we recommend VAST for large MAS with 1N < η 1 for high efficiency and performance. A self-tuning mechanism for η 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+b+c+d). However, this might be too restrictive for some domains. Using nonlinear variants like recurrent neural networks [7, 13] 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.

heading: 8 Potential Negative Societal Impacts
text: The goal of our work is to realize autonomous systems to solve complex tasks at large scale in a distributed way as motivated in Section 1. To focus completely on the potential effects of our work, we refer to [47] for a general overview regarding societal implications of deep reinforcement learning.
VAST is a CTDE approach with a centralized training regime to realize decentralized policies. These policies have a common objective which might include bias of a 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 a 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 Ψ, 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. 6 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 to realize coordinated and distributed strategies as demonstrated in Fig. 6 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 Battle[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 to others, depending on the quality of 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 "Innovationszentrum Mobiles Internet".

Review summaries:
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.

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.

This paper proposes a novel value factorization method for multi-agent Q-learning based on team organization. To enable automatic self-organization, this paper presents a meta-gradient-based approach to explore team structures. The experiments demonstrate the proposed method can outperform baseline value factorization structures.