Maximum Entropy Population Based Training for Zero-Shot Human-AI Coordination
Authors: Rui Zhao
Jinming Song
Hu Haifeng
Yang Gao
Yi Wu
Zhongqian Sun
Yang Wei
Venue: ICLR 2022 Submitted (2022)
Keywords: Human-AI Coordination
Reinforcement Learning
Zero-Shot Human-AI Coordination
Deep Reinforcement Learning

Abstract: An AI agent should be able to coordinate with humans to solve tasks. We consider the problem of training a Reinforcement Learning (RL) agent without using any human data, i.e., in a zero-shot setting, to make it capable of collaborating with humans. Standard RL agents learn through self-play. Unfortunately, these agents only know how to collaborate with themselves and normally do not perform well with unseen partners, such as humans. The methodology of how to train a robust agent in a zero-shot fashion is still subject to research. Motivated from the maximum entropy RL, we derive a centralized population entropy objective to facilitate learning of a diverse population of agents, which is later used to train a robust AI agent to collaborate with unseen partners. The proposed method shows its effectiveness compared to baseline methods, including self-play PPO, the standard Population-Based Training (PBT), and trajectory diversity-based PBT, in the popular Overcooked game environment. We also conduct online experiments with real humans and further demonstrate the efficacy of the method in the real world.

Under review as a conference paper at ICLR 2022
MAXIMUM ENTROPY POPULATION BASED TRAINING FOR ZERO-SHOT HUMAN- AI COORDINATION
Anonymous authors Paper under double-bling review
ABSTRACT
An AI agent should be able to coordinate with humans to solve tasks. We con- sider the problem of training Reinforcement Learning (RL) agent without using any human data, i.c., in a zero-shot setting, to make it capable of collaborating with humans. Standard RI. agents learn through self-play. Unfortunately, these agents only know how to collaborate with themselves and normally do not per- form well with unseen partners, such as humans. The methodology of how to train robust agent in zero-shot fashionn is still subject to research. Motivated by maximum entropy RL, we derive a centralized population entropy objective to facilitate learning of a diverse population of agents, which is later used to train robust AI agent to collaborate with unseen partners. The proposed method shows its effectiveness compared to baseline methods, including self-play PPO, the stan- dard Population- Overcooked game environment. We also conduct online experiments with real humans and further demonstrate the efficacy of the method in the real world.
Training (PBT), and trajectory diversity-based PBT, in the
INTRODUCTION
Deep Reinforcement Learning (RL) has gained many successes against humans in competitive games, such as Go (Silver al. 2017). Dota (OpenAl 2019), and StarCraft (Vinyals et al. 2019a). However, it still remains a challenge to build AI agents that can coordinate and collabo- rate with humans that the agents have not seen during training Klliman--Weiner
| 2016 Lerer & Peysakhovich, 2017] Carroll et al. 2019 Shum et al. 2019 Hu et al. Knott et al.) 2021) Zero-shot human-Al coordination is particularly important real-world applications, such as co- operative games (Carroll et al.) 2019). communicative agents (Foerster et al. 2016). self-driving
vehicles (Resnick et al. 2018), and assistant robots (Andrychowicz et al.) 2018). Ultimately, we want to build Al systems that can assist humans and augmenting our capabilities (Engelbart 1962
Carter & Nielsen 2017) to make our life better.
The mainstream method for building saate-of-the-aee AI agents is through self-play reinforcement learning (Tesauro) 1994, [Silerr et al.) 2017). Self-play-trainee agents are very specialized, and therefore suffered significantly from distributional shift when paired with humans. For example, in the Overcooked game, the self-play-trainee
agents only use a specific pot and ignore the others. However, humans use all pots. The Al agent ends up waiting unproductively for the human deliver a soup from the specific pot, while the human has instead decided to fill up the other pots (Carroll al. 2019). Since the AI agent has only encountered its own policy during training, undergoes distributional shift when it is paired with human players.
We explore how to design a robust and efficient approach train agents for zero-shot human-Al co- ordination. To that end, we draw on the advances in maximum entropy RL (Haarnoja et al. 2018 18b)
diversity (Eysenbach et al.) 2019), and Multi-agent RL (Lowe et al., [017 Foerster et al. 2018
First, maximum entropy RL. augments the standard reward function with an entropy
miztion
term and provides a substantial improvement in exploration and robustness (Ziebart et al.
2008
Toussaint 2009 Ziebart 2010: Rawlik et al.) 2013 Fox et al.) 2015 Haarnoja et al. 2017 7 20 8b Zhao et al. 2019). For population of agents, we use the maximum entropy bonus to encourage individual diversity, i.c., each agent's policy to be diverse and exploratory. Secondly, diverse and distinguishable behaviors (Eysenbach et al.] (2019), we further utilize the sum of cross- entropy terms across all agent pairs in the population encourage pairwise diversity. We define the
acquire

---

