Multi-Agent Collaboration via Reward Attribution Decomposition
Authors: Tianjun Zhang
Huazhe Xu
Xiaolong Wang
Yi Wu
Kurt Keutzer
Joseph E. Gonzalez
Yuandong Tian
Venue:  (2021)
Keywords: multi-agent reinforcement leanring
ad hoc team play

Abstract: Recent advances in multi-agent reinforcement learning (MARL) have achieved super-human performance in games like Quake 3 and Dota 2. Unfortunately, these techniques require orders-of-magnitude more training rounds than humans and don't generalize to new agent configurations even on the same game. In this work, we propose Collaborative Q-learning (CollaQ) that achieves state-of-the-art performance in the StarCraft multi-agent challenge and supports ad hoc team play. We first formulate multi-agent collaboration as a joint optimization on reward assignment and show that each agent has an approximately optimal policy that decomposes into two parts: one part that only relies on the agent's own state, and the other part that is related to states of nearby agents. Following this novel finding, CollaQ decomposes the Q-function of each agent into a self term and an interactive term, with a Multi-Agent Reward Attribution (MARA) loss that regularizes the training. CollaQ is evaluated on various StarCraft maps and shows that it outperforms existing state-of-the-art techniques  (i.e., QMIX, QTRAN, and VDN) by improving the win rate by 40% with the same number of samples. In the more challenging ad hoc team play setting (i.e., reweight/add/remove units without re-training or finetuning), CollaQ outperforms previous SoTA by over 30%. 

