A Unified Diversity Measure for Multiagent Reinforcement Learning
Authors: Zongkai Liu
Chao Yu
Yaodong Yang
peng sun
Zifan Wu
Yuan Li
Venue: NeurIPS 2022 Accept (2022)

Abstract: Promoting behavioural diversity is of critical importance in multi-agent reinforcement learning, since it helps the agent population maintain robust performance when encountering unfamiliar opponents at test time, or,  when the game is highly non-transitive in the strategy space (e.g., Rock-Paper-Scissor). While a myriad of diversity metrics have been proposed, there are no widely accepted or unified  definitions in the literature, making the consequent diversity-aware learning algorithms difficult to evaluate and the insights elusive. In this work, we propose a novel  metric called the Unified Diversity Measure (UDM) that offers a unified view for existing diversity metrics. Based on UDM, we design the UDM-Fictitious Play (UDM-FP) and UDM-Policy Space Response Oracle (UDM-PSRO) algorithms as efficient solvers for  normal-form games and open-ended games. In theory, we prove that UDM-based methods can enlarge the gamescape by increasing the response capacity of the strategy pool, and have convergence guarantee to two-player Nash equilibrium. We validate our  algorithms on games that show strong non-transitivity, and empirical results show that our algorithms achieve better performances than strong PSRO baselines in terms of the exploitability and population effectivity. 

A Unified Diversity Measure for Multiagent Reinforcement Learning
Zongkai Liu
Chao Yu'
School of Computer Science and Engineering Sun Yat-sen University, Guangzhou, China liuzk@mail2. sysu. edu.
School of Computer Science and Engineering Sun Yat-sen University, Guangzhou, China yuchao38mail. sysu. edu. cn
Yaodong Yang
Peng Sun
Institute for AI, Peking University Beijing Institute for General AI, Beijing yaodong yang@pku.n.p edu. cn
ByteDance, Shenzhen, China pengsun000@gmail.ccom
Zifan Wu
School of Computer Science and Engineering Sun Yat-sen University, Guangzhou, China wuzf50mai12. sysu. edu. cn
Abstract
Promoting behavioural diversity is of critical importance in multi- reinforce- ment learning, since it helps the agent population maintain robust performance when encountering unfamiliar opponents at test time, or, when the game is highly non-transitive in the strategy space (e.g., Rock-PPapr-Seeissor). While myriad of diversity metrics have been proposed, there are no widely accepted or unified definitions in the literature, making the consequent diversity-aware learning al- gorithms difficult to evaluate and the insights elusive. In this work, we propose novel metric called the Unified Diversity Measure (UDM) that offers a unified view for existing diversity metrics. Based on UDM, we design the Play (UDM-FP) and UDM-Policy Space Response Oracle (UDM-PSRO) algo- rithms as efficient solvers for normal-form games and open-ended games. In the- ory, we prove that UDM-based methods can enlarge the gamescape by increasing the response capacity of the strategy pool, and have convergence guarantee to two-player Nash equilibrium. We validate our algorithms on games that show strong non-transitivity, and empirical results show that our algorithms achieve bet- ter performances than strong PSRO baselines terms the exploitability and population effectiviiy.
Introduction
Diversity is a widely studied topic in machine learning, including autonomous driving [52], gam- ing AI [46], recommender systems [6], generative models [13], and latent variable models [51]. Specially, in Multi-Agent Reinforcement Learning (MARL) [4, 20, 55, 50), diversity of agents' strategies helpful for learning different skills [14], facilitating explorations [42], and discovering
sophisticated cooperative policies [27] or an automated agenda towards unexploitable policies in
"Coreesponiing authors.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

