RODE: Learning Roles to Decompose Multi-Agent Tasks
Authors: Tonghan Wang
Tarun Gupta
Anuj Mahajan
Bei Peng
Shimon Whiteson
Chongjie Zhang
Venue: ICLR 2021 Poster (2021)
Keywords: Multi-Agent Reinforcement Learning
Role-Based Learning
Hierarchical Multi-Agent Learning
Multi-Agent Transfer Learning

Abstract: Role-based learning holds the promise of achieving scalable multi-agent learning by decomposing complex tasks using roles. However, it is largely unclear how to efficiently discover such a set of roles. To solve this problem, we propose to first decompose joint action spaces into restricted role action spaces by clustering actions according to their effects on the environment and other agents. Learning a role selector based on action effects makes role discovery much easier because it forms a bi-level learning hierarchy: the role selector searches in a smaller role space and at a lower temporal resolution, while role policies learn in significantly reduced primitive action-observation spaces. We further integrate information about action effects into the role policies to boost learning efficiency and policy generalization. By virtue of these advances, our method (1) outperforms the current state-of-the-art MARL algorithms on 9 of the 14 scenarios that comprise the challenging StarCraft II micromanagement benchmark and (2) achieves rapid transfer to new environments with three times the number of agents. Demonstrative videos can be viewed at https://sites.google.com/view/rode-marl.

Published as a conference paper at ICLR 2021
RODE: LEARNING ROLES TO DECOMPOSE MULTI-AGENT TASKS
Tonghan Wang', Tarun "oppaa,Anu) Mahajan', Bei Peng* Institute for Interdisciplinary Information Sciences, Tsinghua University & Univeristy of Oxford
tonghanwang1 9 com
ftarun. gupta, anuj maha jan, bei. eei.pengeecs.o www.c. uk
Shimon Whiteson"
Chongjie Zhang*
Univeristy of Oxford shimon.
Tsinghua University
.ukuk
mhongiie@tsinghua.. edu. cn
ABSTRACT
Role-based learning holds the promise of achieving scalable multi-agent learning by decomposing complex tasks using roles. However, largely unclear how to efficiently discover such a set of roles. To solve this problem, we propose to first decompose joint action spaces into restricted role action spaces by clustering actions according to their effects on the environment and other agents. Learning a role selector based on action effeets makes role discovery much easier because it forms a bi-level learning hierarchy: the role selector searches in smaller role space and at lower temporal resolution, while role policies learn in significantly reduced primitive action-observation spaces. We further integrate information about action effects into the role policies to boost learning efficiency and pol- icy generalization. By virtue of these advances, current state-of-the-art MARL algorithms on 9 of the 14 scenarios that comprise the challenging StarCraft micromanagement benchmark and (2) achieves rapid transfer to new environments with three times the number of agents. Demonstra- tive videos can be viewed at stogsl//e com/ rode-/oordewwee
method (1) outperforms the
INTRODUCTION
Cooperative multi-agent problems are ubiquitous in real-world applications, such as crewless acrial vehicles (Pham et al. 2018 Xu al. 2018) and sensor networks (Zhang & Lesser 2013). However, learning control policies for such systems remains a major challenge. Joint action learning (Claus & Boutilier 1998 learns centralized policies conditioned on the full state, but this global information is often unavailable during execution due to partial observability or communication constraints. Independent learning (Tan 1993) avoids this problem by learning decentralized policies but suffers from non non-staaionarity during learning as it treats other learning agents as part of the environment.
The framework of centralized training with decentralized execution (CTDE) (Foerster et al. 2016 Gupta el al. 2017 Rashid et al. 2018) combines the advantages of these two paradigms. Decentral- ized policies are learned in a centralized manner so that they can share information, parameters, etc., without restriction during training. Although CTDE algorithms can solve many multi-agent prob- lems (Mahjaan et al. 2019 Das et al.) 2019; Wang et al., (2200d), during training they must search in the joint action-observation space, which grows exponentially with the number of agents. This makes it difficult to learn efficiently when the number of agents is large (Samvelyan et al. 2019)
Humans cooperate in more effective way. When dealing with complex tasks, instead of directly conducting collective search in the full action-observation space, they typically decompose the task and let sub-grouph of individuals learn to solve different sub-tasks (Smith 1937] Butler 2012). Once the task is decomposed, the complexity of cooperative learning can be effectively reduced
"Equal advising

---

Published as a conference paper at ICLR 2021
because individuals can focus restricted sub-problems, each of which often involves a smaller vetion-observatton space. Such potential scalability motivates the use of roles in multi-agent tasks, in which each role is associated with certain sub-task and a corresponding policy.
The key question in realizing such scalable learning is how to come up with a set of roles to effectively decompose the task. Previous work typically predefines the task decomposition and roles (Pavón & Gómez-Sanz 2003] Cossentino et al.) 2005 Spanoudakis & Moraitis 2010; [Bon- jean et al. 20144. However, this requires prior knowledge that might not be available in practice and may prevent the learning methods from transferring to different environments.
Therefore, to be practical, it is crucial for role-based methods to automatically learn an appropriate set of roles. However, learning roles from scratch might not be casier than learning without roles, as directly finding an optimal decomposition suffers from the same problem other CTDE learning methods- - searching in the large joint space with substantial exploration (Wang et al. 2020c).
To solve this problem, we propose novel framework for learning ROles to DEcompose (RODE) multi-agent tasks. Our key insight is that, instead of learning roles from scratch, role discovery easier if we first decompose joint action spaces according to action functionality, Intuitively, when cooperating with other agents, only a subset of actions that can fulfill a certain functionality is needed under certain observations. For example, in football games, the player who does not possess the ball only needs to explore how to move or sprint when attacking. In practice, we propose to first learn effect-based action representations and cluster actions into role action spaces according to their effects on the environment and other agents. Then, with knowledge of effects of available actions, we train a role selector that determines corresponding role observation spaces.
This design forms bi-level learning framework. At the top level, a role selector coordinates role assignments in a smaller role space and at a lower temporal resolution. At the low level, role policies explore strategies in reduced primitive action-observation spaces. In this way, the learning complex- ity is significantly reduced by decomposing multi-agent cooperation problem, both temporally and spatially, into several short-horizon learning problems with fewer agents. To further improve learn- ing efficiency on the sub-problems, we condition role policies on the learned effect-based action representations, which improves generalizability of role policies across actions.
We test RODE on StarCraft II micromanagement environments (Samvelyan et al. 2019), Results on this benchmark show that RODE establishes new state of the art. Particularly, RODE has the best performance on 9 out of all 14 maps, including all 5 super hard maps and most hard maps. Visu- alizations of learned action representations, factored action spaces, and dynamics of role selections shed further light on the superior performance of RODE. We also demonstrate that conditioning the role selector and role policies on action representations enables learned RODE policies to be transferred to tasks with different numbers of actions and agents, including tasks with three times as many agents.
2 RODE LEARNING FRAMEWORK
In this section, we introduce the RODE learning framework. We consider fully cooperative multi- agent tasks that can be modelled as a Dec-POMDP (Olichokk et al. 2016) consisting of a tuple G=(T, S, A, P. R, Ω, O, n. 7), where I is the finite set of n. agents, 7 E 1) is the discount factor, and E S is the true state of the environment. each timestep, each agent receives an observation o E Ω drawn according to the observation function O(s, i) and selects action a; E A. forming a joint action a A", leading to a next state s' according to the transition function P( a), and observing reward history T2 E T = (Ω x -)
R(s, a) shared by all agents. Each agent has local action-observation
Our idea is to learn to decompose multi-agent cooperative task into set of sub-tasks, each of which has a much smaller action-observation space. Each sub-task is associated with a role, and agents taking the same role collectively learn role policy for solving the sub-task by sharing their learning. Formally, we propose the following definition of sub-tasks and roles.
Definition 1 (Role and Sub-Task). Given cooperative multi-agent task C= O.
n, (), let be a set of roles. A role Pj E & is a tuple (g), Tp,) where 9j = sub-task and I C T, U3Tn I, and I O Ts 23, J + k. A₃ is the action space of role j.
O,7)
2

---

Published as a conference paper at ICLR 2021
8
Prediction
Role j
4
Pj
AV.
M
$1
Rupresertations
M
Role Selector
Action Reprosetaaion
R2y
A
Action Encoder
Action Represeniations
Avalibble Actions
(o, a
ag
Action
Agent
ofRol
M
M
Vector
Dot Product
Sn
Agent
Network
(a)
(b)
(c)
Figure I: RODE framework. (a) The forward model for learning action representations. (b) Role selector architecture. (c) Role action spaces and role policy structure.
A, C A. U, A, and we allow action spaces of different roles to overlap: |A,nAs 2 0, * k. Tp; T A, - 100 1] is role policy for the sub-task 9j associated with the role.
In our definition, given set roles specifies not only a factorization of the task but also policies for sub-tasks. This role-based formulation is effectively a kind of dynamic grouping mechanism where agents are grouped by roles. The benefit is that we can learn policies for roles instead of agents, providing scalability with the number of agents and reducing search space of target policies. In our framework, an agent decides which role to take by a role selector / that is shared among agents. Here, $ T > T/ is deterministic function that is conditioned on local action-observation history.
Our aim is to learn set of roles T that maximizes the expected global return Q" (st, a:) Es 100 E>in Y ys a., V.. Learning roles involves two questions: learning sub-tasks and role policies. For learning sub-tasks, we need to learn the role selector, ,3, and to determine role action spaces, Aj- These two components determine the observation and action spaces of roles, respectively. We now introduce the framework to learn these components, which is shown in Fig,
2.1 DETERMINING ROLE ACTION SPACES BY LEARNING ACTION REPRESENTATIONS
Restricting the action space of each role can significantly reduce the policy search space. The key to our approach is to factor the action space according to actions' properties and thereby let roles focus on actions with similar effects, such as attacking enemy units the same type in StarCraft II.
To this end, we learn action representations that can reflect the effects of actions on the environment and other agents. The effect of an action can measured by the induced reward and the change in local observations. Therefore, incentivizes including enough information such that the next observations and rewards can be pre- dicted when given the actions of other agents and current observations.
formulate objective for learning action representations that
In practice, we use the predictive model shown in Fig. a() to learn an action encoder fe(:: 0c): R| + Rdd This encoder, parameterized by 9e. maps one-hot actions to d-dimensional represen- tation space. We denote the representation of an action a in this space by 2 i.e., which is then used to predict the next observation of and the global reward r, given the current ob- servation o, of an agent i, and the one-hot actions of other agents, a.j. This model can be interpreted as forward model, which is trained by minimizing the following loss function:
fe (a; 0e),
Le (oes B E...a...''-D
Σ
a.) -6,12 Ae Σ (pr(Zays Os, an)) r)) (1)
where P. and p, are predictors for observations and rewards, respectively, and parameterized by & de is scaling factor, DD is replay buffer, and the sum is carried out over all the agents.
3