Under review as a conference paper at ICLR 2021
MULTI-AGENT COLLABORATION VIA REWARD ATTRI- BUTION DECOMPOSITION
Anonymous authors Paper under double-blind review
ABSTRACT
Recent advances in multi-agent reinforcement learning (MARL) have achieved super-human performance in games like Quake 3 and Dota 2. Unfortunately, these techniques require orders-of-magnitude more training rounds than humans and may not generalize to slightly altered environments or new agent configurations (i.e., ad hoc team play). In this work, we propose Collaborative Q-learning (CollaQ) that achieves state-of-the-an performance in the StarCraft multi-agent challenge and supports ad hoc team play. We first formulate aulti-agent collaboration joint optimization on reward assignment and show that under certain conditions, each agent has decentralized Q-function that is approximately optimal and can be decomposed into two terms: the self-term that only relies on the agent's own state, and the interactive term that is related to states of nearby agents, often observed by the current agent. The two terms are jointly trained using regular DQN, regulated with a M.MMli-Ageee gent Reward Attribution (MARA) loss that ensures both terms retain their semantics. CollaQ is evaluated on various StarCraft maps, outperforming existing ofate-of-the-aar techniques (i.e., QMI,, QTRAN, and VDN) by improving the win rate by 40% with the same number of environment steps. In the more challenging ad hoc team play setting (i.c., reweight/add/rrmove units without re-training or finetuning), CollaQ outperforms previous SoTA by over 30%.
INTRODUCTION
In recent years, multi-agent deep reinforcement learning (MARL) has drawn increasing interest from the research community. MARL algorithms have shown super-human level performance in various games like Dota 2 (Berner al., 2019). Quake 3 Arena (Jaderberg et al. 2019), and
StarCraft (Samvelyan et al. 2019). However, the algorithms (Schulman et al. 2017; Mnih et al. 2013) are far less sample efficient than humans. For example, Hide and Seek (Baker et al. 2011)) it takes agents 2.69 - 8.62 million episodes to learn a simple strategy of door blocking, while it only takes human several rounds to learn this behavior. One of the key reasons for the slow learning is that the number of joint states grows exponentially with the number of agents.
Moreover, many real-world situations require agents to adapt to new configurations of teams. This can be modeled as ad hoc multi-agent reinforcement learning (Stone al. (010)) (Ad-hoc MARL) settings, in which agents must adapt to different team sizes and configurations at test time. In contrast to the MARL. setting where agents can learn fixed and team-dependent policy, in the Ad-hoe MARL setting agents must assess and adapt to the capabilities of others to behave optimally. Existing work in ad hoc team play either require sophisticated online learning at test time (Barrett et al., 2011 prior knowledge about teammate behaviors (Barrett and Stone (015). As result, they do not generalize to complex real-world scenarios. Most existing works either focus on improving generalization towards different opponent strategies (Lanctot al. 2017, Hu al. 2020) or simple ad-hoe setting like varying number of test-time teammates (Schwab et a 2018 Long et al. (2020). We consider more general setting where test-time teammates may have different capabilities. The need to
reason about different team configurations the Ad-hoe MARL results in an additional exponential increase (Stone et al. 2010) in representational complexity comparing to the MARL setting.
In the situation of collaboration, one way to address the complexity of the hoc team play setting is to explicitly model and address how agents collaborate. In this paper, one key observation is that when collaborating with different agents, an agent changes their behavior because she realizes that the team could function better if she focuses on some of the rewards while leaving other rewards to other teammates. Inspired by this principle, we formulate multi-agent collaboration joint

---

Under review as a conference paper at ICLR 2021
optimization over an implicit reward assignment among agents. Because the rewards assigned differently for different team configurations, the behavior of an agent changes and adaptation follows.
While solving this optimization directly requires centralization at test time, we make an interesting theoretical finding that each agent has a decentralized policy that is (1) approximately optimal for the joint optimization, and (2) only depends on the local configuration of other agents. This enables us to learn direct mapping from states of nearby agents (or "observation" of agent to its Q-function using deep neural network. Furthermore, this finding also suggests that the Q-function of agent i should be decomposed into two terms: Qolone that only depends agent i's own state 8t, and Qpollab that depends on nearby agents but vanishes if no other agents nearby. To enforce this semanties, we regularize Qoollab (s:, = 0 in training via a novel Multi-Agen Reward Attribution (MARA) loss.
The resulting algorithm, Collaborative Q-learning (CollaQ), achieves 40% improvement in win rates over state-of-the-art techniques for the StarCraft multi-agent challenge. We show that (1) the MARA Loss is critical for strong performance and (2) both Qalnne and Qoolliab are interpretable via visualization. Furthermore, CollaQ agents can achieve ad hoc team play without retraining or fine-tuning. We propose three tasks to evaluate ad hoc team play performance: at test time, (a) assign a new VIP unit whose survival matters, (b) swap different units in and out, and (c) add or remove units, Results show that CollaQ outperforms baselines by an average of 30% in all these settings.
Related Works. The most straightforward way train such MARL task is learn individual agent's 's value function Q; independently((QL. (Tan 1993). However, the environment becomes non-stationary from the perspective of an individual agent thus this performs poorly in practice. Recent works, c.g., VDN (Sunchag et al. 2017). QMIX (Rashid et al., 2018). QTRAN (Son et al.) 2019), adopt centralized training with decentralized execution to solve this problem. They propose to write the joint value function as Q* = 6(s, (01, a1).... QK (ox. (ox,ak)) ax)) but the formulation of á differs in each method. These methods successfully utilize the centralized training technique to alleviate the non-stationary issue. However, none of the above methods generalize well ad-hoc team play since learned Q; functions highly depend on the existence of other agents.
COLLABORATIVE MULTI-AGENT REWARD ASSIGNMENT
Basic Setting. multi-agent extension of Markov Decision Process called collaborative partially observable Markov Games (Littman 1994), is defined by set of states S describing the possible configurations of all K agents, a set of possible actions A,,... ,,,, Ax. and a set of possible observations Oy...., ,Ox- At every step, each agent chooses its action a; by a stochastic policy πΙ : O, x A, - [0. 1]. The joint action a produces the next state by transition function P : S x A X
Ak + S.
All agents share the same reward r : S x A X x Ak + R and with a joint value function
Q- = E 1 [Ra|s,, ar) where R. === 7 Fe+j is the discounted return.
In Sec. 2. we first model multi-agent collaboration as a joint optimization on reward assignment: instead of acting based on the joint state s, each agent is acting independently on its own state s; following its own optimal value Vi, which is a function of the perceived reward assignment r While the optimal perceived reward assignment r (s) depends requires centralization, in Sec. 2.2 we prove that there exists an approximate optimal solution i; that only depends on the local observation sdocal of agent i, and thus enabling decentralized execution. Lastly in Sec. 2.. we distill the theoretical insights into a practical algorithm CollaQ, by directly learning the compositional mapping s/ncal + f. + V/2 in an end-to-end fashion, while keeping the decomposition structure of self state and local observations.
the joint state of all agents and
2.1 BASIC ASSUMPTION
naive modeling of multi-agent collaboration is to estimate a joint value function Vjoint := (s), (2.., sk), and find the best action for agent i to maximize Vjoint according to the However, has three fundamental drawbacks: (1) Vjoint generally requires exponential number of samples to learn; (2) in order to evaluate this function, a full observation of the states of all agents is required, which disallows decentralized execution, one key preference of multi-agent RL; and (3) for any environment/team changes (e.g., teaming with different agents), Visint needs to be relearned for all agents and renders ad hoc team play impossible.
current joint state (s1, ......, sK). .K))
Our CollaQ addresses the three issues with a novel theoretical framework that decouples the inter- actions between agents. Instead of using Vooint that bundles all the agent interactions together, we consider the underlying mechanism how they interact: in fully collaborative setting, the reason why
2

---

Under review as a conference paper at ICLR 2021
agent i takes actions towards state, is not only because that state is rewarding agent i, but also because more rewarding to agent than other agents the team, from agent i's point of view. This is the concept of perceived reward of agent i. Then each agent acts independently following its own value function V,, which is the optimal solution to the Bellman equation conditioned on the assigned perceived reward, and is a function of it. This naturally leads to collaboration.
We build mathematical framework model such behaviors. Specifically, make the following assumption on the behavior of each agent:
Assumption 1. Each agent has a perceived reward assignment r; IRlS:lAAal that may depend on the joint state ($1...., sK). ). Agent i acts according its own state s; and individual optimal value V, = (1() (and associated Qi(8;; 04; Tz)), which a function of r;.
Note that the perceived reward assignment r; R [ is non-negative vector containing the assignment of scalar reward at each state-action pair (hence its length is As)) We might also equivalently write it as a function: r: (z a) Sy x A; + I, where dummy variable that runs through all states of agent i, while s, refers to its current state.
S, and E A, Here r is
Given the perceived rewards assignment {r;), the values and actions of agents become decoupled.
Due to the fully collaborative nature, a natural choice of {r.} is the optimal solution of the following
objective ((1,, .2...... ., IK). Here r, is the external rewards of the environment, W; 2 0 is the preference of agent and @ is the Hadamard (element- wise) product:
K
K
FK) = E V((a)))))
s.t. Σ W.
(1)
Note that the constraint ensures that the objective has bounded solution. Without this constraints, we could easily take each perceived reward r, to +00, since each value function (ssar), monotonously increases with respect to r,- Intuitively, Eqn. T means that "assign" the external rewards re optimally to K agents as perceived rewards, so that their overall values are the highest.
In the case of sparse reward, most of the state-action pair (I, a), (e a) 0. By Eqn. for all agent i, their perceived reward ri (a, a) = O. Then we only focus on nonzero entries for each r,. Define M to be the number of state-action pairs with positive reward: M = Ea,eA. 1 (r, 0:) > 0}. Discarding zero-entries, we could regard all r; as M-dimensional vector. Finally, we define the reward matrix R = [ri.... .I.....,Ty rx] E R M
Clarification on Rewards. There are two kinds of rewards here: external reward ra and perceived reward for each agent r;. Te is defined to be the environmental reward shared by all the agents: Te : x A1 x.. A + R. Given this external reward, depending on specific reward assignment, each agent can receive a perceived reward ry that drives its behavior. If the reward assignment is properly defined/optimized, then all the agents can act based on the perceived reward jointly optimize (maximize) the shared external reward.
2.2
LEARN TO PREDICT THE OPTIMAL ASSIGNED REWARD (s)
The optimal reward assignments R of Eq. I as well as its i-th assignment r is function of the joint states s = {81, 82, 8K }. Once the optimization is done, each agent can get the best action at arg max.; (i az; r/] (S)) independently from the reconstructed function.
The formulation (((s;; r.) avoids learning the value function of statistically infeasible joint states V,(s). Since an agent acts solely based on r,, ad hoc team play becomes possible if the correct r, assigned. However, there are still issues. First, since each V, convex function regarding r,, maximizing Eqn. iis summation of convex functions under linear constraints optimization, and is hard computationally. Furthermore, obtain actions for each agent, we need to solve Eqn. a every step, which still requires centralization at test time, preventing us from decentralized execution.
To overcome optimization complexity and enable decentralized execution, consider learning direct mapping from the joint state s to optimally assigned reward r (s). However, since s a joint state, learning such mapping can be as hard as modeling (s(s.
Fortunately, Vi(s;; (s)) is not an arbitrary function, but the optimal value function that satisfies Bellman equation. Due to the speciality of V, we could find an approximate assignment F. for each agent so that r; only depends on local observation slocal of the states of nearby other agents
3

---

Under review as a conference paper at ICLR 2021
observed by agent d: (s) fs(ssora)). At the same time, these approximate reward assignments { achieve approximate optimal for the joint optimization (Eqn. I with bounded error:
Theorem 1. For all i {l,..., K}, all 8; E Si, there exists reward assignment f. that (1) only depends on s glocal and (2) i. is the i-th column of a feasible global reward assignment R such that
J(R) 2 (RR) - (r + Rmsx
(2)
where C' Can D are constants related to distances between agents/rewards (details in Appendix).
Since f. only depends on the local observation of agent (i.e., agent's state 8; as well as the states of nearby agents), it emables decentralized execution: for each agent i, the local observation is sufficient for an agent to act near optimally.
Limitation, One limitation of Theorem D is that the optimality gap of i; heavily depends on the size of s/ocal, If the local observation of agent i covers more agents, then the gap is smaller but the cost to learn such a mapping is higher, since the mapping has more imput states and becomes gigher-dimensione. In practice, we found that the observation of agent covers socca works sufficiently well, as shown in the experiments (Sec.
2.3 COLLARORATIVE Q-LEARNING (COLLAQ)
While Theorem. shows the existence of perceived reward i; = fs(sooca)) with good properties, learning it (s/soca)) is not a trivial task. Learning it in supervised manner requires (close to) optimal assignments the labels, which in turn requires solving Eqn. [ Instead, resort an end-to-end learning of Q: for each agent with proper decomposition structure inspired by the theory above.
To see this, we expand the Q-function for agent i: Q; = Qi(s;, az; ity) with respect to its perceived reward. We use Taylor expansion at the ground-zero reward Foz = (8:), which is the perceived reward when only agent i is present in the environment:
Qi a,; f.) = Qi(si, a;; ror) To:) + V.Qi(s;, a3 (f, roz) + Olli; roill
(3)
Qulone
Qcollab (glocsl,ag))
Here (s, a;; a;;Tos) ros) is the alone policy of an agent i. We name it Quione since it operates as if other agents do not exist. The second term is called Qcollab, which models the interaction among agents via perceived reward f,. Both Qulone and Qcuilaab are neural networks. Thanks to Theorem I we only need to feed local observation o, := s loccll of agent i, which contains the observation W K local agents (Fig. []. for an approximate optimal Qi Then the overall Q; is computed by simple addition (here of oflore := s; the individual state of agent i):
Qx(oi, a.) = Qulame (oolone ..s) + Ccollab (opalaaboo,,,))
(4)
Multi-Agent Reward Attribution (MARA) Loss. With a simple addition, the solution of Qplone and Qcollab might not be unique: indeed, we might add any constant to Qalone and subtract that constant from Qeollaa to yield the same overall Q, However, according to Eqn. 3 there is an additional constraint: if o; oflone then f. ro: and Qcollab (oşlone, a;) = O, which eliminates such an ambiguity. For this, we add Multi-agent Reward Attribution (MARA) Loss.
Overall Training Paradigm. For agent i, we use standard DQN training with MARA loss. Define y Egwne(r y max Qi(o', a²) [s, to be the target Q-value, the overall training objective is:
= Ee, (v Qi(os, az)) + (QQoollla gllone .a:))
DQN Objective
MARA Objective
where the hyper-parameter a determines the relative importance of the MARA objective against the DQN objective. We observe that with MARA loss, training is much stabilized. We use a soft constraint version of MARA Loss. To train multiple agents together, follow QMIX and feed the output of (Q+) into a top network and train in an end-to-end centralized fashion.
CollaQ has advantages compared to normal Q-learning. Since Q only takes oflone whose dimension is independent of the number of agents, this term can be learned exponentially faster than Quollab Thus, CollaQ enjoys much faster learning speed as shown in Fig. 5 Fig. 6 Bandd Fig.
4

---

Under review as a conference paper at ICLR 2021
Concet
Attontion2
Scalled Det Product Actention
GRU
Agents
Agent
Figure 1: Architecture of the network. We use normal DRQN architecture for of glone with attention- model for Qroilab, The attention layers take the encoded inputs from all agents and output an attention embedding.
Attention-based Architecture. Fig. [ illustrates the overall architecture. For agent i, the local observation 0; slocal is separated into two parts, of oglone == 8; and o; slocal Here, oglone is sent to the left tower to obtain Qulone, while o, is sent to the right tower to obtain Quollab, We attention architecture between oglone and other agents' states in the field of view of agent i. This is because the observation og can be spatially large and cover agents whose states do not contribute much to agent i's action, and effective s s/ocal is smaller than o;. Our architecture is similar to EPC (Long et al. 2020) except that we use a transformer architecture (stacking multiple layers of attention modules). As shown in the experiments, this helps improve the performance in various StarCraft settings.
Intuition of CollaQ and Connection to the Theory. The intuitive explanation to CollaQ and MARA Loss is that when the agent cannot see others (i.e., other agent has no influence on the particular agent), the Q-value Qi should equal to individual Q-value Qalone, This can interpreted as some equivalent statements: 1. The problem can be decomposed well into local sub-problems. 2. The existence of other agents does not influence the Q-value of the particular agent. The inspired MARA loss helps to climinate the ambiguity. The semantic meaning of Q and Q, are shown in Fig.
The intuition actually connects the theory. Theorem 1. shows that under some mild assumptions, the CollaQ objective can be viewed as a sub-optimal solution to an optimization problem on reward assignment. Thus each component of CollaQ and MARA loss can be well-justifidd. Although the problem defined Eq. [ is hard to optimize, the empirical success of CollaQ to some extent shows the effectiveness. The theory here serves more as an inspiration to the practical algorithm. We leave the analysis between exact optimization and CollaQ future work.
EXPERIMENTS ON RESOURCE COLLECTION
In this section, demonstrate the effectiveness of CollaQ in toy gridworld environment where the states are fully observable. We also visualize the trained policy Q, and Qalone
Ad hoc Resource Collection. We demonstrate CollaQ in a toy example where mul- tiple agents collaboratively collect resources from a grid world to maximize the aggre- gated team reward. In this setup, the same type of resources can return different re- wards depending
the type of agent that collects it. The reward setup is ran- domly initialized at the beginning of cach episode and can be seen by all the agents. The game ends when all the resources are col- lected. An agent expert for certain resource if it gets the highest reward among the team col- lecting that. As consequence, to maximize the shared team reward, the optimal strategy is to let the expert collect the corresponding resource.
Coloo
Truining Reward
"csting howard
300
300
Benard
250
For testing, we devise the following reward setup: We have apple and lemon our resources and N agents. For picking lemon, agent re- ceives the highest reward for the team, agent 2 gets the second highest, and so on. For apple, the reward assignment is reversed (agent N gets the highest reward, agent N gets the second
220
220
0.0
0.0
Figure Results in resource collection. CollaQ (green) produces much higher rewards in both training and ad hoc team play than (orange).
5

---

Under review as a conference paper at ICLR 2021
9
a)
Figure 3: Visualization of Qulone and Qi in resource collection. The reward setup is shown in the leftmost column. Interesting behaviors emerge: in b), Quallah reinforces the behavior of Qf since they both the expert for the nearest resources; in a) and c), Q alters the decision of collecting lemon for red agent since it has lower reward for lemon compared with the yellow agent and similar phenomena occurs for the yellow agent.
highest, ...). This specific reward setup is excluded from the environment setup for training. This is very hard ad hoc team play at test time since the agents need demonstrate completely different behaviors from training time to achieve a higher team reward.
The left figure in Fig. shows the training reward and the right one shows the ad hoc team play. We train on agents in this setting. CollaQ outperforms IQL in both training and testing. In this example, random actions work reasonably well. Any improvement over it is substantial.
we visualize the trained Qplone and Q, (the overall policy for agent i) to show how Quollaa affects the behaviors of each agent. The policies Qulonne and Qi learned by CollaQ are both meaningful: Qelone is the simple strategy of collecting the nearest resource (the optimal policy when the agent is the only one acting in the environment) and Q, is the optimal policy described formerly.
Visualization of Qolone and Q:- In Fig. 3
The leftmost column in Fig. 3 shows the reward setup for different agents on collecting different resources (c.g. the red agent gets 4 points collecting lemon and gets 10 points collecting apple). The red agent specializes at collecting apple and the yellow specializes at collecting lemon. In a), Qalone directs both agents to collect the nearest resource. However, neither agent the expert on collecting its nearest resource. Therefore, Qrallab alters the decision of Qullnne, directing Q; towards resources with the highest return. This behavior is also observed in c) with a different resource placement. b) shows the scenario where both agents are the expert on collecting the nearest resource. Qpollab reinforces the decision of Qalone making Q: points to the same resource as Qplone.
4 EXPERIMENTS ON STARCRAFT MULTI-AGENT CHALLENGE
StarCraft multi-agent challenge (Samvelyan et al.) 2019) is a widely-used benchmark for MARL evaluation. The task in this environment is manage a team of units (each unit is controlled by an agent) to defeat the team controlled by build-in AIs. While this task has been extensively studied in previous works, the performance of the agents trained by the SoTA methods (e.g.. QMIX) deteriorates with a slight modification to the environment setup where the agent IDs are changed. The SoTA methods severely overfit to the precise environment and thus cannot generalize well to ad hoc team play. In contrast, CollaQ has shown better performance in the presence of random agent IDs, generalizes significantly better in more diverse test environments (e.g., adding/wwaping/renoving unit test time), and more robust in ad hoc team play.
4.1 ISSUES IN THE CURRENT BENCIIMARK
In the default StarCraft multi-agent environment, the ID of each agent never changes. Thus, a trained agent can memorize what to do based on its ID instead of figuring out the role of its units dynamically during the play. As illustrated in Fig. if we randomly shuffle the IDs of the agents test time, the performance of QMIX gets much worse. In some cases (e.g., 8m__s__ (sm), the win rate drops from 95% to 50%, deteriorating by more than 40%. The results show that QMIX relies on the extra information (the order of agents) for generalization. As a consequence, the resulting agents overfit to the exact setting, making it less robust in ad hoc team play. Introducing random shuffled agent IDs at training time addresses this issue for QMIX as illustrated in Fig.

---

Under review as a conference paper at ICLR 2021
Traniing merformance GMX ned
Text performance OMX riiined Sand
performance 3MX trained
5m
Bm 3m
1.00
50m 12m
Teee W Ratt
Text Ratee
60-
40
20-
20-
0.0
0.5
2.5
2.0
0.0
0.5
30
1.5
2,0
0.0
0.5
3.6
2.0
Em rom Stops
Enwrr Steps
30d
Ensionment Stops
306
Figure 4: QMIX overfits agent IDs. Introducing random agent IDs at test time greatly affect the performance.
QTRAN
10L
QMX
Galao
Collao with Amtn
1.00
1000
100
Teat Wis Tahe
80-
Text Win Dants (PC)
80-
Text Wis Aatus
60-
40-
20-
20-
0.0
0.5
3.5
2.0
0.0
0.5
3.5
1.5
2.0
0.0
0.5
1.
15
2.
munmant Shaps
Enainomment Staps
Envoroement Steps
Text Wit Ratee 131
Text Pe
00-
Rutos
60-
46-
0.0
0.5
1.5
2.0
0.0
0.5
1.5
2.0
0.0
6.5
100
2.5
Steps
Figure 5: Results in standard StarCraft benchmarks with random agent IDs. CollaQ (without Attn and with Attn) clearly surpasses the previous SoTAs. The attention based model further improves the win rates for all maps except he_vs_6eee vs__4zg. which only has 2 agents and attention may not bring up enough benefits.
4.2 STARCRAFT MULTI-AGENT CHALLENGE WITH RANDOM AGENT IDs
Since using random IDs facilitates the learning of different roles, we perform extensive empirical study under this setting. We show that CollaQ on multiple maps in StarCraft outperforms existing approaches. We use the hard scenarios (e.g., 27m_vs____________ 30m, MMM2 and 2c_vs___ 64 zg) since they are largely unsolved by previous methods. Maps like 1 10m_vs Vs _is__v__iin _11m, 5m_ amnvs__ 6m and @m_vs__ 9m are considered medium difficult. For completeness, we also provide performance comparison under the regular setting in Appendix D Fig. T0 As shown in Fig. [ CollaQ outperforms multiple baselines (QMIX, QTRAN, VDN, and IQL) by around 30% in terms of win rate in multiple hard scenarios. With attention model, the performance is even stronger.
Trained CollaQ agents demonstrate interesting behaviors. On MMM2: (1) Medivac dropship only heals the unit under attack, (2) damaged units move backward to avoid focused fire from the opponent, while healthy units move forward undertake fire. In comparison, QMIX only learns (1) and is not obvious (2) was learned. On 2c_vs_64__ 64 CollaQ learns to focus fire on one side of the attack to clear one of the corridors. It also demonstrates the behavior retreat along that corridor while attacking while agents trained by QMIX does not. See Appendix D for more video snapshots.
4.3 AD HOC TEAM WORK
Now demonstrate that CollaQ is robust to change of agent configurations and/or priority during test time, i.e., ad hoc team play, in addition to handling random IDs.
Different VIP agent. In this setting, the team would get an additional reward if the VIP agent is alive after winning the battle. The VIP agent is randomly selected from agent 1 to N 7 1 during training. At test time, agent N becomes the VIP, which is a new setup that is not seen in training. Fig. 6 shows the VIP agent survival rate at test time. We can see that CollaQ outperforms QMIX by 10%-32%. We also see that CollaQ learns the behavior of protecting VIP: when the team is about to win, the VIP agent is covered by other agents avoid being attacked. Such behavior is not clearly shown in QMIX when the same objective is presented.
Swap/ / Add / Remove different units. we swap the agent type, add and remove one agent at test time. From Fig. [ we can see that CollaQ can generalize better to the ad hoc test setting. Note that to deal with the changing number of agents at test time, all of the methods (QMIX, QTRAN, VDN, IQL., and CollaQ) are augmented with
We also test the ad hoc team play in three harder settings:
7

---

Under review as a conference paper at ICLR 2021
QTRAN
VON
Callad)
Colleo with Alts
5m dm
1000
VNV1
100
am
Text Rants
Rancs 190
Text Whh Satex
60-
40
20
3.5
1.0
Envranment Steps
106
Envinemment. Stegs
1os
Environment Staps
Figure 6: Results for StarCraft ad hac team play using different VIP agent. At test time, the CollaQ has
substantially higher VIP survival rate than QMIX. Attention- based model also boosts up the survival rate.
CTRAN
OTTAAN
CTTAMM
VCN
VON With AOT
VOB with Jemn
Collad aQ with 6m7
2.0
2.0
2.8
0.
2.0
Figure 7: Ad hoc team play on a) swapping. b) adding. and c) removing a unit at test time. CollaQ outperforms QMIX and other methods substantially on all these 3 scttings.
Toa Tal Nalalo 190
20-
Text AD Daben
40-
Test WE
40-
40-
20
20
2.0 Environment Steps
Tmu mommmne Seps
Twe
Er mommme Steps
Teet
1ec
Figure 8: Ablation studies on the mixture of experts and the effect MARA Loss. CollaQ outperforms QMIX
with a mixture of experts by a large margin and removing MARA Loss significantly degrades the performance.
attention-basee based neural architectures for fair comparison. We can also see that CollaQ outperforms QMIX, the second best, by 9.21% 21% on swapping, 14.69% on removing, and 8.28% on adding agents.
4.4 ABLATION STUDY
We further verify CollaQ in the ablation study. First, we show that CollaQ outperforms a baseline (SumTwoNette that simply sums over two networks which takes the agent's 's full observation as the input. SumToNets s does not distinguish between Qalone (which only takes s; as the input) and Qeoilab (which respects the condition Q Qcollab(ss) (s.,-) = 0). Second, we show that MARA loss is indeed critical for the performance of CollaQ.
We compare method with SumIwoNets trained with QMIX in each agent. The baseline has similar parameter size compared to CollaQ. As shown in Fig. B comparing to SumIwoNets trained with QMIX, CollaQ improves the win rates by 17%-47% on hard scenarios. We also study the importance of MARA Loss by removing it from CollaQ. Using MARA Loss boosts the performance by 14%-39% on hard scenarios, consistent with the decomposition proposed in Sec. 2.3
RELATED WORK
Multi-agent reinforcement learning (MARL) has been studied since the 1990s (Tan 1993] Littman 1994. BB et al. 2008). Recent progresses of deep reinforcement learning give rise to an increasing
effort of designing general- purpose deep MARL algorithms (including COMA (Foerster et al.
2018). MADDPG (Lowe et al. 2017), MAPPO (Bemer et al. 2019). PBT (Jaderberg et al. 2019),
MAAC (Iqbal and Sha 2018). etc) for complex multi-agent games. We utilize the Q-learning
framework and consider the collaborative tasks in strategic games. Other works focus on different
aspects of collaborative MARL setting, such as learning communicate (Foerster et al. 2016
Sukhbaatar et al. 2016 Mordatch and Abbeel| 2018), robotics manipulation (Chitnis et al.
2019)
traffic control (Vinitsky et al. 2018), social dilemmas (Leibo et al. (2017), etc.
The problem of ad hoc team play multiagent cooperative games was raised the early 2000s (Bowl ing and McCracken] 2005| Stone et al. 2010) and is mostly studied in the robotic soccer do- main (Hausknecht et al. 2016). Most works (Barrett and Stone 2015 Barrett et al. 2012 Chakraborty
8

---

Under review as a conference paper at ICLR 2021
and Stone, 2013 Woodward et al. 2019) either require sophisticated online learning at test time or require strong domain knowledge of possible teammates, which poses significant limitations when applied to complex real-world situations. In contrast, our framework achieves zero-shol generalization and requires little changes to the overall existing MARL training. There are also works considering a much simplified ad-hoc teamwork setting by tackling varying number of test-time aistttime homogeneous agents (Schwab al. 2018 Long et al. 2020) while our method can handle more general scenarios.
Previous work on the generalization/robsstees in MARL typically considers a competitive setting and aims to learn policies that can generalize to different test-time opponents. Popular techniques include meta-learning for adaptation (Al-Shedivat et al. (017). adversarial training (Li et al.] 2019)). Bayesian
inference (He et al. 2016,) (Shen and How Jerrino et al. (2019). symmetry breaking (Hu et al.
2020 learning Nash equilibrium strategies (Lanctot al. 2017 Brown and Sandholm 2019) and
population based training (Vinyals et al.) 2019; Long et al. 2020 Canaan et al. 2020). Population-
based algorithms use ad hoc team play as training component and the overall objective is to improve opponent generalization. Whereas, we consider zero-shot generalization to different teammates at test time. Our work is also related to the hierarchical approaches for multi-agent collaborative tasks (Shu and Tian 2019; Carion et al., 2019 Yang et al., (0220. They train a centralized manager to assign subtasks individual workers and it can generalize to new workers at test time. However, all these works assume known worker types or policies, which is infeasible for complex tasks. Our method does not make any of these assumptions and can be easily trained in an end-to-end fashion.
There have also been effort decomposing the observation space through individual networks. ASN (Wang et al. 2019) decomposes the observation space of each agent trying to capture semantic meaning of actions, DyAN (Wang et al. 2020) adopts similar architecture in curriculum domain. EPC (Long et al. 2020) also proposes to use attention between individual agents to make the network structure invariant to the size of agents. While the network structure of CollaQ to some extent share some similarity with the works aforementioned, the semantic meaning of each component is different. CollaQ models the interaction between agents using an alone network and an attention- based collaborative network, one used to model self-interest solutions and the other one models the influence of other agents on the particular agent.
Several papers also discuss social dilemma in multi-agent setting (Leibo et al. 2017 Rapoport 1974 Van Lange et al. 2013). Several works in reinforcement learning have been proposed to solve problems such as prisoner's s delimma Sandhhll and Crites (1996); de Cote et al. (2006); Wunder al. 2010). However, in our setting, all the agents share the same environmental reward. Thus, the optimal solution for all the agents is to jointly optimize the shared reward. SSD Daques et al. (2019) gives the agent an extra intrinsic reward when its action has huge influence on others. CollaQ does not use any intrinsic reward.
Lastly, our mathematical formulation is related to the credit assignment problem in RL (Sutton 1985 Foerster et al.] 2018 Nguyen et al., (018)) Some reward shaping literature also fall into this category (Devlin et al. 2014, Devlin and Kudenko| 2012). But our approach does not calculate any explicit reward assignment, we distill the theoretical insight and derive a simple yet effective learning objective.
CONCLUSION
In this work, we propose CollaQ that models Multi-Agent RL as dynamic reward assignment problem. We show that under certain conditions, there exist decentralized policies for each agent and these policies are approximately optimal from the point of view of team goal. CollaQ then learns these policies by resorting to an end-to-end training framework while using decomposition in Q-function suggested by the theoretical analysis. CollaQ is tested in a complex practical StarCraft MultiAgent Challenge and surpasses previous SoTA by 40% in terms of win rates on various maps and 30% in several ad hoc team play settings. We believe the idea of multi-agent reward assignment used in CollaQ can be an effective strategy for ad hoc MARL.
REFERENCES
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Dębiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota 2 with large seale deep reinforcement learning. arXiv preprint 19/1v:99/2006680 2019.

---

Under review as a conference paper at ICLR 2021
Max Jaderberg, Wojeiech M Czarnecki, lain Dunning, Luke Marris, Guy Lever, Antonio Garcia Castaneda, Charles Beattie, Neil C Rabinowitz, Ari S Morcos, Avraham Ruderman, et al. Human- level performance in 3d multiplayer games with population-based reinforcement learning. Science, 364(6443):859 865, 2019.
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 Whiteson. The starcraft multi-agent challenge. In Proceedings the 18th International Conference Autoromous Agents and MultiAgent Systems, pages 2186-2188. International Foundation for Autonomous Agents and Multiagent Systems, 2019.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: (707.06377 2017.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:13/2.5602, 2013.
Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent tool use from multi-agent autocurricula. arXiv preprint MXXiv:1909007555 2019.
Peter Stone, Gal A Kaminka, Sarit Kraus, and Jeffrey S Rosenschein. Ad hoc autonomous agent teams: Collaboration without pre-coordination. In Twenty-Fourth AAAI Conference on Artificial Intelligence, 2010.
Samuel Barrett, Peter Stone, and Sarit Kraus. Empirical evaluation of ad hoc teamwork in the pursuit domain. AAMAS, pages 567-574, 2011.
Samuel Barrett and Peter Stone. Cooperating with unknown teammates in complex domains: A robot soccer case study of ad hoc teamwork. In Twenty-ninhh AAAI conference on artificial intelligence, 2015.
Mare Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. unified game-theoretic approach to multiagent reinforcement learning. In Advances in Neural Information Processing Systems, pages 4190-4203, 2017.
Hengyuan Hu, Adam Lerer, Alex Peysakhovich, and Jakob Foerster. " "other-play" for zero-shot coordination. arXiv preprint arXiv:2003.0299 029979, 2020.
Devin Schwab, Yifeng Zhu, and Manuela Veloso. Zero shot transfer learning for robot soccer. In Proceedings the 17th International Conference on Autonomous Agents and MultiAgent Systems, pages 2070-2072. International Foundation for Autonomous Agents and Multiagent Systems, 2018.
Qian Long, Zihan Zhou, Abhibay Gupta, Fei Fang, Yi Wu, and Xiaolong Wang, Evolutionary popula- tion curriculum for scaling multi-agent reinforcement learning. arXiv preprint 2rXiv:2003.14423, 2020.
Ming Tan. Multi-agent reinforcement learning: Independent vs. cooperative agents. In Proceedings of the tenth international conference on machine learning, pages 330-337, 1993.
Peter Sunchag, Guy Lever, Audrunas Gruslys. Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z. Leibo, Karl Tuyls, et al. vecopoeeconnooiitoon networks for cooperative multi-agent learning. arXiv preprint arXiv: / 7706052296 2017.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Qmix: monotonic value function factorisation for deep multi-agent reinforcement learning. arXiv preprint arXiv:1803.1 1445, 2018.
Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning, arXiv preprint arXiv:/905.05400) 2019.
Michael L. Littman. Markov games as a framework for multi-agent reinforcement learning. In
Machine learning proceedings 1994, pages 157-163. Elsevier, 1994.
10

---

Under review as a conference paper at ICLR 2021
Lucian Bu, Robert Babu, Bart De Schutter, et al. A comprehensive survey of multiagent reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 38(2):16-172,, 2008.
Jakob N Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Thirty-second AAAI conference on artificial intelligence, 2018.
Ryan Lowe, Yi I Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-comprttiee environments, In Advances in neural information processing systems, pages 6379-6390, 2017.
Shariq Iqbal and Fei Sha. Actor-attentionncritte for multi-agent reinforcement learning. arXiv preprint arXiv:/810.0220 1810.02912, 2018.
Jakob Foerster, Ioannis Alexandros Assael, Nando De Freitas, and Shimon Whiteson. Learning communicate with deep multi-agent reinforcement learning. In Advances in neural information processing systems, pages 2137-2145, 2016.
Sainbayar Sukhbaatar, Rob Fergus, et Learning multiagent communication with backpropagation. In Advances in neural information processing systems, pages 2244-2252, 2016.
Igor Mordatch and Pieter Abbeel. Emergence of grounded compositional language in multi-agent populations. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Rohan Chitnis, Shubham Tulsiani, Saurabh Gupta, and Abhinay Gupta. Efficient bimanual manipula- tion using learned task schemas. arXiv preprint arXiv: 13874, 2019.
Eugene Vinitsky, Aboudy Kreidieh, Lue Le Flem, Nishant Kheterpal, Kathy Jang, Cathy Wu, Fangyu Wu, Richard Liaw, Eric Liang, and Alexandre M Bayen. Benchmarks for reinforcement learning in mixed-autonomy traffic. In Conference on Robot Learning, pages 399-409, 2018.
Joel 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 MultiA gent Systems, pages 464 473, 2017.
Michael Bowling and Peter McCracken. Coordination and adaptation in impromptu teams. In AAAI, volume 5, pages 53-58, 2005.
Matthew Hausknecht, Prannoy Mupparaju. Sandeep Subramanian, Shivaram Kalyanakrishnan, and Peter Stone. Half field offense: An environment for multiagent learning and ad hoc teamwork. In AAMAS Adaptive Learning Agents (ALA) Workshop. sn, 2016
Samuel Barrett, Peter Stone, Sarit Kraus, and Avi Rosenfeld. Learning teammate models for hoc teamwork. In AAMAS Adaptive Learning Agents (ALA) Workshop, pages 57-63, 2012.
Doran Chakraborty and Peter Stone. Cooperating with markovian ad hoc teammate. In Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems, pages International Foundation for Autonomous Agents and Multiagent Systems, 2013.
Mark Woodward, Chelsea Finn, and Karol Hausman. Learning to interactively learn and assist. arXiv preprint arXiv:1906. 101877706.177, 2019.
Maruan Al- Al-Shedivat, Trapit Bansal, Yuri Burda, Ilya Sutskever, Igor Mordatch, and Pieter Abbeel. Continuous adaptation via meta-learning in nonstationary and competitive environments. arXiv preprint arXiv: 1710.3371 2017.
Shihui Li, Yi Wu, Xinyue Cui, Honghua Dong, Fei Fang, and Stuart Russell. Robust multi-agent reinforcement learning via minimax deep deterministic policy gradient. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pages 4213-4220, 2019.
He He, Jordan Boyd-Graber, Kevin Kwok, and Hal Daumé III. Opponent modeling in deep re- inforcement learning. In International Conference on Machine Learning, pages 1804-1813, 2016.
11

---

Under review as a conference paper at ICLR 2021
Macheng Shen and Jonathan P How. Robust opponent modeling via adversarial ensemble reinforce- ment learning in asymmetric imperfect-information games. arXiv preprint arXiv: 0e0..990999777 08735, 2019.
Jack Serrino, Max Kleiman-Weinet David C Parkes, and Josh Tenenbaum. Finding friend and foe in multi-agent games. In Advances in Neural Information Processing Systems, pages 1249-1259, 2019.
Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456): 885-890, 2019.
Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung. David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782):350-33 354, 2019.
Rodrigo Canaan, Xianbo Gao, Julian Togelius, Andy Nealen, and Stefan Menzel. Generating and adapting to diverse ad-hoc cooperation agents in hanab. arXiv preprint 2xXi::2004.137100, 2020.
Tianmin Shu and Yuandong Tian. M Mind-aware multi-agent management reinforcement
learning. International Conference on Learning Representations, 2019.
Nicolas Carion, Nicolas Usunier, Gabriel Synnaeve, and Alessandro Lazaric. A structured prediction approach for generalization in cooperative multi-agent reinforcement learning. In Advances in Neural Information Processing Systems, pages 128-8138, 2019.
Jiachen Yang, Alireza Nakhaei, David Isele, Kikuo Fujimura, and Hongyuan Zha. Cm3: Coopera- tive multi-goal multi-stage multi-agent reinforcement learning. In International Conference on Learning Representations, 2020.
Weixun Wang, Tianpei Yang Yong Liu, Jianye Hao, Xiaotian Hao, Yujing Hu, Yingfeng Chen, Changjie Fan, and Yang Gao. Action semantics network: Considering the effects of actions in multiagent systems. arXiv preprint 190. 2019.
Weixun Wang, Tianpei Yang, Yong Liu, Jianye Hao, Xiaotian Hao, Yujing Hu, Yingfeng Chen, Changjie Fan, and Yang Gao. From few to more: Large-scale dynamic multiagent curriculum learning. In AAAI, pages 7293-7300, 2020.
Anatol Rapoport. Prisoner's dilemma recollections and observations. In Game Theory Theory of a Conffict Resolution, pages 17-34. Springer, 1974.
Paul AM Van Lange, Jeff Joireman, Craig D Parks, and Eric Van Dijk. The psychology social dilemmas: A review. Organizational Behavior and Human Decision Processes, 1251111 2013.
Tuomas W Sandholm and Robert H Crites. Multiagentrrinffrrcemmnn reinforcement learning the iterated prisoner's dilemma. Biosystems, 37(1 (7(1-)):177-166 1996.
Enrique Munoz de Cote, Alessandro Lazaric, and Marcello Restelli. Learning cooperate in multi- agent social dilemmas. In Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, pages 783-785, 2006.
Michael Wunder, Michael L Littman, and Monica Babes. Classes of multiagent q-learning dynamics with epsilon- greedy exploration. In Proceedings of the 27th International Conference on Machine Learning (ICML-10), pages 1177-1174. Citeseer, 2010.
Natasha Jaques, Angeliki Lazaridou, Edward Hughes, Caglar Gulcehre, Pedro Ortega, DJ Strouse, Joel Z Leibo, and Nando De Freitas. Social influence as intrinsic motivation for multi-agent deep reinforcement learning. In International Conference on Machine Learning, pages 3040-3049, PMLR, 2019.
Richard S Sutton. Temporal credit assignment in reinforcement learning. 1985.
Due Thien Nguyen, Akshat Kumar, and Hoong Chuin Lau. Credit assignment for collective multiagent with global rewards. In Advances in Neural Information Processing Systems, pages 8102-81 13, 2018.
12

