Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper aims to address the important problem of training AI agents in multi-agent games. Standard self-play training leads to agents that overfit to a particular partner, and even naive population based training may not help much if the population is not very diverse. A number of recent works have looked into generating diversity in the partner strategies so that population based training methods can work better. By covering a diverse set of trajectories/policies, it is more likely that coordinating with a new partner (perhaps a human) at test time will fall in-distribution relative to our training set partners.

The paper proposes a population diversity metric based on cross-entropy between different pairs of agents in the population. They optimize a lower bound to this metric based on the population entropy. They also propose a 'prioritized sampling' procedure that determines which partner in the population the ego-agent should train with. They experiment on the game of Overcooked, compare with TrajeDi, and run a human experiment to check performance of coordination with humans at test time.
main_review: Strengths
The problem is important, and testing it on Overcooked along with a human experiment is a good domain for this exploration.
The population diversity metric is also reasonable, and seems like a good quantity to include as part of an auxiliary loss.
The human experiments are neat (although I am left wondering why TrajeDi is not compared with in the human experiments).


Weaknesses

Though the paper shows the population entropy to be a lower bound of the population diversity, the gap is huge (factor of n^2). Looking at the entropy values in Table 1, the lowest value is about 0.9 and the highest is about 1.8 (only a factor of 2). As such, even for the smallest choice of n=2, it seems that the lower bound ends up being nearly useless. I'm surprised the paper actually proposes to train based on the lower bound. To me, optimizing an approximation of the population diversity seems much more promising.

I also thought section 3.4 was not well motivated, and it is unclear what the takeaway of this section is. On one hand, it's unclear why we are interested in optimizing the worst performing partner, rather than the average reward of the partners. Moreover, looking at the supporting claims for Eq 10 (Lemma 4), I don't have intuition as to why this claim is not completely trivial -- that training with the lowest performing agent improves the minimum reward over all agents (which seems obvious). Related to this, why does the paper claim uniform sampling "does not provide any guarantees" (can't we also claim that training with all agents uniformly increases the overall reward?)

I'm also not convinced by the discussion in Q1 regarding Figure 3. It does not appear that the entropy is converging to a higher value. In fact the plots are very spiky and hard to interpret. Judging from Table 1, however, it does appear that pushing for population entropy does impact the environment reward quite a bit, contrary to the claims in the paper that "the reward does not decrease much".

I found the writing to be poor. There are many choppy parts that break the reader's rhythm such as "less 'panic'", "While uniform sampling does not provide any guarantee on the worst case.". There are also very vague statements, such as "With prioritized sampling, we make the collaboration between the AI agent and any agent in the population as good as possible in general". It's unclear to me what precise claim they are making. Of course there are no guarantees regarding the global optimum, so what precisely does it mean to "make... as good as possible in general"?
summary_of_the_review: The paper tackles an important problem, but leaves much room for improvement. The population entropy should be backed up by (toy) experiments that analyze the effect of the quantity, since on paper it seems that the lower bound exhibits a huge gap compared to the empirical range of entropy values observed in Table 1. The experiments can also be improved (TrajeDi is missing in the human experiments), and the current results are hard to interpret (the reward in Table 1 does drop significantly when the entropy term is pushed up).   Improving the overall writing would also raise the paper's potential impact.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors propose a maximum entropy objective that can be applied to population-based multi-agent training in an RL setting to create a population of multi-agent policies that can more easily cope with zero-shot introductions of "unseen" policies. They formulate a framework for successfully applying this objective at scale by working out a proxy objective, and apply the method to the multi-agent Overcook environment tasks.
main_review: 
I am struggling to come up with sound overall grade for this paper. In short:

1. The method seems to be technically sound, building on simple and relatively popular ideas in both multi-agent and single-agent RL in an interesting way. 

2. It seems to be effective when tested against comparable baselines in an interesting multi-agent environment.

3. The submission does a good job at providing enough details (and code) to enable quickly reproducing the work.

However:

4. The experimental section is relatively weak:

    a. Firstly, multi-agent Overcook is a relatively recent benchmark all things considered (and I would definitely not define it "popular"). There are a variety of choices, ranging from toy-like environments (matrix games, OpenAI's MPE) to complex ones (SMAC, Hanabi, DM Lab) that are popular in the recently wildly exploding MARL literature that could also have been employed, and possibly preferred. This would have enabled to understand the significance of the results compared to state of the art zero-shot coordination.

    b. This is particularly a problem when comparing this manuscript with Lupu et al., 2019, which the authors acknowledge being comparable work. Considering that they are comparing their methods against theirs, it seems unreasonable not to benchmark MEP on at least some of the toy problems proposed in that work (whilst I would accept the authors not trying to compete with their well-tuned Hanabi results, as that would result in quite a lot of potential work).

5. The focus on AI-human coordination seems a little weird. In principle this paper is proposing to increase the diversity of states seen by the agent policy by maximising the types of behaviours generated during training time. This means that the method is applicable to be tested against any kind of out-of-distribution(-ish) agents. This is not a huge issue, but implies that the experimental section could have focused more greatly on undestanding the space of ad-hoc policies over which it is more robust vs possible failure cases. In my opinion, generating an adversarial out of distribution set of agents to test against would have been more effective than qualitatively analysing a comparably small quantity of human trials.

6. The paper at times is unnecessarily handwavy, unclear, or makes dubious statements that are not well backed up by the literature. Here's some examples:

   a. In the introduction, it is stated that self-play is the "mainstream method for building state-of-the-art AI agents" (without reference), but self-play makes for a relatively limited amount of work when looking at the broad RL / MARL literature. I would argue that it is _barely_ mainstream, given the implementation complexity of even its simplest form. It is also stated that "self-play-trained agents are very specialized", but this is not a well understood property of PBT, and in practice doesn't seem to have significantly affected performance when properly done (see e.g. Alphastar).

   b. It is claimed that "prioritized sampling [of agents policies from the population] [makes] the collaboration between the AI agent and any agent in the population as good as possible in general" -- I don't understand how to interpret the sentence: is the manuscript saying that prioritized sampling is generally optimal (a fairly strong claim!) wrt. learning with PBT for cooperative MARL? How does this interact with the fact that the schema utilises a particular ranking system that might be more or less compatible with the task?

### Nits

- Generally: the [...] RL -> [...] RL
- Section 1: prioritized sampling [of what?]
- Section 1: the experimental section is not a contribution of the work -- there's nothing intrinsically new about how MEP was tested, as far as I can see?
- Section 2: modes of sub-optimal -> modes of optimal (?)
- Section 3.1: what do incentive and multi-modal mean here?
- Section 3.4: the first paragraph feels off in terms of syntax / punctuation.
- Figure 3: hard to interpret -- it feels like it could have been reduced to two plots by grouping wrt. y-axis and alpha.
summary_of_the_review: Overall, the manuscript presents an idea that seems compelling and useful, but the experimental section doesn't provide enough signal to compare this method against the literature. This makes my recommendation borderline at this point, so I'm looking forward to discussing the manuscript with the authors and the rest of the reviewers to understand how to improve it towards possibly acceptance.

---

Bumped up score to weak accept.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper tries to find a new approach by enforcing the diversity in multi-agent RL  via the maximum entropy to address the zero-shot human-AI coordination problem. More specifically, in the proposed Maximum Entropy Population-based training (MEP) framework,  the authors choose population entropy as an efficient surrogate objective and use the prioritized sampling. The empirical results on the overcooked show that MEP outperforms other baselines with both simulated and real human players. 

main_review: Strength:

1. The paper is well-written and easy to follow.
2. The idea of combing the population entropy during the training is interesting, which considers both agents' individual diversity and pairwise diversity.

Concerns:
1. The authors propose a good way to promote the policy diversity in multi-agent RL, and this is straightforward that the diversity policy would benefit the zero-shot human-ai coordination. However, I think policy diversity is a general method that can be useful in many other problems, not only limited to human-ai coordination. Therefore, I think the authors can discuss the broader impact of the paper and clarify more about why test this method on specific human-ai coordination problem.
2. The prioritized sampling + entropy population seems important to train the diverse policy, and an ablation study to investigate how each component works would be better.
3. Some important references about diversity in population-based multi-agent RL are missing, like [1,2,3]. It would be good to discuss the relationship between the proposed method and the diversity promoting solutions in the PSRO framework.

[1] Balduzzi, David, et al. "Open-ended learning in symmetric zero-sum games." International Conference on Machine Learning. PMLR, 2019.

[2] Nieves, Nicolas Perez, et al. "Modelling behavioural diversity for learning in open-ended games." arXiv preprint arXiv:2103.07927 (2021).

[3] Liu, Xiangyu, et al. "Unifying Behavioral and Response Diversity for Open-ended Learning in Zero-sum Games." arXiv preprint arXiv:2106.04958 (2021).


Typos & Questions:
1. Algo. 1 gives a detailed algorithm procedure, but I can still be confused about obtaining the initial population/ policy pool? Is it a fixed policy pool, or would it be expanded by adding the new learned policy during the training?
2. Page 5: The repeat 'Environment' sub-section names of the last two paragraphs.
summary_of_the_review: This paper presents an interesting solution to train the diversity policy with a population, but more clarifications (as stated above) are required.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes an approach for training agents that are capable of ad hoc coordination with humans. The method combines an entropy based objective with a method for prioritizing partner selection. Results on the Overcooked domain show improved performance over a series of baselines.
main_review: At present I do not believe this paper should be published at ICLR, for the following reason: it claims to present a novel approach yet it simply combines two previously published methods (TrajeDi and PFSP). The framing of the method is incorrect, it does not cite PFSP until related work (not in Section 3.4) and it claims TrajeDi is "concurrent" which is not true. TrajeDi was presented at AAMAS 2021 (in May) and again at ICML 2021 (in July). This to me is not concurrent. To be concrete on the differences, the TrajeDi objective is almost identical, when the $\gamma$ parameter is set to zero. Meanwhile, PFSP uses almost the same prioritization scheme, but the only difference is that it is used in competitive games vs. cooperative.

However, I believe there is material in this paper that is worthy of publication, and a simple reframing/restructuring may be sufficient for the paper to be a useful contribution. Indeed, the paper does present novel theoretical results, a novel *combination* of existing methods in a new setting (since PFSP has only been used in competitive settings until now), and interesting experiments including testing their agents with humans. This could be a good paper if it reduces claims of novelty and instead focuses on how it builds on these previous works. **If significant changes are made to the claims in the paper and presentation of the methods I would be happy to raise my score**.

More Detailed Comments:
* The ablation studies are useful. Particularly the inclusion of the prioritization scheme with TrajeDi. Which value for $\gamma$ was used for TrajeDi? I would guess it is using $\gamma=1$ which means the results show us the difference between action diversity and trajectory diversity, which is an interesting result, but likely problem specific. What happens if you use other hyperparameters for TrajeDi?
* Figure 3 has a lot of redundancy. I would move both the episode reward curves onto the same plot and also move both of the entropy curves onto the same plot, then use the colors to differentiate between the methods and a shared legend. Then have the name of the plot on the title (across the top) rather than as a y-axis label.
* Missing baseline: Off Belief Learning (Hu et al 2021) is the state-of-the-art method for ZSC in Hanabi. It would be interesting to see how it performs here. At minimum it should be cited.
* For the hyperparameter studies in the Appendix, it would be great if we can also compare different configurations on the same plots with the same axis. 
* As always, it is great that code is included.
* The human experiments are interesting. However, it seems the baselines are reduced. How does TrajeDi perform here? Does the addition of PFSP impact the human coordination? It seems like there are a lot of unanswered questions. Nonetheless, as it is this is a strong result.
* There are no discussion of limitations in the paper. Honest discussion of this would make the work stronger. For example, how would it work with larger population sizes and higher dimensional problems (such as Hanabi).
* Figure 5 - my guess is the bolding just means a higher average, without considering the error bars. It is better to only bold if the error bars do not overlap.
summary_of_the_review: The paper is interesting and well written, and addresses an important problem. The method itself combines two known methods (TrajeDi and PFSP) but does not provide sufficient credit, since it claims TrajeDi is "concurrent" and it only discusses PFSP in related work. Accurately positioning the new contribution w.r.t the previous would make this a solid contribution.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The authors focus on training agents for zero-shot human-AI coordination on Overcooked. They propose to first train a population of agents with a population entropy bonus, and then train another agent as the best response to the population, using a prioritized sampling approach that focuses more training on the worst performing pairs. They evaluate their agent and some baselines and ablations both with a human proxy model (i.e. an agent trained on human-human gameplay data with behavioral cloning) and also a smaller subset of their agent and baselines with real humans on Mechanical Turk. Their method performs as well or better in terms of game score than the baselines and ablations presented.
main_review: STRENGTHS

The high-level motivation of injecting diversity into partner populations is a sound and important one for human-AI coordination. The paper goes beyond just generalization to held-out agents and evaluates with real humans, which I think is crucial for this line of work. The authors include in their supplementary data videos of gameplay, and additionally discuss qualitative aspects of agent behavior, which I found useful in guiding intuition.

WEAKNESSES

There are several crucial missing or misunderstood ablations and baselines.

**Misunderstood baseline - TrajeDi**: the JSD term in the authors' population entropy bonus in equation 7 is just a special case of TrajeDi with gamma=0 (see equation 5 and discussion following in the TrajeDi paper). Thus, the population entropy bonus just amounts to adding the usual (per-agent) entropy bonus to TrajeDi. Can the authors comment? In addition, I could not find the hyperparameters or tuning procedure for the TrajeDi baseline. What value of gamma was used and how was it selected? What size population was used for TrajeDi? Comparing Fig 4a and 4c, it looks like the TrajeDi agent performs significantly worse than self-play, which suggests it was poorly tuned.

Several times the authors suggest they compare to "state-of-the-art" baselines, but the two methods that to my knowledge have a claim to this are not included.

**Missing baseline #1 - PPO_BC**: while the authors include several baselines from the Carroll et al 2019 paper, they for some reason do not include the best-performing one - the best response to a human BC model, PPO_BC. The authors might rightly protest that the comparison wouldn't be exactly apples to apples, since PPO_BC gets to use human data in training. For this reason, I don't think its a prerequisite of a human data-free method to *beat* PPO_BC, but it is still an important, informative, and easy baseline to include for comparison.

**Missing baseline #2 - FCP**: more recently, Strouse at al 2021 (https://arxiv.org/abs/2110.08176) introduced fictitious co-play (FCP), which achieved state-of-the-art human-AI coordination on Overcooked without human data, even seemingly beating the human BC model best response agent above. FCP similarly involves a two-stage training process of first training a diverse set of partners, and then training a best response to them. However, FCP achieves diversity solely through seeds of self-play, and taking checkpoints from different points of training (beginning, middle, and end). Strangely, buried in appendix E, the present authors mention that they too train their best response agent with multiple checkpoints of their partner population, again from the beginning, middle, and end of training. First, this seems like an odd and important detail to bury in an appendix and not mention in the main text. Second, it is an important enough detail to deserve an ablation (which the FCP paper did). Moreover, the combination of omitting mention of FCP while simultaneously using an eerily similar trick and not mentioning it in the main text looks pretty suspicious. In any case, from what I can tell, FCP is essentially the authors' present setup but with alpha=0, beta=0, and a bigger population (N=32 vs N=5) (though the RL algorithms also differ, i.e. VMPO vs PPO). In other words, if the authors use larger partner populations, are the population entropy bonus and prioritized sampling still important?

**Missing ablation #1 - past checkpoints**: as mentioned in the paragraph above, the authors mentioned in appendix E that they train with multiple checkpoints of their partner population. That seems like an important detail to ablate.

**Missing ablation #2 - two terms in population entropy**: the authors' population entropy objective (equation 7) contains two terms - a JSD term and the usual per-agent entropy bonus. The latter is a standard addition in many RL setups. The alpha=0 ablation in Figure 4b turns off both the JSD and per-agent entropy terms together. Thus, it is unclear whether the JSD term, the per-agent entropy bonus, or the combination is important.

**Question about uniform sampling ablation**: I was surprised to see this version do so poorly. Is it just that training takes a bit longer with uniform sampling? Had this agent converged? I couldn't find learning curves for this ablation.

**Missing baselines and ablations in human experiments**: none of the important baselines or ablations were evaluated with humans. While results with the human proxy model are helpful and suggestive, I think its important to include the key baselines and ablations in the human experiments as well, i.e. TrajeDi, alpha=0, beta=0, and the other baselines and ablations mentioned above.

**Between-subjects design**: This worries me, since I'm guessing the evaluation of the MEP agent and the original Carroll et al 2019 agents took place at least two years apart, and may have been performed by different authors. Unfortunately with human evaluations, many small details matter, such as server lag, UI, and sample population, all of which are hard to control for when evaluating two years apart. Could the authors provide additional justification for how they ensure the evaluations are identical? If not, and since I would like to see other baselines and ablations evaluated with humans anyway, perhaps it would be easy to re-evaluate SP and PBT.

Lastly, a few more minor points:
1. Structurally, I found section 3.1 and Theorem 1 unnecessary. It would be simpler to just start their narrative with equation 7, which at least to me is more well motivated than equation 2 anyway.
2. The JSD term in equation 7 is also closely related to the Emergence of Individuality (EOI) reward of Jiang & Lu 2021 (https://arxiv.org/abs/2006.05842), since the JSD term can also be understood as the mutual information between agent index and action choice, conditioned on state, or I(i;a|s).
3. In the answer to Question 1, the authors state that as alpha increases from 0 to .01, the population entropy increases while the reward barely decreases. However, from what I can tell, the changes are of similar magnitude, with reward dropping about 20% and entropy increasing 20%, so this seems like a misleading claim.
4. In the answer to Question 3, the authors state that MEP outperforms SP and PBT in all environments. However, the error bars seem to overlap on Forced, so I might change this to say "performs as well or better."
5. In the intro, are cooperative games and emergent communication really "real world applications"?
6. Tylkin et al 2020 (https://econcs.seas.harvard.edu/files/econcs/files/tylkin_neurips20.pdf) is relevant for citation and discussion on training agents for human-AI coordination.
7. MAVEN from Mahajan et al 2019 (https://arxiv.org/abs/1910.07483), as well as EOI mentioned above, are missing related work on applying population diversity-based methods in the multi-agent setting.
8. TrajeDi is described as "concurrent" work, but the paper has been out for several months. "Concurrent" is I suppose of debatable definition, but I think its more appropriate for work that is in submission at the same time.
9. There are many typos and grammatical errors in the paper. They did not damage readability for me, and I do not penalize the authors for this, but the paper would benefit from a proofreading. Some examples: "from the max ent RL" -> "by max ent RL" (abstract), "assistant" -> "assist" (paragraph 1 of intro), "use" -> "using" (paragraph  4 of intro), "incentive" -> "diverse"? (paragraph 1 of sec 3.1), "unbound" -> "unbounded" (last paragraph of sec 3.1), "Compare" -> "Compared" and "Take" -> "Taking" (paragraph after equation 6), "panic" -> "panicked" (sentence before sec 3.4), etc etc.
summary_of_the_review: There are several crucial missing baselines and ablations and clarifications before I think the paper is ready for publication. However, pending their inclusion and a review of the new results, I am very open to raising my score to an accept.
review_title: null

Meta-review: This paper has several issues:
(1) The empirical results were incomplete and hard to interpret.
1.a The paper uses non-standard benchmark domains making comparisons with results in the literature very difficult. The paper does not use the same environments as related baselines they build on. Some progress on this last point was made during the discussion period---well done authors!
1.b The experiments did not sweep key hyperparameters of the TrajeDi baseline, and generally did not comment on nor ablate several other potentially important hyperparameters and design choices
(2) the proposed method is very similar to another called TrajeDi and the paper and results don't clearly show why the modification of TrajeDi is significant (see #1). The paper initially claimed the TrajeDi was a concurrent submission but one reviewer pointed out the work was published in May 
(3) writing and structure could be improved. In addition some inaccurate statements could be cleaned up
(4) The algorithm is more generally applicable beyond human-AI coordination and the reviewers found it odd the paper did not focus on this

In addition, the authors did not respond to several of the reviewers responses. This made it difficult for the reviewers to increase their scores. Several reviewers found the work intriguing, but its not ready yet
Decision: Reject