{'fraction_non_alphanumeric': 0.04126055031487627, 'fraction_numerical': 0.009537745956257023, 'mean_word_length': 4.467142857142857, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Multi-agent Deep Covering Option Discovery

The use of options can greatly accelerate exploration in reinforcement learning, especially when only sparse reward signals are available. While option discovery methods have been proposed for individual agents, in multi-agent reinforcement learning settings, discovering collaborative options that can coordinate the behavior of multiple agents and encourage them to visit the under-explored regions of their joint state space has not been considered. In this case, we propose Multi-agent Deep Covering Option Discovery, which constructs the multi-agent options through minimizing the expected cover time of the multiple agents' joint state space. Also, we propose a novel framework to adopt the multi-agent options in the MARL process. In practice, a multi-agent task can usually be divided into some sub-tasks, each of which can be completed by a sub-group of the agents. Therefore, our algorithm framework first leverages an attention mechanism to find collaborative agent sub-groups that would benefit most from coordinated actions. Then, a hierarchical algorithm, namely HA-MSAC, is developed to learn the multi-agent options for each sub-group to complete their sub-tasks first, and then to integrate them through a high-level policy as the solution of the whole task. This hierarchical option construction allows our framework to strike a balance between scalability and effective collaboration among the agents. The evaluation based on multi-agent collaborative tasks shows that the proposed algorithm can effectively capture the agent interactions with the attention mechanism, successfully identify multi-agent options, and significantly outperforms prior works using single-agent options or no options, in terms of both faster exploration and higher task rewards.


I. INTRODUCTION
Option discovery [1] enables temporally-abstract actions to be constructed in the reinforcement learning process. It can greatly improve the performance of reinforcement learning agents by representing actions at different time scales. Among recent developments on the topic, Covering Option Discovery [2] has been shown to be a promising approach. It leverages Laplacian matrix extracted from the state-transition graph induced by the dynamics of the environment. To be specific, the second smallest eigenvalue of the Laplacian matrix, known as the algebraic connectivity of the graph, is considered as a measure of how well-connected the graph is [3]. In this case, it uses the algebraic connectivity as an intrinsic reward to train the option policy, with the goal of connecting the states that are not well-connected, encouraging the agent to explore infrequently-visited regions, and thus minimizing the agent's techniques have been developed to extend the use of covering options to large/infinite state space, e.g., Deep Covering Option Discovery [4]. However, these efforts focus on discovering options for individual agents. Discovering collaborative options that encourage multiple agents to visit the under-explored regions of their joint state space has not been considered.
In this paper, we propose a novel framework -Multi-agent Deep Covering Option Discovery. For multi-agent scenarios, recent works [5], [6], [7] compute options with exploratory behaviors for each individual agent by considering only its own state transitions, and then learn to collaboratively leverage these individual options. However, our proposed framework directly recognize joint options composed of multiple agents' temporally-abstract action sequences to encourage joint exploration. Also, we note that in practical scenarios, multi-agent tasks can often be divided into a series of sub-tasks and each sub-task can be completed by a sub-group of the agents. Thus, our proposed algorithm leverages an attention mechanism [8] in the option discovery process to quantify the strength of agent interactions and find collaborative agent sub-groups. After that, we can train a set of multi-agent options for each sub-group to complete their sub-tasks, and then integrate them through a high-level policy as the solution for completing the whole task. This sub-group partitioning and hierarchical learning structure can effectively construct collaborative options that jointly coordinate the exploration behavior of multiple agents, while keeping the algorithm scalable in practice.
The main contributions of our work are as follows: (1) We extend the deep covering option discovery to a multi-agent scenario, namely Multi-agent Deep Covering Option Discovery, and demonstrate that the use of multi-agent options can further improve the performance of MARL agents compared with single-agent options. (2) We propose to leverage an attention mechanism in the discovery process to enable agents to find peer agents that it should interact closely and form subgroups with. (3) We propose HA-MSAC, a hierarchical MARL algorithm, which integrates the training of intra-option policies (for the option construction) and the high-level policy (for integrating the options). The proposed algorithm, evaluated on MARL collaborative tasks, significantly outperforms prior works in terms of faster exploration and higher task rewards.
The rest of this paper is organized as follows. Section II introduces some related works and highlights the innovation of this paper. Section III presents the background knowledge on option discovery and attention mechanism. Section IV and V explain the proposed approach in detail, including its overall framework, network structure and objective functions to optimize. Section VI describes the simulation setup, and presents the comparisons of our algorithm with two baselines: MARL without option discovery, and MARL with single-agent option discovery. Section VII concludes this paper.

II. RELATED WORK
Option Discovery. The option framework was proposed in [1], which extends the usual notion of actions to include options -closed-loop policies for taking actions over a period of time. Formally, a set of options defined over an MDP constitutes a semi-MDP (SMDP), where the SMDP actions (options) are no longer black boxes, but policies in the base MDP which can be learned in their own right. In literature, lots of option discovery algorithms utilize the task-dependent reward signals generated by the environment, such as [9], [10], [11], [12]. Specifically, they directly define or learn through gradient descent the options that can lead the agent to the rewarding states in the environments, and then utilize these trajectory segments (options) to compose the completed trajectory toward the goal state. However, these methods rely on dense reward signals, which are usually hard to acquire in real-life tasks. Therefore, the authors in [13] proposed an approach to generate options through maximizing an information theoretic objective so that each option can generate diverse behaviors. It learns useful skills/options without reward signals and thus can be applied in environments where only sparse rewards are available.
On the other hand, the work in [14], [2] focused on Covering Option Discovery, a method which is also not based on the task-dependent reward signals but on the Laplacian matrix of the environment's state-transition graph. This method aims at minimizing the agent's expected cover time of the state space with a uniformly random policy. To realize this, it augments the agent's action set with options obtained from the eigenvector associated with the second smallest eigenvalue (algebraic connectivity) of the Laplacian matrix. However, this Laplacian-based framework can only be applied to tabular settings. To mitigate this issue, the authors in [4] proposed Deep Covering Option Discovery to combine covering options with modern representation learning techniques for the eigenfunction estimation, which can be applied in domains with infinite state space. In [4], the authors compared their approach with the one proposed by [13] (mentioned above): both approaches are sample-based and scalable to large-scale state space, but RL agents with deep covering options have better performance on the same benchmarks. Thus, in the evaluation part, we use Deep Covering Option Discovery as one of the baselines.
Note that all the approaches mentioned above are for singleagent scenarios and the goal of this paper is to extend the adoption of deep covering options to multi-agent reinforcement learning.
Options in multi-agent scenarios. As mentioned in Section I, most of the researches about adopting options in MARL tried to define or learn the options for each individual agent first, and then learn the collaborative behaviors among the agents based on their extended action sets -{primitive actions, individual options}. Therefore, the options they use are still single-agent options, and the coordination in the multi-agent system can only be shown/utilized in the option-choosing process while not the option discovery process. We can classify these works by the option discovery methods they used: the algorithms in [15], [16] directly defined the options based on their task without the learning process; the algorithms in [17], [5], [6] learned the options based on the task-related reward signals generated by the environment; the algorithm in [7] trained the options based on a reward function that is a weighted summation of the environment reward and the information theoretic reward term proposed in [13].
In this paper, we propose to construct multi-agent deep covering options using the Laplacian-based framework mentioned above. Also, in an N-agent system, there may be not only N-agent options, but also one-agent options, two-agent options, etc. In this case, we divide the agents into some sub-groups based on their interaction relationship first, which is realized through the attention mechanism [8], and then construct the interaction patterns (multi-agent options) for each sub-group accordingly. Through these improvements, the coordination among agents is considered in the option discovery process, which has the potential to further improve the performance of MARL agents.
Hierarchical Multi-agent Reinforcement Learning. Multiagent reinforcement learning (MARL) methods hold great potential to solve a variety of real-world problems. Specific to the multi-agent cooperative setting (our focus), there are many related works: VDN [18], QMIX [19], QTRAN [20], MAVEN [21] and MSAC [22]. Among them, MSAC introduces the attention mechanism [8] to MARL, which is also what we need.
On the other hand, when adopting options in reinforcement learning, agents need to learn the internal policy of each option (low-level policy) and the policy to choose over the options (high-level policy) in the meantime. Also, the highlevel policy is used to select a new option only when the previous option terminates, so the termination signals should be considered when updating the high-level policy. The updating rules of reinforcement learning with options are talked about in literatures like [23], [24], [12] as the option-critic framework.
In this paper, we try to introduce multi-agent options to MARL, so we extend the option-critic framework to multi-agent scenarios and combine it with MSAC to propose HA-MSAC, a hierarchical multi-agent reinforcement learning algorithm, which will be talked about in Section V.

III. BACKGROUND
Before extending deep covering options to the multi-agent setting, we will introduce the formal definition of the option framework and some key issues of deep covering options. Also, we will introduce the soft-attention mechanism leveraged for sub-group division in this section.

A. Formal Definition of Option
In this paper, we use the term options for the generalization of primitive actions to include temporally-extended courses of actions. As defined in [1], an option ω consists of three components: an intra-option policy π ω : S x A → [0, 1], a termination condition β ω : S → {0, 1}, and an initiation set I ω ⊆ S. An option < I ω , π ω , β ω > is available in state s if and only if s ∈ I ω . If the option ω is taken, actions are selected according to π ω until ω terminates stochastically according to β ω . Therefore, in order to get an option, we need to train/define the intra-option policy, and to define the termination condition and initiation set.

B. Deep Covering Option Discovery
As descried in [4], deep covering options can be constructed through greedily maximizing the state-space graph's algebraic connectivity -the second smallest eigenvalue, so as to minimize the expected cover time of the state space. To realize this, they first compute the eigenfunction f associated with the algebraic connectivity by minimizing G(f ): where H is the set of sampled state-transitions and ρ is the distribution of the states in H. Note that this is a sample-based approach and thus can scale to infinite state-space domains. Then, based on the computed f , they define the termination set as a set of states where the f value is smaller than the k-th percentile of the f values on H. Accordingly, the initiation set is defined as the complement of the termination set. As for the intra-option policy, they train it through maximizing the reward, r(s, a, s ) = f (s) − f (s ), to encourage the agent to explore the states with lower f values, i.e., the less-explored states in the termination set.
In this paper, we will compute f of the joint observation space of each collaborative group of agents, and then learn the multi-agent options based on f , so as to encourage the joint exploration of the agents within the same group and to increase the connectivity of their joint observation space.

C. Soft Attention Mechanism
The soft attention mechanism functions in a manner similar with a differentiable key-value memory model [8], [25], [26]. The soft attention weight of agent i to agent j is defined as Equation (2): where h i = g i (o i ) is the embedding of agent i's input (we take the observation as the input and a neural network defined in Section IV-B as the embedding function), W q transforms h i into a "query" and W k transforms h j into a "key". In this case, the attention weight W i,j S is acquired through comparing the embedding h j with h i with a bilinear mapping (i.e., the querykey system) and passing the similarity value between these two embeddings into a softmax function. Note that the weight matrices for extracting selectors (W q ), keys (W k ) are shared across all agents, which encourages a common embedding space.

IV. ALGORITHM FRAMEWORK AND NETWORK STRUCTURE
In this section, we will introduce Multi-agent Deep Covering Option Discovery and how to adopt it in a MARL setting. First, we will provide the key objective functions of Multiagent Deep Covering Option Discovery and the hierarchical Fig. 1: An agent first decides on which option ω to use according to the high-level policy, and then decides on the action (primitive action) to take based on the corresponding intraoption policy π ω . Primitive option: Typically, we train a RL agent to select among the primitive actions; we view this agent as a special option, whose intra-option policy lasts for only one step. Option 1 ∼ N: Based on the attention mechanism, each agent can figure out which agents to collaborate closely and form a sub-group with, so there are at most N sub-groups (duplicate ones need to be eliminated), and we need to train a multi-agent option for each sub-group. Collect a trajectory τ i by repeating this process until done: choose an available option from Ω according to π 1:N , and then execute the corresponding intraoption policy until it terminates 7: Update B with τ i 8: if i mod N int == 0 and n ω < N ω then 9: Generate a set of multi-agent options Ω using Algorithm 2 based on trajectories in B 10: Update Ω : Ω ← {A} ∪ Ω

14:
Update π 1:N , Q 1:N using HA-MSAC (defined in Sec tion V) based on τ 1:batchsize 15: end for algorithm framework to adopt it in MARL. Then, as an important algorithm module, we will show how to integrate the attention mechanism in the network design and how to adopt it for the sub-group division.

A. Main Framework
In order to take advantage of options in the learning process, we adopt a hierarchical RL framework shown as Algorithm 1. Typically, we train a RL agent to select among the primitive actions, aiming to maximize the accumulated reward. In our algorithm framework, we view this agent as a one-step option -primitive option. As shown in Figure 1, when getting a new observation, the hierarchical RL agent first decides on which option ω to use according to the high-level policy, and then decides on the action (primitive action) to take based on the corresponding intra-option policy π ω . In this hierarchical framework, there are two kinds of policy: the high-level policy for selecting among the options, and the low-level (intra-option) policy for selecting among the primitive actions. In this paper, we adopt multi-agent soft actor-critic (MSAC) [22], a typical MARL algorithm, to train the intra-option policy. However, the high-level policy is not executed step by step -as mentioned in Section III-B, once an option is taken, the actions will be selected according to π ω until the option terminates, so we do not decide on a new option with the high-level policy until the previous option terminates. In this case, we propose HA-MSAC, a hierarchical MARL algorithm based on soft actorcritic, for training the high-level policy, which is introduced in Section V.
Except for the primitive option, other options are extracted from transitions collected in the training process, so at first there is only the primitive option A in the option set Ω for selecting (Line 2 in Algorithm 1). Shown as Line 8-12 in Algorithm 1, every time when we get the set of new options Ω (at most for N ω times), we merge it with {A} to update Ω (Line 10 in Algorithm 1). To construct the options, we extend Algorithm 1 of [4] and Equation (1) from a single-agent scenario to a multi-agent scenario to obtain our Algorithm 2 and Equation (3) (as described in Algorithm 2, o G : the joint observation of sub-group G, T G : the joint observation transitions of sub-group G). Through this extension, collaboration among the agents is considered not only at a high level, but also in the option discovery process, which can further improve the performance in scenarios where close collaboration is required.
As described in Algorithm 2, the reward function for learning the intra-option policy is based on f G which represents the connectivity of the joint observation space and is task-independent. Through this intrinsic reward term, agents are encouraged to visit the under-explored regions of their joint observation space. Further, inspired by [7], we can take advantage of the extrinsic reward that is specific to the environment to guarantee that the skills/options learned are also useful for team performance, so the reward at step t for learning the intra-option policy can be defined as: Create an empty set of options Ω 4: Divide the N agents into sub-groups using Algorithm 3 5: for every sub-group G do 6: Define the agents in G as {g 1 , ..., g sizeof (G) }

7:
Extract the set of transitions for G from T as Learn the connectivity function of G's joint observation space f G by minimizing L(f G ) (Equation (3)) 9: Define β as the k-th percentile value of f G in T G

10:
Acquire the termination condition of option ω G : Acquire the initiation set of option ω G :

12:
Learn the policy π G of option ω G by maximizing the accumulated reward defined as Equation (4) using MSAC based on T G

13:
Add option ω G : < I G , π G , β G > to Ω 14: end for 15: Return Ω where (r i t ) env is task-related, η is the weight for the intrinsic term, and G i is the sub-group that agent i belongs to.

B. Network Structure
In real-life multi-agent systems, the agents can usually be divided into some sub-groups and each sub-group is responsible for a sub-task (option). Therefore, before discovering multiagent options, we first adopt the widely-used soft attention mechanism [8] to quantify the interaction among the agents from which we can abstract the sub-groups. Through this division, we can also avoid the joint observation space growing too large, so as to learn the multi-agent options more efficiently. Next, we introduce how to integrate the attention mechanism in the network design.
The network structure of the high/low-level policy is shown in Figure 2(a). When deciding on which multi-agent option is available or to execute, agent i needs to know other agents' observations (joint observation) to see whether they have reached the initiation set, so the communication among the agents is required. Further, we view this multi-agent system as a fully-connected directional graph, where each node represents an agent and the weight of edge i → j represents the importance of agent j to agent i. These weights can be learnt through a soft attention mechanism (i.e., a query-key system). After that, we adopt GNN (e.g., weighted summation) to extract x i , the contribution from other agents to agent i, and then concatenate it with its own observation embedding h i as the input of its own policy head π i . In this way, π i is based on Insert i to its sub-group G i 9: for each agent j = i do 10:  16: Return G observations of all the agents, and the attention mechanism can filter out observations from the agents that have no/low interaction with agent i for better decision-making.
The Q-function network of the high/low-level policy is shown in Figure 2(b). We only use the observations o 1:N to extract the interaction relationship rather than the observation-option/action pairs (o, ω) 1:N (like in [28], [22]), because: (1) the interaction relationship extracted by the policy and Q-function network should be the same, since it's for the same multi-agent task with the same group of agents; (2) parameters of the attention mechanism can be shared between the two networks, which can improve the training efficiency. Also, note that the parameters of the soft attention and GNN part: W k , W q , W v , W ω v are shared by all the agents to encourage a common embedding space.
The attention module in the intra-option policy of the primitive option (defined in Section IV-A) is used for the subgroup division. As shown in Algorithm 3, we use the transitions collected in the training process as input and calculate the accumulated soft attention weight matrix based on the output of the attention layer. Then, we compare the normalized attention weights with a predefined threshold z to finalize the sub-group for each agent. In our experiment, the threshold z is set as 1/(N −1), where N is the number of the agents in the learning system. The intuition is that the attention for the agents within the same sub-group should be higher than the average level. The threshold can also be fine-tuned as a hyperparameter. For example, a higher threshold z may be required for the more closely collaborative tasks.

V. HIERARCHICAL ATTENTIVE MULTI-AGENT SOFT ACTOR-CRITIC (HA-MSAC)
In this section, we extend MSAC [22], a widely-used MARL algorithm with attentive critics, to a hierarchical multi-agent reinforcement learning algorithm with attentive actors and critics, which we name as HA-MSAC. This algorithm can Fig. 3: Single-agent Scenario: The agent chooses the option ω 1 at s 1 (init ω1 (s 1 ) == 1), then the corresponding intra-option policy π ω1 is executed until s 4 (β ω1 (s 4 ) == 1). Meanwhile, a new option ω 4 is chosen at s 4 (init ω4 (s 4 ) == 1). Note that the high-level policy is not executed at state s until the previous option ω ends at this step (β ω (s) == 1) and a new option is required. be used to update the high-level policy and corresponding Q-function network in an off-policy manner.

A. Extension with Attention Modules
In MSAC, they extended soft actor-critic (SAC) [29] to a multi-agent scenario with attentive critics, and define the objective functions for training the policy and Q-function network of agent i as follows: (o = (o 1 , ..., o N ), a = (a 1 , ..., a N )) where B represents the replay buffer, θ and φ are the parameters of the target policy and Q-function network, αlog(π θ ) is the entropy term. b is the baseline term of the advantage function, and in the case of discrete policies, it can be calculated explicitly (Equation (8)). However, we have to estimate the expectation in Equation (6) and (7) through sampling. For example, in Equation (6), we can't enumerate all the possible joint actions a , so we calculate a i ∼ π θi (o i ), f or i = 1 to N , and then obtain the sampled joint action a . In our setting, besides the attentive critics, we also use attentive actors (shown as Figure 2(a)), which means that each agent's policy takes the observations of all the agents as input, so we modify the calculation of y i , ∇ θ J(π θ ), and b(o, a \i ) as follows: Note that when estimating the expectation in Equation (9) and (10), we don't need any extra sampling process as compared with Equation (6) and (7).

B. Extension with Hierarchical MARL
As mentioned in Section IV-A, the high-level policy is adopted to select among the options. Once an option is chosen by the high-level policy, the corresponding intra-option policy will be executed until its termination condition is satisfied. For example, in Figure 3, the agent chooses the option ω 1 at s 1 (init ω1 (s 1 ) == 1), then the intra-option policy π ω1 is executed until s 4 (β ω1 (s 4 ) == 1). Therefore, the execution of the highlevel policy is not step-by-step but option-by-option and each option can last for steps, which is different from typical RL defined on the MDP. Next, we describe the objective functions for learning with options. As a reminder, we first transfer the option-critic framework [5] to SAC, and then extend it from the single-agent scenario to the multi-agent scenario.
Firstly, as shown in Figure 3, during the sampling process,we can collect transitions like (s t , ω t , init ωt t , a t , r t , s t+1 , β ωt t+1 ), where ω t is the option choice at step t, init ωt and β ωt are the corresponding initiation and termination signal. Based on them, we can define the objective functions for the single-agent scenario as follows: Intuitively, if ω t terminates at s t+1 (β ωt t+1 == 1), the agent will choose a new option based on the target high-level policy π θ ; otherwise, it will still execute ω t (i.e., ω t+1 == ω t ).
While, the objective function for updating the policy network is given as: The intuition behind this equation is that init t marks the steps where the high-level policy π θ is executed (init t == 1) and thus the computed gradient is effective for update.
Secondly, as shown in Figure 4, when extended to the multi-agent scenario (with N agents), we can collect the transitions like: Note that the option choice among the agents maybe asynchronous and this brings new difficulty. For example, in Figure  4, agent 2 starts a new option at step 3, while agent 1 is still within ω 1 1 , so we cannot update the two agents' high-level policy at the same time. Instead, the update should be based on the termination or initiation signal specific to each agent. Thus, we define its objective functions as follows: Fig. 5: Task Scenario for Evaluation: There are in total four "agents". Two (or more) "agents" need to touch the "switch" at the same time to turn on the "switch" first, and then two (or more) "agents" need to push the "box" in the same direction at the same time to move it through the "lock" and reach the "target" location.
When estimating the expectation in Equation (16), we need to sample the joint option ω t+1 , which is generated in this way - The intuition is that, for agent i, the new option is not required to be sampled until its previous option terminates (β ω i t t+1 == 1). While, the objective function for updating the policy network is given as: where the expectation in Equation (18) is calculated in the same way as Equation (11), while the expectation in Equation (17) is estimated by samplingω t -for i = 1 to N : if init i t == 1, The intuition behind this that we need to use init i t to mask out the steps where the high-level policy π θi is not executed (init i t == 0). To sum up, the objective functions of HA-MSAC are listed as Equation (15)- (18).

VI. EVALUATION
Generally, a complex multi-agent task can be divided into some sub-tasks and each sub-task can be completed by a subgroup of the agents, and meanwhile, the sub-groups need to coordinate with each other very well to get the whole task done. In our algorithm, under a hierarchical MARL framework, we There are four agents -agent 0 and 1 need to collaborate with each other to turn on the switch first, then agent 2 and 3 need to work together to push the box to the target. Since collaboration is required for each sub-task, the agents without options or with single-agent options cannot complete the whole task very well, especially for pushing the box, as compared with the agents with multi-agent options. Note that there are two sub-groups (i.e., [0, 1] and [2,3]), and a multi-agent option is trained for each sub-group to complete its sub-task at step 5000.
learn the optimal grouping through the attention mechanism, learn the sub-skill (option) of each sub-group through the multi-agent option discovery and learn the coordination among the sub-groups through the high-level policy learning. In this section, we will test the effectiveness of our algorithm on a self-designed simulator which is an extension of the commonlyused benchmark -Push-Box [30].

A. Simulator Setup
As shown in Figure 5, there are four agents in the environment and their task is to push the box to the target. During this process, they have to pass through a wall with a lock which is controlled by a switch, so they have to turn on the switch first to open the gate connecting the two rooms, and then push the box to the target. Note that only when two or more agents touch the switch at the same time will the switch open, and the box would not move until two or more agents push it in the same direction at the same time. In this case, the whole task can be divided into two sub-tasks, and coordination among the agents is required for each sub-task.
We compare our algorithm with two baselines: (1) a SOTA multi-agent reinforcement learning algorithm with attention mechanism but without option discovery -MSAC [22]; (2) a SOTA hierarchical multi-agent reinforcement learning algorithm with single-agent option discovery -Deep Covering Option Discovery [4].
The evaluation is based on the three sub-settings: (1) In this sub-setting, we simplify the task scenario to a two-agent version: agent 0 is able to turn on the switch, agent 1 is able to push the box, and both sub-tasks require only one agent. We will test the two baseline algorithms on this sub-setting and show the effectiveness of the single-agent option discovery method on a relatively simple task. (2) Only two of the agents (agent 0 and 1) are able to turn on the switch and the other two agents (agent 2 and 3) are able to push the box. We will see whether the grouping (group 0: agent 0 and 1, group 1: agent 2 and 3) can be found through the attention mechanism, and whether the sub-tasks (i.e., group 0: turning on the switch, group 1: pushing the box to the target) can be learned through our algorithm. (3) We only have three agents in this sub-setting:  [1,2]) can avoid this, since the adoption of the multi-agent option for the sub-group [1,2] can encourage the exploration of the joint state space of agent 1 and 2.
agent 0 is only able to turn on the switch, agent 2 is only able to push the box, while agent 1 can do both. In this case, agent 1 should first group with agent 0 to turn on the switch and then group with agent 2 to push the box to the target. For agent 1, the grouping is dynamic, which brings more challenges to this sub-setting. Each agent takes its two-dimensional position (continuous) as the observation and chooses to execute one of the primitive actions in {Up, Down, Left, Right, Stay} or the available options. Further, the reward function for each agent is defined as: where c 0:3 > 0 are the weights for each term, e i move represents whether the box is moved for one step by agent i, e i switch represents whether the switch is turned on by agent i, and e target represents whether the box is pushed to the target area successfully (this term is shared by all the agents). Besides, the whole task is required to be completed within 400 steps, and a negative term −c 0 is used to encourage the agents to complete the whole task as soon as possible. Note that this reward setting is very sparse, since only when an event with low probability (e.g., reaching the target) occurs, can the agents get the corresponding reward term. Thus, highlyefficient exploration strategy is required. Baseline (1) is a SOTA MARL algorithm, but it fails in all the three sub-settings in our evaluation task (shown in Section VI-B), which shows that the evaluation scenarios are quite challenging.