competitive games [15, 29]. Promoting diversity of strategies is also an effective method for solv- ing games with non-transitive dynamics [1, 40, 12, 46]. In general, an arbitrary game, of either the normal-form type [5] or the differential type [2], can always be decomposed into sum of transitive part and a non-transitive part, where the former represents a transitive rule (i.e., if A beats B, B beats C, then A beats C), while the latter represents cyclic rule (i.e., the cycles among Rock, Paper and Scissors). In fact, many real-world games demonstrate strong non-transitivity [8], and thus each player must use diverse pool of winning strategies to achieve low exploitability [53], which has been justified recently by the super-human performance of AIs in sophisticated tasks like StarCraft [47, 43] and DOTA2 [3, 57].
In specific, encouraging the diversity of strategies is critical in achieving high-level learning per- formance due to the following two main aspects: (1) in the training process, diversity prevents agents from checking the same strategies repeatedly [40], and helps them explore strategy space sufficiently [42]; and (2) at test time, diversity not only prevents agents from being exploited (i.e., a single strategy can always be beaten by another one on non-transitive games [40, 30]), but also helps them learn adaptable strategies and thus maintain robust performances [49, 30].
Due to its great importance, there are a number of studies that investigate the definition of diver- sity and propose diversity-driven MARL algorithms. The majority of work has followed a heuristic approach [40], such as evolutionary computation [16] with a central focus that mimics the natu- ral evolution process. In evolutionary computation, one idea for encouraging diversity is novelty search [24] that searches for strategies leading to novel outcomes. Quality-diversity (QD) [44] com- bines novelty search with fitness objective, resulting two representative methods: Novelty Search with Local Competition [25] and MAP-Elites [7, 37J. Although these methods achieve empirical successes [21, 7]. quantifying diversity in evolutionary computation is often hand-crafted and task- dependent [40]. There are also various metrics proposed to model diversity in a more rigorous way, which can be mainly classified into Behavioral Diversity (BD) and Response Diversity (RD) [30]. main principle BD to characterize diversity is to construct metrics over the trajectory or state- action distribution [28, 14, 27, 42). However, this kind of methods only focus on the behavioral trajectories and ignore the reward attributes of strategies, which may be problematic in scenarios when a slight difference in strategy behaviors will lead to huge difference in the corresponding reward [30]. Different from BD, RD directly uses the empirical payoff matrix to construct the diver- sity of strategies [1, 40, 30), and thus it estimates the diversity from the response when encountering distinct opponents.
Despite of the above great efforts, there are still no consistent formal definitions for diversity, mak- ing it difficult to evaluate the diverse strategies in MARL. In this paper, we work towards offering a consistent definition for diversity, and propose novel population-wide diversity measure called the
Unified Diversity Measure (UDM) that provides a unified view for the existing metrics, including Effective Diversity (ED) [1], Population Diversity (PD) [42] and Expected Cardinality (EC) [40]. UDM can be interpreted from a geometric perspective through analyzing the meanings of the eigen- values of a kernel matrix. Using UDM, we can also analyze the ad advantages and shortcomings of the existing metrics, and study why ED and PD cannot measure the diversity properly in certain cases. With task-agnostic metric, we design the corresponding diversity-promotiee and develop novel MARL algorithms, i.e., UDM Fictitious Play (UDM-FP) and UDM Policy-Space Response Oracle (UDM-PSRO), for solving normal-form games and open-ended games. Theoreti- cally, we prove that our algorithms can enlarge the gamescape [1], i.e., the convex hull of the row vectors in the payoff matrix, by increasing the response capacity of the strategy pool, and can con- verge on two-player games. We validate our diversity-aware algorithms on games that show strong non transittiii including the the empirical results show that our algorithms achieve lower exploitability [23] and higher popula- tion effectivity [30] than the baselines.
objective
matrix games, Blotto and non- non-transitive mixture model, and
2 Preliminary
2.1 Concepts of Games
Normal-Form Games and Open-Ended Meta-Games. Normal-form games (NFGs) are de-
noted by (N.S. S. G),, where N is the number of players. Each player n E [N] has a finite set of pure strategies S". Denote the space of joint pure-strategy profiles S II S", and the space
2

---

of joint strategy profiles except the n-th player as S payoff table mapping each joint strategy profile S to a vector of reward values for each player. mixed strategy (also called policy) of player is denoted by T" E Ag", where A is a probability sim- plex. π (S) = [N ा (S) represents the probability of joint strategy profile S. all players fol- low π, the expected payoff of player n is denoted as G* = G( , ")= = Eses GS))
G(S) (S),
G)) ER as
However, it is inefficient describe real-world games with NFGs, where the strategy space can be prohibitively large by enumerating all possible game plans [8]. For example, the number of atomic actions in StarCraft is 1026 at every time-step and the number of time-steps per episode is typically several thousands [47], in which case the number of game plans can be more than (1026)1000, To describe this type of games, meta-games denoted by (N, M) are introduced to consider a policy as a "high-level" strategy, i.e., the meta-strategy. With slight abuse of notation, the space of meta-strategies is still denoted by S" for each player n;; and thus T" Ag- denotes the meta-policy of player n. Additionally, meta-games are always open-ended since there could be infinite meta-strategies
play game. A meta-game payoff M can be described by game engine g S + IR. For example, in two-player games, the meta-game payoff can be described as M = (g( 52) ): (S), 5²) E S! x $2); where (SS",5% ) >
if St E S beats S² E 8?, while g < and = refer to losses and ties, respectively. A game is symmetric if S = S², A game is transitive if there exists monotonic rating function h such that g(St
h(S²) - h(S"), VS E st ,5 E 82; and non-transitive if fga g(S), S²) 0, VSa E S1, which means that each strategy can be counterbalanced by another strategy.
Solution Concepts of Games. In a game, a (possibly mixed) strategy H" is a best re- sponse for player against joint strategy π- if лr" E BR" (r)",, where BR" (Ir ") arg maxaa Agn (G" π "].. A Nash Equilibrium (NE) [39] is a joint strategy π π E BR"(T Vn. An e-NE is a joint strategy π if T E BRT ")) Vn, where BR = {x" GD π ") > G"
(R"( Computing NE is PPAD-hard in N- player general-sum games [9]; and thus a-Rank [41] is proposed as an alternative solution concept, which has polynomial-time solvability multi-player general-sum games. A more detailed de- scription of a-Rank can be found in Appendix A.I.
-)
Game Solvers. A game solver consists of an Oracle function and a (meta- jpolicy solver, where the Oracle function O computes strategies given joint strategies, such as the best-response Oracle O²( BR"(n (nt -"), and the (meta-)policy solver S computes the (meta) payoff table. At each time step, the game solver uses the policy solver to compute policy for each player based on the current payoff; and then based on this joint policy, it uses O()) to find new strategy for each player and adds it in their populations. Variations of (meta-)game solvers are summarised in Table
based on the
Table I: Various (Meta-)Game Solvers
Method
(Meta-)Policyy Solver S
O
Self [17]
[0, --- O, 1,
BR(-)
GWFP [26]
UNIFORM
BR.
1301
NE
BR(-)
PSROx [23]
NE NE
BR, (-)
PSRO,x
ED-BR())
a-PSRO [38]
c--Rank NE/ a-Rank
PBR( (-)
EC-PSRO [40]
EC-BR(-) / EC-PBR()) Ex) (q)(9)
Our Methods
NE/ a Rank
2.2 Evaluation Metrics
Empirical Gamescape. The empirical gamescape (EGS) [1] in meta-game is defined as the convex hull of the payoff vectors of all meta-strategies in S", written as EGS(S") := (E,a, m; a 2 0, a. m. = MRa1.. which represents the response capacity of a pool of strategies in meta-gam meta-games.
Exploitability.
The exploitability [10] measures the "distance" of a joint strategy π to the NE, defined as Exploit ;= E'e[M)] ( ( ( n -")) - GDh G² ()] म E BR"(m (T)
3

---

The population effectivity (PE) [30] is fairer evaluation metric to represent the effectiveness of a population (i.e., strategy pool) than exploitability: PE(S")
Population Effectivity.
8"1 ming-n aax,,a= 20 k= a% G GSK ")).
2.3 Existing Diversity Measures
There are various diversity metrics to measure the diversity of population.
Effective Diversity, Effective Diversity (ED) [1] is a metric proposed to measure the diversity of pool of effective-strategies (strategies with support under the NE) in two-player zero-sum symmetric games as follows:
ED(S") n [M]+ T
(1)
where |a]++ = if > and | = = M is the meta-payoff table of S and x " the NE of the M.
Expected Cardinality. Inspired by the derterminantal point process (DPP) [31. 22], the diver- sity population can be increased through increasing the Expected Cardinality (EC) [40] of the random set Y C 8 drawn from the population:
EC(S") == Ex-Pen en [Y]] Tr(I - (C" + +)=
(2)
where Y| means the cardinality of Y, and L MM..
Form of Euclidean Projection. To characterize the contribution of payoff vector the en- largement of the EGS directly, Form of Euclidean Projection (FEP) [30] is defined as the form of Euclidean projection:
FEP(S
min 1T8=1,820
IIM B- Onew 112.
(3)
where S is the new meta-strategy of player n. and a == (S new ")),), Note that FEP only measures the contribution of the new meta-strategy the current population, rather than the diversity of the population.
Population Diversity, sity by:
Population Diversity (PD) [42] uses the determinant to measure the diver-
PD(S") = det(K"),
where K" = K ))), and of = (-Ts) (s means the state in games) is the behavioral embedding of meta-strategy Here rename PD as Reward-PD (RPD) when it replaces the behavioral embedding with d² = -M...
3 Methods
Based on the existing metrics, we now offer a unified view for them by introducing a novel diversity measure. Specially, this measure based on a geometric interpretation of the diversity of strategies, and is capable of offering comprehensive analysis of these existing diversity metrics.
3.1 A Unified Diversity Measure
There are various methods to represent a strategy in the existing studies. In RD. fundamental way to represent a strategy is through the row vector of the empirical payoff matrix [40. 30], since each row in this matrix embeds the response of the corresponding strategy against different opponents; and BD, the trajectory or the action-state distribution is often used characterize the corresponding strategy [42, 30). To represent strategy more flexibly, we introduce the strategy feature:
Definition (Strategy Feature), Let St E S denote the i-th (meta- jeeeta--struegy for player then the strategy feature of Sth defined as vector Φ6 E 1RIxp xPp p S M =: [S"), such that dº Φ3 ) ST Sy, where VS. SS) S".

---

Hence, we can represent the i-th strategy by o = m; =: Ma. in RD, or OF = (+](+s)) in BD. Equipped with the strategy feature, we can then define the diversity kernel to measure the pairwise similarity as follows:
Definition 2 (Diversity Kernel). Consider a finite population S" consisting of M (meta- sstrateess The diversity kernel of player n is defined as a positive semi-definite (PSD) matrix: L == [K (Ø, 3 MMMMMMM M, where K : Baxx xRd I. is given kernel function,, such that |K (Ø): (;)
and K( o Φ.) C.>00
Given a PSD matrix -= BB", where B E DDxx and D1 2 D2. The geometric interpretation of (c)(() is the squared volume of the parallelepiped spanned by the rows of B [22]. Further more, the determinant of diversity kernel represents the squared volume of parallelepiped spanned by strategy feature corresponding to the kernel choice [42]. Thus, a population can be considered diverse its parallelepiped can fill the strategy space as much as possible. A natural idea to measure the diversity of population is to use the determinant of the diversity kernel, which is the intuition of PD (RPD) introduced in section 2.3. However, since the determinant becomes zero with du- plicated rows, PD (RPD) cannot deal with the redundant-ssrateee problem which turns out to be critical challenge for game evaluation [1] (See more discussions in Appendix A.2.). To avoid this problem, the additive term over cigenvalues rather than the product of eigenvalues (i.c., the determinant) to mcasure the diversity and propose the Unified Diversity Measure as follows:
Definition (Unified Diversity Measure). Consider a functio
f fEF: F = { =
- - , 0, K=U
where R is the convergence domain of f.
Denote the eigenvalues of L.k constructed by S" (ST...., ,SM) as >; 2 O. Then the Unified Diversity Measure (UDM) of the population S
defined as follows:
UDM(S") Σ f(x)).
(5)
Since the values and the number of the non-zero eigenvalues represent the lengths and the number of the edges of the parallelepiped, respectively, increasing UDM can help enlarge the volume of the parallelepiped, which indicates a more diverse strategy population. Otherwise, considering only the number of non-zero eigenvalues (i.e., the rank of the diversity kernel) will result in the difference instead of the diversity being measured [40, 56). For example, in RPS, the meta-strategy [0.99 Rock, 0,01 Paper] is different from [0.98 Rock, 0.02 Paper], but they are not diverse since they both favor playing Rock.
Meanwhile, we offer an equivalent representation of UDM which can be computed more easily:
Proposition 1 (Equivalent Representation of UDM). The UDM defined in Definition 3 has an equiv- alent representation:
M
UDM(S") =
(6)
where the definition of [(Ck) is similar to the matrix exponentials.
Proof. See Appendix A.3.I.
Using s(As) rather than X; directly is vital for UDM. In the case where f(Ax) = A.. UDM will degenerate to Tr(L") = Σ; CR where CB = K( Φhh only captures the modulus of ST and thus C3 ignores the similarity L2 between ST and Sy. ; # j. making it unable to measure the diversity properly. Instead, using bounded concave functions f(x: that involve the pairwise similarity, such as f(x,) Txp) 1 0 (the term T is applied to satisfy f(0) = 0),
can force the player explore more novel strategies since this function with supremum gains more marginal benefit from adding a new non-zero eigenvalue rather than increasing an already large eigenvalue. Given the convexity of (xx) UDM becomes concave due to the following proposition:
5

---

Proposition 2 (Convexity of UDM), Consider concave function f E F. Then UDM is concave if all the eigenvalues of C exist in the convergence domain of f.
Proof. See Appendix A.3.2.
3.2 Unify Existing Metries into UDM
By mathematically transformations, argue that some existing diversity metries, especially the RD metrics, are the special cases of UDM, which are summarized Table
Table 2: Unify Existing Metries into UDM
Methods
Korel Function K(--)
Function f Lincar Kemee
Strategy Feature d:
ED [I]
f(x)
PD |422
sell-selected
f(x) = la
{m{+ls))>
RPD
self selected
[(x) In
BC [40]
Linear Kerne
f(a) If
m,
UDM vs. ED. Formally, ED is equivalent the I1,1 norm of the payoff matrix in two-player symmetric zero-sum games [1]:
ED(S") x [.M 1 LMMe x 111,,
where " is the NE on M, @ the Hadamard product (i.e., element-wise product), and || Eggle latyl- Denote M = x M TT then:
max ED max
II = max
2 प.
Σ
Mi
max D1T
T Mr 1= max M
max
X
where X; are the eigenvalues of M Hence, ED can be covered by UDM with -(:-)= and f(x) æ. Using the strategy feature Φ; = m =: MMi. and function f(z) = x in ED encourages the player to amplify its strengths and ignore its weaknesses in finding a new meta- strategy, by focusing only on the strong strategies. However, it can sometimes be problematic since weak strategies may be useful to tackle niche tasks and discover stronger strategies later during training [40]. counter example that fails ED is the RPS-X game [38]:
-1 -2/51 -2/5
G =
-1 0 -2/5 2/3 2/5 2/5
0
In RPS-X, the initial population either (R), (P) or (S}. then PSRO-IN [1], which is variation of PSRO equipped with ED, will terminate in PR P. without finding {X}. since the best response of (R, P. S} still in (R, SJ. However, this population will be exploited by others using strategy X endlessly at test time. We show that how our method tackles this problem in Appendix A.2.
UDM PD (RPD). We consider the case that L has full rank here since PD (RPD) does not work when the rank diversity kernel is not full. Then PD (RPD) is actually UDM with f(x) = In(x)) and the linear kernel function:
max PD max del(C3) max Il
-
max Σ In(A.).
1=1
When the new eigenvalue is less than PD (RPD) would decrease and thus may ignore some weak but useful meta-strategies. In fact, through the Eq. (6) and the Jacobi formula [32]: det (exp (A)) exp Tr(A), A E MXM we can find that UDM also uses determinant to measure the diversity. However, UDM is different from PD (RPD) since the exponential of the diversity kernel is non- decreasing with duplicated rows, and thus UDM is well-defined when dealing with the redundant- strategy problem. We give an example to illustrate how UDM tackles this issue in Appendix A.2.

---

UDM vs. EC.
EC can be rewritten as:
EC By Bx
[||]
Tr(I
(L" +1) Tr(I) - Tr((C*+I))
M
M
X
M
Σ
2 1+
where are the eigenvalues of C MM' Hence, EC special case of QDM when f(x) 11(1+22 (1, K() = (5-) and strategy feature Φ; m.
To summarize, the existing diversity metrics special cases of UDM with explicit feature o kernel function K, and function f. By exploring novel settings these components, we can then propose more reasonable metric to circumvent the shortcomings of existing diversity metrics.
4 Algorithms
Inspired by [40], we extend the classic FP, PSRO and a-PSRO to their diverse versions by incorpo- rating UDM into their Oracle functions, and prove their convergences in two-player games.
4.1 UDM Fictitions Play
At each iteration t, UDM-FP discovers new strategy that gains a higher payoff and at the same time enriches the current population. Formally, UDM-FP only modifies the best response as follows:
BRT (T, arg max ( (ft, ")," + T. UDM(S; U (*)),,
#E
where Ti is tunable constant: and the population is updated by adding the new strategy πp E BR", (Tr,") so 1 Sp U }
Intuitively, as - oc, UDM-FP will almost surely converge to generulised weakened ficitiius play (GWFP) [26] as long as 7. - 0, and thus it has the same convergence guarantees with GWFP which converges to the NE on two-player zero-sum games or potential games (A more detailed description of GWFP can be found in Appendix A.1). So. have the following proposition: Proposition 3 (Convergence UDM-FP). If UDM is concave, and UDM-FP uses the update rule:
Th E m= + (BRR +
where at = o(1/log() is deterministic and perturbations U are the differences between the actual and expected changes in strategies. Then UDM-FP shares the same convergence property as GWFP: the policy sequence TH converges to the NE on two-player zero-sum games or potential games.
Proof. See Appendix A.3.3
4.2 UDM Policy-Space Response Oracle
In open-ended (meta-)games, PSRO [23, 33, 48, 58, 35] is a more effective method than the direct search methods since there are infinite (strttssttttteies... Here we extend our diversity metric to PSRO and develop UDM-PSRO for open-ended (meta-)games, Suppose that player has learned population S t-th iteration. The goal of UDM-PSRO find a new )stratyy Se parame- terised by 0 E RRd which maximizes the payoff's of player n and the diversity of Sp. Therefore, the Oracle function is:
0" ( ") arg max
Σ
"(S") g(S..S + UDDM(S" U {Se))),
(8)
BERd
S-RE8-R
where -" is the (meta-)policy of the player (Meta-)policy nh" is computed by (meta-)policy solver, such as NE, UNIFORM, etc.
UDM-PSRO can enlarge EGS when it adds new (meta-)strategy via Eq. (8); and thus the popula- tion learned by UDM-PSRO has great response capacity. Unlike UDM-PSRO, PSRO-IN can also enlarge EGS, but it needs to assume that both players should use their Nash policies.
7

---

Proposition 4 (EGS Enlargement). Adding a new (meta-) mneta-)strategy Se via Eq. (8) enlarges EGS. Formally, we have EGS(S") C E
Proof. See Appendix A.3.4.
4.3 UDM a-Policy-Space Response Oracle
UDM-PSRO suffers from the shortcomings of high complexity (i.e., (PrD-hard) in computing the NE in N-player general-sum games [9. 11] and the cuullibrium-selection problems [19, 18]. To avoid these problems, UDM a-PSRO replaces NE with a-Rank [54] in the meta-policy solver. Sup- pose that there are I. sink strongly-connected components (SSCC) nodes that have only incoming edges but no outgoing edges in the response graph of the game; and denote the a- a-Rank distribution of 1-th SSCC as π which can be considered as the meta- veta--poiicies for different types of opponents. Inspired by EC a-PSRO [40], we design an Oracle function that suits a-Rank for UDM a-PSRO:
O7 ( ) arg max ( {+})
1)
arg max Tr (f(c"))
*EAsT
Age
where the diversity kernel L = [g (o., d,)gglMMM is constructed by the strategy feature Φ; m and the quality term q::
q exp (E (1
M""("
In fact, Eq. (9) celebrates two aspects of diversity. The first first aspect is from UDM that forces players to find more diverse populations; and the second aspect is from L meta-polices T(),, which represents diverse opponents.
The following proposition shows the convergence of UDM on two-player symmetric NFGs. Proposition 5 (Convergence of UDM a-PSRO). In two-player symmetric NFGs, UDM a-PSRO converges to the sub-cycle of the unique SSCC.
Proof. See Appendix A.3.5
5 Experiments
To validate the diverse game solvers proposed in Section 4, we compare them with the baselines including self-play [17], PSRO [23], Pipeline-PSRO [34], PSRO-N [1], FEP-PSRO [30], and EC-PSRO [40]. Their performances
investigated in several games involving both transitive and non-transitive dynamics. If an algorithm cannot find a diverse and effective population, will easily stuck in local strategy cycles, and thus be exploited by others. Hence, exploitability and PE are used as evaluation metrics in the experiments. We focus on RD metrics and thus use the strategy feature of m, and use the kernel function K K(x, y) ((x, y) + 1)3 since the number of features is the same with the number of strategies. The function in UDM-PSRO a concave function f(x) = I+exp[-z] Y/2 E F (see Appendix A.5 for more discussions on the selection of f and K) More experimental settings and results can be found in Appendix A.4.
Real-World Meta-Game The properties some complex real-world meta-games are studied in paper [8], including AlphaStar and AlphaGO. In Figure I, we report the performances of different algorithms over the AlphaStar game, which contains the meta-payoffss for 888 RL meta-strategies. The results show that our method achieves the smallest exploitability, largest population effectivity and the largest diversity, while baselines without diverse objectives are easily exploited since they do not find diverse meta-strategies. Our method performs better since more diverse meta-strategies can help it jump out the current strategic cycles and thus find better strategies.
Blotto. Blotto is a classical resource allocation game that is often used to analyze electoral com- petition [45]. In this game, each of two players has a budget of coins which will be distributed simultaneously over fixed number of areas. A player wins an area where it puts the most coins; and the player that wins the most areas wins the game. We show the performances of different algorithms in this game with 3 areas and 10 coins in Figure 1; ods perform as well as the diversity-aware baselines, and outperforms baselines without diversity objectives in terms of expolitability and PE.
and the results show that our meth-
8

---

AlphaStar
grdotabll:
Wogatee FE
310
1AB Blotto
2M
Explliabtt
Nogaaive
Iteraiooss
Iterations
Rerations
Self-Play
P.PSRO
Figure 1: AlphaStar and Blotto:
Exploitability & Negative PE & UDM Iterations.
Mixture Model. Non-Transitive Mixture Model [40] is a zero-sum two-player game consisting of seven equally-distanced Gaussian humps on 2D plane. Each meta-strategy corresponds to point on the plane, and each point is translated into 7-dimensional vector S/ with each coordinate being the density in corresponding Gaussian distribution function. Since number of points is infinite, this game is open-ended, and it involves both transitive component and a mon-transitive component, which can be reflected by the payoff:
1
0
1
1
-1
-1
0
1
1
-1
π
1,T
-1
-1
-1
1
1
π
n
x()
-1
-1
-1
0
1
1
-1
-1
-1
0
1
-1
-1
Therefore, player should stay close to the center of the Gaussian and explore all the Gaussian distributions equally to avoid being exploited. We report the exploration trajectories when solving this game using different algorithms in Figure 2, which shows that our method can indeed generate diverse trajectories. We also report the exploitability and PE values for the final population generated by different algorithms in Table It can be found that our method outperforms all the basclines in terms of PE, which is better metric to evaluate diverse populations [30].
PSRO
EC-PSRO
RPD-PSRO
UDM-PSRO
X
X
Figure 2: Non- Transitive Mixture Model: Exploration trajectories during training.
Table 3: The OS (Opponent Strength) associated with the PEx 102 represents the strength of the opponent during the process of using PSRO to solve it. The last row is Exploit. x 10?.
PE(OS)
PSRO
PSRO-N
P-PSRO
EC-PSRO
RPD-PSRO
UDM-PSRO
PE(10)
-18.18
0.32
-18.18
0.32
9.62 + 0.16
9.34 0.13
9.68
0.19
9.73 + 0.24
PE(15)
-27.28
-27.28
0.43 0.04
0.01
0.04
0.39 0.05
0.44 0.06
PE(20)
-26.73 0.04
-26.73
0.10 0.12
0.18 +18 0.06
0.69 0.09
PB(25)
-25.47 = 0.07
-25.47 1.7 0.07
1.12 0.10
1.25 + 0.17
1.39 - 0.14
1.81 + 0.18
Exploit.
33.71 = 0.37
35.11 0.23
2.34 + 0.43
2.05 0.38
1.95 + 0.54
2.07 0.37

---

6 Conclusion
In this paper, we offer a consistent definition for the diversity of strategies in MARL, and propose a novel diversity measure that provides a unified view for existing diversity metric. With this mea- sure, develop corresponding diversity-promooinn algorithms based on FP and PSRO. In theory, we prove that our method converges to two-player NE and can enlarge gamescape by increasing the response capacity of the population. Empirically, we validate our method on games that show strong non-transitive including the matrix games, Blotto and non non-transitive mixture model. The re- sults show that our method outperforms the baselines in terms of the exploitability and population effectivity. In this paper, we mainly focus on the two-player games due to the expensive compu- tational cost of UDM in n-player cases (see Appendix 5 for more explanations). Investigating how to reduce the computational cost when extending UDM to n-player, general-sum, non-symmetric games can be an important future work.
Acknowledgments and Disclosure of Funding
The authors would like to thank anonymous reviewers for helpful feedback and discussions. This work was supported by the SYSU-ByteDance Research Project, and the National Natural Science Foundation of China under Grant 62076259.
References
[1] David Balduzzi, Marta Garnelo, Yoram Bachrach. Wojciech Czarnecki, Julien Pérolat, Max Jaderberg. and Thore Graepel. Open-ended learning in symmetric zero-sum games. International Conference on Machine Learning, volume 97, pages 434 443. PMLR, 2019.
[2] David Balduzzi, Sébastien Racanière, James Martens, Jakoh N. Foerster, Karl Tuyls, and Thore Grac- pel. The mechanics of n-player differentiable games. In International Conference on Machine Learning, volume 80. pages 363-372. PMLR, 2018.
[3] Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung. Przemyslaw Debiak, Christy Denni- son, David Farhi, Quirin Fischer. Shariq Hashme, Chris Hesse, Rafal Józefowicz. Scott Gray, Catherine Olsson, Jakub Pachocki, Michael Petrov, Henrique d.O. Pinto, Jonathan Raiman, Tim Salimans, Jeremy Schlatter, Jonas Schneider, Szymon Sidor, Ilya Sutskever, Jie Tang, Filip Wolski, and Susan Zhang. Dota 2 with large scale deep reinforcement learning. arXiv preprint arXiv: 191206609,, 2019.
[4] Lucian Busoniu, Robert Babuska, and Bart De Schutter. A comprehensive survey of multiagent rein- forcement learning. In IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), volume 38, pages 156 172. IEEE, 2008
[5] Ozan Candogan, Ishai Menache, Asuman E. Ozdaglar, and Pablo A. Parrilo. Flows and decompositions of games: Harmonic and potential games. In Mathematics of Operations Research, volume 36, pages 474-503. INFORMS, 2011.
[6] Laming Chen, Guoxin Zhang, and Eric Zhou, Fast greedy MAP inference for determinantal point process to improve recommendation diversity. In Advances in Neural Information Processing Systems, volume 31, pages 5627-5638, 2018
[7] Antoine Cully, Jeff Clune, Danesh Tarapore, and Jean- Saan-Baptitte Mouret. Robots that can adapt like animals. In Nature, volume 521, pages 503-507, 2015.
[8] Wojeiech M. Czarnecki, Gauthier Gidel, Brendan D. Tracey, Karl Tuyls, Shayegan Omidshafici, David Balduzzi, and Max Jaderberg. Real world games look like spinning tops. In Advances in Neural Informa- tion Processing Systems, volume 33, pages 17443-17454, 2020.
[9] Constantinos Daskalakis. Paul W. Goldberg, and Christos H. Papadimitriou. The complexity of computing nash equilibrium. In SIAM Journal on Computing, volume 39, pages 195-259. SIAM, 2009.
[10] Trevor Davis, Neil Burch, and Michael Bowling. Using response functions to measure strategy strength. In Proceedings of the AAAI Conference Artificial Intelligence, volume 28, pages 630-636, 2014.
[11] Xiaotie Deng, Yuhao Li, David Henry Mguni, Jun Wang, and Yaodong Yang. On the complexity of com- puting markov perfect equilibrium in general-sum sum stochastic games. arXiv preprint arXiv:2109.01995 2021.
10

---

[12] 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.07780, 2021.
[13] Mohamed Elfeki. Camille Couprie, Morgane Rivière, and Mohamed Elhoseiny. GDPP: learning diverse generations using determinantal point processes. In Proceedings of the 36th International Conference on Machine Learning, volume 97, pages 1774-1783. PMIR, 2019.
[14] Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learn- ing skills without a reward function. In International Conference on Learning Representations, 2019.
[15] Xidong Feng, Oliver Slumbers, Ziyu Wan, Bo Liu, Stephen McAleer, Ying Wen, Jun Wang, and Yaodong Yang. Neural auto-curricula in two-player zero-sum games. In Advances in Neural Information Process- ing Systems, volume 34, pages 3504-3517, 2021.
[16] David B. Fogel. Evolutionary computation:: toward new philosophy of machine intelligence. John Wiley & Sons, 2006.
[17] Drew Fudenberg, Fudenherg Drew, David K Levine, and David K Levine. The theory of learning in games. MIT press, 1998.
[18] Paul W. Goldberg, Christos H. Papadimitriou. and Rahul Savani. The complexity of the homotopy method, equilibrium selection, and lemke-howson solutions. In ACM Transactions on Economics and Computa- tion, volume I, pages 1 1-25, 2013.
[19] John C. Harsanyi and Reinhard. Selten. general theory of equilibrium selection in games, volume 18. MIT Press, 2001.
[20] Pablo Hermandez- Leal, Bilal Kartal, and Matthew E. Taylor. Is multiagent deep reinforcement learning the answer or the question? A brief survey. arXiv preprint arXiv: 2018.
[21] Max Jaderberg, Wojciech M Czarnecki, lain Dunning, Luke Marris, Guy Lever. Antonio Garcia Cas- taneda, Charles Beattie, Neil C Rabinowitz, Ari S Morcos, Avraham Ruderman, Nicolas Sonnerat, Tim Green, Louise Deason, Joel Z. Leibo, David Silver, Demis Hassabis, Koray Kavukeuoglu, and Thore Graepel. Human-level performance 3d multiplayer games with population-based reinforcement learn- ing. In Science, volume 364, pages 859 865. American Association for the Advancement of Science, 2019.
[22] Alex Kulesza and Ben Taskar. Determinantal point processes for machine learning. In Foundations and Trends in Muchine Learning, volume 5, pages 123-286. 2012.
[23] Mare Lanctot, Vinícius Flores Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Péro- lat, David Silver, and Thore Graepel. A unified cone-theoretic approach multiagent reinforcement learning. In Advances in Neural Information Processing Systems, volume 30, 2017.
[24] Joel Lehman and Kenneth O. Stanley. Abandoning objectives: Evolution through the search for novelty alone. In Evolutionary computation, volume 19, pages 189-223. MIT Press, 2011.
[25] Joel Lehman and Kenneth O. Stanley. Evolving a diversity of virtual creatures through novelty search and local competition. In 13th Annual Genetic and Evolutionary Computation Conference, pages 211 11121,, 2011.
[26] David S. Leslie and Edmund J. Collins. Generalised weakened fictitious play. In Games and Economic Behavior, volume 56, pages 285-298, 2006.
[27] Chenghao Li, Tonghan Wang, Chengjie Wu, Qianchuan Zhao, Jun Yang, and Chongjic Zhang Celebrat- ing diversity in shared multi-agent reinforcement lcarning. In Advances in Neural Information Processing Systems, volume 34, pages 3991-4002, 2021.
[28] Minghuan Liu, Tairan He, Minkai Xu, and Weinan Zhang. Energy-based imitation learning. In 20th International Conference on Autonomous Agents and Multiagent Systems, pages 809 887. ACM, 2021.
[29] Xiangyu Liu, Hangtian Jia, Ying Wen, Yujing Hu, Yingfeng Chen, Changjic Fan, Zhipeng Hu, and Yaodong Yang. Towards unifying behavioral and response diversity for open-ended learning in zero-sum games. In Advances in Neural Information P Processing Systems, volume 34, pages 941-952, 2021.
[30] Xiangyu Liu, Hangtian Jia, Ying Wen, Yujing Hu, Yingfeng Chen, Changjie Fan, Zhipeng Hu, and Yaodong Yang. Towards unifying behavioral and response diversity for open- ended learning in zero-sum games. In Advances in Neural Information Processing Systems, pages 941 952, 2021.
11

---

[31] Odile Macchi. The fermion processa model of stochastic point process with repulsive points, In Transac- tions the Seventh Prague Conference on Information Theory, Statistical Decision Functions, Random Processes and of the 1974 European Meeting of Statisticians, pages 391-398. Springer, 1977.
[32] Jan R Magnus and Heinz Neudecker. Matrix differential calculus with applications in statistics and econometrics. John Wiley & Sons, 2019.
[33] Stephen McAlcer, JB Lanier, Kevin Wang, Pierre Baldi, Roy Fox, and Tuomas Sandholm, Self-play psro: Toward optimal populations in two-player zero-sum games. arXiv preprint arXiv:2207.06544 2022.
[34] Stephen McAleer, John B. Lanier, Roy Fox, and Pierre Baldi. Pipeline PSRO: A scalable approach for finding approximate nash equilibria in large games. In Advances in Neural Information Processing Systems, volume 33, pages 20238-20248, 2020.
[35] Stephen McAleer, Kevin Wang, Marc Lanctot, John Lanier, Pierre Baldi, and Roy Fox. Anytime optimal psro for two-player zero-sum games, arXiv preprint Sedi::20010070000 2022.
[36] H. Brendan McMahan, Geoffrey J. Gordon, and Avrim Blum. Planning in the presence of cost functions controlled by adversary. In Proceedings of the 20th International Conference on Machine Learning. pages 536-543, 2003.
[37] lean-Baptiste Mouret and Jeff Clunc. Illuminating search spaces by mapping clites. arXiv preprint arXiv:1504.0440 1504,0499, 2015.
[38] Paul Muller, Shayegan Omidshafici, Mark Rowland, Karl Tuyls, Julien Pérolat, Siqi Liu, Daniel Hennes, Luke Marris, Mare Lanctot, Edward Hughes, Zhe Wang. Guy Lever, Nicolas Heess, Thore Graepel, and Rémi Munos. A generalized training approach for multiagent learning. In 8th International Conference on Learning Representations, ICLR 2020, 2020.
[39] John F. Nash. Equilibrium points in n-person games. In Proceedings of the National Academy of Sciences, volume 36, pages 48-49, 1950.
[40] Nicolas Perez Nieves, Yaodong Yang. Oliver Slumbers, David Henry Mguni, Ying Wen, and Jun Wang. Modelling behavioural diversity for learning in open-endee open-ended games. In Proceedings of the 38th Interna- tional Conference on Machine Learning, volume 139, pages 8514-8524, 2021.
[41] Shayegan Omidshafiei, Christos H. Papadimitriou. Georgios Piliouras, Karl Tuyls, Mark Rowland, Jean- Baptiste Lespiau, Wojeiech M. Czarnecki, Mare Lanctot, Julien Pérolat, and Rémi Munos. a-rank: Multi- agent evaluation by evolution. arXiv preprint
2019.
[42] Jack Parker-Holder, Aldo Pacchiano, Krzysztof Marcin Choromanski, and Stephen J. Roberts. Effective diversity in population based reinforcement learning. In Advances in Neural Information Processing Systems, volume 33, pages 18050- 2020.
[43] Peng Peng, Quan Yuan, Ying Wen, Yaodong Yang, Zhenkun Tang. Haitao Long, and Jun Wang. Mul- tiagent cidiiretiioaallycoordnntted nets for learning to play starcraft combat games. arXiv preprint arXiv: 10069, 2017,
[44] Justin K. Pugh, Lisa B. Soros, and Kenneth O. Stanley. Quality diversity: A new frontier for evolutionary computation. In Frontiers in Robotics and AI, volume 3, page 40, 2016.
[45] Brian Roberson. The colonel blotto game. In Economic Theory, volume 29, pages 1-24. 2006.
[46] Ricky Sanjaya, Jun Wang, and Yaodong Yang. Measuring the non-transitivity in chess. In Algoritiuns, volume 15, page 152. Multidisciplinary Digital Publishing Institute, 2022.
[47] Orial Vinyals, Igor Babuschkin, Wojeiech M. Czamecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H. Choi, Richard Powell, Timo Fwalds, Petko Georgiev, Junhyuk Oh, Dan Horgan, Manuel Kroiss, Ivo Danihelka, Aja Huang, Laurent Sifre, Trevor Cai, John P. Agapiou. Max Jaderberg, Alexan- der S. Vezhnevets. Rémi Leblond. Tobias Pohlen. Valentin Dalibard, David Budden, Yury Sulsky, James Molloy, Tom L. Paine, Caglar Gulcehre. Ziyu Wang, Tobias Pfaff. Yuhuai Wu, Roman Ring, Dani Yogatama, Dario Wünsch, Katrina McKinney, Oliver Smith, Tom Schaul, Timothy Lillicrap, Koray Kavukcuoglu, Demis Hassabis, Chris Apps, and David Silver. Grandmaster level in StarCraft II using multi-agent reinforcement learning. In Nature, volume 575, pages 350-354, 2019.
[48] Xinrun Wang, Jakub Cemny Shuxin Li, Chang Yang, Zhuyun Yin, Hau Chan, and Bo An. A unified perspective on deep equilibriu finding. arXiv preprint 2rX4::2004.049.10 2022.
12

---

[49] Zhe Wu, Kai Li, Enmin Zhao, Hang Xu, Meng Zhang, Haobo Fu, Bo An, and Junliang Xing. L2E: learning exploit your opponent. arXiv preprint 200.:2202.003811, 2021.
[50] Zifan Wu, Chao Yu, Deheng Ye. Junge Zhang. Haiyin Piao, and Hankz Hankui Zhuo. Coordinated proximal policy optimization. In Advances in Neural Information Processing Systems, volume 34, 2021.
[51] Pengtao Xie, Jun Zhu, and Eric P. Xing. Diversity-rromtingg bayesian learning of latent variable models. In Proceedings of the 33nd International Conference on Machine Learning, volume 48, pages 59-68. JMLR.org. org, 2016.
[52] Yaodong Yang, Jun Luo, Ying Wen, Oliver Slumbers, Daniel Graves, Haitham Bou Ammar, Jun Wang. and Matthew E Taylor. Diverse auto-curriclumm is critical for successful real-world multiagent learning systems. In Proceedings of the 20th International Conference Autonomous Agents and MultiAgent Systems, pages 51-56, 2021.
[53] Yaodong Yang, Jun Luo. Ying Wen, Oliver Slumbers, Daniel Graves, Haitham Bou-Ammar, Jun Wang. and Matthew E. Taylor. Diverse auto-curriculum critical for successful real-world multiagent learning systems. In 20th International Conference on Autonomous Agents and Multiagent Systems, pages 51-56. ACM, 2021.
[54] Yaodong Yang, Rasul Tutunov, Phu Sakulwongtana, and Haitham Bou Ammar. a -ran:: Practically scaling æ-rank through stochastic optimisation. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, pages 1575-1583, 2020.
[55] Yaodong Yang and Jun Wang. An overview of multi-agens reinforcement learning from game theoretical perspective. arXiv preprint arXiv:201
2020.
[56] Yaodong Yang, Ying Wen, Jun Wang, Liheng Chen, Kun Shao, David Mguni, and Weinan Zhang. Multi- agent determinantal q-learning. In International Conference on Machine Learning, volume 119, pages 10757-10766 PMLR, 2020.
[57] Deheng Ye, Guibin Chen, Wen Zhang, Sheng Chen, Bo Yuan, Bo Liu, Jia Chen, Zhao Liu, Fuhao Qiu, Hongsheng Yu, Yinyuting Yin, Bei Shi, Liang Wang, Tengfei Shi, Qiang Fu, Wei Yang, Lanxiao Huang, and Wei Liu. Towards playing full MOBA games with deep reinforcement learning. In Advances in Neural Information Processing Systems, volume 33, pages 621 2020.
[58] Ming Zhou, Jingxiao Chen, Ying Wen, Weinan Zhang, Yaodong Yang. and Yong Yu. Efficient policy space response oracles. arXiv preprint arXiv:2202. 00633, 2022.
2022.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [N/A]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] See Appendix
A.4
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix A.4
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used type of GPUs, internal cluster, or cloud provider)? [N/A]
13

---

4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're re using/curating? [N/A]
(e) Did you discuss whether the data you are using/eurating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "pgECdCfBuT", "reviewer": "Reviewer_67AT", "summary": "This paper presents a unified diversity measure (UDM) for MARL learning. By choosing different diversity kernels and the function $f$, UDM can recover different existing diversity metrics. The authors establish some convergence properties under UDM and then conduct several experiments (3 in the main text and 2 additional in the appendix) including both transitive and non-transitive games. The experimental results show that UDM outperforms baselines without explicit diversity objectives and is comparable to baselines with diversity objectives in terms of exploitability and population effectivity.", "questions": "The questions are mainly concerning the instantiation of UDM.\n\n(1) Could you elaborate why the kernel function $K\\langle x,y \\rangle=(\\langle x,y\\rangle+1)^3$ and $f(x)=\\frac{1}{1+\\exp(-x)}-\\frac{1}{2}$ is chosen? Or, is there any principle for choosing these two functions in UDM?\n\n(2) Will UDM-FP and UDM-$\\alpha$-PSRO perform better (in terms of expl and PE) than the baselines that used FP and $\\alpha$-PSRO respectively?\n\n(3) This work seems to focus on RD, while UDM can be readily applied to BD. FEP-PSRO unified BD and RD, and the experiments showed it is helpful. Can UDM incorporate RD and BD simultaneously and achieve better performance than only considering one of RD and BD?\n\n(4) The convergence of UDM-FP is provided by showing it is a GWFP process. Is it possible to show a faster convergence speed with this diversity term?", "limitations": "I favor the motivation of this paper, and the proposed method can provide a better perspective on the population diversity in MARL (especially in open-ended learning for two-player zero-sum games). It would be very helpful to provide an ablation study so that future researchers can know how to instantiate UDM.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**:\n\nThis study is closely related to the learning for MARL. With a more diverse population, we are expected to achieve a faster learning speed to the target objective (e.g., lower exploitability, higher population effectivity). However, existing diversity metrics may be motivated by different practical observations and no well-defined unified diversity metric for the learning of multi-agent systems. UDM serves this purpose well by unifying existing diversity metrics into a single function, which may help to design new learning algorithms.\n\nI think this paper is well-written and easy to follow. Based on a diversity kernel matrix, the authors show how UDM correlates to and differs from existing diversities. Some benefits of UDM are also revealed -- UDM can not only recover ED and PD separately but also tackle some of the notorious problems (ignoring weak but useful strategies and cannot distinguish redundant strategies).\n\nBesides, UDM also seems technical sound where the methods and proofs are intuitive.\n\n\n**Weaknesses**:\n\nCurrent implementations (the choice of the kernel function and $f$) and experiment results are less informative. In the experiment part, the authors focus on $K\\langle x,y \\rangle=(\\langle x,y\\rangle+1)^3$ and $f(x)=\\frac{1}{1+\\exp(-x)}-\\frac{1}{2}$ and only RD metrics. UDM generalizes RD and BD, while only a small part of the generation is shown in the current version. From the experiments, in terms of exploitability (expl) and PE, the differences among UDM, EC-PSRO, and FEP-PSRO are indistinguishable in AlphaStar888 and Blotto. I noticed that the experiments on two extensive-form games also demonstrated the above results, and the expl and PE of FEP-PSRO seems to be slightly better. The experiments for UDM-FP and UDM-$\\alpha$-PSRO are missing. More insights (empirical or theoretical) from other instantiations of UDM are expected, which can be achieved by an ablation study.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5BsVUTlAulr", "reviewer": "Reviewer_Bqe8", "summary": "This paper offers a unified diversity measure for multi-agent reinforcement learning. The authors first show the existing diversity measure and then provide Unified Diversity Measure (UDM) from a geometric perspective to unify all existing diversity measures. After showing the relationship between UDM and existing diversity measures, the authors provide two algorithms, UDM Fictitious Play and UDM PSRO, to provide diversity policies. Experiments on AlphaStar and Blotto show the performance of the proposed method over baselines.", "questions": "- Add the background of the geometric intuition.\n- Polish the notation and the writing of this paper for more general audiences, not only for the game theory community but also the reinforcement learning/machine learning community.\n- How to generate strategy feature and diversity kernel when applying UDM in the new games.\n- What if the number of agents is not two?\n- Line 293, missing the experiments of AlphaGO. \n- If a game has NE, why do we need to explore the diversity, especially when we can get the whole payoff matrix.\n- I am curious about the experiments on AlphaStar. AlphaStar is trained for about 14 days with 16 TPUs for each agent. How to get meta-payoffs for 888 RL meta-strategies?\n\n- Minor\n    - Line 203 the meaning of Hadamard product of a vector and a matrix\n    - The meaning of $|| \\cdot ||_{F}$ above line 206\n    - What is $m^*_i$ in line 207\n    - Line 186 “similar with” -> “similar to”\n", "limitations": "I didn't find the description of the limitation of the proposed methods. And the authors didn't discuss any potential negative societal impacts. The author can describe the limitation, for example, is the proposed method limited to the two-player zero-sum game.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Strengths\n    - The unified framework reveals the similarity among various diversity measures, and provides a new view of the diversity of policies.\n    - The overall writing flow is good\n\n- Weaknesses\n    - Lack of the background of the geometric intuition.\n    - The notations are too much and confusing, which are unfriendly to the audiences outside the game theory community.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1VoJI3gaWA", "reviewer": "Reviewer_6GhH", "summary": "This paper proposes a unifying diversity measure of three diversity measures (ED, PD, and EC), and uses the unification to explain properties of the existing metrics. UDM-PSRO is proposed which uses the new diversity metric as an oracle. It is compared to other baselines on some simple normal-form games.", "questions": "Q1: Can this diversity measure be easily extended to n-player, general-sum, or non-symmetric games?", "limitations": "The usual limits on symmetric tow-player zero-sum should be states again in the conclusion please.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: This paper is well-written and clear to follow. The maths and proofs seem sound to me. The key idea is interesting and important research.\n\nWeaknesses: Exploitability experiments show similar performance to other pre-existing methods. Exploitability of extensive-form games was not evaluated.\n\nI think this is a strong paper. More thorough evaluation on (real) extensive form games would make it stronger.\n\nComments:\n\nExperiments Section (Figure 1): I believe all the experiments are made on normal-form games? Therefore it might be good to mention/cite double oracle as well as PSRO.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept