Towards Skill and Population Curriculum for MARL
Authors: Rundong Wang
Longtao Zheng
Wei Qiu
Bowei He
Bo An
Zinovi Rabinovich
Yujing Hu
Yingfeng Chen
Tangjie Lv
Changjie Fan
Venue: NeurIPS 2022 Submitted (2022)
Keywords: reinforcement learning
mutlit-agent system
curriculum learning
multi-armed bandit

Abstract: Recent advances in multi-agent reinforcement learning (MARL) allow agents to coordinate their behaviors in complex environments. However, common MARL algorithms still suffer from scalability and sparse reward issues. One promising approach to resolve them is automated curriculum learning (ACL), where a student (curriculum learner) train on tasks of increasing difficulty controlled by a teacher (curriculum generator). Unfortunately, in spite of its success, ACL's applicability is restricted due to: (1) lack of a general student framework to deal with the varying number of agents across tasks and the sparse reward problem, and (2) the non-stationarity in the teacher's task due to the ever-changing student strategies. As a remedy for ACL, we introduce a novel automatic curriculum learning framework, Curriculum Oriented Skills and Tactics (COST), adapting curriculum learning to multi-agent coordination. To be specific, we endow the student with population-invariant communication and a hierarchical skill set. Thus, the student can learn cooperation and behavior skills from distinct tasks with a varying number of agents. In addition, we model the teacher as a contextual bandit conditioned by student policies. As a result, a team of agents can change its size while retaining previously acquired skills. We also analyze the inherent non-stationarity of this multi-agent automatic curriculum teaching problem, and provide a corresponding regret bound. Empirical results show that our method improves scalability, sample efficiency, and generalization in MPE and Google Research Football. The source code and the video can be found at https://sites.google.com/view/neurips2022-cost/.

