Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors propose a method for containing multiple distinct behaviours (or policies) in a single agent. To do this they store a dictionary of policies observed during training, where the key relates to returns observed during training (this is discretised to keep the buffer size reasonable). 

This is actually very similar to simply holding a population of agents during training. At the start of training the dictionary (size N)  is initialised with N random policies which are all selected randomly and trained with. RPM uses self-play from its buffer to train more agents. Unlike self-play or population-play their is no risk of degeneracy as values are only overwritten for agents which produce the same return.
strength_and_weaknesses: ### Strengths

* Idea is simple and good first step in the melting pot game
* Good ablations


### Weaknesses
* No explanation of the RPM update rule.
* Method makes a major assumption that return is enough to distinguish behaviour. A toy example of where this fails would be that grim trigger and tit-for-tat would get similar returns in IPD against a defective agent but intuitively have some variance in behaviour (e.g.  tit-for-tat is forgiving but grim trigger is not)
* Unclear how large a RPM buffer should be
* This method is computationally much more intensive than baselines, some analysis to count the different number of timesteps used in training or when convergence is achieved would also be reasonable.

clarity,_quality,_novelty_and_reproducibility: ### Clarity
* It is unclear how agents are chosen at evaluation time to be entered into the substrate.
* The focal agent's return is clearly dependent on the co-player trained with, how do you handle this instability during training?

### Quality
* Typos in "newly collected trajecotries and πθb"
* In the ablations diagrams you refer to  \phi type III but do not explain what this is.

### Novelty
Method is sufficiently novel - however it is very similar to [Fictitious Co-Play](https://arxiv.org/abs/2110.08176), the agents stored in the buffer are very similar to a population of agents and thus explaining the differences in related work could be useful. 

### Reproducibility
No code is provided, nor is method clear enough for reproducibility.
summary_of_the_review: Simple method but paper lacks clarity.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new self-play training framework called RPM that focuses on the diversity of the multi-agent population. Specifically, RPM builds the population by maintaining various levels of policies via ranking. Then, RPM trains focal agents that behave well with background agents sampled from the population. The extensive evaluations based on the melting pot domain show the generalization of RPM when interacting with unseen agents in the evaluation scenarios. 
strength_and_weaknesses: **Strengths:**
1. The paper is generally well-written and conveys the methods clearly. The figures are also helpful in understanding the method.
2. While RPM is a relatively simple algorithm based on the episodic return ranking system, it shows effectiveness in multiple scenarios. As such, the algorithm is directly applicable to other settings/methods.

**Questions:**
1. The problem formation and objective in Section 3 are closely related to meta-learning in MARL (Al-Shevidat et al., ICLR 2018; Kim et al., ICML 2021), where the goal is to train a meta-agent with a population of other agents such that the meta-agent can adapt well when interacting with a new agent at meta-testing. The main difference between this paper and meta-MARL is that the focal agents are not allowed to fine-tune their policies during the evaluation in this paper, while meta-agents are allowed to fine-tune their policies. Because both settings are concerned with generalization, I would like to ask discussion comparing the two settings. 
2. Would RPM benefit from using more complicated ranking systems (e.g., TrueSkill)?
3. Adding lines that denote optimal values in Figure 6 (i.e., if ideal generalization is possible) can help identify the gap and the amount of generalization performed by RPM.  

**References:**  
* Maruan Al-Shedivat, Trapit Bansal, Yuri Burda, Ilya Sutskever, Igor Mordatch, Pieter Abbeel. Continuous Adaptation via Meta-Learning in Nonstationary and Competitive Environments. ICLR 2018   
* Dong-Ki Kim, Miao Liu, Matthew Riemer, Chuangchuang Sun, Marwa Abdulhai, Golnaz Habibi, Sebastian Lopez-Cot, Gerald Tesauro, Jonathan P. How. A Policy Gradient Algorithm for Learning to Learn in Multiagent Reinforcement Learning. ICML 2021
clarity,_quality,_novelty_and_reproducibility: **Clarity:** The paper is well-written and conveys the main insights well.  
**Quality & Novelty:** I agree that RPM is new regarding the self-play notion. The setting and objective may overlap with multi-agent meta-learning methods.  
**Reproducibility:** The source code is provided to reproduce the results.  
summary_of_the_review: Overall, I have a positive evaluation of this paper (score of 6), and I will make a final decision on the recommendation after the authors' response.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers improving the generalization capability of MARL agents. The idea is to maintain an archive of policies based on their discretized returns. In each episode, agents from random return categories are selected to perform RL training, which ensures that each episode can contain diversified agent interactions. Experiments are conducted on the melting pot environment against a collection of baselines.

Although the idea of using policies of different skill levels for improved generalization isn't new in MARL, the execution of this idea in the setting of general multi-agent games is neat and intuitive. 


+++++++++++++++++++++++ post rebuttal +++++++++++++++++++++++
The authors have included additional results on the baselines, which makes the paper more compete. Therefore, I decided to update my score from 5 to 6. 

strength_and_weaknesses: ## Strength

The paper is clearly written and easy to follow. Although the overall idea isn't groundbreaking, it is still novel to store policies in a discretized memory and perform training over randomly sampled policies. This is algorithmically different from the classical way of using policy archives in MARL, which typically follows the framework of fictitious self-play. In addition, the selected testbed is sufficiently challenging. The proposed method could be well served as a baseline for the following works. 

## Weakness

### Missing citations

In the related work section, the authors claim that "_there is no method proposed to achieve generalization in MARL_", which, to the best of my knowledge, is not true. It is true that there isn't a systematic study on the setting of general sum and more than two agents, but there are indeed a lot of works on relatively more narrow domains. For example, [1] adopts the same idea of using past policies to generate diverse interactions so that the learned policy can generalize to humans. The difference is that [1] conducts two stages: i.e.,  first, create a policy population of different skill levels and then train an adaptive policy from scratch to compete with diverse partners so that it can generalize during evaluation. [2] also considers the stag hunt game and follows a similar training paradigm to [1] to train a policy that can adapt to cooperative or non-cooperative partners. [3] adopts a similar population-based training framework to this work but improves the generalization ability of policies by promoting policy diversity. I think the paper should also carefully discuss these related works in the paper. 

[1] Collaborating with Humans without Human Data, DJ Strouse, Kevin R. McKee, Matt Botvinick, Edward Hughes, Richard Everett, NeurIPS 2021. 

[2] Discovering Diverse Multi-Agent Strategic Behavior via Reward Randomization, Zhenggang Tang, Chao Yu, Boyuan Chen, Huazhe Xu, Xiaolong Wang, Fei Fang, Simon Shaolei Du, Yu Wang, Yi Wu, ICLR 2021

[3] Trajectory Diversity for Zero-Shot Coordination, Andrei Lupu, Brandon Cui, Hengyuan Hu, Jakob Foerster, ICML 2021

### Relationship to Fictitious Self-Play (FSP)
I have been carrying by the same question throughout the reading of this paper. Although I do see experiments between the proposed method and FSP, I could still hardly understand **why** (at least intuitively) FSP is worse than RPM. I think the paper can be much improved if this question can be carefully answered and discussed. Some of my thoughts on this question are listed below.

1. **The performance of FSP should be tuned**. In Fig 6, the performance of HSP is substantially worse than MAPPO and it is even worse than _random_. I checked the appendix, which states that HSP uses a surprisingly high past sampling rate of 30%. Particularly in the case of multiple agents, such a hyper-parameter choice could largely hurt MARL training. As a reference, [4] uses a 5% past sampling rate. I do think this hyper-parameter should be carefully tuned to ensure a fair comparison, considering the fact that FSP is perhaps the most important baseline to compare with. In particular, the RPM-random baseline achieves comparable performance to RPM in the prisoner's dilemma game while FSP is even worse than random. 


[4] Emergent Tool Use From Multi-Agent Autocurricula, Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, Igor Mordatch, ICLR 2020

2. **The motivation for using a discretized category (rank)**. I'm definitely convinced that we should run MARL training with partners with different skill levels. And, it is great to see in the ablation studies that RPM-random baseline works worse. However, I don't think the paper at any place **explains** and **motivates** why the use of a discretized rank is _necessary_. Intuitively, why wouldn't past sampling achieve the same effect? Note that RPM-random is indeed comparable to RPM in the prisoner's dilemma case. By contrast, why does RPM-random works poorly in pure cooperation? Note that random sampling achieves strong performances in the overcooked game [1], which is also a purely cooperative game. I do think some in-depth analysis should be conducted. 
A possible reason that I can imagine is as follows. Based on the histogram in fig 8(e), the distribution of policy skill levels is not uniform. Those high-reward policies are much rarer than sub-optimal ones. So a naive random sampling may hardly choose those high-reward policies, which accordingly makes training slow. This could be a fair argument. However, if we exclude those policies with the highest rewards (e.g., return > 10), those sub-optimal policies are distributed pretty much uniformly in fig.8(e) to some extent.  So, couldn't this issue (uneven distribution of skill levels) be just solved by FSP with a properly tuned past sampling rate? With a properly tuned rate, the probability of choosing a recent high-reward policy and choosing a poor past policy can be well balanced, if fig 8(e) is a generic diagram for most MARL applications. So, in addition to tuning the FSP baseline better, I would suggest the authors study the policy distribution over every scenario to have a better **understanding** of why random sampling would fail and why a discretized category is necessary. 

3. **A fair comparison**. This is a final and possibly repetitive comment. RPM requires careful tuning over the value of $\phi$, and RPM would simply generate RPM-random if $\phi$ approaches 0. Unfortunately, there isn't a generic way to choose a good $\phi$ (at least not in the current draft), so I would believe a similar amount of tuning efforts should be made for FSP on past sampling rates for a fair comparison. 

clarity,_quality,_novelty_and_reproducibility: The paper is in general well written and particularly easy to follow.

There is a small type saying $\phi$ is an integer (two lines above equation (2)). However, according to Table 2, this isn't the case. 

The reproducibility is good and the website is well-prepared. 

Regarding the novelty, I think the paper can be much stronger if the authors could provide an in-depth analysis of the necessity of the discretized categorization of policy skill level.


summary_of_the_review: This is a well-written paper with a neat idea. The current content is very close to the bar of acceptance in my opinion and can be further improved if more in-depth analysis can be provided.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a simple method called ranked policy memory (RPM) that can be plugged in any existing MARL algorithms to solve the generalization problem of MARL. The main idea of RPM is maintaining a look-up memory of the history rollout policies which are ranked by the training episode return. At each episode, the rollout policies are uniformly sampled from RPM. The objective of this process is to keep the diversity of agents' policies and resemble the the unknown policies that may appear in the evaluation scenarios. The performance of RPM is empirically verified by experiments and abnalation studies.
strength_and_weaknesses: ## Strength
1. This paper is generally well written and the description of the proposed method is clear.
2. The motviation of this paper is clear and I believe this is a meaningful work.
3. The proposed method is demonstrated to improve the performance of generalization.
4. The ablation study well spots the limitation of the proposed method, so that it is transparent and easy for the followers to improve it.
5. The comparisons to the prior works are sufficient.

## Weaknesses
1. The proposed method is so heuristic (though it cannot be a reason to reject it), so that it is unclear why it works.
2. Although the authors claim that the diversified multi-agent trajectories can resemble trajectories generated by the interaction with agents possessing unknown policies in the evaluation scenario, this explanation is unconvincing to me. The most critical reason is that the background agent is pre-trained, so it is possible that the policy space of trained agents **completely** deviates from the policy space of pre-trained agents (with no intersection). The authors should give a better explanation.
3. The proposed RPM is highly dependent on the choice of a hyperparameter $\psi$ as shown in ablation study. Could the authors give a brief proposal to address this issue?
4. As shwon in Fig. (e) in ablation study, the mode of the final distribution of keys of RPM is almost the mean of returns. It can be estimated that the effect of RPM could make the MARL policies adapt the average performance. This might lead to the issue as the authors discussed in the paper that MARL agents' performances will affect the evaluation performance.
clarity,_quality,_novelty_and_reproducibility: The clarity of this paper is good, since the whole paper is well written.

The novelty of this paper may not be adequate, since it is just an intuitive extension from the prior self-play framework with no reasonable explanations.

The originality of the paper is moderate as far as I know. However, I am not sure whether the similar idea has appeared in the past (since it is so direct and intuitive)?

The reproducibility of this paper is good, since it provides both codes and experimental setups.

Overall, the quality of this paper is not bad.
summary_of_the_review: The proposed method in this paper performs better than the baselines and it is demonstrated in the ablation study that it should be effective. Nevertheless, the principle of the effectiveness is blurry.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposes a new MARL algorithm called RPM which maintains a memory of a diverse set of policies using the returns as keys. Experiments on the melting pot environment show that the proposed method is better than other existing algorithms.

Overall this is a solid idea with no major issues. There was one concern about the idea being a heuristic but that cannot be a reason for rejection (as the reviewer also agrees). It works well in practice and not every ML paper has a sound theory. The authors addressed all the concerns of the reviewer and added more results and related work.

I recommend an acceptance.
justification_for_why_not_higher_score: It is an interesting idea that works well in practice. The idea is intuitive and is not totally new to be considered for a spotlight.
justification_for_why_not_lower_score: There is no single solid reason to reject the paper. The authors have addressed all the concerns of the reviewers and the reviewers have accepted them as well with one of them increasing their score.
Decision: Accept: poster