---

Under review as a conference paper at ICLR 2021
Sam Devlin, Logan Yliniemi, Daniel Kudenko, and Kagan Tumer. Potential- difference rewards for multiagent reinforcement learning. In Pruceedings of the 2014 international conference on Autonomous agents and mulli-agent systems, pages 165-172, 2014.
Sam Michael Devlin and Daniel Kudenko. Dynamic potential potential-based reward shaping. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, pages 433-440. IFAAMAS, 2012.
13

---

Under review as a conference paper at ICLR 2021
A COLLABORATIVE Q DETAILS
We derive the gradient and provide the training details for Eq. 5
Gradient for Training Objective. Taking derivative w.r.t 0% and 0ú in Eq. 5 we arrive at the
following gradient:
V 0g Ln (0% 0n) = E (l.aa wealseelll + max Qi(s', re 1- 1) - Qi(os, a ni r., (W))
are
Voz (s,
(6a)
Vog (0n, (%)
E. s: s..a wel(r max Qi(s a re 1- 00-1) Qi(os, a, r;; (2))
a' aQi 0 V (8, a, r;;;; V eg a, 0g)
a, ri;
(6b)
Soft CollaQ. the actual implementation, we use soft-constraint version of CollaQ: we subtract Qeoilab (o oflone aa) from Eq. 4 The Q-value Decomposition now becomes:
Qi(o;, 0z) = Qolonn (o,tone, ..,) + Quallab (oi, a.) - Qeollaa (opilaa(oggo (oflone, as)
The optimization objective is kept the same in Eq. [ This helps reduce variances in all the
setiings in resource collection and Starcraft multi-agent challenge. We sometimes also replace Quailab (oglone, a,) in Eq. 7 its target to further stabilize training.
B ENVIRONMENT SETUP AND TRAINING DETAILS
Resource Collection. We set the discount factor as 0.992 and use the RMSprop optimizer with a learning rate of 4e-5. e-greedy is used for exploration with annealed linearly from 1.0 to 0.01 in 100k steps. We use batch size of 128 and update the target every 10k steps. For temperature parameter a, we set it to 1. We run all the experiments for 3 times and plot the mean/std in all the figures.
StarCraft Multi-Agent Challenge. We set the discount factor as 0.99 and use the RMSprop optimizer with learning rate of 5e-4. e-greedy is used for exploration with annealed linearly from 1.0 to 0.05 50k steps. We use a batch size of 32 and update the target every 200 episodes. For temperature parameter o, we set it to 0.1 for 27m_vs ss_00m and to 1 for all other maps.
All experiments on StarCraft II use the default reward and observation settings of the SMAC benchmark. For ad hoc team play with different VIP, an additional 100 reward is added to the original 200 reward for winning the game if the VIP agent alive after the episode.
For swapping agent types, we design the maps 3s1z_vs vs_ 16zg. 1s3z_vs_ v__l6 and 2s2z_vs_1622 (s
stands for stalker, z stands for zealot and zg stands for zergling). We use the first two maps for training and the third one for testing. For adding units, we use 27m vs 30m for training and 28m vs_30m for testing (m stands for marine). For removing units, we use 29m vs. 30m for training and 28m_ vs 30m for testing.
We run all the experiments for 4 times and plot the mean/std in all the figures.
C DETAILED RESULTS FOR RESOURCE COLLECTION
We compare CollaQ with QMIX and CollaQ with attention-baut model in resource collection setting. As shown in Fig. 9 QMIX does not show great performance Adding attention-basee model introduces larger variance, so the performance degrades by 10.66 in training but boosts by 2.13 in ad ad hoc team play.
even worse than random action.
D DETAILED RESULTS FOR STARCRAFT MULTI-AGENT CHALLENGE
We provide the win rates for CollaQ and QMIX on the environments without random agent IDs on three maps. Fig. 10 shows the results for both method.
14

---

Under review as a conference paper at ICLR 2021
Random Action
Training Reward
Adhoc Testing Reward
250
Rowara
Rowara
200
200
150
150
1.0
Envirenment Steps
Environment Stops
Figure 9: Results for resource collection. Adding attention- based model CollaQ introduces a larger variance so the performance is a little worse. QMI does not show good performance in this sctting.
QMXX w.o Rond ID
Collo w.o. Rand
ID
HHN2
80
80
TestWnn Rahed
Rahen
40
40
40
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
Ensironment Steps
166
Envineement Steps
166
Endironment Steps
106
Figure 10: Results for StarCraft Multi-Agent Challenge without random agent IDs. CollaQ outperforms QMIX on three maps.
show the exact win rates for all the maps and settings mentioned StarCraft Multi-Agent Challenge. From Tab. we can clearly see that CollaQ improves the previous SoTA by a large margin.
Table 1: Win rates for StarCraft Multi-Agent Challenge. CollaQ show superior performance over all baselines.
IQL
VDN
QTRAN
QMIX
CollaQ
CollaQ with Attn
5m_ ps_6m
62.81%
69.37%
35.31 %
66.25%
81.88%
80.00%
MMM2
4.22%
6.41%
0.32%
36.56%
79.69%
84.69%
2c 64zg
33.75%
22.66%
8.13%
34.06%
87.03%
62.66%
27m_ vs_30m
1.10%
6.88%
0.00%
19.06%
41.41%
50.63%
8m vs 9m
71.09%
82.66%
28.75%
77.97%
92.19%
96.41 %
10m vs vs_1im 11m
70.47%
86.56%
31.10%
81.10%
91.25%
97.50%
We also check the margin of winning scenarios, measured how many units survive after winning the battle. The experiments are repeated over 128 random seeds. CollaQ surpasses the QMIX by over 2 units average (Tab. 2). which is huge gain.
Table Number survived units on six StaCraft maps. We compute mean and standard deviation over 128 runs. CollaQ outperforms baselines significantly by managing more units to survive.
5m
6m
MMM2
2c.
64zg
27m
30m
8m
9m
10m.
11m
IQL
0.91 + 0.28
0.02 +0.03
0.05 + 0.04
0.00 + 0.00
0.95 - 0.36
0.6 + 0.44
VDN
1.35 0.13
0.28 1: 0.32
0.23 1 0.12
0.55 1: 0.93
3.16 0.61
3.39 1 1.44
OTRAN
1.76 0.53
0.31
0.44
0.36 0.35
0.00
0.00
2.43 0.53
3.06
QMIX
1.72
1.92 1.02
0,47
- 0.11
1.79
2.75
3.89
1.74
CollaQ
1.95 - 0.41
4.89
+ 1.32
1.48 + 0.15
2.80
3.56
4.91 + 1.48
CollaQ with Attn
2.77 = 0.17
4.73
1.08
1.00
0.49
3.68
4.73
15

---

Under review as a conference paper at ICLR 2021
In simple ad hoc team play setting, assign VIP agent whose survival matters at test time.
Results in Tab. 3 show that at test time, the VIP agent CollaQ has substantial higher survival rate than QMIX.
Table VIP agents survival rates for StarCraft Multi-Agent Challenge. CollaQ with attention surpasses QMIX
by a large margin.
IQL
VDN
QTRAN
QMIX
CollaQ
CollaQ with Attn
5m_vs vs_6m
30.47%
46.72%
16.72%
38. 18.13%
56.72%
61.72%
MMM2
0.31%
0.63%
0.16%
30.16%
62.34%
81.41 %
8m vs_9m
37.35%
47.34%
6.25%
48.91%
59.06%
78.13%
We also test CollaQ in a harder ad hoc team play setting: swapping/adiing/eevviing agents at test time. Tab summarizes the results for ad hoc team play, CollaQ outperforms QMIX by a lot.
Table 4: Win rates for StarCraft Multi-Agent Challenge with swappingg/adiing/erroviigg agents. CollaQ
improves QMIX substantially.
IQL
VDN
QTRAN
QMIX
CollaQ
CollaQ with Attn
Swapping
0.00%
18.91%
0.00%
37.03%
46.25%
46.41%
Adding
13.44%
23.28%
0.16%
70.94%
79.22%
Removing" 0.94%
16.41%
0.16%
58.44%
73.12%
IQL, VDN, QTRAN and QMIX here all use attention-based models.
E
VIDEOS AND VISUALIZATIONS OF STARCRAFT MULTI-AGENT CHALLENGE
extract several video frames from replays CollaQ's agents for better visualization. In addition to that, we provide the full replays of QMIX and CollaQ. CollaQ's s agents demonstrate super interesting behaviors such healing the agents under attack. dragging back the unhealthy agents, and protecting the VIP agent (under the setting of ad hoc team play with different VIP agent settings). The visualizations and videos are available at httpt:://///mmm htpp:///siees googlooooollo.oooo l. com/vieieeeeeee Sallag-starcrafe
F PROOF AND LEMMAS
Lemma 1. af 2 an, then 0 < max(dd; u2) max(a1,, 02) S a
Proof. Note that max(a1, az) = aita2
+
d1 02
So we have:
max(a (m))mmax(a,a a2) a' 0
0 02
01
d
0
2
2
2
(8)
F.1 LEMMAS
Lemma 2. For Markov Decision Process with finite horizon H and daccount y For all i e (1....,K) K}, all r1,12 E IR all s; E St, we have:
[i(s;)) Vi(Sar2)) S
|1 (x, (2(2ra))
3,a
where [s, æ| is the number steps needed to move from to x.
Proof. By definition of optimal value function V: for agent i, know it satisfies the following
Bellman equation:
Vi( max (ri(z;, az) 71E lan.an [Ve(x++11))
(10)
a;
16

---

Under review as a conference paper at ICLR 2021
Note that to avoid confusion between agents initial states {$1,... ........ ssk Sk pair (8, a), we use (xr a) instead. For terminal node æи, which exists due to finite-horizon MDP with horizon H. Vi(wn) ra(an)) The current state is at step 0 (i.e., 25 = 8;).
and reward at state-action
We first consider the case that r1 and r2 only differ a single state-action pair (z). a) for h s H. Without loss of generality, we rn (a) ag) r2 r2(2h. a.).
By definition of finite horizon MDP, Vi(aw; r1) = Vi(ww; r2) for > By the property of max function (Lemma
D. we have:
0 S Vi(ag:r)) TI) V3(3 r2) - r1(a dg) - -22(2 (x))))))) ag)
(11)
Since p(xx) Th 1, ah-1) 1) S 1, for any (2h 11) at step 1, we have:
0 s 7 [Benlen-i,nn-1 [V( - Bessus--aa [i(wn;r2)]]
(12)
7 [m d)) r2(00: [R]]
(13)
Applying Lemma 1 and notice that all other rewards do not change, we have:
V1( - Vi( s [n (0/ og) r2(0%, aR]
(14)
We do this iteratively, and finally we have:
S V((SgT1) (2(s;122) S / [21 a.) r2 aQ)
(15)
We could show similar case when Ti (2% ag) < (2(2%) h a therefore, we have:
() V((s r2) 7 r (w a ra(4h,a))
(16)
where h = | syl is the distance between 8; and z
Now we consider general rı * r2. We could design path (r.) from 1ı to r2 so that each time we only change one distinct reward entry. Therefore each (s, a) pairs happens only at most once and we have:
(((s::))) (2))
Vi(8g Vi(ss;
(17)
l (1 r2(xx, a)l
(18)
2,a
F.2 THM. 1
First we prove the following lemma:
Lemma 3. For any reward assignments for agent i for the optimization problem (Eqn. 7 and local reward set Mlocal 2 {x x sil S C)2 if we construct i; as follows:
az( = = r;( a)
x E M. locall
x of M local
(19)
Then we have:
(((Gr)) vi(s S T Rmax
(20)
where M is the total number of sparse reward sites and Rmax is the maximal reward that could be assigned at each reward site x while satisfying the constraint Φ(r a), 12 a....., ......,,K (8, a)) S
Proof. By Lemma 2 know that
(V((:);)) - V.3;
<
Σ
(r7s,)
(21)
ag.locall
glocal
(s)
(22)
gloaal
<
M
(23)
n
17

---

Under review as a conference paper at ICLR 2021
(b) A function of all agent states = (2..55).
0
(a)
M
R*
R
R
M
A function of s/ocal
+ St comete
0
Riocal
Ricca((
Figure 11: Different reward assignments.
Note that "sparse reward site" is important here, otherwise there could be exponential sites x & Slocal and Eqn. 23 becomes vacant.
Then we prove the theorem.
Proof. Given a constant C, for each agent i, we define the vicinity reward site B,(C) = {x I s S C}.
Given agent i and its local "buddies" slocal (a subset of multiple agent indices), construct the corresponding reward site set M.ocal:
M local
U By(C)
(24)
Eaforal
Define the remote agents s stemote-
s local as all agents that do not belong s Ineall
slocl
Define the distance D between the Mlocal and s stemote,
min min celemote
Ja 851
(25)
Intuitively, the larger D is, the larger distance between relevant rewards sites from remote agents and the tighter the bound. There is a trade-off between C and D: the larger the vicinity, Mlocaa expands and the smaller D is.
Given this setting, we then construct few reward assignments (see Fig. II given the current agent states s = {$1. s......kk! }. For brevity, we write R[M,s) s) to be the submatrix that relates to reward site M and agents set s.
The optimal solution R for Eqn.
The perturbed optimal solution R by pushing the reward assignment of [M|ocal s Rt to [Mlocal slocal].
remote in
s/ocal] From R", we get Rí by setting the region [Mremote A to be zero.
The local optimal solution Riocal that only depends on s Jocal This solution is obtained by setting [:, s gemote)] to zero and optimize Eqn.
From Riceal get Riocal(0) by setting [Mpemote slocal) be zero
18

---

Under review as a conference paper at ICLR 2021
It is easy to show all these rewards assignment feasible solutions to Eqn. I This is because if the original solution is feasible, then setting some reward assignment be zero also yields feasible solution, due to the property of the constraint Ø.
For simplicity, we define Vlocal to the partial objective that sums over sj s) glocal and similarly for Jremote-
We could show the following relationship between these solutions:
Jremote R Jiemote (R*) 7P Rmax M K
(26)
This is because each of this reward assignment move costs at most 7 Remax by Lemma and there are at most M K such movement.
On the other hand, for each 8j s/ocal since Miocal 2 By(C), from Lemma 3 have:
Vy (i(ooooa))))) 2 (j(Roocal) --0 Rinax M
(27)
And similarly have:
(g(R)) 2 V2(R)) - - Rmax-M
(28)
Now we construct a new solution R by combining Riocat(o) s|oca]] with Egl:, This is still a feasible solution since in both (ocal(0) and Ri their top-right and bottom-left sub-matrices are zero, and its objective still good:
J (Rt)
Jineal (oooaa(()) + J (Rt)
(29)
Jocal RRocal) 7 Rmax K + Jremote (Rt)
(30)
Jiocal ( R²) ) + Jremote (Rg) 70 Rmax M K
(31)
Jineat (Tt") (T') + Jremotol ((t)) 7- Rmaxx MK K
(32)
Jocas (I²) ) Jremoto (ît") 70 MmRaxXKK
(33)
Jineal R²) + Jremote (R") Pmaa M K(? +7P)
(34)
J(R") - Rmax RKmx +DD)
(35)
Note that b due to Eqn. 27 ② is due to the optimality of Rffccal (and looser constraints for Rjocat). K due to the fact that ft is obtained by adding rewards released from s sremote to slocal is due
to the fact that Ri and र² has the same remote components. ( is due to Eqn. 26 O is by definition of Jocal and Jremote.
Therefore we obtain r; = [R], that only depends on socca On the other hand, the solution Å is close to optimal R" with gap (7 + P) K.
19


Reviews:
[{"review_id": "xk6cb4IbgjT", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies a team of agents that collaborate to maximize a global objective, where all agents receive the same reward value as a function of their state and actions. The approach suggested here is to assign each agent a virtual (\"perceived\") reward function such that all the virtual rewards sum up to the actual reward. Then the problem from the point of view of agent i can be solved with local value functions that depend on the local state of agent i and its perceived reward.  It is shown that such a decoupled policy exists that approximates the optimal policy if the state structure decomposes \"well enough\" into local states. Experiments demonstrate the advantages of this approach on a resource collection game on the StarCraft Multi-Agent Challange, with dramatic improvements over existing methods for the scenarios that were tested. \n\nThe paper is mostly easy to follow, and is well-written and well motivated. The idea of this paper is nice and intuitive. Being less familiar with the literature, It's hard for me to judge how novel this idea is. It seems like there must exist multi-agent works that exploit the local structure of the interaction to reduce the dimensionality. Hence, as a start, the contribution of this paper can be enhanced by extending the literature review to include works of that kind, even if under different contexts. If indeed this idea is unique enough (and had a major impact on the design of the algorithm), then this is a significant contribution. Then, the other main issue is with improving the rigor of the presentation and the math. While it's clear what the results are showing, some guessing is needed to fill in some gaps. \n\nThe reward and state structure: I guess that the \"external rewards\" referred to above (1) and the \"same reward\" that all agents share are the same thing. Please clarify and unify the definitions. Then it's not clear what's going on with the dimensions of the local states. The local states appear in the second paragraph of Section 2 and are never properly defined, and also the local state spaces S_i are not well defined. Are the cardinalities of S_i and A_i the same for all i? otherwise, the constraint in (1) isn't clear. Additionally, it's not clear how can one measure distances of states that live in different state spaces (of different agents) as is often being done in the proofs (e.g., the proof of Theorem 1, the definition of D, and so on). On that note, the idea of \"nearby agents\" should be more rigorously defined. Ignoring these gaps, it looks like Theorem 1 basically shows that the better the problem decomposes into local environments, the easier it becomes to solve it distributedly. It's not clear if the math provides any added value on top of this important yet simple observation. \n\nThe connection between theory and practice: Assigning perceived rewards to simplify the MARL problem is an elegant and appealing idea. For this reason, it's important to carefully discuss to what extent this idea actually influenced the algorithm that was tested in practice. Subsection 2.3 raises some concerns in this regard since the algorithm resorts to \"end-to-end learning of Q_i\", in what seems like a total bypass of the idea of the perceived rewards. Looking at equation (3) or (4), one can get the impression that the perceived rewards are just an interpretation of what happens \"inside\" when training the Q-values after splitting them as in (4). By itself, (4) makes a lot of sense and is very natural, so it's not clear if it isn't' easier to come up directly with (4) without knowing anything about perceived rewards. This raises the question: why isn't it possible to bypass the idea of the perceived rewards and motivate the paper based on (4), which is closer to the practical algorithm? answering this question is crucial to claim a significant contribution since otherwise the are two loosely related parts in this paper. \n\nPrecise statements: The statements of the mathematical results often lack some definitions. The statement of theorem 1 doesn't define R_{max} (but Lemma 3 does). The statement of Lemma 3 doesn't define the distance between states (but Lemma 2 does). Please make the statements more standalone and well defined. On the same note, make sure that important definitions don't randomly appear in the paper, sometimes too late (e.g., local states). \n\nExperiments: The experimental results are overall nice and promising.  My only question here is why the resource collection scenario only compares to IQL and not to QTRAN/VDN/QMIX like the StarCraft scenario? \n\nVague sentences and typos:\n\n\"each agent i is acted independently on its own state\" - acting? based on its own state? \n\n(s_1,...,s_N) (bottom of page 2) - needs to be s_K\n\n\"so that\" in Theorem 1 - such that \n\n\"We found that using the observation o_i of agent i covers s_i^{local} works sufficiently well\" - not clear. \n\n\"since 1990s\" - since the 1990s. \n\n\"We sometimes also replace... in Eq.7 by its target to further stabilize training\" (Page 12)- what does sometimes mean? how can one reproduce this?\n\n\"doesn't\" - does not \n\n\"Applying Lemma 1 and notice that all other rewards does not change\" - do not change \n\n\"Define the remote agents s_i^{remote}...\" isn't that a set of states and not of agents? please rephrase. \n\n\"the more distant between relevant rewards istes from remote agents\" - the larger the distance?  \n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "rabHEzOzQQL", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Good theoretical analysis and compliant experiment performance\n\n1. The Limitation of Theorem 1: the authors have said that ``the optimal gap of r_i heavily depends on the size of s_i^{local}. But in experiments (including experiments in appendix), the authors only discussed the claimed optimal setting (“using the observation o_i of agent i covers $s_i^{local}$”). More experiments on other size of s_i^{local} could be added to better prove the conclusion. (Whether the best choice can not or hard to be proven mathematically.)\n2. Some expression problems which may cause confusions: 1) Too many kinds of rewards including perceived reward, local reward, external reward and etc. The definitions of them are not very clear.  For example,  the perceived reward is really confused; 2) A brief algorithm flow chat and pseudo codes are needed for better understanding of how the algorithm works.\n3. As this work is eventually an MARL work in solving ad hoc team setting games by decomposing reward. Some explicit comparisons (May be in form or experiments or brief analysis) should be added with some MARL methods(SSD: Social Influnce as Intrinsic Motivation for Multi-Agent Deep Reinforcement Learning; PBRS: Reward shaping for knowledge-based multi-objective multi-agent reinforcement learning). Only the credit assignment problem in RL is discussed, the authors need to discuss more on some other related works like social dilemma in MARL or reward shaping?", "extra_scores": {}, "extra_text": {}}, {"review_id": "UTzNZNeS31D", "reviewer": "AnonReviewer2", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper focuses on reward attribution in multiagent reinforcement learning, proposing a new algorithm, essentially by splitting value functions to what agents can achieve individually and learning separately how different individual rewards interact. This is an old idea, but the paper essentially applies it to the state-of-the-art deep learning machinery, producing impressive results on the hardest games state-of-the-art algorithms can manage. \n\nAs is the case with many similar areas, the work emphasises translation of an idea to the deelp learning setting, with the usual caveats, i.e. that there is not a major new methodological or conceptual insight, and the main advance is in terms of scaling up to real-world scenarios rather than having a better explicit algorithm to manage reward decomposition at runtime in an online learning setting. In other words, we learn more about how to solve challenging games rather than about the key underlying AI problem. \n\nThe paper does not offer a huge amount of novelty, but rather presents a solid deep RL engineering approach to solving the wider problem in a specific setting. Nonetheless, the technical material is well-developed, the presentation is overall of a high quality, and the experimental results extensive (and impressive). ", "extra_scores": {}, "extra_text": {}}, {"review_id": "LC6KEYKa8An", "reviewer": "AnonReviewer3", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "To address the ad hoc team play, the authors propose a residual term of Q function, which additionally considers the states of nearby agents. A novel MARA loss is introduced to the residual term as a regularization to achieve the reward assignment implicitly. The proposed CollaQ could be easily built on QMIX and trained end-to-end. CollaQ outperforms other baselines on various tasks with the ad hoc team play setting. \n\nThe paper is very clear and well-structured. To the best of my knowledge, the MARA regularization is novel enough. The Ad-hoc MARL is an important problem in real-world applications but has not been fully studied. The interactive term with regularization is a practical and promising method to solve this problem and could be followed by other researchers.\n\nHowever, I still have some concerns:\n\nFirst, the theoretical analysis of reward assignment is not close to the implementation of CollaQ. There is no real assignment mechanism. A MARA loss is derived from the theoretical analysis to achieve the reward assignment implicitly, but the MARA loss could be more straightforwardly interpreted as that the Q value should be equal to the individual value when the agent cannot observe other agents. From this perspective, the complex reward assignment is not necessary. Moreover, CollaQ is built on QMIX. However, the individual value function in QMIX does not estimate a real expected return, and the value has no meaning. Is the theoretical analysis of reward assignment still valid in QMIX?\n\nI do not find any experiments to support the claim that \"agents using CollaQ would first learn to solve the problem pretending no other agents are around using Qalone then try to learn interaction with local agents through Qcollab.\" I think it is over-claimed and should be removed. Splitting the end-to-end learning process into two learning stages might harm the learning. \n\nThe visualizations in Fig 3 are helpful to understand how CollaQ works, but they are special cases. Statistical results are more convincing to verify how CollaQ influences the decision.\n\nAt the test time of StarCraft, are the IDs shuffled at each timestep or only at the first timestep of an episode?\n\n----------Update after author response----------\n\nI thank the authors for the detailed response. Most of my concerns have been addressed, and I decide to keep my score.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a method for collaborative multi-agent learning and ad-hoc teamwork. The paper includes extensive empirical results across multiple environments (including one of known outstanding high difficulty) and repeatedly performs favourably in comparison to a suitable set of state of the art methods. The proposed method is motivated by theoretical analysis, which was considered interesting but its connection to the method in the initial paper was weak. 

Overall, there are remaining concerns which have not been fully addressed in the discussion phase. The authors' responses and discussion with the reviewers should be utilised to improve the material's presentation and to clarify the theory-empirical connection in future revisions of the paper.
Decision: Reject