MAXIMUM ENTROPY POPULATION BASED TRAINING
Year: 2021

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 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 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 Overcooked game environment. We also conduct online experiments with real humans and further demonstrate the efficacy of the method in the real world.

heading: 1 INTRODUCTION
text: Deep Reinforcement Learning (RL) has gained many successes against humans in competitive games, such as Go (Silver et al., 2017), Dota (OpenAI, 2019), and StarCraft (Vinyals et al., 2019a). However, it still remains a challenge to build AI agents that can coordinate and collaborate with humans that the agents have not seen during training (Kleiman-Weiner et al., 2016; Lerer & Peysakhovich, 2017; Carroll et al., 2019; Shum et al., 2019; Hu et al., 2020; Knott et al., 2021). Zero-shot human-AI coordination is particularly important in real-world applications, such as cooperative 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 AI systems that can assist humans and augmenting our capabilities (Engelbart, 1962; Carter & Nielsen, 2017) to make our life better.
The mainstream method for building state-of-the-art AI agents is through self-play reinforcement learning (Tesauro, 1994; Silver et al., 2017). Self-play-trained agents are very specialized, and therefore suffered significantly from distributional shift when paired with humans. For example, in the Overcooked game, the self-play-trained agents only use a specific pot and ignore the others. However, humans use all pots. The AI agent ends up waiting unproductively for the human to deliver a soup from the specific pot, while the human has instead decided to fill up the other pots (Carroll et al., 2019). Since the AI agent has only encountered its own policy during training, it undergoes a distributional shift when it is paired with human players.
We explore how to design a robust and efficient approach to train agents for zero-shot human-AI coordination. To that end, we draw on the advances in maximum entropy RL (Haarnoja et al., 2018b), diversity (Eysenbach et al., 2019), and Multi-agent RL (Lowe et al., 2017; Foerster et al., 2018). First, maximum entropy RL augments the standard reward function with an entropy maximization 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; 2018b; Zhao et al., 2019). For a population of agents, we use the maximum entropy bonus to encourage individual diversity, i.e., each agent’s policy to be diverse and exploratory. Secondly, to acquire diverse and distinguishable behaviors (Eysenbach et al., 2019), we further utilize the sum of crossentropy terms across all agent pairs in the population to encourage pairwise diversity. We define the
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 a centralized fashion. Each agent in the population is rewarded to maximize the centralized population diversity. Subsequently, we derive a safe and computationally efficient surrogate objective, i.e., population entropy, which is proven to be a lower bound of the original population diversity objective. 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 to collaborate 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 et al., 2019a;b; Han et al., 2020). The newly trained AI agent encounters a 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 a 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 considers 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 framework, 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 comparing it with state-of-the-art baseline methods. To further verify the improvements, we conduct online experiments with real humans.

heading: 2 PRELIMINARIES
text: Markov Decision Process: A two-player Markov Decision Process (MDP) is defined by a tuple M = 〈S, {A(i)},P, γ, R〉 (Boutilier, 1996), where S is a set of states; A(i) is a set of the i-th agent’s actions, where i ∈ [1, 2]; P is a transition function that maps the current state and all agents’ actions to the next state; γ is the discount factor; R is a reward function. The i-th agent’s policy is π(i). A trajectory is denoted by τ . The shared objective is to maximize the expected sum rewards, which is Eτ [ ∑ tR(st, at)], where at = (a (1) t , a (2) t ). We can extend the objective to infinite horizon problems by the discount factor γ to ensure that the sum of expected rewards is finite.
AI Agent, Population, and Human: Throughout this paper, we use the phrase AI agent to explicitly mean the agent that plays the AI role in human-AI coordination. The population of agents is used to train the AI agent to make it capable of cooperating with different partner agents. The human policy is represented as π(H) and a model of the human policy is π̂(H). The AI agent is denoted as π(A).
Environment: We use the Overcooked environment (Carroll et al., 2019) as the human-AI coordination 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.
Maximum Entropy RL: Standard RL maximizes the expected sum of rewards Eτ [ ∑ tR(st, at)]. 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., 2016). 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:
J(π) = Eτ [∑ t R(st, at) + αH(π( · |st)) ] . (1)
The parameter α adjusts the relative importance of the entropy bonus against the reward and controls 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 et al., 2017a). 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 (Haarnoja et al., 2018a; 2019).

