Towards Unifying Behavioral and Response Diversity for Open-ended Learning in Zero-sum Games
Year: 2022

Abstract:
Measuring and promoting policy diversity is critical for solving games with strong non-transitive dynamics where strategic cycles exist, and there is no consistent winner (e.g., Rock-Paper-Scissors). With that in mind, maintaining a pool of diverse policies via open-ended learning is an attractive solution, which can generate auto-curricula to avoid being exploited. However, in conventional open-ended learning algorithms, there are no widely accepted definitions for diversity, making it hard to construct and evaluate the diverse policies. In this work, we summarize previous concepts of diversity and work towards offering a unified measure of diversity in multi-agent open-ended learning to include all elements in Markov games, based on both Behavioral Diversity (BD) and Response Diversity (RD). At the trajectory distribution level, we re-define BD in the state-action space as the discrepancies of occupancy measures. For the reward dynamics, we propose RD to characterize diversity through the responses of policies when encountering different opponents. We also show that many current diversity measures fall in one of the categories of BD or RD but not both. With this unified diversity measure, we design the corresponding diversity-promoting objective and population effectivity when seeking the best responses in open-ended learning. We validate our methods in both relatively simple games like matrix game, non-transitive mixture model, and the complex Google Research Football environment. The population found by our methods reveals the lowest exploitability, highest population effectivity in matrix game and non-transitive mixture model, as well as the largest goal difference when interacting with opponents of various levels in Google Research Football.

heading: 1 Introduction
text: Many zero-sum games have a strong non-transitive component [2, 4] in the policy space, and thus each player must acquire a diverse set of winning strategies to achieve high unexploitability [36], which has been widely validated by recent studies of constructing AIs with superhuman performance in sophisticated tasks, such as StarCraft [30, 28] and DOTA2 [25, 39]. The non-transitivity in games means there is not a dominating strategy and the set of strategies form a cycle (e.g., the endless cycles among Rock, Paper and Scissors). It is the presence of this special structure in games that requires players to maintain a diverse set of policies. Otherwise, we only need to seek the strongest one. Formally, the necessity of diversity for zero-sum games lies in three ways: (1) policy evaluation: with the presence of non-transitivity, one cannot justify the strength or weakness of a strategy through the outcome of the interaction with a single type of opponent; (2) avoiding being exploited [24]: since in non-transitive games a single strategy can be always beaten by another one, a diverse set of strategies
⇤Correspondence to Ying Wen <ying.wen@sjtu.edu.cn>. Code available at https://github.com/ sjtu-marl/bd_rd_psro
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
allows players to make corresponding responses when encountering different opponents; (3) training adaptable strategies [32]: a diverse set of training opponents helps gradually eliminate the weakness of a strategy, which can adapt to a wide range of opponents with very few interactions at test time.
The open-ended learning framework is a promising direction towards inducing a population of distinct policies in zero-sum games via auto-curricula. Although various open-ended algorithms have been proposed to derive diverse strategies [2, 24, 6, 22], there are no consistent definitions for diversity. One of the most intuitive principles to characterize diversity is to build metrics over the trajectory or state-action distribution [6, 20]. However, this perspective only focuses on the policy behaviors and ignores the reward attributes inherited from the Markov decision process. We argue that this is not reasonable since sometimes a slight difference in the policy can result in a huge difference in the final reward like, in maze. Contrary to this, another line of works builds the diversity measure over empirical payoffs [24, 2, 10], thus revealing the underlying diverse behaviors of a strategy through the responses when encountering distinct opponents.
In this work, based on all previous diversity concepts, we work towards offering a unified view for diversity in an open-ended learning framework by combining both the behavioral attribute and the response attribute of a strategy. The behavioral diversity is formulated through the occupancy measure, which is an equivalent representation of a policy. We hypothesize that the diversity in policy behaviors should be revealed by differences in the state-action distribution, and we use a general divergence family f -divergence to indicate the novelty of a new policy. On the other hand, gamescape [2] has been proposed to represent the response capacity of a population of strategies. Based on gamescape, we formulate a new geometric perspective to treat the response diversity by considering the distance to the gamescape.
To summarize, in this paper, we provide the following contributions:
• We formulate the concept of behavioral diversity in the state-action space as the discrepancies of occupancy measures and analyze the optimization methods in both normal-form games and general Markov games.
• We provide a new geometric perspective on the response diversity as a form of Euclidean projection onto the convex hull of the meta-game to enlarge the gamescape directly and propose the optimization lower bound for practical implementation.
• We analyze the limitation of exploitability as the evaluation metric and introduce a new metric with theoretical soundness called population effectivity, which is a fairer way to represent the effectiveness of a population than exploitability [16].