B. Results and Discussion
In this section, we compare MARL with no options (baseline (1)), single-agent options (baseline (2)), and multi-agent options (our algorithm) on the three sub-settings introduced above.
In the sub-setting 1, there are only two agents and each of them is responsible for a different task, i.e., agent 0: turning on the switch, agent 1: pushing the box to the target. Figure  6(a)-6(b) plot the reward function of agent 0 and 1 in the training process. It can be observed that the agent without options can learn how to turn on the switch and get the corresponding reward term, however, it cannot learn to complete the harder task -pushing the box to the target, due to the fact that the reward function is sparse. Then, we train a singleagent option for each agent at step 2000 with the transitions collected in the first 2000 steps, after which we start to train the high-level policy and low-level policy together within a hierarchical MARL framework introduced in Section IV-A. The performance starts to improve at step 2000, which shows the effectiveness of MARL with the single-agent options. Agent 1 learns its sub-task through a denser reward function (Equation (4)), and also agent 0 and 1 learns how to cooperate with each other (turn on the switch first and then push the box through the gate to the target) through the training of the high-level policy.
In the sub-setting 2, agent 0 and 1 need to touch the switch at the same time to turn it on, and agent 2 and 3 need to push the box in the same direction to make it move, so collaboration is required for each sub-task, which is different from the subsetting 1. Figure 7(a)-7(b) show that the agent without options or with four single-agent options (one for each agent) can learn to open the switch, while it cannot learn how to push the box to the target very well. Then, based on the transitions collected in the first 5000 steps, we can get the attention weight distribution of the agents. As shown in Figure 8(a), the attention weight that agent 0 pays to agent 1 is higher than the threshold 0.33 (≈ 1/(4 − 1), as described Section IV-B) and vice versa, so we can get a sub-group: [0, 1]; similarly, we can get the other sub-group: [2,3]. Then, we can train the multi-agent option for each sub-group to complete its corresponding sub-task, and integrate the options in the whole learning process as shown in Algorithm 1. Results show that the agent with multiagent options performs significantly better, since it considers the collaboration among the agents in the option discovery process. While, the agent with single-agent options does not consider that, so it can do well in the sub-setting 1 but not this sub-setting.
Different from the sub-setting 2, in the sub-setting 3, agent 1 should cooperate with agent 0 first to open the switch, and then push the box to the target area together with agent 2, which makes the task even more challenging. Results in Figure 9 show that agent 1 without options or with single-agent options (grouping: [0], [1], [2]) tend to be stuck by the local optimum, after it completes the easier task -opening the switch. While, agent 1 with multi-agent options can avoid this. The agents are divided into two sub-groups: [0, 1] and [1,2] based on the attention weight distribution shown as Figure 8(b) with Algorithm 3 (z is set as 0.5 = 1/(3 − 1)). The adoption of the multi-agent option for group [1,2] can encourage the exploration of the joint state space of agent 1 and 2, and thus improve their overall performance. Note that the grouping and multi-agent option discovery are based on the transitions collected in the first 5000 steps, and the performance of agents with multi-agent options starts to improve after that.

VII. CONCLUSION
This paper proposes Multi-agent Deep Covering Option Discovery and a hierarchical multi-agent reinforcement learning algorithm based on soft actor-critic to integrate the options in a MARL setting -HA-MSAC. This approach first divides all the agents into some sub-groups through the widely-used attention mechanism based on their interaction relationships, and then learns the multi-agent options for each sub-group to encourage the joint exploration of the multiple agents in a sub-group. Evaluation results show effective sub-group division through the attention mechanism, and superior performance of the MARL agents with multi-agent options as compared to the ones with single-agent options or no options.
As a direction for future research, better algorithms for the sub-group division may be considered for more complicated collaborative tasks. Also, in this paper, the multi-agent option discovery is based on the joint observation space of the agents within a sub-group. If the size of a sub-group is large, its joint observation space can still be huge. Therefore, how to discover the multi-agent options based on the partial observation space of each individual agent is also an important future direction.