---

Published as a conference paper at ICLR 2021
In the beginning, we initialize K roles, each with the full action space. After collecting samples and training the predictive model for te timesteps, we cluster the actions according to their latent representations and set the action space of each role to contain one of the clusters. Outliers are added to all the clusters to avoid action sets consisting of only one action. After this update, training begins and action representations and action spaces of each role are kept fixed during training.
In this paper, we simply use k-means clustering based on Euclidean distances between action repre- sentations, but it can be easily extended other clustering methods. In Appendix [E] we investigate the influence of different & values and how to determine the number of clusters automatically. In practice, we find that the forward model converges quickly. For example, a well-formed represen- tation space can be learned using 50K samples on StarCraft II micromanagement tasks, while the training usually lasts for 2M timesteps.
2.2 LEARNING THE ROLE SELECTOR AND ROLE POLICIES
Learning action representations to cluster actions based on their effects leads to factorization of the action space, where each subset of actions can fulfill a certain functionality. To make full use of such factorization, and primitive actions. At the top level, role selector assigns a role to each agent every e timesteps. After a role is assigned, an agent explores in the corresponding restricted role action space to learn the role policy. We now describe how to design efficient, transferable, and lightweight structures for the role selector and role policies.
bi-level hierarchical structure coordinate the selection of roles
For the role selector, we can simply use conventional Q-network whose input is local action- observation history and output is Q-values for each role. However, this structure may not be efficient because it ignores information about action space of different roles. Intuitively, selecting role is selecting subset of actions to execute for the next timesteps, so the Q-value of selecting a role closely related to its role action space. Therefore, we propose to base the role selector on the average representation of available actions. Fig. [b) shows the proposed role selector structure. Specifically, we call
2,
Zar
())
E
the representation of role Pú. where A is its restricted action space. To select roles, agents share linear layer and a GRU, parameterized by O to encode the local action-observation history into a fixed-length vector hy The role selector, a fully connected network [a(h;;00 03) with parameters 03. then maps h, to 2, E Rdd and we estimate the expected return of agent selecting role Pj as:
Qf P2) 2T,-pp-
Agents select their roles concurrently, which may lead to unintended behaviors. For example, all agents choosing to attack a certain unit type StarCraft II causes overkill. To better coordinate role assignments, we use a mixing network to estimate global Q-values, Qiat- using per-agent utility Q so that the role selector can be trained using global rewards. In this paper, we use the mixing network introduced by QMIX (Rashid et al. 2018) for its monotonic approximation. The parameters of the mixing network are conditioned on the global state and are generated by a hypernetwork (Ha al. 2016) parameterized by Eg. Then we minimize the following TD loss to update the role selector f
)
rite + max (hetes p') Qiad (st, (s,, pi) Σ 00
Ca(Or,, 0g. ED
(4)
where Qhe is target network, p p= (p1, (01,,P,...0 ... . pn)) the joint role of all agents, and the expecta- tion is estimated with uniform samples from a replay buffer D.
After a role is assigned, an agent follows it for the next e timesteps, during which it can only take actions in the corresponding role action space. Each role Pj has role policy Ty₃ T x A, - [0. I] that is defined in the restricted action space. Similar to the role selector, the most straightforward approach to learning role policies is with conventional deep Q-network that directly estimates the Q-values of each action. However, basing Q-values on action representations makes full use of the effect information of actions and can generalize better across actions.
4

---

Published as a conference paper at ICLR 2021
Therefore, we use the framework shown in Fig. (c) for learning role policies. Specifically, agents again use a shared linear layer and a GRU which together encode a local action- observiobservttion history into a vector hy We denote the parameters of these two networks by 0r, Each role policy is fully connected network Spy (hr::pg) with parameters py. whose input is h Soj maps h to 2r, which is a vector in R Using action representations Za. and 2r, we estimate the value of agent i choosing a primitive action dg as:
Qi ax)) 2.. =.,. Fax.
(5)
For learning the Qi using global rewards, we again feed local Q-values into a QMIX-style mixing network to estimate the global ration-valuee Qior(s, a). The parameters of the mixing network are denoted by Ep. This formulation gives the TD loss for learning role policies:
C,(07,: Pps Ep) = ED ( m-ax max Qrot a') (e)((s,))) a'
(6)
Here, Qior is a target network. 0p is the parameters of all role policies, and the expectation is esti- mated with uniform samples from the same replay buffer D as the one for the role selector. More- over, two mixing networks for training the role selector and role policies are only used during train- ing. By virtue of effect- based action representations, our framework is lightweight - in practice, we use single linear layer without activation functions for role policies and a two-layer fully-connected network for the role selector. Basing the role selector and role policies on action representations also enable RODE policies to be rapidly transferred to new tasks with different numbers of agents and actions, which we discuss in detail in Sec. 4.3
3 RELATED WORK
Hierarchical MARL To realize efficient role-based learning, RODE adopts a hierarchical decision-
making structure. Hicrarchical reinforcement learning (HRL) (Sutton et al. 1999 Al-Emran 2015)
has been extensively studied to address the sparse reward problem and to facilitate transfer learning.
Single-agent HRL focuses on learning temporal decomposition of tasks, either by learning sub-
goals (Nachum et al., 201 8b a Levy et al., 2018 Ghosh et al.) 2018) Sukhbaatar et al. 2018 Dwiel [ & Finn 2019 Nasiriany et al.
al.
2019 Dilokthanakul et al. 2019) by discovering
reusable skills (Daniel et al. Gregor et al.
2016 Warde-FFrley et al. 2018] Shankar & Gupta,
2020 Thomas et al. [018]] Sharma et al.] 2020 In multi-agent settings, many challenges, such as
efficient communication (Ossenkopf et al. 2019) and labor division (Wang et al. 2020c) in large systems, necessitate hierarchical learning along the second dimension over agents (Zhang et al., 2010). Ahilan & Dayan (2019) propose hierarchy in FeUdal (Dayan & Hinton 1993; Vezhnevets itt al. 2017) style for cooperative multi-agent tasks, where managers and workers are predefined and workers are expected to achieve the goal generated by managers. Similar hierarchical organizations among agents have been exploited to control traffic lights (Jin & Ma 2018). [ee et al. (2019); Yang et al. (2019) propose use bi-level hierarchies to train (or discover) and coordinate individual skills. Vezhnevets et al.] (2020) extend hierarchical MARL to Markov Games, where a high-level policy chooses strategic responses opponents. RODE proposes to learn multi-agent coordination skills in restricted action spaces and is thus complementary to these previous works.
Dealing with Large Discrete Action Spaces In single-agent settings, being able reason with large number of discrete actions is essential to bringing reinforcement learning to larger class of problems, such as natural language processing (He al. 2016) and recommender systems (Ayush et al. 2020). Sallans & Hinton (2004); Pazis & Parr (2011) represent actions using binary code to reduce the size of large action spaces. Cui & Khardon (2016) 2018) address scalability issues of planning problems by conducting a gradient-based search on a symbolic representation of the state- action value function. [Sharma et al. (2017) show that factoring actions into their primary categories can improve performance of deep RL algorithms on Atari 2600 games (Bellemare et al. 2013). All aforementioned methods assume that a handcrafted binary decomposition of raw actions is provided. Another interesting way to deal with large discrete state-action spaces is by estimating equivalence classes over reward trajectories and learn on quotient MDPs (Mahajan & Tulabandhula 2017a b).
Yet another line of research uses continuous action representations to discover underlying structures of large discrete action spaces, thereby easing training. Vaan Hasselt & Wiering (2009) use policy gradients with continuous actions and select the nearest discrete action. Dulac-Amold et al. (2015)
5

---

Published as a conference paper at ICLR 2021
-64
-63
-0.5 -232
660
3.0 -0.5
Move four directonss
Slop
Allack different unils
Noop
Move
Slop
Allack Zealota
Allack Stalkers
Noop
Figure 2: Action representations learned by our predictive model on corridor (left) and 3s5z_vs vs_3s6z (right). Blue arrows indicate the directions moving towards enemies while red ones show the directions moving away from enemies.
extend this work to large-scale problems but use predefined action embeddings. Tennenholtz & Mannor (2019); Chandak et al. (2019) avoid pre-definitions by extracting action representations from expert demonstrations without prior knowledge. Action representations have been used to solve natural language processing problems (He al. 2016), enable generalization to unseen (Ayush et al. 2020 or under-explored (Chandak et al. 2019) actions in RL, lear linear dynamies that help exploration (Kim et al. 2019). and transfer policy across different tasks (Chen et al. 2019). By contrast,
action representations to factor multi-agent tasks.
Besides learning action representations, Czarnecki et al. (2018): Murali et al. (2018); Farquhar et al. (2020) propose to use curriculum learning over action spaces of increasing sizes scale learning to large spaces. Although the large action space problem is more demanding in multi-agent settings, how to organize effective learning them is largely unstudied most algorithms directly search in the full action spaces, including previous works (Wang et al.) (0200)) that consider the effects (se- mantics) of actions like RODE. This a key motivation for RODE, where search spaces are reduced by an effect-based action space factorization and a role-based hierarchical structure designed for efficient learning in these factored action spaces.
In Appendix G we discuss how RODE is related to other role-based learning approaches and multi- agent reinforcement learning algorithms in detail.
EXPERIMENTS
We design experiments to answer the following questions: (1) Can the proposed predictive model learn action representations that reflect effects of actions? (Sec.44.1 (2) Can RODE improve learning efficiency? If so, which component contributes the most to the performance gains? (Sec. 4.2) (3)
Can RODE support rapid transfer to environments with different numbers of actions and agents? (Sec. 4.3) (4) Can the role selector learn interpretable high-level cooperative behaviors? (Appx.
B
We choose the StarCraft II micromanagement (SMAC) benchmark (Samvelyan al. 2019) as the testbed for its rich environments and high complexity of control. The SMAC benchmark requires learning policies in large action space. Agents can move in four cardinal directions, stop, take noop (do nothing), select an enemy to attack each timestep. Therefore, if there are n,, enemies the map, the action space for each ally unit consists of n, discrete actions.
4.1 ACTION REPRESENTATIONS
For learning action representations, on all maps, we set the scaling factor Àe to 10 and collect samples and train the predictive model for 50K timesteps using the loss function described by Eq. [ The model trained every episode using batch of 32 episodes. Fig. 2 we show the learned action representations two maps, 385z.vs-3862 and corridor.
The map corridor features homogeneous agents and enemies, with 6 Zealots faced with 24 enemy Zerglings. In this task, all attack actions have similar effects because the enemies are homogeneous. Moreover, due to the symmetry of the map, moving northward and eastward exert similar influence on the environment moving the agent towards enemies. Likewise, moving southward and west- ward have the same effect because both actions move agents away from enemies. The learned action encoder captures these underlying structures in the action space (Fig. left). We can observe three

---

Published as a conference paper at ICLR 2021
Weighted Weighttd GMIX (CW-QMMX)
GMIX HSD
RODE
A--
ROMA
6NLMS
NNH2
27mLMs ML 30m
100
100
Te 35
Tost %
50
50
50-
0.5
1.0
2.0
mml)
Tmmill
contidtr
3x52 19_fft
2c 65tg
100
100
100
75
Text
TostWW
50
50
50-
M
0.0
0.5
2.0
2.0
T0ml
Figure 3: Performance comparison with baselines on all super hard maps and one hard map (2c.v8.64zg). In Appendix C.I we show results on the whole benchmark.
clear clusters in the latent action representation space, which correspond the aforementioned three types of actions, respectively. On the map 3s5z vs 3s62, 3 Stalkers and 5 Zealots try to beat 3 en- emy Stalkers and Enemy Zealots. Unlike corridor, the enemy team consists of heterogeneous units, and attacking Stalkers and Zealots have distinct effects. Our predictive model highlights this difference the attack actions are clustered into two groups (Fig. 2 right). Moreover, the learned action encoder also captures the dissimilarity between moving northward/southward and moving in other directions- - these two move actions do not bring agents near to or far away from enemies.
Although only show results two maps, each with random seed, similar action clusters can be observed on the scenarios and are robust across different seeds. Therefore, we conclude that our predictive model effectively learns action representations that reflect the effects of actions.
4.2 PERFORMANCE AND ABLATION STUDY
For evaluation, all experiments in this section are carried out with different random seeds, and the median performance as well as the 25-75% percentiles are shown. The detailed setting of hyper- parameters described in Appendix A
We benchmark our method on all 14 scenarios in order to evaluate its performance across the entire SMAC suite, and the results are shown in Fig. [ We compare with current state-of-the-art value- based MARL algorithms (QMIX (Rashid et al. 2018). QPLEX (Wang et al. 2020b), Weighted QMIX (Rashid el al., 2020a), and AI-QMIX (Iqbal et al., 20200) hierarchical MARL method (HSD, Yang et al. (2019)). role-based MARL method (ROMA, Wang et al. (2020c)), and MARL method based on action semantics (ASN, Wang et al. (2020)). RODE outperforms all the basclines by at least 1 1/32 on of all 14 scenarios after 2M training steps.
Maps of the SMAC benchmark have been classified as easy, hard, and super hard. Hard and super hard maps
Maps Best lout of 14)
Weighted QMIX (OW-QMIX)
8
Weighted (CW-OMIK)
are typically hard-exploration tasks. Since RODE is de-
ASN
signed help exploration by decomposing the joint tion space, we are especially interested in the performance of our method on these maps. Fig. 3 shows the perfor- mance of RODE on all the super hard scenarios and one hard scenario.
AI-OMIX
OMIX
HSD
OPLEX
ROMA
Appendix [..]] we further show learning curves on the whole benchmark. We can see on all super hard maps and most hard maps, RODE has the best per- formance. Moreover, RODE outperforms baselines by the largest margin on the maps that require more exploration: 3s52.vs .366z, corridor, and 6h_vs_8z. In contrast, 5 easy maps, RODE typically needs more samples to learn successful strategy. We hypothesize that this is because
RODE (Gurs)
0.5
(mil)
Figure 4: The number of scenarios (out of all 14 scenarios) in which the algorithm's median test win % is the highest by at least 1/32.

---

Published as a conference paper at ICLR 2021
RODE Spaces QMIX best
Restricted
Rept.
RODE Full Spaces Reper
1.0
100
1.00
80
60
Tea
40
Test
20
20
0.5
2.0
1.0
3.5 T(ml)
0.5
1.5
2.0
3.0
[mi)]
[mmill
Figure 6: Ablation studies regarding each component of RODE. The best performance that can be achieved by QMIX is shown as horizontal dashed lines.
these maps do not require substantial exploration, and the exploratory benefit brought by restricted action spaces is not obvious.
Ablations understand the superior performance of RODE, we carry out ablation studies to test the contribution of its four main components: (A) Restricted role action spaces; (B) Using action effects to cluster actions; (C) The integration of action representations into role policies and the role selector; (D) The hierarchical learning structure. To test component A and B, when updating role action spaces after 50K samples, we let each role action space contains all actions or a random subset of actions, respectively, while keeping other parts in the framework unchanged. For component B, we make sure the union of role action spaces equals the entire action space. To test component C, we can simply conventional Q-networks for learning role policies and the role selector. The testing of component D is a bit different because we cannot ablate it separately while still using different roles. Therefore, we test by ablating components A and C using conventional deep Q-networks for role policies and the role selector and allowing role policies to choose from all primitive actions.
The results on the three most difficult scenarios from the benchmark are shown in Fig. O Gener- ally speaking, performance of RODE using conventional deep Q Q-networks (RODE No Action Repr.) close that of RODE, and is significantly better than the other two ablations where role action spaces are not restricted. Therefore, using action representations in policy learning can help improve learning but the superior performance
RODE mostly due to the restriction of the role action spaces. RODE with full role action spaces and conventional Q-networks (RODE Full Action Spaces No Action Repr.) has similar performance to QMI,, which demonstrates that the hierarchical struc- ture itself does not contribute much to the performance gains. RODE with random restricted role action spaces also cannot outperform QMIX, highlighting the importance of using action effects to decompose joint action spaces.
In summary, by virtue restricted role action spaces and the integration of action effect information into policies, RODE achieves a new state of the art on the SMAC bench- mark. In Appendix B we provide a case study better understand why restricting role action spaces can improve performance. We study the effects of the interval between role selections in Appendix D.I
24
26
28
30
32
34
36
Allies
8.0
0.8
75.0
68.3
6.7
8.0
0.8
0.8
8.0
10
2.5
12
97.5
75.0
74.2
29.2
17.5
9.2
1.7
4.3 POLICY TRANSFER
14
97.5
69.2
42.5
38.3
22.5
5.8
16
A bonus of basing role policies on action representations is that we can transfer the learned policies to tasks with new actions that have similar effects to old ones. To demon- strate this, given a new task, we first collect some samples (50k) and train an action encoder. In this way, we identify the old actions that have similar functionality to the new actions. Then old actions as representations for new actions and add new actions to role action spaces to which the similar old ac- tions belong. Since role action spaces are still expected to contain actions with similar effects, which can be reflected by old role representations, we do not re-calculate the role representations
18
45.0
45.0
Figure 5: Win rates on unseen maps of the policy learned corridor, where 6 ally Zealots face 24 Zerglings. We do not train policies
use the average representation of these
maps.
8

---

Published as a conference paper at ICLR 2021
the new task. Moreover, in our framework, it is roles that are interacting with the environment, and agents only need to be assigned with roles. Therefore, our learned policies can also be transferred to tasks with different numbers of agents.
We test the transferability of our method on the SMAC benchmark. To keep the length of obser- vations fixed, sort allies and enemies by their relative distances to agent and include the information of nearest N₂ allies and N₂ enemies in the visible range. In Fig. | we show win rates of the policy learned from map corridor on different maps without further policy training. In the original task, Zealots face 24 enemy Zerglings. We set Na to 5 and No to 24. We increase the number of agents and enemies, and the number of actions increases as the number of enemies grows. The transferability of RODE is attested by observing that the learned policy can still win 50% of the games on unseen maps with three times the number of agents. More details of this experiment is described in Appendix C.2 Besides rapid transfer, iteratively training the transferred policies on larger tasks may be a promising future direction to scaling MARL large-scale problems.
5 CONCLUSION
Coming up with set of roles that can effectively decompose the task is long standing problem preventing role-based learning from realizing scalability. Instead of learning roles from scratch, in this paper, find that role discovery becomes much easier if we first decompose joint action spaces according to action effects. With a specially designed hierarchical learning framework, we achieve efficient learning over these factored action spaces. We believe that the scalability and transferability provided by our method are crucial in building flexible and parrpoe multi-agent systems.
ACKNOWLEDGMENT
We would like to thank the anonymous reviewers for their insightful comments and helpful sugges- tions. This work is supported in part by Science and Technology Innovation 2030 - "New Genera- tion Artificial Intelligence" Major Project (No. 2018AAA0100904), and grant from the Institute of Guo Qiang, Tsinghua University.
REFERENCES
Sanjeevan Ahilan and Peter Dayan. Feudal multi-agent hierarchies for cooperative reinforcement learning. arXiv preprini urXiv:1901.0880 2019.
Mostafa Al-Emran. Hierarchical reinforcement learning: a survey, International journal of comput- ing and digital systems, 4(02), 2015.
Jain Ayush, Szot Andrew, and J. Lim Joseph. Generalization to new actions in reinforcement learn- ing. In Proceedings of the 37th International Conference on Machine Learning. 2020.
Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent tool use from mulli-agen autocurricula. In Proceedings of the International Conference Learning Representations (ICLR), 2020.
Marc G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environ- ment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47: 253- 2013.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, al. Dota 2 with large scale deep reinforcement learning. arXiv preprint 1912.066880 2019.
Wendelin Böhmer, Vitaly Kurin, and Shimon Whiteson. Deep coordination graphs. In Proceedings of the 37th International Conference on Machine Learning, 2020.
N Bonjean, W Mefteh, MP Gleizes, C Maurel, and Migeon. Adelfe 2.0: Handbook on agent- oriented design processes, m. cossentino, hilaire, molesini, and seidita, 2014.

---

Published as a conference paper at ICLR 2021
Paolo Bresciani, Anna Perini, Paolo Giorgini, Fausto Giunchiglia, and John Mylopoulos. Tropos: An agent-oriented software development methodology. Autonomous Agents and Multi-Agent Sys- tems, 8(3):203-236, 2004.
Eamonn Butler. The condensed wealth of nations. Centre for Independent Studies, 2012.
Lucas Cassano, Kun Yuan, and Ali H Sayed. Multi-agent fully decentralized value function learning with linear convergence rates. arXiv preprint arXiv: 1810.0779,, 2018.
Yash Chandak, Georgios Theocharous, James Kostas, Scott Jordan, and Philip Thomas. Learn- ing action representations for reinforcement learning. In International Conference on Machine Learning, pp. 941-950, 2019.
Yu Chen, Yingfeng Chen, Yu Yang. Ying Li, Jianwei Yin, and Changjie Fan. Learning action- transferable policy with action embedding. arXiv preprint arXiv:1909.0223 2019.
Caroline Claus and Craig Boutilier. The dynamics of reinforcement learning in cooperative multia- gent systems. AAAI/IAA,, 1998(746-752):2, 1998.
Massimo Cossentino, Salvatore Gaglio, Luca Sabatucci, and Valeria Seidita. The passi and agile passi meta-models compared with a unifying proposal. In International Central and Eastern European Conference on Multi-Agent Systems, pp. 183-192. Springer, 2005.
Hao Cui and Roni Khardon. Online symbolic gradient-based optimization for factored action mdps. In IJCAI, pp. 3075-3081, 2016.
Hao Cui and Roni Khardon. Lifted stochastic planning, belief propagation and marginal map. In AAAI Workshops, pp. 658-664, 2018.
Wojeiech Czarnecki, Siddhant Jayakumar, Max Jaderberg, Leonard Hasenelever, Yee Whye Teh, Nicolas Heess, Simon Osindero, and Razvan Pascanu. Mix & match agent curricula for rein- forcement learning. In International Conference on Machine Learning, pp. 1087-1095, 2018
Christian Daniel, Gerhard Neumann, and Jan Peters. Hierarchical relative entropy policy search, In Artificial Intelligence and Statistics, pp. 273-281, 2012.
Abhishek Das, Théophile Gervet, Joshua Romoff, Dhruv Batra, Devi Parikh, Mike Rabbat, and Joelle Pineau. Tarmac: Targeted multi-agent communication. In International Conference on Machine Learning, pp. 1538-1546, 2019.
Peter Dayan and Geoffrey Hinton. Feudal reinforcement learning. In Advances neural infor- mation processing systems, pp. 271-278, 1993.
Scott A DeLoach and Juan Carlos Garcia-Ojeda. O-mase: customisable approach designing and building complex, adaptive multi-agent systems. International Journal of Agent- Oriented Software Engineering. (43):244-280 2010.
Nat Dilokthanakul, Christos Kaplanis, Nick Pawlowski, and Murray Shanahan. Feature control as intrinsic motivation for hierarchical reinforcement learning. IEEE transactions on neural net- works and learning systems, 30(1 1):3409-3415 3418, 2019.
Gabriel Aunol-Amold, Richard Evans, Hado van Hasselt, Peter Sunehag, Timothy Lillicrap, Jonathan Hunt, Timothy Mann, Theophane Weber, Thomas Degris, and Ben Coppin. Deep rein- forcement learning in large discrete action spaces. arXiv preprint 1r1iv:1512.0766 2015.
Zach Dwiel, Madhavun Candadai, Mariano Phielipp. and Arjun K Bansal. Hierarchical policy learning is sensitive to goal space design. arXiv preprint 1905. 2019.
Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu, et al. A density-based algorithm for discovering clusters in large spatial databases with noise. In KDD, pp. 226-231, 1996.
Gregory Farquhar, Laura Gustafson, Zeming Lin, Shimon Whiteson, Nicolas Usunier, and Gabriel Synnaeve. Growing action spaces. In Proceedings of the 37th International Conference on Ma- chine Learning, 2020.
10

---

Published as a conference paper at ICLR 2021
Jakob Foerster, Ioannis Alexandros Assael, Nando de Freitas, and Shimon Whiteson. Learning to communicate with deep multii-geent reinforcement learning. In Advances in Neural Information Processing Systems, pp. 2137-2145, 2016.
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.
Dibya Ghosh, Abhishek Gupta, and Sergey Levine. Learning actionable representations with goal conditioned policies. In International Conference on Learning Representations, 2018.
Deborah M Gordon. The organization of work in social insect colonies. Nature, 380(6570) 1996.
Karol Gregor, Danilo Jimenez Rezende, and Daan Wierstra. Variational intrinsic control. arXiv preprint urXiv:1611.07500 2016.
Carlos Guestrin, Daphne Koller, and Ronald Parr. Multiagent planning with factored mdps. In Advances in neural information processing systems, pp. 1523-1530, 2002a.
Carlos Guestrin, Michail Lagoudakis, and Ronald Parr. Coordinated reinforcement learning. In ICML, volume pp. 227-234. Citeseer, 2002b.
Jayesh K Gupta, Maxim Egorov, and Mykel Kochenderfer. Cooperative multi-agent control using deep reinforcement learning. In International Conference on Autonomous Agents and Multiagent Systems, pp. 66 83. Springer, 2017.
David Ha, Andrew Dai, and Quoc V Le. Hypernetworks. arXiv preprint 1rXiv:1609009110 2016.
Ji He, Jianshu Chen, Xiaodong He, Jianfeng Gao, Lihong Li, Li Deng, and Mari Ostendorf. Deep reinforcement learning with natural language action space. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1621-
1630, 2016.
Edward Hughes, Joel Z Leibo, Matthew Phillips, Karl Tuyls, Edgar Guzman- Anto- nio García Castañeda, lain Dunning, Tina Zhu, Kevin McKee, Raphael Koster, et al. Inequity aversion improves cooperation in intertemporal social dilemmas. In Advances in Neural Informa- fion Processing Systems, pp. 3330-3340, 2018.
Shariq Iqbal and Fei Sha. Actor-attentionnccitie for multi-agent reinforcement learning. In Interna- tional Conference on Machine Learning, pp. 2961-29719 2019.
Shariq Iqbal, Christian A Schroeder de Witt, Bei Peng, Wendelin Böhmer, Shimon Whiteson, and Fei Sha. Ai-qmix: Attention and imagination for dynamic multi-agent reinforcement learning. arXiv preprint 2022:2000600222.,, 2020.
Max Jaderberg, Wojeiech M Czamecki, Tain 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- bassed reinforcement learning. Sci- ence, 364(6443)) 865, 2019.
Natasha Jaques, Angeliki Lazaridou, Edward Hughes, Caglar Gulcehre, Pedro Ortega, Dj Strouse, Joel Leibo, and Nando De Freitas. Social influence as intrinsic motivation for multi-agent deep reinforcement learning. In International Conference on Machine Learning, pp. 3040-3049, 2019.
Raphaël Jeanson, Penelope F Kukuk, and Jennifer H Fewell. Emergence of division of labour in halictine bees: contributions of social interactions and behavioural variance. Animal behaviour, 70(5): 183-1193, 2005.
Junchen Jin and Xiaoliang Ma. Hierarchical multi-agent control of traffic lights based on collective learning. Engineering applications of artificial intelligence, 68:236-222 2888,6-248, 2018.
Hyoungseok Kim, Jaekycom Kim, Yeonwoo Jeong, Sergey Levine, and Hyun Oh Song. Emi: Ex- ploration with mutual information. In International Conference on Machine Learning, pp. 3360- 3369, 2019.
11

---

Published as a conference paper at ICLR 2021
Jelle R Kok and Nikos Vlassis. Collaborative multiagent reinforcement learning by payoff propaga- tion. Journal of Machine Learning Research, (1p.:::7791128., 2006.
Angeliki Lazaridou, Alexander Peysakhovich, and Marco Baroni. Multi-agent cooperation and the
emergence of (natural) language. In Proceedings of the International Conference on Learning Representations (ICLR), 2017.
Youngwoon Lee, Jingyun Yang, and Joseph J Lim. Learning to coordinate manipulation skills via skill behavior diversification. International Conference on Learning Representations, 2019.
Andrew Levy, George Konidaris, Robert Platt, and Kate Saenko. Learning multi-level hierarchies with hindsight. In International Conference Learning Representations, 2018.
Kemas M Lhaksmana, Yohei Murakami, and Toru Ishida. Role-based modeling for designing agent behavior in self-organizing multi-agent systems. International Journal of Software Engineering and Knowledge Engineering. 28(01):79 2018.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-come conpettive environments. In Advances in Neural Information Processing Systems, pp. 6379-6390, 2017.
Sergio Valcarcel Macua, Aleksi Tukiainen, Daniel Garefa-Ocaña Ocaña Hernández, David Baldazo, En- rique Munoz de Cote, and Santiago Zazo. Diff-dac: Distributed actor-critic for multitask deep reinforcement learning. arXiv preprint arXiv: 1710. 10363, 2017.
Anuj Mahajan and Theja Tulabandhula. Symmetry detection and exploitation for function approxi- mation in deep rl. In Proceedings of the 16th Conference Autonomous Agents and MultiAgent Systems, pp. 1619-1621, 2017a.
Anuj Mahajan and Theja Tulabandhula. Symmetry learning for function approximation in reinforce- ment learning. arXiv preprint arXiv: 1706. 02099, 2017b.
Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, and Shimon Whiteson. Maven: Multi-agent
variational exploration. In Advances in Neural Information Processing Systems, pp. 7611-7622,
2019.
Adithyavairavan Murali, Lerrel Pinto, Dhiraj Gandhi, and Abhinav Gupta. Cassl: Curriculum ac- celerated superviie learning. In 2018 IEEE International Conference Robotics and Au- tomation (ICRA), pp. 6453-6460. IEEE, 2018.
Ofir Nachum, Shixiang Gu, Honglak Lee, and Sergey Levine. Near-optimal representation learning for hierarchical reinforcement learning. In International Conference on Learning Representa- tions, 2018a
Ofir Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learning. Advances in Neural Information Processing Systems, pp. 3303-3313, 2b.
Suraj Nair and Chelsea Finn. Hierarchical foresight: Self-supervised learning of long hong-horizon tasks via visual subgoal generation. In International Conference on Learning Representations, 2019.
Soroush Nasiriany, Vitchyr Pong, Steven Lin, and Sergey Levine. Planning with goal-conditioned policies. In Advances Neural Information Processing Systems, pp. 14843-14854, 2019.
Frans A Olichoek, Christopher Amato, al. A concise introduction to decentralized POMDPs, volume 1. Springer, 2016.
Andrea Omicini. Soda: Societies and infrastructures in the analysis and design of agent-based sys- tems. International Workshop on Agent-Oriented Software Engineering, pp. 185-193. Springer, 2000.
Marie Ossenkopf, Mackenzie Jorgensen, and Kurt Geihs. When does communication learning need hierarchical multi-ar multi-agent deep reinforcement learning. Cybernetics and Systems, 50(8):672-692, 2019.
12

---

Published as a conference paper at ICLR 2021
Lin Padgham and Michael Winikoff. Prometheus: A methodology for developing intelligent agents. In International Workshop on Agent- Oriented Software Engineering. pp. 174-185. Springer, 2002.
Juan Pavón and Jorge Gómez-Sanz. Agent oriented software engineering with ingenias. Interna- lional Central and Eastern European Conference on Mulli-Agent Systems, pp. 394-403. Springer, 2003.
Jason Pazis and Ronald Parr. Generalized value functions for large action sets. In Proceedings of the 28th International Conference on International Conference on Machine Learning, pp. 1185- 1192, 2011.
Dan Pelleg, Andrew W Moore, et al. X-means: Extending k-means with efficient estimation of the number of clusters. In International Conference of Machine Learning, volume 1, pp. 727-734, 2000.
Huy Xuan Pham, Hung Manh La, David Feil-Seifer, and Aria Nefian. Cooperative and distributed reinforcement learning of drones for field coverage, 2018.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent rein- forcement learning. International Conference on Muchine Learning, pp. 4292-4301, 2018.
Tabish Rashid, Gregory Farquhar, Bei Peng, and Shimon Whiteson. Weighted qmix: Expanding monotonic value function factorisation for deep agget- reinforcement learning. Advances in Neural Information Processing Systems, 33, 2020a.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder De Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Monotonic value function factorisation for deep multi-agent reinforcement learning. arXiv preprint wxXiv:2003.08833 2020b.
Brian Sallans and Geoffrey E Hinton. Reinforcement learning with factored states and actions. Journal of Machine Learning Research, 5(Aug):1063-1088, 2004.
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. arXiv preprint 1xXi::9902.04443, 2019.
Tanmay Shankar and Abhinav Gupta. Learning robot skills with temporal variational inference. In Proceedings of the 37th International Conference on Machine Learning, JMLR. org, 2020.
Archit Sharma, Shixiang Gu, Sergey Levine, Vikash Kumar, and Karol Hausman. Dynamics-awe aware unsupervised discovery of skills. In International Conference Learning Representations, 2020.
Sahil Sharma, Aravind Suresh, Rahul Ramesh, and Balaraman Ravindran. Learning to factor poli- cies and action-value functions: Factored action space representations for deep reinforcement learning. arXiv preprint arXiv:1705.0722: 07269, 2017.
Adam Smith. The wealth of nations [1776], 1937.
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. In Interna- tional Conference on Machine Learning, pp. 5887-5896, 2019.
Nikolaos Spanoudakis and Pavlos Moraitis. Using aseme methodology for model-driven agent sys- tems development. In International Workshop on Agent-Oriented Software Engineering, pp. 106- 127. Springer, 2010.
Sainbayar Sukhbaatar, Rob Fergus, et al. Learning multiagent communication with backpropaga- tion. In Advances Neural Information Processing Systems, pp. 2244-2252, 2016.
Sainbayar Sukhbaatar, Emily Denton, Arthur Szlam, and Rob Fergus. Learning goal embeddings via self-play for hierarchical reinforcement learning. arXiv preprint arXiv: 18/ 1.09083, 2018.
13

---

Published as a conference paper at ICLR 2021
Changyin Sun, Wenzhang Liu, and Lu Dong. Reinforcement learning with task decomposition for cooperative multiagent systems. IEEE transactions on neural networks and learning systems, 2020.
Peter Sunehag, Guy Lever, Audrunas Gruslys. Wojeiech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Leibo, Karl Tuyls. et al. Value-decomposition networks for cooperative multi-agent learning based on team reward. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pp. 2085-2087, Inter- national Foundation for Autonomous Agents and Multiagent Systems, 2018.
Wesley Suttle, Zhuoran Yang, Kaiqing Zhang, Zhaoran Wang, Tamer Basar, and Ji Liu. A multi- agent off-poliey actor-critic algorithm for distributed reinforcement learning. arXiv preprint arXiv:1903.0637.. 2019.
Richard Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: frame- work for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):181- 211, 1999.
of the tenth international conference on machine learning, pp. 330-337, 1993. Ming Tan. Multi- agent reinforcement learning: Independent cooperative agents. In Proceedings
Guy Tennenholtz and Shie Mannor. The natural language of actions. International Conference on Machine Learning, pp. 6196-6205, 2019.
Valentin Thomas, Emmanuel Bengio, William Fedus, Jules Pondard, Philippe Beaudoin, Hugo Larochelle, Joelle Pineau, Doina Precup, and Yoshua Bengio. Disentangling the independently controllable factors of variation by interacting with the world. arXiv preprint 18Xiv:1802.000 2018.
Hado Van Hasselt and Marco A Wiering, Using continuous action spaces to solve discrete problems. In 2009 International Joint Conference on Neural Networks, pp. 1149-11 156. IEEE, 2009.
Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Heess, Max Jaderberg, David Silver, and Koray Kavukcuoglu. Feudal networks for hierarchical reinforcement learning. arXiv preprint arXiv: 170300111,, 2017.
Alexander Sasha Vezhnevets, Yuhuai Wu, Rémi Leblond, and Joel Z Leibo. Options as responses: Grounding behavioural hierarchies in multi-agent rl. In Proceedings of the 37th International Conference on Machine Learning. JMLR. org, 2020.
Oriol Vinyals, Igor Babuschkin, Wojeiech Czarnecki, Michaël Mathieu, Andrew Dudzik, Juny- oung 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-354 2019.
Jianhao Wang, Zhizhou Ren, Beining Han, and Chongjie Zhang. Towards understanding linear
value decomposition in cooperative multi-agent q-learning. 2020a.
Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjie Zhang. Qplex: Duplex dueling multi-agent q-learning. arXiv preprint 2000022008.01062 2020b.
Tonghan Wang, Heng Dong, Victor Lesser, and Chongjie Zhang. Roma: Multi-agent reinforcement learning with emergent roles. In Proceedings of the 37th International Conference Machine Learning, 2020c.
Tonghan Wang, Jianhao Wang. Wu Yi, and Chongjie Zhang. Influence-based multi- explo- ration. In Proceedings of the International Conference on Learning Representations (ICLR), 2020d.
Tonghan Wang, Jianhao Wang, Chongyi Zheng, and Chongjie Zhang. Learning nearly decom- posable value functions with communication minimization. In Proceedings of the International Conference Learning Representations (ICIR), 2020e.
14

---

Published as a conference paper at ICLR 2021
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. In Proceedings of the International Conference on Learning Representations (ICIR), 2020f.
Yihan Wang, Beining Han, Tonghan Wang, Heng Dong, and Chongjie Zhang. Off-policy multi- agent decomposed policy gradients. arXiv preprint arXiv:2007. 123222, 2020g.
David Warde-Farley Tom Van de Wiele, Tejas Kulkarni, Catalin Ionescu, Steven Hansen, and Volodymyr Mnih. Unsupervised control through non-parametric discriminative rewards. In In- ternational Conference on Leurning Representations, 2018.
Ying Wen, Yaodong Yang. Rui Luo, Jun Wang, and Wei Pan. Probabilistic recursive reasoning for multi-agent reinforcement learning. In Proceedings of the International Conference on Learning Representations (ICLR), 2019.
Aaron Wilson, Alan Fern, and Prasad Tadepalli. Bayesian policy search for multi-agent role discov- ery. In Twenty-Fourtt AAAI Conference on Artificial Intelligence, 2010.
Michael Wooldridge, Nicholas R Jennings, and David Kinny. The gaia methodology for agent- oriented analysis and design. Autonomous Agents and multi-agent systems, 3(3):285-312, 2000.
Zhao Xu, Yang Lyu, Quan Pan, Jinwen Hu, Chunhui Zhao, and Shuai Liu. Multi-vehicle flocking control with deep deterministic policy gradient method. 2018 IEEE 14th International Conference Control and Automation (ICCA), Jun 2018. doi: 10.1 htt.ffccaa21..84444554 URL hrip:
/
Jiachen Yang, Igor Borovikov, and Hongyuan Zha. Hierarchical cooperative multi-agen reinforce- ment learning with skill discovery. arXiv preprint arXiv: 1912.3355,, 2019.
Yaodong Yang, Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang. Mean field multi- agent reinforcement learning, In International Conference Machine Learning, pp. 5571-5580, 2018.
Chongjie Zhang and Victor Lesser. Coordinated multi-agent reinforcement learning in networked distributed pomdps. In Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011.
Chongjie Zhang and Victor Lesser. Coordinating multi-agent reinforcement learning with limited communication. In Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems, pp. 1101-1108. International Foundation for Autonomous Agents and Multiagent Systems, 2013.
Chongjie Zhang, Victor R Lesser, and Sherief Abdallah. Seff-organization for coordinating decen- tralized reinforcement learning. In AAMAS, volume 10, pp. 739-746, 2010.
Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Basar. Fully decentralized multi- agent reinforcement learning with networked agents. International Conference on Machine Learning, pp. 5872-5881, 2018.
Yan Zhang and Michael M 7avlanos. Distributed off oof-policy actor-critic reinforcement learning with policy consensus. arXiv preprint arXiv:1903.09255 2019.
Haibin Zhu and MengChu Zhou. Role-based multi-agent systems. In Personalized Information Retrieval and Access: Concepts, Methods and Practices, pp. 254-285. Igi Global, 2008
15

---

Published as a conference paper at ICLR 2021
A ARCHITECTURE, HYPERPARAMETERS AND INFRASTRUCTURE
In this paper, we use simple network structures for the role selector and role policies. Each role policy is simple linear network without hidden layers activation functions, and the role selector is a two-layer feed-forward fully-connected network with a 64-ddimensionll hidden layer. Agents share trajectory encoding network consisting of two layers, a fully-connected layer followed by a GRU layer with a 64-dimensional hidden state. For all experiments, the length of action representations, d, is set to 20. The outputs of role policies and the outputs of role selector are each fed into their own separate QMIX-style mixing networks (Rashid et al., (020b) to estimate the global action values. The two mixing networks use the same architecture, containing 92-dimensional hidden layer with ReLU activation. Parameters of the mixing networks are generated by hypernetworks conditioning on global states. These settings are the same to QMIX (Rashid et al. 2020b). Moreover, it can be easily extended to other mixing mechanisms, such as QPLEX (Wang et al. 2020b), which may further improve the performance of RODE.
For experiments, the optimization is conducted using RMSprop with learning rate 5x of 0.99, and with no momentum or weight decay. For exploration, we use e-greedy with annealed linearly from 1.0 to 0.05 over 50K time steps and kept constant for the rest of the training. For three hard exploration annealing time 500K, for both RODE and all the baselines and ablations. Batches of 32 episodes are sampled from the replay buffer, and the role selector and role policies are trained end-to-end on fully unrolled episodes. All experiments the SMAC benchmark use the default reward and observation settings of the SMAC benchmark (Samvelyan et al. 2019). Experiments are carried out on NVIDIA GTX 2080 Ti GPU.
1opps-3s5z_ee v3_662, 6h_vs_8,, and 7rm_vs_30mmal we extend the epsilon
We use k-means clustering when determining role action spaces. The number of clusters, k, is treated as hyperparameter. Specifically, on maps with homogeneous enemies, we set 1t to 3, and on maps with heterogeneous enemies, we set & to 5. If the task only involves one enemy, h is set to 2. We can avoid this hyperparameter by using more advanced clustering approaches.
For all baseline algorithms, we use the codes provided by their authors where the hyperparameters have been fine-tuned on the SMAC benchmark.
B CASE STUDY: ROLE DYNAMICS
In this section, we provide a case study to explore the dynamics of the role selector and give an example explain why restricting action spaces of roles improve learning performance.
We carry out our study on the map corridor from the SMAC benchmark. We choose this map because it presents a hard-exploration task. An optimal strategy for this scenario requires active state space exploration for the allied Zealots to learn to move to edges or to the choke point on the map, so as not be surrounded by the enemy army. Previous state-of-the-art algorithms all learn a suboptimal strategy, where agents merely damage the enemy units for rewards, instead of first moving edges and then attacking.
In Fig, 7 we show the roles assigned by the learned role selector at different timesteps in an episode. The first row shows game snapshots, and the second row presents the correspond- ing role assignments. Here, the action encoder gives three clusters of actions (see Fig. efft) move eastward & northward, attack, and move westward & southward. These clusters of actions form the action spaces of three roles. The color of circles indicates the role of an ally unit.
We see that all agents select Role in the beginning (Fig. 7 (a)) to help them move to the edges, which is the good strategy as discussed above. The agents also learn an effective cooperative policy one of the agents (agent A) attracts most of the enemies (enemy group A) so that its teammates have advantage when facing fewer enemies (enemy group B). After killing agent A, enemy group A goes through the choke point and arrives their destination. In Fig. (b). the alive agents start to attack this group of enemies. However, the enemies are still very powerful. To win the game, ally agents learn to attract part of enemies and kill them. They achieve this by alternating between Role O (retract in this case) and Role / (attack), shown in Fig. (b-d).
16

---

Published as a conference paper at ICLR 2021
Role Move Eastward
Northward
Role Attock
Role 2: Move Westword Southward
30
(a) 4
(b) 44
(b) == 66
108
Figure 7: Visualization of roles in one episode on corridor. The first row shows game snapshots. In the second row, black circles are enemies and circles in other colors are ally agents, with different colors indicating different assigned roles. The size of circles is proportional to the remaining health points of units. The remaining and maximum health points are also shown in the lower right corner of the figures.
Rolc Frequency
0.6
Hile Nove bastmard Berdlward
0.4
Role Attact Role Nove Westward Souttwwrd
(mm))
Figure 8: Frequencies of taking each role during training on corridor. Correspond to Fig. 7 The frequencies of two roles which help exploration (Role 0 and Role 2) first increase and then decrease.
Why do restricted action spaces work? Our effect-based action clustering decomposes the full action spaces into smaller role action spaces, each of which focuses smaller subset of actions having similar effects. As each role learns on a smaller action space which has similar actions, en- ables agents to efficiently explore and results in each role being able to learn different strategies, like spread and retracting. Moreover, exploration in the much smaller role space makes the coordination of these sub-strategies easily.
Exploring in the hierarchically decomposed action spaces also provides a bias in exploration space. For example, on corridor, Role and Role 2 motivate agents explore the state space in a certain direction which help them learn several important strategies on this map: 1) Agents first move to the edges (Role 0) avoid being surrounded by the enemies (Fig. (a)), and 2) Agents alternate between attacking (Role Z) and retracting (Role 2) to attract and kill part of the enemies, gaining an advantage in numbers (Fig. (b-d).. The fact that Role 0 and Role help exploration is also
supported by Fig- g their frequencies first improve as the agents explore more, and then decrease when cooperation strategies gradually converge.
On other maps, restricted role action spaces may help agents solve the task in other ways. For example, on the map 3s5z.v8_3e62 agents learn more efficiently because the action encoder de- composes the task into two sub-tasks, one focusing attacking Zealots and another one focusing on attacking Stalkers. Learning policies for these restricted sub-problems significantly reduces the learning complexity. In summary, action effeets provide effective information to decompose joint action spaces. Clustering actions according to their effects makes role discovery much easier, and learning cooperative strategies in smaller action spaces makes learning more tractable.
17

---

Published as a conference paper at ICLR 2021
RODE
Weighted GMIX (CW--MMX)
A--
ROMA
6h
27mLMs 30m
100
100
Te 35
Tost %
50
50
50
mml
T TmmD comtder
Tmill
HMM2
100
100
Test
50
50
0.5
0.5
1.0
1.5
2.5
7.mll
Figure 9: Comparisons between RODE and baselines on all super hard maps.
Weighted GNIX IQW-OMIX) Weighted QMIX QMXX
ASN QMIX
OMIX
GPLEX
RODE (Ours)
2c_v5_44p (4gg
bare_yt bone bone
100
100
50
50
(m/0
[iml)
5m, 1s, dm
3x 1s_y__5
30
75
40
50
25
2.0
1.0
2.0
700l
Figure 10: Comparisons between RODE and baselines on all hard maps.
C EXPERIMENTAL DETAILS
In this section, we provide more experimental results supplementary to those presented in Sec. 4.2 We also discuss the details of experimental settings of rapid policy transfer and analyze the results.
C. BENCHMARKING ON STARCRAFT II MICROMANAGEMENT TASKS
we show the overall performance of RODE on the SMAC benchmark. this section, we further show the performance of our method on all maps. All experiments in this section are carried out with random seeds. Median win rate, together with 25-75% percentiles, shown.
In Sec. 4.2
The SMAC benchmark (Samvelyan et al., 2019) contains 14 maps that have been classified as easy, hard, and super hard. Fig. 9 we compare the performance of RODE with baseline algorithms on all super hard maps. We can see that RODE outperforms all the baselines by a large margin, es- pecially on those requiring the most exploration: 3s5z_vs. v3_3662, corridor, and 6h_vs_8a rz.8.. These results demonstrate that RODE can help exploration and solve complex tasks, in line with our pectations of it.
On hard maps, RODE still has superior performance compared to baselines, as shown in Fig. 10 However, on easy maps (Fig. []p. RODE tends to use more samples to achieve similar performance to baselines. We hypothesize that this is because easy maps do not require substantial exploration ally agents can win by merely engaging in fight and damaging the enemy units for reward. Under these circumstances, RODE still explores lot, which prevents it from performing better.
18

---

Published as a conference paper at ICLR 2021
RODE
Weighttd GMIX (CW-QMMX)
A-Q
ROMA
25.11 M5 15c
2532
3552
100
100
160
Te 35
75
Test We
50
%
50
1.5
0.9
1.0
1.5
0.5
1.3
mml0
Toml
[mmlt
1:355z
10m_m9 11m
100
100
Test
TostWWn
50
10
25
13
0.5
0.5
1.5
15
2.0
0.9
0.5
1.0
2.0
Figure 11: Comparisons between RODE and baselines on easy maps.
In summary, RODE establishes a new state of the art on the SMAC benchmark by outperforming all baselines on 9 out of 14 scenarios. Notably, its superiority is particularly obvious on all of the hard and super hard maps.
C.2 POLICY TRANSFER
In this section, we describe the setting of the policy transfer experiment introduced in Sec.
Policy transfer experiments are based on the assumption that new actions have similar functionalities to some old actions. We train an action encoder on the new task to cluster the actions. In this way, we can distinguish old actions Cj...... a,,. that have similar effects to a new action an,, We then use 1 Σド= Zo,y the representation for an,, where S is the representation for aj on the original task, and we add an, to role action spaces to which dig..... di, belong. For each new action, repeat these operations. The number of roles does not change during this process. This process enables the role selector and role policies learned in original task to be rapidly transferred similar task.
To test our idea, we train RODE on the map corridor, where 6 ally Zealots face 24 enemy Zer- glings, for 5 million timesteps and rapidly transfer the learned policy similar maps by increasing the number of agents and enemies. The number of actions also increases because a new attack action is added for every new enemy unit. The results are shown in Fig. 5
D ROLE INTERVAL AND RECURRENT ROLE SELECTOR
D.1 ROLE INTERVAL.
In our framework, the role selector assigns roles to each agent every e timesteps. We call the role interval. The role interval decides how frequently the action spaces change and may have a critical influence on the performance. To get better sense of this influence, we change the role interval while keeping other parts unchanged and test RODE on several environments. In Fig. [2] we show the results on 2 easy maps (10m_vs.3 1m and 1c3s5z), 1 hard map (3s_vs_52) and super hard map @0h_v__22 Generally speaking, the role interval has a significant influence on performance, but or 7 can typically generate satisfactory results. In this paper, the maps.
role interval of 5 on most of
D.2 RECURRENT ROLE SELECTOR AND FULLY-CONNECTER ROLE SELECTOR
The role selector is supposed to learn a decomposition of observation space. However, we base this component local action-observation history. In this section, discuss the influence of using GRUs in the role selector. Fig. [ we compare RODE to RODE with a fully-connected role selector conditioned local observations. As expected, recurrent role selector performs better
19

---

Published as a conference paper at ICLR 2021
Rola Interval
Role Interval
Rolo internal
Role Interval 10
QMIX best
1:365Z
vs
100
100
100
%0
75
TustWW
25
0.5
1.0
1.5
2.0
6.0
1.0
2,0
0.0
0.5
3.0 [(mb)
1.5
20
[mil)
Imil
8h 82
100
Test 8
75
2.0
[mmil)
Figure 12: Influence of the role interval (the number of timesteps between consecutive role selections).
RODE (Ours)
RODE (Fully Connected Role Selector)
QMIX best
24, vs 1ve
243z
20
1.5
2.5
1.5
Imi0
T (mil)
[ml)
1:305z
10m,rs 11m
2c.v5. 2c.v5_64gg
1.00
100
VextWi
1.0
1.5
[mm
1 (mi0
(mdi
bane_ye hane
5m, v5_
3r_ye_5e
100
100
100
55
WPh
1.0
2.0
1.0
2.0
1.5
[mm)
T (m/0
[mil
165r
vs.
27m vs.
100
100
100
60
Win
Tel:
[m/0
(mml
[mll
100
100
80
Test Ven
60
Win
0.3
0.3
1.3
1.5
2.0
mm/)
Figure 13:
Comparisons between RODE with a recurrent role selector (RODE) and a fully- connected role selector conditioned on local observations (RODE (Fully-Connected Role Selector)).
20

---

Published as a conference paper at ICLR 2021
QMX
3652
10m vs 11m
2c. 642g
75-
Win 96
75
Tist
75
50
Text
25
0.0
0.3
1.0
15
2.0
0.0
6.5
1.0
1.5
2.0
0.0
0.5
1.0
3.5
2.0
[mm0
[mil]
[mll)
MNM2
355t vs. 3502
6h.vs
100
100
100
Test Win Wt
75
Text Win-
50
50
550
25
1.0
(mmb)
100
Text
0mi0
Figure 14: RODE with different & values.
than a selector based on local observations. Even though this conclusion is not surprising, we are interested in those environments where recurrent role selector not perform better. For map 10m_v__111 11m, together with the results presented in Fig. [2] we see that RODE with a role interval of 7 has similar performance to a fully-connected role selector, but underperforms when the role interval is set to other values. This indicates that the role interval has a sophisticated interaction with exploration, optimization, and learning stability. We leave the study of this as future work. In the previous section, we give more examples showing the influence of the role interval.
E CLUSTERING ALGORITHMS
In framework, we use k-meaas cluster action representations determine the role action spaces. K-means algorithm requires predefining the number of clusters k. In this section, we first investigate the influence of k values on the performance and then discuss how to determine the number of clusters with minimum prior knowledge.
E. INFLUENCE OF VALUES
We test the influence values on 7 maps, including 2 easy maps (3s5z and 10m_vs_1im) 2 hard maps (2c_vs_66 vs_44zg and MMM2), and super hard maps 1as5zvs_3s622 Sh_va_8z. and corridor). In Fig. 14 we show the performance of RODE with k-values of 3, 5, and 7. Generally speaking, work well across these maps. practice, we set k
k-value of or homogeneous enemies and k = 5 maps with heterogeneous enemies. For outliers, we add them all other clusters to avoid action sets consisting of only one action, which we find can largely stabilize training across the benchmark.
maps with
To further understand how different values of i affect the learning performance, we take one super hard map, 6h_vs_88 vs, as an example. When k=3 or 5, the clustering method (after adding outliers to all other clusters) gives three role action spaces Move Eastward & Northward, Attack, and Move Vestward & Southward. Similar to the case of corridor as discussed in Appendix B these roles can improve exploration and thus boost the performance. However, when k=7, all move actions become outliers. The result is that most role action spaces become the original full action space. Such a decomposition over action space does not reduce the search space, and thus the performance close to that of QMIX.
21

---

Published as a conference paper at ICLR 2021
RODE
1sc
1.00
100
Text 16
80
80
50
60
60
M
Text
40
40
0.5
13
2.0
0.0
0.5
1.0
2.5
0.5
1.5
2.0
[mm0
[mll)
1:3057
10m 11m
1.00
100
90
Teat 4hn
60
60
Text
50
40
20
20
20
[mi)
T(ml)
[mlll
bare
5m
100
60
Text Vin
60
60
Text
5
40
20
20
20
[mi))
(mi)
[mi]
6h 8t
27m 30m
Text Vin
60
40
40
20
20
[mi)
T (mm0 coriire
(m/i
MMY2
Wht Ro
Tend Wit
60
20
20
mmmp
T 0m/D
Figure 15: Comparisons between RODE using X-means clustering and RODE using k-means clus- tering, where for maps with homogeneous enemies and k = 5 for maps with heterogeneous enemies. X-means does not require predefining the number of clusters.
To avoid such complicated interactions between the selection of & values and the way of dealing with outliers, we propose to use X -mmans when clustering action representations, as we discuss in detail in the next section.
E.2 OTHER CLUSTERING ALGORITTM
In this section, we investigate how to avoid predefining & values.
X-means (Pelleg et al. 2000) improves k-means by automatically determining the number of clus- ters. We use miniman noiseless description length as the splitting criterion for X-means and test RODE using X-means
all the 14 maps. The results are shown in Fig. 15 We that the results are comparable to k-means with predefined values. We thus recommend X-means when facing a new task, while for tasks that users know the number of roles, k-means can be more accurate.
Additionally, we can use density- based clustering algorithms to avoid the predefinition k, like DBSCAN (Ester al.) 1996). In practice, find that DBSCAN spaces to X-means. Since the clustering algorithm is used only to split the action spaces, RODE us- ing DBSCAN clustering is expected to have similar learning performance X-means.
generate similar role action
22

---

Published as a conference paper at ICLR 2021
RDDE
Role Policies)
QMIX
100
100
20
0.0
0.5
3.0
1.5
2.0
0.0
0.5
1.0
1.5
2,0
0m/)
(lml)
Comparisons between RODE and RODE with shared role policies and role selector. The separation of the role selector and role policies is important make the average of action representations well represent the roles.
Figure 16:
F ROLE REPRESENTATIONS
In our framework, we use the average representation of actions in the role action space to represent role. One concern that whether such representations can well represent the roles, given that both role policies and the role selector are based on action representations, We find that the separation of Q networks for the role selector and role policies (including the GRUs for processing local obser- vations and the network fa (or fp,)) }) is important to ensure such role representations have sufficient expressivity. If we share the GRUs and fa (or fp,), ). RODE struggles even on easy maps (Fig. 16
G RELATED WORKS
Role-Based Learning Our approach is an attempt to integrate roles into deep multi-agent rein- forcement learning. Many natural systems feature emergent roles, such as ants (Gordon 1996). bees (Jeanson et al., 2005), and humans (Butler 2012). these systems, roles are closely related to the division of labor and is critical to labor efficiency. These benefits inspired multi-agent sys- tem designers, who try to reduce the design complexity by decomposing the task and specializing
agents with the same role certain sub-tasks (Wooldridge et al. 2000 Omicini 2000, Padgham
& Winikoff 2002 Pavón & Gómez-Sanz) 2003] Cossentino et al. [2005] Zhu & Zhoul 2008
Spanoudakis & Moraitis 2010; DeLoach & Sarcia-Ojeda 2010; Bonjean et al. (014)) However, roles and the associated responsibilities (or subtask-specific rewards (Sun et al., 2020)) are prede- fined using prior knowledge in these systems (Lhaksmana et al. 2018). Although pre-definition can
be efficient in tasks with a clear structure, such as software engineering (Bresciani et al.) 2004). it hurts generalization and requires prior knowledge that may not be available in practice. To solve this problem. Wilson et al. (2010) use Bayesian inference to learn a set of roles and Wang et al. (2020c) design a specialization objective to encourage the emergence of roles. However, these methods search the optimal task decomposition in the full state-action space, resulting in inefficient learning in hard-exploration tasks. RODE avoids this shortcoming by first decomposing joint action spaces according to action effects, which makes role discovery much easier.
Multi-Agent Reinforcement Learning (MARL) Many challenging tasks (Vinyals et al. 2019
Berner al. 2019 Samvelyan al. 2019 Jaderberg al. (219)) can be modelled as multi-agent learning problems. Many interesting real-worle phenomena, including the emergence of tool us-
age (Baker et al., 2020p, communication (Foesster et al. 2016; Sukhbaatar et al. 2016 Lazaridou
et al.
2017 Das et al. 2019), social influence (Jaques et al. 2019), and inequity aversion (Hughes
ct al.
2018 can also be better explained from a MARL perspective.
Learning control policies for multi-agent systems remains a challenge. Centralized learning on joint action space can avoid non-stationarity during learning and may better coordinate the learning process of individual agents. However, these methods typically can not scale well to large-scale problems, as the joint action space grows exponentially with the number agents. The coordination graph (Guestrin et al.) 2002b Böhmer et al. 2020 is a promising approach to achieve scalable centralized learning. It reduces the learning complexity by exploiting coordination independencies between agents. Zhang & Lesser (201 Kok & Vlassis (006)) also utilize the sparsity and locality of coordination. These methods require the dependencies between agents to be pre-supplied. Value function decomposition methods avoid using such prior knowledge by directly learning centralized
23

---

Published as a conference paper at ICLR 2021
but factored global Q-functions. They implicitly represent the coordination dependencies among
agents by the decomposable structure (Sunehag et al. 2018 Rashid et al. 2018 Son et al.) 2019 Wang et al. 2020e b Rashid al. 2020a; Iqbal et al.
2020
Multi-agent policy gradient algorithms enjoy stable theoretical convergence properties compared to value-based methods (Gupta et al., 2017 Wang al.] 2020a) and hold the promise extend MARL to continuous control problems. COMA (Foerster et al.j20188 and MADDPG (Lowe et al.
2017 propose the paradigm of centralized critic with decentralized actors (CCDA). PR2 (Wen al. 2019 and MAAC (Iqbal & Sha 2019) extend the CCDA paradigm by introducing the mechanism of recursive reasoning and attention, respectively. DOP Wang et al., 2020g) solves the centralized- decentralized mismatch problem in the CCDA paradigm and enables deterministic multi-agent pol- icy gradient methods to use off-policy data for learning. Another line of research focuses on fully decentralized actor-critic learning (Macua et at. 2017 Zhang et al. 2018 Yang et al. 2018 Cassano
al. 2018 Suttle et al. 2019 Zhang & Zavlanos 2019).
24


Reviews:
[{"review_id": "aZIIL96-JrH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "This paper describes a role-based learning model for the DEC-POMDPs. The main contribution lies in the efficient discovery of roles from the joint action spaces and then learning a bi-level role assignment for each achievement. This is achieved in two steps. First, the joint action space is clustered into different role action spaces that reduce the action search space for each role. Second, a bi-level role assignment technique is used to learn action and roles for each agent. The technique is tested on StarCraft II micromanagement environments.\n\nFor the action space reduction, the model learns action representations that can reflect the effects of actions on the environment and other agents. To this end, a deep learning model is created which predicts the effects of joint actions on the induced rewards and change in the effects. Actions generating similar effects are cluster together using K-means and are called roles action spaces. This restricts the joint action search spaces for each role. The role selector is now used to learn a bi-level hierarchical assignment to map the action-observation history of each agent. At the top-level the agents are mapped to their corresponding to roles based on a Q-value function of each role conditioned on action-observation history and at a lower-level similar Q-value function is used to find the agent’s action. To avoid too many concurrent selections of a single role and action by multiple agents, a global Q-value is learned from individual Q-values to ensure overall coordination between the agents. This is inspired by QMIX, previous work on multi-agent learning.\n\nPositives:\n1. The idea of reducing the search space by effect-based clustering appears interesting and novel.\n2. The technique leads to good exploration and performance in hard and super maps.\n3. The paper is well-written, and the technique is extensively tested on all the maps with useful ablations\n\nMinor issues:\n1. Some comments/reasoning related to outlier roles and action spaces would have been helpful\n2. Do changes in the clustering algorithm leads to a significant difference in performance or role assignment?\n3. Compared to the previous approaches, the RODE-algorithm learns slower in most of the easier maps. \n\nUpdate - Thank you for the response and updates to the paper", "extra_scores": {}, "extra_text": {}}, {"review_id": "5g1ohWEpSDe", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "This paper introduces a bi-level hierarchical framework for achieving scalable multi-agent learning. In this framework, the high-level policy (role selector) coordinates role assignments in a smaller role space and at a lower temporal resolution. And the low-level policies (role policies) explore strategies in reduced primitive action-observation spaces. In this way, the complex multi-agent problem is decomposed into multiple sub-problems, which is easy to learn. The authors conduct the experiments in the StarCraft II micromanagement benchmark, compared with the state-of-the-art MARL methods.\n\nStrength:\n- The paper is well-written and easy-to-follow. The authors show the demo videos for a better demonstrating of the learned behavior.\n- The introduced idea is original and interesting. I can see that the bi-level multi-agent coordination framework is of great potential in solving various multi-agent tasks.\n- It is nice to demonstrate the generalization of the learned policies on unseen maps.\n- Provide the code in the Supplementary Material.\n\nQuestions:\n- The action clustering. How to choose the roles number k for clustering? According to prior knowledge? Can you explain the effect of different k numbers on the performance? \n- Is the policies for different levels trained simultaneously?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "0HUcTWolnd1", "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": "This paper proposes a new method called RODE, to learn roles for multiagent systems to improve the learning efficiency of MARL. Instead of exploring in the full joint action space, RODE first decomposes the action space into K clusters based on the different influences of each action on the environment and other agents. Then RODE trains a role selector and role policies conditioned on each agent’s action-observation history. Experiments show its superior performance compared with SOTA MARL algorithms.\n\n********\nThis paper is highly related to the subject of ICLR and is well written. But I have some specific confusions listed below, waiting for the authors' reply.\n\nThe authors mentioned that RODE differs from previous role-based methods that require prior knowledge to learn roles. However, the action space decomposition also requires human knowledge, e.g., would a wrong number of k clusters hinder the final performance?\n\nGiven the local observation and all agent’s actions, RODE first learns the action representations by minimizing two prediction errors: the next local observation, and team reward. Then the role representation is calculated by averaging representations of actions in each cluster. What I am concerned is that whether this average representation can well represent the roles, which may further impact the estimation of role policies, since the action representations are used to generate the q-values of both role selector and role policies. \n\n\nSince in SMAC, the attack action must be given an enemy index, so the number of actions increases with the increase of the number of enemies. Transfer of RODE needs to manually add new representations to each cluster and then re-calculate the role representations, In this way, the role representations change. Does this influence the decisions of role selector and role policies? Furthermore, these two components cannot be trained on new maps, because the input and output of the mixing networks are different with a different number of agents. \n\nSome recent MARL algorithms to improve QMIX, such as AI-QMIX[1], Weighted-QMIX[2] should be discussed or compared.\n\nI agree with the authors that the joint action space can be decomposed or classified based on the action effect or action semantics. ASN [2] firstly investigates the influence of actions on other agents, which they call the action semantics. I think these two works are inspired by the same property in MASs to improve multiagent coordination. Moreover, these two works both use SMAC as benchmarks. In this way, I’d like to see the comparison of ASN and RODE to further validate its superior performance.\n\n[1] AI-QMIX: Attention and Imagination for Dynamic Multi-Agent Reinforcement Learning. arXiv preprint arXiv:2006.04222.\n\n[2] Weighted QMIX: Expanding Monotonic Value Function Factorisation. NeurIPS 2020.\n\n[3] Action Semantics Network: Considering the Effects of Actions in Multiagent Systems. ICLR. 2020.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a two-level hierarchical algorithm for efficient and scalable multi-agent learning where the high-level policy decides a reduced space for low-level to explore in. All the reviewers liked the premise and the experimental evaluation. Reviewers had some clarification questions which were answered in the authors' rebuttal. After discussing the rebuttal, AC as well as reviewers believe that the paper provides insights that will be useful for the multi-agent learning community and recommend acceptance.
Decision: Accept (Poster)