Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The aim of this paper is to train diverse populations of agents in the open-ended learning setting. To this end the authors introduce two loss terms that encourage behavioural diversity as well as response diversity. In addition they define a new evaluation metric for the performance of agent populations they call population effectivity. They carry out experiments on a synthetic non-transitive environment, the AlphaStar game as well as the Google Research Football game.

main_review: Positives:
* Overall the paper is well structured and not too hard to follow. 
* The two main contributions (the augmented training objective and the effectivity metric) are interesting and novel in this setup as far as I can tell.
* The experiments include relevant baselines and span a good range from synthetic to more real-world. Most of the results look promising.

Concerns:
* There are parts that lack more detail. For example, the setup of the AlphaStar game is not clear to me at all. From what I understand the authors have not trained AlphaStar from scratch but rather are using payoff matrices from pre-trained agents? This needs to be more clear in order to be able to judge the impact of the results. Another example of this is the matrix for the non-transitive mixture game should be described a bit more in the main text, to at least get an intuition about it’s structure beyond having been “delicately designed”.
* I am not sure about the results on the non-transitive mixture game. I am surprised by the performance of PSRO and in particular PSRO-rN which is aimed at finding diverse strategies. I might be misunderstanding the game (and, if so, this adds to my previous point about this intuition having to be communicated better to the reader), but would the modes of the Gaussians not be where we would want the trajectories to end? If this is the case why are none of the algorithms reaching them? I am also surprised there is no cycling in the trajectories, given the cyclic nature of the game.
* A lot of the paper is in the appendix. I am aware that there is a lot to include and there is a page limit, but I would make an effort to exclude anything that is less relevant from the main text and try to bring at least intuitions about what is specified in the appendix rather than just referring to it.

Suggestions:
* The first sentence of the paper “zero-sum games involve non-transitivity” is not correct. A zero-sum game with two strategies for example is not non-transitive. You can also take any transitive game P and P-P.T will still be transitive as well as zero-sum. I am assuming that the authors might not have meant it as a universal statement, in which case they should be careful when making general statements like this and this particular sentence should be changed (if indeed they did mean it as a universal statement, this could be a concerning indication of lack of fundamental knowledge about game theory).
* Related research that might be of interest in this area is a paper on diversity of populations [1].
* Some variables are not defined, like c and W in line 120. Even if this is notation that is defined in another paper, if the authors use an equation all variables should be explained.
* In algorithm 1 the star of theta in line 5 and in line 7 is not the same, use the same one as they refer to the same thing and otherwise this could be misinterpreted.
* In lines 200 and 208 write out ‘Behavioural diversity’ and ‘Response diversity’ (you can leave out the ‘Discussions on’ part).
* There are several spelling and grammatical errors throughout the paper, I would recommend giving it a thorough scan. Here are some examples: l.24 it’s zero-sum, not zero-sums, l.133 if \rho is *a* valid, l. 214 for practical implementation, l.269 ‘condict *an* ablation study. 

[1] Garnelo, Marta, et al. "Pick Your Battles: Interaction Graphs as Population-Level Objectives for Strategic Diversity." Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems. 2021.
limitations_and_societal_impact: The Authors discussed this appropriately.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This work proposes a novel framework for measuring diversity in (open-ended) multi-agent learning. Using this framework, they formulate objectives to encourage diversity at the policy and policy population level, achieving low exploitability, high population effectivity, and overall good performance in simple as well as relatively complex MARL problems.
main_review: This is great work!

### Clarity

The paper reads beautifully. I wasn't very familiar with the open-ended learning take on MARL, but the manuscript provided both a good and clear introduction to the topic as well as a very clean (and seemingly novel!) view on the problem. I thoroughly enjoyed going through it.

### Originality & Significance
 
I'm not extremely familiar with most on the existing literature on estimating diversity in MARL settings, but the overall proposed analysis framework as well as the obtained losses seem novel and well sound. *At the very least* the manuscript seems significant in bringing a fresh perspective on a few recent methods for population-driven MARL that have helped with generating very successful RL stories.

### Questions

L154:158: How does this actually differ form RED (or RND even) in practice? Furthermore, once the network is learnt on the dataset, does it remain fixed throughout the duration of the experiment, or does it get periodically re-learnt?