heading: 2 Preliminaries

heading: 2.1 Markov Games
text: The extension of Markov decision processes (MDPs) with more than one agents is commonly modelled as Markov games [18]. A Markov game with N agents is defined by a tuple < N,S, {Ai}Ni=1, P, {ri}Ni=1, ⌘, >, where S denotes the state space and Ai is the action space for agent i. The function P controls the state transitions by the current state and one action from each agent: P : S ⇥A1 ⇥ · · · ⇥AN ! P(S), where P(S) denotes the set of probability distributions over the state space S. Given the current state st and the joint action (a1, . . . , aN ), the transition probability to st+1 is given by P (st+1|st, a1, . . . , aN ). The initial state distribution is given by ⌘ : S ! [0, 1]. Each agent i also has an associated reward function ri : S ⇥Ai ⇥ · · ·⇥AN ! R. Each agent’s goal is to maximize the -discounted expected return Ri = E[ P1 t=0 tri(st, ati, a t i)], where i is a compact representation of all complementary agents of i. Specifically, for zero-sum games, the rewards satisfy that PN i=1 ri(s,a) = 0, and players need to behave competitively to achieve higher rewards.
In multi-agent reinforcement learning (MARL) [37], each agent is equipped with a policy ⇡i : S ⇥ Ai ! [0, 1] and the joint policy is defined by ⇡(a|s) = ⇧Ni=1⇡i(ai|s). In single-agent reinforcement learning, occupancy measure is a principled way to characterize a policy, which indicates how a policy covers the state-action space. Inspired by the definition from the single-agent setting, we define the joint occupancy measure in MARL induced by the joint policy ⇡(a|s) as:
Definition 1. (Joint Occupancy Measure in MARL) Let ⇢⇡(s) : S ! R denote the normalized distribution of state visitation by following the joint policy ⇡ = (⇡i,⇡ i) in the environment:
⇢⇡(s) = (1 ) 1X
t=0
tP (st = s|⇡) . (1)
Then the distribution of state-action pairs ⇢⇡(s,a) = ⇢⇡(s)⇡(a|s) is called occupancy measure of the joint policy ⇡.

heading: 2.2 Policy Space Response Oracle
text: Adapted from double oracle [23], policy space response oracle (PSRO) [16, 5] has been serving as a powerful tool to solve the nash equilibrium (NE) in zero-sum games. In PSRO, each player maintains a pool of policies, say Pi = {⇡1i , . . . ,⇡Mi } for player i and P i = {⇡1 i, . . . ,⇡N i} for player i. The so-called meta game APi⇥P i has its (k, j) entry as i(⇡ki ,⇡ j i), where the function
i encapsulates the reward outcome for player i like the winning rate or expected return. When player i adds a new policy ⇡M+1i , it will compute the best response to the mixture of its opponents:
Br(P i) = max ⇡M+1i
X
j
j iE⇡M+1i ,⇡j i [ri(s,a)].
where = ( i, i) is a distribution over policies in Pi and P i, which is usually a NE of APi⇥P i .
The empirical gamescape is introduced by [2] to represent the expressiveness of a population Pi in the reward outcome level given the opponent population P i: Definition 2. Given population Pi and P i with evaluation matrix APi⇥P i , the corresponding empirical gamescape (EGS) for Pi is defined as
GPi|P i := {convex mixtures of rows of APi⇥P i}.

heading: 2.3 Existing Diversity Measures
text: As the metric to measure the differences between models, diversity is an important topic in many fields of machine learning, including generative modelling [6], latent variable models [33], and robotics [1]. Specifically, in reinforcement learning (RL), diversity is a useful tool for learning transferable skills [7], boosting explorations [27], or collecting near-optimal policies that are distinct in a meaningful way. Despite the importance of diversity, as shown in Table 1, there has not been a consistent definition of diversity for RL, and various diversity concepts are used. [22] investigated behavioral diversity in multi-agent reinforcement learning through expected action variation, which is modeled as the average total variation distance of two action distributions under certain sampled states. Considering the geometric perspective that the determinant of the kernel matrix represents the volume of a parallelepiped spanned by feature maps, DvD [26] proposed the concept of population diversity using the determinant of the kernel matrix composed by the behavioral embeddings by multiple policies. Thanks to the tools of empirical game theory analysis, diversity can be modeled from the perspective of the empirical game. Effective diversity [2] is formulated as the weighted L1,1 norm of the empirical payoff matrix, which emphasizes what opponents a policy can win against. Also inspired by determinantal point process (DPP) [14, 38], [24] uses the expected cardinality to measure the diversity of a population.