Multi-agent Reinforcement Learning (MARL) has long been go-to tool in complex robotic and strategic domains [1, 2]. However, learning effective policies with sparse reward from scratch for large-scale multi-agent systems remains challenging. One of the challenges is that the joint observation-actionn space grows exponentially with varying numbers of agents. Meanwhile, the sparse reward signal requires large number of training trajectories. Hence, applying existing MARL algorithms directly to complex environments with a large number of agents is not effective. In fact, Towards Skill and Population Curriculum for MARL
Anonymous Author(s)
Affiliation Address
email
Abstract
Recent advances in multi-agent reinforcement learning (MARL) allow agents to coordinate their behaviors in complex environments. However, common MARL algorithms still suffer from scalability and sparse reward issues. One promis- ing approach to resolve them is automated curriculum learning (ACL), where a student (curriculum learner) train on tasks of increasing difficulty controlled by teacher (curriculum generator). Unfortunately, in spite of its success, ACL's applicability is restricted due to: (1) lack of general student framework to deal with the varying number of agents across tasks and the sparse reward problem, and (2) the non-stationarity in the teacher's s task due to the ever-changing student strategies. As remedy for ACL, we introduce novel automatic curriculum learning framework, Curriculum Oriented Skills and Tactics (COST), adapting curriculum learning multi-agent coordination. To be specific, endow the student with -nvvariinnnnnniiantt communication and a hierarchical skill set. Thus, the student can learn cooperation and behavior skills from distinct tasks with a varying number of agents. In addition, we model the teacher as contex- tual bandit conditioned by student policies. As result, team of agents can change its size while retaining previously acquired skills. We also analyze the inherent non-stationarity of this multi-agent automatic curriculum teaching prob- lem, and provide corresponding regret bound. Empirical results show that our method improves scalability, sample efficiency, and generalization in MPE and Google Research Football. The source code and the video can be found at https: //sites...teeeeee gow.ge..ooo...o.oooooooooo.o.oo. wwt.//reee/eeerrre/222--------
3
5
10
11
12
13
14
15
16
17
18
20
21
22
Introduction
23
25
27
29
30 they may produce agents that do collaborate with each other even when it of significant benefit [3, 4J.
31
There several lines of work related to the large-scale MARL problem with sparse reward, including: reward shaping [5]. curriculum learning [6], and learning from demonstrations [7]. Among these approaches, the curriculum learning paradigm, in which the difficulty of experienced tasks and the
33
35 population of training agents progressively grow, shows particular promise. In automatic curriculum learning (ACL), teacher (curriculum generator) learns adjust the complexity and sequencing of
37 tasks faced by student (curriculum learner). Several works have even proposed multi-agent ACL algorithms, based approximate heuristic approaches to teaching, such as DyMA-CL [8], EPC
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

Specifically, in this paper, we introduce a novel automatic curriculum learning algorithm, Curriculum Oriented Skills and Tactics (COST), which learns cooperative behaviors from scratch. The core idea of COST is to encourage the student to learn skills from tasks with different parameters and different numbers of agents. Motivation from the real world is team sports, where players often train 56 their skills by gradually increasing the difficulty of tasks and the number of coordinating players. In particular, we implement COST with three key components. First, to handle the varying number 39 19], and VACL [6]. However, DyMA-CL and EPC rely on a framework of an off off-policy student with replay buffer, and ignore the forgetting problem that arises when the agent population size grows. In turn, VACI. relies on the strong assumption that the value of the learned policy does not change when agents switch to a different task. Moreover, the teacher in these approaches is still facing an unmitigated non-stationarity problem due to the ever-changing student strategies. In addition, if we somewhat expand the ACL paradigm and presume that the teacher may have another purpose for the sequence of tasks performed by the student, another class of larger-scale MARL solutions should be mentioned. Namely, hierarchical MARL, which learns temporal abstraction with more dense rewards, including: skill discovery [10]. option response [1 I. role-based MARL [12], and two levels of abstraction [13]. Alas, hierarchical MARL mostly focuses on one specific task with a fixed number of agents and does not consider the transfer ability of learned complementary skills. Interestingly, as we show in this paper, a smart merger of ACI. and hierarchical MARL. principles can overcome their combined weaknesses and more.
40
41
42
43
44
45
46
48
50
51
52
53
54
58 of agents across tasks, motivated by the transformer [14], which can process sentences of varying lengths, we implement population-ine invarriat communication by treating each agent's 's message word. Thus, a self-attention communication channel is used to support an arbitrary number of agents sharing their messages. Second, to learn transferable skills in the sparse reward setting, we utilize the skill framework the student. Agents communicate on the high level about a set of shared low-level policies. Third, to address the non-stationarity arising from ever-changing student strategies, we model the teacher as a contextual bandit, where we utilize an RNN-based [15] imitation model to represent student policies and use this to generate the bandit's context. Empirical results show that -ot--o--theerrr our method achieves state-of- of the-artt art performance in several tasks in the multi multi-particle environment (MPE) [16] and the challenging 5vs5 competition in Google Research Football [17].
60
61
62
63
64
65
66
67
2
Further Related Work
69 (Automatic) Curriculum Learning in (MA)RL. Curriculum learning is a training strategy inspired
70 by the human learning process, mimicking how humans learn new concepts in an orderly manner,
71 usually based on the difficulty level of the problems [18]. The selection of tasks is formulated as a
72 Curriculum Markov Decision Process (CMDP) [19]. Automatic Curriculum Learning mechanisms
aim to learn a task selection function based on information about past interactions, such as ADR [20, 21J, AI AMPMMMM|| [22], SPCL [23] and GoalGAN [24]. Inspired by the mechanism of biodiversity
73
74
75 in nature, a series of MARL curriculum learning frameworks have recently been proposed with
76 remarkable empirical success. These include open-ended evolution [25-27], population based training [28, 29], and training with emergent curriculum [18, 30, 31]. In general. these frameworks
78 can be unified under the idea of an automatic curriculum that automatically generates an endless procession of better performing agents by exerting selection pressure among many self-optimizing
80 agents.
81 Hierarchical MARL and Communication. Hierarchical reinforcement learning (HRL) has been extensively studied to address the sparse reward problem and to facilitate transfer learning. Single- agent HRL focuses on learning the temporal decomposition of tasks, either by learning subgoals [32-37] or by discovering reusable skills [38-41]. Recent works about hicrarchical MARL have been discussed in the Introduction. In multi-agent settings, communication has demonstrated success 86 in multi-agent cooperation [42-48]. However, existing approaches that extend HRL to multi-agent systems or utilize communication are limited to a fixed number of agents and are hard to transfer with different number of agents.
82
83
84
88
89 Multi-armed Bandit. Multi-armed bandits (MABs) are a simple but very powerful framework that repeatedly makes decisions under uncertainty. In an MAB, a learner performs a sequence of actions.
90
91 After every action, the learner immediately observes the reward corresponding to its action. Given a
32 set of K actions and time horizon T, the objective is to maximize its total reward over T rounds.
The regret is used to measure the gap between the cumulative reward of an MAB algorithm and the

---

94 best- best-arm benchmark. A related work is the Exp3 algorithm [49], which is proposed to increase the probability of pulling good arms and achieves regret of ((vKT) log( ()) under a time-varying reward distribution. Another related work is the contextual bandit problem [50], where the learner
95
96
97
makes decisions based on prior information. In this work, the teacher is modeled as a contexual
96
bandit. We learn the dynamic context, leverage the Lipschitz assumption with respect to the context, and provide regret bound of the proposed method.
100
Google Research Football [17]. There are some challenges in the GRF (see Fig. 2). (1) Large-scale problem: In the GRF, for cooperative players, the joint action space is large; therefore, it is difficult to build a single agent to control all players. Moreover, the opponents are not fixed due a stochastic environment and a difficulty configuration, and the agents should be adapted to various opponents. (2)
101
102
103
104
Sparse rewards: The goal of the football game is to maximize the scores, which can only be obtained after a long time by iteration. Therefore, it is almost impossible to receive a positive reward when starting with random agents. Recent works attempt to tackle multi-agent scenarios in GRF by using containerized learning framework [51], learning from demonstration [7], individuality [52], and diversity [53]. However, they mainly focus on single-agent control, or train relatively easy academy tasks in GRE, or use offline expert data to train agents.
105
106
108
Problem Formulation: MARL with Curriculum
110
111
Dec-POMDP, An MARL problem is formulated as decentralised partially observable Markov decision process (Dec-POMDP) [54], which is described as tuple Sn S, A, R. O, S2, 7), where n denotes the space of actions of all agents. O = {=. .n denotes the space of observations of all agents. P: S x - S denotes the state transition probability function. All agents share the same reward as function of the states and actions of the agents R: S x A- + R. Each agent i receives a private observation o E O, according to the observation function (2 i) : S + Oz, 7 E [0, 1| denotes the discount factor.
112
113
represents the number of agents. S represents the space of global states. A A=
114
115
116
117
118
Curriculum-enhanced Dec-POMDP. A Dec-POMDP is defined by a tuple (#, M) where is the task space. Given task o, Dec-POMDP M(Ø) is presented as { n2,,, S A pd, r 0º, 52 y00 J. The superscript & denotes that the Dec-POMDP elements are determined by the task G. Note that task & can be few parameters of the environment or task IDs in finite task space. In a curriculum- enhanced Dec-POMDP, the objective is to improve the student's 's performance on the target tasks by the teacher's 's giving the sequence of training tasks.
119
121
122
123
124
Let denote trajectory whose unconditional distribution (r. under policy and a task with initial state distribution p(so) is (r) = μ (so) Er т (a; | st) p6 ($1+1 | st, ae). We use p()) to represent the distribution of target tasks and ((δ) to represent the distribution of training tasks
125
126
127
128
at each task sampling step. Considering the joint agents' policies To(als) and (Ø) parameterized
129
by f and vt respectively. The overall objective to maximize in a auriculuu-ennaane
Dec-POMDP
is:
p(
J(0, 1/) = E [R] = E Es (o))
V (d. TO) (Ø)
(1)
where (T) = Ee 7'r0 (Se, ar; 80) and V (d), mo) represent the value function of na in Dec-POMDP M()) However, when optimizing ge we cannot get the partial derivative v 1b)
131
132
Pr, (r)' since the reward function and the transition probability function w.r.t number of agents are non-parametric, non-differentiable, and discontinuous in most MARL scenarios.
V Ex Te (ত) (7) Pr,
133
134
135
136
Thus, we use the non-differentiable method, i.e., multi-armed bandit algorithms to optimize qo and optimize the overall objective by learning the distribution of training tasks (the teacher) and an RL algorithm (the student) in alternating periods. However, there are three key challenges in solving this problem: (1) There is a lack of general student framework to deal with the varying number of agents across tasks and the sparse reward problem. (2) The teacher is facing a non-stations -tatioationar problem due to the ever-changing student's strategies. (3) The forgetting and relearning problem.
138
140
'(()) is not in the partial derivative since it is fixed distribution.
3

---

Teacher
Student
Population-invariant
skill
Contexts
T
41
0j
1ow
hidden
state
RNN
my
m;
view j
Prob.
0,
a
m
171
self-att channel
171
-722
Env
Tasks
nr S A poe,
m
Φ1 42
x--
teacter
configurable environ- ments, teacher, and student. Left. The teacher is modeled contextual multi-arme bandit. At each teacher timestep, the teacher chooses a training task from the distribution of bandit actions. Mid. The student is endowed with ippulation-invariann communication and a skill framework, and trained with MARL algorithms on the training task. The student returns to the teacher not only the hidden state of RNN imitation model contexts but also the average discounted cumulative rewards on the testing task. Right. The student learns hierarchical policies. The population-invann invaarrinnn communication on the high level, and implemented with a self-attention communication channel handle the messages from varying number of agents. The agents in the student share the same low-level policy.
Figure I: The overall framework of COST. COST is composed of three parts:
142
Some tasks can be the prerequisites of other tasks and some tasks can be inter-independent and parallel. For tackling these challenges, in the following section, we propose novel multi-agent automatic curriculum learning framework, Curriculum Oriented Skills and Tactics (COST).
143
14
Curriculum Oriented Skills and Tactics
145
In this section, we present automatic curriculum learning algorithm named Curriculum Oriented Skills and Tactics (COST) as shown in Fig. 1. First, we present the student with a skill and population- invariant communication framework to tackle the varying number of agents and the sparse reward problem. Then, to deal with the non-stationarity as well as unknown prior knowledge, we propose a contextual multi-armed bandit algorithm as the teacher.
147
149
150
151
4.1
Student with Population-invariant Communication and Skills
152
In the student, we treat many agents as whole and apply the MARL algorithms to train the student. To address the varying number of agents, we propose population-invarial communication framework where agents can communicate via self-attention channel. Moreover, deal with the sparse reward problem, we introduce skill framework in which agents can learn the skills (high-level actions) that can be transferred among different tasks.
153
154
196
157
Population-invariann Communication. Instead of learning independent policies for agents in the student, we introduce communication to enable the population-ing -nvttiionnvviiantt property and learn tactics among agents. Motivated by the fact that the transformer [14] in natural language processing can handle varying lengths of sentences, we use the self-attention mechanism in our communication. As shown in Fig. Right, each agent j receives an observation 0j. In each round of communication, each agent j sends message vector m, f (o;) to a self-attention channel, where an observation encoder function.
158
159
160
162
163
164
The channel aggregates all messages and sends the new message vector my through the self-attention mechanism. Concretely, given the input of the channel M [m,,72, ,m,] Raxdm and the trainable weight of the channel We. W K, Wy E Rddxdd. we can obtain three different representations Q = MW K = MW K. V = MWv. Then, the output messages are
165
167
QKT
M Attention( K, V) softmax
V [Mmi,
[mi, m2, m.n]
Vitm
168
where dm is the dimension of the messages. Since the dimensions of the trainable weight are irrelevant 189 to the number agents, the student can take advantage of the population-invent -nivariann property to learn tactics.

---

171
Skill Framework in Student. As shown in the dotted box in Fig. 1 Right, after receiving the new messages m, from the channel, each agent takes the high-level action (skill) dn.j [o, m2, to
172
178
execute the low-level policy aj = toow ( (0g; (h.j). ). In this work, we generalize the high-level action (skill) as.j to a continuous emhedding space, so that the skill can be either latent continuous vector as in DIAYN [55], or categorical distribution for sampling discrete options [56].
174
175
178
We implement the high- and low-level policies in the student with PPO [57]. The high-level policy for each agent is learned independently, whereas the low-level policies share parameters, since the most basic action pattern should be the same within different agents. The low-level agent is rewarded by the environment. The high-level policy takes actions given a fixed interval during training. Within this interval, a cumulative low-level reward is used as high-level reward. When the categorical
177
178
179
180
181
distribution is used to enable an option-style skill, we would sample an "option" from the categorical distribution and feed the corresponding one-hot embedding to the low-level policy.
182
183
4.2
Teacher: Contextual Bandit in a Non-stationary Environment
184
The teacher expected to guide the student to learn the skills and tactics by offering and ordering different tasks. However, since the student learns across different tasks, the teacher is facing non-stationn non-stationarity problem due to the ever-changing student's 's strategies. That is, in different stages of student learning, the teacher will observe different student's 's performances when giving the same task to the student, thus leading to a time-varying reward distribution of the teacher.
186
188
189
In addition, there exists the forgetting and relearning problem of the student, where the student forgets the learned policy. To avoid this problem, the teacher should offer some trained tasks to the student.
190
It can be seen as the exploitation and exploration problem of the teacher. The teacher is encouraged to give the training tasks that benefit the student's performance on the target tasks; however, there is still need for sufficient exploration various training tasks.
192
194
Fortunately. we notice that the stationatin stems from the student, which can be mitigated with a contextual bandit which embeds the student policy into the context. As shown in Fig. Left, the teacher takes the student's policy representation as the context and chooses task from the distribution of training tasks. Specifically, we extend the Exp3 algorithm [49] with context by utilizing an online cluster algorithm BIRCH [58] Alg. The context x is the student's policy representation, the teacher's action is certain task é, and the teacher's 's reward is the return of the student in the target
195
196
197
198
199
200
tasks. In steps 1-4, the teacher samples a task for the student's 's training, and in steps 6-7, the teacher would update the parameters based on the evaluation reward of the student.
Algorithm Teacher Sampling and Training
Input:
Context x, the number of Clusters Ne. No instances of Exp3 with task distribution
w(Ok, c) for & = 1,..., ......K K and for c = I.....,Ne No. learning rate a, a buffer maintaining the his-
torical contexts
Output: M(Ø) n 8o, A Pd, r 0+ 52 7o the teacher bandit parameters
Sampling
Get the the context x, and save it to the buffer
2. Run the online cluster algorithm and get the index of the cluster center e(x)
Let the active Exp3 instance be the instance with index c(x)
4. Set the probability p(e c(x)) Σ c(()),c(x))
(I=))u(0),c(aa)) + K
for each task Φx
5. Sample a new task according to the distribution of Pox.c Training
6. Get the return (discounted cumulative rewards) from student testing r
7. Update the active Exp3 instance by setting w(pr, c(x) = w Φk, c(r))
202
4.2.1
Context Representation
We learn the representation of the student policy as context. A straightforward representation is to directly use the student parameters as the context. However, the number of parameters is large and
204
ever-changing if we change the student's architecture. Thus, we turn an alternative method.
5

---

206 A principle to learn a good representation of policy is predictive representation, that is, the representation should be accurate to predict policy actions given states. According the principle, we utilize an imitation function through supervised learning. Supervised learning does not require direct access to reward signals, making it an attractive task for reward- -agnossic representation learning. Intuitively, the imitation function attempts to mimic low-level policy based on historical behaviors.
207
209
211 In practice, we use an RNN-based imitation function fim x A + [0, 1]. Since recurrent neural networks are theoretically Turing complete [59], its internal states can be used as the representation of the student's policy. Regarding the training this imitation function, we use the negative cross entropy objective Ellog fim a)).
213
215
4.2.2
Regret Analysis
216
In this subsection, we show the regret bound of the proposed teacher algorithm E[R(T)]
217 O (IK log 1/33), where T the number of total rounds, is the Lipschitz constant, and K is the number of arms (the number of the teacher's actions). Since the teacher's 's reward is the return of the student in the target tasks, the regret bound shows the optimality of the proposed method.
219
First, we introduce the Lipschitz assumption about the generalization ability of the task space.
Assumption 4.1 (Lipschitz continuity w.r.t the context). Without loss of generality, the contexts are mapped into the [o, 1] interval, so that the expected rewards for the teacher are Lipschitz with respect
222
223
to the context.
Ir( .)) (ø xz)) S L |r --'l
for any arm Φ T and any pair of contexts x, E X where L is the Lipschitz constant, and X' is the context space.
224
225
This assumption suggests that, for any policy that is trained on set of tasks, the rate of performance change is not faster than the rate of policy change. It is realistic assumption since we cannot expect the student to achieve a dramatic improvement on a given task when the student is represented by new context via few training steps.
227
229
Then, we borrow a contextual bandit algorithm for a small number of contexts [49] (see Appendix Alg. 2) and the lemma 4.2, as a stepping stone for the proof of Theorem 4.3.
230
Lemma 4.2. Alg. 2 has regret ((((T)) O(VTK log K).
232
Lemma 4.2 introduces a square root dependence on | if running a separate copy of Exp3 for each
233
context [49]. It motivates us handle large context space by discretization.
Theorem 4.3. Consider the Lipschitz contextual bandit problem with contexts in [0, 1). The Alg. !
yields regret E[R(T)] O (T2/3 TT)
236
Proof. See Appendix B for the proof.
237
In practice the contextual space is high-dimensional instead of in [0, 1], and in the proof uniform mesh is used discretize the context space. Since cannot have such uniform mesh, without loss of generality, we use the BIRCH streaming data cluster algorithm [58] to generate and discretize the context space. At the end of the training, the cluster can be seen as an approximation of the uniform mesh.
238
239
240
241
5 Experiments
243
We consider several tasks in two environments, Simple-Spread and Push-Ball in the Multi-agent Particle-world Environment (MPE) [16], and the challenging 5vs5 task of GRF [17], to further demonstrate the performance of our approach.
245
246
We aim to answer the following three research questions. Q1: Is curriculum learning needed in the complex large-scale MARL problem? (See Sec. 5.2) Q2: Can our COST outperform previous curriculum-bused MARL methods? If so, which components in COST contributes the most to performance gains? (See Sec. 5.3) Q3: Can COST learn good curriculum for the student? (See
247
249
Sec. 5.4)

---

Simple Spruad
Ball
gents
Landmark
Ball
(b)
Figure 2: The environments. (a): Multi-particle Environment. (b): Google Reaserach Football
251 5.1
Environments, Baselines and Metric
Environments. In the GRF 5vs5
253
scenario, we need to control 4 agents (except the goalkeeper) to compete with the opponent built- in AI Each agent would observe a compact encoding, which con- sists of 15-dimensional vector summarizing many aspects of the
Table 1: Baseline algorithms.
255
Categories
Methods
QMIX [60]
257
MARL (Q1)
IPPO [61]
259
IPPO with uniform task sampling
260
game, such player coordinates, ball possession and direction, ac- tive player, and game mode. The action set available to an individ- ual agent consists of 19 discrete actions such as idle, movement, passing, shooting, dribbling, or sliding. The GRF provides two types of reward: scoring and checkpoints, encourage the agent move the ball forward and have successful shot.
Curriculum- (Q2)
VACL [6]
261
COST with uniform task sampling
262
Ablation Study (Q3)
COST without HRL
263
264
285
266
268
and Push-Ball (see Fig. 2a). In Simple-Spreate there are n agents that need to cover all n landmarks. Agents are penalized for collisions and only receive positive reward when all the landmarks are covered. In Push-Ball, there n agents, balls, and landmarks. The agents need to push the balls to cover every landmark. A success reward is given after all the landmarks have been covered.
In MPE, investigate
269
270
272
273
Baselines. We evaluate the following approaches as baseline in Table 1:
274
We compare MARL algorithms to justify curriculum learning in the complex large-scale MARL problem. Also, we modify VACL by removing the centralized critic for fair comparison of the MPE.
275
276
Due to the difficulty of the GRF, we include shooting reward to encourage the student to shoot.
the reward to optimize various algorithms, the mean episode reward in such environments cannot show the performance of the agents. Therefore, for GRF scenarios, we plot the win rate and the average goal difference, which the number of goals scored by the MARL agents minus the number of goals scored by the other team.
Metric.
Even if
278
279
280
The experiments are carried out on 30 nodes, one of which has 128-core CPU and 4 A100 GPUs. Each experiment trial is repeated over 5 seeds and runs for 1-2 days.
282
5.2
The Necessity of Curriculum Learning
284
First, we describe experiments using MPE. In contrast to the fully observable setting and the centralized critic in VACL, we consider individual PPO in partially observable environments with
285
286
default rewards. We randomly pick a starting state, and the episode ends after fixed number of
287
maximum steps. To be specific, the task space consists of n agents, where ri (2, 4, 8, 16). We set
the maximum allowed steps to 25. All evaluations are performed on the target task, where = 16.
289
IPPO trained and evaluated directly on the target task. In Fig. 3, we can see that IPPO performs nearly VACL. COST achieves higher coverage rate than the baseline methods, but the improvement
7

---

Simple Spread
0.40
PPQ VACL COST
Owey woee beb
0.35
0.25
0.20
6-
0.35
IPFO VACL CoST
VACL COST
VACL
COST
0.0
0.3
2.5
2.5
Trannig
0.
2.0
15
Figure 3: The evaluation performance of vari- ous methods on MPE.
Figure 4: The changes in the number of agents on MPE.
COST
COST
COST uniform
COST W. unifomm
COST w/o, HAL
COST wib. 4R.
IPPO W. unitom
IFPO uniform
0.6
IPPO tescher
OPie wio tsacher
IPO wio, teacher
Wi 800
0.4
Tha moniing Timestops
Trairing Timestopa
(a) Win Rate
(b) Goal Difference
Figure 5: The evaluation performance of various methods 5ys5 football competition.
291
not significant. Furthermore, we experimentally investigate the probability variation of different population sizes in Fig. 4. We observe that the curriculum afforded by COST is approaching the target task. The results illustrate that in a simple environment where the student can directly learn to complete the task, there is need to apply curriculum learning.
293
295
Then we show the performance comparison with the baselines in GRF We also run CDS [53] and CMARL [51], however, we did not include their performances. since the goal difference reported CMARL [51] is relatively low compared to our method. In Fig. 6, we can see that without the curriculum learning scheme, QMix and IPPO cannot perform well in the 5ys5 scenario. However,
296
297
299
IPPO slightly better than QMix in the scope MARL algorithms in this scenario. In Fig. 5b, we omit the lines of QMix since the mean score is low, affecting the presentation of the figure. The reason could be that QMix is off-policy MARL algorithm, which would rely heavily on the replay buffer. However, in such sparse reward scenarios, the replay buffer has much less efficient samples for Qix to learn. For example, the replay buffer would contain tons of zero-score samples, leading to a non- promprrmmiingg performance. Meanwhile, IPPO with a shared actor and critic, on-policy algorithm, would utilize the samples more efficiently. Therefore, curriculum learning is promising solution to the complex large-scale MARL problem.
301
302
303
305
307
During our experiments, we found that IPPO or shared parameter PPO can easily achieve good performance in most academic scenarios in GRF However, 5vs5 is an obstacle for agents to handle more complex scenarios. Due the limitation of computational resources, we tested COST in the
308
309
1 1lvsl1 scenario. The result can be seen in the Appendix C.
311
5.3
Performance and Ablation Study
In the experiments MPE, In both environments, COST performs better than VACL. Instead of training with continuous relaxation of the categorical distribution of population size in VACL, our bandit teacher achieves higher success rate at test time, since the population size is discrete variable in nature. Also, in Fig. 4, we observe that the curriculum provided by COST is effective in exploring the task space agents become increasingly competent.
313
315
316
317 In the experiments on GRF, we not include VACI. in our baselines in the GRF, since the imple- mentation in the source code of VACL is heavily based on prior knowledge of specific scenarios,
8

---

1.0
5_v5_5
3_v5_3
academy
Baapmmm_ppss__eee passsaadd____. shoot with with_weeeeeeeeeeee keeper
0.5
acadomy_3__s.
Dimension 2
Task Prkp
0.6
academy_emeaee gww.gooollaaao
0.2
-35
0.0
0.5
0.0
0.8
Training Timesteps
Dimension
(a) The task distribution of COST during training.
(b) The visualization of contexts
Figure 6: Visualization of Learned Curriculum.
319
such as the threshold to divide the learning process. We can see that COST has higher win rate and goal difference than IPPO with uniform task sampling in the 5vs5 football competition. The experiments on MPE and GRF show that when the teacher is rewarded by the student's performance, the bandit-based teacher can exploit the student learning stage and give the suitable training tasks to the student.
320
321
322
323
324
For ablation study, we replace our contextual multi-armed bandit teacher with uniform task sampling and remove the hierarchical part in the student framework. As shown in Figs. 5a, 5b, we can clearly see that COST can achieve a higher win rate and a greater score difference than COST with uniform and COST w/o. HRL. Also, COST with uniform task sampling outperforms IPPO with uniform task sampling. The difference between these two methods is only the introduction of HRL. It shows the contribution of HRL in the 5vs5 football competition. When removing HRL and contextual multi-armed bandit, the performance degradation w.r.t. COST are similar. It shows that HRL and the contextual multi-armed bandit seem to contribute equally. This can again justify the need for curriculum learning scheme. However, we can see that COST w. uniform has a larger variance in
326
328
329
330
331
332
333
performance than COST w/o. HRL. It means that uniform sampling might introduce more undesired
334
tasks for student training.
5.4
Visualization of Learned Curriculum
336
We visualize the distribution of task sampling of COST during training based on a selected trial as shown in Fig. 6a. An interesting observation that the task probability seems nearly uniform. We interpret this into an anti-forgetting mechanism. We can see that at the beginning of training, the task probability seems to be near-uniform, since the teacher should explore the task space and try keep track of the student's 's learning status. During training, the probabilities vary over time steps. For exam- ple, at about 80-100 million timesteps, we can see sudden drop in academy Beaddde_empty_aeee empty-goal. close and academy_2 3__ vs 1_with__ __wwwwkeeeeeeeee keeper, since the student almost handles the skills learned in such scenarios. However, when training continued, we can still observe that agents are trained on these
338
340
341
342
343
344
tasks more frequently.
We also visualize the distribution of contexts in Fig. 6b using t-SNE [62]. The contexts collected and stored a buffer. We divide the contexts into four classes according to the index. We can clearly shift in student policy representation from the beginning of training the end.
346
Conclusion
348
3/9
In this paper, to address the scalability and sparse reward issue in the current multi-agent system, we introduce a novel ACL algorithm, Curriculum Oriented Skills and Tactics (COST), to learn complex behaviors from scratch. Specifically, to handle the varying number of agents, we incorporate population- innllation-invariant multi-agen communication framework and exploit a hierarchical scheme for
350
351
352
353
each agent to learn skills to deal with sparse rewards. Moreover, to mitigate the otosstation,rity, we model the teacher as contextual bandit, where the context is represented by the student's policy representation. Empirical results show that our method achieves wate-of-the-an performance on environment and the challenging 5vs5 competition in GRF,
355
several tasks in the

---

References
357
358
[1] RoboCup. Robocup Federation Official Website. https://www.robccup.co orgg/// 2019. Ac- cessed April 10, 2019.
360
[2] OpenAL. OpenAI Five. 4, 2019.
Accessed March
362
[3] Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, pages 321-384, 2021.
363
364
385
[4] Yaodong Yang and Jun Wang. An overview of multi-agent reinforcement learning from game theoretical perspective. arXiv preprint arXiv:2011.00583 2020.
386
367
[5] Yujing Hu, Weixun Wang, Hangtian Jia, Yixiang Wang, Yingfeng Chen, Jianye Hao, Feng Wu, and Changjie Fan. Learning to utilize shaping rewards: A new approach of reward shaping. arXiv preprint arXiv:2011 1.l.2669,100269, 2020.
368
389
[6] Jiay Chen, Yuanxin Zhang. Yuanfan Xu, Huimin Ma, Huazhong Yang, Jiaming Song, Yu Wang, and Yi Wu. Variational automatic curriculum learning for sparse-reward cooperative multi-agent problems. Advances in Neural Information Processing Systems, 34, 2021.
371
372
373
[7] Shiyu Huang, Wenze Chen, Longfei Zhang, Ziyang Li, Fengming Zhu, Deheng Ye, Ting Chen, and Jun Zhu. Tikick: Toward playing multi-agent football full games from single-agent demonstrations. arXiv preprint 1rX1v:2110.04507, 2021.
375
376
[8] Weixun Wang, Tianpei Yang, Yong Liu, Jianye Hao, Xiaotian Hao, Yujing Hu, Yingfeng Chen, Changjie Fan, and Yang Gao. From few to more: Large-scale dynamic multiagent curriculum learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 7293-7300, 2020.
377
378
379
380
[9]
Qian Long, Zihan Zhou, Abhibav Gupta, Fei Fang, Yi Wu, and Xiaolong Wang. Evolution- ary population curriculum for scaling multi-agent reinforcement learning. arXiv preprint arXiv:2003. 10423, 2020.
381
382
[10] Jiachen Yang, Igor Borovikov, and Hongyuan Zha. Hierarchical cooperative multi- reinforcement learning with skill discovery. arXiv preprint arXiv:1912.03558, 2019.
384
[11] Alexander Sasha Vezhnevets, Yuhuai Wu, Remi Leblond, and Joel Z Leibo. Options responses: Grounding behavioural hierarchies in multi-agent rl. arXiv preprint arXiv: 1906 2019.
386
[12] Tonghan Wang, Tarun Gupta, Anuj Mahajan, Bei Peng, Shimon Whiteson, and Chongjie Zhang. Rode: Learning roles to decompose multi-agent tasks. arXiv preprint arXiv:2010.01523, 2020.
388
389
[13] Zie Pang, Ruo-Ze Liu, Zhou- Yu Meng, Yi Zhang. Yang Yu, and Tong Lu. On reinforeement learning for full-length game of starcraft. In Proceedings of the AAAI Conference on Artificial Intelligence, 2019.
380
382
[14] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems, 30, 2017.
393
394
385
[15] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9()): 1735-1780, 1997.
396
397
[16] Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperativee-oompetiivv environments. Advances in Neural Information Processing Systems, 2017.
399
[17] Karol Kurach, Anton Raichuk, Piotr Stanczyk, Michal Zajac, Olivier Bachem, Lasse Espeholt, Carlos Riquelme, Damien Vincent, Marein Michalski, Olivier Bousquet, et al. Google research football: A novel reinforcement learning environment. arXiv preprint arXiv:1907. 11180, 2019.
401
10

---

403
[18] Rémy Portelas, Cédric Colas, Lilian Weng. Katja Hofmann, and Pierre- Yves Oudeyer. Au- tomatic curriculum learning for deep RL: A short survey. arXiv preprint arXiv:2003.04664 2020.
404
[19] Sanmit Narvekar and Peter Stone. Learning curriculum policies for reinforcement learning. arXiv preprini arXiv: 18/2.00285 2018.
407
[00] lige Akkaya, Marcin Andrychowicz. Maciek Chociej, Mateusz Litwin, Bob McGrew, Arthur Petron, Alex Paino, Matthias Plappert, Glenn Powell, Raphael Ribas, et al. Solving rubik's ' cube with robot hand. arXiv preprint arXhv:1910.0711:. 2019.
409
411
[21] Bhairav Mehta, Manfred Diaz, Florian Golemo, Christopher Pal, and Liam Paull. Active domain randomization. In Conference on Robot Learning, pages 1162-1176. PMLR, 2020.
413
[22]
Rémy Portelas, Cédric Colas, Katja Hofmann, and Pierre- Oudeyer. Teacher algorithms for curriculum learning of deep RL in continuously parameterized environments. In Conference on Robot Learning, pages 835-855 853, 2020.
414
415
[23] Lu Jiang, Deyu Meng, Qian Zhao, Shiguang Shan, and Alexander G Hauptmann. Self-paced 416
417
curriculum learning. In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015.
418
[24]
Carlos Florensa, David Held, Xinyang Geng, and Pieter Abbeel. Automatic goal generation for reinforcement learning agents. In International Conference Machine Learning, pages 1528. PMLR, 2018.
420
[25] Wolfgang Banzhaf, Bert Baumgaertner, Guillaume Beslon, René Doursat, James A Foster, Barry McMullin, Vinicius Veloso De Melo, Thomas Miconi, Lee Spector, Susan Stepney, et al. Defining and simulating open-ended novelty: Requirements, guidelines, and challenges. Theory in Biosciences, 131(1)131-161, 2016.
422
424
425
[26] Joel Lehman, Kenneth O Stanley, et al. Exploiting open-endedness to solve problems through the search for novelty. In ALIFE, pages 329-336. Citeseer, 2008
426
427
[27] Russell K Standish. Open-ended artificial evolution. International Journal of Computational Intelligence and Applications, 3002):167-175. 2003.
429
[28] Max Jaderberg. Wojeiech M Czarnecki, Iain Dunning, Luke Marris, Guy Lever, Antonio Garcia Castaneda, Charles Beattie, Neil C Rabinowitz, Ari S Morcos, Avraham Ruderman, et al. Human-level performance in 3d multiplayer games with population-based reinforcement learn- ing. Science, 364((443):859--888) 865, 2019.
431
433
[29] Siqi Liu, Guy Lever, Josh Merel, Saran Tunyasuvunakool, Nicolas Heess, and Thore Graepel. Emergent coordination through competition. arXiv preprint arXiv: 190.00090,,,7511,, 2019.
434
[30] Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent tool use from multi-agent autocurricula. arXiv preprint 1rX1v:190.007528. 2019.
436
437
438
[31] Joel Z Leibo, Edward Hughes, Mare Lanctot, and Thore Graepel. Autocurricula and the emergence of innovation from social interaction: A manifesto for multi-agent intelligence research. arXiv preprint arXiv:1903.0077: 2019.
440
[32] Ofir Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learning. Advances in neural information processing systems, 31, 2018
442
443
[33] Olir Nachum, Shixiang Gu, Honglak Lee, and Sergey Levine. Near-optimal representation
444
learning for hierarchical reinforcement learning, arXiv preprint arXiv:1810.01257, 2018.
445
(34] Dibya Ghosh, Abhishek Gupta, and Sergey Levine. Learning actionable representations with goal-conditioned policies. arXiv preprint / 18110/// 2018.
447
[35] Sainbayar Sukhhaatar, Emily Denton, Arthur Szlam, and Rob Fergus. Learning goal embeddings via self-play for hicrarchical reinforcement learning. arXiv preprint arXiv:1811.0900 2018.
11

---

449
[36]
Suraj Nair and Chelsea Finn. Hierarchical foresight: Self-supervised learning of hong-horizon tasks via visual subgoal generation. arXiv preprint arXiv:1909.0582, 2019.
450
451
[37] Rundong Wang. Runsheng Yu, Bo An, and Zinovi Rabinovich. 12hrl: Interactive influence- based hierarchical reinforcement learning. In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence, pages 3131-3138,
452
453
2021.
455
[38]
Christian Daniel, Gerhard Neumann, and Jan Peters. Hierarchical relative entropy policy search. In Artificial Intelligence and Statistics, pages 273-281, 2012.
456
457
[39] Karol Gregor, Danilo Jimenez Rezende, and Daan Wierstra. Variational intrinsic control. arXiv 2016.
458
preprint a6
459
[40] 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.
460
461
[41] Archit Sharma, Shixiang Gu, Sergey Levine, Vikash Kumar, and Karol Hausman. Dynamics- aware unsupervised discovery of skills. In International Conference on Learning Representa- tions, 2020.
462
463
464
[42] Jakob Foerster, loannis Alexandros Assael, Nando De Freitas, and Shimon Whiteson. Learning to communicate with deep multi-agent reinforcement learning. Advances in neural information processing systems, 29, 2016.
465
486
467
[43] 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, pages 5538-1546. PMLR, 2019.
468
469
470
[44] Sainbayar Sukhbaatar, Rob Fergus, et al. Learning multiagent communication with backpropa- gation. Advances in neural information processing systems, 29, 2016
472
[45] Amanpreet Singh, Tushar Jain, and Sainbayar Sukhbaatar. Learning when to communicate at scale in multiagent cooperative and competitive tasks. arXiv preprint arXiv: wrXiv:18/2.00755, 2018.
473
474
[46] Jiechuan Jiang and Zongqing Lu. Learning attentional communication for multi-agent coopera- tion. Advances in neural information processing systems, 31, 2018.
475
[47] Daewoo Kim, Sangwoo Moon, David Hostallero, Wan Ju Kang, Taeyoung Lee, Kyunghwan Son, and Yung Yi. Learning to schedule communication multi-agent reinforcement learning. arXiv preprin! arXiv: 0905.0 2019.
477
[48] Rundong Wang, Xu He, Runsheng Yu, Wei Qiu, Bo An, and Zinovi Rabinovich. Learning efficient multi-agent communication: An information bottleneck approach. In International Conference Machine Leurning, pages 9908-9918. PMLR, 2020.
480
482
[49] Peter Auer, Nicolo Desa-Bianchi, Yoav Freund, and Robert E Schapire The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48-77, 2002.
483
484
[50] Flad Hazan and Nimrod Megiddo. Online learning with prior knowledge. In International Conference on Computational Learning Theory, pages 499-513. Springer, 2007.
[51] Siyang Wu, Tonghan Wang, Chenghao Li, and Chongjie Zhang. Containerized distributed value-based multi-agent reinforcement learning. arXiv preprint 1 2021.
487
488
[52] Jiechuan Jiang and Zongqing Lu. The emergence of individuality. In International Conference on Machine Learning, pages 4992-5001. PMLR, 2021.
490
553 Chenghao Li, Chengjie Wu, Tonghan Wang, Jun Yang, Qianchuan Zhao, and Chongjie Zhang. Celebrating diversity in shared multi-agent reinforcement learning. arXiv preprint arXiv:2106.02195 2021.
491
[54] Daniel S Bernstein, Robert Givan, Neil Immerman, and Shlomo Zilberstein. The complexity of decentralized control of Markov Decision Processes. Mathematics of Operations Research, 27 (4):819-844 840, 2002.
494
12

---

496
[55] Benjamin Eysenbach. Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without a reward function, arXiv preprint arXiv:1802.06070, 2018.
497
488
[56]
Pierre-Luc Bacon, Jean Harb, and Doina Precup. The option-critic architecture. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
489
500
[57] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal 2017.
policy optimization algorithms. arXiv preprint
502
[58] Tian Zhang, Raghu Ramakrishnan, and Miron Livny. Birch: An efficient data clustering method for very large databases. ACM Aigmod Record, 25(2):103-114, 1996.
503
504
[59]
Heikki Hyötyniemi. Turing machines are recurrent neural networks. In STeP '96/Publications of the Finmish Artificial Intelligence Society, 1996.
505
[60]
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In International Conference on Machine Learning, pages 4304, 2018.
507
509
[61] Christian Schroeder de Witt, Tarun Gupta, Denys Makoviichuk, Viktor Makoviychuk, Philip HS Torr, Mingfei Sun, and Shimon Whiteson. Is independent learning all you need in the StarCraft multi-agent challenge? arXiv preprint arXiv:2011.09533 2020.
511
513
[62] Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 911), 2008.
514
Checklist
515
516
1. For all authors...
517
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
518
(b) Did you describe the limitations of your work? [Yes] Limitations and Future Work. As mentioned in the Sec. 5.2, when the tasks are not complex, current multi-agent reinforcement learning algorithms, even independent versions, can easily handle tasks. In our work, our aim is to provide a general framework for handling complex MARL tasks. There remains large space for some methods, such as feature extraction and reward shaping, which can provide significant improvement. In the future, we plan to include curriculum based on self-play or population-based training, since current experiments in GRF are only involved in competition with built-in AI. (c) Did you discuss any potential negative societal impacts of your work? [Yes] Our method is proposed for agents to do the large-scale complex multi-agent reinforcement learning problem. Currently, the method is limited to simulation and video games. The potential negative societal impacts of our work will be limited to the development of reinforcement learning applications. That is, if reinforcement learning can be used for negative social impacts, our work could also be used.
520
522
524
525
526
$28
530
532
533
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
534
535
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See 4.1
537
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix B
538
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] As a URL in Abstract
540
541
542
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Experiment Section and Appendix
13

---

544
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
545
546
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes] See line 281
548
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
549
(a) If your work uses existing assets, did you cite the creators? [Yes]
550
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material URL? [No]
(d) Did you discuss whether and how consent obtained from people whose data you' 're using/curating? [N/A]
553
554
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
555
358
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
558
559
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
560
561
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14

---

583
A
Algorithm
Algorithm 2 A contextual bandit algorithm for small number of contexts
Initialization: For each context z, create an instance Exp3, of algorithm Exp3 for each round do
1. Invoke algorithm Exp3_. with I
Play the action chosen by Exp3,.
3. Return reward rt to Exp3,.
Proof of Theorem 4.3
584
685
Theorem 4.3. Consider the Lipschitz contextual bandit problem with contexts in [0, 1]. The Alg. yields regret [[[[T]] = (T2/3 (LK 1)/3)
586
587
Proof. Let Sm be the e-unfform mesh on [0, 1], that is, the set of all points in [0, 1] that are integer multiples of We take 1/(d 1) where the integer d the number of points in Sm, which will be adjusted later in the analysis.
588
589
We apply Alg. 2 to the context space Sm- Let fs.. (a)) be mapping from context the closest point in Sm
571
fs.. (z) min
aargmin |ac z'| x'ESm
572 In each round t. we replace the context Ię with fsm (zt) and call Exp3 The regret bound
573 will have two components: the regret bound for Exp3ş and (a suitable notion of) the discretiza-
574 tion error. Formally, let us define the "discretized best response" TS X + Φ: T (x) =
575 T (fs,, (x)) for each context E X.
578 We define the total reward of an algorithm Alg is Reward(Alg) = Σ Then the regret of Exp3 577 and the discretization error are defined as:
(T) Reward (TT) Reward (Exp3g)
DE(S) = Reward (Tt Reward (T'))
578 follows that regret is the sum R(T) (T( + DE(S). We have E =
from Lemma 4.2, it remains to upper bound the discretization error and adjust the discretization
580
step
For each round f and the respective context = 2t, r (T²(2z fs(z)) 2 (T*( fs(x)) >
582
r (w (a) z) cL. The first inequality is determined by the optimality of म and the second determined by Lipschitzness. Summing this up over all rounds t, we obtain E [Reward (πT) 2
583
584
Reward [x*] eLL'.
585
Thus, the regret that
(V log' = (12//0 log T)
E[R(T))
SELT ELT
(4)
For the last inequality, we choose e = ( (KloxT] 1113
586
C 11vs11 Full Game on GRF
587
588
further conduct experiments on the 1lvlll scenario of GRF, As shown Fig. 7, COST achieves about 50% win rate after training with 200 million timesteps.
15

---

CCOT
0.6
0.3
Rutei bval
0-4
0.1
0.0
0.1
25.4
50.0
75.01
300
150
200
Traiinn Timestops
Figure 7: The performance of COST on the 11v11 scenario.
D
Implementation Details
590
Here we describe the COST framework. We use the open-sourced Ray RLlib implementation of Proximal Policy Opumization (PPO), which scales out using multiple workers for experience collection. This allows us use large amount of rollouts from parallel workers during training to
392
593
594
ameliorate high variance and aid exploration. We do multiple rollouts in parallel with distributed
585
workers and parameter sharing for each agent. The trainer broadcasts new weights the workers after their synchronous sampling. We now turn our attention to environment-speccinn settings.
596
597
D.1
Google Research Football
596
set five tasks for training the 5vs5 scenario. They are academy_ emptyy-oamtyggll goallygooollllseeeeeooooeo _cosee academy _paly_pas_______ ____s__nd____ee____ aad_sshot__we
herd__hoot_wtt__ete_eeee wwwwwwhhteeeeeeeeee 3_vs_3 academy_3 _s_ __________________________ In scenarios, we do not control our team's goalkeeper.
5_vs_5.
600
601
one agent need to move forward and shoot with an empty keeper and v_v__3, two agents are controlled to play against a goalkeeper and players respectively, In academy 3__ $_vs____ __wtwwkeeppeeeeeeee__ three agents are controlled play against center-back and a goalkeeper. In 5_ _s_5,, agents are controlled to play against 5 players. Without loss of generality, we initialize all player with fixed positions and roles as center midfielders.
In the academy..mmpty-ggal_coooo
602
goal. In academy-pass aataass__nd_shott__a_eee shoot_with keeeee
803
604
605
606
607
We use both MLP and self-attention mechanism for the high-level policy, and use MLP for the low-level policy. For high-level policy, the input first projected to an embedding using 2 hidden layers with 256 units each and ReLU activation, which is then fed into multi-head self-attention (8 heads, 64 units each). The output then projected to the actions and values using another fully
609
610
connected layer with 256 units. For low-level policy, we use MLP with 2 hidden layers with 256
612
units each, i.c. the default configuration of policy network in RLlib.
Table 2: COST hyper-parameters used in GRF,
Name
Value
Discount rate
0.99
GAE parameter
1.0
KL coefficient
0.2
Rollout fragment length
1000
Training batch size
100000
SGD minibatch size # of SGD iterations Learning rate
10000
60
le-4
Entropy coefficient
0.0
Clip parameter
0.3
Value function clip parameter
10.0
16

---

D.2 MPE
614
In this environment, agents must cooperate through physical actions reach set of landmarks. Agents observe the relative positions of other agents and landmarks, and are collectively rewarded based on the proximity of any agent to each landmark. In other words, the agents have 'cover' all of the landmarks. Further, the agents occupy significant physical space and are penalized when colliding with each other. The agents need to infer the landmark to cover and move there while avoiding other agents.
615
616
618
COST in MPE are shown in Table 3. In MPE, syper-parameters such as rollout fragment length, training batch size and SGD minibatch size are adjusted according to horizon 621
620
The hyper-parametert
622
of the scenarios so that policy updated after episodes are done. We use the same network as
623 in GRF, but with 128 units for all MLP hidden layers. Other omitted hyper-parameter follow the
default configuration in RLlib PPO implementation.
Table 3: COST hyper-paramettrs used MPE.
Name
Value
Discount rate
0.99
GAE parameter
1.0
KL coefficient
0.5
# of SGD iterations
10
Learning rate
le-4
Entropy coefficient
0.0
Clip parameter
0.3
Value function clip parameter
10.0
17


Reviews:
[{"review_id": "r8MaNf04EY", "reviewer": "Reviewer_1MvZ", "summary": "The paper proposes a multiagent curriculum method where a \"Teacher\" proposes tasks to a \"Student\" to learn to solve. The teacher follows a bandit algorithm to propose tasks taking into account the non-stationarity comes from the student learning algorithm, and the student uses a sophisticated attention-based learning architecture.", "questions": "- How is the \"distribution of tasks\" defined? How is the original (final) task modified to build this distribution?\n- How are the policies transferred/adapted across tasks? How similar should the tasks be for the method to work?", "limitations": "- The paper has an interesting choice of works added to its references. Arxiv papers [5,6,7] are added to cite the general concepts \"reward shaping\", \"curriculum learning\", and \"learning from demonstrations\", where there are plenty of very comprehensive peer-reviewed surveys in all of those areas. In special, the main surveys of the area of the paper (Curriculum Learning for RL) are not even mentioned (the first is probably the most comprehensive survey while the second is probably the first one to explicitly survey on Curriculum Learning for RL)\n\nNarvekar, Sanmit, et al. \"Curriculum Learning for Reinforcement Learning Domains: A Framework and Survey.\" Journal of Machine Learning Research 21.181 (2020): 1-50.\n\nDa Silva, Felipe Leno, and Anna Helena Reali Costa. \"A survey on transfer learning for multiagent reinforcement learning systems.\" Journal of Artificial Intelligence Research 64 (2019): 645-703.\n\nPerhaps due to an insufficient coverage of the literature, the authors have not added any heuristic-based curriculum learning method in ter experimental evaluation (e.g., one of the many surveyed on those two papers), and also failed to explicitly address many important aspects of a curriculum learning algorithm.\n\n- One of the most important aspects is how the set of subtasks is defined from the final task. If it is assumed that the \"distribution of tasks\" is manually defined somehow, there is a very big number of heuristic-based curriculum methods that could be applicable for the empirical evaluation and some of them should be included. If this is somehow autonomously defined, there is a smaller group of applicable methods, and the one that comes to my mind at this moment is the Object-oriented curriculum:\n\nSilva, Felipe Leno Da, and Anna Helena Reali Costa. \"Object-oriented curriculum generation for reinforcement learning.\" Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems. 2018.\n\nAnother aspect that is not made clear is exactly how to interrupt the training in one task and proceed to the other. This seems to have been defined in a very ad hoc manner for this paper, but the procedure to do this should have been explicitly added in the algorithm.\n\nMoreover, there are some assumptions followed in the work given that this is a multiagent procedure. It is assumed that all agents require constant and perfect communication between agents, which is not true for most practical multi agent scenarios. This should have been made very clear in the paper.\n\nFinally, it is not very clear to me how the knowledge is transferred across the tasks.\n\n- There should be a little more of evidence that the curriculum method is better than not using curriculum. You could add a baseline where exactly the same learning algorithm is used but without switching the task (training directly on the target task).", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Albeit the paper explores a very relevant research topic, the experimental evaluation is very limited for a mainly-empirical approach. Moreover, there are a number of aspects and assumptions in the algorithm that are not made clear. Finally, there is a huge group of curriculum for RL papers that are not even mentioned (and hence it's no surprise that those methods are not included in the experimental evaluation). Therefore, I am not entirely convinced the method performs better than other state-of-the-art works (or even classical ones). More details on the reasons in the \"Limitations\" field.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "mGA-1768_iY", "reviewer": "Reviewer_Vwt6", "summary": "This paper proposes a contextual bandit policy based curriculum learning method and applies it to MARL problems. To handle the changing input size induced by the changing numbers of agents, they utilize a self-attention mechanism in the communication channel. To mitigate the non-stationarity, they propose the imitation function to represent the policies and use a cluster algorithm to discretize and reduce the contextal space. The paper is well written and the experiments are introduced clearly.", "questions": "1. Section 5.2: it says “The results illustrate that in a simple environment where the student can directly learn to complete the task, there is no need to apply curriculum learning.”, however, the coverage rate in Figure 3 is pretty low (around 0.35 on SimpleSpread, and 0.30 on Push ball). It seems the ACL methods do not help very much to boost the performance, which is also consistent with the generated curriculum in Figure 4 where the curriculum from COST is only around the target task. \n2. Figure 6a shows the task distribution generated by COST, which is close-uniform. Why does it produce a very different performance from the uniform curriculum in Figure 5(a)?\n3. How much does the HRL policy used in COST help to improve the performance?", "limitations": "1. The motivation and advantage of the hierarchical policy and clustering methods are not analyzed clearly. How can they help?\n2. The performance on MPE tasks does not show the effectiveness of the proposed method; and the performance on GRF cannot be connected well to the generated task distribution. ", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The researched problem regarding curriculum learning on MARL is interesting and can be beneficial for the community.\n2. The proposed using a contextual bandit policy on curriculum learning is promising.\n3. The experiments are also well designed.\n\nWeaknesses:\n1. The self-attention based population-invariant architecture is similar to the architecture proposed by EPC, which might not be claimed as one of the main contributions.\n2. The motivation and benefits of (hierarchical reinforcement learning) HRL in this work are not well explained.\n3. The performance of the method seems not significant, especially on MPE tasks. And on both MPE and GRF tasks, the generated task distribution is hard to explain and connected to their corresponding performance. ", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JavAE5erwhm", "reviewer": "Reviewer_9xYX", "summary": "The authors identify several challenges of cooperative multi-agent reinforcement learning (MARL): sparse rewards, non-stationarity, and the more general requirement compared to existing works, of supporting a varying number of agents or agents with varying existing capabilities in the task space of interest. To tackle these challenges, the authors propose COST, a learning algorithm combining several components: a bandit-based task selection technique, a hierarchical skill-based MARL policy, and a self-attention-based message-passing system.", "questions": "- What exactly is the task parameterization that is used for varying the environment in each episode and as input to BIRCH for clustering? This is a core detail that does not seem to be clearly detailed anywhere.\n- Similarly, why was VACL chosen as a baseline? Further, why was VACL only used as a baseline for the MPE environment and not Google Research Football?\n- Can the authors elaborate on both why BIRCH was chosen for clustering and how this clustering method works? These details would provide missing justification for this essential design choice in the curriculum-learning component of their method.\n- Why does the starting number of agents for VACL and COST differ so drastically in Figure 4?\n- Are the differences between the learning curves in Figure 5 statistically significant?\n- Do the baseline methods also make use of a message-passing self-attention architecture? If not, isn’t this a confounder for the experimental results?", "limitations": "COST assumes the ability to use a cheap talk channel both at training and at evaluation, which may often be infeasible in practice. Furthermore, it is not clearly discussed in the paper how scalable this method is to larger numbers of agents or what population size is ideal for applying this method. The authors should clarify these points in a future version of the paper.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The paper provides a detailed discussion of the challenges of learning complex task spaces in cooperative MARL, and the authors propose several ideas for addressing these issues.\n- The self-attention message-passing architecture is an interesting method for supporting an a flexible number of participating agents. This approach, however, is quite similar to that taken by deep coordination graphs [1], and so a discussion and comparison with respect to this line of work seems necessary.\n\nWeaknesses:\n\n- While there are good ideas in this paper, the current presentation of the method and results is disorganized and unfocused. The result is that while the authors identify several important challenges for improving cooperative MARL, they fail to provide much insight into whether any of their proposed solutions are at all effective. This paper is trying to do too much at once, and as a result, focuses on too many problems simultaneously with independent methods for each, while not clearly demonstrating the benefits of their method for solving any one of them.\n- The experiments show ablations only on the Google Research Football environment, and only for the curriculum and hierarchical skill-based components of the method. Meanwhile, the results compare to baselines that seem to use a completely different policy architecture, as the baselines do not seem to use the self-attention message-passing components. As a result, it seems that the self-attention architecture acts as a confounder for the results, making it hard to draw any conclusions from the presented results.\n- In procedurally-generated environments, it is important to test for generalization to held-out test configurations of the environment. Some methods that use a return-maximizing curriculum, as performed by COST's multi-arm bandit, may result in overfitting to the training tasks. This aspect of their problem setting is completely ignored, and fully missing from the paper.\n- Some design decisions seem entirely arbitrary without clear motivation, for example, the choice of BIRCH for task clustering and the decision to train the higher-level skill policies independently, while the low-level policies with parameter sharing across all agents.\n- The curriculum visualization results seem to suggest no real curriculum is being learned. This also seems supported by the large overlapping error bars between COST and the COST without curriculum ablation in the Google Research Football learning curves.\n- The authors miss crucial related work from the unsupervised environment design subfield of reinforcement learning [1,2,3,4] as wells prior work on Teacher-Student Curriculum Learning [5].\n- The authors should consider moving the multi-armed bandit section in Section 2, their related works section to Section 3, which serves as their background section.\n- Overall, the paper presents a large number of ultimately disparate ideas for improving cooperative MARL, without providing sufficient experiments teasing apart the effect of each newly proposed component. Each of the proposed solution components also already exists in a similar form in prior works (see cited references below), while, judging from the experimental results, no clear emergent benefits seem to result from their combination. This suggests that the novelty of this paper is limited.\n\nReferences:\n\n[1] Böhmer et al, 2020. Deep Coordination Graphs.\n\n[2] Dennis et al, 2020. Emergent Complexity and Zero-shot Transfer via Unsupervised Environment Design.\n\n[3] Jiang et al, 2021. Prioritized Level Replay.\n\n[4] Jiang et al, 2021. Replay-Guided Adversarial Environment Design.\n\n[5] Parker-Holder et al, 2022. Evolving Curricula with Regret-Based Environment Design.\n\n[6] Matiisen et al, 2019. Teacher-Student Curriculum Learning", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Hm0m-rRCHNZ", "reviewer": "Reviewer_mgEj", "summary": "This paper proposes a curriculum learning framework for MARL to solve large-scale and more difficult multi-agent tasks. To deal with the problem of varying agent numbers, sparse reward, and the non-stationarity from changing student policies, the authors combine several techniques including the Transformer-based communication structure, hierarchical network design, and contextual bandit for better multi-task learning performance. The proposed method shows good performance on several tasks from MPE and GRF and the visualization results prove that the teacher model can learn a good curriculum for students. ", "questions": "1. What does the forgetting problem mentioned in Line 40 mean since I thought curriculum learning does not require solving old tasks as continual learning\n2.  I didn't quite understand the experimental settings in GRF since only the 5_vs_5 scenario is trained, what is the teacher agent selecting from?\n3. Is the modification of baselines and environments like adding the shooting reward necessary? Since the VACL is the only curriculum-based method but it's modified and the original 5_vs_5 scenario can already be solved by some works.\n\n\n", "limitations": "Limitations should be discussed more adequately in the paper. Societal impact is likely minimal.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This paper attempts to solve the curriculum learning problem in MARL in a multi-task learning way, which is very interesting and intuitive. While most other works only focus on generating the curriculum or learning from a manually selected task sequence, the proposed method applies a teacher-student structure to solve these two problems concurrently.\n2. Although there are some previous works utilizing the techniques like the self-attention module or the hierarchical structure of agents in MARL, it is natural to implement them under the curriculum learning setting in this paper and yield good results.\n3. The experiment results on selected tasks outperform other baselines on two benchmarks. The ablation study and visualization results are also helpful for understanding the impact of each part.\n\nWeaknesses:\n1. The problem of varying numbers of agents in MARL has been widely discussed in MARL and several methods have been proposed and achieved good performance. This paper did not review these works or set them as baselines to compare.\n2. The tasks selected in MPE and GRF are mostly 16 agents and 4 agents, which is either not very difficult or really large-scale, making the significance of this work not very good.\n3. The baselines didn't include recent works and are clearly not enough for evaluation. The final performance is not impressive and only three scenarios are presented.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject