CM3: Cooperative Multi-goal Multi-stage Multi-agent Reinforcement Learning
Authors: Jiachen Yang
Alireza Nakhaei
David Isele
Kikuo Fujimura
Hongyuan Zha
Venue:  (2020)
Keywords: multi-agent reinforcement learning

Abstract: A variety of cooperative multi-agent control problems require agents to achieve individual goals while contributing to collective success. This multi-goal multi-agent setting poses difficulties for recent algorithms, which primarily target settings with a single global reward, due to two new challenges: efficient exploration for learning both individual goal attainment and cooperation for others' success, and credit-assignment for interactions between actions and goals of different agents. To address both challenges, we restructure the problem into a novel two-stage curriculum, in which single-agent goal attainment is learned prior to learning multi-agent cooperation, and we derive a new multi-goal multi-agent policy gradient with a credit function for localized credit assignment. We use a function augmentation scheme to bridge value and policy functions across the curriculum. The complete architecture, called CM3, learns significantly faster than direct adaptations of existing algorithms on three challenging multi-goal multi-agent problems: cooperative navigation in difficult formations, negotiating multi-vehicle lane changes in the SUMO traffic simulator, and strategic cooperation in a Checkers environment.

Published as a conference paper at ICLR 2020
CM3: COOPERATIVE MULTI-GOAL MULTI-STAGE MULTI-AGENT REINFORCEMENT LEARNING
Jiachen Yang", Alireza Nakhaei David Isele', Kikuo Fujimura' & Hongyuan Zha'
Georgia Institute of Technology
Honda Research Institute
3 Toyota Research Institute
ABSTRACT
A variety of cooperative multi-agent control problems require agents to achieve individual goals while contributing to collective success. This multi-goal multi- agent setting poses difficulties for recent algorithms, which primarily target settings with single global reward, due to two new challenges: efficient exploration for learning both individual goal attainment and cooperation for others' success, and credit-assignment for interactions between actions and goals of different agents. To address both challenges, we restructure the problem into a novel two-stage curricu- lum, in which single-agent goal attainment is learned prior to learning nulli--gent cooperation, and we derive a new multi-goal multi-agent policy gradient with a credit function for localized credit assignment. We use function augmentation scheme to bridge value and policy functions across the curriculum. The complete architecture, called CM3, learns significantly faster than direct adaptations of exist- ing algorithms on three challenging multi-goal multi-agent problems: cooperative navigation in difficult formations, negotiating multi-vehicle lane changes the SUMO traffic simulator, and strategic cooperation in Checkers environment.
INTRODUCTION
Many real-world scenarios that require cooperation among multiple autonomous agents are multi-goal multi-agent control problems: each agent needs to achieve its own individual goal, but the global optimum where all agents succeed is only attained when agents cooperate to allow the success of other agents. In autonomous driving, multiple vehicles must execute cooperative maneuvers when their individual goal locations and nominal trajectories are in conflict (e.g., double lane merges) (Cao) et al., 2013). In social dilemmas, mutual cooperation has higher global payoff but agents' individual goals may lead to defection out of fear or greed (Van Lange et al. 2013). Even settings with a global objective that seem unfactorizable can be formulated as multi-goal problems: in Starcraft micromanagement,, unit that gathers resources must not accidentally jeopardize a teammate's attempt to scout the opponent base (Blizzard Entertainment. 2019); in traffic flow optimization, different intersection controllers may have local throughput goals but must cooperate for high global performance (Zhang et al. 2019). While the framework of multi-agent reinforcement learning (MARL) (Littman] 1994] Stone and Veloso 2000 [Shoham et al.) (003) has been equipped with methods in deep reinforcement learning (RL) (Mnih al. 20155] Lillicrap et al. 2016) and shown promise on high-ddimensionl problems with complex agent interactions (Lowe et al. 2017 Mordatch and Abbeel, 2018 Foerster al. 2018 Lin al. 2018 Srinivasan el al. 2018), learning mulli-agent cooperation in the multi-goal scenario involves significant open challenges.
First, given that exploration is erucial for RL (Thrum) 1992) and even more so in MARL with larger state and joint action spaces, how should agents explore to learn both individual goal attainment and cooperation for others' success? Uniform random exploration is common in deep MARL (Hernandez--Lec er al. (2188) but can be highly inefficient as the value of cooperative actions may be discoverable only in small regions of state space where cooperation is needed. Furthermore, the conceptual difference between attaining one's own goal and cooperating for others' success calls for
"Correspnndecce to jiachen.yangee www.-yaanngggteeee.nn gatech.edu Work done at HRI

---