heading: 3 A Unified Diversity Measure
text: Motivated by bisimulation metrics [8] to measure the similarity of two states in MDPs: d (si, sj) = maxa2A(1 c) · Rasi R a sj + c ·W1 ⇣ Pasi ,P a sj ; d ⌘ that considers both the immediate reward and the following transition dynamics, where c 2 [0, 1] and W1 is the 1-Wasserstein distance, we want to build a metric to measure the similarity of two policies in a given Markov game through the task-specific reward attributes and the interaction between policy behaviors and transition dynamics. We will firstly model the interaction between policy behaviors and transition dynamics through the principled occupancy measure in MDPs, which encodes how a policy behaves in a given state and how the state will transit. On the reward side, the interaction responses with different opponents feature a policy, which can be used for common diversity measures like DPP [24] and rectified Nash [2].

heading: 3.1 Behavioral Diversity via Occupancy Measure Mismatching
text: One fundamental way to characterize a policy in MDPs is through the distribution of the state-action pairs (s, a). Formally, we define the occupancy measure in multi-agent learning as the distribution of the joint state-action distribution. It has been shown that there is a one-to-one correspondence between the joint policy ⇡ and the occupancy measure ⇢⇡ . Proposition 1 (Theorem 2 of [29]). If ⇢ is a valid occupancy measure, then ⇢ is the occupancy measure for ⇡⇢(a | s) = ⇢(s, a)/ P a0 ⇢ (s, a
0), and ⇡⇢ is the only policy whose occupancy measure is ⇢.
Usually, the policy ⇡ is parameterized as a neural network, and tackling the policy in the parameter space is intractable. However, due to the one-to-one correspondence between the policy and occupancy measure, the occupancy measure ⇢⇡ serves as a unique and informative representation for the policy ⇡. Therefore, we are justified in considering diversity from a perspective of the occupancy measure.
Next, we will consider how to promote diversity in the framework of policy space response oracle. Suppose after t iterations of PSRO, the joint policy aggregated according the distribution of nash is ⇡E = (⇡i,⇡E i). The occupancy measure is given by ⇢⇡E . For player i in the t+ 1 iteration, it will seek the new policy ⇡0i, which can maximize the discrepancy between old ⇢⇡E and ⇢⇡0i,⇡E i .
max ⇡0i
Divocc(⇡ 0 i) = Df (⇢⇡0i,⇡E i ||⇢⇡i,⇡E i ) , (2)
where we use the general f -divergence to measure the discrepancy of two distributions.
We firstly investigate the objective under the one-step game by giving the following theorem: Theorem 1. By assuming the game is a one-step game (normal-form games, functional-form games, etc.) and policies among players are independent, the behavioral diversity can be simplified by:
Df (⇢⇡0i,⇡E i ||⇢⇡i,⇡E i ) = Es0⇠⌘(s)[Df (⇡ 0 i(·|s0)||⇡i(·|s0))] , (3)
where ⌘(s) is the initial state distribution.
Proof. See Appendix A.1.
For more general Markov games, computing the exact occupancy measure is intractable. However, notice that we are maximizing a f -divergence objective of occupancy measures, while occupancy measure matching algorithms in imitation learning try to minimize the same objective [13, 11, 9]. Leveraging the powerful tool from occupancy measure matching, we here propose an approximate method to maximize Divocc.
Prediction Error for Approximate Optimization. Inspired by random expert distillation [31], a neural network f✓̂(s,a) is trained to fit a randomly initialized fixed network f✓(s,a) on the dataset of state-action pair (s,a) ⇠ ⇢⇡E . Then we can assign an intrinsic reward rinti (s,a) = ||f✓̂(s,a) f✓(s,a)|| to the player, which will encourage the agent to visit the state-action with large prediction errors, thus pushing occupancy measure of the new policy to be different from the old one.
Alternative Solutions. There are also many other practical occupancy measure matching algorithms. One popular paradigm is learning a discriminator D(s,a) to classify the state-action pair (s,a) from the distribution ⇢⇡0i,⇡E i and the distribution ⇢⇡E . Then the trained D(s,a) can be used to construct different intrinsic rewards, which will correspond to different choices of f -divergence [13, 11, 9]. One major drawback of this paradigm is that the discriminator depends on the new policy ⇡0i and needs re-training once the policy ⇡0i is updated. Another popular paradigm is to learn an intrinsic reward directly from the target distribution ⇢⇡E like the prediction error. Besides using the prediction error, there are also other choices, including energy-based models (EBM) [19] and expert variance [3]. However, those methods usually require specialized training techniques.

