Scalable Multi-agent Covering Option Discovery based on Kronecker Graphs
Authors: Jiayu Chen
Jingdi Chen
Tian Lan
Vaneet Aggarwal
Venue: NeurIPS 2022 Accept (2022)
Keywords: Multi-agent Reinforcement Learning
Option Discovery
Kronecker Product

Abstract: Covering option discovery has been developed to improve the exploration of RL in single-agent scenarios with sparse reward signals, through connecting the most distant states in the embedding space provided by the Fiedler vector of the state transition graph. Given that joint state space grows exponentially with the number of agents in multi-agent systems, existing researches still relying on single-agent option discovery either become prohibitive or fail to directly discover joint options that improve the connectivity of the joint state space. In this paper, we show how to directly compute multi-agent options with collaborative exploratory behaviors while still enjoying the ease of decomposition. Our key idea is to approximate the joint state space as a Kronecker graph, based on which we can directly estimate its Fiedler vector using the Laplacian spectrum of individual agents' transition graphs. Further, considering that directly computing the Laplacian spectrum is intractable for tasks with infinite-scale state spaces, we further propose a deep learning extension of our method by estimating eigenfunctions through NN-based representation learning techniques. The evaluation on multi-agent tasks built with simulators like Mujoco, shows that the proposed algorithm can successfully identify multi-agent options, and significantly outperforms the state-of-the-art. Codes are available at: https://github.itap.purdue.edu/Clan-labs/Scalable_MAOD_via_KP.

Scalable Multi-agent Covering Option Discovery based on Kronecker Graphs
Jiayu Chen Purdue University West Lafayette, IN 47907 chen3686@purdue. edu
Jingdi Chen
The George Washington University Washington, DC 20052 j jingdic@guu.ed
Tian Lan
Vaneet Aggarwal
The George Washington University Washington, DC 20052
Purdue University West Lafayette, IN 47907 vaneet@purdue edu
tlan@gwu. edu
Abstract
Covering option discovery has been developed to improve the exploration of RL in single-agent scenarios with sparse reward signals, through connecting the most distant states in the embedding space provided by the Fiedler vector of the state transition graph. Given that joint state space grows exponentially with the number agents in multi-agent systems, existing researches still relying on single-agent option discovery either become prohibitive or fail to directly discover joint options that improve the connectivity of the joint state space. In this paper, we show how directly compute multi-agent options with collaborative exploratory behaviors while still enjoying the ease of decomposition. Our key idea is to approximate the joint state space Kronecker graph, based which we can directly estimate its Fiedler vector using the Laplacian spectrum of individual agents' transition graphs. Further, considering that directly computing the Laplacian spectrum is intractable for tasks with infinite-scale state spaces, we further propose a deep learning extension of our method by estimating eigenfunctions through NN-based representation learning techniques. The evaluation on multi-agent tasks built with simulators like Mujoco, shows that the proposed algorithm successfully identify multi-agent options, and significantly outperforms the state-of-the-art Codes are available at: https://github.iie wwwpppuuuudeeec wttpeeeee//aaaaaaaaalalllee MatiecaaaaaaaeMMMMMMMM.. MAOD_ LiDD_via___ KP
Introduction
Option discovery [1] enables temporally-abstee abbttrat actions to be constructed and utilized in RL, which can significantly improve the performance of RL agents. Among recent developments, Covering Option Discovery 2 has been shown to be effective approach to improve the exploration in environments with sparse reward signals. In particular, it first computes the second smallest eigenvalue X2 and the corresponding eigenvector F (i.e., Fiedler vector (4) of the Laplacian matrix extracted from the state transition process in RL. Then, options are built to connect the states corresponding the minimum maximum in F. which greedily improves the algebraic connectivity of the state space [5] and accelerate exploration within it. In this paper, we consider constructing and utilizing covering options in MARL. Due the exponentially-large a commonly-adoptee way to solve this problem 66-9 to construct individual options as in single-agent environment first, and then learn to collectively leverage these individual options to
state space in multi-agent scenarios,
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

tackle multi- agent tasks. This method fails to consider the coordination among agents in the option discovery process, and thus can suffer from poor behavior in multi-agent collaborative tasks.
To this end, we propose a framework that makes novel use of Kronecker graphs to directly construct multi-agent options and adopt them to accelerate the joint exploration of agents in MARL.. In particular, the joint state space is approximated as the Kronecker product of the state spaces of individual agents. Then, based on the theorem we propose, we can directly estimate the Fiedler vector of the joint state space using the Laplacian spectrum of individual ones. Next, the joint options can be constructed to explore the joint states corresponding to the minimum or maximum in the Fiedler vector, resulting in greedy improvement of the joint state space's 's connectivity. However, calculating the Laplacian spectrum can be expensive a matrix base. As a scalable extension, we leverage a deep neural network approximation to learn the Laplacian spectrum so that our method can be adopted to tasks with infinite-scale state spaces. Our main contributions are: (1) We propose Multi-agent decentralized manner to discover multi-agent options which can greatly aid the joint exploration of agents in MARL. (2) We propose that multi-agent options can be adopted to MARL in either decentralized or centralized manner, which means that agents can either jointly decide on their options, or choose their options independently and select different options to execute simultaneously. (3) We scale Multi-agent Covering Option Discovery to infinite-scale state spaces using SOTA representation learning techniques, and propose that the discovered options can be adopted with deep MARL methods for continuous tasks. (4) We empirically show that agents using our multi-agent options significantly outperform agents with single-agent options or no options.
Covering Option Discovery
2 Related Work
The option framework was proposed in M. which extends the usual notion of actions to include options - the closed-loop policies for taking actions over a period of time. A lot of option discovery algorithms have been proposed. Some of them are based on task-related reward signals [3 Specifically, they directly define or learn the options through gradient descent that can lead the agent to the rewarding states, and then utilize these trajectory segments (options) to compose the completed trajectory toward the goal state. These methods rely on dense reward signals, which are hard to acquire in real-life tasks. Other works define the sub-goal states (termination states of the options) based on the visitation frequency of the states. For example, in [14166, they discover the options by recognizing the bottleneck states in the environment, through which the agent can transfer between the sub-arcas that are loosely connected in the state space, and they define these options as betweenness options. Recently, there are some otate-of-the--e option generation methods based on the Laplacian spectrum of the state-transition graph, such 22 17H19), since the cigenvectors of the Laplacian of the state space can provide embeddings in diwer-dimensionl space, based which we can obtain good measurements of the accessibility from one state to another. Especially, in B 19), they propose covering options and prove that their option generation method has higher exploration speed and better performance compared with the previous option discovery methods. Note that all the approaches mentioned above are for single-agent scenarios, we will extend the construction and adoption of covering options MARL in this paper.
Option Discovery:
Adopting options in multi-agent scenarios: Most of the researches on adopting options in MARL 66 20 21] try to first learn the options for each agent with the option discovery methods mentioned above, and then Iearn to collaboratively utilize these individual options. Therefore, the options they use are still single-agent options, and the coordination among agents can not be utilized in the option discovery process. In this paper, we propose directly constructing multi-agent covering options of the joint state transition graphs based on Laplacian spectrum of the individual ones, and explore how to utilize the multi-agent options in MARL tasks effectively. Further, to scale our algorithm, we extend a tabular algorithm considered in (22), adopt SOTA representation learning techniques to obtain the Laplacian spectrum for option discovery, and integrate the discovered options with deep MARL algorithms, to aid the learning performance in scenarios with infinite-scale state spaces, which is testified on multiple complex Grid and Mujoco tasks.
3 Background
Kronecker Product of Graphs: Let = (Va,: FG,) and G2 = (Vo,: F.g,)) be two state transition graphs (defined in Appendix B), corresponding to the individual state space Sj and Sy. The Kronecker
2