L169:170: Shouldn't $-i$ be assignable to a single opponent player? What value does it take in say a game with 3 or 4 players?

### Typos

L45: "like, in Maze" -- looks like a bad copy-paste.

L169: s/for an example/for example/
limitations_and_societal_impact: Strictly speaking, I don't think the manuscript provides a good overview of the limitations of the proposed framework, nor of any particular weakness in the experimental setting used.

Analysis on societal impact is also very limited (if not non-existent).

I would personally enjoy a discussion at the very least on what other types of losses could be potentially steam from utilising the BD / RD decompositions.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper focuses on approaches for producing diverse policies in single and multi agent reinforcement learning (RL). The authors first introduce Behavioral and Response diversity, with a single metric to represent each. They then present two mechanisms to evaluate the effectiveness of diverse populations of agents. Finally, they introduce a new algorithm and test it on a series of benchmark environments, showing the performance in terms of the newly introduced objectives as well as overall performance. The paper covers a large amount of material, and overall does a good job in explaining how each component relates, while the results are reasonably strong. My score is only a weak accept, because I believe in the current form it is a useful contribution to the field, but it could be made significantly stronger. There are more details below, but at a high level, it seems there is not actually much unification happening here, and at times the authors seem to re-introduce things. It is worth saying, my score is *more likely to increase than decrease* at this point, but of course that can change given author responses.

_______

Score raised to an accept from a weak accept, on the premise that many of the additional clarifications from the author response are included in the paper. 
main_review: Strengths

* The paper addresses an interesting problem, clearly motivated by non-transitive games which have been in focus with agents such as AlphaStar.

* The paper is thorough and rigorous in its definitions, which is clear to follow given sufficient time. The authors introduce their own notation to think about several well known methods and once the reader gets up to speed with this the rest of the paper is clear and interesting.

* The empirical results are clear and seem convincing, with the new approach clearly outperforming a strong set of baselines.

* The definitions of BD and RD make sense to me. This is an intuitive way to think about diversity metrics. 

* The hyperparameter ablations are a great addition, compared to many works which do not show this level of granularity. 

Questions & Areas for Improvement:

1. The paper fails to deliver on its core promise, to quote the abstract: "work towards offering a unified measure of diversity". Indeed, after categorizing diversity metrics into two classes, I expected to see some analysis explaining when they differ and when they are equivalent. I then expected to see a new metric or objective that provides many or all of the desirable properties of both classes of methods. Instead, the final outcome is rather unsatisfactory - the authors simply add both to the objective. In a sense, this is not unified, this is just adding two (very much distinct) pieces together. I think there are two ways to improve here. The first is to discover the novel diversity objective that truly unifies the methods. However, this is of course very hard. The second, would be to change the title to something like "Towards Unifying... " or "Demystifying..." because those are more appropriate for the contribution of the paper, which in a sense, lays the ground work for the new objective to be discovered. In this second case, I would still hope to see some analysis, either empirical or theoretical, of when these objective succeed and fail. 

2. Can you possibly explain the behavior in Figure 2? It seems that DPP-PSRO which uses Response Diversity, has a very similar profile to P-PSRO with Behavioral Diversity, and looks very different to P-PSRO with Response Diversity. Is DPP-PSRO classified correctly in Table 1?

3. In some cases the authors make things a little convoluted, and could explain the theorems in words, as they are often very straightforward observations (e.g. Theorem 1). 

4. The population effectivity metric looks like a robustness objective, but this is not mentioned. For example [1] focuses on minimax objectives w.r.t reward and of course this is very related, it is just about generalizing with a different degree of freedom. There is nothing wrong with PE not being 100% novel, it just should be more clearly compared to existing works.  

5. Limitations of the method do not seem to be thoroughly discussed anywhere. The checklist says yes, but I couldn't find it. 

Minor Comments/Typos:

-l.24: "Zero-sums" -> "zero-sum"

-l.83: "is a principle way" -> "is a principled way"

-l.119: "bisimulation metric" -> "bisimulation metrics"

-l.121: "build the metric" -> "build a metric"

-l.130: "state-action pair" -> "state-action pairs"

-l.166: "energy-based model" -> "energy-based models"

-l.320: "showed the most" -> "showed that most"

References

[1] Zahavy et al. Discovering a set of policies for the worst case reward. ICLR 2021
limitations_and_societal_impact: I could not find a detailed discussion of limitations.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper is concerned with learning in zero-sum Markov games, in which there are often non-transitive dynamics between policies/strategies (e.g., Rock beats Scissors beats Paper beats Rock ...). A common approach to avoid getting stuck in cycles or local optima when training in such domains is to encourage algorithms to discover *diverse* solutions or policies. 

This paper discusses and formalises how diversity measures can be split up in two broad categories: **behavioral diversity** measures, which measure whether different policies visit different state-action distributions, and **response diversity** measures, which measure whether different policies obtain different vectors of empirical outcomes against a population of opponents. For each of these two categories, the paper proposes a concrete measure and (approximate) methods to optimise them within a Policy Space Response Oracle (PSRO) framework. Additionally, the paper proposes a new Population Effectivity metrid, which is argued to be more fair and informative for evaluating the effectiveness of a population of policies than the Exploitability metric.

The additional diversity objectives are shown to improve training in several different domains.
main_review: **Originality**: to the best of my knowledge, there is a good amount of novel work in this paper, and an adequate discussion of related work.

**Technical quality**: The technical quality of the paper looks solid to me. I will note here that the most theoretical / math-heavy parts, like the proofs, seem beyond my ability and I would probably not easily spot any mistakes in them if there were any. I do feel that I was able to follow along well with the majority of the paper, at the very least on an intuitive level, and from that point of view I do not see many major issues. I only have the following two remarks:

1) Many parts of the paper refer to **unifying** measures of diversity, or providing a **unified** diversity measure: the title of the paper, the abstract, the introduction, Section 4, the conclusion, etc. Maybe I'm mistaken or forgetting about something here, but my understanding of the word "unifying" seems to be different from what's going on in this paper. When I see "unifying", I think of something more *general* (an algorithm, a model, a theory, etc.) that encapsulates multiple other more specific things (which were often previously viewed as being distinct things) as special cases. For example, I would think of TD(lambda) as an algorithm that unifies several other simple reinforcement learning algorithms, such as Monte-Carlo returns (special case with lambda=1) and one-step returns (special case with lambda=0). I do not see the behavioral and response diversity measures being unified in this paper, since they are essentially still two completely distinct objectives that can simply be added together (as in Equation 8).

2) In tables of results, such as Table 2, when some results are presented in boldface this is often interpreted as those results being the best of their row with statistical significance. But in Table 2, it appears that all the best results of every row are presented in boldface, even if their confidence intervals (or are they standard errors?) are overlapping. For example, in the first row, the 40.49 +- 0.07 interval for DPP-PRSO overlaps with the 40.54 +- 0.12 interval for P-PRSO w. BD&RD, but only the latter is in boldface. In these cases, either no result should be in boldface, or all the results for which the intervals overlap with that of the best should be in boldface.

**Clarity**: the paper is clear, well-written, easy to follow. I will just list a few small typos / points of confusion I found:

- Line 24: Zero-sums --> Zero-sum
- Line 45: why is Maze capitalised? Is this just about any arbitrary maze, or a specific environment named "Maze"?
- Line 255: "and B_i subset of Q_i" --> the Q symbol used here looks different from all the other Qs, is that intentional?
- Page numbers of reference [10] should be 586--593 instead of 1--8
- First point of the Checklist says "See Section ??"

**Significance**: I am not sure if many of the results for the matrix games in Table 2 can be considered significant, but the Google Research Football results in Figure 3 look more convincing. The theoretical insights in terms of diversity measures and Population Effectivity evaluation metric also look promising.
limitations_and_societal_impact: Limitations are adequately addressed (for example when approximations to optimisation are necessary).
review_title: null

Meta-review: This paper explores different methods for measuring population diversity and how they can be applied in open-ended learning. All reviewers agreed that it provides a valuable contribution. One important point that emerged from the discussion with reviewer QZCS was that the paper's title is a bit of an overclaim. The authors graciously agreed to qualify it by changing to "Towards unifying...".
Decision: Accept (Poster)