heading: 3.2 Response Diversity via Convex Hull Enlargement
text: Take the two-player game for example. In games with more than two players, one can simply denote players other than player i as player i. Thanks to the empirical payoff matrix, another fundamental way to characterize the diversity of a new policy is through the reward outcome from the interaction with many different opponents. Each row in the empirical payoff matrix embeds how the corresponding row policy behaves against different opponent policies. We are therefore justified in using the row vector of the empirical payoff matrix to represent the corresponding row policy.
Formally, assume the row player maintains a pool of policies Pi = {⇡1i , . . . ,⇡Mi } and the column player maintains a pool of policies P i = {⇡1 i, . . . ,⇡N i}. The induced (k, j) entry in the empirical payoff matrix APi⇥P i is given by i(⇡ki ,⇡ j i), where the function i encapsulates the reward outcome for player i given the joint policy (⇡ki ,⇡ j i). Now we can define the diversity measure induced by the reward representations: Divrew(⇡ M+1 i ) = D(aM+1||APi⇥P i) (4)
a>M+1 := ( i(⇡ M+1 i ,⇡ j i)) N j=1 . (5)
D(aM+1||APi⇥P i) essentially measures the diversity of the new vector aM+1 given the presence of row vectors in APi⇥P i .
Inspired by the intuition of the convex hull that indicates the representational capacity of a pool of policies, the diverse new policy should seek to enlarge the convex hull of reward vectors as large as possible. To characterize the contribution of a vector to the enlargement of the convex hull directly, we define the novel diversity measure as a form of Euclidean projection:
Divrew(⇡ M+1 i ) = min
1> =1 0
||A>Pi⇥P i aM+1|| 2 2 . (6)
Unfortunately, there is no closed-form solution to this optimization problem. To facilitate the optimization, we propose a practical and differential lower bound: Theorem 2. For a given empirical payoff matrix A and the reward vector aM+1, the lower bound of Divocc is given by:
Divrew(⇡ M+1 i )
2min(A)(1 1>(A>)†aM+1)2
M + ||(I A>(A>)†)aM+1||2 , (7)
where (A>)† is the Moore–Penrose pseudoinverse of A>, and min(A) is the minimum singular value of A.
Proof. See Appendix A.2.
Let F (⇡M+1i ) be the right hand of the inequality. Then F (⇡ M+1 i ) serves as a lower bound of Divrew(⇡ M+1 i ).

heading: 4 A Unified Diverse Objective for Best Response
text: Equipped with the unified diversity measure, we are ready to propose the diversity-aware response during each iteration of PSRO:
argmax ⇡0i Es,a⇠⇢⇡0i,⇡E i [r(s,a)] + 1 Divocc(⇡
0 i) + 2 Divrew(⇡ 0 i) . (8)
If both 1 and 2 are 0, then objective is a normal best response.
Algorithm 1 Gradient-based Optimization for Unified Diverse Response 1: Input: population Pi for each i, meta-game APi⇥P i , state-action dataset {(s,a)}, weights 1
and 2 2: i, i Nash on APi⇥P i 3: ⇡E Aggregate according to i, i 4: rinti (s,a) Train fixed reward from distribution (s,a) ⇠ ⇢⇡E by EBM or prediction errors. 5: ✓⇤ Train ⇡0i(✓) against fixed opponent policies ⇡E i by single-agent RL algorithm with
ri(s,a) = rexti (s,a) + 1r int i (s,a), rexti is the original reward function.
6: @F@aM+1 Simulate the reward row vector aM+1 using new ⇡ 0 i(✓) and compute @F @aM+1 analytically. 7: ✓̂ Train ⇡0i(✓?) against a new mixture distribution i + 2 @F@aM+1 of opponent policies. 8: Output: policy ⇡0i(✓̂)