---

(.1
(,33
(2.4)
(1.1)
(,33
(2,4)
(2.1)
(144)
(2.1)
(144)
(a) Joint state transition graph of agent 1 and 2
(b) Joint state transition graph with individual options
Figure I: An illustrative example: limitations of utilizing single-agent options alone for MARL.
product of them denoted by G1 @ G2 is a graph defined on the set of vertices VG, x VG such that [23]: Two vertices of G1 @ G2, namely (g. h) and (g', hi),, are adjacent if and only if and g' are adjacent in G1 and h and h' are adjacent in G2. Thus, the Kronecker graph can capture the joint transitions of agents in their joint state space very well. Section 4.2 we propose to use the Kronecker graph as an effective approximation of the joint state transition graph, so that we can discover the joint options based on the factor graphs. Further, Ai @ A is an |S x |S SSa] matrix with elements defined by (Ai @ A2) and A2 are the adjacency matrices of G1 and G2, A1 () is the element lies on the i-th row and j-th column of A1 (indexed from 1).
Ai (i, 1) with Equation ① where A
I = (i 1) x |& + k, J (j - 1) x S2 +
(1)
Covering Option Discovery: As defined in M. an option w consists of three components: an intra- option policy T. S A [0, 1]. termination condition 3_, S - {0, 1). and an initiation set I S S. An option < Iu Ruo. S., > is available in state s if and only if s E Iu- If the option w is taken, actions are selected according to T., until w terminates stochastically according to Bw (i.c., 3w 1). Recently, the authors of B3 proposed Covering Option Discovery discovering options by minimizing the upper bound of the expected cover time of the state space. First, they compute the Fiedler vector F of the Laplacian matrix of the state transition graph. Then, they collect the states 8; and 8, with the largest (E, - 32 (F; is the i-th element in F), based on which they construct two symmetric options: way =< way { Tany: 1 Bung { >, W/i < Luy {8y}, Tuys Auge = (s,) > to connect these two subgoal states, where Twi, is defined as the optimal path from 8 to 8z-
The intuition of this method as follows. The authors of [5] prove that (F, - FF) gives the first order approximation of the increase in (L) (i.e., algebraic connectivity) by connecting (s;, sy), and propose a greedy heuristic to improve the algebraic connectivity of a graph: adding a certain number of edges one at a time, and each time connecting (s;, 55) corresponding to the largest (F; - F3)². Further, [3], they prove that the larger the algebraic connectivity is, the smaller the upper bound of the expected cover time would be and the easier the exploration tends to be. Therefore, applying this greedy heuristic to the state transition graph can effectively improve the exploration in the state space.
Proposed Algorithm
4.1 System Model
In this paper, we consider to compute covering options in multi-agent scenarios, with n being the number of agents,, = S₁ x S₂ .... x S,, being the set of joint states, A = Ai X A2 X ... X A,, being the set of joint actions, S; and A, being the individual state space and action space of agent i. The size of the joint state space grows exponentially with the number of agents. Thus, it is prohibitive to directly compute the covering options based on the joint state transition graph using the approach introduced in Section 3 for large n.
A natural method to tackle this problem is to compute the options for each agent by considering only its own state transitions, and then learn to collaboratively leverage these individual options. However, it fails to directly recognize joint options composed of multiple agents' temporal action sequences for encouraging the joint exploration of all the agents. The algebraic connectivity of the joint state space may not be improved with these single-agent options. We illustrate this with simple example.
Illustrative example: Figure ((a) shows joint state transition graph G of two agents, where
S = 21 and S. = (1, 2, 3, 4). In order to compute the individual options, we can restrict our attention to the state transition graph of each agent, namely G₁ and Gz. The Fiedler vectors (not
3

---

(L.)
(244)
(a) Joint state transition graph updated with option wi (b) Joint state transition graph updated with option we
Figure 2: The joint state transition graph updated with the detected multi-agent options
111-11--20 -111,,, 1. Then, according the option discovery approach described in Section we can get the individual options for agent 1 to connect its state (minimum) and state 2 (maximum), and individual options for agent 2 to connect its state I and state 4. With these options, the updated joint state space is Figure [(b) The straightforward decomposition of option discovery for MARL fails to create a connected graph. Thus, utilizing single-agen agent options alone may not be sufficient for efficient exploration.
normalized) of 1₁ and G2 are: = [-1, --1
Therefore, we propose to build Multi-agent Covering Options to enhance the connectivity of the joint state space. We can represent it as tuple: < Iw Tw. Bw >, where L. C Š is the set of initiation joint states, 3. S - (0, }} indicates the joint states to terminate,
= (x w ) S, A, + (0, 1)), the joint intra-option policy that can lead the agents from the initiation states to the termination states. The key challenge is to calculate the Fiedler vector of the joint state space according which
define In Tw. S. >. Given that SS] grows exponentially with propose to estimate the joint Fiedler vector based on the individual state spaces in the next section.
4.2 Theory results
We propose to use the Kronecker graph to decompose the calculation of the joint Fielder vector to single-agent state spaces, because: (1) the Kronecker product of individual state transition graphs
@ G. = G1 @ @ Gn provides good approximation of the joint state transition graph G; (2) The Fielder vector of _ G; can be estimated with its factor graphs Gi =
n2)
The use of @ G2 as factorized approximation of G introduces noise, since G = @"= G2 becomes exact only in the case where agents' transitions are not influenced by the others. However, for the purpose of option discovery, we only need to identify areas in the state space with relatively low or high values in the Fielder vector, so exact calculation of G and its Fiedler vector is not necessary. Moreover, the state transition influence among agents, e.g., collisions and blocking, would most likely result in local perturbations of the transition graph and thus is inconsequential global properties of G (e.g., the algebraic connectivity), especially for large-scale state spaces. Therefore, approximating G by G allows efficient option discovery. We empirically show in Figure 8 that superior exploration can still be achieved under such approximation noise, even if the transition influence is heavy (affecting 63% of the episode length), numerically validating the robustness of our proposed approach to the approximation error. We further provide a quantitative study on the approximation error in Appendix E.4 Next, we show how to effectively approximate the Fiedler vector of @ G based on the Laplacian spectrum of the factor graphs, to achieve an effective decomposition. Inspired by (24] that proposed an estimation the Laplacian spectrum of the Kronecker product two factor graphs, prove Theorem 4.1 for arbitrary number of factor graphs
Theorem 4.1. For graph G = 18/-110 Gi, we can approximate the eigenvalues and eigenvectors v of its Laplacian L, by:
II
Pk.....k
x
Uky.......
1
Gr are the kę-th smallest eigenvalue and corresponding eigenvector of Ca, (normal- where Xe and Uyg ized Laplaciann of Gt), dG: is the kitth smallest diagonal entry of Do, (degree matrix of G:).
The proof of Theorem can collect the cigenvalues and corresponding eigenvectors of G by Equation (2). Then, the
provided in Appendix A Through enumerating (ki,... ,,,), we

---

eigenvector "y.... & corresponding to the second smallest eigenvalue Mk,,.. &.. is the estimated joint Fiedler vector Fe. We can define the joint states corresponding to the maximum minimum in Få as the initiation or termination joint states, As discussed in Section [3] connecting these two joint states with options can greedily improve the algebraic connectivity of the joint state space.
Illustrative example: Now we reconsider Figure [(a) where द = G1 @ G2. We approximate Fg using Theorem 4.1 and get two approximations (details are Appendix C
T
1
1 v2
1
1
011
1, 1, V2 Lv2
2
1,
1,
U24
1, 11
v2 V2
1,
1,
v2
(3)
Based on them and the indexing relationship between G and its factor graphs (Equation 11. we can get two sets of multi-agent options: =(1,2) (1,3), (2.2), (2.3)), ((1,), (1,4), (2,1), (2.4))} and the maximum or minimum as the initiation or termination states respectively. For example, in V11 the 7-th element (indexed from 1) is maximum, so the 7-th joint state is in Lw, and denoted as (2,3) (Equation T.. As shown in Figure 2 both of the two options can lead to a connected graph. Thus, the adoption of multi-agent options has the potential to encourage efficient exploration in the joint state space. Next, we will formalize our algorithm.
(2,3)), =,,,3, (2.2))), where we set the joint states corresponding to
4.3 Scalable Multi-agent Covering Option Discovery
In this section, we first introduce how to construct multi-agent options based individual state transition graphs of each agent (represented as adjacency matrices A1m). of which the detailed pseudo codes are in Appendix D Then, we propose scalable extension of our algorithm infinite-scale state space, by which we don't I need to explicitly construct the state transition graph or compute its Laplacian spectrum through eigendecomposition.
First, we need to calculate the estimation of Fg through Theorem 4.1 based on Alm- and collect the joint states corresponding to the minimum or maximum in F3 as the lists of subgoals MIN and MAX. Then, we split each joint state into a list of individual states. For example, we convert (Smin; Smaz) into (()) the joint state space by connecting each (8 S mmax) in the corresponding individual space. After decentralizing the joint states, we can define the multi-agent options as follows: (I) For each option w. we define Lu as the explored joint states, and B. as a joint state in MIN U M AX or the unexplored area. Option w is available in state s if and only if s E Iw- Therefore, instead of constructing a point option between (Smin: Smaz). e.g., setting {Smin I as Ia and {Smaz] | as B... we extend I_ to the known area to increase the accessibility of w. (2) As for the intra-option policy Tw used for connecting the initiation and termination joint state, we divide it into list of single-agent policies Th (i , n), where x can be trained with any single-agent RL algorithm aiming at leading agent i from its own initiation state to the termination state s (6mma)) To sum up, the proposed algorithm first discovers the joint states that need to be explored most, then projects each abb- into individual state spaces and train the policy for each agent to visit the projection.
>min), (siggs
mma))) )) that can connect (8min, 8max) in
Here is the computational complexity analysis: Consider an MDP with n agents and m states for each agent. To compute the Fiedler vector, which is the computation bottleneck of the algorithm, directly from the joint state transition graph would require time complexity O(m3*), since there are m" joint states and the time complexity of eigenvalue decomposition is cubic with the number of joint states. While, with our approach, we can decompose the original problem into computing eigenve of the individual state transition graphs, of which the overall time complexity is O(m²)). Thus, our solution significantly reduces the problem complexity from O(m²") ) to O (nm3). As for problems with large state space (i.e., m is large), our option discovery approach could be directly integrated with sample-based based techniques for eigenfunction estimation 25 26), which makes it scalablee
Extension to tasks with infinite-scale state space. According to (26) the A smallest eigenvalues Assk and corresponding eigenvectors Ui.h of the normalized Laplacian L can be estimated by:
k min Σ (k- 1)o7 Lus, s.l. of vy = 6,5, V i = 1, 1k.
(4)
For the large-scale state space, the eigenvectors can be represented as neural network that takes a state as input and outputs k-dimension vector [s), ... f& (s)) as an estimation of [e1 (s). (.)))))))))))))
5