heading: 3 METHOD
text: 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 AI agent via prioritized sampling using the population.

heading: 3.1 POPULATION DIVERSITY
text: Motivated by maximum entropy RL, we want to make the policy population exploratory and diverse. First, by utilizing the maximum entropy bonus, we encourage each policy itself to be diverse and multi-modal. Secondly, to encourage the policies in the population, {π(1), π(2), ..., π(n)}, to be complementary and mutually different, we naturally utilize the cross entropy objective (Murphy, 2012). Formally, we define the Population Diversity (PD) as the combination of the sum of the entropy of each agent’s policy and the sum of the Cross Entropy (CE) between each pair of agents in the population. Mathematically,
PD({π(1), π(2), ..., π(n)}, st) := n∑ i=1 n∑ j 6=i CE(π(i)( · |st), π(j)( · |st)) + n∑ i=1 H(π(i)( · |st)), (2)
where cross entropy (CE) and entropy (H) are defined as follows: CE(π(i)( · |st), π(j)( · |st)) = − ∑ a∈A π(i)(at|st) log π(j)(at|st), (3)
H(π(i)( · |st)) = − ∑ a∈A π(i)(at|st) log π(i)(at|st). (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 is 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 O(n2), where n is the population size.

heading: 3.2 POPULATION ENTROPY
text: To improve the stability and the runtime complexity, we derive a safe and efficient surrogate objective for optimization, which is named the Population Entropy (PE). Population entropy is defined as the entropy of the mean of all policies in the population. Mathematically,
PE({π(1), π(2), ..., π(n)}, st) := H(π̄( · |st)), where π̄(at|st) := 1
n n∑ i=1 π(i)(at|st). (5)
The population entropy serves as a lower bound of the population diversity objective.
Theorem 1. Let the population diversity be defined as Equation (2). Let the population entropy be defined as Equation (5). Then, we have
PD({π(1), π(2), ..., π(n)}, st) ≥ n2PE({π(1), π(2), ..., π(n)}, st), (6) where n is the population size. Proof. See Appendix A.
Compared to the population diversity objective, the population entropy objective, H(π̄( · |st)), is safe to maximize and it has only a linear runtime complexity O(n). Therefore, we use the derived population entropy objective for optimization. Taking a closer look at the population entropy objective, we find that it can be written into the Jensen-Shannon Divergence (JSD) and entropy form as follows:
H(π̄( · |st)) = JSD(π(1)( · |st), ..., π(n)( · |st)) + 1
n n∑ i=1 H(π(i)( · |st)), (7)
A step-by-step derivation is in Appendix B. From Equation (7), 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 7.

heading: 3.3 TRAINING A MAXIMUM ENTROPY POPULATION
text: 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 as follows:
J(π) = Eτ [∑ t R(st, at) + αH(π̄( · |st)) ] , where π̄( · |st) := 1 n n∑ i=1 π(i)( · |st). (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 is 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, it considers all the agents in the population. We summarize the method of training a maximum entropy population in Algorithm 1 and Figure 1.
After having the maximum entropy population, we utilize this diverse set of agents to train the AI agent to be ready to pair with human players. The intuition behind MEP is that the AI 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 to cover most of the human behaviors in the training set. Subsequently, the final AI agent should be less “panicked” when facing “abnormal” human actions.

heading: 3.4 TRAINING THE AGENT VIA PRIORITIZED SAMPLING
text: Considering that playing with different partner agents in the population, the AI 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:
p(π(i)) = rank
( 1/Eτ [∑ tR(st, a (A) t , a (i) t ) ])β
∑n j=1 rank ( 1/Eτ [∑ tR(st, a (A) t , a (j) t ) ])β , (9)
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; β is a hyper-parameter for 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 a performance lower bound of the cooperation between the AI agent and any agent in the population. Mathematically,
π(A) = arg max min i∈{1,...,n} J(π(A), π(i)), (10)
where J(π(A), π(i)) denotes the expected sum reward achieved by π(A) and π(i) collaborating with each other. With prioritized sampling, we make the collaboration between the AI agent and any agent in the population as good as possible. While uniform sampling does not provide any guarantee on the worst case. For more detail on the performance lower bound, i.e., Equation (10), see Lemma 4 in Appendix C. Furthermore, we derive the performance connection between two pairs of agents, i.e., (π(A), π(i)) and (π(A), π(j)), when the partner agent π(i) in the first pair is -close (Ko, 2006) to the other partner agent π(j) in the second pair, see Lemma 5 in Appendix D. Based on Lemma 5, if the population we used for training is diverse and representative enough, then we can find an agent that is -close to the human player’s policy and have a performance lower bound of human-AI coordination. In this case, prioritized sampling optimizes not only the performance lower bound of the AI agent and the population, see Equation (10), but also the performance lower bound between the human player and the AI agent, see Corollary 1 in Appendix D.

heading: 4 EXPERIMENTS
text: Environment: To evaluate the proposed method, we first use a toy environment, i.e., the matrix game (Lupu et al., 2021), see Figure 3, and then use the Overcooked environment (Carroll et al., 2019), see Figure 2. The Overcooked game naturally requires human-AI coordination to achieve a high score. The players are tasked to cook the onion soups as fast as possible. The relevant objects are onions, plates, and soups. Players are required to place 3 onions in a pot, cook them for 20 timesteps, put the cooked soup in a plate, and serve the soup. Afterwards, the players receive a 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 Advantages, 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 in the right is closer to the onions.
Experiments: First, we train the population using the population entropy reward and investigate the effect of the entropy weight α. Secondly, we use the learned maximum entropy population to train the AI 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. We compare our method with other methods, including Self-Play (SP) Proximal Policy Optimization (PPO) (Schulman et al., 2017b; Carroll et al., 2019), Population Based Training (PBT) (Jaderberg et al., 2017; Carroll et al., 2019), and Trajectory Diversity (TrajeDi)-based PBT (Lupu et al., 2021). To test the methods, we use the protocol proposed by Carroll et al. (2019), in which a human proxy model, HProxy, is used for evaluation. The human proxy model is 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 AI agents. The experimental details are shown in Appendix E. Our code is available as supplementary material.
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., 2021), player 1 must select a row while player 2 chooses a column independently. Both agents get the reward associated with the intersection of their choices at the end of the game. We use the same evaluation protocol as proposed by Lupu et al. (2021). From Figure 3, we can see that MEP converges faster than TrajeDi. We did an extensive hyper-parameter search for TrajeDi, as shown in Figure 7 in Appendix F.
Question 2. Does the population entropy reward increase the entropy of the population?
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 population and its corresponding population entropy is shown in Figure 4. This figure shows that as the training starts, the reward increases, and the population entropy decreases. Comparing the left two figures with α = 0 and the right two figures with α = 0.01, we can see that with the population entropy reward, the population entropy indeed converges to a higher value. We also try different values of α and investigate its effect on the reward and the population entropy, see Table 1 in Appendix F. The parameter α controls the balance between reward and entropy. The complete collection of the reward and population entropy learning curves with different α is shown in Appendix F.
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 to 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 of 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 HProxy, 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 – Overcooked. Following the evaluation protocol proposed by Carroll et al. (2019), 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 5 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?
We take a closer look at some examples. The maximum entropy population contains a diverse set of policies, shown in the supplementary video from 0:01 to 0:21. In the video, from 0:24 to 0:44, we show three human-AI 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, it sees a wide range of behaviors and learns to adapt to these policies. This helps to make the AI agent more robust during deployment.
Question 6. How does MEP perform compared to TrajeDi?
There is a recent related work on zero-shot coordination with a diversified population, which is called TrajeDi (Lupu et al., 2021). To the best of our knowledge, TrajeDi is the most related work. TrajeDi utilizes a trajectory-based diversity objective to obtain a 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 use 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 to TrajeDi(wPS). Overall, MEP shows better performance compared to 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 a real human player. For this human-AI coordination test, we 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-AI evaluation on AMT carried out by Carroll et al. (2019). These testing results are compatible because the evaluation procedure is the same and uses a between-subjects design, meaning each user was only paired with a single AI agent. The results are presented in Figure 6. The chart in Figure 6 shows that on average across all five layouts, MEP significantly outperforms SP and PBT and its performance is on par with the Human-Human coordination performance. For more detailed results, we take a closer look at the table in Figure 6. 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 5 layouts in comparison with SP and PBT. Now, we describe some representative cases below.
Question 8. What does AI do when paired with real human players?
Here, we show and analyze some qualitative behaviors that we observed during the real human-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 to 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 to 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 is 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-trained agents tend to overfit to their optimal opaque policies, whereas MEP-trained agent is more robust.

heading: 5 RELATED WORK
text: Recent works (Lerer & Peysakhovich, 2018; Tucker et al., 2020; Carroll et 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). However, collecting a large amount of human data in real life is expensive and time-consuming. We consider the zero-shot setting, where no behavioral data from the human partner is available during training (Hu et al., 2020). From a Bayesian perspective, when we don’t know what the human policies look like, we want to train the AI agent to be robust and be capable of collaborating with a diverse set of policies (Murphy, 2012). There is a growing amount of works on diversity in maximum 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 et al., 2017a; Haarnoja et al., 2018b) or discovering skills (Eysenbach et al., 2019; Zhao et al., 2021). However, how to train a diversified population through entropy maximization is still subjective to research. In Multi-agent Reinforcement Learning (MARL), a group of agents is trained to 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 a centralized surrogate objective – population entropy, to encourage diversity in the population. Subsequently, we train the AI agent with the maximum entropy population and dynamically sample the partner agent based on the learning progress, which shares similarities with Prioritized Fictitious Self-Play (PFSP) (Vinyals et al., 2019b). PFSP is designed exclusively for zero-sum competitive games, whereas we are concerned with cooperative games and derive the relationship between prioritized sampling and cooperation performance lower bound, see Appendix C. With prioritized sampling, we make the AI agent learn a policy that is generally suitable for all the strategies presented in the population.
The idea of MEP shares a 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 et al., 2017; Yu et al., 2017; Peng et al., 2018; Tan et al., 2018; Akkaya et al., 2019; Tang et al., 2020). MEP can be seen as a domain randomization technique, where the randomization 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-based diversity objective. To the best of our knowledge, 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 as Diversity via Determinants (DvD) (ParkerHolder et al., 2020) and Diversity-Inducing Policy Gradient (DIPG) (Masood & Doshi-Velez, 2019), which are 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., RockPaper-Scissors, Policy-Space Response Oracle (PSRO)-based methods (Balduzzi et al., 2019; PerezNieves et al., 2021; Liu et al., 2021) provide solutions to learn diverse behaviors. Our method is complementary to these previous works and could be combined with them. MEP bridges maximum entropy RL and PBT, which is generally applicable for many human-AI coordination tasks.