heading: 4.1 On the Optimization of Diverse Regularizers
text: Discussions on Optimizing Behavioral Diversity. As discussed in Section 3.1, diversity in the occupancy measure level is fully compatible with the reinforcement learning task since the agent can get an intrinsic reward rinti (s,a) to indicate the novelty of a state-action pair (s,a). Therefore, to optimize the first two items in the objective, we only need to add the original reward by the 1- weighted intrinsic reward. Another issue we need to address is to sample (s,a) from the distribution ⇢⇡E , which has been mentioned in Section 3. Since ⇡E is not a true policy but only a hypothetical policy aggregated according to the mixture ( i, i), sampling from ⇢⇡E is equivalent to sampling from ⇢⇡ki ,⇡ji with probability k i j i.
Discussions on Optimizing Response Diversity. Optimizing Divrew is not so easy since it involves an inner minimization problem. Fortunately, we have derived a closed-form low-bound F , which can serve as a surrogate for the outer maximization.
Assume the policy ⇡0i is parameterized by ✓ as ⇡0i(✓). Then the gradient of F with respect to ✓ is given by:
@F (⇡0i(✓))
@✓ = @aM+1 @✓ @F @aM+1 =
✓ @ i(⇡0i(✓),⇡ 1 i)
@✓ , . . . ,
@ i(⇡0i(✓),⇡ N i)
@✓
◆ @F
@aM+1 .
@F @aM+1 controls weights of the policy gradient backpropagated from different opponents policies ⇡ i. For practical implement, we sample an opponent j according to the absolute values of @F@aM+1 and then train ⇡0i against the opponent ⇡ j i using gradient descent or ascent, which depends on the sign of the jth entry of @F@aM+1 .
Joint Optimization. One issue worth our notice is that the update direction of Divrew will heavily rely on the initialization of ⇡0i(✓). A bad initialization of ✓ will make the response diversity tell ⇡0i to update toward worse rewards. Therefore, we propose to first optimize the first two items in the objective jointly and then optimize ⇡0i using Divrew. The final unified diverse response with gradient-based optimization is described in Algorithm 1.
In addition to the gradient-based optimization, we also provide other kinds of optimization oracles suitable for different games. Pseudocodes can be found in Appendix G.

