Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths
1. Interesting extension to the covering discovery framework for MARL. 
2. Helpful sensitivity analysis on sub-task grouping and random grouping for large n in the experiments.

Weaknesses
1. 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.
2. Entension to MARL environments where tabular Q learning methods may fail.
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
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
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.

I 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)

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.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: Strengths：

1. 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.
2. The paper is well organized and clearly written.

Weaknesses：

1. 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.
2. 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).
3. The paper is an extended version of [1], only extending the algorithm to the continuous state space environment, and additionally replacing the experimental environment.
4. 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}$.



[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
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.
2. 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.
3. 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.
4. Can the comparison with the SOTA MARL algorithm all use the NN-based DRL algorithm? For example, DQN-based MAOD.
5. 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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
Moreover, the authors provide empirical investigation in 2d navigation mazes (discrete and continuous).  

 
strengths_and_weaknesses: 
## Strength:
+ The paper is well written and well motivated
+ I appreciated the illustrative example in Figure 1 and 2.
+ 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.
+ The authors provide first an algorithm in the tabular case and then extended it to large state space using the generalized graph drawing objective.
+ 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.

## Weakness:
-  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 ? 
- 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) 
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 ?
- 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
review_title: null

Meta-review: metareview: This paper proposes an extension of the covering discovery framework from single-agent to MARL. There was unanimous support for accepting this paper and agreement that it is an interesting and very useful contribution.

The responses to reviewers helped to clarify a few points. When preparing a revision, we strongly encourage you to address these points which came up during the review process:
* Consider putting more emphasis on the Mujoco experiments and DL extension in the main paper, to illustrate the generality of the results
* Discuss limitations and future work related to communication complexity of the proposed approach
* Clarify/justify details of how tabular and NN-based methods are compared in the grid world experiments
* Clarify the setup in the option discovery phase
confidence: Certain
Decision: Accept