Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper proposes an unsupervised framework SPD to discover diverse policies for agents with no extrinsic reward. SPD uses synergy pattern graph to represent the joint policy for agents and discovers diversity policy by applying optimal transport. The experiments show that SPD outperforms some MARL algorithms in some environments. The contributions of this work are designing a new method to represent the joint policy for agents by considering other agents in MARL and proposing to explore skills by optimal transport. 
strengths_and_weaknesses: Strengths:

1. This work provides an interesting and novel idea on the use of graphs to represent the joint policy for MARL.

2. The paper is well written.

Weaknesses:

1. There is no support for the conclusion that SPD is better than other URL methods in terms of performance.

2. Some standard benchmarks used in the MARL community need to be considered. Some of the results are very confusing to me, such as CDS does not work at all. 




questions: 
Questions:
1. Why is CDS performance worse than QMIX?

2. Why not compare with some other methods of URL on google football? Although these URL methods are not designed for the MARL algorithms, they are needed for comparison.



Suggestions:

I think the auther should discuss some works that are designed to encourage diversity [1] [2] [3]. 
Furthermore, I believe the baselines that are compared in this work are weak. Specifically, some MA exploration works are not considered, and the baseline with the best performance in the experiments (i.e., football game) is QMIX. The authors need to consider some effective MA exploration works [1].
In addition, the experiments do not compare URL methods on google football and more URL methods should be taken into consideration, e.g., [4] [5].
Finally, SPD is compared on some environments and more environments need to be considered, such as SMAC, MAMUJOCO.
For example, on some SMAC or on Google football environments used by CDS. Thus a more comprehensive experiments could significantly improve the paper.


[1]: Zhou Z, Fu W, Zhang B, et al. Continuously Discovering Novel Strategies via Reward-Switching Policy Optimization[J]. arXiv preprint arXiv:2204.02246, 2022.

[2]: Parker-Holder J, Pacchiano A, Choromanski K M, et al. Effective diversity in population based reinforcement learning[J]. Advances in Neural Information Processing Systems, 2020, 33: 18050-18062.

[3]: Lupu A, Cui B, Hu H, et al. Trajectory diversity for zero-shot coordination[C]//International Conference on Machine Learning. PMLR, 2021: 7204-7213.

[4]: Lee L, Eysenbach B, Parisotto E, et al. Efficient exploration via state marginal matching[J]. arXiv preprint arXiv:1906.05274, 2019.

[5]: Liu H, Abbeel P. Aps: Active pretraining with successor features[C]//International Conference on Machine Learning. PMLR, 2021: 6736-6747.
limitations: Limitations should be discussed more adequately in the main body of the paper. Societal impact is likely minimal.
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 work proposes a novel unsupervised reward labeling method called SPD, which rewards a population of agents when they have a relationship graph (synergy patten graph) that different to other populations. The 

Concretely, this work first builds "synergy pattern graph" of a given population and then uses the SPG discrepancy between populations as the metric to encourage inter-agent diversity. 

Experiments show that the proposed method can (1) learn diverse synergy patterns and (2) improve the generalizability on downstream tasks.

Generally, I like this work. I will raise my score if the writing can be improved and more convincing evaluation results, both qualitatively and quantitatively, can be provided.


# Update after responses

I am happy to see the authors revise the paper to make it more clear. I raised my score.

strengths_and_weaknesses: 
### Strengths

* This work formulates the diversity between agents in the perspective of "synergy pattern graph". This formulation of inter-agent diversity is novel. It encourages the **diversity in relationship**, which stands higher than simply computing diversity based on agents within one group or computing diversity based on single-agent information.
* The continuity and completeness of the writing is good. There are no obvious flaws and disconnected notations. 
* I am very happy to see that code is provided. The code is provided with detailed documents and function description. This is a very big plus. 


### Weaknesses