Under review as a conference paper at ICLR 2022
combination of individual diversity and pairwise diversity as population diversity. Thirdly, analog to multi-agent RL (Lowe et al. 2017: Foerster et al., 2018). the population diversity is calculated in centralized fashion. Each agent in the population rewarded to maximize the centralized popula- tion diversity. Subsequently, we derive a safe and computationally efficient surrogate objective, i.e., population entropy, which is proven to be lower bound of the original population diversity objec- tive. The population entropy is defined as the entropy of the averaged action probability distribution conditioned on the state across all agents in the population. Eventually, we train a new agent col- laborate with each agent in the diversified population using prioritized sampling of agents policies from the population based on the learning progress (Schaul et al.) 2016 Vinyals al. 2019a Han et al. 2020). The newly trained AI agent encounters diverse set of strategies and is in general more robust to human behaviors (Pan Yang 2009: Tobin et al. 2017] Andrychowicz et al. 2018). We
evaluate the proposed Maximum Entropy Population-based training (MEP) framework in testbed
based on the popular Overcooked game (Ghost Town Games
2016).
Our contributions are three-fold. First, based on the novel population diversity objective that con- siders both agents' individual diversity and pairwise diversity, we derive a safe and computationally efficient surrogate objective, i.e., the population entropy. Secondly, we develop the MEP frame- work, which comprises training a diversified population and using this population to train a robust AI agent. Last but not least, in the experiments, We show MEP's superior performance, by compar- ing it with state-of-the-arr baseline methods. To further verify the improvements, we conduct online experiments with real humans.
PRELIMINARIES
Markoy Decision Process: A two-player Markov Decision Process (MDP) is defined by tuple M = (8, [A P, y, R) (Boutilier, 1996). where S is set of states; A is a set of the i-th agent's actions, where i E [1,2]:P P|: is transition function that maps the current state and all agents' actions to the next state; 7 is the discount factor; It is reward function. The i-th agent's 's policy is (9). A trajectory is denoted by The shared objective is to maximize the expected sum rewards, which is E,, [,, R(s,, at)]. where a (a aj a(²)). We can extend the objective infinite horizon problems by the discount factor y to ensure that the sum of expected rewards is finite.
AI Agent, Population, and Human: Throughout this paper. we use the phrase Al agent to explicitly mean the agent that plays the AI role in human-AI coordination. The population of agents is used to train the Al agent to make capable of cooperating with different partner agents. The human policy represented as (HH) and a model of the human policy is (HH), The AI agent is denoted as (A4).
We use the Overcooked environment (Carroll et al. 2019) as the human-Al coor- dination testbed, see Figure 2 In the Overcooked game, to have a high score, it naturally requires coordination and collaboration between the two players. The players are tasked to cook soups.
Environment:
Maximum Entropy RL: Standard RL maximizes the expected sum of rewards EE, E, R(se, ac)]. At the beginning of learning, almost all actions have equal probability. After some training, some actions have a higher probability in the direction of accumulating more rewards. Subsequently, the entropy of the policy is reduced over time during training (Mnih et al. (016).) Maximum entropy RL augments the standard RL objective with a maximum entropy term (Ziebart, 2010, Haarnoja et al., 2018b), which gives a reward to the agent if it selects the non-dominate actions during training, and the higher the reward favors more exploration. The maximum entropy RL objective is defined as:
((T) E E, Σ H(ss, ar) + aH((T( (s:))
The parameter a adjusts the relative importance of the entropy bonus against the reward and con- trols the stochasticity of the optimal policy. The maximum entropy RL objective has a number of advantages. First, the policy is incentivized to explore more widely. Prior works have demonstrated improved exploration using the maximum entropy RL objective (Haarnoja et al. 2017 Schulman jt al. 7a) Secondly, the policy can capture multiple modes of optimal behaviors. In situations where multiple actions are equally important, the policy will give equal probability mass to those actions. Lastly, recent works have shown improved robustness of the policy trained with maximum entropy RL (Haarooj et al. 2018a 2019)
2

---

Under review as a conference paper at ICLR 2022
Algorithm 1: Maximum Entropy Population
POPULATION [ x
while not converged do
Sample agent from population:
Sample an agent from the pupulation
Evaluate each policy population
π
(+) { , ..... _,,,, x()}}
for to steps eepisode eee do
Sample action 0, 7 (a, (t))
AGENT dt (0) (aels))
POP ENTROPY (..(ss)))))
Step environment $1+1 ~ p(5c+1 st. oz).
Calculate the population entropy reward and combine it with the task reward:
L'ddate policy the task and entropy reward
= , a+) (og( (s)))
Update policy (+) to maximize E, [r].
Maximum Entropy Population: We train each agent in the population to maximize its task reward well as the population entropy reward to attain maximum entropy population.
Figure I:
3 METHOD
In this section, we first define the population diversity objective, which includes the policy entropy and the pairwise difference among policies. Secondly, we derive a safe and computationally efficient surrogate objective, i.e., the population entropy, for optimization. Thirdly, we illustrate the MEP framework, which comprises two parts: training a maximum entropy population and training a robust Al agent via prioritized sampling using the population.
3.1 POPULATION DIVERSITY
Motivated by maximum entropy RL, we want to make the policy population exploratory and diverse. First, by utilizing the maximum entropy bonus, encourage each policy itself to be diverse and multi-modal. Secondly, encourage the policies in the population, {m(1), complementary and mutually different, we naturally utilize the cross entropy objective (Murphy) 2012). Formally, define the Population Diversity (PD) the combination of the of the entropy each agent's policy and the sum the Cross Entropy (CE) between each pair of agents in the population. Mathematically,
T(7)3, }. to be
PD((=()) (1) (2) ..... x (n) s(s))
Σ> CE(T (st), 5 (sc)) + Σ H(m ( (.1s)),
(2)
where cross entropy (CE) and entropy (7t) are defined as follows:
CE(T() (s2),, (5)))((1) (. = Σ
π ( (aclse) (a.ss))
(3)
aEA
H(x (s)))) = Σ aeA
(8) π
(:) log म ( (aglst).
(4)
This objective not only captures single agent's diversity but also encourage multiple agents to be far from each other. However, the population diversity objective not safe to be maximized as a reward function, since cross entropy is unbounded. Besides, evaluating the population diversity objective has a quadratic runtime complexity of On)²), where n the population size.
3.2 POPULATION ENTROPY
To improve the stability and the runtime complexity, we derive safe and efficient surrogate objec- tive for optimization, which is named the Population Entropy (PE). Population entropy defined as the entropy of the mean of all policies in the population. Mathematically,
1
PE([m (1) f
(2) .... x (n) st) = ((=(-1s))) where ã (arls:) =
(0)
(ay
(5)
n
The population entropy serves lower bound of the population diversity objective.
3

---

Under review as a conference paper at ICLR 2022
Theorem 1. Let the population diversity be defined as Equation defined as Equation (5). Then, we have
Let the population entropy be
PD( ((1) ,,,,,,,,,,,, 8+)= 2 (EPE((= (2)
(1) (1)), 81)))
(6)
where n is the population size. Proof. See Appendix
Compared to the population diversity objective, the population entropy objective, H( (1.)). is
safe to maximize and it has only linear runtime complexity (n). Therefore, we use the derived population entropy objective for optimization. Taking a closer look at the population entropy objec-
tive, we find that it can be written into the -aasennShannon Divergence (JSD) and entropy form as follows:
H(T( (s:)) = (SD(T()( (1)6))))())))))))))))))))))))))) (s)),..., or (. (-18)) + Σ 71 1=1
H((T(0(-(s))..
A step-by-step derivation is in Appendix From Equation 77) we can see that when we maximize the population entropy objective, it attempts to push each policy away from each other via the JSD) term in Equation 7 as well as increase each policy's entropy via the entropy term in Equation
3.3 TRAINING A MAXIMUM ENTROPY POPULATION
We want to train a population of agents, who can play well with themselves. In the meantime, we also want their strategies to be different from each other. Subsequently, we define the reward function for MEP follows:
=<x)= = E Σ a()) ooH(() (-H((((11s)))) where ((-1s))= 1 Σ (-1s))
(8)
Equation 8 tells us that for each agent in the population, the agent is trained to maximize its task reward as well as the centralized population entropy objective. The task reward related to the agent and its partner agent, which is a copied version of itself playing the partner role in our case. When the centralized population entropy reward is calculated, considers all the agents in the population. We summarize the method of training maximum entropy population in Algorithm Land Figure
After having the maximum entropy population, we utilize this diverse set of agents to train the Al agent to be ready to pair with human players. The intuition behind MEP is that the Al agent should be more robust when paired with a group of diversified partners during training than trained only via self-play. In the extreme case, when the AI agent can coordinate well with an infinite set of different partners, it can also collaborate well with humans. In a more realistic sense, the more diverse the population is, it is more likely cover most of the human behaviors in the training set. Subsequently, the final Al agent should be less "panicked" when facing "abnormal" human actions.
3.4 TRAINING THE AGENT VIA PRIORITIZED SAMPLING
Considering that playing with different partner agents in the population, the Al agent needs different amounts of training time to learn to coordinate with them. We propose to use prioritized sampling based on the learning progress (Vinyals et al., 2019b), i.e., the expected accumulated reward, to adjust the frequency of each partner agent in the population to occur during training. Mathematically, the probability of the i-th agent to be sampled is:
(0) rank (1/E, E. R(si, (4) , aa ).
Ej= rank (I/E, E., R(s,, af afa) . a..z)))
..a))) 3
where the superscript (A) refers to the AI agent that we train for coordinating with humans; n is the population size; rank(-) is the ranking function ranging from 1 to n: 3 is a adjusting the strength of the prioritization. We assign a higher priority to the agents that are relatively harder to collaborate with. In the extreme case, at each optimization step. if we always choose the hardest agent in the population to train the AI agent, then we optimize performance lower bound of the cooperation between the Al agent and any agent in the population. Mathematically,
for
t (A) arg max
min ( (1)),
(10)
SE(1....
4

---

Under review as a conference paper at ICLR 2022
Figure 2: Overcooked environment: From left to right, the layouts are Cramped Room, Asymmetric
Advanlages, Coorlination Ring, Forced Coordination, and Counter Circuit.
where (()(A), x( denotes the expected reward achieved by ((A) and (+() collaborating with each other. With prioritized sampling, we make the collaboration between the Al agent and any agent in the population as good as possible. While uniform sampling does provide any guarantee on the worst case. For more detail on the performance lower bound, i.e., Equation (TO), see Lemma 4
in Appendix C Furthermore, we derive the performance connection between two pairs of agents, i.., (A(A), π ) and (r{(), r76)), when the partner agent (+) in the first pair is e-close (Ko) 2006)
the other partner agent マ in the second pair, see Lemma 5 in Appendix D Based on Lemma
if the population we used for training is diverse and representative enough, then we can find an agent that is e-close the human player's 's policy and have performance lower bound of human-AI coordination. In this case, prioritized sampling optimizes not only the performance lower bound of the Al agent and the population, see Equation (I0). but also the performance lower bound between the human player and the Al agent, see Corollary in Appendix [
4 EXPERIMENTS
Environment: To evaluate the proposed method, we first use a toy environment, i.c., the matrix game (Lupu al. 202T), see Figure 3 and then use the Overcooked environment (Carroll et al. 2019). see Figure The Overcooked game naturally requires human-Al coordination to achieve a high score. The players are tasked to cook the onion soups fast possible. The relevant objects are onions, plates, and soups. Players are required to place onions in a pot, cook them for 20 timesteps, put the cooked soup in a plate, and serve the soup. Afterwards, the players receive reward of 20. The six actions are up, down, left, right, noop, and interact. There are five different layouts, see Figure 2 Each layout has a different challenge. For example, in Asymmetric Advan- tages, good players should discover their advantages and play to their strengths. The player in the left has the advantage to deliver the soup. The player the right closer to the onions.
First, we train the population using the population entropy reward and investigate the effect of the entropy weight a. Secondly, we use the learned maximum entropy population to train the Al agent with the learning progress-based prioritized sampling and report the performance. In an ablation study, we show the effectiveness of both population entropy and prioritized sampling. method with other methods, including Self-Play (SP) Proximal Policy Optimiza- tion (PPO) (Schulman et al., 2017b] Carroll et al.) 2019), Population Based Training (PBT) (Jader- berg al. 2017| Carroll et al., 2019), and Trajectory Diversity (TrajeDi)- based PBT (Lupu al.] 2021). To test the methods, we use the protocol proposed by Darrolll et al. (2019), in which a human proxy model, H Prozy. is used for evaluation. The human proxy model trained through behavior cloning (Bain & Sammut 1999) on the collected human data. Furthermore, we conduct a user study using Amazon Mechanical Turk (AMT), in which we deploy our models through web interfaces and let real human players play with the Al agents. The experimental details are shown in Appendix Our code is available as supplementary material.
Experiments:
We compare
Question 1. How does MEP perform in the toy environment, i.e., the matrix game?
In the single-step collaborative matrix game (Lupu et al. 202T), player must select row while player 2 chooses a column independently. Both agents get the reward associated with the intersection of their choices at the end the game. We use the same evaluation protocol as proposed by Lupu et al. (2021). From Figure 3 we can that MEP converges faster than TrajeDi. We did an extensive hyper- hyper-parameter parameter search for TrajeDi, as shown in Figure in Appendix
Question 2. Does the population entropy reward increase the entropy of the population?
5

---

Under review as a conference paper at ICLR 2022
Self Retum
Cross Pay
1.
1.-
2
0
2
000
A.C
0.4
5:00
0.02
02-
cass
0.2
BK basel
PSP
vilaa agents
Instl duall agents
38 MEP sec.
B% N2P pcp.
25
55
100
125
159
375
200
25
57
u00 1:5
150
375 220
Trann mg Stops
Tratiing Stets
Figure 3: Performance comparison: Train and test performances on the matrix game. Shown the results for Best Responses (BRs) to MEP agents, BRs to TrajeDi populations, BRs to baseline populations, and individual agents. MEP allows faster learning compared to TrajeDi and others.
Arttoratric
Arrrnaati Advasagee
62
8.6 2A
Figure 4: Mean episode reward and population entropy learning curve: The left two plots are the mean episode reward and population entropy with entropy reward weight a = O in the Asymmetric Advantage layout. The right two plots show the quantities with 0.01 in the same layout.
To verify if the population entropy reward indeed increases the entropy of the population, we monitor the population entropy during training. The learning curve of the mean episode reward of the popu- lation and its corresponding population entropy is shown in Figure This figure shows that as the training starts, the reward increases, and the population entropy decreases. Comparing the left two figures with tropy reward, the population entropy indeed converges to higher value. We also try different values of a and investigate its effect on the reward and the population entropy, see Table Mable[]in in Appendix F The parameter a controls the balance between reward and entropy. The complete collection of the reward and population entropy learning curves with different shown in Appendix
0 and the right two figures with 0.01, we can see that with the population
Question 3. What does a maximum entropy population look like?
To have an intuition of what a maximum entropy population looks like, we show the populations in the supplementary video from 0:01 0:21. In this video clip, we present the population trained without the entropy reward in the first row and with the entropy reward in the second row. From the first row, we can see that the blue agent and the green agent move synchronized most of the time. The opaque routines among agents in the first population are similar. In the second row of the video clip, we can see that the behaviors of the maximum entropy population are more diverse. First, the movements of the blue agent and the green agent are less synchronized, especially in the fifth animation the second row. Secondly, the routines are less predictable. In general, we observe more diverse behaviors and randomness of the policies in the maximum entropy population.
Question 4. How does MEP perform compared to baseline methods?
We pair each agent, including SP, PBT, and MEP, with the proxy human model H Prezy, and evaluate the team performance. We test the performance in each of the layouts, shown in Figure 2 Good coordination between teammates is essential to achieve high scores in the collaborative game Over- cooked. Following the evaluation protocol proposed by Carroll et al. (201)), we use the cumulative rewards over a horizon of 400 timesteps as the proxy for coordination ability. For all tests, we report the average reward per episode and the standard deviation across 5 different random seeds. Figure 3 shows the quantitative results among different methods and the ablation tests. From Figure [5a we can see that MEP outperforms both SP and PBT in all environments. Additionally, we show the ablation test in Figure [5b] From the ablation test, we can see that both the population entropy reward the prioritized sampling are necessary components for achieving the best performance.
Question 5. Why does MEP perform better?

---

Under review as a conference paper at ICLR 2022
Performance with human proxy model
PST prary
Avernge newardd per opisdde
SP-Hppuny
125
300
75
50
25
Cracsped Rmn.
Asymu. Adv.
Coord. Ring
Focced Coard.
Counter Clrre
(a) Performance Comparison
Performance with human proxy model
150
Average eptoode
125
100
Cramped Rin.
Asymm.
Coord. Ring
Forced Cocrd.
(b) Ablation fests
Performance with human proxy model
TrajolX-HHee
MaP+Hooury
Averigge pitt
75
50
25
Cramped Rm.
Asyrm, Adv.
Cocod. Ring
Porzed Cocrd.
Counter Cire.
(c) Performance Comparison
Figure 5: Performance comparison and ablation test: Average episode rewards over 400 timestep (1 min) trajectories for different methods, with standard error over 5 different random seeds, paired with the proxy human Hprozy- The hashed bars with the slash (/) show results with the starting position of the agents switched. Figure (a) shows the performance comparison among MEP and baselines including SP and PBT. Figure (b) shows the ablation tests, where we use MEPa-1 and MEP3=0 to denote the MEP model without the population entropy reward and without the prioritized sampling mechanism, respectively. Figure (c) shows the performance comparison with TrajeDi.
We take closer look at some examples. The maximum entropy population contains a diverse set of policies, shown the supplementary video from 0:01 to 0:21. In the video, from 0:24 to 0:44, we show three human-Al gameplay demonstrations of SP, PBT, and MEP, respectively. From the video, we can see that the SP-trained agent and the PBT-trained agent are prone to get stuck during the process. However, the MEP-trained agent rarely gets stuck and mostly coordinates smoothly with its human partner. The reason is that the SP-trained agent and the PBT-trained agent are more likely to overfit their training partners' policies, which are usually different from humans' strategies. However, MEP uses a high entropy population, which contains a more diverse set of policies. When the AI agent is trained using the high entropy population, sees wide range of behaviors and learns to adapt to these policies. This helps to make the Al agent more robust during deployment.
Question 6. How does MEP perform compared TrajeDi?
7

---

Under review as a conference paper at ICLR 2022
Performance with real humans
H
MBP+Hmpe
SP+Hpu
PBT+H
80
Average reward per episode across layouts
Average reward per episode in each layout
Cramped Rm.
Asymm. Adv.
Coord. Ring
Forced Coord.
Counter Circ.
SP+HTrue 094.1
133.2
084.1
046.8
050.5
HBT+H7ue 101.6
124.9
098.4
027.6
033.5
MEP+H7muc 124.1
154.7
099.5
056.8
059.1
Figure 6: Performance with real humans
There is recent related work zero-shot coordination with diversified population, which is called TrajeDi (Lupu et al. [022). To the best of our knowledge, TrajeDi is the most related work. TrajeDi utilizes a trajectory- based diversity objective to obtain diversified population, whereas MEP formulates a novel action level diversity objective in the multi-agent population setting. To compare TrajeDi and MEP, we show the experiment results in Figure [5c] In the figure, we TrajeDi to denote the original TrajeDi method and use TrajeDi(wPS) to denote the TrajeDi method enhanced with the proposed Prioritized Sampling (PS) mechanism. From the figure, we can see that in all settings, MEP significantly outperforms TrajeDi. In 80% settings, MEP performs superiorly in comparison TrajeDi(wPS), Overall, MEP shows better performance compared TrajeDi(WPS).
Question 7. How does MEP perform with real human players?
We test the MEP-trained AI agent and measured the average episode reward when the agent was paired with real human player. For this human-Al coordination test, recruited 40 users (24 male, 14 female, 2 other, ages 22-71) on Amazon Mechanical Turk (AMT) and followed the same evaluation procedure proposed by Carroll et al. (2019). We reuse the testing results of SP and PBT from human-Al evaluation on AMT carried out by Carroll et al. (2019). These testing results compatible because the evaluation procedure is the same and uses netween-subject design, meaning each user was only paired with a single Al agent. The results are presented in Figure (6] The chart in Figure [ shows that on average across all five layouts, MEP significantly outperforms coordination performance. For
SP and PBT and its performance is on par with the Human- more detailed results, we take closer look at the table Figure This table shows the performance of each method in each layout. From this table, We can see that MEP achieves the best performance in all layouts in comparison with SP and PBT. Now, we describe some representative cases below.
Question 8. What does Al do when paired with real human players?
Here, we show and analyze some qualitative behaviors that we observed during the real human-Al AI coordination experiments, which are shown in the supplementary video from 0:22 to 2:27. From 0:24 to 0:44, we observe that in the Forced Coordination layout, the MEP-trained agent is more robust and less gets stuck during coordination, in comparison SP and PBT. Next, from 0:44 to 1:09, in the Asymmetric Advantage layout, the SP-trained and the PBT-trained agents only learned put the onion into the pot. They didn't learn to deliver the onion soup. While, the MEP-trained agent not only learned to put the onion into the pot but also learned to deliver the onion soup when its human partner busy. Similarly, from 1:09 to 1:29, in the Cramped Room layout, the SP-trained and PBT-trained agents only learned to use the plate to take the soup, whereas the MEP-trained agent additionally learned to carry the onion to the pot. Interestingly, from 1:29 to 1:56, in the Coordination Ring layout, the SP-trained and PBT-trained agent only learned to deliver the onion soup in one direction, while the MEP-trained agent learned to deliver the soup both clockwise and counterclockwise depending on where its human partner stands. Last but not least, from 2:01 to 2:26, in the Counter Circuit layout, the SP-trained and PBT-trained agent learned only pass the onion over the "counter". However, the MEP-trained agent also learned to take the plate and deliver the soup. From all these observations, we observe that the SP-trained and the PBT--rrined agents tend to overfit their optimal opaque policies, whereas trannd agent is more robust.
8

---

Under review as a conference paper at ICLR 2022
5 RELATED WORK
Recent works (Lerer Peysakhovich 2018 Tucker et al. 2020 Carroll al. 2019 Knott et al. 2021) tackle the collaboration problem using some behavioral data from the partner to select the equilibrium of the existing agents (Lerer & Peysakhovich 2018 Tucker et al.
2020 or build and
incorporate a human model into the training process (Carroll et al. 2019 Knott et al. 2021). How- ever, collecting a large amount of human data in real life is expensive and time-consuming. We consider the zero-shot setting, where behavioral data from the human partner is available dur- ing training (Hu et al. 2020). From a Bayesian perspective, when we don't 't know what the human policies look like, want to train the Al agent to be robust and be capable of collaborating with diverse set of policies (Murphy 2012). There is a growing amount of works on diversity in maxi- mum entropy reinforcement learning (Ziebart et al., 2008 Ziebart 2010: Fox et al., 2015 Haarnoja
et al. 2017; 2018b), many of which leverage it as a means of encouraging exploration (Schulman
ct al. 2017a Haarnoja et al. 2018b) or discovering skills (Eysenbach et al. 2019; Zhao al. 2021).
However, how to train a diversified population through entropy maximization is still subjective to research. In Multi-agent Reinforcement Learning (MARL), group of agents is trained achieve a common goal by Centralized Training and Decentralized Execution (CTDE) (Lowe et al.) 2017] Foerster et al. 2018). Taking inspiration from CTDE, we propose to train a population of agents to maximize centralized surrogate objective population entropy, to encourage diversity in the population. Subsequently, we train the Al agent with the maximum entropy population and dy- namically sample the partner agent based the learning progress. which shares similarities with Prioritized Fictitious Self-Play (PFSP) (Vinyals et al.) 2019b). PFSP is designed exclusively for concerned with cooperative games and derive the
zero-sum competitive games, whereas lationship between prioritized sampling and cooperation performance lower bound, see Appendix With prioritized sampling, we make the Al agent learn a policy that is generally suitable for all the strategies presented in the population.
The idea of MEP shares common intuition with domain randomization, where some features of the environment are changed randomly during training to make the policy robust to that feature (Tobin al. 2017 Yu al. 2017 Peng et al. 20118) Tan et al. 2018 Akkaya et al.) 2019 Tang et al. 2020). MEP can be seen as a domain randomization technique, where the randomizatio
is conducted
over a set of partners' policies. A recent related work TrajeDi (Lupu et al., 2021 has a similar motivation and formulates a trajectory- TrajeDi is the most related work to MEP, In comparison to TrajeDi, we derive the population entropy objective as an action level diversity objective, which is suitable for the multi-agent PBT setting. In the experiments, MEP shows superior performance compared to TrajeDi empirically. There are also other population diversity-based methods, such Diversity via Determinants (DvD) (Parker- Holder et al. (020) and Diversity- Inducing Policy Gradient (DIPG) (Masood & Doshi Doshi-Velez) 2019). which formulated for the single-agent setting, whereas MEP is designed for the multi-agent cooperative setting. In games with non-transitive dynamics where strategic cycles exist, e.g., Rock- Paper-Scissors, Policy-Space Response Oracle (PSRO)-based methods (Balduzzi et al. 2019 Perez- Nieves et al., 2021; Liu et al. 2021) provide solutions to learn diverse behaviors. Our method is complementary these previous works and could be combined with them. MEP bridges maximum entropy RL and PBT, which is generally applicable for many human-A Al coordination tasks.
diversity objective. To the best of our knowledge,
CONCLUSION
This paper introduces Maximum Entropy Population-basee training (MEP), deep reinforcement learning method for robust human-Al coordination. The derived population entropy theoretical ob- jective encourages learning a diverse set of policies. Subsequently. with the learning progress-bass based prioritized sampling technique, MEP helps the AI agent to be robust to different human strategies. In the simulated environments, we show that the developed approach achieves the best overall per- formance in comparison to -fate-of-the-as methods. Furthermore, in the real world evaluation with human players, MEP still demonstrates superior performance, which is comparable with human- human coordination performance. In addition, the qualitative examples show that policies are relatively flexible and robust to various human strategies.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Iige Akkaya, Marcin Andrychowicz, Maciek Chociej, Mateusz Litwin, Bob McGrew, Arthur Petron, Alex Paino, Matthias Plappert, Glenn Powell, Raphael Ribas, Jonas Schneider, Nikolas Tezak, Jerry Tworek, Peter Welinder, Lilian Weng. Qiming Yuan, Wojciech Zaremba, and Lei Zhang. Solving rubik's cube with robot hand. arXiv preprint, 2019.
Marcin Andrychowicz, Bowen Baker, Maciek Chociej, Rafal Jozefowicz, Bob McGrew, Jakub Pa- chocki, Arthur Petron, Matthias Plappert, Glenn Powell, Alex Ray, et al. Learning dexterous in-hand manipulation. arXiv preprint 11Xiv:/8888.0017..30 2018
Michael Bain and Claude Sammut. A framework for behavioural cloning. Machine Intelli- gence 15, Intelligent Agents [St. Catherine's 's College, Oxford, July 1995], pp. 103-129. Ox- ford, UK, UK, 1999. Oxford University. ISBN 0-19-853867-7. URL
org/
tat wfmm d 733043
David Balduzzi, Marta Garnelo, Yoram Bachrach, Wojciech Czarnecki, Julien Perolat, Max Jader- berg, and Thore Graepel. Open-ended learning in symmetric zero-sum games. In International Conference on Machine Learning, pp. 434-443, PMLR, 2019.
Craig Boutilier. Planning, learning and coordination in multiagent decision processes. Proceed- ings of the 6th conference on Theoretical aspects of rationality and knowledge, pp. 195-210. Morgan Kaufmann Publishers Inc., 1996.
Micah Carroll, Rohin Shah, Mark K Ho, Tom Griffiths, Sanjit Seshia, Pieter Abbeel, and Anca Dragan. On the utility of learning about humans for human-ai coordination. In Advances in Neural Information Processing Systems, pp. 5175-5186, 2019.
Shan Carter and Michael Nielsen. Using artificial intelligence to augment human intelligence. Dis- pub/2017/aia
till, 2017. doi: 10.2391 133915/10 //distill https::/ http//iistiillom http///ltti....ppp////////a////a
Douglas C Engelbart. Augmenting human intellect: A conceptual framework. Menlo Park, CA, 1962.
Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity all you need: Learning skills without reward function. In International Conference Learning Representa- tions, 2019. URL htttps: //tp:revee//eeeeiieeeeee net /ot./mmdmmmmmmim JRqFm
Jakob Foerster, Ioannis Alexandros Assael, Nando De Freitas, and Shimon Whiteson. Learning to communicate with deep multi-agent reinforcement learning. In Advances in neural information processing systems, pp. 2137-2145, 2016.
Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Roy Fox, Ari Pakman, and Naftali Tishby. Taming the noise in reinforcement learning via soft updates. arXiv preprint arXiv:1512.088 2015.
Ghost Town Games. Overcooked, 2016.
attos://store..teempweeeeee
448510/ /011////occooke///////
Tuomas Haarnoja, Haoran Tang, Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep energy-based policies. In International Conference on Machine Learning, pp. 1352-1361. PMLR. 2017.
Tuomas Haarnoja, Kristian Hartikainen, Pieter Abbeel, and Sergey Levine. Latent space policies for hierarchical reinforcement learning. arXiv preprint arXiv: 1804.02808 2018a.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critie: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In Proceedings of the 35th International Conference Machine Learning, pp. 1861-1870. PMLR, 2018b.
10

