Multi-Agent Concentrative Coordination with Decentralized Task Representation

1 Introduction

Multi-Agent Reinforcement Learning (MARL) has attracted widespread attention [Du and Ding, 2021] and been applied in numerous domains, including sensor networks [Zhang and Lesser, 2011], autonomous vehicle teams [Zhou et al., 2020], and traffic signal control [Du et al., 2021]. To address the multi-agent system problems, a popular paradigm named Centralized Training with Decentralized Execution (CTDE) [Oliehoek et al., 2008a] is widely adopted, where agents' policies are trained with access to extra global information but executed only based on local information, including both policy gradient methods [Lowe et al., 2017;

∗Equal contribution.

†Corresponding author: Yang Yu.

Wang et al., 2020] and value-based methods [Sunehag et al., 2018; Rashid et al., 2018; Wang et al., 2021a], which demonstrate state-of-the-art performance on challenging tasks (e.g., StarCraft unit micromanagement [Samvelyan et al., 2019]). Despite their success, previous value-based MARL methods struggle in complex scenarios as they mainly consider designing a delicate mixing network but neglect the nearly decomposable structure of complex environments [Simon, 1991; Zhang, 2011; Sarkar and Debnath, 2012], such as agent-wise coordination patterns and agent-task relationships.

Efficient utilizing the environment structure plays a promising role in relieving the mentioned issue. Some researchers decompose the interaction structure among agents to improve coordination. CollaQ [Zhang et al., 2020] decomposes the local observation into different parts and employs a transformer architecture to capture the relationships between the ego agent and its teammates. RODE [Wang et al., 2021b] learns action representations and applies clustering methods to decompose joint action into restricted role spaces to reduce the policy search space. The mentioned methods of learning structure decomposition among agents can improve the coordination ability among agents but are still restricted as they seldom consider the task structure decomposability, a general property of real-world multi-agent systems [Oliehoek et al., 2008b; Kr¨uger, 2020]. For example, in the Factored Firefighting problem [Oliehoek et al., 2008b], several firefighters are assigned to some buildings on fire. The fire of different intensities are the factored state that can be taken as subtasks. Current methods ignore the task structure's decomposability and tacitly assume that the decentralized local policy can autonomously capture the relationship between agents and subtasks, resulting in low coordination efficiency. For example, in the StarCraft II micromanagement tasks [Samvelyan et al., 2019], agents with a sub-optimal policy may attack different enemies, while the optimal approach is to focus fire on a specific enemy to weaken the enemy forces rapidly. By learning useful representations for subtasks, agents can implicitly infer their teammates' intentions and form local groups to focus their energy on mutually beneficial subtasks.

Towards utilizing the task structure decomposability for efficient cooperation, we propose Multi-Agent Concentrative Coordination (MACC), a value-based MARL framework that follows the CTDE paradigm, with which agents can concentrate on most relevant subtasks, forming an implicit coordination pattern of agents based on local information. In MACC, an agent first learns a compact representation for each subtask via a subtask representation model, incorporating its belief about subtasks. During centralized training, the model is optimized to reconstruct the true state history based on the agent's local information. An attention mechanism is then used to obtain targeted weights for different subtasks. During the decentralized execution phase, MACC can build an integrated concentrative representation for subtasks based on local information and use it to augment the local policy.

We conduct extensive experiments on various cooperative multi-agent benchmarks, including level-based foraging [Papoudakis et al., 2021], predator-prey [Boehmer et al., 2020], and the StarCraft II unit micromanagement benchmark [Samvelyan et al., 2019], and compare our method against previous approaches, strong baselines, and ablations of our method. Experimental results show that MACC significantly improves the coordination ability among agents in complex scenarios, and visualization experiments furthermore indicate that MACC can learn meaningful coordination patterns. Careful ablation results further validate the efficacy of each component of our method.

2 Cooperative MAS with Task Decomposition