heading: 6 CONCLUSION
text: This paper introduces Maximum Entropy Population-based training (MEP), a deep reinforcement learning method for robust human-AI coordination. The derived population entropy theoretical objective encourages learning a diverse set of policies. Subsequently, with the learning progress-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 performance in comparison to state-of-the-art methods. Furthermore, in the real world evaluation with human players, MEP still demonstrates superior performance, which is comparable with humanhuman coordination performance. In addition, the qualitative examples show that MEP-trained policies are relatively flexible and robust to various human strategies.

heading: A POPULATION ENTROPY LOWER BOUND
text: Theorem 2. Let the population diversity be defined as:
PD({π(1), π(2), ..., π(n)}, st) := n∑ i=1 n∑ j 6=i CE(π(i)( · |st), π(j)( · |st)) + n∑ i=1 H(π(i)( · |st)). (11)
Let the population entropy be defined as:
PE({π(1), π(2), ..., π(n)}, st) := H(π̄( · |st)), where π̄(at|st) := 1
n n∑ i=1 π(i)(at|st). (12)
Then, we have
PD({π(1), π(2), ..., π(n)}, st) ≥ n2PE({π(1), π(2), ..., π(n)}, st), (13)
where n is the population size.
Proof. Cross entropy is given by: CE(π(i)( · |st), π(j)( · |st)) = − ∑ a∈A π(i)(at|st) log π(j)(at|st) (14)
Entropy is given by:
H(π(i)( · |st)) = − ∑ a∈A π(i)(at|st) log π(i)(at|st). (15)
We can derive the follows:
PD({π(1), π(2), ..., π(n)}, st) = n∑ i=1 ∑ j 6=i CE(π(i)( · |st), π(j)( · |st)) + n∑ i H(π(i)( · |st)) (16)
=n2 ∑ a∈A 1 n2 ( ∑ i,j −π(i)(at|st) log π(j)(at|st)) (17)
=n2 ∑ a∈A ∑ i − 1 n π(i)(at|st) ∑ j 1 n log π(j)(at|st) (18)
≥n2 ∑ a∈A ∑ i − 1 n π(i)(at|st) log ∑ j 1 n π(j)(at|st) (19)
=n2 ∑ a∈A −π̄(at|st) log π̄(at|st) (20)
=n2H(π̄( · |st)) (21) =n2PE({π(1), π(2), ..., π(n)}, st) (22)
From Equation (18) to Equation (19), we use Jensen’s inequality (Murphy, 2012).

heading: B POPULATION ENTROPY AND JENSEN-SHANNON DIVERGENCE
text: Lemma 3. The population entropy has the following relation with Jensen-Shannon Divergence (JSD):
H(π̄( · |st)) = JSD(π(1)( · |st), ..., π(n)( · |st)) + 1
n n∑ i=1 H(π(i)( · |st)), (23)
where JSD is given by
JSD(π(1)( · |st), ..., π(n)( · |st)) = 1
n n∑ i=1 ∑ a∈A π(i)(at|st) log π(i)(at|st) π̄(at|st) . (24)
Proof.
H(π̄( · |st)) = ∑ at∈A −π̄(at|st) log π̄(at|st) (25)
= n∑ i=1 ∑ at∈A − 1 n πi(at|st) log π̄(at|st) (26)
= n∑ i=1 ∑ at∈A 1 n πi(at|st) ( log πi(at|st) π̄(at|st) − log πi(at|st) )
(27)
=JSD(π(1)( · |st), ..., π(n)( · |st)) + 1
n n∑ i=1 H(π(i)( · |st)) (28)
From the derivation, we can see that maximizing the population entropy is equivalent to maximizing the JSD of all agent’s policies in the population and the entropy of each agent’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.

heading: C PRIORITIZED SAMPLING AND PERFORMANCE LOWER BOUND
text: Here, we use π(A) to denote the AI policy and use θ to represent the parameter of π(A). At the training step t, we use θt to denote the current parameter. {π(1), ..., π(n)} is the population used to train π(A). We want to find the optimal parameter θ∗ for the AI policy π(A), so that the AI agent could cooperate well with any agent in the population.
At each training step, we first sample π(i) from the population, then let π(i) to cooperate with π(A). Then, we use the sampled trajectory τ to train π(A). J(π(A), π(i)) is the excepted sum rewards achieved by π(A) and π(i) together. With prioritized sampling introduced in Section 3.4, we assign higher priority to the agent that is harder to collaborate with. To be more specific, let
i = arg min i
J(π (A) θt , π(i)), (29)
then we sample π(i) to cooperate with π(A)θt . During training, θ is updated using the gradient ascent method with non-increasing learning rate αt. At each training step t, there exists a subset of {1, ..., n} denoted by Kθt = {ik|k = 1, ..., l, l ≤ n}, such that
J(π (A) θt , π(i)) > J(π (A) θt , π(ik)) = Ct, if i /∈ Kθt , ik ∈ Kθt . (30)
Since prioritized sampling is used, one of ik′ (k′ ∈ 1, ..., l) could be sampled. Then the gradient of the current step t is
∇θtJ(π(A)θt , π (ik′ )) (31)
The parameter is updated as following:
θt+1 = θt + αt∇θt, (32) where αt is the learning rate at the training time step t.
Assume that {J(π(A)θt , π(i))|i = 1, ..., n} are smooth towards θt, then
g(θ) = min i∈{1,...,n}
J(π (A) θ , π (i)) (33)
is a piece-wise smooth function and ∇θtJ(π(A)θt , π(ik′ )) is equal to the gradient of g(θ) almost everywhere. Next we prove that using ∇θtJ(π(A)θt , π(ik′ )), it could also converge to a local maximum of g(θ).
Lemma 4. π(A) with parameter θ is trained with the population {π(1), ..., π(n)}. We use the learning progress-based prioritized sampling to sample the agent from the population for training. Assume that J(π(A)θ , π
(i)) is smooth towards the parameter vector θ and has an L-Lipschitz gradient for all i. θ is optimized using the gradient ascent with a sufficiently small constant step size. If J(π
(A) θ , π (i)) converges and doesn’t go to infinity, it would converge to a local maximum of g(θ). That is θ converges to a neighborhood Vθ̂ of θ̂, where θ̂ is define as
θ̂ = arg max θ∈Vθ̂ min i∈{1,...,n}
J(π (A) θ , π (i)). (34)
Proof. θt denotes the parameter of π(A) at the training step t. We define the index set of i, that J(π
(A) θt , π(i)) equal to mini∈{1,...,n} J(π(A), π(i)):
Kθt = {ik|k = 1, ..., l, l ≤ n}, (35) where ik satisfies
J(π (A) θt , π(i)) > J(π (A) θt , π(ik)) = Ct, if i /∈ Kθt , ik ∈ Kθt . (36)
ik′ is sampled from Kθt and current gradient is∇θtJ(π(A)θt , π(ik′ )).
If ik′ ∈ Kθt+l for all l > 0, the optimization process could be regarded as a non-convex optimization problem by gradient ascent, then θt converges to a local maximum almost surely by the assumption J(π
(A) θt , π(i)) has an L-Lipschitz gradient (Lee et al., 2016).
If ⋂ l>0Kθt+l = ∅, then first we prove that the sequence {θt} can’t converge to a saddle point. If θ̂ is a saddle point,∇θJ(π(A)θ̂ , π (ik′ )) = 0 for all ik′ ∈ Kθ̂, which means J(π (A) θt , π(ik′ )) are identical in a neighborhood of θ̂. This contradicts the local minimum convergence of θt (Lee et al., 2016).
Assume the convergent point θ̂ has a non-zero gradient∇θJ(π(A)θt , π(ik′ )), since we use a sufficiently small constant learning rate α, if J(π(A)
θ̂+∆θ , π(ik′ )) > J(π
(A) θ̂ , π(ik′ )), this would contradict the
convergence of θ, and if J(π(A) θ̂+∆θ , π(ik′ )) ≤ J(π(A) θ̂ , π(ik′ )), which means θ̂ is the local maximum.
From Lemma 4, we can see that with prioritized sampling, we could improve the lower bound of the cooperation performance between π(A) and the population {π(1), ..., π(n)}. In comparison, uniform sampling does not provide any guarantee on the worst case. We call θ′ the optimal solution of mean sampling:
θ′ = argmax θ ∑ i∈{1,...,n} J(π (A) θ , π (i)). (37)
Then, the worst cooperation between πθ′ and the population must be no greater than the cooperation between πθ̂ and the population. That is:
min i∈{1,...,n}
J(π (A) θ̂ , π(i)) ≥ min i∈{1,...,n} J(π (A) θ′ , π (i)). (38)