---

Under review as a conference paper at ICLR 2022
Tuomas Haarnoja, Sehoon Ha, Aurick Zhou, Jie Tan, George Tucker, and Sergey Levine. Learning to walk via deep reinforcement learning. In Robotics: Science and Systems, 2019.
Lei Han, Jiechao Xiong, Peng Sun, Xinghai Sun, Meng Fang. Qingwei Guo, Qiaobo Chen, Tengfei Shi, Hongsheng Yu, and Zhengyou Zhang. Tstarbot-x: An open-sourced and comprehensive study for efficient league training in starcraft ii full game. arXiv preprini vrXiv:2011.13722 2020.
Hengyuan Hu, Adam Lerer, Alex Peysakhovich, and Jakob Foerster. "'thher-pla"" for zero-shot coordination. In International Conference Machine Learning, pp. 4399-4410. PMLR, 2020.
Max Jaderberg. Valentin Dalibard, Simon Osindero, Wojciech M Czameeki, Jeff Donahue, Ali Razavi, Oriol Vinyals, Tim Green, lain Dunning, Karen Simonyan, et al. Population based train- ing of neural networks. arXiv preprint arXiv:1711.0984/ 2017.
Max Kleiman Weiner, Mark K Ho, Joseph Austerweil, Michael Littman, and Joshua Tenen- baum. Coordinate to cooperate or compete: abstract goals and joint intentions in social interac- tion. In CogSci, 2016.
Paul Knott, Micah Carroll, Sam Devlin, Kamil Ciosek, Katja Hofmann, Anca Dragan, and Rohin Shah. Evaluating the robustness of collaborative agents. In Proceedings of the 20th International Conference Autonomous Agents and MultiAgent Systems, pp. 1560-1562, 2021.
Stanley Ko. Mathematical analysis. 2006.
Jason D Lee, Max Simchowitz, Michael Jordan, and Benjamin Recht. Gradient descent only converges to minimizers. In Conference on learming theory, pp. 1246-1257. PMLR, 2016.
Adam Lerer and Alexander Peysakhovich. Maintaining cooperation in complex social dilemmas using deep reinforcement learning. arXiv preprint arXiv:1707.01068 2017.
Adam Lerer and Alexander Peysakhovich. Learning social conventions in markov games. arXiv preprint arXiv: 10071, 2018
Xiangyu Liu, Hangtian Jia, Ying Wen, Yaodong Yang, Yujing Hu, Yingfeng Chen, Changjie Fan, and Zhipeng Hu. Unifying behavioral and response diversity for open-ended learning in zero-sum 2021.
games. arXiv preprint
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor- critic for mixed cooperative--ompeiiii environments. In Advances in Neural Information Pro- cessing Systems, pp. 6379-6390, 2017.
Trajectory diversity for zero-shot coordination. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 7204-7272111 PMLR, 18-24 24 Jul 2021. URL https: h http:::://ppocceei.n
Andrei Lupu, Brandon Cui, Hengyuan Hu, and Jakob Foerster.
mlr www.:mmr....es.e....em. /ttesss/vvv///////// 39/lupp2la.... 1tt.pllla..mmllll.
Muhammad A Masood and Finale Doshi-Velez. Diversity-inducing policy gradient: Using maxi- mum mean discrepancy to find set of diverse policies. Proceedings of the Twenty-Eighth Inter- national Joins Conference on Artificial Intelligence (IJCAI), 2019.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International conference machine learning, pp.
PMLR, 2016.
Kevin P Murphy. Machine learning: A probabilistic perpppeettiiceerppettttiii adaptive computation and machine learning, 2012.
OpenAl. OpenAl Five
finals.
2019.
https://openai.comm htt.:/aaaaaiccmoooo/o/oooo
openai five- Finals/
Sinno Jialin Pan and Qiang Yang. survey on transfer learning. IEEE Transactions on knowledge and data engineering, 22(10):1345-1355 2009.

---

Under review as a conference paper at ICLR 2022
Jack Parker-Holder, Aldo Pacchiano, Krzysztof M Choromanski, and Stephen J Roberts. Effective diversity in population based reinforcement learning. Advances in Neural Information Processing Systems, 33, 2020.
Xue Bin Peng, Marcin Andrychowicz, Wojciech Zaremba, and Pieter Abbeel. Sim-to-real transfer of robotic control with dynamics randomization. In 2018 IEEE international conference on robolics and automation (ICRA). pp. 1-8. IEEE, 2018.
Nicolas Perez-Nieves, Yaodong Yang, Oliver Slumbers, David H Mguni, Ying Wen, and Jun Wang. Modelling behavioural diversity for learning in open-ended games. In International Conference on Machine Learning. pp. 8514 8524. PMLR, 2021.
Konrad Rawlik, Marc Toussaint, and Sethu Vijayakumar. On stochastic optimal control and rein- forcement learning by approximate inference. In Twenty-third international joint conference on artificial intelligence, 2013.
Cinjon Resnick, Ilya Kulikov, Kyunghyun Cho, and Jason Weston, Vehicle community strategies. arXiv preprint arXiv:1804.07178, 2018.
Tom Schaul, John Quan, loannis Antonoglou, and David Silver. Prioritized experience replay. In International Conference on Learning Representations, 2016.
John Schulman, Xi Chen, and Pieter Abbeel. Equivalence between policy gradients and soft q- learning. arXiv preprint arXiv:
2017a.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 1 1707.06347, 2017b.
Michael Shum, Max Kleiman-Weiner, Michael I. Littman, and Joshua B Tenenbaum. Theory of minds: Understanding behavior in groups through inverse planning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 6163-6170, 2019.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. Mastering chess and shogi by self-play with general reinforcement learning algorithm. arXiv preprint arXiv: 2017.
Jie Tan, Tingnan Zhang, Erwin Coumans, Atil Iscen, Yunfei Bai, Danijar Hafner, Steven Bohez, and Vincent Vanhoucke. Sim-to-real: Learning agile locomotion for quadruped robots. arXiv preprint arXiv:1804. 10332, 2018
Zhenggang Tang, Chao Yu, Boyuan Chen, Huazhe Xu, Xiaolong Wang, Fei Fang, Simon Shaolei Du, Yu Wang, and Yi Wu. Discovering diverse multi- agent strategic behavior via reward random- ization. In International Conference on Learning Representations, 2020.
Gerald Tesauro. Td-gammon, a self-teaching backgammon program, achieves master-level play.
Neural computation, 6(2):215-219, 1994.
Josh Tobin, Rachel Fong, Alex Ray, Jonas Schneider, Wojeiech Zaremba, and Pieter Abbeel. Do- main randomization for transferring deep neural networks from simulation to the real world. In 2017 IEEE/RSJ international conference on intelligent robots and systems (IROS), pp. 23-30. IEEE, 2017.
Mare Toussaint. Robot trajectory optimization using approximate inference. In Proceedings of the 26th annual international conference on machine learning. pp. 1049-1056, 2009.
Mycal Tucker, Yilun Zhou, and Julie Shah. Adversarially guided self-play for adopting social con- ventions. arXiv preprint arXiv:2001.05994 2020.
Oriol Vinyals, Igor Babuschkin, Junyoung Chung, Michael Mathieu, Max Jaderberg, Woj- ciech M. Czamecki, Andrew Dudzik, Aja Huang. Petko Georgiev, Richard Powell, Timo Ewalds, Dan Horgan, Manuel Kroiss, Ivo Danihelka, John Agapiou, Junhyuk Oh, Valentin Dal- ibard, David Choi, Laurent Sifre, Yury Sulsky, Sasha Vezhnevets, James Molloy, Trevor Cai, David Budden, Tom Paine, Caglar Gulcehre, Ziyu Wang, Tobias Pfaff, Toby Pohlen, Yuhuai
12