---

Accordingly, the objective in Equation 4 can be expressed as: (please refer to (26] for details)
G(fi.... fk)
2 E (-.
Σ ( (c()))
where T is set of transssranssso collected by interacting with the environment randomly. Further, the orthonormal constraints in Equation (4) is implemented as a penalty term:
k
P(fi,'" .. fkk ;kk -
ΣΣΣ (s(()) -6,)0 - 6.z) 1=1 1=1 5=1
(6)
where 3 is the weight term and p is the distribution states T. To sum up, the eigenfunctions can be trained as NN by minimizing the loss function: L(fi, fu) G(fi.'. fu) P(fi.... fk).
After getting estimation of Ui:k. we can estimate the corresponding eigenvalues A1.k by:
1
=; of Ce; - 2 " [(f((s) fi(s))) i= i 1,...,
(7)
As for the degree d of each state in the individual state transition graph, we can obtain them through f1 which is the eigenvector corresponding to the smallest eigenvalue of L and satisfies (51)) / vd(s2) [27]. Therefore, we can collect the k-smallest eigenvalues and corresponding eigenvectors, and the degree list for each agent, after which we can utilize Theorem 4. to estimate the joint Fielder vector. Note that since we only care about the second smallest eigenvalue, we don't it need to enumerate all the eigenvalues of the factor graphs, and we only need to know the relative value of the degrees. After getting the joint Fiedler vector, we define the subgoal joint states .mamn) }) as the termination set,
corresponding to the minimum or maximum (e.g., Smin=(smin and the other joint states as the initiation set. As for the intra-option policy, can be trained with any deep RL algorithms for each agent to reach its corresponding individual termination state (e.g.. min)). In this way, we can obtain the multi-agent options in infinite-scale state spaces.
4.4 Adopting Multi-agent Options in MARL
To utilize options in MARL, we adopt a hierarchical algorithm framework shown in Figure 3 Typically, we train a RL agent to select among the primitive actions, aiming to maximize the accumulated reward. We view this agent as one-step option- primitive option. As shown in Figure 3 when getting new observations, the hierarchical agent first decides on which option w to use with the high-level policy, and then decides on the primitive action to take based on the corresponding intra-option policy T The agent does not decide on policy until the current option terminates.
Aprer
Agret
Hish level Policy
Primitive Optica
Mulli-egent Option
Multi-ggant
Option
Policy
Primitive Actions
Primitive Actions
Primitive
Actions
Figure 3: Hierarchical algorithm framework
option with the high-level
For a multi-agent option < Lw, = (T), TT), ((s1,"--,ss)) >. it can be adopted either in decentralized or centralized manner. As the purple arrows in Figure the agents choose their own options independently, and they may choose different options to execute in the meantime. In this case, agent selects option w, will execute zÚ, until reaching its termination state s; or exceeding the execution step limit. On the other hand, we can force the agents to execute the same multi-agent option simultaneously. As shown by the blue arrows in Figure 3 we view the n agents as whole, which takes the joint state as the input and chooses the same multi-agent option to execute at a time. Once a multi-agent option w is chosen, agents 1 n will execute x until they reach ($1, ......... sn) exceed the step limit. The decentralized way is more flexible but has larger search space. While, the centralized way fails to consider all the possible solutions but makes it casier for the agents to visit the sub-go -oal joint states, since the agents select the same joint option which won't terminate within the time limit until the agents arrive at the sub-goal.
Further, the centralized manner may not be applicable when the number of agents n is large, since the input space will grow exponentially with n. Thus, we propose to partition the agents into sub-groups, and then learn the joint options within each sub-group. The intuition is that multi-agent task can usually be divided into sub-tasks, each of which can be completed by a sub-group of agents. For each sub- gub-group, we can learn a list of joint options, and then the agents of this group can utilize these

---

(a) Grid Room
(b) Grid Maze
(c) Mujoco Room
(d) Mujoco Maze
Figure 4: Simulators for Evaluation
options in a decentralized or centralized way as mentioned above. Further, if there is no way to divide the agents based sub-tasks, can still partition them randomly some two-agent or three-agent sub-groups. Agents within the same sub-group will co-explore their joint state space sharing their views. More intelligent grouping methods, e.g., attention mechanism (28), can be easily integrated into our solution to boost the performance, which is not the focus here (multi-agent option discovery).
Evaluation and Results
5.1 Experiment Setup
As shown in Figure 4 the proposed approach is evaluated four multi-agent goal-achieving tasks. (1) For tasks shown as Figure(((a) [ [bb] n (2~8) agents agents (triangles) must reach the goal area (circles) at the same time to complete this task; Or even harder,
m agents are divided into m groups and each group of agents has a special goal labeled with the same color, the n X m agents should get their related goals simultaneously complete this task, without knowing which goal is related to them at first. Hence, highly coordinated policy is required. (2) To test the performance of the deep learning extension of our algorithm,
build the tasks shown Figure 44C) and 4(d)
based on Mujoco [29]. where two point agents need to reach the target area (red) simultancously to complete the task. Both the state and action spaces of the point agent are continuous and infinite-scale. Note that these tasks are quite challenging: (1) Agents' observations do not include any information about the goal area, so they need to fully explore their joint state space find the rewarding state. (2) The reward space is highly sparse and delayed: for all the tasks, only when the agents complete the task can they receive a reward signal r 1.0 (shared by all the agents); otherwise, they will receive exploration strategies like ours cannot complete these
r = 0.0. Hence, agents without highly-efficiee tasks. In Section 5.2] we conduct experiments with tasks of increasing complexity (e.g., Figure 5}. showing that the more difficult the task is, the more advantageous our approach becomes.
There are a high-level and low-level policy in the hicrarchical framework (Figure 3). The low-level policy is decomposed into single-agent policies for each agent to reach its individual termination state, so can be trained with single-agent RL. (1) For discrete tasks (e.g., Figure 4(a) and 4(b). we adopt Distributed Q-Learning [30] (decentralized manner: each agent decides on its own option based on the joint state) or Centralized Q-Learnin + Force (centralized manner: viewing n agents as whole, adopting Q-Learning to this joint agent and forcing them to choose the same joint option at a time) to train the high-level policy and adopt Value Iteration [3I for the low-level policy training. (2) For continuous control tasks (e.g.. Figure (CC) and (4d)). the tabular RL algorithms mentioned above cannot work. Instead, to improve the scalability of the our method, we adopt MAPPO [32 to train the high-level policy of the joint options, and Soft Actor-Critic 33 to train the low-level policy, which are SOTA deep MARL and RL algorithms respectively.
We compare our approach- agents with multi-agent options, with two baselines: (1) Agents without options: SOTA MARL algorithms are adopted train the agents without using options. For discrete tasks, we use Distributed and Centralized Q-Learning. These tabular Q-learning algorithms which update the Q-value for all the state-action pairs in each training episode, usually outperform the NN-based algorithms. We show this through comparison with COMA (34). MAVEN [35, Weighted
QMIX 336. For continuous tasks, we use MAPPO. MADDPG (37 and MAA2C as comparisons,
which have been proven as strong MARL baselines for continuous control 38 39 Comparisons
with this baseline can show the effectiveness of using options to aid exploration. (2) Agents with
single-agent options: first construct covering options for each agent based on their individual state
7

---

(a) Grid Maze with 2 agents
(b) Grid Maze with 3 agents
(c) Grid Maze with 4 agents
(d) Grid Maze with 2 agents
Grid Maze with 3 agents
(f) Grid Maze with 4 agents
Figure 5: Evaluation n-agent Grid Maze tasks: (a)-(c): Distributed Q-Learning; (d)-(f) Centralized Q-Learning + Force. The performance improvement of our approach are more and more significant the number of agents increases. The centralized way utilize the n-agent options performs better.
Dug
(a) agents
(b) 3x2 agents
(c) 2x2 agents
(d) 3x2 agents
Figure 6: Comparisons on the m x n Grid Maze tasks: (a)-(b) Distributed Q-Learning: (c)-(d) Centralized Q-Learning Force. Agents with pairwise options can learn these tasks much faster than the baselines, even when both the baselines fail on the 3 x Grid Maze task. Also, agents trained with Centralized Q-Learning Force have higher convergence speed and better final performance.
spaces, and then utilize these options in MARL, like what they do in 6 discovery method, we adopt the SOTA algorithm proposed previous option discovery algorithms for sparse reward scenarios, like I7
As for the option 19 which claims outperform Comparisons with
20 8 9.
40].
this baseline can show the superiority of our approach to directly identify and adopt joint options in multi-agent tasks. The number of single- and multi-agent options for each agent to select is the same.
Last, regarding the setup of the option discovery phase, we collect 1 x 10 transitions (i.e., {[s,, a, 8'))) for the discrete tasks and 5 x 10a transitions for the continuous control tasks in order to build the state transition graphs, based on which we can extract single- or multi-agent options. In discrete tasks, we use random walk policy to collect the data. While, in Mujoco tasks, the data collection is in stages, Specifically, the agents explore the environment through a random walk in the first stage. Then, in the next stage, the agents explore with their primitive actions and options that are extracted from the samples collected in the first stage. Our results guarantee that these options can significantly improve the joint exploration in the second stage. As for the number, we learn 16 multi-agent options the Grid tasks and multi-agent options in the Mujoco tasks.
5.2
Main Results
For each experiment, we present comparisons among agents with multi-agent options (blue line), single-agent options (red line) and no options. We use the number of time steps to complete the task the metric (the lower the better). The maximum of steps that agent discrete task and 500 for the continuous task. We run each experiment for five times with different random seeds and plot the mean and standard deviation during the training process.
take is 200 for the
n-agent Grid Maze task: Figure 5(a) 5(a)5(c) 5(c) we test these methods with Distributed Q-learning as the high-level policy. The performance improvement brought by our approach are more and more

---

(a) 4 agents
(b) agents
(c) agents
(d) 6 aggnts
Figure 7: Comparisons on the n-agent Grid Maze tasks with random grouping: (a)-(b) Distributed
Q-Learnin:: (c)-(d) Centralized Q-Learnnng Force. When n-agent options are not available, can still get a significant performance improvement with only pairwise options.
Tretustar abcukaion
(a) Grid Room with 4 agents
(b) Grid Room with agents
(c) Change with collision numbers
Figure 8: Comparisons on the n-agent Grid Room tasks where agent's state transitions can be influenced by the others.
significant as the number of agents increases. When n = 4, both the baselines fail to complete the task, while agents with four-agent options can converge within ~ 400 episodes. While, in Figure (5(d) 5()) we show the results of using Centralized Q-Learning + Force. We can see that the centralized manner utilize n-agent options leads faster convergence, since the joint output space of the agents is pruned (Figure 3. The results of the n-agent Grid Room task can be found in Appendix E. based on which we can get the same conclusion. To justifyy the difficulty of the Grid tasks for evaluation. we provide the performance of COMA, MAVEN, Weighted QMIX on the most challenging 4-agent Grid Maze in E.T None of them can learn to complete the coordinated goal-achieving task due the highly sparse reward setting in our eva evaluation tasks. Still, our method performs much better (Figure 5(c]p()) Given that the neural network training in these baselines requires a longer time, we set the training horizon as 5000 episodes which is five times that of the tabular methods and the networks are trained for ten iterations in each episode, to maintain the fairness.
Grid Maze task with sub-task grouping: The size of the joint state space grows exponentially with the number of agents, making it infeasible directly construct n-agent options for large n. However, in practice, a multi-agent task can usually be divided into sub-tasks, and the agents can be divided into uub-groups based on the sub-tasks they are responsible for. Thus, we test our proposed method on the m x n Grid Maze tasks shown as Figure 4(b] where we divide the agents into m uub-groups, each of which contains n agents with the same goal area (labelled with the same color). Note that, in the 2 x 2 (3 x 2) task, we use two-agent (pairwise) options rather than four-agent (six-agent) options, and for the high-level policy, we only use the joint state of the two agents as input to decide on their joint option choice. We can see from Figure 6 that agents with pairwise options can learn to complete the tasks much faster than the baselines (e.g., improved by about two orders of magnitude in Figure ((C). Also, we see that agents trained with Centralized Q-Leer-inn + Force (Figure ((d) have faster convergence speed and better convergence value. The results for the
m X 12 Grid Room tasks are in Appendix E.2
Further, we note that our method also works with random grouping when sub-task grouping may not work. The intuition is that adopting two-agent or three- agent options can encourage the joint exploration of the agents small sub-groups, which can increase the overall performance compared with only utilizing single-agent explorations. As shown Figure 7 we compare the performance of agents using pairwise options with the baselines on the naggent Grid Maze tasks. When = 6, agents with single-agent options or options can't 't complete this task, while we can get a significant performance improvement with only pairwise options. On the other hand, agents with pairwise options can't an complete the most challenging six-agent task, when
Grid Maze task with random grouping:

---

However, if we adopt Centralized Q- Q-Learning + Force. agents with pairwise options can still complete this challenging task with satisfaction (Figure ( The same set of results for the Grid Room task are in Appendix E.3
using Distributed Q- Q-Learning (Figure [
Grid Room task with random grouping and dynamic influences among agents: Further, show that even if in environments where an agent's 's state transitions can be strongly influenced by the others, we can still obtain good approximations of the multi-agent options to encourage joint exploration using Theorem 4.1 For this new setting, different agents cannot share the same grid so that an agent may be blocked (controlled with a probability parameter) by others when moving ahead, and this influence is highly dynamic. We use the Centralized Q- Q-Learning + Force as the high-level policy, of which the results are shown as Figure [8] Compared the results shown in Appendix E..] this modification leads to slight instability in the training process, but we can still get significant
performance improvement with the identified pairwise options. Especially, in [{c] our solution still perform well (i.e., reach the target in 60 100 steps) in cases where the collision influence is heavy (i.e., collisions occur in up to 63% of the steps).
Mujoco continuous control tasks: Finally, in order to show the effectiveness and generality of the deep learning extension of our approach (introduced in Sec- tion 4.3) on tasks with anfnite-scale state space, we compare it with the baselines on the Mujoco tasks
Mida, agai Cytton
shown as Figure 4(c) and [dd) of which the results are shown in Figure 2
On one hand, the comparison between our method and MARL (including MAPPO,
(a) Mujoco Room
MADDPG, MAA2C) without using options shows that abstracting some control series into options and inte- grating them with a hierarchical training framework can reduce the learning difficulty of continuous control tasks. On the other hand, the comparison with agents using single-agent options shows that discovery and centralized adoption of multi-agen agent options can aid the exploration in their joint state space, and lead them toward the "bottleneck" joint states which are essen- tial to complete the cooperation tasks. Note that the options adopted pre-trained with SAC for 1 10 episodes, have pretrained the baselines: MAA2C, MADDPG, and MAPPO, for the same number of episodes to maintain fairness.
AGAASE wie Outice
MAAITO wil Oyeaces
(b) Mujoco Maze
Figure 9: Comparisons on Mujoco tasks.
6 Conclusion And Future Works
In this paper, we propose to approximate the joint state space in MARL as a Kronecker graph and es- timate its Fiedler vector using the Laplacian spectrum of the individual agents' state transition graphs. Based on the approximation of the Fiedler vector, multi-agent covering options are constructed, containing multiple agents' temporal action sequence towards the sub-goal joint states which are usually infrequently visited, so as to accelerate the joint exploration the environment. Moreover, we propose a scalable extension of our algorithm so that it can work on tasks with large-scale or continuous state spaces, in order to improve the generality. Further, we propose algorithms to adopt these multi-agent options in MARL, using centralized, decentralized, and group- strategies, respectively. We empirically show that agents with multi-agen options have significantly superior performance than agents relying single-agent options or options.
One limitation of our method is that there will be noglneglie differences between our approx- imation G and the true joint state transition graph G, if the state transitions of an agent are hugely influenced by the others. Therefore, developing specific approximation error bound as a supplement to Theorem 4.1 can be an interesting future direction. On the other hand, to utilize the multi-agent options, agents need share their views (i.e., observations) since the initiation and termination conditions of the multi-agent options are defined based on the joint observations. Communication among the agents is required in cases where the joint observations are not directly available. Thus, integrating our method with efficient communication strategies in MARL [4] to mitigate the communication complexity can be meaningful future works.
10

---

References
[1] Sutton, R. S., D. Precup, S. P. Singh. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial Intelligence, 1 112(1-2):1112111 1999.
[2] Jinnai, Y., D. Abel, D. Hershkowitz, M. L. Littman, G. D. Konidaris. Finding options that minimize planning time. In Proceedings of the 36th International Conference Machine Learning, ICML 2019, vol. 97 of Proceedings of Machine Learning Research, pages 3120-3129. PMLR, 2019.
[3] Jinnai, Y., J. W. Park, D. Abel, G. D. Konidaris. Discovering options for exploration by minimizing cover time. In Proceedings of the 36th International Conference Machine Learning, ICML 2019, vol. 97 of Proceedings of Machine Learning Research, pages 3130-3139. PMLR, 2019.
[4] Fiedler, M. Algebraic connectivity of graphs. Czechoslovak mathematical journal, 23(2):298- 305, 1973.
[5] Ghosh, A., S. Boyd. Growing well-connected graphs, 2006.
[6] Amato, C., G. D. Konidaris, L. P. Kaclbling. Planning with macro-actions decentralized pomdps. In Proceedings of the 13rd International conference Autonomous Agents and Multiagent Systems, AAMAS, 2014, pages 1273-1280 IFAAMAS/ACM, 2014.
[7] Amato, C.. G. Konidaris, L. P. Kaclbling, J. P. How. Modeling and planning with macro-actions in decentralized pomdps. Journal of Artificial Intelligence Research, 64:817-859, 2019.
[8] Chakravorty, J., P. N. Ward, J. Roy, M. Chevaller-Boisvert, S. Basu, A. Lupu, D. Precup. Option-critic cooperative multi-agent systems. In Proceedings of the 19th International Conference Autonomous Agents and Multiagent Systems, AAMAS 2020, pages 1792-1794. 2020.
[9] Lee, Y., J. Yang, J. J. Lim. Learning to coordinate manipulation skills via skill behavior diversification. Proceedings the
the 8th International Conference on Learning Representations, ICLR 2020. OpenReview.net, 2020.
[10] McGovern, A., A. G. Barto. Automatic discovery of subgoals in reinforcement learning using diverse density. In Proceedings of the 18th International Conference on Machine Learning, ICML 2001, pages 361-368. Morgan Kaufmann, 2001.
[11] Menache, I., S. Mannor, N. Shimkin. Q-cut - dynamic discovery of sub-goals in reinforcement learning. In Proceedings of the 13th European Conference Machine Learning, ECML 2002, pages 295-306. Springer, 2002.
[12] Mankowitz, D. J., T. A. Mann, S. Mannor. Adaptive skills adaptive partitions (ASAP). In Advances in Neural Information Processing Systems 29, NIPS 2016, pages 1588-1596. 2016.
[13) Harb, J., P.-.. Bacon, M. Klissarov, D. Precup. When waiting is not an option Learning options with deliberation cost. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, AAAI 2018. 2018
[14] Stolle, M.. D. Precup. Learning options in reinforcement learning. In International Symposium on abstraction, reformulation, and approximation, pages 212-223. Springer, 2002.
[15] Simsek, Ö., A. P. Wolfe, A. G. Barto. Identifying useful subgoals in reinforcement learning by local graph partitioning. In Proceedings of the 22nd International Conference on Machine Learning, ICML 2005, vol. 119, pages 816-823, 2005.
[16] Simsek. Ö., A. G. Barto. Skill characterization based on betweenness. In Advances in Neural Information Processing Systems 21, NIPS 2008, pages 1497-1504. 2008
[17] Machado, C., M. Bellemare, M. H. Bowling. laplacian framework for option discovery in reinforcement learning. CoRR, abs//703 700000 2017.

---

[18] Machado, M. C., C. Rosenbaum, X. Guo, M. Liu, G. Tesauro, M. Campbell. Eigenoption discovery through the deep successor representation. In Proceedings of the 6th International Conference on Learning Representations, ICLR 2018. OpenReview.net, 2018.
[19] Jinnai, Y., J. W. Park, M. C. Machado, G. D. Konidaris. Exploration in reinforcement learning with deep covering options. In Proceedings of the 8th International Conference on Learning Representations, ICLR 2020. OpenReview.net, 2020.
[20] Shen, J., G. Gu. H. Liu. Multi-agent hierarchical reinforcement learning by integrating options into maxq. In First international symposiissssss on computer and computational sciences (IMSCCS 066,, vol. 1, pages 076-682. IEEE, 2006.
[21] Yang, J., I. Borovikov, H. Zha. Hierarchical cooperative multi-agent reinforcement learning with skill discovery. In Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020, pages 1566-1574. 2020.
[22] Chen, J., J. Chen, T. Lan, V. Aggarwal. Learning multi-agent options for tabular reinforcement learning using factor graphs. IEEE Transactions on Artificial Intelligence, pages 1-13, 2022.
[23] Weichsel, P. M. The kronecker product of graphs. Proceedings of the American mathematical society, 13(1):77-52, 1962.
[24] Bašić, M., B. Arsić, Z. Obradović. Another estimation of laplacian spectrum of the kronecker product of graphs. Information Sciences, 609:605-622 2022.
[25] Wu, Y., G. Tucker, O. Nachum. The laplacian in RL: learning representations with efficient ap- proximations. Proceedings of the 7th International Conference on Learning Representations, ICLR 2019. OpenReview.net, 2019.
[26] Wang, K., K. Zhou, Q. Zhang, J. Shao, B. Hooi, J. Feng. Towards better laplacian representation reinforcement learning with generalized graph drawing. In Proceedings of the 38th Inter- national Conference Machine Learning, ICML 2021, vol. 139 of Proceedings of Machine Learning Research, pages 11003-11012. PMLR, 2021.
[27] Chung, R., C. Graham. Spectral graph theory. 92. American Mathematical Society, 1997.
[28] Vaswani, A., Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. Gomez, Kaiser, I. Polo- sukhin. Attention is all you need. In Advances in Neural Information Processing Systems 30, NIPS 2017, pages 5998-6008, 2017.
[29] Todorov, E., T. Erez, Y. Tassa. Mujoco: A physics engine for model-based control. In 2012 JEEE/RSJ International Conference on Intelligent Robots and Systems, pages 5026-5033. IEEE, 2012.
[30] Lauer, M., M. A. Riedmiller. An algorithm for distributed reinforcement learning in cooperative multi-agent systems, In Proceedings of the 17th International Conference on Machine Learning, ICML 2000, pages 535-542. Morgan Kaufmann, 2000.
[31] Sutton, R. S., A. G. Barto. Reinforcement learning: An introduction. MIT press, 2018.
[32] Yu, C., A. Velu, E. Vinitsky, Y. Wang, A. M. Bayen, Y. Wu. The surprising effectiveness of MAPPO cooperative, multi-agent games. CoRR, abs/2103.01955. 2021.
[33] Haarnoja, T., A. Zhou, P. Abbeel, S. Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, vol. 80 Proceedings of Machine Learning Research, pages
PMLR, 2018.
[34] Foerster, J. N.. G. Farquhar, T. Afouras, N. Nardelli, S. Whiteson. Counterfactual multi-agent policy gradients. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, AAAI 2018, pages 2974-2982, AAAI Press, 2018
[35] Mahajan, A., T. Rashid, M. Samvelyan, S. Whiteson. MAVEN; multi-agent variational explo- ration. In Advances in Neural Information Processing Systems 32, NIPS 2019, pages 7611-7622. 2019.
12

---

[36] Rashid, T., G. Farquhar, B. Peng, S. Whiteson. Weighted QMIX: expanding monotonic value function factorisation for deep multi-agent reinforcement learning. Advances in Neural Information Processing Systems 33, NIPS 2020. 2020.
[37] Lowe, R., Y. Wu, A. Tamar, J. Harb, P. Abbeel, I. Mordatch. Multi-agent actor-critic for mixed cooperative-compettee 30, NIPS 2017, pages
environments. In Advances in Neural Information Processing Systems 2017.
[38] Papoudakis, G., F. Christianos, L. Schäfer, S. V. Albrecht. Benchmarking multi-agent deep reinforcement learning algorithms in cooperative tasks. In Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks 1. 2021.
[39] Papoudakis, G., F. Christianos, L. Schafer, S. Albrechht Comparative evaluation of multi-agent deep reinforcement learning algorithms. CoRR, abs/2006.07869, 2020.
[40] Eysenbach, B., A. Gupta, J. Ibarz, S. Levine. Diversity is all you need: Learning skills without a reward function. In Proceedings of the 7th International Conference on Learning Representations, ICLR 2019, OpenReview.net, 2019.
[41] Foerster, J. N., Y. M. Assael, N. de Freitas, S. Whiteson. Learning communicate with deep multi-agent reinforcement learning. In Advances in Neural Information Processing Systems 29, NIPS 20/6, pages 2137-2145. 2016.
[42] Sayama, H. Estimation of laplacian spectra of direct and strong product graphs. Discrete Applied Mathematics, 205:160-170, 2016.
13


Reviews:
[{"review_id": "tsa2voeXUa", "reviewer": "Reviewer_2Vpw", "summary": "The paper studies the topic of covering option discovery in multi-agent reinforcement learning. The proposed approach extends in non-trivial way the single-agent approach that is based on greedily connecting distant state in the embedding space provided by the Fiedler vector of the MDP graph (the second smallest eigenvector of the MDP Laplacian). As the joint state space grows exponentially with the number of agents, performing option discovery directly on the joint space is computationally very intense. Instead, the authors propose to approximate the joint space by Kronecker product of single agents' state space, estimate the spectrum of each individual agent's Laplacian and then find the joint Fiedler vector on the whole space using their main theorem 4.1.\nMoreover, the authors provide empirical investigation in 2d navigation mazes (discrete and continuous).  \n\n ", "questions": "- Could you please explain the experimental setup for the option discovery phase in each environment? how much data do you use ? under which policy you collect the data ? how many options are learned ? Is there any finetuning or pruning of options ?\n- How the primitive option is defined in the experiments ? Once the primitive option is selected by the high-level policy, under which distribution the primitive actions are sampled ? ", "limitations": "The authors adequately addressed the limitations and potential negative societal impact of their work", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n## Strength:\n+ The paper is well written and well motivated\n+ I appreciated the illustrative example in Figure 1 and 2.\n+ The proposed approach is technically sound and the authors show in theorem 4.1 how we can estimate the Laplacian spectrum of Kronecker product of factor graphs.\n+ The authors provide first an algorithm in the tabular case and then extended it to large state space using the generalized graph drawing objective.\n+ The authors investigate different variants of the algorithm (centralized, distributed, sub-task and random grouping) and provide a comparison with SOTA multi-agent algorithms with and without options. Overall, the proposed method provide a boost of performance consistently across tasks.\n\n## Weakness:\n-  The experimental setup for the option discovery phase is not explained at all. What is data used? how it was collected ? How many options are considered ? \n- The authors considered only 2-d navigation tasks. The scalability of the method in more challenging and practical environment remains a weak spot of the paper (The Mujoco experiments provide some insights but the domains have essentially  very small dimensionality) ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HAlS0XSMFsJ", "reviewer": "Reviewer_pJbE", "summary": "This paper proposes a new multi-agent hierarchical reinforcement learning algorithm — Multi-agent Covering Option Discovery. Since the state space and action space of a multi-agent environment grow exponentially with the number of agents, this paper approximates the joint state transition graph as the Kronecker product of single-agent ones, which reduces the complexity of computing the joint state transition graph's Fiedler vector. Finally, the covering options method is applied to construct multi-agent options. In addition, the algorithm is extended to the continuous state space environment. The algorithm achieves state-of-the-art performance in some multi-agent tasks.", "questions": "1. When the algorithm is applied to an infinite-scale state-space environment, the eigenvectors need to be represented as a neural network. Is it possible to provide an experimental analysis of this estimation error? For example, the same method can be used for experimental analysis in discrete tasks.\n2. In a more complex infinite-scale state-space environment, does the random interaction still work? Cause agents may not be able to explore the environment effectively, or even only a small part of the environment, so the eigenvector representing may have a large error.\n3. Does the difference in the frequency of changing options by different agents have an effect on the results? Does it happen that a certain state is the termination state of one option but not the termination state of another option? Specifically, in a decentralized manner, if agents A and B choose different options and reach a state where A terminates and B continues, B will switch options while A continues.\n4. Can the comparison with the SOTA MARL algorithm all use the NN-based DRL algorithm? For example, DQN-based MAOD.\n5. As stated in Weakness.2, is the MAOD in the Mujoco environment the centralized manner or the decentralized manner?", "limitations": "The authors analyze the estimation error of the joint state transition graph and verify it experimentally accordingly. However, if the algorithm is applied to an environment with a more complex state space, the state transfer graph will be very large, leading to increased storage and computational complexity. So adding a section would be quite helpful.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths：\n\n1. The motivation is very clear. The paper gives an illustrative example to explain that the multi-agent option is more conducive to effective exploration compared to the single-agent option. And the Kronecker product is rationally applied to simplify the computation of the joint Fielder vector, and the robustness of the estimation error is experimentally analyzed.\n2. The paper is well organized and clearly written.\n\nWeaknesses：\n\n1. The algorithm is difficult to apply to large-scale environment training. Whether or not the Kronecker product approximation is used, the computational effort required to construct the graph and the space required to store the graph is huge if the environment is complex. In this paper, although experiments are conducted on a Mujoco environment which is an infinite-scale state space, the state space is only 6 dimensions, still very small.\n2. The experimental comparison with SOTA MARL algorithms (COMA, MAVEN,...) is not convincing. First, tabular and NN-based algorithms can not be compared based on the same training episodes. Second, these MARL algorithms are based on the CTDE (Centralized Training Distributed Execution) framework, so the agents' execution is independent, which is not a fair comparison with MAOD (Centralized manner).\n3. The paper is an extended version of [1], only extending the algorithm to the continuous state space environment, and additionally replacing the experimental environment.\n4. Typographical error. Eq.18 in Appendix should be $v_{11} = v_1^{G_1} \\otimes v_1^{G_2}$ not $v_{11} = v_1^{G_1} \\otimes v_2^{G_2}$.\n\n\n\n[1] Chen, J., Chen, J., Lan, T. and Aggarwal, V., 2022, May. Multi-agent Covering Option Discovery through Kronecker Product of Factor Graphs. In *Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems* (pp. 1572-1574). https://www.ifaamas.org/Proceedings/aamas2022/pdfs/p1572.pdf", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "AL8mU74zJH0", "reviewer": "Reviewer_RS6U", "summary": "This work extends the Covering Option Discovery framework (for tabular Q-learning) to the multi agent setting. Their contributions lies in using the kronecker product of each agent's state transition graphs to get a joint graph who Felder vector (eignevector of second smallest eigen value) can be estimated. Then, like in covering option discovery where the states that have to be explored most are extracted from the Felder vector, they extract the joint states that have to be explored most. This is followed a projection of the important joint states into individual state spaces to obtain the individual states that have to be explored most. They perform experiments with a decentralized and centralized framework that learn these options (in a tabular framework and a deep learning extension) on grid room/grid maze/mujoco room/mujoco maze.", "questions": "1. Are the MAPPO, MADDPG, MAA2C baselines doubly set back: (1) because they don't have options and hence they require longer to learn and (2) use neural networks that would require longer to learn? Can tabular approximation methods be used in the baselines as well for a fair comparison? What about in COMA, MAVEN and QMIX? Alternatively would using an MLP in centralized and decentralizing Q learning slow down learning by a large factor?", "limitations": "None", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1. Interesting extension to the covering discovery framework for MARL. \n2. Helpful sensitivity analysis on sub-task grouping and random grouping for large n in the experiments.\n\nWeaknesses\n1. Missing analysis of the options learnt. It would be hlepful to understand what states were deemed most important to explore. Especially in the multi-agent setting.\n2. Entension to MARL environments where tabular Q learning methods may fail.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1bn8MgUDFpn", "reviewer": "Reviewer_kydJ", "summary": "This paper studies an empirical method to encourage the exploration of RL algorithm in multi-agent settings. The proposed method is inspired by the covering option discovery in single-agent scenarios. A naïve application of single-agent option discovery cannot work because the joint state space. To address this challenge, the authors proposed a novel method to compute multi-agent options based on a Kronecker-product approximation of the joint state space. The proposed method reduces the computing complexity significantly when each local state space is large. The authors also extend their method to tasks with infinite-scale state space, and provide four simulation results to show the effectiveness of their method.", "questions": "Besides the suggestions I gave in the previous part, I’m also curious about if the proposed multi-agent option recovery approach can be used when the learning algorithm is not tabular Q learning? Possible candidates include Q learning with function approximation and policy gradient methods.", "limitations": "I encourage the authors to add a discussion about the limitations and future works at the end of this paper. I do not see any potential negative social impacts.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper makes a good contribution to the multi-agent reinforcement learning. It is interesting to see a method based on graph Laplacian can be used to encourage exploration and be implemented efficiently in a multi-agent setting. The paper is well-written and easy to follow with adequate intuitions and contexts.\n\nI also have some suggestions for further improvement: In Theorem 4.1, it would be better to provide a more specific error bound instead of using a vague phrase “can approximate”. Further, the authors shall consider specify what assumptions are required in line 577. In Section 4.3, I recommend to move the pseudo code of the algorithm in Appendix D to the main body. In the second paragraph of Section 4.3, the authors emphasize the proposed method significantly reduces the computational complexity. What about the communication complexity? What will happen if $m$ is small and $n$ is large? (line 200)\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept