Towards Unifying Behavioral and Response Diversity for Open-ended Learning in Zero-sum Games
Authors: Xiangyu Liu
Hangtian Jia
Ying Wen
Yujing Hu
Yingfeng Chen
Changjie Fan
Zhipeng Hu
Yaodong Yang
Venue: NeurIPS 2021 Poster (2021)
Keywords: reinforcememt learning
multi-agent learning
diverse policies

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 \textit{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 \textit{Google Research Football}.

Towards Unifying Behavioral and Response Diversity for Open-ended Learning in Zero-sum Games
Xiangyu Liu', Hangtian Jia², Ying Wen', Yujing Hu?
Yingfeng Chen", Changjic Fan", Zhipeng Hu", Yaodong Yang²
Shanghai Jiao Tong University, "Netease Fuxi AT Lab, IInstitute for AI, Peking University liuxiangyu999 @ @jw.eeuunn ying.wen@ www.weeeeeed..... yaodong yaodong. pku.edu.en
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., Sock-Paper-SScisoors 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 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 the categories of BD or RD but not both. With this unified diversity measure, we design the corresponding diversity-promotte 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 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.
Introduction
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 achieve high unexploitability [36], which has been widely validated by recent studies of constructing Als 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 three ways: (1) policy evaluation: with the presence of non-transinn non-transitivity, one cannot justify the strength or weakness of strategy through the outcome of the interaction with a single type of opponent; (2) avoiding being exploited [24]: since in non-transitive games single strategy can be always beaten by another one, diverse set of strategies
"Correspondence to Ying Wen <ying. wen @ sjtu.edu.cn> sj mau-marlbbdddddppee
Code available at https: /tt///gttttu///.///////eee.... com/
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

allows players to make corresponding responses when encountering different opponents; (3) training adaptable strategies [32]: diverse set of training opponents helps gradually eliminate the weakness of strategy, which can adapt to wide range of opponents with very few interactions at test time.
The open-ended learning framework is promising direction towards inducing population of distinct policies in zero-sum games via auto-curricla.. Although various open-ended algorithms have been proposed 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 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 slight difference 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 payoft' [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 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 population of strategies. Based on gamescape, we formulate 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 discrep- ancies of occupancy measures and analyze the optimization methods in both normal-form games and general Markov games.
We provide new geometric perspective on the response diversity as a form of Fuclidean 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 the evaluation metric and introduce new metric with theoretical soundness called population esfectivity, which is fairer way to represent the effectiveness of a population than exploitability [16].
2 Preliminaries
2.1 Markov Games
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, ) 1= P, (r.) (ri 7 2, where S denotes the state space and A, 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: x Ai X x...X X AN + P(S), where P(S) denotes the set of probability distributions over the state space S. Given the current state s; and the joint action (aI,..., aN). the transition probability to St+1 is given by P(s++1|sp, 1s,. ......, aN). The initial state distribution is given by 7: S + 00. 1]. Each agent also has an associated reward function r; S x A, X ... X AN + R. Each agent's 's goal is to maximize the y-discounted expected return R E o "r, a .)]. where -i is compact representation of all complementary agents of i. Specifically, for zero-sum games, the rewards satisfy that ΣN (r,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 n. S x A: + [0, 1] and the joint policy is defined by म (als) = IT (a (s). In single-agent reinforcement learning, occupancy measure is a principled way to characterize policy, which indicates how 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:

---

Table I: Comparisons of Different Algorithms.
Method
Tool for Diversity
BD
RD
Game Type
DvD PSRON PSRO,N DPP-PSRO
Determinant
Single-agent
None
X
X
n-player general-sum game
L1.1 norm
2 2-player zero-sum game
Determinantal point process
X
2 player general-sum game
Our Methods
Occupancy measure & convex hull
n-player general-sum game
Definition 1. (Joint Occupancy Measure in MARL) Let P (s) S - R denote the normalized
distribution of state visitation by following the joint policy π (T T--) the environment:
(*( -1
Σ
P(s = s|T)
(I)
t=0
Then the distribution of state-action pairs Pir (s, a) Pm (s))s(a)s) is called occupancy measure of the joint policy π.
2.2 Policy Space Response Oracle
Adapted from double oracle [23]. policy space response oracle (PSRO) [16, 5] has been serving powerful tool to solve the nash equilibrium (NE) in zero-sum games. In PSRO, each player maintains a pool of policies, say 33 =
T.²) for player i and p=; _......., क _ー player -i. The so-called meta game 13, has its (k, j) entry ( x where the function 6, encapsulates the reward outcome for player like the winning rate or expected return. When player i adds a new policy n.
for
it will compute the best response to the mixture of its opponents:
Br( max Σ oo
EoLEE
_ a)).
where a = (0s, is a distribution over policies in T. and P_is which is usually a NE of Ap......
The empirical gamescape is introduced by [2] represent the expressiveness population P; in the reward outcome level given the opponent population B_
Definition 2. Given population B. and Q with evaluation matrix Ap,xp_ the corresponding empirical gamescape (EGS) for G is defined as
G = {convex mixtures of rows of Ap.xp J.
2.3 Existing Diversity Measures
As the metric measure the differences between models, diversity is important topic in many fields of machine learning, including generative modelling [6], latent variable models [33], and roboties [1]. Specifically, in reinforcement learning (RL), diversity is useful tool for learning transferable skills [7], boosting explorations [27], or collecting near-optimal policies that are distinct in meaningful way. Despite the importance of diversity, shown in Table 1, there has not been consistent definition of diversity for RI., 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) formulated as the weighted L1,1 norm of the empirical payoff matrix, which emphasizes what opponents policy can win against. Also inspired by determinantal point process (DPP) [14, 38), [24] uses the expected cardinality to measure the diversity of population.
3

---

3 A Unified Diversity Measure
Motivated by bisimulation metrics [8] to measure the similarity of two states in MDPs: (s,, 85),
maxae c) R_ R c (Pa, P.. PS;:d) that considers both the immediate reward and the following transition dynamics, where E [0, 1] and W1 is the 1-Wasserstein distance, want to build a metric to measure the similarity two policies in 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 policy behaves in given state and how the state will transit. On the reward side, the interaction responses with different opponents feature policy, which can be used for common diversity measures like DPP [24] and rectified Nash [2].
3.1 Behavioral Diversity via Occupancy Measure Mismatching
One fundamental way characterize policy in MDPs is through the distribution of the state-action pairs as. 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 Pn.
Proposition 1 (Theorem 2 of (291). If p is a valid occupancy measure, then is the occupancy measure for pp 8) a(s,a)/ Eas P (8, a and up is the only policy whose occupancy measure is
Usually, the policy is parameterized as neural network, and tackling the policy in the parameter space is intractable. However, due to the one-to-one correspondence between the policy and occu- pancy measure, the occupancy measure Prr serves as a unique and informative representation for the policy и. Therefore, we are justified in considering diversity from perspective of the occupancy measure.
Next, we will consider how to promote diversity in the framework of policy space response oracle. Suppose after iterations of PSRO, the joint policy aggregated according the distribution of nash is TE (T:: gg .). The occupancy measure is given by Pre- For player i in the I ++ 1 iteration, it will seek the new policy T/. which can maximize the discrepancy between old Pre and Pat.me_..
max Divace (m.) Dy(Pot ( x
where we use the general f-divergence 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-fore games, functional-- form games, etc.) and policies among players are independent, the behavioral diversity can be simplified by: (MM,,,,n_,llPp,0e
(
(3)
where 7(5) is the initial state distribution.
Proof. See Appendix A.I.
For more general Markov games, computing the exact occupancy measure is intractable. However, notice that we are maximizing a /ddivergence objective 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 Div
Prediction Error for Approximate Optimization. Inspired by random expert distillation [31], a neural network fī (s, a) is trained to fit randomly initialized fixed network fo (s. on the dataset of state-action pair (s,a) frg. Then we can assign an intrinsic reward (f a) = [| a) Ss(s, a)ll 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 discriminator D(s, a) to classify the state-action pair (s, a) from the distribution Pxç,s_; and the distribution Pag. Then the trained (ss, a) can be used to construct different intrinsic rewards, which will correspond to different choices of f f-divergence [13, 11, 91. One major drawback of this paradigm that the discriminator depends on the new policy T/. and needs re-training once the policy ni updated. Another popular paradigm is learn intrinsic reward directly from the target distribution peg 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.
3.2 Response Diversity via Convex Hull Enlargement
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 -in -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 7, { ...., T.M and the column player maintains a pool of policies p: fm_....,,""" The induced (R: entry in the empirical payoff matrix Ag, x3_,, is given by ox _',,). where the function Φ; encapsulates the reward outcome for player given the joint policy : Now we can define the diversity measure induced by the reward representations:
Divrew ( M+1 D(am++ A
(4)
M+11 (dt( +
D(a Al Ap.. xq_..) essentially measures the diversity of the new vector aM+1 given the presence of row vectors in A3, xT
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 form of Euclidean projection:
Divrew (T) M 1+ = min [|...
aM+1
p=
020
Unfortunately, there is no closed-form solution to this optimization problem. To facilitate the optimization, we propose practical and differential lower bound:
Theorem 2. For given empirical payoff matrix A and the reward vector aM+1, the lower bound of Divoce is given by:
M Divrow M+1 o² min (A)(1 - (AT) ) aM+1)² + +I[[I - A (ATA) )am
(7)
where (AT is the Moore-Penrose pseudoinverse of AT, and minn(A) is the minimum singular value of A.
Proof. See Appendix A.2.
Let Fm be the right hand of the inequality. Then F(xM+1) serves as a lower bound of Div (T)) M+1).
4 A Unified Diverse Objective for Best Response
Equipped with the unified diversity measure, we are ready to propose the diversity-awan response during each iteration of PSRO:
arg max FF E. (r(s, a)] + A Divoce + X2 Divrew
(8)
If both a and Ag are 0, then objective is a normal best response.
5

---

Algorithm I Gradient-based Optimization for Unified Diverse Response
1: Input: population Pi for each meta-game xq i state-action dataset {(8, a)), weights À and 22
2: 0, --j f- Nash on Apxxy: x
3: TE f- Aggregate according to 04, 0-i
4: r (s, f Train fixed reward from distribution (s, a) Prg by EBM prediction errors.
5: 0* + Train m. (0) against fixed opponent policies TE_, by single-agent RL algorithm with
rs a) = (s, + Apri"((s, (s, a). rf is the original reward function.
6: 0mar
aF + Simulate the reward row vector a using new (0) and compute S0rri
ar analyti-
cally.
7: 0 < TTainn =((0)) against a new mixture distribution a-j + λ2 8axr11
ar of opponent policies.
8: Output: policy (0)
4.1 On the Optimization of Diverse Regularizers
Discussions 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 get intrinsic reward r (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 address is to sample (s, a) from the distribution Prg. which has been mentioned in Section 3. Since тe is not a true policy but only a hypothetical policy aggregated according to the mixture (a,, -=:), sampling from Præ is equivalent sampling from Pr with probability ofoL.
Discussions on Optimizing Response Diversity, Optimizing Div is not so easy since it involves an inner minimization problem. Fortunately, we have derived closed-form low-bound F, which can serve as a surrogate for the outer maximization.
Assume the policy ni is parameterized by 0 as (0). Then the gradient of F with respect to 0 is given by:
OF (F) 0am+1 OF
Ooh (T((0) =I.)
(0)(
OF
00
00 0aM+1
00
00
θaM+1
Jau++1 controls weights of the policy gradient backpropagated from different opponents policies T-j- For practical implement, we sample an opponent j according the absolute values of aF and Bass:
aF
then train x. against the opponent ~²_ using gradient descent or ascent, which depends on the sign of the jth. entry of OF Jam-11
Joint Optimization. One issue worth our notice is that the update direction of Divrew will heavily rely on the initialization of T(()). A bad initialization of 0 will make the response diversity tell T to update toward worse rewards. Therefore, we propose to first optimize the first two items in the objective jointly and then optimize Tद using Divrew- The final unified diverse response with gradient-based optimization is described in Algorithm 1.
In addition to the gradient-basee optimization, also provide other kinds of optimization oracles suitable for different games. Pseudocodes can be found in Appendix G.
4.2 Evaluation Metries
Exploitability. Exploitability [16] measures the distance of joint policy from the Nash equilibrium. shows how much each player gains by deviating to their best responses:
Expl(T) (max (i क 6.(T,, x-)))
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 single joint policy is. Therefore, to evaluate the effectiveness of a population, we first need to get an aggregated policy from 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 population. Intuitivelyy 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 the worst cases:
(E
k )k=1) min max Σ anoi( π-1).
(10)
PE is again NE over two-player zero-sum game, where the player owning the population optimizes towards an optimal aggregation denoted by a, 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 simple example to further illustrate the limitations of exploitability and superiority of PE.
Example 1. Consider the matrix game Rock-Scissor- where di (TI, TT) क. Amz and
0
-1
(2( mI) = T2 BTi, TI
R3, 72 E
R3,
A
= AT Suppose
1
-1
0
0
player 1 holds the population B1
1
0
}, i.e. {Rock, Scissor, Paper} and
0
1
1 J. i.e. {Rock). Then the meta-game Acp, xqp_
D2 -x=1(
{
-1
The nash aggregated joint
1
policy (T1)
0
). Now we can compute Expl(( 12)) as:
0
EXpl((TI, T2))
max 01 ( π2) di (TI, m2) + max (2 mI) (2((T2 TT)
(11)
max 61 (#1, m2) max (2 m)) = 2.
(12)
Now notice that the contribution of player to the esploitubility is max cha(T') TI), which equals 1. However, is not reasonable that player 1 and 2 have the same contribution to the exploitability since player 1 has perfect diverse policy set. Instead, if we use PE as the metric:
PE(P1) 0,
(13)
which justifies that player 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:
PI. Equivalence: If N = 1 and the underlying game (ix(,)) symmetric two-player zero-sum game, PE is equivalent to exploitability.
P2. Monotonicity: If there two populations B. Di and Ti C Di then PE( S PE(D)), while the relationship for exploitability of the Nash aggregated policies of Gg and Q; may or may not hold.
P3. Tractability: If the underlying game (el.s)) a matrix game, then computing PE still solving a matrix game.
Proof. See Appendix A.3.
7

---

AphaStor
PSRO
PSR0
P-PS20
P-PSto
PERD-N
PS00
Self play
Nacastive Phosutaton Eitecdiyy
Solpley
DPP PERD
DPP PSRO
P-PSRO W RD
P-PSRDw 2D
Expotabiity
P-P1SPO W. BD
P-SSRD 3D
IM4PSPIO W. BUMOO
P-PSRDD w. 306ND
10"
terattone
beration
(a)
(b)
Figure I: Exploiiiiayyyl vs. training iterations (the number of times the optimization oracle is called) on the AlphaStar game, (b): Negative Population Effectivity vs. training iterations on the AlphaStar game. Ablation studies of P-PSRO only with BD RD are also reported.
PSRO
PSRD-rN
PAPSRO
DPE-PSBO
P.PSRO w.
P-PSRO w. P.PSRD w. BD&RD
X
X
X
Figure 2: Exploration trajectories during training process Non-Transitive Mixture Games.
5 Experiments
To verify that our diversity-regulame
best response algorithm can induce a diverse and less ex- ploitable population, compare methods with sfate-of-the-art game solvers including Self- play [12], PSRO [16], PSRO,, N [2]. want 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,
Pipeline-PShRl
(P-PSRO) [21], DPP-PSRO [24]. this section,
also have the results the complex Google Research Foothall game, and
methods can still work. In all the following experiments, we choose the appropriate diversity weights A and X2 by extensive happer-pramettr tuning. We also conduct ablation study by choosing different A and A2 in Appendix F. The environment details are in Appendix D, and the hyper-paramete settings for each experiment are Appendix E.3.
Games. [4] studies the properties of some complex real-world games, including AiphaStar and AlphaGO. We test method on the empirical games generated through the process of solving these real-world games. In Figure la, we report the exploitabilities of different algorithms during solving the AlphaStar game, which contains the meta-payoff' for 888 RL policies. We report values of exploitability and PE during the growth of the population Figure 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.
Ton-Transitive Mixture Games. This zero-sum two-player game consists of 2/+ squally-distaneee Gaussian humps the 2D plane. Each player chooses point in the 2D plane, which will be translated into a (2l + 1)-dimension vector n; with each coordinate being the density in the corresponding Gaussian distribution. The payoff of the game is given by:d,(m,, T-4) = म. ST_; + 1 (TT - π --:). According to the delicately designed S, this game involves both the transitive component and non- transitive 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 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. can found that unified diversity regularizer always help PSRO dominate other basclines in terms of

---

Table 2: PEx 102 for populations generated by different methods when encountering opponents with varying strength on tonntrrane Mixture Games. The OS (Opponent Strength) associated with the PE represents the strength the opponent during the process of using PSRO solve it. More details can be found in Appendix B. We also report the Exploitability 102 for each population in last row.
PE(OS)
PSRO
PSRO.N
P-PSRO
DPP-PSRO
P-PSRO
P-PSRO w. BD
P-PSRO
BD&RD
PG(5)
1.11
22.11
0.14
40.20
1. 0.00
40.49 0.00
J0.42 1: 0.08
J0.19 1 0.10
40.54
0.12
PB(10)
0.221
-13.18+000
0.28
29.14
0.19
1..45+
29.55
29.05
0.21
29.63
PE(15)
31.17 0:337
31.17
0.37
11.03
5: 0.26
11.49
11.63
0.15
10.97
0.29
11.57 0.13
PEr20)
44.112
-49.12
0.24
-6.78 0.114
16.411.:000
-6,52 0.110
-7.03
0.21
-6.37
0.24
PR(25)
54.59
0.02
54.50
0.01
12.51
0.05
12.28
0.0.4
12.42
0.03
12.58
12.18
Expl
54.66 1: 0.06
34.90 1 0.10
13:21
0.29
13:24 1 0.33
13.77 1. 0.40
41.132 1: 1.06
13:26 0.24
5:05
0:0.7
0.03
0.03
1:25
Avg Doal Difeennc
0.50
0.25
0.00
Figure 3: The average goal difference between all the methods and the built-in bots with various difficulty levels 0 (0 E [o, 1] and larger 0 means harder bot) on Google Research Football.
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 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- 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 certain policy or PE of 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 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 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 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.
Conclusions
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-pronet 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 A and X2 in our paper are manually tuned. Our methods target the non-transitivity in zero-sum games. Therefore, the weights for 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 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- ta-ttaanitiivtt of the environment [4]. To be specific, if there aren't 't too many cyclic policies involved in the environment (such as Rock>>Paper->Scissonn the newest model generated by the naive self- 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-pay peyaa-a Regarding the limitations from the perspective of real-world application, the game dynamics could be complex and there could be 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.
Acknowledgments
This work is supported by Shanghai Sailing Program (2IYF1421900), The authors thank Minghuan Liu for many helpful discussions and suggestions.
References
[1] Tucker Balch, Behavioral diversity in learning robot teams. Technical report, Georgia Institute of Technology, 1998.
[2] David Balduzzi, Marta Garnelo, Yoram Bachrach, Wojciech Czarnecki, Julien Perolat, Max Jaderberg, and Thore Graepel. Open-ended learning in symmetric zero-sum games. In Interna- tional Conference on Machine Learning, pages 434-443. PMLR, 2019.
[3] Kiante Brantley, Wen Sun, and Mikael Henaff. Disagreementtreguulaiize imitation learning. In International Conference Learning Representations, 2019.
[4] Wojeiech Marian Czarnecki, Gauthier Gidel, Brendan Tracey, Karl Tuyls, Shayegan Omidshafiei, David Balduzzi, and Max Jaderberg. Real world games look like spinning tops. arXiv preprint arXiv:2004.00 09468, 2020.
[5] Le Cong Dinh, Yaodong Yang, Zheng Tian, Nicolas Perez Nieves, Oliver Slumbers, David Henry Mguni, Haitham Bou Ammar, and Jun Wang. Online double oracle. arXiv preprint arXiv:2103.0771 2021.
[6] Mohamed Elfeki, Camille Couprie. Morgane Riviere, and Mohamed Elhoseiny. Gdpp: Learning diverse generations using determinantal point processes. In International Conference on Machine Learning, pages 1774-1783. PMLR, 2019.
[7] Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without a reward function. arXiv preprint arXiv:1802.00000 1802006070 2018.
[8] Norm Ferns, Prakash Panangaden, and Doina Precup. Bisimulation metrics for continuous markov decision processes. SIAM Journal on Computing, 166-111111 2011.
[9] Justin Fu, Katie Luo, and Sergey Levine. Learning robust rewards with adversarial inverse reinforcement learning, arXiv preprint arXiv:1710.11248. 2017.
10

---

[10] Marta Garnelo, Wojciech Marian Czarnekki, Siqi Liu, Dhruva Tirumala, Junbyuk Oh, Gau- thier Gidel, Hado van Hasselt, and David Balduzzi. Pick your battles: Interaction graphs as population-level objectives for strategic diversity. In Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, pages 1501-1503, 2021.
[11] Seyed Kamyar Seyed Ghasemipour, Richard Zemel, and Shixiang Gu. A divergence mini- mization perspective imitation learning methods. In Conference Robot Learning, pages 1259-1277. PMLR, 2020.
[12] Daniel Hernandez, Kevin Denamganai, Yuan Gao, Peter York, Sam Devlin, Spyridon Samoth- rakis, and James Alfred Walker. A generalized framework for self-play training. In 2019 IEEE Conference on Games (CoG), pages 1-8. IEEE, 2019.
[13] Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. arXiv preprint arXiv:1606.03476 2016.
[14] Alex Kulesza and Ben Taskar. Determinantal point processes for machine learning. arXiv preprint
2012.
[15] Karol Kurach, Anton Raichuk, Piotr Staúczyk, Michal Zając, Olivier Bachem, Lasse Espeholt, Carlos Riquelme, Damien Vincent, Marcin Michalski, Olivier Bousquet, et al. Google research football: A novel reinforcement learning environment. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 4501-4510, 2020.
[16] Mare Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. A unified theeetteerettc approach to multiagent reinforcement learning. arXiv preprint 17Iivv/711.00
2017.
[17] P. Langley. Crafting papers on machine learning. In Pat Langley, editor, Proceedings of the 17th International Conference on Machine Learning (ICML 2000), pages 1207-1216, Stanford, CA, 2000. Morgan Kaufmann.
[18] Michael L Littman. Markov games as framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pages 157-163. Elsevier, 1994.
[19] Minghuan Liu, Tairan He, Minkai Xu, and Weinan Zhang. Energy-based imitation learning. arXiv preprint Stt1:20044.03955, 2020.
[20] Muhammad Masood and Finale Doshi Velez. Diversity-inducing policy gradient: Using
maximum mean discrepancy to find set of diverse policies. arXiv preprint 2019.
[21] Stephen McAleer, John Lanier, Roy Fox, and Pierre Baldi. Pipeline psro: scalable approach for finding approximate nash equilibria in large games. arXiv preprint arXiv:2006.088: 085555 2020.
[22] Kevin R McKee, Joel Z. Leibo, Charlie Beattie, and Richard Everett. Quantifying envi- ronment and population diversity in multi-agent reinforeement learning. arXiv preprint arXiv:2102.08370, 2021.
[23] Brendan McMahan, Geoffrey Gordon, and Avrim Blum. Planning in the presence of cost functions controlled by an adversary. In Proceedings of the 20th International Conference Machine Learning (ICML-03), pages 536-543, 2003.
[24] Nicolas Perez Nieves, Yaodong Yang, Oliver Slumbers, David Henry Mguni, and Jun Wang. Modelling behavioural diversity for learning in open-ended games. arXiv preprint arXiv:2103.07927, 2021.
[25] OpenAl. Openai five. https://bboot https://bloo.oppmai..oo wtt..////oppiiiiiiveeee 2018.
[26] Aldo Pacchiano, Jack Parker-Holder, Krzysztof Marcin Choromanski, and Stephen Roberts. Effective diversity in population- based reinforcement learning. 2020.
[27] Jack Parker-Holder, Aldo Pacchiano, Krzysztof Choromanski, and Stephen Roberts. Effective diversity in population-bas based reinforcement learning, arXiv preprint 2721022002.00632, 2020.
11

---

[28] Peng Peng, Ying Wen, Quan Yuan, Yaodong Yang, Zhenkun Tang, Haitao Long, and Jun Wang. Multiagent bidhrectionally-conn coordaatte nets for learning to play starcraft combat games. arXiv preprini arXiv: /703. 10069, 2:2, 2017.
[29] Umar Syed, Michael Bowling, and Robert E Schapire. Apprenticeship learning using linear programming. In Proceedings of the 25th international conference on Machine learning, pages 1032-1039, 2008.
[30] Oriol Vinyals, Igor Babuschkin, Wojeiech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Jun- young Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft using multi-agent reinforcement learning. Nature, 575(7782)33003344 2019.
[31] Ruohan Wang, Carlo Ciliberto, Pierluigi Vito Amadori, and Yiannis Demiris. Random expert distillation: Imitation learning via expert policy support estimation. In International Conference on Machine Learning, pages 6536 6544. PMLR, 2019.
[32] Zhe Wu, Kai Li, Enmin Zhao, Hang Xu, Meng Zhang, Haobo Fu, Bo An, and Junliang Xing. L2e: Learning to exploit your opponent. arXiv preprint arXiv:2102.09388 2021.
[33] Pengtao Xie, Jun Zhu, and Eric Xing. Diversity-rromotin bayesian learning of latent variable models. In International Conference on Machine Learning, pages 59-68. PMLR, 2016.
[34] Huan Xu and Shie Mannor. Robustness and generalization. Machine learning, 86(3):391-423, 2012.
[35] Zhongwen Xu, Hado van Hasselt, and David Silver. Meta-gradien reinforcement learning. arXiv preprint arXiv: 1805.0901, 2018.
[36] Yaodong Yang, Jun Luo, Ying Wen, Oliver Slumbers, Daniel Graves, Haitham Bou Ammar, Jun Wang, and Matthew Taylor. Diverse auto-curriculum is critical for successful real- world multiagent learning systems. In Proceedings of the 20th International Conference Autonomous Agents and MultiAgent Systems, AAMAS '21, page 51-56, Richland, SC, 2021. International Foundation for Autonomous Agents and Multiagent Systems.
[37] Yaodong Yang and Jun Wang. An overview of multi-agent reinforcement learning from game theoretical perspective. arXiv preprint arXiv:20I 1.00583, 2020.
[38] Yaodong Yang, Ying Wen, Jun Wang, Liheng Chen, Kun Shao, David Mguni, and Weinan Zhang. Multi-agent determinantal q-lcarning. International Conference Machine Learning. pages 10757-10766. PMLR, 2020.
[39] Deheng Ye, Guibin Chen, Wen Zhang, Sheng Chen, Bo Yuan, Bo Liu, Jia Chen, Zhao Liu, Fuhao Qiu, Hongsheng Yu, et al. Towards playing full moba games with deep reinforcement learning. arXiv preprint 2rXiv:2011.12699) 2020.
[40] Tom Zahavy, Andre Barreto, Daniel J Mankowitz, Shaobo Hou, Brendan O' O'Donoguue, Iurii Kemaev, and Satinder Baveja Singh. Discovering a set of policies for the worst case reward. 2021. 2021.
arXiv preprint 1024:3200..04333,
12


Reviews:
[{"review_id": "fgK0fI-R-0k", "reviewer": "Reviewer_Rpgw", "summary": "This work proposes a novel framework for measuring diversity in (open-ended) multi-agent learning. Using this framework, they formulate objectives to encourage diversity at the policy and policy population level, achieving low exploitability, high population effectivity, and overall good performance in simple as well as relatively complex MARL problems.", "questions": "", "limitations": "", "rating": 8, "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": "This is great work!\n\n### Clarity\n\nThe paper reads beautifully. I wasn't very familiar with the open-ended learning take on MARL, but the manuscript provided both a good and clear introduction to the topic as well as a very clean (and seemingly novel!) view on the problem. I thoroughly enjoyed going through it.\n\n### Originality & Significance\n \nI'm not extremely familiar with most on the existing literature on estimating diversity in MARL settings, but the overall proposed analysis framework as well as the obtained losses seem novel and well sound. *At the very least* the manuscript seems significant in bringing a fresh perspective on a few recent methods for population-driven MARL that have helped with generating very successful RL stories.\n\n### Questions\n\nL154:158: How does this actually differ form RED (or RND even) in practice? Furthermore, once the network is learnt on the dataset, does it remain fixed throughout the duration of the experiment, or does it get periodically re-learnt?\n\nL169:170: Shouldn't $-i$ be assignable to a single opponent player? What value does it take in say a game with 3 or 4 players?\n\n### Typos\n\nL45: \"like, in Maze\" -- looks like a bad copy-paste.\n\nL169: s/for an example/for example/", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Strictly speaking, I don't think the manuscript provides a good overview of the limitations of the proposed framework, nor of any particular weakness in the experimental setting used.\n\nAnalysis on societal impact is also very limited (if not non-existent).\n\nI would personally enjoy a discussion at the very least on what other types of losses could be potentially steam from utilising the BD / RD decompositions.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "doTkzcCvYuT", "reviewer": "Reviewer_QZCS", "summary": "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.\n\n_______\n\nScore 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. ", "questions": "", "limitations": "", "rating": 7, "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": "Strengths\n\n* The paper addresses an interesting problem, clearly motivated by non-transitive games which have been in focus with agents such as AlphaStar.\n\n* The paper is thorough and rigorous in its definitions, which is clear to follow given sufficient time. The authors introduce their own notation to think about several well known methods and once the reader gets up to speed with this the rest of the paper is clear and interesting.\n\n* The empirical results are clear and seem convincing, with the new approach clearly outperforming a strong set of baselines.\n\n* The definitions of BD and RD make sense to me. This is an intuitive way to think about diversity metrics. \n\n* The hyperparameter ablations are a great addition, compared to many works which do not show this level of granularity. \n\nQuestions & Areas for Improvement:\n\n1. The paper fails to deliver on its core promise, to quote the abstract: \"work towards offering a unified measure of diversity\". Indeed, after categorizing diversity metrics into two classes, I expected to see some analysis explaining when they differ and when they are equivalent. I then expected to see a new metric or objective that provides many or all of the desirable properties of both classes of methods. Instead, the final outcome is rather unsatisfactory - the authors simply add both to the objective. In a sense, this is not unified, this is just adding two (very much distinct) pieces together. I think there are two ways to improve here. The first is to discover the novel diversity objective that truly unifies the methods. However, this is of course very hard. The second, would be to change the title to something like \"Towards Unifying... \" or \"Demystifying...\" because those are more appropriate for the contribution of the paper, which in a sense, lays the ground work for the new objective to be discovered. In this second case, I would still hope to see some analysis, either empirical or theoretical, of when these objective succeed and fail. \n\n2. Can you possibly explain the behavior in Figure 2? It seems that DPP-PSRO which uses Response Diversity, has a very similar profile to P-PSRO with Behavioral Diversity, and looks very different to P-PSRO with Response Diversity. Is DPP-PSRO classified correctly in Table 1?\n\n3. In some cases the authors make things a little convoluted, and could explain the theorems in words, as they are often very straightforward observations (e.g. Theorem 1). \n\n4. The population effectivity metric looks like a robustness objective, but this is not mentioned. For example [1] focuses on minimax objectives w.r.t reward and of course this is very related, it is just about generalizing with a different degree of freedom. There is nothing wrong with PE not being 100% novel, it just should be more clearly compared to existing works.  \n\n5. Limitations of the method do not seem to be thoroughly discussed anywhere. The checklist says yes, but I couldn't find it. \n\nMinor Comments/Typos:\n\n-l.24: \"Zero-sums\" -> \"zero-sum\"\n\n-l.83: \"is a principle way\" -> \"is a principled way\"\n\n-l.119: \"bisimulation metric\" -> \"bisimulation metrics\"\n\n-l.121: \"build the metric\" -> \"build a metric\"\n\n-l.130: \"state-action pair\" -> \"state-action pairs\"\n\n-l.166: \"energy-based model\" -> \"energy-based models\"\n\n-l.320: \"showed the most\" -> \"showed that most\"\n\nReferences\n\n[1] Zahavy et al. Discovering a set of policies for the worst case reward. ICLR 2021", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I could not find a detailed discussion of limitations.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "GGvMC6UaAI8", "reviewer": "Reviewer_qQqw", "summary": "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.\n", "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": "Positives:\n* Overall the paper is well structured and not too hard to follow. \n* The two main contributions (the augmented training objective and the effectivity metric) are interesting and novel in this setup as far as I can tell.\n* The experiments include relevant baselines and span a good range from synthetic to more real-world. Most of the results look promising.\n\nConcerns:\n* There are parts that lack more detail. For example, the setup of the AlphaStar game is not clear to me at all. From what I understand the authors have not trained AlphaStar from scratch but rather are using payoff matrices from pre-trained agents? This needs to be more clear in order to be able to judge the impact of the results. Another example of this is the matrix for the non-transitive mixture game should be described a bit more in the main text, to at least get an intuition about it’s structure beyond having been “delicately designed”.\n* I am not sure about the results on the non-transitive mixture game. I am surprised by the performance of PSRO and in particular PSRO-rN which is aimed at finding diverse strategies. I might be misunderstanding the game (and, if so, this adds to my previous point about this intuition having to be communicated better to the reader), but would the modes of the Gaussians not be where we would want the trajectories to end? If this is the case why are none of the algorithms reaching them? I am also surprised there is no cycling in the trajectories, given the cyclic nature of the game.\n* A lot of the paper is in the appendix. I am aware that there is a lot to include and there is a page limit, but I would make an effort to exclude anything that is less relevant from the main text and try to bring at least intuitions about what is specified in the appendix rather than just referring to it.\n\nSuggestions:\n* The first sentence of the paper “zero-sum games involve non-transitivity” is not correct. A zero-sum game with two strategies for example is not non-transitive. You can also take any transitive game P and P-P.T will still be transitive as well as zero-sum. I am assuming that the authors might not have meant it as a universal statement, in which case they should be careful when making general statements like this and this particular sentence should be changed (if indeed they did mean it as a universal statement, this could be a concerning indication of lack of fundamental knowledge about game theory).\n* Related research that might be of interest in this area is a paper on diversity of populations [1].\n* Some variables are not defined, like c and W in line 120. Even if this is notation that is defined in another paper, if the authors use an equation all variables should be explained.\n* In algorithm 1 the star of theta in line 5 and in line 7 is not the same, use the same one as they refer to the same thing and otherwise this could be misinterpreted.\n* In lines 200 and 208 write out ‘Behavioural diversity’ and ‘Response diversity’ (you can leave out the ‘Discussions on’ part).\n* There are several spelling and grammatical errors throughout the paper, I would recommend giving it a thorough scan. Here are some examples: l.24 it’s zero-sum, not zero-sums, l.133 if \\rho is *a* valid, l. 214 for practical implementation, l.269 ‘condict *an* ablation study. \n\n[1] Garnelo, Marta, et al. \"Pick Your Battles: Interaction Graphs as Population-Level Objectives for Strategic Diversity.\" Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems. 2021.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The Authors discussed this appropriately.", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical concerns about this work from my side.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours."}, "extra_text": {}}, {"review_id": "8nDnnVeXS5q", "reviewer": "Reviewer_1idw", "summary": "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. \n\nThis 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.\n\nThe additional diversity objectives are shown to improve training in several different domains.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "**Originality**: to the best of my knowledge, there is a good amount of novel work in this paper, and an adequate discussion of related work.\n\n**Technical quality**: The technical quality of the paper looks solid to me. I will note here that the most theoretical / math-heavy parts, like the proofs, seem beyond my ability and I would probably not easily spot any mistakes in them if there were any. I do feel that I was able to follow along well with the majority of the paper, at the very least on an intuitive level, and from that point of view I do not see many major issues. I only have the following two remarks:\n\n1) Many parts of the paper refer to **unifying** measures of diversity, or providing a **unified** diversity measure: the title of the paper, the abstract, the introduction, Section 4, the conclusion, etc. Maybe I'm mistaken or forgetting about something here, but my understanding of the word \"unifying\" seems to be different from what's going on in this paper. When I see \"unifying\", I think of something more *general* (an algorithm, a model, a theory, etc.) that encapsulates multiple other more specific things (which were often previously viewed as being distinct things) as special cases. For example, I would think of TD(lambda) as an algorithm that unifies several other simple reinforcement learning algorithms, such as Monte-Carlo returns (special case with lambda=1) and one-step returns (special case with lambda=0). I do not see the behavioral and response diversity measures being unified in this paper, since they are essentially still two completely distinct objectives that can simply be added together (as in Equation 8).\n\n2) In tables of results, such as Table 2, when some results are presented in boldface this is often interpreted as those results being the best of their row with statistical significance. But in Table 2, it appears that all the best results of every row are presented in boldface, even if their confidence intervals (or are they standard errors?) are overlapping. For example, in the first row, the 40.49 +- 0.07 interval for DPP-PRSO overlaps with the 40.54 +- 0.12 interval for P-PRSO w. BD&RD, but only the latter is in boldface. In these cases, either no result should be in boldface, or all the results for which the intervals overlap with that of the best should be in boldface.\n\n**Clarity**: the paper is clear, well-written, easy to follow. I will just list a few small typos / points of confusion I found:\n\n- Line 24: Zero-sums --> Zero-sum\n- Line 45: why is Maze capitalised? Is this just about any arbitrary maze, or a specific environment named \"Maze\"?\n- Line 255: \"and B_i subset of Q_i\" --> the Q symbol used here looks different from all the other Qs, is that intentional?\n- Page numbers of reference [10] should be 586--593 instead of 1--8\n- First point of the Checklist says \"See Section ??\"\n\n**Significance**: I am not sure if many of the results for the matrix games in Table 2 can be considered significant, but the Google Research Football results in Figure 3 look more convincing. The theoretical insights in terms of diversity measures and Population Effectivity evaluation metric also look promising.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are adequately addressed (for example when approximations to optimisation are necessary).", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper explores different methods for measuring population diversity and how they can be applied in open-ended learning. All reviewers agreed that it provides a valuable contribution. One important point that emerged from the discussion with reviewer QZCS was that the paper's title is a bit of an overclaim. The authors graciously agreed to qualify it by changing to "Towards unifying...".
Decision: Accept (Poster)