---

Under review as a conference paper at ICLR 2022
Wu, Dani Yogatama, Julia Cohen, Katrina McKinney, Oliver Smith, Tom Schaul, Timothy Lillicrap, Chris Apps, Koray Kavukcuoglu, Demis Hassabis, and David Silver. AlphaStar: Mastering the Real-Time Strategy Game StarCraft II. https:://depmaiiieeee com/ blog/
a
weweastterinngreeeee real- -tee--iteeseee gane-e--e-ettteaann---ee-e wtw.aammttttarrrtttttaaaaa. 2019a.
Oriol Vinyals, Igor Babuschkin, Wojciech M Czamecki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David Н Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782)3350-33 2019b.
Wenhao Yu, Jie Tan, Karen Liu, and Greg Turk. Preparing for the unknown: Learning universal policy with online system identification. arXiv preprint arXiv: 1702.02453, 2017.
Rui Zhao, Xudong Sun, and Volker Tresp. Maximum entropy-regularizee multi-goal reinforcement learning. In Proceedings of the 36th International Conference on Machine Learning, pp. 7553- 7562. PMLR. 2019.
Rui Zhao, Yang Gao, Picter Abbeel, Volker Tresp, and Wei Xu. Mutual information state intrin- sic control. In International Conference Learning Representations, 2021. URL https:
Brian D Ziebart. Modeling purposeful adaptive behuvior with the principle of maximum causal entropy. Carnegie Mellon University, 2010.
Brian D Ziebart, Andrew L Maas, J Andrew Bagnell, Anind K Dey, et al. Maximum entropy inverse reinforcement learning. 2008.
APPENDIX
A POPULATION ENTROPY LOWER BOUND
Theorem 2. Let the population diversity defined as:
PD((7()) (2) (n) (,88))))) 8t) =
(-1s),, + Σ (. (.18)). (11)
Let the population entropy be defined as:
(T(( (2) .... T { = (((F(-1118)) where F(aeloe) = Σ
(arls))
(12)
1=1
Then, we have
PD( (1), (2) ...,, (1)) 2 n² TTPEE(= (1), (1)),
(13)
where n is the population size.
Proof. Cross entropy is given by: x x00( -
CE( (t))),
Σ
x ( log n (1) (a.1s:)
(14)
aEA
Entropy is given by:
H( (. = Σ
n (acls)) log ( (cclse))
(15)
aEA
13

---

Under review as a conference paper at ICLR 2022
We can derive the follows:
PD( (3)) ... x (m) J. s() =
CB ( ( (1(t), (-1s)) + " (((T(((-ss)))
(16)
t= jti
x (ae(sr) log (as)se))
(17)
n
(0) (aclst)
log (1) (agls))
(18)
AEA
2n 2 Σ
(0) (ar(s)) log Σ n () (aclss))
(19)
2 [[aels)) (ag
(00)
aEA
n [H(T(-
(21)
=n PP (1) (2)
7 (n) J, 81)
(22)
From Equation
18 to Equation
T9p. we use Jensen's inequality (Murphy 2012).
B POPULATION ENTROPY AND JENSEN-SHANNON DIVERGENCE
Lemma 3. The population entropy has the following relation with Jensen-Shannon Divergence (JSD):
1 Σ H(m (- (-1s:)),
H(#(- = JSD(=()) (se),.., (1))
(23)
where JSD is given by
(.) (.1ss)...., (st)) 1 1
π 10 (cr(se)
Σ Σ
x (ecls)) log (ar(st)
(24)
i=1 .EAA
Proof.
H( Σ (arlss)) log (a:(s))
(25)
a.EA
n
(arls))) log (arlse)
(26)
n
G.EA
log m(() #(ae(8))
(T((aels))
log me (a(e(s)))
(27)
n
D.EA
1 12
=JSD(=
(s,)...,, (1)) (m) (118)) + (-)ee)
Σ n
H( (+)
(28)
1=1
From the derivation, we can see that maximizing the population entropy is equivalent to maximizing the JSD of all agent's 's policies in the population and the entropy of each agent's 's policy. Since the JSD measures similarity, the first term of Equation (28) encourages the policies to be different from each other. The second term of Equation (28) encourages each policy to explore.
14

---

Under review as a conference paper at ICLR 2022
C PRIORITIZED SAMPLING AND PERFORMANCE LOWER BOUND
Here, we use (44) to denote the AI policy and use 0 to represent the parameter of x(4), At the training step t, we use 8e to denote the current parameter. {x(1) ....,,())) is the population used to train (4). We want to find the optimal parameter 8* for the Al policy (44), so that the Al agent could cooperate well with any agent in the population.
At each training step, we first sample 7(() from the population, then let (+) to cooperate with x(4) Then, we use the sampled trajectory T to train 7(*), ( is the excepted sum rewards achieved by ((4) and (+) together. With prioritized sampling introduced in Section 3.4 we assign higher priority to the agent that harder to collaborate with. To be more specific, let
i arg arg min J (T6..)
(A) ,T()),
(29)
(4) During training, 0 is updated using the gradient as- then we sample x to cooperate with Tg. cent method with non-increasing learning rate ay- At each training step t, there exists a subset of {1, {I...., n denoted by Ko, = {ia I, $ n), such that
(A) (t)) Ct J( (A) (0)) > [
if & Ko,; is E Ko.-
(30)
Since prioritized sampling used, one of in (K' L......) 1) could be sampled. Then the gradient of the current step t is
(TT
(A) , (b())
(31)
The parameter is updated as following:
4 00 + 02 V0
(32)
where a₂ is the learning rate at the training time step t.
Assume that (J(m6.) (A) x ( 1.... n) are smooth towards 0,, then
( min
[TT (A) 7 ())
(33)
xE sE(!.....)
is a piece-wise smooth function and Vo.J (1) T ((r))) ) is equal to the gradient of g(f) almost ev- erywhere. Next we prove that using V (TT of g(t).
(A) (Ww)) it could also converge to a local maximum
Lemma 4. (A) with parameter 0 is trained with the population (x(1) (,."),,,,(())))) We use the learn- ing progress-based prioritized sampling to sample the agent from the population for training. As- sume that J (A) (60) is smooth towards the parameter vector 0 and has L-Lipschitz gradient (
for all i, is optimized using the gradient ascent with a sufficiently small constant step size. If (mxb)), ((0) converges and doesn't i go to infinity, it would converge to local maximum of g(0). That is f converges to a neighborhood Vi of where ô define as
i arg max min DEV, iE(I....n)
J( (1).
(34)
Proof. O, denotes the parameter of - (4) at the training step L. We define the index set of i, that J(mb.) (A) (()) equal to min;g(l......) J (A)(A), .(0)):
Ke. = (ixlk = 1,..,,,15m,,,
(35)
where is satisfies
[ (A) (0)) > J [(
(A) . ((()) = Cc. if & Ko,, is E Ko.-
(36)
in is sampled from Ko, and current gradient is Vo, (a) {(w)).
15

---

Under review as a conference paper at ICLR 2022
If fgg E Kor-i for all | O, the optimization process could be regarded non-convex optimization problem by gradient ascent, then 8g converges to local maximum almost surely by the assumption (A) (TT. x!0) has an L-Lipschitz gradient (Lee et al. 2016).
If Ifsso Ko.+, = D. then first we prove that the sequence {0,} can't converge to a saddle point. If a saddle point, [= x(1) for all iy E Kg. which means J(mb,)) (.4) x ( are identical
neighborhood of 0. This contradicts the local minimum convergence 0g (Lee et al. 2016).
Assume the convergent point 0 has a non-zero gradient VoJ(mT
(A) x((e)) since we use a sufficiently
small constant learning rate o, if [ (A) x
x(w2)) > [[ (4) =((2)), this would contradict the convergence of 0, and if Jmx(A) 04200 ml2)) J(mb/) xl1)),, which means @ is the local maximum.
0420"
From Lemma 4
that with prioritized sampling, could improve the lower bound of the
cooperation performance between (AA) and the population {T(1), ..... T(*)). J. In comparison, uniform sampling does not provide any guarantee on the worst case. We call the optimal solution of mean sampling:
0' = argmaxx
Σ
J(mba) (0)
(37)
iE(L......
Then, the worst cooperation between Te and the population must be no greater than the cooperation between T6 and the population. That is:
(A) 20) min [(g ie ()....))
min Hm (A) (1))
(38)
iE uE......
D RELATION TO HUMAN-AI COORDINATION PERFORMANCE
To illustrate that we could improve the lower bound of human-Al coordination performance, here we introduce the connection between e-close (Ko 2006) and return, i.e., expected sum rewards.
Definition 1. We define that x is e-close to (2) at the state if
n (agls)) x (a.ls))
- <c
(39)
for all E A. If this is satisfied at every 3, S, we call (11) is e-close to (2))
Lemma 5. If an MDP has T time steps and (11) is e-close to T(2), then for all (AA), we have
(1 (1-c)T (((12)) (A)) < 1 < (1+ +c)+c)= J(T n (A))),
(40)
where [()((), (AA) denotes the expected sum reward achieved by (9) and (A) collaborating with each other.
((())
Proof.
For all trajectory 7, we have
(1 (7) (( (4al (1) ( (.)))
(41)
Since
(1 (a < < (a.(s)))) (1 < (arls))
(42)
we have
(1 (1-6) P2(2) p(t)) (T) P (7) (1 T) pr ((as(())
(43)
And because
(1, x(1)) Σ Pr(t) 200 (7)r(T).
(44)
16

---

Under review as a conference paper at ICLR 2022
where
r(r) = r(s0: ao ... .T, E r(s, az) and ar = (A())
(45)
Therefore, we have
(1 -1 [(=))) x < , < (1)).
(46)
We use (HH to denote the human player's policy, From Lemma we can see that if (8)) is similar any of the policy (+) in the population {T(1) :..., (()) in certain degree, measured by c-close, then its cooperation performance with the AI policy x (A4), which is trained with the population, would not deteriorate too much. Furthermore, we derive the following corollary.
Corollary 1. We call the infimum of expected sum rewards of (A4) cooperating with the population (x(1) xt x(m)] as:
min 1E
((T(A),
((T) = C.
(47)
If (H) e-close to the policy xt in the population, then we have
[(x(A), T (1)) > C(1 c)
(48)
where T is the total steps in the trajectory.
Proof. If a (H) is e-close to n (6) based on the property of e-close, see Lemma 5 we have
J n (11)) > (1 - (()))) (1)).
(49)
Additionally, since
[(m(A), > C2
(50)
we have
{(T(A), x(H)) > C(1 -)
(51)
Since prioritized sampling optimizes the lower bound of expected sum rewards of the AI agent cooperating with the population, see Lemma 4 and with Corollary [ we could say that it also optimizes the lower bound of expected sum rewards of the Al agent cooperating with the Human player, when the population is diverse and representative enough so that it is close to cover human behaviors.
E EXPERIMENT DETAILS
We ran all the methods in each environment with different random seeds and report the average episode reward and the standard deviation. The experiments of the maximum entropy population- based training use the following arper-parametens.
The learning rate is 8c-4.
The reward shaping horizon is 5e6.
The environment steps per agent is 1.1c7.
The number of mini-batches is 10.
The mini-batch size is 2000.
PPO iteration timesteps are 40000. The PPO iteration timesteps refer to the length in envi- ronment timesteps for each agent pairing training.
17

---

Under review as a conference paper at ICLR 2022
The population size is for training the maximum entropy population. We use the beginner model, the middle model, and the best model each agent in the population to form the final population for training the Al agent.
The weight for the population entropy reward is 0.01 in general. For the Forced Coordi-
nation layout, we use 0.04.
The number of parallel environments used for simulating rollouts is 50.
The discounting factor y is 0.99.
The max gradient norm is 0.1.
The PPO clipping factor is 0.05.
The number of hidden layers is 3.
The size of hidden layers is 64.
The number of convolution layers
The number of filters is 25.
The value function coefficient 0.1.
The 8 for prioritized sampling is 3.
F
EXPERIMENTAL RESULTS
Cross Pay Return
10
0.-
Tracch plamo
0.4
Trucch pfem??
Traje phe- Trae pham3 Traie
0.
Staps
Figure Performance comparison: We did an extensive hyper-parameter search for TrajeDi. MEP converges faster than TrajeDi under all the parameters.
Table 1:
Best self-play reward and corresponding population entropy with different a: In
this table, a denotes the weight of the population entropy reward in Equation (8)
Cramped Rm.
Asymm. Adv.
Coord.
Ring
Forced Coord.
Counter Circ.
Rew.
Ent.
Rew.
Ent.
Rew.
Ent.
Rew.
Ent.
Rew.
Ent.
0.000
196.8
0.971
164.1
1.120
183.4
0.878
149.4
0.970
129.0
0.988
0.001
187.6
1.031
160.9
1.051
183.7
0.907
152.0
0.858
118.0
1.152
0.005
189.8
0.949
153.0
1.075
164.1
0.901
163.7
0.889
119.2
1.038
0.010
183.7
1.057
151.8
1.139
167.8
0.840
151.2
1.079
136.5
1.151
0.020
174.2
1.029
149.7
1.074
157.8
0.947
137.8
1.093
121.7
1.171
0.030
154.0
1.134
138.7
1,203
153.6
1,028
133.6
0.957
0.130
1,715
0.040
137.0
1.194
135.0
1.353
125.7
1.122
081.0
1.460
0.000
1,791
0.050
137.1
1.127
118.4
1.364
129.6
0.996
024.5
1.703
0.000
1.791
18

---

Under review as a conference paper at ICLR 2022
o=0.000
a=0.001
a=0.005
a=0.010
65.
Coo
Cordiraton
Freedd Coeudra
Ineed
Exchnessn trange
Couara Crand
Ceuase Crasd
Couara Cland
Table 2: Mean episode reward and population entropy with different in all five layouts: Each column corresponds to a different value of a in the set of [0.000, 0.001, 0.005, 0.010). There are five row sections, which correspond to the five layouts. Each row section contains two rows, which are the plots of the mean episode reward and the mean population entropy of the layout, respectively.
19

---

Under review as a conference paper at ICLR 2022
a=0.020
o=0.030
a=0.040
a=0.050
Chumpst
Chiment
65
Condinatco
Cordiracan Ring
Condinatan
Cordinatan
Enered Cocdrraarttt
Enerdd TonndrCandaatte
Oo Orineasnntoorg
Excineaset Erange
Di Dr bratage
Coeara Ciran
Couare Crai
Couare Cana
Cauare Crana
Table 3: Mean episode reward and population entropy with different in all five layouts: Each column corresponds to a different value of a in the set [0.020, 0.030, 0.040, 0.050). There are five row sections, which correspond to the five layouts. Each row section contains two rows, which are the plots of the mean episode reward and the mean population entropy of the layout, respectively.
20


Reviews:
[{"review_id": "xNQs5ZNA5mT", "reviewer": "Reviewer_MRtf", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nHowever, 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**.\n\nMore Detailed Comments:\n* 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?\n* 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.\n* 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.\n* 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. \n* As always, it is great that code is included.\n* 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.\n* 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).\n* 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_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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "l78MVPtuDqY", "reviewer": "Reviewer_5ykj", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nI am struggling to come up with sound overall grade for this paper. In short:\n\n1. 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. \n\n2. It seems to be effective when tested against comparable baselines in an interesting multi-agent environment.\n\n3. The submission does a good job at providing enough details (and code) to enable quickly reproducing the work.\n\nHowever:\n\n4. The experimental section is relatively weak:\n\n    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.\n\n    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).\n\n5. 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.\n\n6. 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:\n\n   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).\n\n   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?\n\n### Nits\n\n- Generally: the [...] RL -> [...] RL\n- Section 1: prioritized sampling [of what?]\n- 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?\n- Section 2: modes of sub-optimal -> modes of optimal (?)\n- Section 3.1: what do incentive and multi-modal mean here?\n- Section 3.4: the first paragraph feels off in terms of syntax / punctuation.\n- 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_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.", "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.\n\n---\n\nBumped up score to weak accept.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "bu36Otbj8Ea", "reviewer": "Reviewer_PRq2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\nThe problem is important, and testing it on Overcooked along with a human experiment is a good domain for this exploration.\nThe population diversity metric is also reasonable, and seems like a good quantity to include as part of an auxiliary loss.\nThe human experiments are neat (although I am left wondering why TrajeDi is not compared with in the human experiments).\n\n\nWeaknesses\n\nThough 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.\n\nI 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?)\n\nI'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\".\n\nI 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_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.\n\nThe 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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "O79X6ooM_5v", "reviewer": "Reviewer_mavT", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "STRENGTHS\n\nThe 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.\n\nWEAKNESSES\n\nThere are several crucial missing or misunderstood ablations and baselines.\n\n**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.\n\nSeveral 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.\n\n**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.\n\n**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?\n\n**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.\n\n**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.\n\n**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.\n\n**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.\n\n**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.\n\nLastly, a few more minor points:\n1. 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.\n2. 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).\n3. 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.\n4. 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.\"\n5. In the intro, are cooperative games and emergent communication really \"real world applications\"?\n6. 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.\n7. 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.\n8. 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.\n9. 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_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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "GQw_qCuPXCU", "reviewer": "Reviewer_1grX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n\n1. The paper is well-written and easy to follow.\n2. The idea of combing the population entropy during the training is interesting, which considers both agents' individual diversity and pairwise diversity.\n\nConcerns:\n1. 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.\n2. 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.\n3. 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.\n\n[1] Balduzzi, David, et al. \"Open-ended learning in symmetric zero-sum games.\" International Conference on Machine Learning. PMLR, 2019.\n\n[2] Nieves, Nicolas Perez, et al. \"Modelling behavioural diversity for learning in open-ended games.\" arXiv preprint arXiv:2103.07927 (2021).\n\n[3] Liu, Xiangyu, et al. \"Unifying Behavioral and Response Diversity for Open-ended Learning in Zero-sum Games.\" arXiv preprint arXiv:2106.04958 (2021).\n\n\nTypos & Questions:\n1. 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?\n2. Page 5: The repeat 'Environment' sub-section names of the last two paragraphs.", "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. \n", "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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

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