Hierarchical Multi-Agent Skill Discovery
Authors: Mingyu Yang
Yaodong Yang
Zhenbo Lu
Wengang Zhou
Houqiang Li
Venue: NeurIPS 2023 poster (2023)
Keywords: Multi-Agent Reinforcement Learning
Hierarchical Skill Discovery
Probabilistic Graphical Model
TL;DR: A hierarchical algorithm for discovering both team skills and individual skills in multi-agent reinforcement learning.

Abstract: Skill discovery has shown significant progress in unsupervised reinforcement learning. This approach enables the discovery of a wide range of skills without any extrinsic reward, which can be effectively combined to tackle complex tasks. However, such unsupervised skill learning has not been well applied to multi-agent reinforcement learning (MARL) due to two primary challenges. One is how to learn skills not only for the individual agents but also for the entire team, and the other is how to coordinate the skills of different agents to accomplish multi-agent tasks. To address these challenges, we present Hierarchical Multi-Agent Skill Discovery (HMASD), a two-level hierarchical algorithm for discovering both team and individual skills in MARL. The high-level policy employs a transformer structure to realize sequential skill assignment, while the low-level policy learns to discover valuable team and individual skills. We evaluate HMASD on sparse reward multi-agent benchmarks, and the results show that HMASD achieves significant performance improvements compared to strong MARL baselines.