Published as a conference paper at ICLR 2020
more modularized and targeted approaches. Second, while there are methods for mullti-ggem credit assignment when all agents share a single goal (i.e., global reward) (Chang et al. 2004;] Foerster el. (2018] Nguyen et al., 2018), and while one could treat the cooperative mulfi-god scenario as problem with a single joint goal, this coarse approach makes it extremely difficult to evaluate the impact of an agent's 8 action on another agent's success. Instead, the multi-goal scenario benefit from fine-grained credit assignment that leverages available structure in action-goal interactions, such as local interactions where only few agents affect another agent's goal attainment at any time.
Given these open challenges, our paper focuses on the cooperative multi-goal multi-agent setting where each agent is assigned a goal and must learn to cooperate with other agents with possibly different goals. To tackle the problems of efficient exploration and credit assignment in this complex problem setting, we develop CM3, a novel general framework involving three synergistic components:
1. We approach the difficulty of multi-agent exploration from novel curriculum learning perspective, by first training an actor-critic pair to achieve different goals in an induced single-agent setting (Stage 1), then using them to initialize all agents in the multi-agent environment (Stage 2). The key insight is that agents who can already act toward individual objectives are better prepared for discovery of cooperative solutions with additional exploration once other agents are introduced. In contrast to hierarchical learning where sub sub-goals are selected sequentially in time (Sutton et al. 1999). all agents act toward their goals simultaneously Stage 2 of our curriculum.
Observing that a wide array of complex MARL problems permit decomposition of agents' observations and state vectors into components of self, others, and non-agent specific environment information (Hernandez-LLeal el al.) [018]) we employ function augmentation to bridge Stages 1-2: we reduce the number of trainable parameters of the actor-critic in Stage by limiting their input space to the part that is sufficient for single-agent training, then augment the architecture in Stage 2 with additional inputs and trainable parameters for learning in the multi-agent environment.
3. We propose credit function, which is an action-value function that specifically evaluates action- goal pairs, for localized credit assignment in multi-goal MARL. We use it to derive a multi-goal multi-agent policy gradient for Stage 2. In synergy with the curriculum, the credit function is constructed via function augmentation from the critic in Stage 1.
We evaluate our method on challenging multi-goal multi-agent environments with high-dimensional state spaces: cooperative navigation with difficult formations, double lane merges in the SUMO simulator (Lopez et al. 2018). and strategic teamwork in a Checkers game. CM3 solved all domains significantly faster than IAC and COMA (Tan] 1993 Foerster et al. 2018), and solved four out of five environments significantly faster than QMIX RRahid et al. 2018). Exhaustive ablation experiments show that the combination of all three components crucial for CM3's overall high performance.
RELATED WORK
While early theoretical work analyzed Markov games in discrete state and action spaces TTan 1993, Littman 1994, Hu and Wellman 2003). recent literature have leveraged techniques from deep RL to develop general algorithms for high dimensional environments with complex agent interactions (Tampuu al. 2017 Mordatch and Abbeel, 2018 Lowe et al. (017), which pose difficulty for traditional methods that do not generalize by learning interactions (Bhattacharya et al.) 2010)).
Cooperative multi-agent learning is important since many real-world problems can be formulated as distributed systems in which decentralized agents must coordinate to achieve shared objectives (Panait and Luke| (005). The multi multi-agent credit assignment problem arises when agents share global reward (Chang et al. (204). While credit assignment be resolved when independent individual rewards available (Singh et al. 2019), this may not be suitable for the fully cooperative setting: Austerweil el at. (2016) showed that agents whose rewards depend on the success of other agents can cooperate better than agents who optimize for their own success. In the special case when all agents have a single goal and share a global reward, COMA (Foerster et al.) 2018) uses a counterfactual baseline, while Nguyen et al. (2018) employs count- based variance reduction limited to discrete-ste state
'Goal discovery and assignment are challenges for MARL. However, many practical multi agent problems have clear goal assignments, such as in autonomous driving and soccer. Our work is specific to known goal assignment and is complementary methods such (Carion et al. 2019) for the unknown case.
2

---

Published as a conference paper at ICLR 2020
environments. However, their centralized critic does not evaluate the specific impact of an agent's action on another's ' success in the general multi-gon goaal setting. When a global objective is the sum of agents' individual objectives, value-decompossitonn methods optimize centralized Q-function while preserving scalable decentralized execution (Sunehag el al.) 2018 Rashid et al. 2018: Son et al. 2019), but do not address credit assigament. While MADDPG (Lowe
(017] )) and M3DDPG (Li) et al. (2019) apply to agents with different rewards, they do not address multi-goal cooperation as
they do not distinguish between cooperation and competition, despite the fundamental difference.
Multi-goal MARL was considered in Zhang et al. (2018), who analyzed convergence in a special networked setting restricted to fully-decentraiize training, while we conduct centralized training with decentralized execution (Olichock er al., (008). In contrast to multi-task MARL, which aims for generalization among non-sinultaneous tasks (Omidshafiei et al.) 2017), and in contrast to hierarchical methods that sequentially select subtasks (Vezhnevets et al.) 2017|Shu and Tian (019)) our decentralized agents must cooperate concurrently to attain all goals. Methods for optimizing high-level agent-task assignment policies in hierarchical framework (Carion et al. (019) are complementary to our work, as we focus on learning low-level cooperation after goals are assigned. Prior application of curriculum learning (Bengio al. 2209) to MARL include single cooperative task defined by the number of agents (Gupta er al.) (017) and the probability of agent appearance
(Sukhbaatar el al. 2016), without explicit individual goals. Rusu el al. (2016) instantiate new neural
network columns for task transfer in single-agen RI. Techniques in transfer learning (Pan and Yang 2010 are complementary our novel curriculum approach MARL.
PRELIMINARIES
In multi-goal MARL, each agent should achieve a goal drawn from a finite set, cooperate with other agents for collective success, and act independently with limited local observations. We formalize the problem as an episodic multi-goal Markov game, review an actor-critic approach to centralized multi-agent credit assignment.
training of decentralized policies, and summarize counterfactual-basee
P.R. Multi-goal Markov games. A multi-goal Markov game is tuple (8, {O*), }. (Ar). ; P, R. G, N, with N agents labeled by E [N]. In each episode, each agent n has one fixed goal g" E G that is known only to itself. At time and global state s, E S, each agent n receives an observation of := (s(s:) E O and chooses an action of E A". The environment moves St41 due to joint action a, := fa......................... a according to transition probability P(s az). Each agent receives a reward R
R(s g²), and the learning task is to find stochastic decentralized policies n" O" x g x A" + [0, 1]. conditioned only on local observations and goals, to maximize J(T)) = ET Li 7t EN R(se, ((.s,,,.g")) a..g"). where 7 E 10 and joint policy π factorizes as Talssg) = Ih T" (a"""""" l0","")) g actions and goals, respectively, except that of agent n. Let boldface a and g denote the joint action and joint goals, respectively. For brevity, let r(a") == x² (a"lo" -, gg). This model covers diverse set of cooperation problems in the literature (Hernandez- et al. 2018), without constraining how the attainability of a goal depends on other agents: at traffic intersection, each vehicle can easily reach its target location if not for the presence of other vehicles; in contrast, agents in a strategic game may not be able to maximize their rewards in the absence of cooperators (Sunehag et al. 2018).
due to decentralization. Let a a" and g denote all agents'
Centralized learning of decentralized policies. A centralized critic that receives full state-action in- formation can speed up training of decentralized actors that receive only local information (Lowe et al. 2017 Foerster et al., 2018). Directly extending the single-goal case, for each n. E [1..N] in multi- goal Markov game, critics are represented by the value function V :) == Em [2 7² RT so s] and the action-value function Q (s, a) == Ex [Eee R joint policy π against the reward R for each goal g".
80 8, ag = a] which evaluate the
Multi-agent credit assignment. In MARL with single team objective, COMA addresses credit assignment by using a counterfactual baseline in an advantage function (s, a) := Q (s, a) Ea x" <"""" [o") (* (s, (à", a a)) (Foerster et al. 2018 Lemma 1), which evaluates the contribution of a chosen action a" versus the average of all possible counterfactuals am, keeping a - fixed. The analysis in Wu et al, (2018) for a formally equivalent action-dependent baseline in RL suggests that COMA is a low-variance estimator for single- goal MARL. We derive its variance in Appendix C However, COMA is unsuitable for credit assignment in multi-goal MARL, as it would treat the
3

---

Published as a conference paper at ICLR 2020
collection of goals g as global goal and only leam from total reward, making it extremely difficult to disentangle each agent's impact on other agents' goal attainment. Furthermore. global Q-function does not explicitly capture structure in agents' interactions, such as local interactions involving limited number agents. We substantiate these arguments by experimental results in Section 6
4 METHODS
We describe the complete CM3 learning framework as follows. First we define a credit function as mechanism for credit assignment in multi-goal MARL, then derive new cooperative multi-goal policy gradient with localized credit assignment. Next we motivate the possibility of significant training speedup via curriculum for multi-goal MARL. We describe function augmentation mechanism for efficiently bridging policy and value functions across the curriculum stages, and finally synthesize all three components into a synergistic learning framework.
4.1 CREDIT ASSIGNMENT IN MULTI-GOAL MARL
If all agents take greedy goal-directed actions that individually optimal in the absence of other agents, the joint action can be sub-optimal (e.g. straight-line trajectory towards target in traffic). Instead rewarding agents for both individual and collective success can avoid such bad local optima. na've approach based on previous works (Foerster el al. 2018) Lowe et al. (017)) would evaluate the joint action a via global Q-function Q (s. a) for each agent's goal g" but this does not precisely capture each agent's contribution to another agent's 's attainment of its goal. Instead, we propose an explicit mechanism for credit assignment by learning an additional function Q (s, a²)) that evaluates pairs of action a and goal g", for use in multi- qulti-goal actor-critic algorithm. We define this function and show that it satisfies the classical relation needed for sample- based model-free learning.
Definition 1. For n., m [N], E S, the credit function for goal g" and am Ant by agent is:
(H,saa)) = E
R
80 -,000 a
1=
Proposition 1. For all m,n [N]. the credit function
satisfies the following relations:
(n a an)) VIT(()
Em [R] + -Q% (#1+1, (441)) 8t =8, "." "
Σ (a"" on .g" (s,aa""
am
Derivations are given in Appendix B.I including the relation between Q (s, a") and Q a). Equation ( takes the form of the Bellman expectation equation, which justifies learning the credit function, parameterized by lq.. by optimizing the standard loss function in deep RL:
L(QQ.) = En [17 + +QQ (St41, a Q (Se, of"; (Q)))
While centralized training means the input space scales linearly with agent count, many practical environments involving only local interactions between agents allows centralized training with few agents while retaining decentralized performance when deployed at scale (evidenced in Appendix E
4.2 COOPERATIVE MULTI-GOAL MULTI-AGENT POLICY GRADIENT
We use the credit function critic within a policy gradient for multi-goal MARL. Letting 0 parameterize æ, the overall objective J(TT) maximized by ascending the following gradient: Proposition 2. The cooperative multi-goal credit function based MARL policy gradient
VoJ(T) =E
(vo log " (a (1"" 10 )) A7
(s,
(5)
72
AT m (s, a) := (TT Σ क (a"
(6)
4

---

Published as a conference paper at ICLR 2020
This is derived in Appendix B.2 For fixed agent m, the inner summation over considers all agents' goals g" and updates m s policy based on the advantage of a" over all counterfactual actions a" measured by the credit function for g". The strength of interaction between action-gon -goal pairs is captured by the extent to which Q% (s, â=*) varies with am", which directly impacts the magnitude of the gradient on agent m's policy. For example, strong interaction results in non-constant Q (s,, +), which implies larger magnitude of AW,,, and larger weight on Va log π (a""). ). The double summation accounts for first-order interaction between all action-goal pairs, but complexity can be reduced by omitting terms when interactions are known to be sparse, and our empirical runtimes are on par with other methods due to efficient batch computation (Appendix F). As the second term in A is a baseline, the reduction of variance can be analyzed similarly to that for COMA, given in Appendix C.2 While A n. = (x, a) Vi (s) (due to )3. ablation results show stability improvement due to the credit function (Section 6p. As the credit function takes in single agent's 's action, it synergizes
with both CM3's curriculum and function augmentation as described in Section 4.5
4.3 CURRICULUM FOR MULTI-GOAL. MARI
Multi-goal MARL. poses a significant challenge for exploration. Random exploration can be highly inefficient for concurrently learning both individual task completion and cooperative behavior. Agents who cannot make progress toward individual goals may rarely encounter the region of state space where cooperation needed, rendering any exploration useless for learning cooperative behavior. On the other extreme, exploratory actions taken in situations that require precise coordination can easily lead to penalties that cause agents to avoid the coordination problem and fail achieve individual goals. Instead, we hypothesize and confirm in experiments that agents who can achieve individual goals in the absence of other agents can more reliably produce state configurations where cooperative solutions are easily discovered with additional exploration in the multi-agent environmen
We propose a MARL curriculum that first solves a single-agent Markov decision process (MDP), as preparation for subsequent exploration speedup. Given a cooperative multi-goal Markov game MG, we induce an MDP M to be the tuple (S", O" A P", R, 7), where an agent n is selected to be the single agent in M. Entities S". P", and R are defined by removing all dependencies on agent interactions, so that only components depending on agent n remain. This reduction to M is possible in almost all fully cooperative multi-agent environments used in large body of work Hernandez-L er al. (2188), precisely because they support a variable number of agents, including N 1. Important real-world settings that allow this reduction include autonomous driving, multi traffic light control, and warehouse commissioning (removing all but one car/controller/rrbo,, respectively, from the environment). Given full Markov game implementation, the reduction involves only deletion of components associated with all other agents from state vectors (since an agent is uniquely defined by its attributes), deletion of if-else conditions from the reward function corresponding to agent interactions, and likewise from the transition function if a simulation is used. Appendix G provides practical guidelines for the reduction. Based on M, we define a greedy policy for MG.
Definition 2.
A greedy policy n" by agent n for cooperative multi-goal MG is defined as the optimal policy x² for the induced MDP M where only agent is present.
This naturally leads to our proposed curriculum: Stage trains single agent in M to achieve greedy policy, which is then used for initialization in MG in Stage 2. Next we explain in detail how to leverage the structure of decentralized MARL to bridge the two curriculum stages.
4.4 FUNCTION AUGMENTATION FOR MULTI-GOAL CURRICULUM
In Markov games with decentralized execution, an agent's observation space decomposes into 2h = U00 othere. where our E Ohr captures the agent's own properties, which must be observable by the agent for closed-loop control, while ohherrs E Oathers is the agent's egocentric observation of other agents. In our work. egocentric observations are private and not accessible by other agents (Pynadath and Tambe 2002). Similarly, global state decomposes into 8 := (Benv, 8²2, 8"),, where
We provide synthetic example aid intuition in Appendix
'Environments include: discrete 2D worlds, continuous 3D physics simulators, StarCraft 1I, transportation tasks, 3D first-person multiplayer games, etc. Exceptions are settings where single task is purely defined by inter-agent communication, but these are multi-goal Markov games.
5

---

Published as a conference paper at ICLR 2020
Stage
Function augmentation
Stage
(s(s.
2 (s,
h
W
(,(s,0r)
Qn(s,
R(5
Input
Input
Environment
(5.g. [.)
Environment
In Stage 1, Q' and T² learn to achieve multiple goals in single-agent environment. Between Stage 1 and 2, constructed from the trained x² and new module π² according to ( same construction is done for (n, a) and (s,s ) not shown). In the multi-agent environment of Stage 2, these augmented functions are instantiated for each N agents (with parameter-sharing)
Figure 1:
Senv environment information not specific any agent (e.g., position of a landmark), and 8 captures agent n information. While this decomposition is implicitly available in a wide range of complex multi-agent environments (Bansal er al. 20188 Foerster er al.) 2018 Lowe al. 2017, Rashid et al. 2018 Liu er al. 2019 Jaderberg et al, 2019), we explicitly use it to implement our curriculum. In Stage as the ability to process Ophers and s -- x unnecessary, we reduce the input space of policy and value functions, thereby reducing the number of trainable parameters and lowering the computation cost. In Stage 2, we restore Stage parameters and activate new modules to process additional inputs o'thters and 8 s This augmentation is especially suitable for efficiently learning the credit function (T) and global Q-function, since ((s, a) can be augmented into both Q77 (s, a) and Q a aa"), explained below.
4.5 A COMPLETE INSTANTIATION OF CM3
We combine the preceding components to create CM3, using deep neural networks for function approximation (Figure and Algorithm [T]. Without loss generality, we assume garameter-sharinn (Foerster et al.) 2018) among homogeneous agents with goals as input (Schaul et al.) (015).. The inhomogeneous case can be addressed by N actor-critics. Drawing from multi-task learning (Taylor) and Stone 2009), sample goal(s) in each episode for the agent(s), to train one model for all goals.
Stage 1.
We train an actor π (alo, g) and critic Q' (s*, a, to convergence according to (4) and (5) in the induced MDP with N = and random goal sampling (see Appendix D). This uses orders of magnitude fewer samples than for the full multi-agent environment compare Figure with Figure 5
Stage 2.
The Markov game is instantiated with all N agents. We restore the trained n'' parameters, instantiate a second neural network n² for agents to process others and connect the output x² to a selected hidden layer of n Concretely, let h E IR mi denote hidden layer i L with m, units in L.- layer network n connected to layer - 1 via h! = (W!h)) with Wi! E Rm,xm;-> Xm;-1 and nonlinear
activation f- Stage 2 introduces a K-layer network 7² (0 with outputs 1& E TR chooses i of ! and augments h/- to be h1- = (W..A..... + w3:2 n2x) with W1.2 E R Xmx_ Being restored from Stage 1, not re-initialized, hidden layers < i* begin with the ability process (o% g)), while the new weights in x² and W-122 specifically learn the effect of surrounding agents. Higher layers i i" that already take greedy actions achieve goals Stage I must now do so while cooperating to allow other agents' success. This augmentation scheme is simplest for deep policy and value networks using fully-connected or convolutional layers.
a layer Fl
The middle panel of Figure depicts the construction of π from x² and n The global QT (s, a, g.) constructed from Q' similarly: when the input to Q" is (S s" """.")). new module takes input (s- a-) and connects to a chosen hidden layer of Q'. Credit function Q (s, am ggd) is
"Setting 1" to be the last hidden layer worked well our experiments, without needing tune.

---

Published as a conference paper at ICLR 2020
Dar?
Figure 2: Checkers
Artion
B
Goed
(a) Antipodal (b) Cross
(c) Mergee
Figure 4: Agent sedans must perform double lane merge reach goal lanes. SUMO controls yellow sedans and trucks. Policy generalization was tested such traffic conditions.
Figure 3: Cooperative navigation
augmented from copy of Q", such that when Q' inputs are (Semv; 8", ,am gg"), the new module's inputs are (sTT, ") We train the policy using 5 train the credit function with loss (4) and train the global Q-function with the joint-action analogue of
5 EXPERIMENTAL SETUP
We investigated the performance and robustness of CM3 versus existing methods on diverse and challenging multi-goal MARL environments: cooperative navigation in difficult formations, double lane merge in autonomous driving, and strategic cooperation in Checkers game. We evaluated ablations of CM3 on all domains. We describe key setup here, with full details Appendices G
Cooperative navigation: We created three variants of the cooperative navigation scenario in Lowe el al. (2017), where agents cooperate to reach a set of targets. We increased the difficulty by giving each agent only an individual reward based on distance to its designated target, not global team reward, but initial and target positions require complex cooperative maneuvers to avoid collision penalties (Figure 3). Agents observe relative positions and velocities (details in Appendix G.I). SUMO: Previous work modeled autonomous driving tasks as MDPs in which all other vehicles do not learn to respond to single learning agent (Isele et al., 2018 Kuefler al. (017). However, real-world driving requires cooperation among different drivers' with personal goals. Built in the SUMO traffic simulator with sublane resolution (Lopez al. 2018), this experiment requires agent vehicles to learn double-merge maneuvers to reach goal lane assignments (Figure(4). Agents have limited field of view and receive sparse rewards (Appendix G.2p. Checkers: We implemented challenging strategic game (Appendix GG.3] an extension of Sunehag et al. (2018)), to investigate whether CM3 is beneficial even when an agent cannot maximize its reward in the absence of another agent. In gridworld with red and yellow squares that disappear when collected (Figure 2 Agent A receives +1 for red and -0.5 for yellow; Agent B receives -0.5 for red and +1 for yellow. Both have limited 5x5 field of view. The global optimum requires each agent to clear the path for the other.
Algorithm implementations. We describe key points here, leaving complete architecture details and hyperparameter tables to Appendices [ and CM3: Stage is defined for each environment as follows (Appendix G): in cooperative navigation, a single particle learns to reach any specified learns to reach any specified goal lane; in Checkers,
landmark; in SUMO, training one agent as A and B. Appendix H describes function augmentation in Stage 2 of CM3. COMA (Foerster al. 2018): the joint goal g and total reward Σn R" can be used to train COMA's global Q function, w which receives input (s.0". ",..."""_. a .g Q(s,a" i,
alternate between
Each output node represents "aa"",,)) g). IAC (Tan 1993. Foerster al. 2018): IAC trains each agent's actor and
critic independently, using the agent's ss own observation. The TD error of value function V(o", """) is used in standard policy gradient (Sutton er al. (000). QMIX (Rashid et al. 2018): :
we used the
original hypernetoork, giving all goals to the mixer and individual goals to each agent network. We used a manual coordinate descent on exploration and learning rate hyperparameters, including values reported in the original works. We ensured the number of trainable parameters are similar among all methods, up to method-specific architecture requirements for COMA and QMIX.
'Input 8th is needed for disambiguation, so that input action a is associated with agent m. 'Code for all experiments is availahle wtthttps://ggttiie com/ 1tt.o///111555511 1235813/ccm
7

---

Published as a conference paper at ICLR 2020
(a) Antipodal
(b) Cross
(c) Merge
SUMO
(e) Checkers
Maledd
(1) Antipodal
(g) Cross
(h) Merge
ii) SUMO
Checkers
Figure 5: a-e: Comparison against baselines in cooperative navigation (a-c). SUMO (d), Checkers (e). f-j: Comparison against ablations. Average and standard deviation (shaded) of 10 evaluation episodes conducted every 100 training episodes, across 3 independent runs.
Ablations. We conducted ablation experiments in all domains. To discover the speedup from the curriculum with function augmentation, we trained the full Stage 2 architecture of CM3 (labeled as Direct) without first training components n² and Q² in an induced MDP. To investigate the benefit of the new credit function and multi-gon golli-ggoa policy gradient, we trained an ablation (labeled QV) with advantage function A (s. a) == Q" (s. a) - (s). where credit assignment between action-gon pairs is lost. QV uses the same n², Q², and function augmentation as CM3.
RESULTS AND DISCUSSIONS
CM3 finds optimal or opar-optimal policies significantly faster than IAC and COMA on all domains, and performs significantly higher than QMIX four out of five. We report absolute runtime in Appendix [ and account for CM3's Stage episodes (Appendix ! when comparing sample efficiency.
Main comparison. Over all cooperative navigation scenarios (Figures 55 to 5cp. CM3 (with Ik episodes in Stage 1) converged more than 15k episodes faster than IAC. TAC reached the same final performance CM3 because dense individual rewards simplifies the learning problem for IAC's fully decentralized approach, but CM3 benefited significantly from curriculum learning, as evidenced by comparison to "Direct" in Figure 5i QMIX and COMA settled suboptimal behavior. Both learn global critics that use all goals as input, in contrast to CM3 and IAC that process each goal separately. This indicates the difficulty of training agents for individual goals under purely global approach. While COMA was shown to outperform IAC in SC2 micromanagement where IAC must learn from a single team reward (Foerster et al.) 2018), our IAC agents have access to individual rewards that resolve the credit assignment issue and improve performance (Singh al. 2019). In SUMO (Figure 5d), CM3 and QMIX found cooperative solutions with performances within the margin of error, while COMA and IAC could not break out of local optima where vehicles move straight but do not perform merge maneuvers. Since initial states force agents into the region of state space requiring cooperation, credit assignment rather than exploration is the dominant challenge, which CM3 addressed via the credit function, as evidenced in Figure 5i] IAC underperformed because SUMO requires longer sequence of cooperative actions and gave much sparser rewards than the "Merge" scenario in cooperative navigation. We also show that centralized training of merely two decentralized agents allows them to generalize to settings with much heavier traffic (Appendix E). In Checkers (Figure 5e). CM3 (with 5k episodes in Stage 1) converged 10k episodes faster than COMA and QMIX to the global optimum with score 24. Both exploration the combinatorially large joint trajectory space and credit assignment for path clearing are challenges that CMB successfully addressed. COMA only solved Checkers among all domains, possibly because the small bounded environment alleviates COMA's difficulty with individual goals in large state spaces. IAC underperformed all centralized learning methods because cooperative actions that give no instantaneous reward are hard for selfish agents to discover in Checkers. These results demonstrate CM3's ability to attain individual goals and find cooperative solutions in diverse multi-agent systems.
8

---

Published as a conference paper at ICLR 2020
Ablations. The significantly better performance of CM3 versus "Direct" (Figures 5i to shows that learning individual goal attainment prior to learning multi-agent cooperation, and initializing Stage with Stage parameters, crucial for improving learning speed and stability. It gives evidence that while global action-value and credit functions may be difficult to train from scratch, function augmentation significantly eases the learning problem. While "QV" initially learns quickly to attain individual goals, it does so at the cost of frequent collisions, higher variance, and inability to maintain cooperative solution, giving clear evidence for the necessity of the credit function.
CONCLUSION
We presented CM3, a general framework for cooperative multi-goal MARL. CM3 addresses the need for efficient exploration to learn both individual goal attainment and cooperation, via a two-stage curriculum bridged by function augmentation. It achieves local credit assignment between action and goals using credit function in multi -oaal policy gradient. In diverse experimental domains, CM3 attains significantly higher performance, faster learning, and overall robustness than existing MARL methods, displaying strengths of both independent learning and centralized credit assignment while avoiding shortcomings of existing methods. Ablations demonstrate each component is crucial the whole framework. Our results motivate future work analyzing CM3's theoretical properties and generalizing to inhomogeneous systems or settings without known goal assignments.
ACKNOWLEDGMENTS
JY thanks Rakshit Trivedi (Georgia Institute of Technology), Ahmad Beirami (Facebook Al), and Peter Sunehag (DeepMind) for detailed and helpful feedback on this work.
REFERENCES
Austerweil, J. L., Brawner, S., Greenwald. A., Hilliard, E., Ho, M., Littman. M. L., MacGlashan, J., and Trimbach, C. (2016). How other-regarding preferences can promote cooperation in non- zero-sum grid games. In Proceedings of the AAAI Symposium Challenges and Opportunities in Multiagent Learning for the Real World.
Bansal, T., Pachocki, J., Sidor, S., Sutskever, I., and Mordatch, I. (2018). Emergent complexity via multi-agent competition. In International Conference on Learning Representations.
Bengio, Y., Louradour, J., Collobert, R., and Weston, J. (2009). Curriculum learning. In Proceedings of the 26th annual international conference on machine learning. pages 41-48. ACM.
Bhattacharya, S., Likhachev, M., and Kumar, V. (2010). Multi-agent path planning with multiple tasks and distance constraints. In Robotics and Automation (ICRA), 2010 IEEE International Conference on, pages 953-959 IEEE.
Blizzard Entertainment (2019). Starcraft ii cessed 2019-09-07.
Last ac-
Cao, Y., Yu, W., Ren, W., and Chen, G. (2013). An overview recent progress in the study of distributed multi-agent coordination. IEEE Transactions on Industrial informatics, 9(1), 427-438.
Carion, N., Synnaeve, G., Lazaric, A., and Usunier, N. (2019). A structured prediction approach for generalization in cooperative multi-agent reinforcement learning. In Advances neural information processing systems.
Chang. Y.-H., Ho, T., and Kaelbling, L. (2004). All learning is local: Multi-agent learning in global reward games. In Advances in neural information processing systems, pages 807-814.
Foerster, J. N., Farquhar, G., Afouras, T., Nardelli, N., and Whiteson. S. (2018). Counterfactual multi-agent policy gradients. In Thirty-Second AAAI Conference Artificial Intelligence.
Gupta, J. K., Egorov, M., and Kochenderfer, M. (2017). Cooperative multi-agent control using deep reinforcement learning. In International Conference on Autonomous Agents and Multiagent Systems, pages 66-83. Springer.

---

Published as a conference paper at ICLR 2020
Hemandez-Leal, P., Kartal, B., and Taylor, M. E. (2018). Is multiagent deep reinforcement learning the answer or the question? a brief survey. arXiv preprint arXiv:1810.05587.
Hu, J. and Wellman, M. P. (2003). Nash q-learning for general-sum stochastic games. Journal of machine learning research, 4(Nov,, 1039-1069.
Isele, D., Rahimi, R., Cosgun, A., Subramanian, K., and Fujimura, K. (2018). Navigating oc- cluded intersections with autonomous vehicles using deep reinforcement learning. In 2018 IEEE International Conference on Robotics and Automation (ICRA), pages 2034 2039. IEEE.
Jaderberg, M., Czarnecki, W. M., Dunning, I,, Marris, L.,, Lever, G., Castaneda, A. G., Beattie, C., Rabinowitz, N. C., Morcos, A. S., Ruderman, A., et al. (2019). Human-level performance in 3d multiplayer games with population-base reinforcement learning. Science, 364(6443), 859,
Kuefler, A., Morton, J., Wheeler, T., and Kochenderfer, M. (2017). Imitating driver behavior with generative adversarial networks. In 2017 IEEE Intelligent Vehicles Symposium (IV), pages 204-211. IEEE.
S., Wu, Y., Cui, X., Dong, H., Fang, F., and Russell, S. (2019). Robust multi-agen reinforcement learning via minimax deep deterministic policy gradient. In AAAI Conference on Artificial Intelligence (AAAI).
Lillicrap, T. P., Hunt, J. J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D. (2016). Continuous control with deep reinforcement learning. In International Conference on Learning Representations.
Lin, K., Zhao, R., Xu, Z., and Zhou, J. (2018). Efficient large-scale fleet management via multi-agent deep reinforcement learning. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1774-1783. ACM.
Littman, M. L. (1994). Markov games framework for multi-agent reinforcement learning. In Machine Learning Proceedings 1994, pages 157-163. Elsevier.
Liu, S., Lever, G., Merel, J., Tunyasuvunakool, S., Heess, N., and Graepel, T. (2019). Emergent coordination through competition. In International Conference on Learning Representations.
Lopez, P. A., Behrisch, M., Bieker-Waid L., Erdmann, J., Flötteröd, Y.-P., Hilbrich, R., Lückenn L., Rummel, J., Wagner, P., and Wießner, E. (2018). Microscopic traffic simulation using SUMO. In The 21st IEEE International Conference on Intelligent Transportation Systems. IEBE.
Lowe, R., Wu, Y., Tamar, A., Harb, J., Abbeel, O. P., and Mordatch, I. (2017), Multi-agent actor-critic for mixed cooperative-competine environments. Advances in Neural Information Processing Systems, pages 6382-6399
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., et al. (2015). Human-level control through deep reinforcement learning. Nature, 518(7540), 529.
Mordatch, I. and Abbeel, P. (2018), Emergence of grounded compositional language in multi-agent populations. In Therod AAAI Conference on Artificial Intelligence.
Nguyen, D. T., Kumnr, A., and Lau, H. C. (2018). Credit assignment for collective multiagent rl with global rewards. In Advances in Neural Information Processing Systems, pages 1112-8123
Oliehoek, A., Spaan, M. T., and Vlassis, (2008). Optimal and approximate q-value functions for decentralized pomdps. Journal of Artificial Intelligence Research, 32, 289-353.
Onidshafiei, S., Pazis, J., Amato, C.,, How, P., and Vian, J. (2017). Deep decentralized multi-task multi-agent reinforcement learning under partial observability. In International Conference on Machine Learning, pages 2681-2690.
Pan, S. J. and Yang. Q. (2010). A survey on transfer learning. IEEE Transactions on knowledge and data engineering, 22(10), 1345-1359.
10

---

Published as a conference paper at ICLR 2020
Panait, L. and Luke, S. (2005). Cooperative multi- agent learning: The state of the art. Autonomous agents and multi-agent systems, 11(3). 387-434.
Pynadath, D. V. and Tambe, M. (2002). The communicative multiagent team decision problem: Analyzing teamwork theories and models. Journal of artificial intelligence research, 16, 389-423.
Rashid, T., Samvelyan, M., Schroeder, C., Farquhar, G., Foerster, J., and Whiteson, S. (2018). QMIX: Monotonic value function factorisation for deep multi-agent reinforcement learning. In Proceedings of the 35th International Conference on Machine Learning, pages 4295-4304.
Rusu, A. A., Rabinowitz, N. C.,, Desjardins, G., Soyer, H., Kirkpatrick, J., Kavukcuoglu, K., Pascanu, R., and Hadsell, R. (2016). Progressive neural networks. arXiv preprint arXiv: 060..046677
Schaul, T., Horgan, D., Gregor, K., and Silver, D. (2015). Universal value function approximators. In International Conference on Machine Learning, pages 1312-1320.
Shoham, Y., Powers, R., and Grenager, T. (2003). Multi-agent reinforcement learning: critical survey. Technical report, Technical report, Stanford University.
Shu, T. and Tian, (2019). M3rl: Mind-aware multi-agent management reinforcement learning. In International Conference Learning Representations.
Silver, D., Lever, G., Heess, N., Degris, T., Wierstra, D., and Riedmiller, M. (2014). Deterministic policy gradient algorithms. In ICML.
Singh, A., Jain, T., and Sukhbaatar, S. (2019). Learning when to communicate at scale in multiagent cooperative and competitive tasks. International Conference on Learning Representations.
Son, K., Kim, D., Kang, W. J., Hostallero, D., and Yi, Y. (2019). Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. In International Conference on Machine Learning.
Srinivasan, S., Lanctot, M., Zambaldi, V., Pérolat, J., Tuyls, K., Munos, R., and Bowling, M. (2018 8). Actor-critic policy optimization partially observable multiagent environments. Advances in Neural Information Processing Systems, pages 1439..439.
Stone, P. and Veloso, M. (2000). Multiagent systems: A survey from machine learning perspective. Autonomous Robots, 8(3), 345-383.
Sukhbaatar, S., Fergus, R., et al. (2016). Learning multiagent communication with backpropagation. In Advances Neural Information Processing Systems, pages 2244 -2522.
Sunehag, P., Lever, G., Gruslys, A., Czarnecki, W. M., Zambaldi, V., Jaderberg, M., Lanctot, M., Sonnerat, N., Leibo, J. Z., Tuyls, K., et al. (2018). Valoe-decompositionn networks for cooperative multi-agent learning based on team reward. In Proceedings of the 17th International Conference Autonomous Agents and MultiAgent Systems, pages Autonomous Agents and Multiagent Systems.
International Foundation for
Sutton, R. S., Precup, D., and Singh, S. (1999). Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2), 181-2.1.
Sutton, R. S., McAllester, D. A., Singh, S. P., and Mansour, Y. (2000). Policy gradient methods for reinforcement learning with function approximation. In Advances in neural information processing systems, pages 1057-1063.
Tampuu, A., Matüisen T., Kodelja, D.,, Kuzovkin, I., Korjus, K., Aru, J., Aru, J., and Vicente, R. (2017). Multiagent cooperation and competition with deep reinforcement learning. PloS one, 12(4), e0172395.
Tan, M. (1993). Multi-agent reinforcement learning: Independent vs. cooperative agents. In Proceedings of the tenth international conference on machine learning, pages 330-337.
Taylor, M. E. and Stone, P. (2009). Transfer learning for reinforcement learning domains: A survey. Journal of Machine Learning Research, 10(Jul), 1633-1685.

---

Published as a conference paper at ICLR 2020
Thrun, S. B. (1992). Efficient exploration in reinforcement learning. Technical report, Carnegie Mellon University, Pittsburgh, PA, USA.
Van Lange, P. A., Joireman, J., Parks, C. D., and Van Dijk, E. (2013). The psychology of social dilemmas: A review. Organizational Behavior and Human Decision Processes, 120(2), 125-141.
Vezhnevets, A. S., Osindero, S., Schaul, T., Heess, N., Jaderberg, M., Silver, D., and Kavukeuoglu, K. (2017). Feudal networks for hierarchical reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 3540-3549 JMLR. org.
Wu, C., Rajeswaran, A., Duan, Y., Kumar, V., Bayen, A. M., Kakade, S., Mordatch, I., and Abbeel, P. (2018). Variance reduction for policy gradient with action-dependen factorized baselines. In International Conference on Learning Representations.
Zhang, K. Yang, Z., Liu, H., Zhang, T., and Basar, T. (2018). Fully decentralized multi-agent reinforcement learning with networked agents. In Proceedings of the 35th International Conference on Machine Learning, pages 5872-5881.
Zhang. 7., Yang, J., and Zha, H. (2019). Integrating independent and centralized multi-agent reinforcement learning for traffic signal network optimization. arXiv preprint arXiv: 1909. 1065
12

---

Published as a conference paper at ICLR 2020
A ALGORITHM
Algorithm 1 Cooperative multi-goal multi-stage multi-agent reinforcement learning (CM3)
1: for curriculum stage c to 2 do
2: if = 1 then
3: Set number of agents N =1
4: Initialize Stage main networks 2= =
Q' ======""" == n² with parameters lqr, 0,'
5: Initialize target networks with 0r 21, 22
6:
else if c= 2 then
7:
Instantiate N >> 1 agents
8:
Construct global Qg (n, = 1Q', Qg) credit function Q. Q ( {Q), Q22) and x (- 3 using function augmentation with parameters QQ Qq Oz
9:
Initialize target networks with 82,
10:
Restore values of trained parameters 0Qt, 0,, into the respective subsets of 0q pq. O
end
12:
Set all target network weights to equal main networks weights Initialize exploration parameter e Estart and empty replay buffer B for each training episode
13:
14:
to E do Assign goal(s) g. to agent(s) according to given distribution Get initial state 81 and observation(s) 0n
15:
17:
for t= to T do // execute policies in environment
Sample action of [aa" [o," (g.,) for each agent. Execute action(s) a,, receive {ri ha S1+1, and O++1 Store (st: Ot, ges a, {oZ) JriJn Ry. St+1, 0(+1) into B f- S141.0 +- O1+1
19:
21:
22:
end for
23:
if e mod Emin 0 then
24:
for epochs 1... K do conduct truining
25:
Sample minibatch of S transitions (st, O, gi a, (ri) Ins 81+1, 0,-1) from B
26:
Compute global target for all n: x. = rf + QQ(4 a411, 9:¹ 8 laatoo
27:
Gradient descent on C(OQ,) = } En (x. Q(s a. g:: 0Q,))
28:
= then A AT a.) Q* ai Mzi 021) E., क Tiā:lo, 9n QQ' (8 ai 91 0Q1)
29:
30:
else if then
31:
Vm, n E [1..N], compute target yf r. + s1+1 +1. 0 Nom wost
32:
Minimize L(OQ.) E. Σ
Em=
(v
( a." 9hhh 0Q
33:
AT (5;, a, = Qs ai g. (0,)
2
am
Ti
((;;, ā g. 0q.)
34:
end if
35:
V - I mm VV, log π. (a ",,","" ) A n,m (st, a.)
36:
Update policy: 0x - 0~ + J
Update all target network parameters using: 8 7 (1 T 0 Reset buffer B
38:
39:
end for end if
40:
41:
If > 6ends then f- E Estep
42:
end for
43:
end for
Off-policy training with large replay buffer allows RL algorithms to benefit from less correlated transitions (Silver et al. 2014 Lillicrap et al., 2016). The algorithmic modification for off-policy training is maintain circular replay buffer that does not reset (i.e. remove line 38), and conduct training (lines 24-41) while executing policies in the environment (lines 17-22). Despite introducing bias in MARL, found that off- off-policy training benefited CM3 in SUMO and Checkers.
13

---

Published as a conference paper at ICLR 2020
B DERIVATIONS
B.I PROPOSITION T
By stationarity and relabeling the credit function be written:
00
(s a = ET 7 R(s ar. so = 8, 40 = m
E
81 = 8, aj = a
[=1
Using the law of iterated expectation, the credit function satisfies the Bellman expectation equation
@ (8, (, ENT 7' R(st, ar. g²) = =8,00 aa
Ex
R(so, an, )") +
2 RRss;, ar, 9e) ) 80 =8,00 = =
- (50,00:
Ex
R(su. ap. 8") +
) R(s, ac. ar. | = s, 00 = =a"... 81 = =s'a"" am
Su = 8, 0g
a
1=1
Σ Taa m s, " R 8, (a n a ),""")
00
+ E
7 R(s;, az gr:
|00 = s, 0 = aam 81 = s',a"" am
s0 = s, ab a
Σ π
s
R(s, (am m)) 9)
a3 80.7 Err Σ
E
R(ss ax ,r, 80 = 8.00 am 81 8',aT" âm
80 8, 0 am
Σ
(a ml 3,g
H(s, (a )""")
Σ (a m2 8,
P(s'ls, (a",a=" Σ
x (0000'))'')0))))))( (
R(st,ar,
81 = 6' am
am
Σ
(a 8, m R(ss (amh, ",)"")))))
y Σ P(s' ((s")s,(a")) (a m)) Σ T(a"l 1- R( aq 9²) 81 = sa am
Σ Taa m ss s.-- m) (a", a,)g")))))))) + Σ P(s'|s, (mm a am)) Σ T. (a 0n (s'( (s') 2 (s', am)
8m
Ex R(s ar, g") + 70 (x0 = -, s, = a
The goal-specific joint value function is the marginal of the credit function:
V (T(()
E
7 R(st,
8o =
t=0
Eng / se
E
? R(st, as, g²) so s, s,a a
80
Σ
) am)
14

---

Published as a conference paper at ICLR 2020
The credit function can be expressed in terms of the goal-specine action-value function:
(s) = Σ T(a a o" 9 (O"""
by
(s) Σ Q
by (
T(a" o" "0""g"")T(( ((aa,ss (s, ""))
ahh
(s,
Σ T(a 9 (s,
B.2 PROPOSITION 2
First we state some elementary relations between global functions V and QT, a). These carry over directly from the case an MDP, by treating the joint policy π as as an effective "single-agent" policy and restricting attention to single goal g" (standard derivations are included the end of this section).
@T a) = a(s,, + E P(S
(*) = Σ ma
(8)
We follow the proof of the policy gradient theorem Sutton el al. 2000
(s) V Σ T(als,g)(H
+7 P(s)ss.))
Σ
(ol a(als))) Σ P(57\s.a)
* k8,k [(Vor(als (by recursively unrolling)
Voln(T) = VoV Σ
k P(so k Σ (7
k=
(s) Σ T(a gaals.g)(v (V (M
Ex (Vo log (als, g)) 0 as)
We can replace Q (s, a) by the advantage function A (s. a) = Q (s, (s), which does not
change the expectation in Equation because:
Ex Vo V (s)] = Σ (T(s)
Σ Taa (Taassg) log π (als.
Σ (3) Σ (a)s,
So the gradient can be written
VT),(TT) Ex
(Vo m=
log (a om "m" (QT vT)) (s)
(10)
15

---

Published as a conference paper at ICLR 2020
Recall that from 3 for any choice of agent label & [1..N]:
V (s) = Σ T(a" T(a""o" (0
(1I)
Then substituting 33 into 10
VGJn(TT) ET V Σ
log a la""(""""".""")) A (s.aa
(12)
m=1
(5, = Q (s,a)
Σ M lot 9 ) Q7
(13)
a
Now notice that the choice of k in [13 completely arbitrary, since 3 holds for any k E [I..N]. Therefore, it is valid to distribute A & (8, a) into the summation in (12) using the summation index
m instead of k. Further summing 112 over all n, we arrive at the result of Proposition 2
VoJ(TT = E
Σ
Vo log "o" lo") A A7 (s.
m= ==1
A Amm (8, = Q (s, a)
T omh .9" (m))n((s (s
The relation between V (s) and (s a) and (8) are derived as follows:
(s, = E, Σ 7d R(s,, ar, ) 8,
Fy R(s0 an, 8dd +
R(s,, ar. 800 8, = al
-Rs,,,g")) + Ean a0
Er
R(si, a( ac, 80 s, ag a, 81 5
80 8, ag
R(s,a, )d) + Σ P(
R(5,, "1,""" / 81 =
R(s, ) + Σ a(5
(s) = E
? R(st, at, gdd
|800 =s]
Eng. 10.
E
R(ss, ar 9") so s.a0 a
(=U
Σ (aass
(t(ss,ar,g'))
ag
1=0
Σ T(als, ()
16

---

Published as a conference paper at ICLR 2020
C VARIANCE
C.I VARIANCE OF COMA GRADIENT.
Let : Q (s, a, g) denote the centralized Q function, let (Taa) == lo"" gg") denote a single agent's s policy, and let xaa -") [<"""o "g denote the other agents' joint policy.
In cooperative multi-goal MARL, the direct application of COMA has the following gradient.
Velogr(a" g (Q bn ..))
V&J
bn bn a 22 g
Σ =(a"lo", """""""g"""""""""""""" g²) (s, ."
Define the following:
Zm == V log laggoa"'o"""""
fn == Vo clogn(a"'00 "0") - bs(sa =2 bn
Define Mnm = En and let M = En, Mon.
Ex
Then we have Mnm
Ex [zn Q)2RE [2m Q) since
Ex bn] ES
Σ g Volog g")bn an
Σ p" 88)
(a
T(a """og
ΣN7())
"(a
Vo ("""
2
Σ0 pT (8)
(a 10
bn 9
V. Σ
T(a"'o".""" =0
Since the COMA gradient is Ex EN
fu]. its variance can be derived to be Wu al. 2018
N
Var
fn)
En
T Zn 2n
Q2
-2b, 2n b 2n
E
T Zn
(Q bQ bmm) - M
C.2 VARIANCE OF THE CM3 GRADIENT
For convenience, let Qn == QT (s, a) = QT a, gd) denote the global Q function for goal g", and
let (a (aa loth ). The CM3 gradient can be rewritten
VoJ(T) = Ex
Ve log T(a" (Q brom (s))
1=1
bam (3) = Σ a(aa)) ((a")QQ (H,aaaaa)))
As before, = Va log ). Define Im Zm (nn bam (8)) and let hn : Em ham Then the variance is
Var Σ kn)
Var(hw) + Σ Cov hem)
72
mgfin
Var + Σ
Σ
Cov ((hammmmnn)) Σ Σ Cov(hnn Bam)
17

---

Published as a conference paper at ICLR 2020
D EXAMPLE OF GREEDY INITIALIZATION FOR MARL EXPLORATION
greedy initialization can provide significant improvement in multi-agent exploration versus naive random exploration, shown by simple thought experiment. Consider two-player MG defined by a 4 X 3 gridworld with unit actions (up, down, left, right), Agent starts at (1,2) with goal (4,2), while agent B starts at (4,2) with goal (1,2). The greedy policy for each agent in MG is to move horizontally toward its target, since this optimal in the induced M (when the other agent is absent). and take random actions (p(a) = 1 144 with probability Then the probability of a symmetric optimal trajectory is p (ccopperate) 2c2 - e/4) For e 0.5, P P(cooperate) 0.01. Case 2: If agents execute uniform random exploration, then P(cooperate) = 3.05e-5 < 0.01.
Case 1: Suppose that for E (0, 1), and B follow greedy policies with probability
E GENERALIZATION
Table 1: Test performance with heavy traffic difficult initial and goal lanes configurations
Config
Initial lanes
Goal lanes
CM3
IAC
COMA
C1
[1,2]
3, 0]
16.17
11,40
10.00
C2
Unif. random
Unif. random
14.93
12.20
12.93
C3
[1
2,
15.85
14.32
15.00
C4
[0,1
3, 2]
16.35
9.73
8.1
We investigated whether policies trained with few agent vehicles (N = 2) on an empty road can generalize to situations with heavy SUMO-controlled traffic. We also tested initial and goal lane configurations (C3 and C4) which occur with low probability when training with configurations C1 and C2. Table Table shows the sum of agents' reward, averaged over 100 test episodes, on these configurations that require cooperation with each other and with minimally-interactive SUMO- controlled vehicles for success. CM3's higher performance than IAC and COMA in training is reflected by better generalization performance on these test configurations. There is almost negligible decrase in performance from train Figure Sd to test, giving evidence to our hypothesis that centralized training with few agents is feasible even for deployment in situations with many agents, for certain applications where local interactions are dominant.
F ABSOLUTE RUNTIME
CM3's higher sample efficiency does not come at greater computational cost, as all methods' runtimes are within an order of magnitude of one another. Test times have no significant difference as all neural networks were similar.
Table 2: Absolute training runtime of all algorithms in seconds
Environment
CM3
IAC
COMA
QMIX
Antipodal
1.14441348
0.9e41120
1.9e4-1238
1.0e4
Cross
1.9e44256
1.5e4+26
1.3c4+12
1.1e4=34
Merge
8.5e3#21
6.8
9.6e3+:294
1.2c4=61
SUMO
9.6e3+2278
1.553
8.7e3+1.3e3
6.3e3=21
Checkers
8.2
8.583+5568
7.7e3+2.2e3
1.e3+11.463
G ENVIRONMENT DETAILS
The full Markov game for each experimental domain, along with the single-agent MDP induced from the Markov game, defined in this section. In all domains, each agent's observation in the Markov game consists of two components, o and o CM3 leverages this decomposition for faster training, while IAC, COMA and QMIX do not.
18

---

Published as a conference paper at ICLR 2020
G.1 COOPERATIVE NAVIGATION
This domain is adapted from the multi-agent particle environment in Lowe et al. (2017). Movable agents and static landmarks are represented as circular objects located 2D unbounded world with real-valued position and velocity. Agents experience contact forces during collisions. A simple model of inertia and friction involved.
State. The global state vector is the concatenation of all agents' absolute position (x, v) E IR² and velocity (Uz, vy) E R²
Observation. Each agent's observation of itself, Oself, is its own absolute position and velocity, Each agent's observation of others, Outhrrs is the concatenation the relative positions and velocities of all other agents with respect to itself.
Actions. Agents take actions from the discrete set do nothing, up, down, left, right, where the movement actions produce instantaneous velocity (with inertia effects).
Goals and initial state assignment. With probability 0.2, landmarks are given uniform random locations in the set (-1, and agents are assigned initial positions uniformly at random within the set (-1, 1)². With probability 0.8, they are predefined as follows (see Figure 3 In "Antipodal", landmarks for agents to 4 have (z, y) coordinates [(0.9,0.9), (-0.9,-0.9), (0.9, -.9. (-0.9.0.9)], while agents to 4 are placed at ((-0.9,-099), (0.9,0.9), (-0.9,0.9), (0.9.-0.9)). In "Intersection", landmark coordinates are ((0.9.-0.15), (-0.9.0.15), (0.15,0.9), (-0.15,-0.9)), while agents placed at [(-0.9,- 0.15), (0.9.0.15), (0.15,-0.9), (-0.15,0.9)]. In "Merge", landmark coordinates are [(0.9.00.), (0.9,022)), while agents are [(-0.9,0.2), (-0.9,-0.2)). Each agent's goal is the assigned landmark position vector.
Reward. At each time step, each agent's individual reward is the negative distance between its position and the position of its assigned landmark. If collision occurs between any pair of agents, both agents receive an additional -1 penalty. A collision occurs when two agents' distance is less than the sum of their radius.
Termination. Episode terminates when all agents are less than 0.05 distance from assigned land- marks.
Induced MDP. This is the N = 1 case of the Markov game, used by Stage of CM3. The single agent only receives Ower- In each episode, its initial position and the assigned landmark's initial position are both uniform randomly chosen from (-1,1)2.
G.2 SUMO
We constructed a straight road of total length 200m and width 12.8m, consisting of four lanes. All lanes have width 3.2m, and vehicles can be aligned along any of four sub-lanes within a lane, with lateral spacing 0.8m. Vehicles are emitted at average speed 30m/s with small deviation. Simulation time resolution was 0.2s per step. SUMO file merge_s _stagetaa __deeee___________e___ rou. xml contains all vehicle parameters, and merge. net xm1 defines the complete road architecture
State. The global state vector s is the concatenation of all agents' absolute position (I, v), normalized respectively by the total length and width of the road, and horizontal speed normalized by 29m/s.
Each agent observation of itself owr is a vector consisting of: agent speed normalized by 29m/s, normalized number of sub-lanes between agent's current sub-lane and center sub-lane of goal lane, and normalized longitudinal distance to goal position. Each agent's ' observation of others otheers discretized observation tensor of shape [13,9,2] centered on the agent, with two channels: binary indicator of vehicle occupancy, and normalized relative speed between agent and other vehicles. Each channel is a matrix with shape [13,9], corresponding to visibility of 15m forward and backward (with resolution 2.5m) and four sub-lanes to the left and right.
Observation.
Actions. All agents have the same discrete action space, consisting of five options: no-op (maintain current speed and lane), accelerate (2.5m/s²) decelerate (-2.5m/s* 2², shift one sub-lane to the left, shift one sub-lane to the right. Each agent's 's action a" is represented as a one-hot vector of length 5.
Goals and initial state assignment. Each goal vector g" is one-hot vector of length 4, indicating the goal lane at which agent n should arrive once it crosses position 1=100m. With probability 0.2, agents are assigned goals uniformly at random, and agents assigned initial lanes uniformly at
19

---

Published as a conference paper at ICLR 2020
random position z=0. With probability 0.8, agent I's goal is lane 2 and agent 2's goal is lane 1, while agent is initialized at lane and agent is initialized at lane 2 (see Figure 4). Departure times were drawn from a normal distribution with mean Os and standard deviation 0.5s for each agent.
Reward. The reward R(s az, g") for agent n with goal g" is given according to the conditions: -1 for a collision; -10 for time-out (exceed 33 simulation steps during episode); 10(1 А) for reaching the end of the road and having a normalized sub-lane difference of A from the center the goal lane; and -0.1 if current speed exceeds 35.7m/
Termination. Episode terminates when 33 simulation steps have elapsed or all agents have x > ~190.
Induced MDP. This is the N 1 case of the Markov game defined above, used by Stage of CM3. The single agent receives only Oself- For each episode, agent initial and goal lanes are assigned uniformly at random from the available lanes.
G.3 CHECKERS
This domain is adapted from the Checkers environment in Sunnhag et adl](20))) is a gridworld with 5 rows and 13 columns (Figure 2). Agents cannot move to the two highest and lowest rows and the two highest and lowest columns, which are placed for agents' finite observation grid to be well-defined. Agents cannot be in the same grid location. Red and yellow collectible reward are placed in a checkered pattern in the middle 3x8 region, and they disappear when any agent moves to their location.
State. The global state s consists of two components. The first is sy, a tensor of shape [3,9,2], where the two "channels" in the last dimension represents the presence/absence of red and yellow rewards as 1-hot matrices. The second is sv, the concatenation of all agents' (x, y) location (integer-valued) and the number of red and yellow each agent has collected so far.
Observation. Each agent's obsevation of others, o Laharr is the concatenation of all other agents' normalized coordinates (normalized by total size of grid). An agent's observation of itself, oar consists of two components. First, V is vector concatenation of agent n'ss normalized coordinate and the number of red and yellow it has collected far. Second, o tensor of shape [5,5,3], centered on its current location in the grid. The tensor has three "channels", where the first two represent presence/absence of red and yellow rewards as 1-hot matrices, and the last channel indicates the invalid locations as a h-hot matrix. The agent's 's own grid location is valid location, while other agents' locations are invalid.
Actions. Agents choose from discrete set of actions do-nothing, up, down, left, right. Movement actions transport the agent one grid cell in the chosen direction.
Goals. Agent A's goal is to collect all red rewards without touching yellow. Agent B's goal is to collect all yellow without touching red. The goal is represented as a I-hot vector of length 2.
Reward. Agent A gets +1 for red, -0.5 for yellow. Agent B gets -0.5 for red, +1 for yellow.
Initial state distribution. Agent A is initialized at (2,8), Agent initialized (4,8). (0,0) the top-left cell (Figure 2)
Termination. Each episode finishes when either 75 time steps have elapsed, or when rewards have been collected.
Induced MDP. For Stage of CM3, the single agent randomly assigned the role of either Agent or Agent B in each episode. Everything else is defined as above.
H ARCHITECTURE
For all experiment domains, ReLU nonlinearity was used for all neural network layers unless otherwise specified. All layers are fully-comnected feedforward layers, unless otherwise spec- ified. All experiment domains have a discrete action space (with [A] = 5 actions), and ac- tion probabilities were computed by lower- lower-bounding softmax outputs of all policy networks by P(a" = i) = (1 - c)softmax(() + +//lA), where is a decaying exploration parameter. To keep neural network architectures similar as possible among all algorithms, neural networks for
20

---

Published as a conference paper at ICLR 2020
COMA differ from those of Foerster et al. (2018) in that we do not use recurrent networks, and we do not feed previous actions into the Q function. For the Q network in all implementations of COMA, the value of each output node i is interpreted as the cetion-value Q(s, a aa = i,g) for agent rt taking action and all other agents taking action a a= Also for COMA, agent n's label vector (one-hot indicator vector) and observation Oseir were used input to COMA's global Q function, to differentiate between evaluations of the Q-function for different agents. These were choices in Foerster et al. (2018) that we retain.
H.1 COOPERATIVE NAVIGATION
CM3. The policy network π² in Stage 1 feeds the concatenation of Oself and goal to one layer with 64 units, which is connected the special layer h. with 64 units, then connected to the softmax output layer with 5 units, each corresponding to one discrete action. In Stage 2, Oothers is connected to a new layer with 128 units, then connected h!
The Q' function in Stage feeds the concatenation of state s, goal g. and 1-hot action a to one layer with 64 units, which connected the special layer h! with 64 units, then to a single linear output unit. In Stage 2, Q' is augmented into both Q a) and Q% (s." as separate networks. For Q (s, a), 8 (part of state 8 excluding agent n)) and a are concatenated and connected to layer with 128 units, then connected to h. For Q (s, am'), 8 (agent portion of state 8) and 8 s- are concatenated and connected to a layer with 128 units, then connected to h
IAC. IAC uses the same policy network Stage 2 of CM3. The value function of IAC concatenates Selr and goal g", connects to layer with 64 units, which connects to a second layer h2 with 64 units, then to single linear output unit. oteers is connected to a layer with 128 units, then connected to h2-
COMA. COMA uses the same policy network as Stage 2 of CM3. The global Q function of COMA computes Qs,, (a", a "") for each agent as follows. Input is the concatenation of state s, all other agents' 1-hot actions a am,, agent n's goal g", all other agent goals g" agent label n, and agent n's observation Serr-- This is passed through two layers of 128 units each, then connected to linear output layer with 5 units.
QMIX. Individual value functions take input (ohar o oo 9") and connects to one hidden layer with 64 units, which connects to the output layer. The mixing network follows the exact architecture of Rashid al. 2018) with embedding dimension 64.
H.2 SUMO
CM3. The policy network T during Stage feeds each of the inputs Oseir and goal g" to a layer with 32 units. The concatenation then connected to the layer h! with 64 units, and connected to softmax output layer with 5 units, each corresponding to one discrete action. In Stage 2, the input observation grid ohher is processed by a convolutional layer with 4 filters of size 5x3 and stride 1x1, flattened and connected to a layer with 64 units, then connected to the layer h! of π
The Q' function Stage feeds the concatenation of state s, goal g. and 1-hot action a to one layer with 256 units, which is connected to the special layer h2 with 256 units, then to single linear output unit. In Stage 2, Q" is augmented into both Q (s. a) and QT( (s)) as separate networks. For Q7 (s, a), s (part of state excluding agent nt), a and g are concatenated and connected to a layer with 128 units, then connected to h.. For QT a."), s (agent m portion of state s), s and g are concatenated and connected to a layer with 128 units, then connected to h!-
IAC. IAC uses the same policy network as Stage 2 of CM3. The value function of IAC concatenates Self and g", feeds it into layer with 64 units, which connects to a layer h2 with 64 units, which connects to one linear output unit. other is processed by a convolutional layer with 4 filters of size 5x3 and stride 1x1, flattened and connected
layer with 128 units, then connected to h2.
COMA. COMA uses the same policy network as Stage 2 of CM3. The Q function of COMA is exactly the same as the one in COMA for cooperative navigation defined above.
QMIX. Individual value functions take input (0% g and connects to one hidden layer with 64 units, which connects to layer he with 64 units. ofhers passed through the same convolutional layer
21

---

Published as a conference paper at ICLR 2020
above and connected to hg. by is fully-com connected to output layer. The mixing network follows the exact architecture of Rashid et al. (2018) with embedding dimension 64.
H.3 CHECKERS
CM3. The policy network n during Stage I feeds o to convolution layer with 6 filters of size 3x3 and stride 1x1, which flattened and connected to layer with 32 units, which is concatenated with Sar, previous action, and its goal vector. The concatenation is connected to a layer with 256 units, then to the special layer h! with 256 units, finally to softmax output layer with 5 units. In Stage 2, others is connected to layer with 256 units, then to the layer /! of 7
The Q" function in Stage is defined as: state tensor 8r fed convolutional layer with filters of size 3x5 and stride 1x1 and flattened. Sarr is given to a convolution layer with 6 filters of size 3x3 and stride 1x1 and flattened. Both are concatenated with s (agent part of the Sy vector), goal g", action a" and Selr. The concatenation is fed to a layer with 256 units, then to the special layer h4 with 256 units, then single linear output unit In Stage 2, Q' is augmented into both (part of state vector sy excluding concatenated and connected to a layer with 32 units, then connected to h For Q" (s, a"),, 8 (agent m portion of state sy) and s are concatenated and connected to a layer with 32 units, then connected to h!
QR a) and Q (s, a"") as separate networks. For Q (s, a), agent n) and a
IAC. IAC uses the same policy network as Stage 2 of CM3. The value function of IAC feeds o convolutional layer with 6 filters of size 3x3 and stride 1x1, which flattened and concatenated with o Ve and goal g". The concatenation is connected to layer with 256 units, then to layer lz2 with 256 units, then single linear output unit. others is connected to a layer with units, then to the layer h2.
COMA. COMA uses the same policy network Stage of CM3. The global Q(s, (a" (a".a" a)")
function of COMA is defined as follows for each agent n. Tensor part of global state is given to a convolutional layer with 4 filters of size 3x5 and stride 1x1. Tensor part of agent n's observation T is given convolutional layer with 6 filters of size 3x3 and stride 1xl. Outputs of both convolutional layers flattened, then concatenated with sv, all other agents' actions an, agent n's goal g", other agents' goals g g", agent n 's label vector, and agent n's vector observation oar, The concatenation is passed through two layers with 256 units each, then a linear output layer with units.
QMIX. Individual value functions defined on Sell, is passed through the convolutional layer as above, connected to hidden layer with 32 units, then concatenated with Sell vs a/-1, and g². This is connected to layer h22 with 64 units. oehers connected to a layer with 64 units then connectd h2. ha is fully-connected to output layer. The mixing network feeds ST into the same convolutional network as above and follows the exact architecture of Rashidd et al. (2018) with embedding dimension 128.
I PARAMETERS
We used the Adam optimizer in Tensorflow with hyperparameters in Tables to Ediv is used to Ediv-
compute the exploration decrement <ste (Estan Fend)
22

---

Published as a conference paper at ICLR 2020
Table Parameters used for CM3, ablations, and basclines in cooperative navigation
CM3
Parameter
Stage
Stage 2
QV
Direct
IAC
COMA
QMIX
Episodes
le3
8e4
8e4
8e4
8e4
8e4
8e4
Estart
1.0
0.5
0.5
1.0
1.0
1.0
1.0
Fend
0.01
0.05
0.05
0.05
0.05
0.05
0.05
Cdiv
1e3
2e4
2e4
8e4
8e4
2e4
8e4
Replay buffer
le4
le4
le4
le4
le4
le4
le4
Minibatch size
256
128
128
128
128
128
128
Episodes per train
10
10
10
10
10
10
N/A
Learning rate
le-4
le-4
1e-4
1e-4
le-4
le-5
N/A
Learning rate Q
le-3
le-3
1e-3
1e-3
N/A
le-4
le-3
Learning rate V
N/A
N/A
1e-3
N/A
le-3
N/A
N/A
Epochs
24
24
24
24
24
24
NA
Steps per train
N/A
N/A
N/A
N/A
N/A
N/A
Max env steps
25
50
50
50
50
50
50
Table Parameters used for CM3 and baselines in SUMO
CM3
Parameter
Stage
Stage 2
QV
Direct
IAC
COMA
QMIX
Episodes
2.5e3
5e4
5e4
5e4
5e4
5e4
5e4
Cstart
0.5
0.5
0.5
0.5
0.5
0.5
0.5
Gend
0.05
0.05
0.05
0.05
0.05
0.05
0.05
Estep
2e3
le3
4e4
4e4
le3
le4
4e4
Replay buffer
le4
2e4
2e4
2e4
2e4
2e4
2c4
Minibatch size
128
128
128
128
128
128
128
Steps per train
10
10
10
10
N/A
N/A
10
Episodes per train
N/A
N/A
N/A
N/A
10
N/A
Learning rate π
le-4
1e-4
le-4
1e-4
1e-4
1e-4
N/A
Learning rate Q
le-3
le-3
1e-3
le-3
N/A
le-3
le-3
Learning rate V
N/A
N/A
le-3
N/A
le-3
N/A
N/A
Epochs
N/A
N/A
N/A
N/A
33
33
N/A
Max env steps
33
33
33
33
33
33
33
Table 5: Parameters used for CM3 and baselines Checkers
CM3
Parameter
Stage
Stage 2
QV
Direct
IAC
COMA
QMIX
Episodes
5e3
5e4
5e4
5e4
5e4
5e4
5e4
Cstart
1.0
0.5
0.5
1.0
1.0
1.0
1.0
Cand
0.1
0.1
0.1
0.1
0.1
0.1
0.1
éstep
5e2
le3
le3
le4
2e4
le4
le4
Replay buffer
le4
le4
le4
le4
le4
le4
le4
Minibatch size
128
128
128
128
128
128
128
Steps per train
N/A
10
10
10
N/A
N/A
10
Episodes per train
10
N/A
N/A
N/A
10
10
N/A
Learning rate
le-4
le44
le-4
1e-4
1e-4
le-4
N/A
Learning rate Q
le-3
le-3
le-3
le-3
N/A
le-3
le-5
Learning V
N/A
N/A
le-3
N/A
le-3
N/A
N/A
Epochs
10
N/A
N/A
N/A
33
33
N/A
Max env steps
75
75
75
75
75
75
75
23

---

Published as a conference paper at ICLR 2020
J STAGE 1
The Stage functions Q' and x for single agent are trained with the 1 equivalents of and
I(0q)= = Ex [vi - Dog (ss, (s))
(14)
yi R( ai g²)) + 2o0 (141)
(15)
VoJ(=²) = E Vo (() (8, (a) (c,
(16)
Stage training curves for all three experimental domains are shown in Figure 6
-10
Reward
Noward
-22
-30
562
1202
1000
2000
2503
1020
2000
5000
4000
5000
Eptsode
(a) Cooperative navigation
(b) SUMO
(c) Checkers
Figure 6: Stage reward curves for CM3 in cooperative navigation, SUMO and Checkers.
24


Reviews:
[{"review_id": "r1e0fqAaKr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "Contribution:\n\nThis paper derives a loss for cooperative MARL for the case where agents have individual goals assigned to them.\nThe assumption of individual goals allows for a better credit assignment, as well as effective pre-training of one agent to solve its own goal in isolation. Based on this observation, the paper subsequently proposes a curriculum learning scheme to fully take advantage of this property.\nExperiments in varied domains are shown.\n\nReview:\n\nThe paper is well written and easy to follow, and makes a good case by having a thorough experimental analysis, as well as a theoretical analysis of the credit function.\n\nThe applicability of the method seems rather high, even though there exists multiple MARL environments where the multi-goal assumption will be broken. In a predator-prey domain, for example, the predators can't learn anything because their tasks is not solvable with only one agent. In that context, it seems that stage 1 would be useless, but would stage 2 still work, and if yes how would that compare to other baseline methods?\n\nSome details of the multi-stage training are a bit unclear to me. Section 4.5 states \"we train an actor \\pi^1 and critic Q^1 to convergence [...]\". However, I don't fully grasp how this agent will be able to learn to solve all the goals? It seems to me that with N=1, equation (5) reduces to normal actor critic with one agent and one goal, but I'd expect that the policy must be trained on all the goals, as this is hinted at in section 5 (\" in Checkers, we alternate between training one agent as A and B\"). Could you clarify that part?\n\nAbout the function augmentation, could you clarify how the new network \\pi^2 is initialized? It seems that the initial values of W^1 and W^{1:2} in particular are quite important, because if the resulting policy is too far off from the initial policy \\pi^1, then the benefit of the pre-training could be lost on the way. Did you find that any special care like initializing W1 = I and W^{1:2} = 0 is required here?\n\n\nOne minor complaint is that the proposed method never seems to achieve statistically better performance than the best baseline on any of the tasks (for cooperative navigation it is tied with IAC and for SUMO and Checkers it is tied with QMIX). But since the best baseline is different across tasks, it suggests that the proposed method is more versatile.\n\n\nA potentially relevant missed reference: [1].\n\n\n[1] A Structured Prediction Approach for Generalization in Cooperative Multi-Agent Reinforcement Learning, Carion et al, https://arxiv.org/abs/1910.08809\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Hyg_RfRAtr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 presents a new method CM3 for multi-goal multi-agent settings where agent must care about the rewards of others as well as theirs. The method restructures the problem into two-stage curriculum where individual agents solve the problem in the individual setting of the environment in the first stage and then more agents are introduced in the multi-agent setting in second stage. The method also uses function augmentation to only learn parameters which are necessary for single agent in first stage and then more parameters are introduced in the second stage. The results are shown on three environments which show that CM3 outperforms the baselines.\n\nThe paper is well-written, motivated and clear to read. A lot of important stuff has been pushed into appendix and experiments/setup require more details but overall I believe paper has significant contributions and results. Therefore, I assign a rating of weak accept which I am happy to raise if clarity of paper can be improved.\n\nThe paper doesn’t comment on parameter counts of CM3 compared with baselines which is also an important factor in choosing one method over the other. I would like to see more quantitative analysis as presented in IAC to understand what is happening behind the scenes. It is very surprising to see that IAC is outperforming COMA in most of the tasks which is opposite of what COMA paper suggested.\n\nOn the note of curriculum [1] and [2] uses curriculum in traffic junction settings to improve overall performance as agent increases. This can be compared to moving from stage 1 to stage 2 but instead we move from less number of agents to more. [2] also suggests that using individualized rewards help in better credit assignment. There is also an assumption in the setup that private observations from all other agents are readily available. It would be interesting to see what would happen if agents have to communicate their private state. So, the paper is also missing discussion on communication protocols (discrete, continuous, through critic) [1][2]. \n\nIt is hard to directly compare through the charts. So, tables in Appendix E and F should be moved to the main text. The experiment section needs to be extended and the main model section needs to be decreased in the content amount.\n\nIt seems like you missed 1/n in advantage function’s equation in Section 3, Multi-agent credit assignment section. Figure 6 has been mentioned in 6 second paragraph but doesn’t appear until the last page.\n\n[1] Sukhbaatar, Sainbayar, and Rob Fergus. \"Learning multiagent communication with backpropagation.\" In Advances in Neural Information Processing Systems, pp. 2244-2252. 2016.\n[2] Singh, Amanpreet, Tushar Jain, and Sainbayar Sukhbaatar. \"Learning when to communicate at scale in multiagent cooperative and competitive tasks.\" arXiv preprint arXiv:1812.09755 (2018).", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJlEGDCkqS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "This paper presents a method for adding credit assignment\nto multi-agent RL and proposes a way of adding a curriculum\nto the training process.\nThe best heuristics and structures to incorporate in the\nmodeling, learning, and exploration parts of multi-agent\nRL are still largely unknown and this paper explores some\nreasonable new ones.\nIn most of the tasks this is evaluated on in Figure 5\nthis approach adds a slight improvement to the SOTA\nand I think an exciting direction of future work is\nto continue pushing on multi-agent RL in even more\ncomplex envirnoments where the SOTA break down in\neven worse ways.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper was generally well received by reviewers and was rated as a weak accept by all.
The AC recommends acceptance.

Decision: Accept (Poster)