heading: D RELATION TO HUMAN-AI COORDINATION PERFORMANCE
text: To illustrate that we could improve the lower bound of human-AI coordination performance, here we introduce the connection between -close (Ko, 2006) and return, i.e., expected sum rewards.
Definition 1. We define that π(1) is -close to π(2) at the state st if∣∣∣∣π(1)(at|st)π(2)(at|st) − 1 ∣∣∣∣ < (39)
for all at ∈ A. If this is satisfied at every st ∈ S, we call π(1) is -close to π(2). Lemma 5. If an MDP has T time steps and π(1) is -close to π(2), then for all π(A), we have
(1− )TJ(π(2), π(A)) < J(π(1), π(A)) < (1 + )TJ(π(2), π(A)), (40) where J(π(i), π(A)) denotes the expected sum reward achieved by π(i) and π(A) collaborating with each other.
Proof. For all trajectory τ , we have
pπ(1),π(A)(τ) = p(s0)Π T−1 t=0 π (A)(at|st)π(1)(at|st)p(st+1|st, a(A)t , a(1)t ). (41) Since
(1− )π(2)(at|st) < π(1)(at|st) < (1 + )π(2)(at|st), (42) we have
(1− )T pπ(2),π(A)(τ) < pπ(1),π(A)(τ) < (1 + )T pπ(2),π(A)(τ). (43) And because
J(π(i), π(A)) = ∑ τ pπ(1),π(A)(τ)r(τ), (44)
where
r(τ) = r(s0, a0, ..., sT−1) = ∑ t r(st, at) and at = (a(i), a(A)). (45)
Therefore, we have
(1− )TJ(π(2), π(A)) < J(π(1), π(A)) < (1 + )TJ(π(2), π(A)). (46)
We use π(H) to denote the human player’s policy. From Lemma 5, we can see that if π(H) is similar to any of the policy π(i) in the population {π(1), ..., π(n)} in a certain degree, measured by -close, then its cooperation performance with the AI policy π(A), 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 π(A) cooperating with the population {π(1), ..., π(n)} as:
min i∈{1,...,n}
J(π(A), π(i)) = C. (47)
If π(H) is -close to the policy π(i) in the population, then we have
J(π(A), π(H)) > C(1− )T , (48) where T is the total steps in the trajectory.
Proof. If π(H) is -close to π(i), based on the property of -close, see Lemma 5, we have
J(π(A), π(H)) > (1− )TJ(π(A), π(i)). (49) Additionally, since
J(π(A), π(i)) > C, (50)
we have
J(π(A), π(H)) > C(1− )T . (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 1, we could say that it also optimizes the lower bound of expected sum rewards of the AI agent cooperating with the Human player, when the population is diverse and representative enough so that it is close to cover human behaviors.

heading: E EXPERIMENT DETAILS
text: We ran all the methods in each environment with 5 different random seeds and report the average episode reward and the standard deviation. The experiments of the maximum entropy populationbased training use the following hyper-parameters:
• The learning rate is 8e-4. • The reward shaping horizon is 5e6. • The environment steps per agent is 1.1e7. • 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.
• The population size is 5 for training the maximum entropy population. We use the beginner model, the middle model, and the best model of each agent in the population to form the final population for training the AI 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 γ 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 is 3. • The number of filters is 25. • The value function coefficient 0.1. • The β for prioritized sampling is 3.

heading: F EXPERIMENTAL RESULTS

Review summaries:
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.

The paper aims to address the important problem of training AI agents in multi-agent games. Standard self-play training leads to agents that overfit to a particular partner, and even naive population based training may not help much if the population is not very diverse. A number of recent works have looked into generating diversity in the partner strategies so that population based training methods can work better. By covering a diverse set of trajectories/policies, it is more likely that coordinating with a new partner (perhaps a human) at test time will fall in-distribution relative to our training set partners.  The paper proposes a population diversity metric based on cross-entropy between different pairs of agents in the population. They optimize a lower bound to this metric based on the population entropy. They also propose a 'prioritized sampling' procedure that determines which partner in the population the ego-agent should train with. They experiment on the game of Overcooked, compare with TrajeDi, and run a human experiment to check performance of coordination with humans at test time.

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.  

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.