heading: 4.2 Evaluation Metrics
text: Exploitability. Exploitability [16] measures the distance of a joint policy from the Nash equilibrium. It shows how much each player gains by deviating to their best responses:
Expl(⇡) = NX
i=1
(max ⇡0i
i(⇡ 0 i,⇡ i) i(⇡i,⇡ i)) . (9)
Therefore, the smaller exploitability means the joint policy is closer to the Nash equilibrium.
Population Effectivity. Note the limitation of exploitability is that it only measures how exploitable a single joint policy is. Therefore, to evaluate the effectiveness of a population, we first need to get an aggregated policy from a population, and we usually use the Nash aggregated policy output by PSRO. Since the Nash is computed over the meta game, which varies with the opponents, the aggregation may be sub-optimal and cannot be used to represent a population. Intuitively, the aggregation weights, and further, the evaluation of a population should not be determined by the population that a specific opponent holds. To address this issue, we propose a generalized opponent-free concept of exploitability called Population Effectivity (PE) by looking for the optimal aggregation in the worst cases:
PE({⇡ki }Nk=1) = min⇡ i max 1>↵=1 ↵i 0
NX
k=1
↵k i(⇡ k i ,⇡ i) . (10)
PE is again a NE over a two-player zero-sum game, where the player owning the population optimizes towards an optimal aggregation denoted by ↵, while the opponent can search over the entire policy space. Similar ideas of revealing the relationship between the minimax objective and diversity can be also found in [40, 34]. Next, we offer a simple example to further illustrate the limitations of exploitability and superiority of PE. Example 1. Consider the matrix game Rock-Scissor-Paper, where 1(⇡1,⇡2) = ⇡>1 A⇡2 and
2(⇡2,⇡1) = ⇡>2 B⇡1, ⇡1 2 R3, ⇡2 2 R3, A = "
0 1 1 1 0 1 1 1 0
# , B = A>. Suppose
player 1 holds the population P1 = { "
1 0 0
# , " 0 1 0 # , " 0 0 1 # }, i.e. {Rock, Scissor,Paper} and
P2 = { "
1 0 0
# }, i.e. {Rock}. Then the meta-game AP1⇥P2 = " 0 1 1 # . The nash aggregated joint
policy (⇡1,⇡2) = ( " 0 0 1 # , " 1 0 0 # ). Now we can compute Expl((⇡1,⇡2)) as:
Expl((⇡1,⇡2)) = max ⇡01
1(⇡ 0 1,⇡2) 1(⇡1,⇡2) + max
⇡02 2(⇡
0 2,⇡1) 2(⇡2,⇡1) (11)
= max ⇡01
1(⇡ 0 1,⇡2) + max
⇡02 2(⇡
0 2,⇡1) = 2. (12)
Now notice that the contribution of player 1 to the exploitability is max⇡02 2(⇡ 0 2,⇡1), which equals 1. However, it is not reasonable that player 1 and 2 have the same contribution to the exploitability since player 1 has a perfect diverse policy set. Instead, if we use PE as the metric:
PE(P1) = 0 , (13)
which justifies that player 1 has already found a perfect population.
In the following theorem, we show that PE is a generalized notion of exploitability under certain conditions and has some desirable properties: Theorem 3. Population effectivity has the following properties: P1. Equivalence: If N = 1 and the underlying game i(·, ·) is a symmetric two-player zero-sum game, PE is equivalent to exploitability.
P2. Monotonicity: If there are two populations Pi, Qi and Pi ✓ Qi, then PE(Pi)  PE(Qi), while the relationship for exploitability of the Nash aggregated policies of Pi and Qi may or may not hold.
P3. Tractability: If the underlying game i(·, ·) is a matrix game, then computing PE is still solving a matrix game.
Proof. See Appendix A.3.

heading: 5 Experiments
text: To verify that our diversity-regularized best response algorithm can induce a diverse and less exploitable population, we compare our methods with state-of-the-art game solvers including Selfplay [12], PSRO [16], PSROrN [2], Pipeline-PSRO (P-PSRO) [21], DPP-PSRO [24]. In this section, we want to demonstrate the effectiveness of our method to tackle the non-transitivity of zero-sum games, which can be shown via higher PE, lower exploitability, and diverse behaviors. Beyond the simple games, we also have the results on the complex Google Research Football game, and our methods can still work. In all the following experiments, we choose the appropriate diversity weights 1 and 2 by extensive hyper-parameter tuning. We also conduct ablation study by choosing different 1 and 2 in Appendix F. The environment details are in Appendix D, and the hyper-parameter settings for each experiment are in Appendix E.3.
Real-World Games. [4] studies the properties of some complex real-world games, including AlphaStar and AlphaGO. We test our method on the empirical games generated through the process of solving these real-world games. In Figure 1a, we report the exploitabilities of different algorithms during solving the AlphaStar game, which contains the meta-payoffs for 888 RL policies. We report values of exploitability and PE during the growth of the population in Figure 1a and Figure 1b. The result shows that with our unified diversity regularizer, our methods achieve the smallest exploitability and largest population effectivity, while most baselines fail to recover the diverse strategies and are easily exploited.
Non-Transitive Mixture Games. This zero-sum two-player game consists of 2l+1 equally-distanced Gaussian humps on the 2D plane. Each player chooses a point in the 2D plane, which will be translated into a (2l + 1)-dimensional vector ⇡i with each coordinate being the density in the corresponding Gaussian distribution. The payoff of the game is given by: i(⇡i,⇡ i) = ⇡>i S⇡ i + 1>(⇡i ⇡ i). According to the delicately designed S, this game involves both the transitive component and nontransitive component, which means the optimal strategy should stay close to the center of the Gaussian and explore all the Gaussian distributions equally.
We firstly visualize the exploration trajectories during different algorithms solving the game in Figure 2. It shows that the best response algorithm regularized by both BD and RD achieves the most diverse trajectories. Although our algorithm finds the most diverse trajectories, such superiority is not revealed by the metric of exploitability in the last row of Table 2. On the other hand, we also report the PE values for the final population generated by different algorithms in Table 2. It can found that our unified diversity regularizer can always help PSRO dominate other baselines in terms of
population effectivity, which also justifies why PE is a better metric to evaluate diverse populations. The details of computing approximate PE using PSRO can be found in Appendix B.
Google Research Football. In addition to the experiments on relatively simple games, we also evaluate our methods on a challenging real-world game named Google Research Football (GRF) [15]. GRF simulates a complete football game under standard rules with 11 players on each team, and a normal match lasts for 3000 steps. The enormous exploration spaces, the long-time horizon, and the sparse rewards problems in this game make it a challenging environment for modern reinforcement learning algorithms. In such complex scenarios, the exploitability of a certain policy or PE of a certain population would be hard to calculate because both metrics involve a max or min operator, and the approximate best response can be quite inaccurate for this complex game. Since our goal is to find robust policies with strong capabilities in real-world games, we compare the average goal differences between the aggregated policies of different methods and the built-in bots with various difficulty levels of GRF. The models within each aggregated policies are trained for 300000 steps under the generalized framework of Self-play [12] by selecting opponents according to the probabilities output by different methods.
As depicted in Figure 3, policies trained by PSRO with both BD and RD achieve the largest goal differences when playing against the built-in bots. Moreover, they have an average of 60% win-rate over other baseline methods (see the table in the Appendix C). We do not report the results of DPP-PSRO since it needs evolutionary updates and cannot scale to such a complex setting. We also abandon the pipeline trick for ease of implement since it does not affect the relative performance among algorithms. Additionally, the discussion of robustness of policies trained with different methods, the network architectures, the hyperparameters, and other detailed experimental setups can also be found in Appendix C.

heading: 6 Conclusions
text: This paper investigated a new perspective on unifying diversity measures for open-ended learning in zero-sum games, which shapes an auto-curriculum to induce diverse yet effective behaviors. To this end, we decomposed the similarity measure of MDPs into behavioral and response diversity and showed that most of the existing diversity measures for RL can be concluded into one of the categories of them. We also provided the corresponding diversity-promoting objective and optimization methods, which consist of occupancy measure mismatching and convex hull enlargement. Finally, we proposed population effectivity to overcome the limitation of exploitability in measuring diverse policies for open-ended algorithms. Experimental results demonstrated our method is robust to both highly non-transitive games and complex games like the Google Research Football environment.
We also include a discussion on the limitation of our method here. Regarding the limitations from the perspective of the proposed algorithm, One limitation is that the diversity weights 1 and 2 in our paper are manually tuned. Our methods target the non-transitivity in zero-sum games. Therefore, the weights for a game should be related to how strong the non-transitive component is. In future work, we will work towards quantifying the non-transitivity component of a given game automatically and determining the diversity weights correspondingly. Similar ideas have been tested in single-agent RL cases on learning the discount rate [35]. In addition, our methods also inherit the limitations from the framework of PSRO. The advantage of the PSRO based methods also depends on the amount of non-transitivity of the environment [4]. To be specific, if there aren’t too many cyclic policies involved in the environment (such as Rock->Paper->Scissor), the newest model generated by the naive self-play training paradigm could probably be the strongest one (a Nash Policy), which implies that a naive self-play would suffice to solve the problem. The PSRO methods will then lose their advantage under such circumstances since they need extra computation resources to maintain meta-payoffs. Regarding the limitations from the perspective of real-world application, the game dynamics could be complex and there could be a lot of randomnesses involved in the real-world games. Thus, the approximated best response trained by reinforcement learning algorithms towards a certain policy could be inaccurate. In the Google Research Football experiment, we empirically save the checkpoint when the model win-rate is stable (i.e. the change of win-rate is less than 0.05 during two checks with the check frequency is 1000 model steps) or the training model steps reach an upper bound of 50000. These criteria could be potentially improved or further studied for all the PSRO based methods.

heading: Acknowledgments
text: This work is supported by Shanghai Sailing Program (21YF1421900). The authors thank Minghuan Liu for many helpful discussions and suggestions.

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

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

This paper is concerned with learning in zero-sum Markov games, in which there are often non-transitive dynamics between policies/strategies (e.g., Rock beats Scissors beats Paper beats Rock ...). A common approach to avoid getting stuck in cycles or local optima when training in such domains is to encourage algorithms to discover *diverse* solutions or policies.   This paper discusses and formalises how diversity measures can be split up in two broad categories: **behavioral diversity** measures, which measure whether different policies visit different state-action distributions, and **response diversity** measures, which measure whether different policies obtain different vectors of empirical outcomes against a population of opponents. For each of these two categories, the paper proposes a concrete measure and (approximate) methods to optimise them within a Policy Space Response Oracle (PSRO) framework. Additionally, the paper proposes a new Population Effectivity metrid, which is argued to be more fair and informative for evaluating the effectiveness of a population of policies than the Exploitability metric.  The additional diversity objectives are shown to improve training in several different domains.