Hierarchical Multi-Agent Skill Discovery
Mingyu Yang', Yaodong Yang" Zhenbo Lu Wengang Zhou Houqiang Li
"University of Science and Technology of China, IIstitute for AI, Peking University Institute of Artificial Intelligence. Hefei Comprehensive National Science Center ymyemail ustc. edu, en, yaodong yang@pku. edu. cn luzhenbo@ial. ustc. edu. en, {zhwg Lustc, edu. cn
Abstract
Skill discovery has shown significant progress in unsupervised reinforcement learning. This approach enables the discovery of a wide range of skills without any extrinsic reward, which can be effectively combined to tackle complex tasks. However, such unsupervised skill learning has not been well applied to multi-agent reinforcement learning (MARL) due to two primary challenges. One is how learn skills not only for the individual agents but also for the entire team, and the other is how to coordinate the skills different agents to accomplish multi- agent tasks. To address these challenges, we present Hierarchical Multi-Agent Skill Discovery (HMASD), a two-level hierarchical algorithm for discovering both team and individual skills in MARL. The high-level policy employs transformer structure to realize sequential skill assignment, while the low-level policy learns to discover valuable team and individual skills. We evaluate HMASD sparse reward multi-agent benchmarks, and the results show that HMASD achieves significant performance improvements compared to strong MARL baselines.
Introduction
Multi-agent reinforcement learning (MARL) has recently demonstrated remarkable potential in solving various real-world problems, such as unmanned aerial vehicles (1. autonomous driving 2 and traffic light control 3. Despite its broad applications, current MARL algorithms 4 S typically
require well-crafted team or individual rewards guide the agents to learn policies for efficient coordination. This limitation hinders the generalization of MARL to the sparse reward multi-agent tasks, where agents receive non-zero reward only when they coordinate to achieve a challenging goal. Compared to single-agent tasks, the sparse reward problem in multi-agent tasks poses more challenges. On the one hand, the joint state and action spaces of multi-agent tasks increase exponentially with the number of agents, which exacerbates the difficulty for agents to explore those valuable but rare states. On the other hand, we need to distribute the received sparse reward not only to different timesteps but also to different agents (6).
To solve sparse reward multi-agent problems, promising approach is to discover underlying skills within the multi-agent task and effectively combine these skills to achieve the final goal. For example, football game, there are various skills involved such as dribbling, passing, receiving and shooting. A common training strategy for football team is to let each player learn these fundamental skills first and then train players together to cooperatively use these skills for scoring the goal, which is more efficient than directly training players without any skills together. Similarly, in sparse reward multi-agent task, it's difficult for agents to cooperatively achieve a challenging goal from scratch. We can first try to discover the underlying useful skills within the task, which is much easier than solving the entire task under the sparse reward setting 7 8) Although these discovered skills may
CCoresponding authors: Yaodong Yang and Zhenbo Lu
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

not independently achieve the goal or induce non zero rewards, we can leam to effectively combine them to accomplish the final task. In short, it is possible to decompose sparse reward multi-agent task into a combination of different skills, which greatly simplifies the task complexity.
Previous works mainly follow learn shared team skill 10), which promotes team cooperation behaviors but suffers from high complexity. The other does the opposite and learns skills only from the perspective of individual agents MT [2]. which is more efficient since individual skills are usually casier to learn than team skills. However, merely learning individual skills may be insufficient achieve team objectives. Taking football as an example again, in- dividual skills can refer to the technical abilities of individual players, such as drib- bling and passing, while team skills refer to the ability of players to work together whole, i.e., the overall team tactics, such as wing-play and tiki-taka [13] As shown in Fig. [ the goal of a football team is to let all players coordinate to master useful team skills from global perspective. Di- rectly learning the team skill is usually too complex. A better way is to decompose the team skill into different individual skills for players from an individual perspective, and ensure that the joint behavior of all players can form the team tactic. Both team skills and individual skills are important agent skill discovery is how to simultaneously learn the individual skill for each individual agent and the team skill for the whole team, and the second challenge is how to combine these skills to accomplish multi- agent tasks.
paradigms discover skills in MARL. One is let all agents
from a global perspective
Team skill
Individual skill
Wing- play
Dribbling
Tiki-taka
Passing
:
Counter-
Shooting
attack
from an individual perspective joint behavior
Figure I: Illustration of team skill and individual skill in football.
successful team. Therefore, a primary challenge for multi-
To this end, present
paradigm for discovering both team and individual skills in MARL. Inspired by probabilistic inference in RL [1], we embed the multi-agent skill discovery problem into a probabilistic graphical model (PGM). With the PGM, an inference problem, allowing us to take advantage of various approximate inference tools. Then, we derive variational lower bound our optimization objective by following the structured variational inference [14), and propose Hierarchical Multi-Agent Skill Discovery (HMASD), a practical two-level hierarchical MARL algorithm for optimizing the derived lower bound. Specifically, the high-level 115 structure to assign skills to agents, with inputs consisting of the sequence of global state and all agents' observations, and outputs consisting of the sequence of team skill and agents' individual skills. In this way, an agent's 's individual skill depends on the team skill and all previous agents' individual skills, allowing agents choose complementary skills and achieve better skill combination. The low-level policy chooses primitive actions for each agent to interact with the environment conditioned on the assigned skills. Moreover, we introduce two skill discriminators to generate intrinsic rewards for agents to learn diverse and distinguishable skills. Finally, we show that HMASD achieves superior performance on sparse reward multi-agent benchmarks compared to strong MARL baselines. To our best knowledge, our work is the first attempt to model both team skills and individual skills with the probabilistic graphical model in MARL.
formulate multi-agent skill discovery as
policy employs a transformer
2 Preliminaries
In this section, we first introduce the problem formulation and notations for cooperative MARL. Then, we describe the concept of skill and mutual information based objective for skill discovery in unsupervised RL. We finally present the framework representing RL as a probabilistic graphical model. More related works are discussed in Sec. 5
2.1 Problem Formulation
In this work, we consider a fully cooperative MARL problem, which usually described as decentralized partially observable markov decision process (Dec-POMDP) [16]. A Dec-POMDD is

---

O
St
O
St
at
St+1
at
St+1
o
Agent g
(a)
(b)
Figure 2: (a) RL can be cast as an inference problem by considering basic probabilistic graphical model consisting of states 8t, actions a, and optimality variables O₂. (b) Similarly, we formulate multi-agent skill discovery as an inference problem by augmenting the basic probabilistic graphical model with team skills Z, individual skills z² and observations oj.
defined by tuple G =
is the set of n agents and S is the global state space of the environment. All agents share the same action space A and the joint action space is A At timestep t, each agent g E N chooses an action of E A, where 21, ... n} is the agent identity. The actions of all agents form joint action a, E AA" By executing d,, the environment transitions to the next global state 8t+1 ~ P(s |St, az), and all agents receive a shared team reward rss,, a.). Each agent g' can only observe a partial observation of Ω according to the observation probability function O's,g')) The joint observation of all agents is denoted as o,, 7 E [0, 1) is the discount factor. The objective is to learn a joint policy π that maximizes the expected global return E 1- 7'rr| T|. In particular, this paper focuses on the sparse reward setting, where the team reward r, zero for most timesteps.
Ω, 0,7), where N ""..
2.2 Mutual Information based Skill Discovery
Skill discovery is popular paradigm in unsupervised RL, which enables agents discover diverse skills without a reward function. A skill is represented by a latent variable z, which is used as an additional input to the policy and results in latent-conditioned policy T< 8, =). The intention behind skill discovery is to expect the skill to control which states the agent visits and different skills to visit different states. This can be achieved by simple objective of maximizing the mutual information between state and skill 2, i.e., I(s; z) = H(z)) H(=[s). It's challenging to directly optimize the mutual information. Therefore, a majority of skill discovery methods lower bound for the mutual information as follows:
20 derive a variational
I(s; 2) Bs,z=p(s.s) [log p(2)s) log p(z)] 2 Bx,z-p((.2) [log (=(s)) - loz), (1)
where go (=(s)) is a learned model parameterized by à to approximate the intractable posterior p(=[s). Then, we can treat log (2]s) logp(=) 2) as the intrinsic reward to optimize the latent-conditioned policy π (als, 2), where different = correspond to different skills.
2.3 Probabilistic Graphical Model for RL
The probabilistic graphical model (PGM) is a powerful tool for modeling complex and uncertain systems. It provides a graphical representation of the relationship between variables in system, where nodes correspond to random variables and edges represent conditional dependencies. In recent years, PGM has been widely used in RL to model complex recision-makinn tasks [14] 21 24).
In this work, we follow the basic PGM for RL [14), which embeds the control problem into graphical model and formulates it as an inference problem. As shown in Fig. 2(a). it first models the relationship among states, actions, and next states based on the dynamics P(s az). To incorporate the reward function, it introduces binary random variable O called optimality variable into the model, where O denotes timestep t is optimal, and O, 0 indicates timestep t is not optimal. The probability distribution over O, p(O, 1|8r, a.)) = exp (r(*,, az)). Refer to [14, we then perform structured variational inference to derive the final objective, which is to optimize a variational lower bound (also called evidence lower bound). The evidence is that O2 = for all t (0.... .T.. We will use O, to denote O = 1 for conciseness in the remainder of this paper.

---

The variational lower bound is given by:
T Σ r(s - log (((((()))
log o(oor)) 2 E Eoor 0o. (ou aorT)
where q(ar(st) is the learned policy. Optimizing this lower bound corresponds maximizing the cumulative reward and the policy entropy at the visited states, which differs from the standard RL objective that only maximizes reward. The entropy term can promote exploration and prevent the policy from becoming too deterministic. This type of RL objective is sometimes known as maximum
entropy RL 25 26
3
Method
In this section, present our solution for learning both team and individual skills in MARL. We first model the multi-agent skill discovery problem with a PGM and derive a tractable variational lower bound the optimization objective. We then propose practical MARL algorithm to optimize the derived lower bound.
3.1 Multi-Agent Skill Discovery Inference Problem
In this work, we study the skill discovery problem in multi-agent tasks. One way for multi-agent skill discovery treat all agents as one big virtual agent and directly learn skills from the perspective of the whole team, which can improve teamwork but suffer from high complexity. Another way is to learn skills from the perspective of each individual agent, which reduces the complexity but lacks collaboration. To combine the advantages of two ways, we propose to learn skills not only from the individual perspective but also from the team viewpoint.
Specifically, we utilize latent variable denoted by Z E to represent the skill of the entire team, latent variable denoted by 2 X' to represent the skill of agent g', referred to as individual skill. The individual skills of all agents are represented by 1:m E X". In this work, both the team skill space Z and the individual skill space X' are defined as discrete spaces consisting of finite latent variables with one-hot encoding, where the number of team skills and individual skills are denoted as rz and 71., respectively. The team skill view and is expected to control the global states that the whole team visits, while the individual skill 2' is developed through an individual perspective and is intended to control the partial observations accessed by agent g¹. Besides, since individual behaviors are typically based on the overall team strategy, the individual skill 2² should depend on the team skill Z. According to these intuitions, we employ a PGM illustrated in Fig. bb) to model the multi-agent skill discovery problem, where the team skill Z is conditioned on the global state 8 and the individual skill 2 is conditioned on both the team skill Z and agent g partial observation of. With the PGM, we formulate multi-agent skill discovery as an inference problem. Then, we perform structured variational inference to derive our objective, which to optimize variational lower bound as follows:
referred to team skill. And
acquired from the global
T
logg((o.r)) 2 Eyng(T)
Σ
((st, as)
+ Σ log p(z prrpp(("o, Z)
diversity torn
(3)
log 9(2(s)))
Σ log a(> ((2211/,, 2)
Σ
-= log g(aijoi, z²
}
skill entropy term
action opy torm
where T = (So:T, O0:T, ag,T, Z, 2, is the joint trajectory containing states, observations, actions and skills. The detailed derivation of Eq. is shown in Appendix B
Optimizing this lower bound is to maximize the team reward r(st, ar) and three terms. The diversity term shows the probability of skills on their corresponding states and observations, which can be maximized to encourage different skills to visit different states and observations, and is a crucial element for learning diverse skills. The skill entropy term and the action entropy term reflect the entropy of skills and actions at the visited states and observations, respectively. Optimizing the two entropy terms can enhance the exploration during skill learning.

---

mlaallo22)
(i,
Pacony
x
Actor
Critic
sample
a
MLP
1, fim 7,
6
MLP
Skill Discoverer
5, 0,0,
Z, Zm
State Encoder
Skill Decoder
Env
4o (2]s)
4u(2 (z(22lo222
8,0
Embedding
Embodding
Team
Individual Discriminator
Discriminator
a"
2
5
Skill Coordinator
Skill Discriminator
0,
Figure 3: The overall framework of HMASD. At the high level, the skill coordinator adopts a transformer structure assign team skill Z and individual skills 2 to agents. At the low level, the skill discoverer chooses primitive action for agent g' conditioned on the assigned skill 2² and forms joint action to interact with the environment. The environment returns global state 8, joint observation o and team reward r. To make the skills diverse and distinguishable, two skill discriminators employed to generate intrinsic rewards rin for the skill discoverer.
3.2 Hierarchical Multi-Agent Skill Discovery
In this subsection, we present Hierarchical Multi-Agent Skill Discovery (HMASD), practical two-level hierarchical MARL algorithm designed to optimize the derived lower bound in Eq. To estimate the probability distributions in the lower bound, we utilize four approximate functions. Specifically, we first employ a team skill discriminator qD(Z) (Z()s) to approximate p s()]s)). Then, individual skill discriminator qa(=" !oi, Z) approximate p( of Z). Moreover, skill
coordinator Ta [Z, x I:m |s,, 0:) is utilized to approximate both (Z st) and ((="oot. 2), while a skill discoverer (a lot, =²) is applied to approximate q(a)) of 2²). As shown in Fig. 3 these approximate
functions are integrated into a two-level hierarchical structure for multi-agent skill discovery. At
the high level, the skill coordinator assigns team skill Z and individual skills ش/: agents every timesteps, where k E N+ is the number of timesteps between two consecutive skill assignments and called skill interval. At the low level, the skill discoverer employs a latent-conditioned policy for each agent to explore the assigned skills using intrinsic rewards generated by the skill discriminators. Below, we describe how to learn these approximate functions for optimizing the derived lower bound.
Skill Coordinator Transformer 15] has recently shown great potentials in MARL 21 In this work, take inspiration from MAT (II, which applies transformer structure map the agents' observation sequence into the agents' action sequence. Similar to MAT, we employ a transformer structure for the skill coordinator in our method shown in Fig. 3 Specifically, take the sequence of state and observations (s, o², ...... ,0*) as inputs and embed them into vectors with the same dimension. Then, the embedded sequence is passed through a state encoder, which contains several encoding blocks. Each encoding block consists of self-attention mechanism, a multi-layer perceptron (MLP) and residual connections. The state encoder outputs a sequence denoted as (3, o², 6², ō²"), which encodes (s, o², 0², o²) into informative representations and is used approximate the high-level value function V₁. After encoding the state and observations, we assign skills in an nuto-regressive way. We start with an arbitrary symbol Zd, which is embedded and then fed into skill decoder containing several decoding blocks. Each decoding block consists of two masked self-attention mechanisms, an MLP and residual connections, where the query of the second masked self-attention mechanism is the output of state encoder. The output of skill decoder is then fed to an MIP to generate the high-level policy nn & 6tm 2o). We sample team skill Z from the policy and insert back into the decoder to generate 21. By analogy, after n + decoding rounds, get team skill Z and all agents' individual skills z Im In this way, agent g" individual skill 2
5

---

depends on team skill Z and all previous agents' individual skills 2 2!:i-1, which can prevent skill duplication and allow agents to choose complementary individual skills based on the team skill.
Skill Discoverer After assigning skills sequentially, we learn a shared skill discoverer to explore the assigned skills for agents. The skill discoverer consists of decentralized actor and a centralized critic as shown in Fig. 3 The decentralized actor takes the partial observation of and individual skill z' as inputs, and outputs the low-level policy xy [o"]o', 2*) that chooses action a² for each agent g'. All agents share a centralized critic to approximate the low-level value function (i Z) based on the global state & and team skill Z. In our implementation, both the actor and the critic consist of an MIP, a GRU 32) and another MIP. The actor aims to learn the assigned individual skill =² for each agent g¹, while the critic takes a global view and expects to guide the joint behavior of all agents to discover the assigned team skill Z.
Skill Discriminator To make the learned skills diverse and distinguishable, we learn two skill discriminators, a team discriminator and an individual discriminator: The team discriminator inputs the global state and outputs the probability of each team skill Z E Z, denoted as qn (Z])). In addition, employ an individual discriminator qa(="lo', Z). which takes the partial observation of and team skill Z as inputs and then outputs the probability of cach individual skill 2t E X. Both discriminators are composed of an MLP. The team discriminator aims to discriminate the team skill based on the global state, while the individual discriminator is designed to discriminate the individual skill given the observation and team skill. The two skill discriminators intrinsic rewards log qD ( () and log (a(2" lo', Z), respectively. log (D(Z) [Z s) is to reward all agents to jointly explore global states that easy to discriminate, while log qa(2" lo Z) rewards each agent I" for visiting those easily distinguishable observations given the team skill Z. In other words, it encourages different skills explore different areas of the state-observation space. Since if two skills explore the same state, this state will be hard to discriminate and then lead to low intrinsic rewards. Therefore, the intrinsic rewards can guide agents to learn diverse and distinguishable skills.
utilized to generate
Overall Training and Execution According to Eq. B] we need to optimize the team reward, the diversity term, the skill entropy term and the action entropy term. At each episode, the high-level skill coordinator assigns skills to agents every & timesteps, then the low-level skill discoverer learns explore the assigned skills for agents during these timesteps. We define the sum of team rewards over these k timesteps as the single-step reward for the high-level policy, i.e., the high-level reward can be written as rf = -/- Te+p. For the low-level policy, use a combination of extrinsic team reward and intrinsic rewards, i.e., the low-level reward for agent g¹ is:
Te + Ap log gD (Z|s++) + Xa log ga (= Z),
where Ae, An and A are three positive coefficients. The team reward ensures the learned skills are useful for the team performance. while the intrinsic rewards are used to optimize the diversity term in We adopt the popular PPO (33 objective to optimize both the high-level skill coordinator and the low-level skill discoverer. Given policy π (alx) with parameters O, value function V (v) with parameters & and a reward function r, we write a generic template for PPO objective as:
Eq. 3
(oro(T(alz), V()), r = L(0) + AcL(o),
((0) -Ee min =(ae(x))) Ac, clip T(a((2))) 1 e, +C A.)]. (22 (V(wr)-
(5)
(()) E. max {
(Vona(ve) + (V (V()) Voia(ve), -c,t) -R.) -.)) "}]
where A, is the advantage computed using GAE [34, R, A. + Vota(y)) and de is the coefficient of value loss. Then, we write the overall objective for the high-level skill coordinator as:
La (on, (n) = Cor (Z)3, z²), V3()
Lmo Lmolma (m 0 22. -. V,('')).
An (E [H((T plm 2d
E (= 0 20,2,z (1))))))))))
(6)
where H(( (-)) is the entropy of the high-level policy that aims to optimize the skill entropy term in Eq. 3 and X the high-level entropy coefficient. On and on denote the parameters of the policy and

---

(a) Alice and Dob
3,2²
(c) 1,
Figure 4: (a) The Alice_and_ Bob game. The objective is to collect both diamonds, where each diamond is allowed to be collected only when an agent is standing on the button with the same color. (b) At timestep two individual skills for reaching the blue button (z1 3) and blue diamond (22 2). (c) After
0, HMASD selects the team skill of collecting the blue diamond (Z 0) and
collecting the blue diamond, the team skill transitions to collecting the red diamond (Z = 1) with two individual skills of reaching the red button (a 1) and red diamond (z² 0) timestep k. where & is the skill interval.
value function in the skill coordinator, respectively. Similarly, the overall objective for the low-level skill discoverer is:
(i,, Φi)
Σ Cooofm Vi(s, Z),rl) A Σ H(m(a')o',='))
where H( (-) denotes low-level policy entropy and optimizes the action entropy term in Eq. 3 and X is the low-level entropy coefficient. 0 and Φi represent the parameters of the low-level policy and value function, respectively. The skill discriminator is trained in a supervised manner with the categorical cross-entropy loss:
La(ØD, 0a) 2,D Dlog un (Z]=)] Σ Bio
[log q===="'',, .2):
(8)
where D= ((s Z, o, 2, } is dataset storing the state-skill pairs during training. ΦD and @u are the parameters team discriminator and individual discriminator, respectively. The pseudo code of our method is shown in Appendix A
During the execution phase, only the centralized high-level policy Tn mz( = 0) and the de- centralized low-level policy (a(a"o" 2²). For every l timesteps, the high-level policy nn (Z, 2 2/m |s, o) first chooses team skill Z (i.e., team strategy) from global perspective and then sequentially assigns complementary individual skills 1:m to agents based on the team strategy Z. With the assigned individual skill 2 each agent g² selects an action a' according the low-level policy : ( (a' 2²) every timestep for execution. Therefore, our method performs one timestep of centralized execution and k timesteps of decentralized execution in every timesteps. Such periodic and spaced centralized execution can coordinate agents more efficiently from a global view compared to the fully decentralized execution, and a small amount of centralized execution is acceptable in many multi-agent tasks. For example, during basketball game, the coach can call a timcout and gather all players adjust the team strategy and each player's individual strategy. short, our method achieves balance between fully centralized execution 31 35 and fully decentralized execution [ 36 39
4 Experiments
In this section, we evaluate the effectiveness of our method. We first conduct case study to show how HMASD effectively learns diverse useful skills and combines them to complete the task. Then, we compare HMASD with strong MARL baselines on two challenging sparse reward multi-agent benchmarks, i.e., SMAC 40 with reward and Overcooked [41]. We further perform ablation studies for HMASD to confirm the benefits of components in our method. We select MAPPO (5), MAT 31 and MASER 42 as our baselines. MAPPO and MAT are two strong policy-based MARI. algorithms that achieve state-of-art performance various multi-agent tasks 44 45 MASER
7

---

3m
24_ vo_
2m_ _e_
100
Fatee(N)
Moan Tooer Win Raaoo(a))
Mean Test Win Rate(
MATPO
MASI
60
SEASER
80
130
20
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
Timesleps(k)
Timesteps(M)
TimestepsiM)
Figure 6: Performance comparison between HMASD and baselines on SMAC with 0-1 reward.
cramped_ room
seymmelltc_atvvarlggee
advantagee
coordination rrnng
240
IRASS
Meen Test Eptood Reward
300
Meen Test Eproode Reward
120
MA3PO
240
344GER
120
120
60
0.0
2.0
4,0
8.0
8.0
10.0
0.0
2.0
4.0
6.0
8.0
10.0
0.0
200
1,0
6.0
8.0
10.0
Timesteps/M)
Timesteps(M))
Timestep((M)
Figure 7: Performance comparison between HMASD and baselines Overcooked.
presents a goal-conditioned method for solving sparse reward MARL. For all methods, we show the mean and variance of the performance across five different random seeds. The hyperparameter setting can be found in Appendix F
4.1 Case Study
In this subsection, we design a toy game siice_an___ Bob to demonstrate how our method works. As shown Fig. [a), the Alice and_ and_Bob _ob game an 8 8 grid world environment surrounded by walls. There are two agents Alice and Bob with random imitial positions, two buttons at the top and two diamonds at the bottom. The goal of the game to collect both diamonds, where each diamond is allowed to be collected only when an agent is standing on the button with the same color. Alice and Bob can receive a non-zero team reward only after they cooperatively collect both diamonds. We set
Meen Test Success Rate(%)
100
the number of team skills nz = 2 and the number of individual skills nı 4 for HMASD. Fig. (b) and (c) show the learned skills of our method. We can observe that the two team skills Z 0, correspond collecting the blue diamond and red diamond for the whole team, respectively, and the four individual skills z' 0, 1, 2, guide the individual agent to reach the red diamond, red button, blue diamond and blue button, respectively. We observe similar skills for agents with different initial posi- tions in Appendix C By learning these diverse and useful skills, our method achieves a higher success rate of task completion than baselines as shown in Fig. 5 These sults demonstrate that HMASD could discover significant team and individual skills, and effectively combine them accomplish the task.
MAPPO
MASER
40
0.0
1.0
2.0
3.0
Timesteps(M)
Performance comparison between HMASD and baselines Alice and_Bodd_l
Figure 5:
4.2 Performance on Sparse Reward Multi-Agent Benchmarks
In this subsection, we first test our method on a widely-used MARL benchmark, SMAC 40 where we learn to control team ally units against team of enemy units controlled by a built-in strategy. The ally team wins the game only if all enemy units are killed within the time limit of an episode. Our objective to maximize the win rate for ally team. The default reward setting of SMAC contains many dense rewards, such the unit's health and damage. These dense rewards enable many MARL algorithms like MAT (31 and MAPPO 5 to attain almost 100% win rate on all scenarios. However, designing useful dense rewards is usually expensive and adjusting the weights between rewards is

---

3m
2m vs_
coordination _
Test Fasee(N)
IMAD
Mean Toner Win Rato((a)
Mean less Epleodi Rewerd
120
IDMASO
TBASO Naldiin
60
30
20
10
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0 Timesteps/M)
1.5
2.0
0.0
2.0
4,0
6.0
8.0
10.0
Timesleps(M)
Timestep(MM)
Figure 8: Ablation studies regarding components of HMASD.
time-consuming. In this work, we consider more general reward setting, i.e., SMAC with 0-1 reward, which returns a non-zero team reward of 1 only at the last timestep if the ally team wins. As shown in Fig. 66 HMASD significantly outperforms baselines on SMAC with 0-1 reward, where MAT and MAPPO don't t work at all. MASER only works on the scenario 3m and fails on the other two scenarios 2s vs __ssc and 2m_ 2m_vs__ vs_1z. This demonstrates the effectiveness of HMASD and the high efficiency of skill discovery for solving sparse reward multi-agent tasks.
Next, we evaluate HMASD on another sparse reward multi-agent task called Overcooked, a popular cooperative cooking simulation game. We follow a simplified version of the game proposed in [41]. the objective of which is to deliver the soup as fast as possible. Each soup requires agents to place onions in pot, cook them for 20 timesteps, put the cooked soup in a dish, and deliver it to the service desk. All agents will receive a team reward of 20 after delivering a soup. In Fig. 7 we compare HMASD with baselines on three Overcooked scenarios. It can be observed that HMASD could also achieve superior performance over baselines on Overcooked, which further confirms that HMASD can discover useful skills to effectively complete the task.
Moreover, visualize the learned skills and find that HMASD uses only few skills complete the complex task after training. This is because HMASD will encourage different skills to explore different state-observation spaces, but only small part of the state-observation space can result in non-zero team reward in the complex sparse reward multi-agent task. For example, on the SMAC scenario, there is usually big map, we observe that most of the learned skills explore areas of the map without enemies and thus don't ton't contribute to the team reward. These results indicate that when the Saterobbervvtiion space is large, HMASD can discover diverse skills but maybe only some of them are useful for the team reward. More fine-grained results can be found in Appendix |
Additionally, we compare HMASD with an exploration bonus MARL baseline [46] in Appendix H The results show that the performance improvements HMASD mainly come from diverse skill discovery and effective skill combination, rather than implicit exploration.
4.3 Ablation Studies
In this subsection, we conduct ablation studies to investigate the impact of three main components in HMASD: (1) discovering both team and individual skills, (2) using a combination of extrinsic team reward and intrinsic rewards for the low-level reward and (3) employing the high-level skill coordinator to assign skills to agents. To test component (1), we introduce two variants of HMASD, denoted as HMASD MMMaa_ NoTTeam and HMASD_ IIMASD_Nondii, respectively. HMASD_NG -ooTeemmmm only learns individual skills for agents, while HMASD_N _Nondi only lets all agents learn a shared team skill. To evaluate component (2), we consider HMASD NoExRew and HMASD NoInRew, which set X and AD = Zu = 0 in Eq. 4 respectively, As for component (3), we adopt HMASD MMASD_NoHighh NoHigh, which removes the high-level policy and randomly assigns skills agents the start of each episode. As shown in Fig. 8, HMASD performs better than both HMASD NoTeam and HMASD NoIndi, which emphasizes the importance of discovering both team and individual skills in multi multi-agent tasks. After removing the extrinsic team reward or intrinsic rewards in the low-level reward, the performance of HMASD has a large drop. Especially without intrinsic rewards, HMASD can't work on most scenarios. This highlights the considerable contributions of optimizing the diversity term in Eq. 3 Besides, the performance comparison between HMASD and HMASD Higggh reveals the necessity of the high-level policy. More ablations for HMASD are shown in Appendix

---

Related Work
Skill Discovery in MARL Skill discovery a promising approach to solving complex tasks for its ability to discover diverse skills even without any extrinsic reward. Recently, this approach has been extended MARL. MASD [ learns coordinating skills adversarially by setting an information bottleneck. VMAPD TO constructs a diverse Dec-POMDP to learn diverse skills as different solutions for multi-agent tasks. However, these two methods focus on learning a shared team skill for all agents, and use only one skill throughout an episode. To combine different skills to tackle multi-agent tasks, HSD [T] employs hierarchical structure, where the high-level policy selects low-level skills for agents based on local observations. HSL [12] follows a similar hierarchical structure and introduces a skill representation mechanism to enhance skill learning. Nevertheless, these two methods only learn individual skills from each agent's 's individual perspective, without considering team skill learning. Besides, in these two methods, each agent selects skills only based on its local observation, leading potential skill duplication between agents with similar observations. ODIS [47] applies skill discovery to offlin MARL, which discovers generalizable individual skills across different tasks from offline multi-task data, and trains coordination policy assign skills to agents with the centralized training and decentralized execution paradigm [4] However, this decentralized skill assignment may also lead to skill duplication. Chen et al.
[88]
49 learn joint
options (i.e., skills) by approximating the joint state space as the Kronecker product of the state spaces of individual agents. In this work, we propose discover both team skills and individual skills. Moreover, we assign skills to agents from a global perspective to enable complementary skill selection and prevent skill duplication effectively.
Sparse Reward MARL The issue of sparse reward poses a significant obstacle when applying RL to solve real-world problems, which will be exacerbated in multi-agent tasks. Several approaches have been proposed to address the sparse reward problem in MARL. SEAC [50] leverages experience sharing among agents enable efficient exploration. CMAE
[T
promotes cooperative exploration
by selecting a shared goal for agents from state spaces. VACL
52
tackles the sparse reward problem
in MARL by utilizing an automatic curriculum learning algorithm that incrementally expands the
introduces a conl-conditioned method that generates subgoals for agents from the experience replay buffer. In this work, we present hierarchical MARL algorithm that discovers underlying skills and effectively combines these skills to solve sparse reward multi-agent tasks.
training tasks from easy to hard. More recently, MASER 42
Conclusion
It is efficient way to learn set of skills and combine them properly tackle complex tasks. In this study, we take advantage of skill discovery to address MARL problems. We propose to discover latent team and individual skills by embedding them into probabilistic graphical model. In this way, we formulate multi-agent skill discovery as an inference problem, and derive a variational lower bound as the optimization objective. We then design practical MARL method called HMASI) to optimize the lower bound, where different team skills explore different global state spaces and different individual skills explore different local observation spaces. The empirical results show that HMASD significantly improves performance on challenging sparse reward multi-agent tasks by learning diverse team and individual skills with efficient skill combination.
10

---

Acknowledgments
This work supported by National Key R&D Program of China under Contract 20222D01 19802, and National Natural Science Foundation of China under Contract 61836011 1. It was also supported by GPU cluster built by MCC Lab of Information Science and Technology Institution, USTC, and the Supercomputing Center of the USTC. What's more, it is funded by Collective Intelligence & Collaboration Laboratory (Open Fund Project No. QXZ23014101) and by Young Elite Scientists Sponsorship Program by CAST 2022QNRC001.
References
[1] D. Rizvi and D. Boyle, "Multi-agent reinforcement learning with action masking for uav-enabled mobile communications," " arXiv preprint arXiv:2303 2023.
[2] B. Xiao, R. Li, F. Wang, C. Peng, J. Wu, Z. Zhao, and H. Zhang, "Stochastic graph neural network-based value decomposition for marl internet vehicles," arXiv preprint arXiv:2333.13213, 2023.
[3] T. Wu, Zhou, K. Liu, Y. Yuan, X. Wang, H. Huang, and D. O. Wu, "Multi-agent deep reinforcement learning for urban traffic light control vehicular networks," IEEE Transactions on Vehicular Technology, vol. 69, no. 8. pp. 9243-8256, 2020.
[4] T. Rashid, M. Samvelyan, C. Schroeder, G. Farquhar, J. Foerster, and S. Whiteson, "Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning," in Proceedings of the International Conference on Machine Learning. PMLR, 2018, pp. 4295-4304.
[5] C. Yu, A. Velu, E. Vinitsky, J. Gao, Y. Wang, A. Bayen, and Y. Wu, "The surprising effectiveness of ppo in cooperative multi-agent games," Advances in Neural Information Processing Systems, vol. 35, pp. 24 1661111466666 624, 2022.
[6] J. She. K. Gupta, and M. J. Kochenderfer, "Agent-time attention for sparse rewards multi-agent rein- forcement learning," arXiv preprint arXiv:2210.17540 2022.
B. Eysenbach, A. Gupta, J. Ibarz, and S. Levine, "Diversity is all you need: Learning skills without reward function," arXiv preprint 1802.06677 2018
[8] A. Sharma, S. Gu, S. Levine, V. Kumar, and K. Hausman, "Dynamics-aware unsupervised discovery of skills," arXiv preprint arXiv:1907.0166 2019.
S. He, Shao, and X. "Skill discovery of coordination multi agent reinforcement learning." arXiv preprint arXiv:2006.00 0400 2020.
[10] S. Huang,
Wang, D. Li, Wang. T. Chen, J. Zhu. "Vmapd: Generate diverse solutions for multi-agent games with recurrent trajectory discriminators," in IEEE Conference on Games. IEEE, 2022, 9-16.
[11] J. Yang. Borovikov, and H. Zha, "Hierarchical cooperative multi-agent reinforcement learning with skill discovery." arXiv preprint (912.0:99903358 2019.
[12] Y. Liu, Li, X. Xu, Y. Dou, and D. Liu, "Heterogeneoou skill learning for multi-agent tasks," Advances in Neural Information Processing Systems, vol. 35, pp. 37 011-37 023, 2022.
[13] L. Gyarmati, H. Kwak, and P. Rodriguez, "Searching for a unique style in soccer," arXiv preprint arXiv: 1409.0308, 2014.
[14] S. Levine, "Reinforcement learning and control as probabilistic inference: Tutorial and review," arXiv preprint 1.0.v:1800500009 2018.
[15] A. Vaswani. N. Shazeer, N. Parmar. J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. "Attention is all you need," Advances Neural Information Processing Systems, vol. 30, 2017.
[16] F. A. Olichock and C. Amato, A concise introduction to decentralized POMDPs. Springer, 2016.
[17] K. Gregor, J. Rezende, and D. Wierstra, "Variational intrinsic control," arXiv preprint arXiv: 161 1.05007
2016.
[18] J. Achiam, H. Edwards, D. Amodei, and P. Abbeel, "Variational option discovery algorithms." arXiv preprint arXiv:1807.10240 2018.

---

[19] S. Hansen, W. Dabney, A. Barreto. T. Van de Wiele, D. Warde-Farley, and V. Mrih, "Fast task inference with variational intrinsic successor features," arXiv preprint arXiv:190..05030, 2019.
[20] I.. Lee, B. Bysenbach, E. Parisotto, E. Xing, S. Levine, and R. Salakhutdinov, "Efficient exploration via state marginal matching," arXiv preprint 1xXi::9066005777000 2019.
[21] T. Haarnoja, A. Zhou, K. Hartikainen, G. Tucker, S. Ha. J. Tan, V. Kumar, H. Zhu, A. Gupta, P. Abbeell et al., "Soft critrc algorithms and applications." arXiv preprint (.12iv:812.0099000 2018.
[22] T. Haarnoja, K. Hartikainen, P. Abbeel, and S. Levine, "Latent space policies for hicrarchical reinforcement learning." in Proceedings of the International Conference on Machine Learning. 1851-1860.
PMLR, 2018, pp.
[23] Y. Wen, Y. Yang. R. Luo, J. Wang. and W. Pan. "Probabilistic recursive reasoning for multi-agent reinforcement learning," arXiv preprint a 1901.09077 2019.
[24] Li, I.. Wu, J. Wang, and H. Bou Ammar, "Multi-view reinforcement learning." Advances in Neural Information Processing Systems, vol. 32, 2019.
[25] B. D. Ziebart, Modeling purposeful adaptive behavior with the principle of maximum causal entropy. Carnegie Mellon University, 2010.
[26] T. Haarnoja, A. Zhou, P. Abbeel, and S. Levine, "Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor," in Proceedings of the International Conference on Machine Learning. PMLR, 2018, pp. 1861-1870.
[27] S. Hu, F. Zhu, X. Chang, and X. Liang, "Updet: Universal multi-agent reinforcement learning via policy decoupling with transformers," " arXiv preprint arXiv:2 2021.
[28] M. Wang. M. Feng, W. Zhou, and H. Li, "Stabilizing voltage in power distribution networks via multi-agent reinforcement learning with transformer." in Proceedings of ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2022, pp. 1899-1909.
[29] W.-C. Tseng, T.-H. J. Wang. Y.-.. Lin, and P. Isola, "Offline multi-agent reinforcement learning with knowledge distillation," Advances in Neural Information Processing Systems, vol. 35, pp. 226-237, 2022.
[30] L. Meng, M. Wen, Y. Yang, C. Le, X. Li, W. Zhang, Y. Wen, H. Zhang, J. Wang, and B. Xu, "Offline pre-trained mulli--gentt decision transformer: One big sequence model conquers all starcraftii tasks," arXiv preprint arXiv:21 /2. 02.02455 2021.
[31] M. Wen, Kuba, R. Lin, W. Zhang, Y. Wen, J. Wang, and Y. Yang. "Multi-agent reinforcement learning is a sequence modeling problem," Advances in Neural Information Processing Systems, vol. 35, pp. 16 509-16521,, 2022.
[32] K. Cho, B. Van Merriënboer, C. Gulcehre, D. Bahdanau, F. Bougares, H. Schwenk, and Y. Bengio, "Learning phrase representations using rnn encoder-decoder for statistical machine translation." arXiv preprint arXiv:1406.1078, 2014.
[33] Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, "Proximal policy optimization algorithms," arXiv preprint 1777v: 2017.
[34] J. Schulman, P. Moritz, S. Levine. M. Jordan, and P. Abbeel, "Hligh-dimensional continuous control using generalized advantage estimation," arXiv preprint ar0iv 024388 2015.
[35] J. G. Kuba, R. Chen, M. Wen, Y. Wen, F. Sun, J. Wang. and Y. Yang. "Trust region policy optimisation in multi-agent reinforcement learning," arXiv preprint arXiv:2109 /251, 2021.
[36] P. Sunchag, G. Lever, A. Gruslys, W. M. Czarnecki, V. Zambaldi, M. Jaderberg, M. Lanetot, N. Sonnerat,
J. Z. Leibo, K. Tuyls et al., Vallue-dcoomposition networks for cooperative multi-agent learning," arXiv preprint 1rXiv:/706. 05296, 2017.
[37] Y. Yang, J. Hao, B. Liao, K. Shao, G. Chen, W. Liu, and H. Tang, "Qatten: A general framework for cooperative multiagent reinforcement learning." arXiv preprint arXiv:2002.03922 033399 2020.
[38] K. Son, D. Kim, W. J. Kang, D. E. Hostallero, and Y. Yi, "Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement leamnng," in Proceedings of the International Conference on Machine Learning. PMLR, 2019, pp. 5887-5896.
[39] J. Wang. Z. Ren, T. Liu. Y. Yu, and C. Zhang, "Qplex: Duplex dueling multi-agent q-learning." in Proceedings of the International Conference Learning Representations, 2021.
12

---

[40] M. Samvelyan. T. Rashid, C. S. De Witt, G. Farquhar. N. Nardelli, T. G. Rudner, C.-M. Hung, P. H. Torr J. Foerster, and S. Whiteson, "The starcraft multi-agent challenge." arXiv preprint arXiv: 002.04043, 2019.
[41] M. Carroll, R. Shah, M. K. Ho, T. Griffiths, S. Seshia, P. Abheel, and A. Dragan, "On the utility of learning about humans for human-ai coordination." Advances in Neural Information Processing Systems, vol. 32, 2019.
[42] J. Jeon, W. Kim, W. Jung, and Y. Sung, "Maser: Multi-agent reinforcement learning with subgoals generated from experience replay buffer," Proceedings of the International Conference on Machine Learning. PMLR, 2022, pp. 1044110052.
[43] C. S. Witt, Peng, P.-. Kamienny, P. Torr, W. Böhmer, and Whiteson, "Deep multi-agent reinforcement learning for decentralized continuous cooperative control," arXiv preprint arXiv:2003.06709, vol. 19, 2020.
[44] Y. Chen, T. Wu, S. Wang. X. Feng. J. Jiang, Z. Lu, S. McAleer, H. Dong, S.-C. Zhu, and Y. Yang. "Towards human-level bimanual dexterous manipulation with reinforcement learning," Advances in Neural Information Processing Systems, vol. 35, pp. 5150-5163, 2022.
[45] K. Kurach, A. Raichuk, P. Stanczyk, M. Zajac, O. Bachem, L. Espeholt, C. Riquelme, D. Vincent, M. Michalski, O. Bousquet al., "Google research football: A novel reinforcement learning environment," in Proceedings of the AAAI Conference on Artifiical Intelligence, vol. 34, no. 04, 2020, pp. 4501 -5100
[46] T. Wang. J. Wang, Y. Wu, and C. Zhang, lifluence-bbsee multi-agent exploration." arXiv preprint 19X.v:9110005512 2019.
[47] F. Zhang, C. Jia, Y.-C Yuan, Y. Yu, and Z. Zhang. "Discovering generalizable multi agent coordi- nation skills from multi-task offline data," " Proceedings of the International Conference on Learning Representations, 2023.
[48] Chen, Chen, Lan, and V. Aggarwal, "Learning multi agent options for tabular reinforcement learning using factor graphs," arXiv preprint arXiv:2201.08227 2022.
[49] Chen, Chen, T. Lan, V. Aggarwal, "Scalable aueti- covering option discovery based on
kronecker graphs," Advances in Neural Information Processing Systems, vol. 35, pp. 30 (06-30418, 2022.
[50] F. Christianos, Schäfer, and Albrecht, "Shared experience actor-critic learning." Advances in Neural Information Processing Systems, vol. 33, pp. 10707-11 717, 2020.
ageti- reinforcement
[51] I.JJ. Liu, U. Jain, R. Yeh, A. Schwing, "Cooperative exploration for multi-agent deep reinforcement learning," Proceedings of the International Conference on Machine Learning. 6826- 6836.
PMLR, 2021, pp.
[52] J. Chen, Y. Zhang. Y. Xu, H. Ma, H. Yang. J. Song. Y. Wang. and Y. Wu, "Variational automatic curriculum lcarning for sparse-reward cooperative multi-agent problems," Advances in Neural Information Processing Systems, vol. 34, pp. 9681-9699 2021.
13

---

A Pseudo Code of Hierarchical Multi-Agent Skill Discovery
Algorithm 1: Hierarchical Multi-Agent Skill Discovery
Initialize: Skill coordinator parameters 0, and Φn. Skill discoverer parameters 0r and Φ1. Skill discriminator parameters @D and 6a. High-level replay buffer Bi, Low-level replay buffer B;. State-skill pair dataset DD for episode 0, 1, .... do
# The inference phase
for t = 0, 0, 1.. 7T do
Collect global state 8, and agents' partial observations o, = (o) ,0f' from environments.
if' mod k = then
Sample skills Z, 2mm TA TT 2/m O.). end
for each agent g" E E do
Sample action af ~ m 2*)
end
Execute joint actions a, (a) ... aa) in environments and collect the team reward Tr. next state 8 and next observations 0++1-
for each agent g² EW do
Compute low-level reward = xeri + AD log (oggo((/)44))) + log Z). Store (t, o, 2", rf) into Bi.
end
if mod
then
Store 1 1: Ex=o rc-p) into Bi.
end
Store ($1+1, 0,, 21:0 into D. end
# The training phase
Sample random minibatch of data from B3 update 0n and Φn, by minimizing (0,, (n)) Sample random minibatch of data from BJ to update 0; and øi by minimizing (1,,, Φ1). Sample random minibatch of data from to update oD and @d by minimizing CaloD.
end
B Derivation of the Variational Lower Bound
In this section, we adopt the structured variational inference to formulate our objective based on the PGM Fig. (b). In structured variational inference, approximate inference performed by optimizing the variational lower bound [14. Let = (So.T: Oo.T, Co.r, Z, 2 2lm). the variational lower bound is given by:
log ((O..))) log / p(Oo,T, T)dr
log / p(OorT,77 7) 9(T)
((T)) dr
p p(OOTT,T)
log (oggg)))())
((T)
2 Brrg(r) [log ((o,: T) - log q(T)),
14

---

1,
1
0,
3,
(e)
2,
Z 0,2 3,2
(d) 1,2' 1,2
-0- 1,2-
Figure 9: Visualization of learned team and individual skills on Alice_ ______d__Bo__ (a-b), (c-d), (e-f) show the skills learned by the agents with three different initial positions, respectively.
where the inequality in the last line is derived using Jensen's inequality. We assume that the action prior distribution p(a)) is a uniform distribution. Then, we have:
p(Ou.T: 7) = p(so) Il
2) p(=='o," Z)
((T) ((su) II t=
2))aalo)))(( " x.-a((""o"'"""))
Similar 14 we fix (ss)) ((so)..(o;) ((541l(( at) p(sc+1156, at) and let
sr, an) exp(r(st, az)). The bound reduces to:
(og.(( ETrg(r) [log p(O..(OO.... 7) log
(r(s), ar) + +logp(Z(ss) Σ" logp(2"|o/,,
ETng(T)
log ((((s)) -" log q(> 2)
-) E"
log (ogg(otlo(,='))
C Visualization of skills on alice_and_Bor
We visualize the learned team and individual skills on Alice_and @alce_anddBee and_Bob by the agents with different initial positions in Fig. D With different initial positions, agents can learn similar team and individual skills. Specifically, team skills Z 0 and Z = guide the whole team to collect the blue diamond and the red diamond, respectively. Individual skills zz 0. z² = 1, zd 2 and zt guide the individual agent to reach the red diamond, red button, blue diamond and blue button, respectively.
15

---

100
100
Meen Test Win Ratee
Moan Tece Win Rato(t))
80
k0
80
80
Texe
20
20
0.0
0.5
1.0 Timestepu(k)
1.5
2.0
0.0
0.5
1.0 Timestaps(M) (b)
1.5
2.0
0.0
0.5
1.0
1.5
2,0
Timesteps(M))
(c)
Figure 10: More ablations for HMASD. (a) The performance of HMASD with different skill intervals. (b) The performance of HMASD with different numbers of team skills. (c) The performance of HMASD with different numbers of individual skills.
D
More Ablations
We conduct more ablations about the skill interval k, the number of team skills and the number of individual skills n, in Fig. TO Results reveal that HMASD) performs poorly with too short or too long skill intervals, which demonstrates that an appropriate number of timesteps is necessary for each skill be learned effectively. Furthermore, can be observed that the performance of HMASD varies greatly with different numbers of team skills and individual skills, which shows that HMASD not very stable on sparse reward multi-agent tasks. The limitations of our work are discussed in Appendix G
E
Hyperparameter Setting
For all baselines, we use the open source code of the original paper. We implement HMASD based on the codebase of MAT and MAPPO. The hyperparameters for different tasks are presented in Table m 3 In particular, we want emphasize the setting Xe. i.e., the weight of team reward in the low-level reward. It guides the skills to be useful for the team performance. On the simple aee_and__Bo__ the state-observation space small, and it's easy for skills to explore those states that contribute to the team reward. So we set A = 0. On the complex SMAC with ()- reward and Overcooked, the obtervobservttion space is large, and it's very difficult to explore those rare states that induce positive team reward. We set Å 100, which is much larger than the weights of intrinsic rewards Ap and Aς. In this way, the team reward can dominate the low-level reward when agents encounter positive team reward, which guides the agents to learn to complete the task more quickly.
Table 1: Common hyperparameters used for HMASD, MAT and MAPPO across all tasks.
hyperparameters
value
hyperparameters
value
hyperparameters
value
training threads
16
rollout threads
32
hidden size
64
use valuenorm
True
use orthogonal
True
gain
0.01
optimizer
Adam
optimizer epsilon
le-5
weight decay
0
ppo epoch
15
clip param
0.2
num mini batch
1
value loss coef
1
use gae
True
gae lambda
0.95
gamma
0.99
use huber loss
True
huber delta 10
Table 2: Common hyperparameters used for HMASD, MAT and MAPPO in different tasks.
task
Ir
episode length
num env steps
eval episodes
eval rollout threads
Alice_and and_Babbbb______
Bob
5e-4
100
3e6
100
SMAC with 0-1 reward
le-4
100
2e6
100
Overcooked
le-4
400
1c7
32
16

---

Table Different hyperparameterss used for HMASD different scenarios.
scenario
nz
n2
A
À
Xe
AD
Xd
Alice _ice_anddBoo
50
2
0.1
0.01
0
0.1
0.2
3m
25
3
0.001
0.01
100
0.1
0.5
2s sn_and_ Isc 2m and lz
25
2
0.03
0.01
100
0.1
1
50
3
0.005
0.01
100
0.1
1
cramped room
3
0.01
0.01
100
0.5
asymmetric_advantages
25
3
0.01
0.01
100
0.1
0.1
coordination rring
3
0.01
100
0.15
0.1
(H) Individuual skill
(b) Individual skill
(c) Individuul skill 2
Figure 11: Visualizations of 3 learned individual skills on the SMAC scenario 3m. To visualize the ith individual skill, we all agents' individual skills to be i, i.e., 2² x² 23
where 1. (a) For individual skill 0, agents learn to spread out to both sides to form an are formation and focus fire the same enemy the same time, which can quickly reduce the number of enemies and win the game. (b) For individual skill I, agents learn to explore the bottom left area of the map, where there are no enemies. In the end, agents lose the game for not killing all enemies within the time limit. (c) For individual skill 2. agents learn to move right to approach enemies but not attack them in time, which leads to losing the game.
i = 0, 1,..,.....
Individul
(b) Individull skill
Figure 12: Visualizations of 2 learned individual skills on the SMAC scenario 2m_ vs_ 1z. (a) For individual skill O. agents learn take advantage of attack range kite the enemy. The agent closer to the enemy will run away, and the other agent will attack the enemy. In this kiting way, the two agents take turns attacking the enemy and ultimately win the game. (b) For individual skill 1, agents learn to explore the bottom area of the map, while the enemy is in the upper area. Finally, agents fail find the enemy and lose the game.
More Fine-grained Results
Percentage skills useful for the team reward We count the average percentage of useful individual skills among all learned individual skills on the SMAC. For each SMAC scenario, we conduct 5 different runs with different random seeds. We learn 3, 5, individual skills for each run on 3m, 2s_vs_ vsc,sc, 2m_ in__s_1e 1z, respectively. Therefore, we learn 3 skills on three SMAC scenarios. After our test, only individual skills are useful for the team performance. In other words, only 24% of the learned individual skills are useful for completing the task on average after training.
+ 2 * 5 = 50 individual
Percentage of runs that learn meaningful behavior For every scenario, we conduct 5 runs. For each the SMAC scenario, agents discover useful skills, the performance will quickly
17

---

increase to 1. So the final performance is either 1 or 0, which leads to a large variance among 5 runs. There are 7 scenarios in this work. Among 5 35 runs, 26 runs could learn meaningful behavior. Therefore, the percentage of the model to learn meaningful behavior among all trials is 26/35 74.3%. One of our future goals increase this percentage and reduce the variances of our method.
Visualization of the learned skills We visualize the learned individual skills on SMAC as shown in Fig. and Fig. 12 We can observe that only one skill can result in a non-zero team reward on both scenarios, and the remaining skills explore the state-observation spaces that don't I contribute to the team reward. As for the learned skills Overcooked, we find that in those segh-performance runs, all skills are useful and each of them can perform well individually. This may be because Overcooked is grid world task and has smaller state-observation space than SMAC. Thus those states with positive rewards are easier to be explored by all skills. These visualizations reflect the potential inefficiency of HMASD in solving complex tasks with large state-observation space.
G Limitations
In this section, we discuss three potential limitations of HMASD. Firstly, when the state-observation space is large, HMASD can discover diverse skills but maybe only some of them (about 24% on SMAC) are useful for the team reward. There are a large percentage of skills are assigned to explore those zero-reward states. Secondly, the number of team skills and individual skills should be carefully adjusted. When applying HMASD to new task, it requires to adjust several hyperparameters as shown in Table 3 Thirdly, HMASD can only learn team skills for the entire team, which lacks flexibility in multi-agent tasks that require team skills within sub-teams. Our future work aims to improve these limitations and make HMASD better at solving sparse-reward multi-agent tasks.
H Comparison of HMASD with the Multi-Agent Exploration Baseline
In this section, compare HMASD with an exploration bonus MARL baseline, EITI/EDTI (46). on Overcooked. EITI/EDTI proposes exploration strategies where agents start with decentralized exploration driven by their individual curiosity (i.e., individual exploration), and are also encouraged to coordinate their exploration (i.e., joint exploration). The final reward for each agent is the sum of team reward, individual exploration bonus and joint exploration bonus. EITI and EDTI provide 2 ways to calculate the joint exploration bonus. The comparison of HMASD with EITI/EDTI on Overcooked is shown in Table
We can see that HMASD outperforms EITT and EDTI on all Overcooked scenarios. Although EITI/EDTI encourages both individual exploration and joint exploration, it doesn't 't formulate the relationship between individual exploration and joint exploration. These two explorations may have confficts, causing neither exploration to work well. In our work, propose to discover both team and individual skills for solving sparse-reward multi-agent tasks. Importantly, we build a probabilistic graphical model to formulate the relationship between team skill and individual skill, and then derive a lower bound as our objective. The results show that our method could discover significant team and individual skills, and effectively combine them to accomplish the sparse- reward multi-agen task.
Table 4: The final episode reward of HMASD and EITI/EDTI on Overcooked.
Scenario
EITI
EDTI
HMASD
cramped gramped_room room
0. + 0.013
0.119 + 0.015
236.0 + 8.0
ssymmetric_advantaen
0.008 + 0.002
0.004 + 0.002
295.1 + 84.5
coordination ring
0.0 0.0
0.0 + 0.0
80.0 = 97.9
18


Reviews:
[{"review_id": "digV7Wzplr", "reviewer": "Reviewer_Jm7Q", "summary": "This paper presents Hierarchical Multi-Agent Skill Discovery (HMASD) that can discover both team and individual skills in MARL. The authors formulate multi-agent skill discovery as an inference problem in probabilistic graphical models. The model consists of a skill coordinator that reasons about team and individual skills, a skill discoverer that maps skills into actual execution, and a skill discriminator that encourages the learning of diverse and distinguishable skills. The proposed method is evaluated on sparse reward multiagent benchmark including SMAC and overcooked and is shown to achieve superior performance comparing to baselines. Ablation studies are also done to verify the effectiveness of each proposed components.", "questions": "- In figure 6, there is no orange line and does that mean MAPPO fails to learn anything?\n- By comparing figure 6 and 7, the performance of MASER is so different. In figure 6, MASER is the only baseline that works; however, in figure 7, MASER is the baseline that works the worst. Could authors briefly explain why this is the case?\n- Why conduct experiment in SMAC rather than SMACv2?\n- I cannot find the 3m scenario in SMAC [40]. Does it mean 3 marine or MMM2?\n- How do the authors deal with the heterogenous agents in SMAC 2s_vs_1sc and 2m_vs_1z?\n- It would be interesting to visualize the learned skills in both SMAC and overcooked environments. \n- In the paragraph at line 314, the authors discuss interesting observation of how skill learning is done. It will be more convincing if some quantitative results can be shown here to support the statement.\n- In spite of the limited space, it's better to include the related work section in the main paper to make it more self-contained.\n- The variances of HMASD in 2s_vs_1sc, 2m_vs_1z, and coordination_ring are extremely large and the lower bounds of the shaded area are at zero, making it hard to justify the effectiveness of the method. What is the percentage of the model to learn meaningful behavior among all trials?\n- How many random seeds are used for plotting those training curves?", "limitations": "The limitation of this work is not explicitly discussed in the paper.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The proposed method is intersting.\n- The paper is nicely structured.", "weaknesses": "There is a bit limited given only training curves are shown. More fine-grained experiments like visualization of learned skills, progression of skill learning, etc., may provide more insight into the effectiveness of the proposed method. Overall the experiment is on a low side and see more detailed comments in the questions section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed comments. We hope we can address your concerns below.\n\n**Q1**: In figure 6, there is no orange line and does that mean MAPPO fails to learn anything?\n\n**A1**: Yes, the orange line is covered by the blue and green lines. Both MAT and MAPPO fail to learn anything on SMAC with 0-1 reward.\n\n**Q2**: In figure 6, MASER is the only baseline that works; however, in figure 7, MASER is the baseline that works the worst. Could authors briefly explain why this is the case?\n\n**A2**: MASER proposes to automatically generate subgoals for agents, and it only demonstrates the effectiveness on the SMAC tasks in the original paper. In our work, we find that MASER works only in SMAC but fails in Overcooked. There are other works[1,2] that also find that MASER performs poorly on other multi-agent tasks. This may be because the automatic subgoal generation mechanism of MASER may only work in some specific tasks, e.g., SMAC.\n\n**Q3**: Why conduct experiment in SMAC rather than SMACv2?\n\n**A3**: SMACv2 was proposed because SMAC with dense reward is so easy that many algorithms (such as MAT and MAPPO) can achieve almost 100% win rate on all dense-reward SMAC scenarios. In our work, we aim to solve challenging multi-agent tasks with sparse reward. And in our early experiments,  we found that SMAC with 0-1 reward is hard enough to compare the performance of different algorithms. So we choose SMAC rather than SMACv2.\n\n**Q4**: I cannot find the 3m scenario in SMAC. Does it mean 3 marine or MMM2?\n\n**A4**: The original SMAC paper introduces only 14 scenarios, while SMAC's codebase provides more scenarios, including 3m. The 3m scenario represents 3 allied marines versus 3 enemy marines.\n\n**Q5**: How do the authors deal with the heterogeneous agents in SMAC 2s_vs_1sc and 2m_vs_1z?\n\n**A5**: In both 2s_vs_1sc and 2m_vs_1z, the type of all agents controlled by MARL method is the same. Therefore, they are scenarios with homogeneous agents, not heterogeneous agents. Our method can also deal with heterogeneous agents.\n\n**Q6**: It would be interesting to visualize the learned skills in both SMAC and overcooked environments.\n\n**A6**: Thanks for your suggestion. Due to time limit, we visualize the learned individual skills on the SMAC scenario 3m as shown in Figure 1, which can be found in the one-page PDF of the global response. We can observe that only 1 of 3 skills can result in a non-zero team reward, and the remaining 2 skills explore the state-observation spaces that don’t contribute to the team reward.  We will provide more skill visualizations in our next revision.\n\n**Q7**: In the paragraph at line 314, the authors discuss interesting observation of how skill learning is done. It will be more convincing if some quantitative results can be shown here to support the statement.\n\n**A7**: We count the average percentage of useful individual skills among all learned individual skills on the SMAC. For each SMAC scenario, we conduct $5$ different runs with different random seeds. We learn $3, 5, 2$ individual skills for each run on 3m, 2s_vs_1sc, 2m_vs_1z, respectively. Therefore, we learn $3\\*5+5\\*5+2\\*5=50$ individual skills on three SMAC scenarios. After our test, only $12$ individual skills are useful for the team performance. In other words, only $24$% of the learned individual skills are useful for completing the task on average after training.\n\n**Q8**: In spite of the limited space, it's better to include the related work section in the main paper to make it more self-contained.\n\n**A8**: Thanks for your suggestion. We will include the related work section in the main paper in our next revision.\n\n**Q9**: The variances of HMASD in 2s_vs_1sc, 2m_vs_1z, and coordination_ring are extremely large and the lower bounds of the shaded area are at zero, making it hard to justify the effectiveness of the method. What is the percentage of the model to learn meaningful behavior among all trials?\n\n**A9**: For every scenario, we conduct $5$ runs. For each run on the SMAC scenario, once agents discover useful skills, the performance will quickly increase to $1$. So the final performance is either $1$ or $0$, which leads to large variance among $5$ runs. There are $7$ scenarios in our paper. Among $5*7=35$ runs, $26$ runs could learn meaningful behavior. Therefore, the percentage of the model to learn meaningful behavior among all trials is $26/35=74.3$%. One of our future goals is to increase this percentage and reduce the variances of our method.\n\n**Q10**: How many random seeds are used for plotting those training curves?\n\n**A10**: As mentioned in line 268, for each training curve, we show the mean and variance of the performance across five different random seeds.\n\n**Q11**: The limitation of this work is not explicitly discussed in the paper.\n\n**A11**: HMASD has two main limitations. Firstly, as mentioned in lines 320-321, when the state-observation space is large, HMASD can discover diverse skills but maybe only some of them (about $24$% on SMAC) are useful for the team reward. There are a large percentage of skills are assigned to explore those zero-reward states. Secondly, as mentioned in line 52 of Appendix E, the number of team skills and individual skills should be carefully adjusted. When applying HMASD to a new task, it require to adjust several hyperparameters as shown in Table 3 of Appendix F. Our future work aims to improve these limitations and make HMASD better at solving sparse-reward multi-agent tasks.\n\nFinally, thank you again for your thoughtful comments. We will incorporate your suggestions into our next revision. If some of your concerns are addressed, you could consider raising the rating. This is very important for us and we will appreciate it very much.  \n\n##### Reference\n\n[1] Yang X, et al. Learning Graph-Enhanced Commander-Executor for Multi-Agent Navigation.\n\n[2] Li W, et al. Semantically Aligned Task Decomposition in Multi-Agent Reinforcement Learning."}, {"review_id": "KEvvFBqU2I", "reviewer": "Reviewer_skAV", "summary": "This paper focuses on applying unsupervised skill learning to multi-agent reinforcement learning. For this purpose, the authors proposed a two-level hierarchical algorithm for discovering both team and individual skills in MARL, where individual skills refers to the abilities of individual agents and team skills refer to the ability of agents to work together as a whole. To this end, they embed the multi-agent skill discovery problem into a probabilistic graphical model and formulate it as an inference problem. Finally, they show that the proposed method achieves superior performance on sparse reward MARL benchmarks. ", "questions": "1. Have the authors encountered instability problems when training as there are so many components combined with the MARL algorithm?\n2. In Table 3 of Appendix F, different tasks require different hyperparameters. How did the authors choose these hyperparameters? Is it possible to find a suitable set of hyperparameters that can be suitable for most tasks?", "limitations": "This paper does not discuss the limitations. The biggest limitation might be that this method is too sensitive to hyperparameters, making it difficult to apply it directly to new tasks.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The problem this paper considers is rather important and it is a promising way to learn a set of skills and combine them properly to tackle complex tasks.\n2. The literature review is sufficient in Appendix B.\n3. The proposed method of decomposing the team skill into different individual skills for agents and ensuring that the joint behavior of all agents can form the team tactic is well-motivated with the football example.\n4. The proposed method is novel as this work is the first attempt to model both team skills and individual skills with the probabilistic graphical model in MARL.\n5. The empirical evaluation, especially Figure 4, is of high quality and quite interesting. \n6. The results on SMAC with sparse rewards and Overcooked are significant.\n7. The paper is generally well-written.", "weaknesses": "The reviewer is concerned about the training of the proposed method. (1) Too many components that require function approximation may bring instability into the MARL training process.  (2) In Figure 3 of Appendix E, the proposed method seems to be very sensitive to hyperparameters. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed comments. We hope we can address your concerns below.  \n\n**Q1**: Have the authors encountered instability problems when training as there are so many components combined with the MARL algorithm?\n\n**A1**: Yes, in the early version of HMASD, we found that HMASD performed poorly even in the dense reward tasks. We have iterated 28 versions to achieve the performance in the paper, including the problem formulation of multi-agent skill discovery, the way of training skills, the model structure, the hyperparameters, etc.\n\n**Q2**: In Table 3 of Appendix F, different tasks require different hyperparameters. How did the authors choose these hyperparameters? Is it possible to find a suitable set of hyperparameters that can be suitable for most tasks?\n\n**A2**: We mainly adjust hyperparameters through grid-search. There are 8 important hyperparameters in HMASD as shown in Table 3 of Appendix F. We don't directly perform grid-search on all 8 hyperparameters. We divide the 8 hyperparameters into 3 groups, i.e., $(k, n_Z, n_z), (\\lambda_h, \\lambda_l), (\\lambda_e, \\lambda_D, \\lambda_d)$. We first perform grid-search on $(k, n_Z, n_z)$ and fix them. The next grid-search is on $(\\lambda_e, \\lambda_D, \\lambda_d)$ and the last is on $(\\lambda_h, \\lambda_l)$. Although the final hyperparameters obtained in this way may be not the best,  it can greatly reduce tuning time. Among 8 hyperparameters, we find that the skill interval $k$, the number of team skills $n_Z$ and the number of individual skills $n_z$ are the three most important hyperparameters. The ablations on the three hyperparameters can be found in Appendix E. The performance of HMASD varies greatly with different $k, n_Z, n_z$. These hyperparameters mainly depend on the specific task, especially the number of skills for solving the task. It is possible to find a suitable set of hyperparameters that can generalize to a set of similar tasks. \n\n**Q3**: This paper does not discuss the limitations. The biggest limitation might be that this method is too sensitive to hyperparameters, making it difficult to apply it directly to new tasks.\n\n**A3**: HMASD has two main limitations. Firstly, as mentioned in lines 320-321, when the state-observation space is large, HMASD can discover diverse skills but maybe only some of them (about $24$% on SMAC) are useful for the team reward. There are a large percentage of skills are assigned to explore those zero-reward states. Secondly, as mentioned in line 52 of Appendix E, the number of team skills and individual skills should be carefully adjusted. When applying HMASD to a new task, it require to adjust several hyperparameters as shown in Table 3 of Appendix F. Our future work aims to improve these limitations and make HMASD better at solving sparse-reward multi-agent tasks.\n\nFinally, thank you again for your recognition and positive review to our work. We will incorporate your suggestions into our next revision."}, {"review_id": "wlFJH1G8qT", "reviewer": "Reviewer_7A65", "summary": "This paper proposed HMASD, a two-level hierarchical algorithm for discovering both team and individual skills in MARL. The high-level policy based on the transformer structure generates team skills and individual skills in an autoregressive manner, and the low-level policies output primitive actions according to individual skills and local observations. The authors formulate multi-agent skill discovery as an inference problem by augmenting the basic probabilistic graphical model. Experimental results show that HMASD can outperform other baselines in sparse reward multi-agent tasks.", "questions": "1. Shouldn't the distribution over $\\mathcal{O}$ be proportional to $\\exp(r(s,\\boldsymbol{a}))$ in L121?\n2. Would the initialization method of the arbitrary symbol $Z_0$ affect the performance of HMASD?\n3. Is the build order of the individual skills preset?\n4. In the *Alice_and_Bob* game, does $Z=1$ always correspond to the team skill collecting the red diamond?\n5. Can HMASD be applied to value-based multi-agent reinforcement learning algorithms such as QMIX?\n6. How does HMASD perform compared to CMAE and EITI/EDTI [1]?\n\n**Reference**\n\n[1]  Wang, Tonghan et al. Influence-Based Multi-Agent Exploration. 2019.", "limitations": "The authors state that the limit of their method is the number of team skills and individual skills should be carefully adjusted. That is to say, due to the introduction of more hyperparameters, HMASD needs more hyperparameter tuning.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-organized and well-motivated. The authors explain their formalism extremely well throughout, including in their methods section.\n2. The authors design a toy game *Alice_and_Bob* to demonstrate how their method works, which improves the soundness of their method.\n3. Some MARL work related to skill discovery or exploration is fully mentioned in the appendix.\n4. The authors conduct solid experiments in some popular benchmarks, and carry out sufficient ablation experiments.", "weaknesses": "1. Some important baselines are missing in the experiment section, such as HSD and CMAE.\n2. Some curves are stopped while learning does not seem to have converged in Figure 6 & 7.\n3. Due to the introduction of more hyperparameters (8 new hyperparameters can be seen from Table 3), HMASD needs more hyperparameter tuning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed comments. We hope we can address your concerns below.  \n\n**Q1**: Some important baselines are missing in the experiment section, such as HSD and CMAE.\n\n**A1**: HSD is an old method proposed in 2019. It performs poorly even on the dense reward SMAC as shown in [1]. In this paper, we select most recent related works as our baselines, including MAT(NeurIPS 2022)，MAPPO(NeurIPS 2022)，MASER(ICML 2022). Besides, HSD is a hierarchical MARL method that only learns individual skills, which has similar idea with HMASD\\_NoTeam in our ablations. We have compared HMASD with HMASD\\_NoTeam to verify the importance of learning team skills. So we don't use HSD as our baseline. CMAE is a solid method but has complex implementation details. We don't choose CMAE as a baseline because CMAE doesn't provide the code running on SMAC. There are someone that raised an issue about the SMAC running code on its github repository, but the author did not reply.\n\n**Q2**: Some curves are stopped while learning does not seem to have converged in Figure 6 & 7.\n\n**A2**: Yes, we stop the training when HMASD converges. Overall, HMASD can achieve faster convergence and higher average performance than baselines.\n\n**Q3**: Due to the introduction of more hyperparameters (8 new hyperparameters can be seen from Table 3), HMASD needs more hyperparameter tuning.\n\n**A3**: Yes, this is one limitation of HMASD. We mainly adjust hyperparameters through grid-search. We don't directly perform grid-search on all 8 hyperparameters. We divide the 8 hyperparameters into 3 groups, i.e., $(k, n_Z, n_z), (\\lambda_h, \\lambda_l), (\\lambda_e, \\lambda_D, \\lambda_d)$. We first perform grid-search on $(k, n_Z, n_z)$ and fix them. The next grid-search is on $(\\lambda_e, \\lambda_D, \\lambda_d)$ and the last is on $(\\lambda_h, \\lambda_l)$. Although the final hyperparameters obtained in this way may be not the best,  it can greatly reduce tuning time.\n\n**Q4**: Shouldn't the distribution over $\\mathcal{O}$ be proportional to exp⁡($r(s,\\boldsymbol{a})$) in L121?\n\n**A4**: We follow the Eq. (3) in [2] to define the distribution over $\\mathcal{O}$. Even if the distribution over $\\mathcal{O}$ is proportional to exp⁡($r(s,\\boldsymbol{a})$), it just adds a constant to the optimized lower bound in Eq. (3), which has no effect on our method.\n\n**Q5**: Would the initialization method of the arbitrary symbol $Z_0$ affect the performance of HMASD?\n\n**A5**: Following MAT, we set the first symbol of the decoder (i.e., $Z_0$) to a fixed vector. We would like to explore the effect of $Z_0$ in the future.\n\n**Q6**: Is the build order of the individual skills preset?\n\n**A6**: No, all individual skills are learned equivalently, not learned in a specific order. The learning of individual skills for each agent depends on the skill assignment of the high-level skill coordinator. And we train skill coordinator, discover, discriminator simultaneously.\n\n**Q7**: In the *Alice_and_Bob* game, does $Z=1$ always correspond to the team skill collecting the red diamond?\n\n**A7**: No, HMASD can discover diverse team skills in different runs on *Alice_and_Bob*. We choose one of the runs that have well-explainable behaviors to visualize the skills.\n\n**Q8**: Can HMASD be applied to value-based multi-agent reinforcement learning algorithms such as QMIX?\n\n**A8**: No, it can't. From the derived lower bound in Eq. (3), we can see that the skill entropy term and the action entropy term are related to the entropy of high-level policy and low-level policy. So HMASD can only be applied to policy-based MARL.\n\n**Q9**: How does HMASD perform compared to CMAE and EITI/EDTI?\n\n**A9**: No comparison with CMAE has been explained in A1.  Here, we compare HMASD with EITI/EDTI on Overcooked. EITI/EDTI proposes exploration strategies where agents start with decentralized exploration driven by their individual curiosity (i.e., individual exploration), and are also encouraged to coordinate their exploration (i.e., joint exploration). The final reward for each agent is the sum of team reward, individual exploration bonus and joint exploration bonus. EITI and EDTI provide 2 ways to calculate the joint exploration bonus. The comparison of HMASD with EITI/EDTI on Overcooked is shown in Table 1.\n\nTable1: The final performance of episode reward on Overcooked.\n\n|Scenario|       EITI        |       EDTI        |      HMASD       |\n| :------------------- | :--------------- | :--------------- | :-------------- |\n|     cramped_room      | 0.122 $\\pm$ 0.013 | 0.119 $\\pm$ 0.015 | 236.0 $\\pm$ 8.0  |\n| asymmetric_advantages | 0.008 $\\pm$ 0.002 | 0.004 $\\pm$ 0.002 | 295.1 $\\pm$ 84.5 |\n|   coordination_ring   |   0.0 $\\pm$ 0.0   |   0.0 $\\pm$ 0.0   | 80.0 $\\pm$ 97.9  |\n\nWe can see that HMASD outperforms EITI and EDTI on all Overcooked scenarios. Although EITI/EDTI encourages both individual exploration and joint exploration, it doesn't formulate the relationship between individual exploration and joint exploration. These two explorations may have conflicts, causing neither exploration to work well. In our work, we propose to discover both team and individual skills for solving sparse-reward multi-agent tasks. Importantly, we build a probabilistic graphical model to formulate the relationship between team skill and individual skill, and then derive a lower bound as our objective. The results show that our method could discover significant team and individual skills, and effectively combine them to accomplish the sparse-reward multi-agent task.\n\nFinally, thank you again for your thoughtful comments. We will incorporate your suggestions into our next revision. If some of your concerns are addressed, you could consider raising the rating. This is very important for us and we will appreciate it very much.\n\nReference\n\n[1] Wang T, et al. Rode: Learning roles to decompose multi-agent tasks.\n\n[2] Levine S. Reinforcement learning and control as probabilistic inference: Tutorial and review."}, {"review_id": "vKBOFRCuu0", "reviewer": "Reviewer_HRuC", "summary": "The paper proposes a two level hierarchical model for cooperative multi-agent RL. The key idea is to use variational inference based skill discovery over joint and individual policies. Intuitively, the objective can described as follows: i) find individual options, that are diverse (in terms of state visitations), ii) find joint options that are diverse (in terms of joint state visitation) iii) maximise the reward.\nThe experimental results on several cooperative domains are presented and the method performs better than well established baselines.", "questions": "I would like the authors to address the comment above on the (joint) exploration baseline.\nI would also like the authors to explicitly discuss the limitations of the method.\n\nI am willing to increase my score based on the answers.", "limitations": "There is no discussion on limitations, which I would encourage the authors to write.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper presents a technically solid, novel algorithm.\n- The experiments are convincing and demonstrate that the method indeed discovers helpful joint and individual skills and combines them to into a reward-maximising policy\n", "weaknesses": "- My main concern is that most of the improvement comes from implicit exploration bonus that arises from skill discovery objective, rather than from decomposition of the main task into subs tasks. It would be more convincing to have some sort of exploration bonus baseline. For example, adding a reward for individuals visiting new states and population visiting new joint states. For example, one could derive them via \"Exploration by random network distillation\" (https://arxiv.org/abs/1810.12894) method, one RND trained on individual states and another on the joint and summing up the reward.\n\n- There is no discussion on limitations.\n\n- Minor issue. The notation is a bit overloaded and makes things slightly confusing:\n - line 143-145. $Z \\in \\mathcal{Z}$ and $z \\in \\mathcal{X}$ is confusing\n - line 157-159. p and q seem to be referring to two distributions each \n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed comments. We hope we can address your concerns below.\n\n**Q1**: My main concern is that most of the improvement comes from implicit exploration bonus that arises from skill discovery objective, rather than from decomposition of the main task into subs tasks. It would be more convincing to have some sort of exploration bonus baseline. \n\n**A1**: Thanks for your suggestion. Here, we compare HMASD with an exploration bonus MARL baseline, EITI/EDTI[1], on Overcooked. EITI/EDTI proposes exploration strategies where agents start with decentralized exploration driven by their individual curiosity (i.e., individual exploration), and are also encouraged to coordinate their exploration (i.e., joint exploration). The final reward for each agent is the sum of team reward, individual exploration bonus and joint exploration bonus. EITI and EDTI provide 2 ways to calculate the joint exploration bonus. The comparison of HMASD with EITI/EDTI on Overcooked is shown in Table 1.\n\nTable1: The final performance of episode reward on Overcooked.\n\n|       Scenario        |       EITI        |       EDTI        |      HMASD       |\n| :------------------- | :--------------- | :--------------- | :-------------- |\n|     cramped_room      | 0.122 $\\pm$ 0.013 | 0.119 $\\pm$ 0.015 | 236.0 $\\pm$ 8.0  |\n| asymmetric_advantages | 0.008 $\\pm$ 0.002 | 0.004 $\\pm$ 0.002 | 295.1 $\\pm$ 84.5 |\n|   coordination_ring   |   0.0 $\\pm$ 0.0   |   0.0 $\\pm$ 0.0   | 80.0 $\\pm$ 97.9  |\n\nWe can see that HMASD outperforms EITI and EDTI on all Overcooked scenarios. Although EITI/EDTI encourages both individual exploration and joint exploration, it doesn't formulate the relationship between individual exploration and joint exploration. These two explorations may have conflicts, causing neither exploration to work well. In our work, we propose to discover both team and individual skills for solving sparse-reward multi-agent tasks. Importantly, we build a probabilistic graphical model to formulate the relationship between team skill and individual skill, and then derive a lower bound as our objective. The results show that our method could discover significant team and individual skills, and effectively combine them to accomplish the sparse-reward multi-agent task.\n\n**Q2**: There is no discussion on limitations.\n\n**A2**: HMASD has two main limitations. Firstly, as mentioned in lines 320-321, when the state-observation space is large, HMASD can discover diverse skills but maybe only some of them (about $24$% on SMAC) are useful for the team reward. There are a large percentage of skills are assigned to explore those zero-reward states. Secondly, as mentioned in line 52 of Appendix E, the number of team skills and individual skills should be carefully adjusted. When applying HMASD to a new task, it require to adjust several hyperparameters as shown in Table 3 of Appendix F. Our future work aims to improve these limitations and make HMASD better at solving sparse-reward multi-agent tasks.\n\n**Q3**: Minor issue. The notation is a bit overloaded and makes things slightly confusing: line 143-145. $Z \\in \\mathcal{Z}$ and $z^i \\in \\mathcal{X}$ is confusing; line 157-159. p and q seem to be referring to two distributions each\n\n**A3**: (1) $\\mathcal{Z}$ is the team skill space and $\\mathcal{X}$ is the individual skill space. The team skill space is for the whole team, and the individual skill space is for each individual agent. All agents share a same individual skill space $\\mathcal{X}$. (2) In this paper, we adopt the structured variational inference to derive the lower bound. In structured variational inference, we aim to approximate some distribution $p(y)$ with another, potentially simpler distribution $q(y)$. Typically, $q(y)$ is taken to be some tractable factorized distribution. So $p$ is the true distribution and $q$ is the approximate distribution for $p$.\n\nFinally, thank you again for your thoughtful comments. We will incorporate your suggestions into our next revision. If some of your concerns are addressed, you could consider raising the rating. This is very important for us and we will appreciate it very much.\n\n##### Reference\n\n[1] Wang, T, et al. Influence-Based Multi-Agent Exploration. ICLR 2020."}, {"review_id": "x79YL5oRpS", "reviewer": "Reviewer_Ty5M", "summary": "This paper introduces a framework that concurrently learns the individual skills for each agent and the team skill for the entire team, amalgamating these skills to perform multi-agent tasks. The discovery of skills is grounded in a probabilistic graphical model and employs variational inference tools for scalable optimization, extending unsupervised skill discovery in single-agent RL. The proposed algorithm exhibits superior performance on sparse reward multi-agent benchmarks when compared to robust MARL baselines.", "questions": "(a) The statement in Line 40, \"One is to let all agents learn a shared team skill [9, 10], which promotes team cooperation behaviors but suffers from high complexity,\" lacks clarity. Could you expand on why the complexity can be high? Since your work also aims to discover multi-agent skills, how have you addressed this complexity issue compared to [9, 10]?\n\n(b) There are additional works on multi-agent option (also known as skill) discovery, such as [1]. Please consider offering a comprehensive review of this research field to highlight your novel contributions.\n\n(c) Based on the definition in Line 144, it seems that the agents in the environment must be homogeneous as they share the same individual skill space. Is that correct?\n\n(d) In Line 197, it's unclear how the protocol design can prevent skill duplication.\n\n(e) It's unclear how you can maximize the lower bound in Eq. 3 with the objectives in Eq. 4-8, given that several coefficients are introduced and the optimization of functions are separated.\n\n(f) For fair comparisons, MAPPO, MAT, and MASER should also include the global state as part of the input. Is that the case in your study?\n\n(h) The number of team skills and individual skills are crucial hyperparameters and should be explicitly stated in the main paper.\n\n[1] Chen, Jiayu, Jingdi Chen, Tian Lan, and Vaneet Aggarwal. \"Scalable multi-agent covering option discovery based on Kronecker graphs.\" Advances in Neural Information Processing Systems 35 (2022): 30406-30418.", "limitations": "The limitation part is not included.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(a) The paper is effectively articulated, with clear exposition of the intuitions underlying each aspect of the algorithm design.\n\n(b) The empirical results provide substantial support for the paper's technical contributions.\n\n(c) The extension of unsupervised skill discovery from single-agent to multi-agent RL is a considerable achievement, offering a promising direction for future research.", "weaknesses": "(a) The algorithm might face limitations in practical applications due to: (1) the high-level policy necessitating input that comprises the global state and all agents' observations, and (2) the multi-agent options designed for the entire team, which lack flexibility as coordination among agents often manifests within sub-teams.\n\n(b) The algorithm framework is complex, encompassing multiple components and hyperparameters. The fine-tuning efforts, particularly for coordinating the training of neural networks across different scenarios, could be resource-intensive.\n\n(c) The paper omits important details in certain areas and requires more clarity. My queries and suggestions follow.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed comments. We hope we can address your concerns below.\n\n**Q1**: Weaknesses (a) in the Official Review.\n\n**A1**: Thank you for pointing out our potential limitations. For (1), as mentioned in lines 252-258, HMASD performs only one timestep of centralized execution in every $k$ timesteps. Such a small number of centralized information introduced can coordinate agents better from a global view compared to the fully decentralized method. And in many applications, it allows such a small amount of centralized execution. For (2), our team skills are for the entire team and expected to explore different global state spaces. it will be more difficult to learn team skills for a sub-team. How to divide the team into sub-team and how to learn team skills for sub-teams with variable number of agents. We think this could be an important direction in our future research.\n\n**Q2**: Weaknesses (b) in the Official Review.\n\n**A2**: Yes, in the early version of HMASD, we found that HMASD didn't work at all. We have iterated 28 versions to achieve the performance in the paper, including the problem formulation of multi-agent skill discovery, the way of training skills, the model structure, the hyperparameters, etc. Our future work aims to make HMASD more practical at solving sparse-reward multi-agent tasks.\n\n**Q3**: The statement in Line 40 lacks clarity. Could you expand on why the complexity can be high? Since your work also aims to discover multi-agent skills, how have you addressed this complexity issue compared to [9, 10]?\n\n**A3**: The joint state and action spaces of multi-agent tasks increase exponentially with the number of agents, so directly let all agents learn joint behavior to form team skills is exponential complexity. Our method reduces this complexity by decomposing the team skill into different individual skills (easier to learn) and guiding the joint behavior of all agents to form the team skill.\n\n**Q4**: There are additional works on multi-agent option (also known as skill) discovery, such as [1]. Please consider offering a comprehensive review of this research field to highlight your novel contributions.\n\n**A4**: Thanks for your suggestion. We will conduct a wider review of this research field in our next revision.\n\n**Q5**:  it seems that the agents in the environment must be homogeneous as they share the same individual skill space. Is that correct?\n\n**A5**: No, our method can also deal with heterogeneous agents. Although all agents share a same set of individual skills, the set of individual skills can be seen as the union of all agents' individual skills. An agent is not required to use all individual skills in the individual skill space.\n\n**Q6**: In Line 197, it's unclear how the protocol design can prevent skill duplication.\n\n**A6**: In some multi-agent tasks, it has the need for assigning different skills to agents with similar observations. In muti-agent skill learning methods like [1] and [2], each agent selects skills only based on its local observation, leading to potential skill duplication between agents with similar observations. In our method, agents select skills sequentially. When an agent selects the skill, it will know all previous agents' selected skills, which can prevent skill duplication between agents with similar observations.\n\n**Q7**: It's unclear how you can maximize the lower bound in Eq. 3 with the objectives in Eq. 4-8.\n\n**A7**: The lower bound in Eq. 3 has four terms, i.e, team reward, diversity term, skill entropy term and action entropy term. We maximize these four terms with different components in HMASD. We maximize the team reward by using it as the extrinsic reward for both the high-level policy and low-level policy. We maximize the diversity term by using it as the intrinsic reward for the low-level policy. The skill entropy term and action entropy term are maximized by optimizing the entropy of high-level policy and low-level policy, respectively. We also introduce several coefficients to balance the optimization weights of the four terms.\n\n**Q8**: For fair comparisons, MAPPO, MAT, and MASER should also include the global state as part of the input. Is that the case in your study?\n\n**A8**: We used the global state for MAPPO and MASER. Due to the problem formulation of MAT, we can't find a place to use global state in MAT. Besides, even if the environments don't provide global state, we can concentrate all agents' observations as the global state, which is the way we used in Overcooked and it can also get good performance.\n\n**Q9**: The number of team skills and individual skills are crucial hyperparameters and should be explicitly stated in the main paper.\n\n**A9**: Due to page limit, we list the number of skills on all scenarios in Table 3 of Appendix F. We will consider putting it in the main paper in our next revision.\n\n**Q10**: The limitation part is not included.\n\n**A10**: HMASD has two main limitations. Firstly, as mentioned in lines 320-321, when the state-observation space is large, HMASD can discover diverse skills but maybe only some of them (about $24$% on SMAC) are useful for the team reward. There are a large percentage of skills are assigned to explore those zero-reward states. Secondly, as mentioned in line 52 of Appendix E, the number of team skills and individual skills should be carefully adjusted. When applying HMASD to a new task, it require to adjust several hyperparameters as shown in Table 3 of Appendix F. Our future work aims to improve these limitations and make HMASD better at solving sparse-reward multi-agent tasks.\n\nFinally, thank you again for your recognition and insightful review to our work. We will incorporate your suggestions into our next revision.  \n\n##### Reference\n\n[1] J. Yang, I, et al. Hierarchical cooperative multi-agent reinforcement learning with skill discovery.\n\n[2] Y. Liu, et al. Heterogeneous skill learning for multi-agent tasks."}]

Author rebuttal:
We have uploaded a one-page PDF containing a new figure that visualizes the learned individual skills on the SMAC scenario 3m.

Meta-review: This paper proposes a hierarchical model for cooperative multi-agent reinforcement learning. The paper presents a novel algorithm that discovers both team and individual skills for solving sparse-reward multi-agent tasks. The reviews generally praise the technical contributions and experimental results, but also point out concerns and weaknesses, such as the complexity of the framework and the need for more clarity and details in certain areas. The authors provide rebuttals that address these concerns. Overall, the reviews suggest the paper to be of moderate-to-high impact, meanwhile there are still minor revisions the author should take care of.
Decision: Accept (poster)