This paper considers a fully cooperative decomposable multiagent task where agents only have access to partial observations, which can be modeled as an extended factored DecPOMDP [Pajarinen and Peltonen, 2011]. The model is defined as M = ⟨N , S, {Ai}ni=1 , P, {Oi}ni=1 , Ω, R, γ⟩, where N = {1, . . . , n} is the set of agents, s ∈ S is the state from which agents can get local observation Oi ∈ Ω. With regard to decomposability, we consider the setting state can be represented as S = {[Si]i∈N , [Uj ]kj=1 , Senv}, where Si is the set of features of agent i, Uj is the set of features of subtask j (e.g., positions) and k is the number of subtasks. Senv stands for the information irrelevant of agents and subtasks. In order to relieve the partial observability problem, we add an RNN module, GRU [Cho et al., 2014], called agent trajectory encoder, to encode the history (o1i , a1i , . . . , ot-1 i , at-1 i , oti ) into τi, with ati ∈ Ai, oti ∈ Oi stand for the action and observation of agent i at time t. At each timestep, each agent selects an action ai ∈ A, forming a joint action a ∈ A = ∏ni=1 Ai, leading to the next state st+1 ∼ P(st+1|st, a) and getting a shared reward R(st, a). The formal objective is to find a joint policy π(a|τ) to maximize the global value function Qπtot (s, a) = Est,at [∑∞t=0 γ tR(st, at) | s0 = s, a0 = a, π] with γ indicates the discount factor.

Given a cooperative multi-agent task M = ⟨N, S, {Ai}ni=1 , P, {Oi}ni=1 ,Ω,R, γ⟩, a subtask mj contains ⟨Gj, Sj, {Ai}i∈Gj , P, {Oi}i∈Gj ,Ω,R, γ⟩, where Gj ⊆ N is the group of agents assigned to the subtask j, Sj = {[Si]i∈Gj , Uj, Senv}, and {Ai}i∈Gj , {Oi}i∈Gj are the action and observation spaces for the group of agents, respectively. In our setting, the overall task can be represented as different subtasks but the corresponding optimal groups of agents are usually unknown. If agents can learn to form different groups correctly and efficiently, the search space of targeted policies could be reduced [Zhang, 2011] and the learning efficiency can be improved.

3 Method

In order to realize the mentioned goal, we propose MACC, a novel value-based MARL framework that follows the CTDE paradigm to learn the proper coordination structure of agents and relieve the MARL miscoordination problem. Figure 1 provides an overview of our MACC framework.

As with most of the existing value-based MARL algorithms, MACC includes individual networks and a mixing network (Figure 1(a)). The individual networks are shown in Figure 1(c), and Figure 1(d) shows the detailed structure of the referred modules. We will introduce the state encoder (Figure 1(b)) module which is only used in centralized training in Section 3.1. Section 3.2 introduces the subtasks representation module that agents use in decentralized execution to capture the information about each subtask. Section 3.3 presents the module with which agents can learn a concentrative learned representation for subtasks and pay targeted attention to different subtasks so that agents can form an implicit coordination pattern to better cooperate.

3.1 Subtask State Encoding

During the centralized training process, we can decompose state st into different parts and adopt a GRU [Cho et al., 2014] module called subtask state encoder to encode subtask state history (u1j , . . . , utj ) into htj . MACC then takes the combination of the environment features stenv , the current state of each agent sti , and htj as input (Figure 1(a)) instead of the original state st as QMIX [Rashid et al., 2018] and QPLEX [Wang et al., 2021a] into the mixing network. During the decentralized execution process, the mixing network and subtask state encoder will be removed. Agents then use the learned subtask representations to anticipate each subtask's true history information based on local information.

3.2 Subtasks Representation Learning

To learn the relationship between the trajectory of a learning agent and each subtask j properly, we assume there exist some latent variables (or embedding) zt j that contain information about each subtask j, as well as an generative model pθ(htj | zt j ) that can reconstruct htj from zt j , with unknown parameters θ.

Then we seek to approximate the true posterior of p(zt j | htj ) from local information. However, agents have no access to subtask j's accurate history information htj during decentralized execution, so we seek to find a way to get the embedding vectors using only agents' local information. Benefiting from the strong ability of the deep neural networks to identify informative features from data, it is feasible for each agent to build a representation for each subtask from its local information even if there are times when some subtasks are invisible. Notice that agent i has an action-observation history until timestep t, denoted by τ t i , we then leverage τ t i to anticipate zt j with ˆ zt ij , which is the representation of agent i for subtask j. Formally, agent i inputs τ t i into qw, a subtask encoder with multiple fully connected layers parameterized with w, to learn {ˆ zt ij }kj=1 for subtasks. We denote the encoder as qw( ˆ zt ij | τ t i ) and use it to approximate the true posterior of p(zt j | htj ). Then the KL divergence of the true posterior from its approximation is calculated as:

The subtask encoder qw outputs parameters of an nmultivariate Gaussian distribution N(µtij ,σt ij ), where µtij and σt ij are mean and standard deviation, respectively. We then use the reparameterization trick to sample ϵ from a standard normal distribution, and then shift the sampled ϵ by the latent distribution's mean µtij and scale it by the latent distribution's variance σt ij . That is to say, ˆ zt ij = µtij + σt ij ⊙ ϵ, where ϵ ∈ N(0, I) and ⊙ represents the Hadamard product.

By following the variational inference theory [Kingma and Welling, 2014], Eq. 1 equals to minimize the representation loss function:

where pθ is the decoder with multiple fully connected layers to approximate the true generative model of subtasks. In the above equation, we can observe that the variational distribution depends only on local information. Under the CTDE paradigm, only the subtask encoder is required to generate representations of the subtasks during the testing period. The first term of Eq. 2 is the reconstruction loss (Rec Loss in Figure 1(d)) of the subtask state history information htj . The second term is the KL-divergence that ensures qw(ˆ zt ij | τ t i ) is similar to the prior distribution p(zt j ), where p(zt j ) is a standard normal distribution. This term is used to keep the representations of similar data points close together rather than separated in different regions of the encoding space. Then we sample the subtask representation ˆ zt ij from the multivariate Gaussian distribution with parameters µtij and σt ij during the training process.

3.3 Concentrative Subtask Representation

To cooperate more efficiently, each agent is expected to build a representation for each subtask and concentrate on relevant ones to adjust its policy accordingly and implicitly form a coordination pattern. We then adopt a simple attention mechanism [Vaswani et al., 2017] to select the most relevant subtasks for each agent. Formally, we calculate a weighted combination of the subtask representations:

Here, the sum of the weights ∑nj=1 αij is equal to one, and the value vij is the result of a linear transformation of the according representation by a shared value matrix Wv. The attention weight αij computes the relevance between the historical information τ t i and the related subtask representation ˆ zt ij , and we use the softmax operator to compute it:

where λ ∈ R+ is the temperature parameter set to 1 by default, Wq is a shared query matrix to transform τ t i into "query", andWk is a shared key matrix to transform ˆ zt ij into "key". Then, we use a Fully Connected (FC) layer which takes the concatenation of τ t i and xi as its input to calculate the individual Q-value function Qi(τi, ai).

3.4 Overall Optimization Objective

For the training object of our method, as MACC is agnostic to any value based MARL methods follow CTDE paradigm, here we take our original version based on QMIX to illustrate the optimization objective. MACC can be trained in an endto-end way, thus all parameters in the framework are updated with the gradients induced from the standard TD loss of reinforcement learning and the representation loss. To compute the global TD loss, individual utilities are fed into a mixing network whose output is the estimation of joint action-value Qtot, and the parameters of the mixing network are generated by a hyper-network conditioned on state st. Note that MACC decomposes it and encodes subtask state history information with a GRU. Hence the final learning objective to minimize is:

Here, LTD(θ) is the temporal difference loss, which equals to [r +γmaxa′ Qtot(s′ , a′ ; θ-) -Qtot(s, a; θ)]2 , where θare parameters of a periodically updated target network. λI is an adjustable hyperparameter to achieve a trade-off between the temporal difference loss and the summation of all agents' subtask representation learning loss. In our CTDE framework, the mixing network will be removed after the centralized training, thus only the learned subtask representation encoder, the attention module, and individual utility networks are used in decentralized execution.

4 Experiments

In this section, we evaluate MACC in several complex multiagent tasks 1 to answer the following questions: (1) Can MACC be applied to multiple existing MARL methods and improve their performance in complex scenarios? (Section 4.2) (2) What are the coordination structures learned by our method? (Section 4.3) (3) How do different components of MACC influence team cooperation? (Section 4.4)

For evaluation, we compare MACC with two value-based MARL baselines, VDN [Sunehag et al., 2018] and QMIX [Rashid et al., 2018], and three state-of-the-art multi-agent algorithms, CollaQ [Zhang et al., 2020], QPLEX [Wang et al., 2021a], and RODE [Wang et al., 2021b]. To ensure fair evaluation, we carry out all the experiments with five random seeds, and the results are shown with a 95% confidence interval. Detailed network architecture and hyperparameters choices are shown in Appendix. Note MACC is implemented on QMIX if not specified based on PyMARL 2 .

4.1 Environment

We evaluate the proposed method under environments where subtasks have different strategies (one immobile, one random moving strategy, and one fixed unknown strategy), including level-based foraging (LBF) [Papoudakis et al., 2021], predator-prey (PP) [Boehmer et al., 2020], and StarCraft II unit micromanagement benchmark (SMAC) [Samvelyan et al., 2019]. More detailed descriptions of these environments can be found in Appendix.

Level-Based Foraging (LBF)

LBF (Figure 2(a)) is a cooperative partially observable gridworld game, where the agents and the immobile foods (subtasks) are assigned with different levels and random positions at the beginning, the action space of each agent consists of the movement in four directions, loading food and a "none" action. Agents can coordinate to collect the food only if the sum of their levels is no less than the level of the food, then receive a normalized reward correlated to the level of the food.

1 Code available at https://github.com/DrZero0/MACC

2 Our experiments are all based on the PyMARL framework, which uses SC2.4.6.2.6923. Note that performance is not always comparable among versions.

Predator-Prey (PP)

PP (Figure 2(b)) is another partially observable grid-world task where m predators (agents) are trained to capture n randomly moving preys (subtasks). Agents get rewards only when there are no empty grids around the prey and at least two predators adjacent to it execute "catch" action concurrently, and miscatching would lead to a punishment of -2, this punishment makes it a challenging benchmark for current MARL methods.

StarCraft II Micromanagement Benchmark (SMAC)

SMAC (Figure 2(c)) is a popularly used combat scenario of StarCraft II unit micromanagement tasks, where we train the ally units to beat enemy units (subtasks) controlled by the built-in AI with an unknown strategy. At each timestep, agents can move or attack any enemies and get a global reward equal to the total damage done to enemy units. We test our method on 15 different maps. The detailed descriptions of this environment can be found in Appendix.

4.2 Competitive Results

Experiments are conducted in this part to show that MACC has superiority over multiple approaches on various benchmarks and is agnostic to multiple existing MARL methods.

Overall Performance Comparison

Figures 3 and 4 show the learning curves of different methods in the three multi-agent environments.

As shown in Figure 3(a), MACC outperforms all baselines in LBF. Our method yields a faster convergence speed than QPLEX and higher asymptotic performance than VDN on this benchmark where subtasks are immobile, demonstrating that MACC can efficiently help agents find targeted subtasks and achieve high cooperation ability.

Figure 3(b) exhibits that when we penalize the miscoordination action in a more complex environment with randomly moving subtasks, only VDN and MACC succeed in finding the optimal policy, VDN learns faster than MACC in this environment because the symmetry and linearity of VDN's mixing network make it good at tasks with similar structures. RODE fails in LBF and PP, indicating inappropriate role and subtask assignment may injure the coordination process. CollaQ works worse than QMIX in LBF and fails in PP, because the wrong value attribution decomposition causes inefficient coordination. In addition, QMIX and QPLEX's failures on PP indicate it is of no use for settling some miscoordination problems only with a complex mixing network. MACC

works on all the two benchmarks, manifesting that MACC is not restricted by these problems, and building a concentrative representation for subtasks can help improve coordination.

For more complex scenarios, we evaluate all methods on the mentioned SMAC environment. From Figure 4(d), we can find VDN gets the lowest averaged win rates, showing a simple addition of individual value functions cannot handle such complex settings. MACC gets lower win rates than QPLEX before 0.8M timesteps, which is because QPLEX's improved network representation capability makes it good at easy and medium maps at the beginning of training. Still, MACC outperforms all other methods gradually and exceeds nearly 10% median test win rate averaged across all 15 maps finally. We can also find that RODE specializes in super hard maps such as MMM2 (Figure 4(b)) and fails in some easy maps, but MACC works well on maps of all difficulty levels. CollaQ only has a slight advantage over QMIX on performance, indicating only local observation cannot capture the relationship between agents on complex maps like 1c3s5z vs 1c3s6z (Figure 4(a)). More results can be found in Appendix.

Integrating MACC into Different Methods

MACC is agnostic to specific algorithms, and we can integrate it into existing value function factorization methods. We apply MACC to VDN (MACC-VDN), QMIX (MACCQMIX), and QPLEX (MACC-QPLEX) and test them on maps including 2c vs 64zg and MMM2. The results are shown in Figure 5. As we can see, on the two maps, MACC-QMIX, MACC-VDN, and MACC-QPLEX all outperform their corresponding vanilla methods, indicating the learned concentrative representation for subtasks of MACC can significantly enhance coordination for various valuebased MARL methods.

(a) t-SNE projection at the start

(b) t-SNE projection at the end

Table 1: Relative reconstruction errors at different stages of an episode in three environments.

4.3 Coordination Structure Analysis

This section will show the subtask representation and the dynamic coordination pattern learned by our method.

Subtask Representations Visualization

We analyze the subtask representations learned by the encoder in the LBF environment, where four agents with levels 1, 2, 3, and 4, coordinate to collect three food with levels 3, 5, and 7 (Figure 2(a)). Figure 6 shows the results when we project the representation vectors on the three-dimensional plane using the t-SNE method [Van der Maaten and Hinton, 2008]. We can find the representations are chaotically distributed at the beginning but gradually belong to three clusters as agents better understand the subtasks at the end, indicating MACC can learn useful representations for different subtasks based on local information.

We further consider the reconstruction errors of our method in different settings (MMM2 for SMAC). Table 1 shows the averaged reconstruction errors of all agent-subtask pairs at specific time points in one episode, where "Start" means timestep t = 5, "End" means the timestep tend that the game ends, and "Middle" means t = ⌊ tend 2 ⌋. The reconstruction error is defined as the mean square errors between the true history information and the history information our method predicts of each subtask, and we use the maximum one in an episode to regularize the errors. It can be seen that at the beginning of each episode, the agents are unfamiliar with the subtasks, resulting in a relatively higher reconstruction error. As the game progresses, the agents can have more comprehensive information about the subtasks and reconstruct more precisely. In addition, the reconstruction errors are relatively low in LBF, especially at the end of an episode, which is because the subtasks in LBF are fixed during the game. On the contrary, the errors are higher in PP and MMM2. We guess it is because the subtasks are moving, making it challenging to model precisely.

Coordination Structure Learned by MACC

To investigate the coordination structure MACC learned, Figure 7 shows a visualization analysis on the attention weights of the agents in LBF. We use the same setting in the Subtask Representations Visualization part to keep the consistency of visualization experiments.

In the starting stage of one episode, as the representations are imprecise, agents pay equal attention to all subtasks. After some interactions with the environment, agents have more knowledge about the environment and move forward to collect the foods they are paying attention to (as shown in the middle), forming two different groups for two subtasks. Finally, the agent with level 3 completes the food collection with level 3 and starts to give attention to its next nearest food with level 7. The other three agents are still on their way to collect the food with level 7. The learned implicit coordination pattern validates the effect of MACC. After each agent builds representations for subtasks, it would use its action-observation history and the representations to calculate weights for the subtasks. The action-observation history contains information about its teammates so that the agent can utilize the information to infer which subtasks its teammates are heading for and concentrate on the subtasks that are most suitable for the teamwork, which helps agents group properly and achieve more efficient coordination patterns.

4.4 Ablation Studies

Finally, we design ablation studies for components of MACC on maps 3s vs 5z and MMM2 to answer the following questions: (1) Whether the effectiveness of MACC is due to the increase in the number of parameters? (2) Does the attention mechanism make sense? (3) Is the GRU that we add in the mixing network the reason our method works? (4) How does MACC perform when facing tasks can not be decomposed? The results are illustrated in Figure 8. To answer the question (1), when QMIX has an exact number of parameters as MACC (denoted as QMIX-LARGE), QMIX-LARGE improves performance someway but is still not comparable with MACC, proving that the increase in parameters is not the direct reason why MACC works. Moreover, removing the attention module (MACC w/o ATTEN replies to the question (2)) makes MACC fail to learn a good policy because, without an attention module, too many representation vectors enlarge the local policy and increase the learning complexity. QMIX-RNN corresponds to question (3), and the results illustrate that only using the history information in the mixing network can hardly improve performance. To investigate the adaptability of MACC (question (4)), we name this version MACC-INDEC as it learns a whole belief for all subtasks. We find MACC-INDEC can surpass QMIX but is inferior to MACC. It demonstrates that even when the task is indecomposable, our method also makes sense, showing strong adaptability. See Appendix for more ablation studies.

5 Conclusion

We propose MACC, a novel framework that utilizes the task structure decomposability to learn a decentralized concentrative subtasks representation for cooperative MARL, with which agents can concentrate on the most relevant subtasks for efficient coordination. Empirical results in multiple multiagent cooperative tasks show that our method significantly outperforms various baselines and can be integrated with existing value-based methods to improve coordination. We further design visualization experiments to investigate the coordination pattern learned by MACC, showing it can learn the dynamic coordination pattern of agents, enhancing coordination. Ablation studies validate the effectiveness of each component of MACC, and it can still facilitate coordination even faced with some scenarios where tasks are indecomposable. Further research on automatically decomposing the overall task and building more accurate representations for subtasks under POMDPs would be of great value.

Acknowledgements

We would like to thank Rong-jun Qin, Lanjihong Ma, Yu Fan, Yun-Tian Zhang, Cong Fu, and the anonymous reviewers for their helpful discussions and support. This work is supported by National Key Research and Development Program of China (2020AAA0107200), NSFC (61876077, 61876119), the Major Key Project of PCL (PCL2021A12), and Alibaba Group through Alibaba Research Fellowship Program.