* The evaluation results do not provide a full view on the effectiveness of the proposed method. See questions.
* Writing clarity can be further improved since the notations are a bit overwhelmed. I think the terms like SPG, SPG batch, SPG element, Discrepancy of SP and so are messed. It would be better to simplify them if don't have enough space to clarify define and introduce them. Also, I expect to see a concrete form of reward in implementation section, rather than a notation that refers to another notation that refers to third notation.
* Besides, the connection between paragraphs and sections is not smooth enough, which creates huge burden in understanding. A good idea is to draw an illustrative diagram showing the relationship between concepts (I don't think Figure 1 is informative.). 
 

questions: 
### Questions on experiments


I saw StartCraft2 SMAC environment is supported in your code. Why don't put its result in the paper?

In Figure 2 (a), the d_sp is computed based on the Gromov-Wasserstein discrepancy between different populations. How you compute this for DIAYN and WURL? IIUC they only has one population. I think this figure is not convincing to stand for the claim "SDP captures the relative relations of agents" (line 338) and "SPD can inspire agents to visit identifiable states while further encouraging agents to explore with other types of coordination policies" (line 291). I expect more convincing evidence to show that after SPD pre-training the models already "learns useful synergy patterns" (line 338).

Can you plot the test performance of SPD population while conducting the unsupervised learning? If we can see performance improvement then it shows that SPD can learn policy without reward at all!






### Questions on method

If I understand correctly, there exists Z populations of policies and the population that actually involve in each episode is uniformly sampled from the pool of Z populations. Correct? 
**Is it possible that this is the reason why SPD is working? This is similar to league training and ensemble method, which have shown can improve generalization.**
This is an important question. Please point out existing exp result in the paper if I miss it.

A question related to this is that do the Z populations really diverse? Figure 2 (a) shows the d_sp 


---

Current method labels transitions with pseudo reward and stores them into replay buffer for QMIX training. Therefore the reward might be outdated in the process of training. Is it necessary to relabel those reward based on latest policies?


---


Related to above question, is it possible to compute the proposed pseudo reward based on truncated episode? For example, to generalize your method to on-policy RL algorithm like independent PPO, the reward should be computed on-the-fly before the episode is terminated.



### Other questions


Why the webpage is empty? If you don't prepare it, don't post it.

---

Some typos:

* CSD paper has wrong citation format.
* Algorithm 1 Line 14: Update d_gw according to Eq (6) as well as Eq (1).
* Line 139: "about how to [solving] the optimization problem"
* Line 244: "which could solve such [a] assignment"
* Line 288: can add a reference to d_sp


---

I don't think Figure 1 is informative.

---

Figure 2 (a) and (b) are in quite different styles. And the legend of Fig2(b) is sketchy. This could be improved.

---

Appendix C figure 1 is good, but can be improved. Agents in different teams should have clear difference. For example, opponent, ball and guard should use different shape rather than circle. I actually prefer to watch video, but unfortunately you don't provide video nor webpage.

---

Proposition 4.1 is boring. Maybe we can move it to appendix.

limitations: 

In Appendix D, the authors describe the limitations. 

I think a limitation is that, supposing URL methods (including SPD) perform bad when simply deploying the learned models to the test tasks without further fine-tuning, how to make URL method works in a complete reward-free setting. Previous works in single-agent RL, like DIAYN, shows that we can learn policy without any reward. This also relates to the next limitation.

The second limitation is that, I think we can incorporate diversity encouraging technique in single-agent with the SPD. By doing this, we can improve the intra-agent diversity as well as inter-agent diversity.
review_title: null

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: The authors proposed a MARL algorithm to learn generic coordination policies for agents with no extrinsic reward called Synergy Pattern Diversifying Oriented Unsupervised MARL (SPD). They utilized a graph representing the relationships of agents at each time step called Synergy Pattern Graph (SPG), and an episode-wise divergence measurement to approximate the discrepancy of synergy patterns. Results showed the capacity of SPD to acquire meaningful coordination policies, such as maintaining specific formations in Multi-Agent Particle Environment and pass-and-shoot in Google Research Football. Furthermore, they demonstrated that the same instructive pretrained policy’s parameters can serve as a good initialization for a series of downstream tasks’ policies, achieving higher data efficiency and outperforming state-of-the-art approaches in Google Research Football.
strengths_and_weaknesses: The strength of this paper is as follows:
* The proposed unsupervised MARL algorithm seems to be original, and they used the synergy graph to train team skills without rewards from the environment, which brings the agents good generalization ability in downstream tasks, and takes no extra cost in execution. 
* The experimental results demonstrate that SPD achieves better performance in MARL compared to conventional unsupervised RL approaches and shows great potential to learn synergy patterns with generalizability for downstream tasks.

The weakness of this paper is as follows:
* The presentation was sometimes unclear (please see below)
* The experiment descriptions were sometimes unclear (please see below)

questions: * L 84: no extra cost?
* L 244: utilize/an assignment?
* Algorithm 1 L15: Is eq. (2) correctly eq. (3)?
* The performances of CDS (Li et al. 2021, NeurIPS) in Figure 3 may be worse than expected (in the paper, CDS outperformed QMIX and QPLEX). I previously ran their code and it worked well. I know the experimental condition was different, but I want to know the reason (were there no code and hyperparameters for CDS?).
* There was no video at https://sites.google.com/view/spd-umarl.
* L328-329: “To avoid the effect of randomness, we repeat the visualization for 10 times for each skill.” It was not clear to me. What did the authors do?
* Appendix L83: The results show that none of the URL approaches, including our method SPD, achieve more than 75% on DSR. The values in Fig. 2 a seem to be 60%. Why did the authors mention 75%?

limitations: The limitations and potential negative societal impact were described in Appendices D and E, respectively.
review_title: null

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: The paper presents a method for unsupervised multi-agent reinforcement learning which uses diversity bonuses as an intrinsic reward.  The SPD method rewards diversity between _synergy pattern graphs_, which measure the similarity of the full set of agents' behavior.  The paper argues that diversity as measured between these graphs can capture the dependencies between agents better than promoting diversity in the state space alone.  The paper demonstrates improved performance in the Google Research Football (GRF) benchmark.

# Update after author response

Thank you for the well-considered responses and updated experiments.  The updated results provide a stronger support for the SPD method, and I have raised my score to reflect them.
strengths_and_weaknesses: ### Originality
 - To the best of my knowledge, the SPD method is a novel approach that combines diversity-based unsupervised RL approaches with a graph-based representation of agent interactions.

### Quality
 - The comparisons between SPD, DIAYN and WURL in section 5.1 use $d_{sp}$ as an evaluation metric, which seems incomplete.  Without establishing that $d_{sp}$ correlates with, say, better down-stream task generalization performance, it is difficult to be confident in conclusions drawn using it as a metric.  I would have liked to see these baselines (DIAYN and WURL) used in the experiments in section 5.2 as well.  Can we attribute the improved performance of SPD demonstrated in figure 3 to diversity bonuses in general, or specifically to the diversification of synergy patterns?

### Clarity
 - Although the SPD method is complex, the authors do a good job describing the approach, including describing the necessary background for understanding SPD. 
 - The discussion of the ablation experiments in section 5.1 and figure 2 is very light on details.  I am not sure what the reward scale is, what the precision on the solution means, and why these are relevant ablations to consider.
 - A diagram illustrating $G^{sp}$ and $d_{sp}$ could aid understanding, even though the descriptions are clear.

### Significance
The significance of the approach is hard to judge given the current experiments.  The approach seems to make advances on the state of the art in CTDE MARL approaches on GRF, but the concerns raised in the Quality section of this review above make it hard to know what to attribute the performance to.  
questions: Related to my concern above, what do you expect the relationship between $d_{sp}$ and downstream task performance to be?  Did I misunderstand why it should be a good metric on its own?  My rating depends mostly on this point, because the approach seems promising and the results are good on one benchmark, but it could be possible to achieve these results with more straightforward diversity methods.  Arguments in the paper suggest reasons why we should expect DIAYN and WURL to perform worse, but there is no experiment to back this up.  Since this is a major claim of the paper, I'd like to see it supported.
limitations: The authors address the limitations and potential societal impact well in the appendix.
review_title: null

Meta-review: metareview: Reviewers appreciated the paper's contribution of a novel method for unsupervised skill learning in MARL. While the scores were borderline, reviewers are mostly in favor of acceptance, therefore I recommend acceptance as well. Additional baselines and environments added during the rebuttal phase were important considerations in this decision.
confidence: Less certain
Decision: Accept