Policy Space Diversity for Non-Transitive Games
Authors: Jian Yao
Weiming Liu
Haobo Fu
Yaodong Yang
Stephen Marcus McAleer
QIANG FU
Yang Wei
Venue: NeurIPS 2023 poster (2023)
Keywords: Policy Diversity
Policy-Space Response Oracles
Nash Equilibrium
Multi-agent Reinforcement Learning
TL;DR: A new and better-justified policy diversity regularization for improving the Nash Equilibrium approximation in Policy-Space Response Oracles.

Abstract: Policy-Space Response Oracles (PSRO) is an influential algorithm framework for approximating a Nash Equilibrium (NE) in multi-agent non-transitive games. Many previous studies have been trying to promote policy diversity in PSRO. A major weakness with existing diversity metrics is that a more diverse (according to their diversity metrics) population does not necessarily mean (as we proved in the paper) a better approximation to a NE. To alleviate this problem, we propose a new diversity metric, the improvement of which guarantees a better approximation to a NE. Meanwhile, we develop a practical and well-justified method to optimize our diversity metric using only state-action samples. By incorporating our diversity regularization into the best response solving of PSRO, we obtain a new PSRO variant, \textit{Policy Space Diversity} PSRO (PSD-PSRO). We present the convergence property of PSD-PSRO. Empirically, extensive experiments on single-state games, Leduc, and Goofspiel demonstrate that PSD-PSRO is more effective in producing significantly less exploitable policies than state-of-the-art PSRO variants.

Policy Space Diversity for Non-Transitive Games
Jian Yao'*, Weiming Liu Haobo Fu' Yaodong Yang², Stephen McAleer'. Qiang Fu', Wei Yang'
Tencent AI Lab. Shenzhen, China
PPeknng University, Beijing, China
Carnegie Mellon University
Abstract
Policy-Space Response Oracles (PSRO) is an influential algorithm framework for approximating Nash Equilibrium (NE) in multi-agent non-transitive games. Many previous studies have been trying to promote policy diversity in PSRO. A major weakness in existing diversity metrics is that more diverse (according their diversity metrics) population does not necessarily mean (as we proved in the paper) better approximation NE. To alleviate this problem, we propose new diversity metric. the improvement of which guarantees a better approximation to NE. Meanwhile, we develop practical and well-justified method to optimize our diversity metric using only state-action samples. By incorporating our diversity regularization into the best response solving PSRO, we obtain new PSRÓ variant, Policy Space Diversity PSRO (PSD-PSRO). We present the convergence property of PSD-PSRO. Empirically, extensive experiments on various games demonstrate that PSD-PSRO is more effective in producing significantly less exploitable policies than state-of-the-ar PSRO variants. The experiment code is available http:://tthhbb.com/nggg//////e http::/wwhhbboooooooeecee///oo/p
1 Introduction
Most real-world games demonstrate strong non-transitivity 9 where the winning rule follows a cyclic pattern (e.g., the strategy cycle in Rock-Paper-Scissors))
6 3 A common objective in solving
non-transitive games is to find Nash Equilibrium (NE), which has the best worst-case performance in the whole policy space. Traditional algorithms, like simple self-play, fail converge NE in games with strong non-transitivity (26). Recently, many game-theoretic methods have been proposed to approximate NE in such games. For example, Counterfactual Regret Minimization (CFR) [54] minimizes the so-called counterfactual regret. Neural fictitious self play 19 extends the classical game-theoretic approach, Fictitious Play (FP) 4. larger games using Reinforcement Learning (RL) to approximate Best Response (BR). Another well-known algorithm is Policy- Space Response Oracles (PSRO) (26). which generalizes the double oracle approach [38 by adopting a RL subroutine to approximate BR.
Improving the performance of PSRO on approximating a NE is active research topic, and many PSRO variants have been proposed so far, which generally fall into three categories. The first category (36, 45
29 aims to improve the training efficiency each iteration. For instance, PiReline-PSRO (36] trains multiple BRs in parallel at each iteration. Neural population learning (29 enables fast transfer learning across policies via representing a population of policies within single conditional model. The second category [37 53 incorporates no-regret learning into PSRO, which solves an unrestricted-restriee
12
game with a no-regret learning method to guarantee the decrease of exploitability of the meta-strategy across each iteration. The third category [2 41 32 33
"Equal contribution. Correspondence to: Haobo Fu (haohofu@tennemt.coom
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

promotes policy diversity in the population, which is usually implemented by incorporating a diversity regularization term into the BR solving in the original PSRO.
Despite achieving promising improvements over the original PSRO, the theoretical reason why the
diversity metrics in existing diversity-enhancing PSRO variants (2 41 32 33 help PSRO in terms of approximating a NE is unclear. More specifically, those diversity metrics are 'justified' in the sense that adding the corresponding diversity-reguularized BR strictly enlarges the gamescape. However, as we prove and demonstrate later in the paper, a population with a larger gamescape is neither a sufficient nor a necessary condition for better approximation (we will define the precise meaning later) to a NE. One fundamental reason is that gamescape is a concept that varies significantly according to the choice of opponent policies. In contrast, exploitability (the distance to a NE) measures the worst-case performance that is invariant to the choice of opponent policies.
In this paper, we seek for new and better justified diversity metric that improves the approximation of a NE in PSRO. To achieve this, we introduce a new concept, named Population Exploitability (PE), quantify the strength of a population. The PE of population the optimal exploitability that can be achieved by selecting a policy from its Policy Hull (PH), which is simply a complete set of polices that are convex combinations of individual polices in the population. In addition, we show that larger PH means a lower PE. Based on these insights, we make the following contributions:
We point out a major and common weakness of existing diversity-enhanccin PSRO variants: their goal of enlarging the gamescape of the population in PSRO is somewhat deceptive to the extent that it can lead to weaker population in terms of PE. In other words, a more diverse (according to their diversity metrics) population = larger gamescape #> closer to a full game NE.
We develop new diversity metric that encourages the enlargement of population's PH. In addition, we develop a practical and well-justified method to optimize our diversity metric using only state-action samples. We then incorporate our diversity metric (as regularization term) into the BR solving in the original PSRO and obtain a new algorithm: Policy Space Diversity PSRO (PSD-PSRO). Our method PSD-PSRO establishes the causality: more diverse (according to our diversity metric) population = larger PH + a lower PE = closer to full game NE.
We prove that a full game NE is guaranteed once PSD-PSRO converged. In contrast, it is not clear, in other state-of-the-art diversity-enhancing PSRO variants 2 32 33), whether full
game NE is found once they are converged in terms of their optimization objectives. Notably, PSRO, is not guaranteed to find NE once converged (36]
2 Notations and Preliminary
2.1 Extensive-form Games, NE, and Exploitability
Extensive-form games are used to model sequential interaction involving multiple agents, which can be defined by a tuple (N, S, P. A, u). .V {1, 2 denotes the set of players (we focus on the two-player zero-sum games). S is set of information states for decision-making. Each information state node S includes set of actions A(s) that lead subsequent information states. The player function P S + N [c]. with c demoting chance, determines which player takes action in s. We St S, (s E Ss)(s) i), and A, Uses, A(s) to denote player i's state, set of states, and set of actions respectively. We consider games with perfect recall, where each player remembers the sequence of states to the current state.
player's behavioral strategy is denoted by ny (s) E A(A(s)), Vs S,, and (als)) the probability of player taking action in s. A strategy profile π (TI, T2) is pair of strategies for each player, and we use n- to refer to the strategy in π except π,. (²(=) = u, u, --)) denotes the payoff for player i when both players follow The BR of player to the opponent's strategy m= is denoted by ()) = arg max,; U4 Uz(T π c). The exploitability of strategy profile æ is defined as:
{(T)
Σ
(max us (T/, T- u.(TT, -)].
(1)
2
NE.V
When E(T) 0, is a NE of the game.

---

2.2 Meta-Games, PH, and PSRO
Meta-gaman aeta-games are introduced represent games at a higher level. Denoting a population of mixed strategies for player i by II, == { m. ..... J. the payoff matrix on the joint population II = II; x II is denoted by MI..I... where Mn..I.11. k] := u, ( xf,). The meta game II and Mn, .I_;; is simply a normal-form game where selecting an action means choosing which T. to play for player Accordingly, we use o; (o; is called meta-strategy and could be, e.g.. playing [m] x3] with probability [0.5, 0.5) to denote a mixed strategy over II, i.., oj E An,- A meta-policy o; over II; convex combination of polices in II, and we define the PH of population H(I,))
can be viewed as the set of all convex combinations of the policies in IT, Meta-games are often open-ended in the sense that there exist an infinite number of mixed strategies and that new policies will be successively added to IT, and IT_; respectively. We give a summary of notations in Appendix
PSRO operates meta-games and consists of two components: oracle and meta- veta-policy solver. At each iteration t, PSRO maintains a population of policies, denoted by 11;, for each player i. The joint meta-policy solver first computes a NE meta-policy of on the restricted meta-game represented by M : Afterwards, for each player i, the oracle computes an approximate BR (i.e., m/+1)
against the meta-policy o'ا; ={+1 E BR(o".). The new policy प. is then added to its population (TT++ I U (m;+1)), and the next iteration starts. In the end, PSRO outputs meta-policy NE on the final joint population as an approximation to a full game NE.
2.3 Previous Diversity Metries for PSRO
Effective diversity [2] measures the variety of effective strategies (strategies with support under a meta-policy NE) and uses a rectifier focus on how these effective strategies beat each other. Let (a ox,) denote a meta-policy NE on MII.II.-- The effective diversity of II, is:
Div(II,) = M
where |ar]+ == x if x 2 clse 0.
Expected Cardinality 41,, inspired by the determinantal point processes [35, measures the diversity of population II, as the expected cardinality the random set Y sampled according to del( (En):
Div(II,) = EEy-PEn [|]]] = Tr(I - (Ln + I)=),,
where Y is the cardinality of and L = Mn, M" II,II.,
Convex Hull Enlargement 332 builds on the idea of enlarging the convex hull of all row vectors in the payoff matrix:
Div (+)))
min
| m||:
1 3=1,10000
where Tς is the new strategy to add, and m is the payoff vector of policy nद against each opponent policy in II:;: mij] (<(=,,___))
Occupancy Measure Mismatching 32 considers the state- state-action distribution pa (= a) induced by joint policy When considering adding new policy n/K the corresponding diversity metric is:
(II U (x())
(5)
where n/ is the new policy to add; (at.aï.) is a meta-policy NE on My..I... and Dy is general f- divergence between two distributions. It is worth noting that Equation 5 only considers the difference between two policies (τ, and of), instead of 9i and II, In practice, this diversity metric is used together with the convex hull enlargement [2).
Unified Diversity Measure
33 offers a unified view on existing diversity metrics and is defined as:
[..
DIv = Σ s(Am).
where f takes different forms for different existing diversity metrics; Am is the eigenvalues of [K (&m; Φnn] [x I.I: K(,,)) is predefined kernel function; and om.. is the strategy feature for the m-th policy in II, It is worth mentioning that only payoff vectors in MI,. were investigated for the strategy feature of the new diversity metric proposed in [33]
3

---

3 A Common Weakness of Existing Diversity-Enhancing PSRO Variants
As shown in last section, all previous diversity-enhancing PSRO variants the gamescape of IT, which is the convex hull of the rows in the empirical payoff matrix:
33 try to enlarge
GL IL)) = 1 aymy a 0, 0,a"1=11,
where mj is the j-th row vector in MI..I.,- However, the gamescape of population depends on the choice of opponent policies, and two policies with the same payoff vector are not necessarily the same. Moreover, enlarging the gamescape without careful tuning would encourage the current player to deliberately lose to the opponent to get 'diverse" payoffs. We suspect this might be the reason why the optimization of the gamescape is activated later in the training procedure in [32] PSRO variants why
More importantly, is not theoretically clear from previous diversity-enhancii enlarging the gamescape would help in approximating a full game NE in PSRO.
To rigorously answer the question whether diversity metric helpful in approximating a NE in PSRO, we need a performance measure to monitor the progress of PSRO across iterations in terms of finding a full game NE. In other words, we need to quantify the strength of population of policies. Previously, the exploitability of meta NE of the joint population is usually employed to monitor the progress of PSRO. Yet, as demonstrated in [37], this exploitability may increase after an iteration. Intuitively, a better alternative is the exploitability of the least exploitable mixed strategy supported by a population. We define this exploitability as the population exploitability:
Definition 3.1. For a joint population 11 = II, x 11 let (ot, be a meta NE on MI.. The
relative population performance of 11, against I1_; [2] is:
(T, II;) = a; "MM MM,,u,,
The population exploitability of the joint population II is defined as:
1
PE(II)
Σ
max P.(II, IL,), m
(8)
2
1,1,2
where Qi is the full set of all possible mixed strategies of player
We notice that PE is equal the sum of negative population effectivity defined in 32 PE as it is more of a natural extension to exploitability in Equation Some properties of PE and its relation to PH are presented in the following. Proposition 3.2. Considering a joint population II, II_,, we have:
Yet, prefer
1. (TI 2 0, III
2. For another joint population IT', (I,) H(T22) H(IT)) x H(TT_,)) then PE(IT) 2 PE(IT))
3. II; { and I1;; {m- then PE(II) {TT), where (TT)
4. 3r = =(Ts,T_)) E H(III,) x H(II.) s.t. (TT) = PIIII = EMD. E(T').
5. Let (ot,o",) denote an arbitrary NE of the full game. PE(II) = 0 if and only if (ot, H(II:) X H(II.)).
The proof is in Appendix B.2 Once we use PE to monitor the progress of PSRO, we have: Proposition 3.3. The PE of the joint population II' at each iteration t in PSRO is monotonically decreasing and will converge in finite iterations for finite games. Once PE 0, a meta NE on II is full game NE.
The proof is in Appendix B.3 From Proposition 3.2 and 3.3 we are convinced that PE is indeed an
appropriate performance measure for populations of polices. Using PE, we can now formally present why enlarging the gamescape of the population in PSRO is somewhat deceptive:
Theorem 3.4. The enlargement of the gamescape is neither sufficient nor necessary for the decrease of PE. Considering two populations (I1; and I1;) for player i and one population II_, for player -i,
and denoting IT = TT: x II 1,2 we have GS(II) & GS * PE(IT)) > PE(II))
PE(II) > PE(II) * GS(LI))LLA & G
(9)

---

The proof of Theorem 3.4 is in Appendix B.5 where we provide concrete examples.
In other words, enlarging the gamescape in either short term long term does necessarily lead to a better approximation to full game NE.
4 Policy Space Diversity PSRO
In this section, we develop new diversity-enhaneing PSRO variant, i.e., PSD-PSRO. In contrast to methods that enlarge the gamescape, PSD-PSRO encourages the enlargement of PH of a population, which helps reduce a population's 's PE (according to Proposition 3.2). In addition, we develop well-justified acttinattion sampling method to optimize our diversity metric in practice. Finally, we present the convergence property of PSD-PSRO and discuss its relation the original PSRO.
4.1 A New Diversity Regularization Term for PSRO
Our purpose of promoting diversity PSRO facilitate the convergence to full game NE. We follow the conventional scheme in previous fiversity-enhancing PSRO variants [4] 32 33 which introduces a diversity regularization term to the BR solving in PSRO. Nonetheless, our diversity regularization encourages the enlargement of PH of the current population, which is in contrast the We thus name our diversity metric policy space diversity. Intuitively, the larger the PH of a population is, the more likely it will include a full game NE. More formally, a larger PH means a lower PE (Proposition 3.2). which means our diversity metric avoids the common weakness (Section 3) of existing ones.
enlargement of gamescape in previous methods 2 41 32 33
Recall that the PH of population simply the complete set polices that are convex combinations of individual polices in the population. To quantify the contribution of new policy to the enlargement of the PH of the current population, a straightforward idea is to maximize a distance between the new policy and the PH. Such distance should be 0 for any policy that belongs to the PH and greater than otherwise. Without loss of generality, the distance between a policy and a PH could be defined the minimal distance between the policy and any policy in the PH. We now write down the diversity regularized BR solving objective in PSD-PSRO, where at each iteration for player we add new policy [+1 by solving:
1+1 arg max u(TT,,''))) +
min dist(T,, ( xf)
(10)
x =
where of_, is the opponent's meta NE policy at the t-th iteration, À is a Lagrange multiplier, and dist(;,)) -) is distance function (will be specified in the next subsection) between two polices.
4.2 Diversity Optimization in Practice
To be able to optimize our diversity metric (the right part in Equation 10p in practice, we need to encode a policy into some representation space and specify a distance function there. Such representation should be one-to-one mapping between policy and representation. Also, to ensure that enlarging the convex hull in the representation space results in the enlargement of the PH, we require the representation to satisfy the linearity property. Formally, we have the following definition:
Definition 4.1. A fine policy representation for our purpose is function p 11, - RN,, which satisfies the following two properties:
(bijection) For any representation p(T;),, there exists a unique behavior policy n, whose representa- tion is p(TTs, and vice-versa.
(linearity) For any two policies (mī and mht and a (0 S a < 1), the following holds:
plan) + +11 - (1-a)=²) = ap( p))
where am? + a. means playing नं with probability and .. with probability (1 a).
5

---

Existing diversity metrics explicitly or implicitly define policy representation B3
For instance,
the gamescape- methods [2 4T 32 331 represent a policy using its payoff vector against the opponent's population. Yet, this representation is not a fine policy representation as it is not a bijection (different policies can have the same payoff vector). The (joint) occupancy measure, which is a
fine policy representation, is usually used to encode policy in the RI community [48] 20 32 The f-divergence is then employed to measure the distance between two policies [32 24 16]. However,
computing the f-divergence based on the occupancy measure is usually intractable and often in practice roughly approximated using the prediction neural networks
[6]
Instead, we use another fine policy representation, i.e., the sequence-form representation [2] 31 [. which was originally developed for representing policy agent games. We then define the distance between two policies using the Bregman divergence, which can be further simplified to tractable form and optimized using only state-action samples in practice.
The sequence-form representation of a policy remembers the realization probability of reaching state-action pair. We follow the definition in [I], where the sequence form representation z; X2 S [0, 1] Sxxx; I of Ty is vector:
(1(8,a)=
II
(a(
(11)
where r(s, a) is trajectory from the beginning to a)) By the perfect-recall assumption, there is unique T that leads to (s, a). The policy क, can be written as {.(ass) = 0i a)/[2z [s)]), where (s) is (z:(s, a.).....: (s, a..)) with d1...., an E A(s). Unlike the payoff vector representation or the occupancy measure representation, x; is independent of the opponent's policy as well as the environmental dynamics. Therefore, it should be more appropriate representing policy for the diversity optimization. Without loss of generality and following 21 31,. we define the distance (ist(T;; xd) between two policies as the Bregman divergence the sequence form representation Ba (z: [ar)), which can be further written in terms of state-action pairs (the derivation is presented in Appendix B.T) in the following:
dist(mg Te, T() = Ba(x):laa))) =
E 8,0ES,XA,
II
B,Ba, (Te(s)
(12)
where Ba, (s: T (s)) is the Bregman divergence between (s) and (s). our experiment,
we let BR, (s) [s)[[((())))))))))))))))){){))){
>n (a)ss) ) log T. (c(ss))/(((als)
(L(T, (s) (s)), i.e., the KL di-
vergence. In previous work 11011 31, the coefficient B, usually declines monotonically as
length of the sequence increases. In our case, we make 3, depend on an opponent's policy b-,:
This weighting method allows us to estimate the distance using the sampled average KL divergence and avoids importance sampling:
B, = II . (
dist(T,, m3)
Σ
(.((..))
II (LL (- Ba, (T))))))))))
5,ESS:AA
(.
E B
(T:
(13)
where 8; Tú, bbi means sampling player i 's information states from the trajectories that are collected by playing n; against b_g. As a result, we can rewrite the diversity regularized BR solving objective in PSD-PSRO as follows:
1+1 = arg max ITs
u( (((Ti,
min *FEH((I))))
(14)
Now provide a practical way to optimize Equation 14 By regarding the opponent and chance as the environment, we can use the policy gradient method [4
43] 44 in RL to train af I+1 Denote the probability of generating by (T),,, and the payoff of player for the trajectory 7 by R(r). Let n.. arg min Be,oTe,B_, [KL (s;) | (s:)) be the policy in H(II.) that minimizes
the distance and let RK RKL(T) = E, (L (s)))
Assume 3, O. ie.. (alss-))) 0,, D,s S-; A-i.

---

The gradient of the first term u(TT; of in Equation 14
with respect to can be written as:
Vu(mi,o''j) T. (T))
V
VTi(t)
E
log n. (T)
(15)
The gradient of the diversity term in Equation
with respect to ny can be written as:
Va min of *FE(II))
R R.
VE ET.TNR [KL(T, (m)"((:)))))
((T) (T)dr
(T((T) (T)dT
Ti(T (T(T)BBs (VLL[T (s:)))dr
-Erorehhe (V log TH RR EV
(s:))),
(16)
where we use the property that VE|K (T (s:)] 8 min L correctness can be shown from the following proposition:
whose
Proposition 4.2. For any local Lipschitz continuous function fxx y), assume Vx, miny f(x, y) exists, then Oz (Ir, velye min f(2,g) O2 miny (x, y), where 0f is the generalized gradient (Z].
Proof. According to Theorem 2.1 (property (4) in [7]. the result is immediate, as 0, min,, f (x, y) is convex hull of (x, w)ly E arg max g(r y)}.
Combining the above two equations, we have,
u(( 0-1) X min En [KL(( (
* *TEHITT))
(17)
E Er V log T. [(T]] + AE b.. V log (T)
AR V KT (8:)
min (x:))]
According to Equation| 17 we can see that optimizing x. ++1 requires maximizing two types of rewards: R(r) and (T). This can be done by averaging the gradients using samples that are generated by playing n; against o², and b_, separately. The last term in Equation 17 is easily estimated by sampling states in the sampled trajectories via playing क; against b... For training efficiency, we simply set b-; of in our experiments, although other settings of b., are possible, e.g., the uniform random policy. We also want emphasize that we optimize 7 for each iteration and of_ is fixed during an iteration and thus can be viewed as part of the environment. Finally, to estimate the distance between m. and n. mimnn we should ideally compute T: exactly first by solving convex optimization problem. In practice, we find sampling the policies in H(II)) and using the minimal sampled distance already gives us satisfactory performance. The pseudo-code of PSD-PSRO is provided in Appendix
4.3 The Convergence Property of PSD-PSRO
We first show how the PH evolves in the original PSRO:
Proposition 4.3. Before the PE of the joint population reaches O, adding BR to the meta NE policy from last iteration in PSRO will strictly enlarge the PH of the current population.
The proof is in Appendix B.3 From Proposition
we can see that adding a BR serves one way (an implicit way) of enlarging the PH and hence reducing the PE. In contrast, the optimization of our diversity term in Equation 14)onn14ainn aims to explicitly en enlarge the PH. In other words, adding diversity regularized BR in PSD-PSRO serves as mixed way enlarging the PH. More formally, we have the following theorem:

---

Theorem 4.4. (1) In PSD-P before the PE of the joint population reaches 0, adding an optimal solution in Equation will strictly enlarge the PH and hence reduce the PE. (2) Once the PH can not be enlarged (i.e., PSD-PSRE converges) by adding an optimal solution in Equation 14 the PE reaches 0, and PSD-PSRO finds a full game NE.
The proof is in Appendix B.6 In terms of convergence property, one significant benefit of PSD-PSRO over other tatte-of-thh-arr diversity-enber wenhnniy-nnanniing PSRO variants [2 41 32 [3] is the convergence of PH guarantees full game NE in PSD-PSRO Yet. it is not clear in those papers whether full game NE is found once the PH of their populations converge. Notably, PSRO,N 2 is not guaranteed to find NE once converged [36]. In practice, we expect significant performance improvement of PSD-PSRO over PSRO in approximating a NE. As for different games, there might exist different optimal trade-offs between 'exploitation' (adding BR) and 'exploration' (optimizing diversity metric) in enlarging the PH and reducing the PE. In other words, PSD-PSRO generalizes PSRO (a PSD-PSRO instance when À 0) in ways of enlarging the PH and reducing the PE.
Related Work
Diversity has been widely studied evolutionary computation [3] with a central focus that mimics
the natural evolution process. One of the ideas is novelty search 28 which searches for policies that lead to novel outcomes. By hybridizing novelty search with a fitness objective, quality-diversity [42) aims for diverse behaviors of good qualities. Despite these methods achieving good empirical results 88 2,), the diversity metric is often hand-crafted for different tasks.
Promoting diversity is also intensively studied in RL. By adding distance regularization between the current policy and a previous policy, diversity-driver approach has been proposed for good exploration 22 Unsupervised learning of diverse policies [10] has been studied to serve as an effective pretraining mechanism for downstream RL tasks. A diversity metric based on DPP [39] has been proposed to improve exploration in population-based training. Diverse behaviors were learned order to improve generalization ability for test environments that are different from training [25]. A diversity-regullriizdd collaborative exploration strategy has been proposed in [40]. Reward randomization [49] has been employed to discover diverse strategies in multi-agent games. Trajectory diversity has been studied for better zero-shot coordination in multi-agent environment 34]. Quality-similat diversity has been investigated [5I].
Diversity also plays role in game- theoreti methods. Smooth FP 17 adds policy entropy term when finding BR. PSRO,, 2 encourages effective diversity, which considers amplifying the strength over the weakness in a policy. DPP-PSRO 41 introduces a diversity metric based on DPP and provides a geometric interpretation of behavioral diversity. &D&RD- occupancy measure mismatch and the diversity on payoff vectors as a unified diversity metric. UDM 33 summarizes existing diversity metries, by providing a unified diversity framework. In both opponent modeling [15] and opponent-liminee limited subgame solving (30,, diversity has been shown to have a large impact on the performance.
332 combines the
AlphaStarB88
AlphaStar88B
PSRRO
PSRC-HN
PSRD-N
DPP PSRO
Pop Population Erolotabbiity
DPP PSRO
PSD-PSRO (Ours)
PSD-PSRO (Ours)
300
120
130
175
attons
Iterations
Figure 1: (a): Exploitability of the meta NE, (b): PE of the joint population.

---

A-5RR
PSRO-IN
SPR-5510
SDARD
Egp 40
Exp: 2.9
Exp: 2.7
2:4
Egc 2
Expe Ld8a
Figure 2: Non-Transitiv Mixture Game Exploration trajectories during training. For each method, the final exploitability x 100 (Exp) is reported at the bottom.
6 Experiments
The main purpose of the experiments is to compare PSD-PSRO with existing state-of-the- PSRO variants in terms of approximating a full game NE. The baseline methods include PSRO Pipeline
PSRO (P-PSRO) 36. PSRO,, [2], DPP-PSRO AT. and BD&RD-PSRO [32. The benchmarks consist of single-state games (AaphaSta8888 and transitiniie mixture game) and complex extensive games (Leduc poker and Goofspiel). For AlphaStar888 and Ledue poker, we report the exploitability of the meta NE and the PE of the joint population through the training process. For the non-transitive mixture game, we illustrate the 'diversity" of the population and report the final exploitability. For Goofspiel where the exact exploitability intractable, In addition, we illustrate how the PH evolves for each method using the Disc game 2 in Appendix D.3 where PSD-PSRO more effective at enlarging the PH and approximating NE. An ablation study on Å of PSD-PSRO in Appendix D.2 reveals that, for different benchmarks, an optimal trade-off' between 'exploitation' and "exploration" in enlarging the PH to approximate NE usually happens when À is greater than zero. Error bars or stds in the results are obtained via 5 independent runs. In Appendix D.3, we also investigate the time cost of calculating our policy space diversity. More details for the environments and hyper- parameters are given in Appendix E
report the win rate between the final agents.
AlphaStar888 is empirical game generated from the process of solving Starcraft (50] which contains a payoff table for 888 RL policies. be viewed as a zero-sum symmetric two-player game where there only one state $g- In so, there are 888 legal actions. Any mixed strategy is discrete probability distribution over the 888 actions. Hence, the distance function in Equation [4 for AlphaStar888 reduces to the KL divergence between 888-dim discrete probability distributions.
In Figure [ we can see that PSD-PSRO more effective at reducing both the exploitability and PE than other methods.
Non-Transitive Mixture Game consists of equally-distanced Gaussian humps on the 2D plane. Each strategy can be represented by a point on the 2D plane, which is equivalent to the weights (the likelihood of that point in each Gaussian distribution) that each player puts on the humps. The optimal strategy is to stay close to the center of the Gaussian humps and explore all the distributions. In Figure 2 we show the exploration trajectories for different methods during training, where PSRO and PSRO, get trapped and fail in this non-transitive game. In contrast, PSD-PSRP tends to find diverse strategies and explore all Gaussians. Also, the exploitability of the meta NE of the final population is significantly lower in PSD-PSRO than others.
Ledicc Poker
Leduc Poker
253/
PS30
PSRO
S-PSAO
P-PSAO
IN
Rop
1250
Eakcodos 12640
Figure 3: (a): Exploitability of the meta NE, (b): PE of the joint population.

---

Ledue Poker is a simplified poker 446, where the deck consists of two suits with three cards in each suit. Each player bets one chip as an ante, and single private card is dealt to each player. Since DPP-PSRO cannot scale to the RI. setting [2 and the code of ED&RD--PSRC for complex games is not available, we compare PSD-PSRO only to P-PSRO, PSRO, and PSRO. As demonstrated in Figure 3 PSD-PSRO is more effective at reducing both the exploitability and PE.
PSRO
PSRO,N
P-PSRO
PSD-PSROOOURS)
PSRO
0.61310.019
0,46910.034
0.42210.02
PSRO,N
0.387+0.019
0.412+00030
0.358
P-PSRO
0.531+0.033
0.588
0.370+F0.031
PSD-PSRO(OURS)
0.578
0.642=0.019
0.630_0.031
Table 1: The win rate of the row agents against the column agents on Goofspiel.
Goofspiel is commonly used as large-scale multi-stage simultaneous move game. Goofspiel features strong non- transitivitty, as every pure strategy can exploited by a simple counter-strates compare PSD-PSRO with PSRO, P-PSRO, and PSRO,, on Goofspiel with 5 point cards and 8 point cards settings. In the game with point cards setting, due to the relatively small game size, we can calculate the exact exploitability. We report the results in Appendix [.I] in which we see that PSD-PSRO reduces the exploitability more effectively than other methods. In the game with 8 point cards setting, the game size is too large show exact exploitability for each iteration. In this setting, we provide a comparison among final solutions produced by different methods. We report the win rate between each two methods in Table T where existing methods with a 62% win rate on average.
We
see that PSD-PSRO consistently beats
Conclusions and Limitations
In this paper, we point out major and common weakness of existing diversity metrics in previ- ous diversity-enhaneing PSRO variants, which is their goal of enlarging the gamescape does not necessarily result in better approximation to a full game NE. Based on the insight that a larger NE), we develop new diversity metric (policy
PH means lower PE (a better approximation space diversity) that explicitly encourages the enlargement of a population's 's PH. We then develop practical method to optimize our diversity metric using only state-action samples, which is derived based the Bregman divergence the sequence form of policies. We incorporate our diversity metric into the BR solving in PSRO to obtain PSD-PSRO. We present the convergence property of PSD-PSRO, and extensive experiments demonstrate that PSD-PSRO is significantly more effective in approximating a NE than tfate-of-the-a PSRO variants.
The diversity regularization term À in PSD-PSRO plays an important role in balancing the 'exploita- tion' and 'exploration' in terms of enlarging the PH to approximate a NE. In this paper, other than showing that different problems have different optimal settings of X, we have not discussed about the guidance of choosing optimally. Although there has been related work on how adapt a diversity regularization term using online bandits [39], future work is still needed on how our policy space diversity could benefit the approximation of a full game NE most. Another interesting direction of future work is to extend PSD-PSRO to larger scale games, such as poker 5 Mahjong [14] and dark chess [52].
References
[1] Yu Bai, Chi Jin, Song Mei, and Tiancheng Yu. Near-optimal learning of extensive-form games with imperfect information. In International Conference Machine Learning, pages 1337-1382. PMLR, 2022.
[2] David Balduzzi, Marta Gamelo, Yoram Bachrach, Wojeiech Czamecki, Julien Perolat, Max Jaderberg, and Thore Graepel. Open-ended learning in symmetric zero-sum games. International Conference on Machine Learning, pages 434-443. PMLR, 2019.
[3] David Balduzzi, Sebastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel. The mechanics of n-player differentiable games. International Conference on Machine Learning, pages 354-363. PMIR, 2018.
[4] George W Brown. Iterative solution of games by tictitious play. Act. Anal. Prod Allocation, 13(1)3374. 1951.
10

---

[5] Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359663374):418-4424 2018.
[6] Ozan Candogan, Ishai Menache, Asuman Ozdaglar, and Pablo A Parrilo, Flows and decompositions of games: Harmonic and potential games. Mathematics of Operations Research, 36(3):474-503, 2011.
[7] Frank H Clarke. Generalized gradients and applications. Transactions of the American Mathematical Society, 205:247-288 262, 1975.
[8] Antoine Cully, Jeff Clune, Danesh Tarapore, and Jean- Ban-BBptiste Mouret. Robots that can adapt like animals. Nature, 521(7553):033--07 2015.
[9] Wojeiech Czameeki, Gauthier Gidel, Brendan Tracey. Karl Tuyls, Shayegan Omidshafiei, David Balduzzi, and Max Jaderberg. Real world games look like spinning tops. In Advances in Neural Information Processing Systems, volume 33, pages 17443-17454, 2020.
[10] Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without a reward function. In International Conference on Learning Representations. 2018.
[11] Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Optimistic regret minimization for extensive- games via dilated distance gennraainggnnni functions. Advances in neural information processing systems, 32, 2019.
[12] Xidong Feng, Oliver Slumbers. Ziyu Wan, Bo Liu, Stephen McAleer, Ying Wen. Wang, and Yaodong Yang. Neural auto-curricula in two-player zero-sum games. In Advances in Neural Information Processing Systems, volume 34, pages 3504-3517, 2021.
[13] David Fogel. Evolutionary computation: toward a new philosophy of machine intelligence. John Wiley & Sons, 2006.
[14] Haobo Fu, Weiming Liu, Shuang Wu, Yijia Wang, Tao Yang. Kai Li, Junliang Xing, Li, Bo Ma. Qiang Fu, et al. Actor-critic policy optimization a large-scale imperfect-informan game. In International Conference on Learning Representations, 2021.
[15] Haobo Fu, Ye Tian, Hongxiang Yu, Weiming Liu, Shuang Wu, Jiechao Xiong, Ying Wen, Kai Li, Junliang Xing, Qiang Fu, et al. Greedy when sure and conservative when uncertain about the opponents. In International Conference on Machine Learning, pages 6829-6848. PMLR, 2022.
[16] Justin Fu, Katie Luo, and Sergey Levine, Learning robust rewards with adversarial inverse reinforcement learning. arXiv preprint
2017.
[17] Drew Fudenberg and David K Levine. Consistency and cautious fictitious play. Journal of Economic Dynamics and Control,
1995.
[18] Johannes Heinrich, Mare Lanctot, and David Silver. Fictitious self-play in extensive-form games. In International conference on machine learning, pages 805 813. PMLR, 2015.
[19] Johannes Heinrich and David Silver. Deep reinforcement learning from self-play in imperfeectinformaaiion games. arXiv preprint 103301160..,,,,, 2016.
[20] Jomathan Ho and Stefano Ermon. Generative adversarial imitation learning. Advances in neural information processing systems, 29, 2016.
[21] Samid Hoda, Andrew Gilpin, Javier Pena, and Tuomas Sandholm. Smoothing techniques for computing nash equilibria of sequential games. Mathematics of Operations Research, 3542)4994-512, 2010.
[22] Zhang- Wei Hong, Tzu-Yuu Yun Shann, Shih-Yang Su, Yi-Hsiang Chang. Tsu-Jui Fu, and Chun-V Yi Lec. Diversity-driven exploration strategy for deep reinforeement learning. In Advances in neural information processing systems, volume 31, 2018
[23] Max Jaderberg, Wojciech M Czamecki, lain Dunning, Luke Marris, Guy Lever, Antonio Garcia Castaneda, Charles Beattie, Neil C Rabinowitz. Ari S Morcos, Avraham Ruderman, et al. Human-level performance in 3d multiplayer games with population-based reinforcement learning. Science, 364(6444)),59-8655 2019.
[24] Seyed Kamyar Scyed Ghasemipour, Richard Zemel, and Shixiang Gu. A divergence minimization perspective on imitation learning methods. arXiv e-prints, pages arXiv-1911, 2019.
[25] Saurabh Kumar, Aviral Kumar, Sergey Levine, and Chelsea Finn. One solution is not all you need: Few-shot extrapolation via structured maxent rl. In Advances in Neural Information P Processing Systems, volume 33, pages 8198- 8210, 2020.

---

[26] Mare Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. A unified game-theoretic approach to multiagent reinforcement learning. In Advances in neural information processing systems, volume 30, 2017.
[27] Chung-War Wei Lee, Christian Kroer, and Haipeng Luo. Last-iterate convergence in extensive-form games. Advances in Neural Information Processing Systems, 14144993--405, 2021.
[28] Joel Lehman and Kenneth O Stanley. Abandoning objectives: Evolution through the search for novelty alone. Evolutionary compulation, 19(2):189 223, 2011.
[29] Siqi Liu, Luke Marris, Daniel Hennes, Josh Merel, Nicolas Heess, and Thore Graepel. Neupl: Neural population learning. arXiv preprint urXiv:2202.07411 2022.
[30] Weiming Liu, Haobo Fu. Qiang Fu, and Yang Wei. Opponent-limited online search for imperfect information games. In International Conference on Machine Learning. PMLR, 2023.
[31] Weiming Liu, Huacong Jiang, Bin Li, and Houqiang Li. Equivalence analysis between counterfactual regret minimization and online mirror descent. In Proceedings of the 39th International Conference on Machine Learning, volume 162. pages 13717-13745, 2022.
[32] 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 Processing Systems, volume 34, pages 941-952, 2021.
[33] Zongkai Liu, Chao Yu, Yaodong Yang, Zifan Wu, Yuan Li, et al. A unified diversity measure for multiagent reinforcement learning. In Advances in Neural Information Processing Systems, 2022.
[34] Andrei I Lupu, Brandon Cui, Hengyuan Hu, and Jakob Foerster. Trajectory diversity for zero-shot coordina- tion. In International Conference on Machine Learning, pages 7204-7213. PMLR, 2021.
[35] Odile Macchi. The fermion process model of stochastic point process with repulsive points. In Transactions of the Seventh Prague Conference on Information Theory, Statistical Decision Functions, Random Processes and of the 1974 European Meeting of Statisticians, pages 391 991-398. Springer, 1977.
[36] 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 202488, 2020.
[37] Stephen McAleer, Kevin Wang, Mare Lanctot, John Lanier, Pierre Baldi, and Roy Fox. Anytime optimal psro for two-player zero-sum games. arXiv preprint arXiv:2201.0777 2022.
[38] H Brendan McMahan, Geoffrey J Gordon, and Avrim Blum. Planning the presence of cost functions controlled by an adversary. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pages 536-543, 2003.
[39] Jack Parker-Holder, Aldo Pacchiano, Krzysztof Choromanski, and Stephen J Roberts. Effective diversity in population based reinforcement learning. In Advances in Neural Information Processing Systems, volume 33, pages 18050-18062 2020.
[40] Zhenghao Peng, Hao Sun, and Bolei Zhou. Non-local policy optimization via riversity collaborative exploration. arXiv preprint arXiv:2006.07781, 2020.
[41] Nicolas Perez-Nieves, Yaodong Yang, Oliver Slumbers, David H Mguni, Ying Wen, and Jun Wang. Modelling behavioural diversity for learning in open-ended games. In International Conference on Machine Learning, pages 3514-8524, PMLR, 2021.
[42] Justin Pugh, Lisa Soros, and Kenneth O Stanley. Quality diversity: A new frontier for evolutionary computation. Frontiers in Robotics and Al, page 40, 2016.
[43] John Schulman, Sergey Levine, Pieter Abheel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. International conference on machine learning, pages 1889-1897. PMIRR 2015.
[44] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 2017.
[45] Max Smith, Thomas Anthony, and Michael Wellman. Iterative empirical game solving via single policy best response. In International Conference on Learning Representations, 2020.
[46] Finnegan Southey. Michael P Bowling, Bryce Larson, Carmelo Piccione, Neil Burch, Darse Billings, and Chris Rayner. Bayes' bluff: Opponent modelling in poker. arXiv preprint 1rXiv:1207.1411, 2012.
12

---

[47] Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
[48] 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
[49] Zhenggang Tang, Chao Yu, Boyuan Chen, Huazhe Xu, Xiaolong Wang, Fei Fang. Simon Shaolei Du, Wang. and Wu. Discovering diverse multi agent strategic behavior reward randomization. In International Conference on Learning Representations, 2020.
[50] Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki. Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-ages agent reinforcement learning, Nature, (557788):330-3544 2019.
[51] Shuang Wu, Jian Yao, Haobo Fu, Ye Tian, Chao Qian. Yaodong Yang. Qiang Fu, and Yang Wei. Quality- similar diversity via population based reinforcement learning. In The Eleventh International Conference on Learning Representations, 2022.
[52] Brian Zhang and Tuomas Sandholm. Subgame solving without common knowledge. Advances in Neural Information Processing Systems, 34:23993- 14-23993-240044 2021.
[53] Ming Zhou, Jingxiao Chen, Ying Wen, Weinan Zhang, Yaodong Yang, Yong Yu, and Jun Wang, Efficient policy space response oracles. arXiv preprint arXiv: 00633, 2022.
[54] Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information, In Advances in neural information processing systems, volume 20, 2007.
13

---

A
Notation
We provide the notation in Table 2
Table Notations
Notation
Mcaning
Extensive Form Games
.V
N (1,2); of players
of information states
8
s E S; state node
A(s)
set of actions allowed to be performed at state player function
P
i Ms player players except
8
player i's information state
S,
S; {s E (s) = i): set of player's information state
A,
A; = Usss; set of player i's actions
player i's behaivoral strategy
(m, strategy profile
u4
(x( (M, TT+): - the payoff for player
(x(x..)
(TR(T-)) = arg max, eass, u(m, T-1); best response for player i against players -i
{(x)
E(r) & ExeN mmax.. u. (.( x))) - ux(T,, T=)]: exploitability for policy æ
Meta Games
i/
i E {1, 2); player i players except i j-th policy any policy player
x/ / m.
π (2): policy
I1:
11: == " }: policy set for player
IT IT, [T; joint policy
a,
a, E An, meta-policy over IT;
(21, meta-policy
Mn..n.
(M.,.n.)). == ux( x-.): player payoff table the meta mnta-gamess (1l,, 11..)
the full set of all possible mixed strategies of player
H(II.)
H(II.) = {2, 8, [8, 2 0, Ej {3 = 1); Policy Hull of II, = (n. . m
P((s))
PI 11_.) m. Mn... II _ Reelttie Population Performance for player
PE())
PE(LI) E maxn: go, PII,,, 11:)): Population Exploitability
[T = (, o,m,
0, a 1. m, M M...u-pp... gamescape of II;
PSRO PSD-PSRO Training
11
II = (m....., n. J: the policy set of player at the 1-th iteration in PSRO of Ang; the meta-policy of player at f-th iteration in PSRO
of
p(-)
policy representation
æ; E X. S [o, [|(S sequence form representation policy trajectory from the initial state to (s, a)
a.
T(s,a)
Ba, (m
(s)[(((((()
Bregman divergence between (.(s) and n((s)
Div())
diversity the policy specified in different methods distance function
dist(;
diversity weight
KL
Bullback-Leibler divergence
B Theoretical Analysis
B.1 Derivation of Bregman Divergence
We define the Bregman divergence the sequence-form representation of the policies. Given strictly convex function d defined on x.A, Bregman divergence is defined
14

---

Ba(x;](={) d(x;) d(z,)
(Vd(z)), z/).
(18)
for any 2; x E X. Intuitively, Bregman divergence is the gap between d(æ,) and its first-order approximation at x. It is non-negative (zero is achieved if and only if æ; = xx) and strictly convex in its first argument. So, it can be used to measure the difference between æ; and æ;. Examples of Bregman divergence include the Squared Euclidean distance, which is generated by the l2 function, and the Kullback-Leibbe (KI.) divergence, which is generated by the negative entropy function. For sequence-form policies, we use the dilated Distance-Geenerating Function (dilated DGF)
31
2 (s)
d(x;)
Σ
a),s,
(19)
s,0ES;XA,
where 3, > 0 is a tlyer-paramette and d, is strictly convex function defined on A(s)), for example, the negative entropy function. proven that for the dilated DGF (Lemma D.2 in 31 ) we have the Bregman divergence
(s(s) (s)ll
<1(s) (
Ba(x;||<())
E S.0.S.XA.
x,(s,,)8,Bb,
(20)
|
The result allows us to compute the Bergman divergence using the behavior policy instead of explicitly using the sequence-fon coruence-form representation, which is prohibited in large- scale games. Formally, we define the distance two policies mi n/ as
dist(m;, m() = (a( =
E
II (,
<((ā[T,) B. B,Ba, (T(())))())))
(21)
X;
B,2 Proof of Proposition 3.2
Proof. Recall that the PE of joint policy set IT in two-player zero-sum games can be written into
PE(IT)
Σ
max Pi(IT,, II_;)
1=1, nr
max Pi( 112) IES
min m
Pi 112),,
since (_,(II';: 111) = (I,, I12).
1. We can check this property directly, since
PE(II)
max P,(1I,, 112) I1Ss.
min Pi(l,, I12))
(P, (I, I12) (II, II)) =
2. We first note that H(II.) x H(ll) C H(U)) x H(IIL,) means H(II,) C H(I))) and H(II)) C HIIII"))
H(l1)) S. H(I))) suggests that V Q. we have P,( 11,2 2 P.(4, I1), which is property of relative population performance (2]. Take the maximum for both sides, we have,
max P,( II:) > max Pi( I) $.
(22)
2.50
Similarly, using the condition H(Il,) S H(11)), we have,
min
PI(II, 4_:) : < min P.U,, $_.)
(23)
$_/CO_ C
.0.0__
Combining Equation 22 and
23
we obtain PE(II) > PE(II')
15

---

3. By the monotonicity of PE, we have
PE(MT (P, IT-)) ((
(24)
Since II_; ( contains only policy, by the definition of relative population performance, we have,
P.(S4, (m-1)) u(BR( PP u( BR(T.)
(25)
Substituting Equation 25 into Equation 24 we obtain
PE(II) = (TT)
(26)
4. By Equation 24 and the definition of the relative population performance, there exists NE (0t, T-i) in game Mn, and NE (m, a-i) in game Mu,00,, s.t.
PE(II) (u(o,, T-I) u-1),
By the definition of NE, we have.
PE(II) 2 xfE
max u( T-i) min
u(TT; x x'_)))
{(T)
(27)
We now prove (T,, TT)) is also the least exploitable policy in the joint policy set. V x (T/, mL,) 11, x 1I_4. , we have,
E(x) = PE(I)) & PE([T} x (T'+;) E(x')
(28)
where the inequality is from the monotonicity of PE. Hence, (T, T-:) is the least exploitable policy in the Policy Hull the population.
5. Necessity If (a7, a the NE of the game, we can regard the (ot) and {a-x} as the populations which contain single policy. Then by property 2, we have,
PE( < PE((o)} x {oi,))
(Pils (o".)) - PP((f))),
2 (u(o, o",) ulo;; o",)) =
Note that by property 1, we have PE(II) 2 0, so we have (1I = 0. Sufficiency Using the conclusion from 3, It is easy check the sufficiency. If PE(T) there exists a (a,, -i) s.t. E(r) = 0, which means is the NE the game.
B.3 Proof of Proposition 3.
Proof. Recall that at each iteration i, the PSRO calculates the NE (of, of,)) of the meta-game Mugms, then adds the new policy x² = (BR(o',), BR(a()) to population.
If PE(II)) >> 0, then by the second property in Proposition 3.2 we know the population does not contain the NE of the game. Therefore, since (af, of E II' is the NE of the full game, which means at least one of the conditions holds; (1) BR(²",) & H(I);;; (2) BR(af) & H(II',), which suggests the enlargement of the Policy Hull.
In finite games, since the PSRO adds pure BR each iteration, this Policy Hull extension stops at some iteration, saying T, in which case we have BR(aT.) E H(II)) and BR(a)) E H(IL.) (by above analysis). Let (TT+1 , (BR(o BR(o))) )))), claim that (,² T+1 - is
16

---

the NE of the whole game. To see this, note that (o? ,2,,) is the NE of the game Mn² _ and T+1 H(II))) ) hence we have,
u ,o 2 u( +1 ,,)
(29)
On the other hand, since m. T+1 is the BR o have.
"( T+1 -
o_,).
(30)
Combining Equation 29 and 30 we obtain ui T+1 o
ulo of.). which suggests of is also
the BR of o_... Similarly, we can prove that o is the BR of of" and hence (o? o ;) is the NE of the game.
Finally, by the fourth property in Proposition 3.2 we have PE(IIT) O.
B.4 Proof of Proposition 4.3
This is an intermediate result in the proof of 3.3 (Appendix B.3)
B.5 Proof of Theorem 34
Proof. We prove this theorem by providing the counterexamples. Let's first focus on the following
two-player zero-sum game:
R
P
S
R
-1
1
0
-1
S
-1
1
0
(31)
R²
-1
1
p
1
-1
S'
-1
1
The game is inspired by Rock- Dack-Paper-Scissors. We add high-level strategies P", player in the original R-P-S game. The high-level strategy can beat the low-level strategy with the same type.
Let 11, {S, R', P') and II_, {R. 1 R + JPP, where 1 + P means playing [R, P. with
probability 1 d. The payoff matrix Mn. TI is
R
1 +
2
LP
S
-1
0
R'
1
-1
0
(32)
pr
It is in player i'turn to choose his new strategy. Considering two candidates no S' and nï, fR + HR' (There are many choices for कद to construct the counterexample, just take one for example).
The payoff of π. against IT_; is (- 0), the same the first row in Mn, The payoff of x? is (1 -1-11 }), which is out of the gamescape of II,
Denote IT! II, U {m.) IT IT, {m?). By the analysis above, we have
GS( & (8(1I)
(33)
Hence, to promote the diversity defined on the payoff matrix and aim to enlarge the gamescape 2 41,
we should choose nद to add. However, in this case, we show adding m is more helpful to decrease PE.
Denote II II: I1, and II2 11? x II by Equation 24 and a few calculation, we have,
PE(II-) PE(II") 1o--pppz P 2 + P(I)) 0.17 0.10 0, (34)
17

---

i... P < (II We can see that adding new policy following the guidance of enlarging gamescape may not be the best choice decrease PE.
Back to the Proposition 3.4, since we have found an example that,
G :) & CS I_) but PE(IT") PE(IT()
(35)
hence,
GS & (S(T))LL))) PE(II) 2 PE(II")
(36)
Rewrite the example in Equation 35| we have,
PE(IT") > PE((TT)) but GS(M)) 2 (S
(37)
Rename the superscripts (exchange the identity 1, in the superseript), we obtain.
(E( 2 (E * ( & GS(U))LLL
(38)
Combine Equation 36 and 38
complete the proof.
Remark We offer another example in symmetric game, proving that this proposition is also valid in this type of game.
A
B
C
D
E
A
0
-1
0.5
-1
4
B
0
0.5
4
C
0.5
-0.5
0
4
(39)
0
D
-4
E
4
-4
0
Current policy set IT, {4,
B}. the payoff is
A
B
A
0
-1 0
(40)
Considering m. = C, = D. the payoff of n! = C againstt IT,, is (0.5, -.5), contained in
GS(MT,[TT:;) :), while the payoff of oद D against IT is (1, which is out of (TLL).
Denote II! II, U ( 11 = 11, U (m²). II = 11, II,, and IIf = 11 x II.4, we have
GS( S G However,
PE(IT") PE(IT)) 1
0.17 - <<0
(41)
Hence, similar to the above analysis, we can prove the Proposition 3.4 in symmetric games.
B.6 Proof of Theorem
Proof. Similar to Appendix B.3 of PSRO, if PE(IT') >> 0, then from Appendix B.3 we know that at least one of the conditions holds: (1) BR(a & H(T)): (2) BR(af) & H(II' J. Without loss of generality, we assume
denote the meta-strategy at iteration as (af o².)) At iteration t
BR(OL)) $ H(U)).
(42)
Then V và E H(I))) and >
ul6;, 0- + min E (LLO) **EX(U))
=u(o,,0-,)00
<u(BR(o'))o'))
<u(BR(o')))
X min Ex (TT (s:)) +(E)()))
(43)
where the first equation because à; H(TT() and the last two inequalities is due to the definition of BR and Equation 42 respectively.
18

---

Algorithm PSD-PSRO
Initial policy sets I1: II: Compute payoff matrix M Mn;. m
Input:
Initialize meta policies of ~ UNIFORM(TT) for r in {1,2, ...) do for player i E {1,2) do
Initialize n, = मं and sample policies (= from Policy Hull IIŞ for many episodes do
Sample - ~ o'_ and collect the trajectory 7 by playing π, against T-
Discount the terminal reward u( TT+) to each state as the extrinsic reward
Discount R to each state as the intrinsic reward 12
Store (s, a, s',, to the buffer, where s' is the next state and r1 72 Estimate the gradient in Equation 17 with the samples in the buffer and update m
end for t
[+1
T. and I
end for
Compute missing entries in Mng...
Compute stta-strategies (of ++ _or)) from Mnj.n.
end for
Output: current meta-strategy for each player.
Table 3:
The exploitability x 100 for populations generated by PSD with different diversity weights in Non-transitive Mixture Games. The standard error calculated by running 5 experiments.
3
EXP
40.88 2.18
2.81 0.66
1.72 + 0.54
2.87 + 0.70
3.73 0.77 4.31 0.67 8.22 1.73
know that any policy in M(II)) will not be considered the optimal solution since they are dominated by at least one of the policy that out of ((II)) i.e., the BR. Hence, before PE reaches O, solving Equation 14 will find policy not in H(III) which guarantees the enlargement of the Policy Hull. Once we can not enlarge the Policy Hull by adding the optimal solution in Equation [4] the PE of the Policy Hull must be otherwise the optimal solution will be outside of the Policy Hull.
From Equation
43
in Equation| 14
C Algorithm for PSD-PSRO
We provide the algorithm for PSD-PSRO in Algorithm 1 which generates the algorithm of PSRO to incorporate the estimation of the diversity in Equation
D Additional Study
D.1 PE on Ledue
In Figure
4
report the exploitability of the meta NE on Goofspiel with 5 point cards setting.
D.2 Ablation Study Diversity Weight
We conduct the ablation study on the sensitivity of the diversity weight À on the Non-Transitive Mixture Game and Ledue Poker. In Table and Table g population against different diversity weights in respectively. We can see that the À can significantly affect the training convergence and the final exploitability. A large small À can lead to high exploitability. This suggests that properly combing the BR (implicitly enlarges the Policy Hull) and PSD (explicitly enlarges the Policy Hull) critical to improving the efficiency at reducing the exploitability.
we show the exploitability of the final Mixture Game and Leduc Poker,
19

---

Goofspiel (5 point cards)
PSRO
P-PSRO
PSRO-IN
PSD-PSRO (Ours)
Exploitabiitty
0.
100
250
Episodes (1e4)
Figure 4: Exploitability on Goofspicl (5 point cards).
Table 4: The exploitability for populations generated by PSD with different diversity weights in Ledue Poker. The standard erorr is calculated by running experiments.
0.1
0.5
2
5
EXP
0.590 0.017
0.403 +: 0.027
0.356 +: 0.012
0.398 0.030
0.412 0.042
0.664 + 0.062
D.3 The Visualization of PH
demonstrate the expansion of PH the Disc game 2 represented by point in the circle. Due to the linearity in the payoff function, mixed strategy is equivalent a pure strategy and thus can be equivalently visualized. Figure 5 the expansion of PH on the Disc game [2]. It demonstrates that PSD-PSRO is more effective than other PSRO variants enlarging the PH.
In Disc game, each pure strategy is
D.4 Time Consumption in PSD-PSRO
We experiment Ledue poker to estimate the time portion of different parts in algorithm PSD-PSRO. We can see from Table that the majority of time in PSD-PSRO is in BR solving and computing the payoff matrix. which is shared by PSRO and all its variants. The time spent calculating our diversity metric not significant, which accounts for 7.9% computational time.
E Benchmark and Implementation Details
E.1 AlphaStar888
AlphaStar888 an empirical game generated from the process of solving Starcraft (50] which contains payoff table for 888 RL policies. The occupancy measure is reduced the action distribution as the game can be regarded as single-state Markov Game. We choose diversity weight be 0.85 in this game.
E.2 Non-Transitive Mixture Game
This game consists 7 equally-distanced Gaussian humps on the 2D plane. We represent each strategy by a point on the 2D plane, which is equivalent to the weights (the likelihood of that point in each Gaussian distribution) that each player puts the humps. The payoff of the game which contains
20

---

Iter5
Iter10
Iter15
Iter20
PSO PSR0
DPP PSRO
iter5
Iter10
Iter15
iter20
Iter5
Iter10
Ite/15
Iter20
Iter5
Iter10
iter15
iter20
Iter5
Iter10
iter15
Iter20
PSRC-I Unit Cirds
Figure 5: Equivalent visualization of PH of different methods across iterations in the Disc game
both non non-transitive and transitive components is गं ST + 2
E
(T x²,), where
0
1
1
-1
-1
1
-1
0
1
1
S
1
-1
-1
0
I
-1
-1
-1
0
I
-1
-1
-1
1
1
1
-1
-1
-1
0
We choose diversity weight À to be 1.9 in this game.
21

---

Table 5: Time Consumption in PSD-PSRO on Leduc poker
MAIN PART PSD-PSRO
PERCENTAGE
COMPUTE NE OF THE META-GAME COMPUTE THE APPROXIMATE BR
0.9%
59.9%
COMPUTE THE EXTRA DIVERSITY METRIC
7.9%
COMPUTE THE PAYOFF MATRIX
31.3%
E.3 Leduc Poker
Since the DPP-PSRO needs evolutionary updates and cannot scale to the RL setting, and the code for BD&RD- PSRO complex games, where f-divergence occupancy measure is approximated using prediction errors of neural networks, is not available, we compare PSD-PSRO with P-PSRO, P and PSRO in this benchmark. We implement the PSRO framework with Nash solver, using PPO as the oracle agent.
are shown in Table
Table 6: Hyperparameters for Ledue poker
Hyperparameters
Value
Oracle
Oracle agent
PPO
Replay buffer size
10a
Mini-batch size
512
Optimizer
Adam
Learning rate
3 x 10
Discount factor (?)
0.99
Clip
0.2
Max Gradient Norm
0.05
Policy network
MLP (state_dim- (iaaae__im-255--5--55-----
Activation function in ML.P
ReLu
PSRO
Episodes for each BR training
x 104 Nash
meta-policy solver
PSRO,N
Episodes for each BR training
2 x 104 rectified Nash
meta-policy solver
P-PSRO
Episodes for each BR training
2 x 104 Nash 3
meta-policy solver
number of threads
PSD-PSRO
Episodes for each BR training
x 10a
meta-policy solver
Nash
diversity weight À
0.1
E.4 Goofspiel
In game theory and artificial intelligence, Goofspiel is commonly used as an example of multi-stage simultaneous move game. two-player Goofspiel, each player has one suit of cards, which is ranked A (low), 2, ... 10, J. Q. K (high). Another suit of cards serves the prize (competition cards). Play proceeds series of rounds. The players make sealed bids for the top (face up) prize by selecting card from their hand (keeping their choice secret from their opponent). Once these cards are selected, they are simultaneously revealed, and the player making the highest bid takes the competition card. tied, the competition card is discarded. The cards used for bidding discarded, and play continues
22

---

with new upturndd prize card. After 13 rounds, there are no remaining cards and the game ends. Typically, players earn points equal the sum the ranks of cards won (i.e. A is worth one point, is worth two points, etc., J 11, Q 12, and K 13 points). Goofspiel demonstrates high non-transitivity. Any pure strategy this game has a simple counter-strategy where the opponent bids one rank higher, or low as possible against the King bid. As an example, consider the strategy of matching the upturned card value mentioned in the previous section. The final score will be 78 with the K being the only lost prize. we focus on the simple versions of this game; goofspiel with point cards and point cards settings.
Similar to the setting in Leduc poker, we compare PSD-PSRO with P-PSRO. PSRO,N and PSRO in this benchmark. We implement the PSRO framework with Nash solver, using DQN the Oracle agent. We use Linear Programming to solve NE from the payoff table. As the game size of Goofspiel larger than Leduc poker, we improve the capacity of the model by setting the hidden dimension in MLP to be 512 and the episodes for each BR training to be 3 x 10 Other settings are similar to Ledue poker in Table
23


Reviews:
[{"review_id": "Fqi9b039Ac", "reviewer": "Reviewer_6jtZ", "summary": "This paper studies how to promote policy diversity in two-player zero-sum games to better converge to a Nash Equilibrium (NE) under the algorithm framework of policy-space response oracles (PSRO). While previous works propose various diversity metrics to enlarge the gamescape, this paper shows that the enlargement of gamescape does not necessarily contribute to a better approximation of NE. Therefore, the authors propose a new diversity metric in policy space, namely KL divergence, to alleviate this issue. Theoretical results show that the proposed algorithm, PSD-PSRO, enjoys good convergence properties to NE. Experiment results in several common benchmarks for PSRO demonstrate the strong empirical performance of PSD-PSRO.", "questions": "+ I'm not quite familiar with the notation in two-player zero-sum games. In Eq.11, xi seems to be the occupancy measure over the entire state-action space. Why is the state transition probability omitted here?\n\n+ In line221 the authors say that Eq.11 is independent of environment dynamics, but why? Eq.11 involves the trajectory \\tau.\n\n+ From my point of view, the derivation process from line215 to line234 tells the reader that KL divergence essentially measures the differernce of policies w.r.t. the sequence representation, but in my opinion this is not that straightforward. If this is generally true in RL (or two-player zero-sum games), I think there should be previous works illustrating this point as a theorem. In line230, why \\beta_s can depend on the opponent policy? Depending on the opponnet policy is intuitively true, but I didn't see any theoretical evidences that it should be this way. Why does setting \\beta_s in this way not changing the property that Eq.13 still measures policy differences in terms of sequence representation?\n\n", "limitations": "The authors have addressed several limitations in Sec.7. I didn't see any additional major limiatations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "+ The main logic and presentation of this paper is very clear. Personally, I like the writing paradigm of first analyzing drawbacks of previous approaches, motivating the algorithm, and then showing strong theoretical and empirical results with the proposed algorithm.\n\n+ This paper points out an important issue of the main-stream diversity-motivated PSRO algorithms, which in my opinion is a solid contribution to the community. To resolve this issue, the proposed algorithm is quite simple (with KL divergence) but effective.", "weaknesses": "+ The defined diversity metric in Eq.14 is simple in form but very complex in derivation (from line215 to line234). The fancy derivation process essentially prevents readers from obtaining the algorithm insights. I will ask detailed questions in the next section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks very much for the review and the questions. We believe that there may be some misunderstandings in L215-L234.  We list your questions below and respond to them in the following. If there is anything still unclear, please bright it up.  \n\n- **Q1**: In Eq.11, $x_i$ seems to be the occupancy measure over the entire state-action space. Why is the state transition probability omitted here?\n- **Q2**: In line221 the authors say that Eq.11 is independent of environment dynamics, but why? Eq.11 involves the trajectory $\\tau$.\n- **Q3**: From my point of view, the derivation process from line215 to line234 tells the reader that KL divergence essentially measures the difference of policies w.r.t. the sequence representation, but in my opinion this is not that straightforward. If this is generally true in RL (or two-player zero-sum games), I think there should be previous works illustrating this point as a theorem. \n- **Q4**: In line230, why $\\beta_s$ can depend on the opponent policy? Depending on the opponent policy is intuitively true, but I didn't see any theoretical evidences that it should be this way. Why does setting \\beta_s in this way not changing the property that Eq. 13 still measures policy differences in terms of sequence representation?\n\n**Responses for Q1-Q2**:\n\n$x_i$ in Eq 11 is the sequence form representation (which has been widely used for imperfect-information games [1-5] ) of a policy $\\pi_i$. The joint occupancy measure is another representation of the policy $\\pi_i$. The occupancy measure is a probabilistic distribution over the entire state-action space (the sequence form is **not** a probabilistic distribution). The occupancy measure of $\\pi_i$ depends on $\\pi_i$, the opponent policy, and the environment dynamics. In contrast, the sequence form of $\\pi_i$ only depends on $\\pi_i$: the opponent policy and the environment transition probability are deliberately omitted in Eq 11 when traversing a trajectory $\\tau$ (because of perfect-recall, there is a unique $\\tau$ that leads to (s,a)) that leads to the state-action pair (s,a). **By definition**, the right term in Eq11 only takes the product of the probability that player $i$ chooses an action along **his** infosets (states) in $\\tau$, i.e., on $(\\widetilde{s}_i, \\widetilde{a}) \\in \\tau(s, a)$.\n\nActually, our diversity metric is defined in Eq 10, which calculates a distance **between the current policy $\\pi_i$ and the policy hull $\\mathcal{H}(\\Pi_i)$**. Section 4.2 and Appendix B.1 basically state **why&how** we encode a policy using the sequence form and how we employ the Bregman divergence on the sequence form to deduce a clean, practical, manageable, state-action based diversity objective function (Eq 14). To summarize, Eq 14 is a practical and theoretically justified implementation of Eq 10. \n\n\n\n**Responses for Q3**:\n\nAs we know, Bregman Divergence is defined with a strictly convex function $d$ in Eq 16. \nWhen $d$ is a dilated Distance-Generating Function (DGF) [1,2] as defined in Eq 17, a recent theorem (Lemma D.2 in [3]) states that the Bregman Divergence of two policies can be transformed to a weighted sum of the Bregman divergence on the action probability distribution in a state (Eq 18).  The same theorem in simpler forms (when $d_s$ is set to a negative entropy function) have also been proven (or used) in  [4,5].  This is crucial, since it enables a practical method to calculate our Bregman Divergence **using only state-action samples**.\n\nIn our work, we choose $d_s$ to be a negative entropy function (one of the dilated DGF). In this situation, $B_{d_s}$ is the KL divergence. \n\n\n\n**Responses for Q4**:\n\nAccording to the dilated Distance-Generating Function (Eq 17), $\\beta_s >0$ is a state dependent parameter. As a result, setting $\\beta_s$ as been done in Line230 can be viewed as a state dependent parameter. \n\nIn line230, making $\\beta_s$ depend on the opponent policy like what we did can simplify Eq 12 to Eq 13 (avoid importance sampling). Why simplification? Because we need a practical and easy way to optimize our diversity. The choices ($\\beta_s$, $d_s$) above lead to a clean and practical form to calculate the distance of two polices (Eq 13). Furthermore, the gradient of Eq 14 can be deduced as in Eq 15. It is worth mentioning that when comparing two distances ($dist(\\pi_a, \\pi_b)$ and $dist(\\pi_a, \\pi_c)$), it should be based on trajectories generated by $\\pi_a$ playing against the same opponent $b_{-i}$ (this leads to the same $\\beta_s$).\n\n[1] Samid Hoda, Andrew Gilpin, Javier Pena, and Tuomas Sandholm. Smoothing techniques for computing nash equilibria of sequential games. Mathematics of Operations Research, 35(2):494–512, 2010.\n\n[2] Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Optimistic regret minimization for extensive-form games via dilated distance-generating functions. Advances in neural information processing systems, 32, 2019.\n\n[3] Weiming Liu, Huacong Jiang, Bin Li, and Houqiang Li. Equivalence analysis between counterfactual regret minimization and online mirror descent. In Proceedings of the 39th International Conference on Machine Learning, volume 162, pages 13717–13745, 2022.\n\n[4] Lee, Chung-Wei, Christian Kroer, and Haipeng Luo. \"Last-iterate convergence in extensive-form games.\" Advances in Neural Information Processing Systems 34 (2021): 14293-14305.\n\n[5] Bai, Yu, et al. \"Near-optimal learning of extensive-form games with imperfect information.\" International Conference on Machine Learning. PMLR, 2022."}, {"review_id": "u5PGiYWod3", "reviewer": "Reviewer_jhEH", "summary": "In this work, the authors sought to justify the benefit of diversity by investigating properties of an expanding policy hull (PH), as supported by a set of policies in the context of population learning using Policy Space Response Oracle (PSRO). The authors discussed the limitations of expanding gamescape as a proxy for exploration in the policy space and reviewed several works on inducing diversity in prior works. Finally, the authors proposed their own diversity regularisation techniques and showed evidence that this approach leads to faster convergence to full game NE compared to baselines. ", "questions": "* Eq 14: how is the min operator implemented as there are infinite such mixed policies? If each such sample corresponds to a mixture-policy mixed at the start of an episode, would you draw multiple samples from the same distribution in the population simplex?  \n\n* Policy Hull: is the definition of Policy Hull the same as Population Simplex described in https://arxiv.org/pdf/2205.15879.pdf? I.e. they both correspond to all convex mixtures supported by a set of policies? If so, would simplex-NeuPL be a useful representation scheme when searching for diverse BR policies? If not, could you clarify their differences? \n\n* L269: ... PSD-PSRO over PSRO in approximating a NE. Is this statement empirical or do you expect better convergence rate in theory which can be stated more explicitly?\n\n* Fig 1 (Left): nit: could you specify finer-grained y-axis for these figure? \n\n* L302: instances of Goofspiel as implemented in OpenSpiel could be solved exactly, could the authors clarify which game setting is used? Could similar analysis be done in more restricted setting such that we can show exact convergence in Goofspiel? \n\n* AlphaStar888: the dataset presents the payoff between 888 RL agents, but the diversity regularisation term seem to suggest needing access to state action in the underlying game. Could you clarify how diversities between these RL policies are computed?  \n\n* Fig 3: exploitability in Leduc Poker seems to be reducing still (at 0.2 currently), would it reduce further to lower level? Are there computational bottleneck that would prevent further training? How are best-responses solved in this experiment? By RL? Or by exact solvers from OpenSpiel? \n\nMy reservation in accepting this work is primarily due to my confusion as stated above, I would encourage the authors to further clarify their empirical results and experimental settings. ", "limitations": "This work is methodological and does not present immediate potential for negative societal impact. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* originality / significance\nI find the discussion on what to focus on when it comes to defining policy space diversity interesting, thorough and well motivated. There have been several works on this topics in the literature (as surveyed by the authors) but prior works presented different definitions and motivations for the need for policy space diversity which this work attempts to address. Having a unified language to discuss diversity with the goal of game-solving is sorely needed by the community. \n\n* quality / clarity \nEmpirical results of PSD-PSRO appear thorough, though I have a few clarifying questions on the results. I would encourage the authors to revise the presentation to make the experimental protocol more clear and convincing. The theoretical justification for policy hull expansion appears sound. ", "weaknesses": "* Clarity: the authors presented prior works from the angle of NE game-solving. However I believe this is not necessarily the stated goal in all prior works? For instance, PSRO_rN was proposed as a way to expand gamescape (rather than a method that solves for a full game NE at faster convergence rate). This should be clear from their discussion on the disc game where focusing on NE game solving would lead to a contracted gamescape, i.e. the final solution would not contain pure strategies that would be interesting to represent as they optimally exploit certain opponents (as compared to the NE mixed strategy). I would encourage the authors to revisit the stated motivation for these prior works and re-state their motivations more precisely.\n\n* Scope: the scope of this work could be stated more precisely? Several prior works on population diversity explicitly focused on symmetric two-player zero-sum games (i.e. gamescape was defined in this regime). The authors appear to state their results generally (e.g. L103, $\\Pi_i$, $\\Pi_{-i}$), do you aim to make statements about n-player general-sum games in this paper? If so, how should one interpret e.g. Equation 7? Should I interpret $\\sigma_{-i}$ as the joint distribution across all coplayers of player $i$? What would be the dimensions of the relative population performance in that case? \n\n* Preciseness: in several places the authors seem to imply that vanilla PSRO would not converge to a full game NE while there are convergence guarantees when using suitable best-response solvers. Perhaps revisit these statements to make it clear that the intention is to offer faster convergence rate? E.g. L266 and L174. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks very much for your review. We respond to all your comments and questions below. \n\n**Q1.** The weakness of Clarity. I would encourage the authors to revisit the stated motivation for these prior works and re-state their motivations more precisely.\n\n**A1.** Many thanks for your suggestion. We will update the paper and state the goal of PSRO_rN more precisely. Yes, other than the NE game-solving, PSRO_rN is also explicitly targeting the policy population diversity defined on the gamescape. \n\n**Q2.** The weakness of Scope. the scope of this work could be stated more precisely?\n\n**A2.** Many thanks for your suggestion. The scope of this work can be stated more precisely: we focus on two-player zero-sum games. We did not mean to state our results beyond two-player zero-sum games. \n\n**Q3.** The weakness of Preciseness.  In several places the authors seem to imply that vanilla PSRO would not converge to a full game NE while there are convergence guarantees when using suitable best-response solvers. \n\n**A3.** Many thanks for your suggestion. The intention of our method PSD-PSRO is indeed to **accelerate** PSRO in finding a NE. We did not mean to imply that PSRO would not converge. In fact,  PSRO would find a full game NE once it converges. By contrast, it is not clear, in other state-of-the-art diversity-enhancing PSRO variants [1, 35, 26, 27] (citation index in the paper), whether a full game NE is found once they are converged in terms of their optimization objectives. Notably, as pointed out in [30] (citation index in the paper), PSRO_rN is not guaranteed to find a NE once converged. Again, we are aware that PSRO_rN is not solely about NE game-solving. \n\n**Q4.** Eq 14: how is the min operator implemented as there are infinite such mixed policies? would you draw multiple samples from the same distribution in the population simplex?\n\n**A4.** In practice, we sampled multiple policies (the exact number equals to the size of $\\Pi^t_i$) in the policy hull of $\\Pi^t_i$ and used the sampled min policy to approximate the true $\\pi_i^{min}$.  Each such sample corresponds to a mixture-policy mixed at the start of an episode. We only need to **evaluate** (no need of play) the sampled mixture-policy on trajectories generated by playing $\\pi_i$ against a fixed opponent $b_{-i}$ (see Eq 14). We will make this clearer in the revision. \n\n\n**Q5.** Policy Hull: is the definition of Policy Hull the same as Population Simplex described in https://arxiv.org/pdf/2205.15879.pdf?\n\n**A5.** The definition of Policy Hull is the same as Population Simplex described in https://arxiv.org/pdf/2205.15879.pdf\nThe neural architecture of simplex-NeuPL is orthogonal to the contributions of our method PSD-PSRO. It is definitely worth trying this architecture in PSD-PSRO. Also, we believe the diversity optimization scheme in PSD-PSRO could be helpful to simplex-NeuPL for its own purpose as well. We will add the discussion in the revised paper.  \n\n**Q6.** L269: ... PSD-PSRO over PSRO in approximating a NE. Is this statement empirical or do you expect better convergence rate in theory which can be stated more explicitly?\n\n**A6.** This statement is empirical. A better convergence rate in theory of PSD-PSRO (or other algorithms) over PSRO is an importnat future work. \n\n**Q7.** Fig 1 (Left): nit: could you specify finer-grained y-axis for these figure?\n\n**A7.** Yes. This will be made clearer in the revision. \n\n**Q8.**  could the authors clarify which game setting is used about Goofspiel? Could similar analysis be done in more restricted setting such that we can show exact convergence in Goofspiel?\n\n**A8.** Yes, the goofspiel results we have provided in the main paper is the goofspiel with 8 point cards, corresponding to the setting \"turn_based_simultaneous_game(game=goofspiel(imp_info=True,num_cards=8,points_order=descending))\" in open-spiel. \nThe goofspiel results with exact exploitability convergence (please check the rebuttal pdf at the top) we add in the rebuttal is the goofspiel with 5 point cards, corresponding to the setting \"turn_based_simultaneous_game(game=goofspiel(imp_info=True,num_cards=5,points_order=descending))\" in open-spiel.\n\n**Q9.** AlphaStar888: the dataset presents the payoff between 888 RL agents, but the diversity regularisation term seem to suggest needing access to state action in the underlying game. Could you clarify how diversities between these RL policies are computed?\n\n**A9.** AlphaStar888 can be viewed as a zero-sum symmetric two-player game (like the rock-paper-scissors), where there is only one state $s_0$. In $s_0$, there are 888 legal actions. Any mixed strategy is a discrete probability distribution over the 888 actions. So, the diversity term in Eq 14 for AlphaStar888 reduces to the KL divergence between two 888-dim discrete probability distributions. This will be made clearer in the revision. \n\n\n**Q10.** Fig 3: exploitability in Leduc Poker seems to be reducing still (at 0.2 currently), would it reduce further to lower level? Are there computational bottleneck that would prevent further training? How are best-responses solved in this experiment? By RL? Or by exact solvers from OpenSpiel?\n\n**A10.** There is no computational bottleneck that would prevent further training. Longer training curves are provided in the rebuttal pdf at the top.  Best-responses for Leduc are exact solvers from OpenSpiel.\n\nHope the above clarifies your confusion. If there is anything still unclear, please do not hesitate to bring it up."}, {"review_id": "6G6Zm4NW28", "reviewer": "Reviewer_YW2F", "summary": "This paper considers PSRO framework for approximating a NE in multi-agent non-stransitive games. The authors points out that the existing diversity matrics cannot guarantee that a more diverse policy space leads to a better approximation of the NE. To solve this issue, this paper proposes a new diversity metric and a corresponding algorithm, PSD-PSRO, which enjoys better convergence property. \n", "questions": "See the Weakness section", "limitations": "See the Weakness section", "rating": 5, "confidence": 4, "soundness": 1, "presentation": 3, "contribution": 2, "strengths": "The paper is very well-organized and easy to follow. It provides a nice overview of related literature and states its contribution clearly.\n", "weaknesses": "My major concern is the correctness of the result. In specific, I think the derivation of the gradient caculation in equation (15) might be incorrect. The derivation from line 484 to 485 in the supplementary material might need some reconsideration. I particular I don't think the first equation actually holds because the $\\pi_i^{\\min}$ should be a function of $\\pi_i$. It might even be questionable whether this function is differentiable.\n\nI'm also curious about the computational complexity of the algorithm proposed in the paper. It seems that compared with other diversity metrics, the new metrics proposed is harder to compute because it needs to solve a minimization problem. What are the computational time for the numerical examples? And how does it compare with other methods? In Section D.3, the authors only provides the percentage, but it would be better to have a comparison among different methods.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks very much for your review. We respond to all your comments of weaknesses in the following and will update the paper to make it clearer. \n\n**Q1** I think the derivation of the gradient calculation in equation (15) might be incorrect.\n\n**A1** We double-checked the derivation of equation 15 (in appendix Line 484-485, Eq 21), and we believe it is **correct** (though we will edit to make this derivation clearer). $\\pi_i^{min}$ corresponds to the nearest policy in the policy hull of  $\\mathcal{\\Pi^t_i}$ to $\\pi_i$ (as defined in line239). $\\pi_i^{min}$ indeed depends on $\\pi_i$. Yet, given the current $\\pi_i$, $\\pi_i^{min}$ is fixed (suppose it is unique) and can be approximated **in advance**. More specifically for Eq 21:\n\n1. In L484, since $\\min_{\\pi_i^k\\in H(\\Pi_i^t)} E_{s_i \\in \\tau, \\tau \\sim \\pi_i, b_{-i}} [KL(\\pi_i(s_i) \\| \\pi_{i}^{k}(s_i))]= E_{s_i \\in \\tau, \\tau \\sim \\pi_i, b_{-i}} [KL(\\pi_i(s_i) \\| \\pi_{i}^{min}(s_i))]$, we can get the first line. \n2. The second line is by the definition of expectation, and the third line is the application of the product rule.\n3. We use the policy gradient theorem for the left term in the last second line, and rewrite the right term using the notation $ E_{s_i \\in \\tau, \\tau \\sim \\pi_i, b_{-i}} $. \n4. The last term in Eq 21, which is a gradient with respect to the parameters of $\\pi_i$ of a KL between $\\pi_i$ and $\\pi^{min}_i$. Here, the action probabilities of $\\pi^{min}_i$ in $s_i$ have been evaluated in advance and are constants (not a function of $\\pi_i$). As a result, this term is a function of only $\\pi_i$. Also, to get the gradient properly,  a small prob (1e-5) is added to each action (normalizing afterwards) to ensure that there is no zero-prob action in both $\\pi_i$ and $\\pi^{min}_i$. This new detail will be added to the revision.\n\nWe would be happy to provide further details if anything remains unclear. \n\n**Q2** I'm also curious about the computational complexity of the algorithm proposed in the paper.  And how does it compare with other methods? In Section D.3, the authors only provides the percentage, but it would be better to have a comparison among different methods.\n\n**A2**   As we show in Appendix D.3,  the majority time in PSD-PSRO is on BR solving and computing the payoff matrix, which is **shared** by PSRO and all its variants. The time spent on calculating our diversity metric is not significant (accounts for 7.9\\% computational time). We will make this clearer in the revision.\n\n\n**Q3** It seems that compared with other diversity metrics, the new metrics proposed is harder to compute because it needs to solve a minimization problem.\n\n**A3** Ideally, to get the true $\\pi_i^{min}$, we should solve a convex optimization problem. In practice, we sampled multiple policies in the policy hull of $\\mathcal{\\Pi_i}$ and used the sampled min policy to approximate the true $\\pi_i^{min}$. This is straightforward to implement and does not add too much complexity. We will make this clearer in the revision. "}, {"review_id": "VVseJ3doxZ", "reviewer": "Reviewer_Mw94", "summary": "This paper investigates the strategy exploration problem faced in learning-based game-solving algorithms. Their posed solution is to expand the empirical game with policies that are both approximate best responses to the current solution and maximally expands the policy hull. This method is motivated by an analysis on the exploitability of the population captured by the empirical game. They show a variety of performance benefits across a suite of games.", "questions": "- Convex Hull Enlargement and Occupancy Measure Mismatching appear to be functionally different from the other diversity measures because they focus on the impact of including another policy. I was wondering if you thought about how your methods or the others might be alternatively used between these two perspectives? \n- Population exploitability appears to be similar to the metrics defined in Lanctot et al.. \"Population-based Evaluation in Repeated Rock-Paper-Scissors as a Benchmark for Multiagent Reinforcement Learning.\" Might be worth discussing as concurrent/previous work.\n- L159-160: There's nothing ill-posed with the idea of enlarging a gamescape generally. I would recommend refining this claim to focus on your point: for diversity. \n- L165-166: Exploitability increasing in the short-term might be OK if it facilitates better long-term exploration. I would suggest revising this claim to focus on when future iterations occurring are uncertain---I believe AnytimePSRO makes an argument like this.\n- L197: If you're defining the concept of fine policy representation could you make it more clear please?\n- L218: There is something potentially confusing about your definition of the sequence-form. Shouldn't it either include all possible trajectories to (s,a) or be only the probability chain of actions since perfect recall makes all paths unique? A quick comment about this in the paper I think would be very nice.\n- L245: This method requires a design choice of which opponent distribution diversity will be measured against. Could the authors comment on different settings they tried? It might be also useful to discuss how this is both a limit and potential advantage of this method when compared to other diversity metrics. You are both potentially more limited in your measure with a bad choice of opponent, or able to better measure by including behaviors outside of the empirical game. \n- For the AlphaStar888 experiments could you explain how you computed the diversity metrics given only the empirical game? The metrics are all dependent on the policies that are not directly available. \n- L323: I would be interested in having the details of what makes BD&RD-PSRO to tune and anything you might have learned from the attempted reimplementation in the appendix. \n- For Goofspiel, if you can easily get them, could you please also provide approximate regret curves? This can be estimated using the combined empirical game across methods.\n- For Goofspiel, are you using the final solutions produced by the algorithms to compare or regret? It's also not clear how long this experiment has been run and the respective population sizes.\n", "limitations": "There is no focused discussion on either the limitations or broader impact of this work within the paper. \n\nThe last paragraph, presumably their limitation sections, quickly discuss the role of trading-off diversity in game solving. I would have preferred to see discussions related:\n - Setting the opponent policy for policy comparisons\n - How the selection of the aforementioned opponent biases the measure of diversity\n - How changes in the opponent policy will require much larger computational costs\n - Results are partially on games that are not exactly solved, and the true relative performance of methods may differ\n - etc..\n\n", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "Overall, this paper is well-rounded. The framing is clear and the related work very nicely characterizes a variety of the preceding work. While the contributed ideas of population performance and exploitability are lightly different than previous work, I think the interpretation brought forward by the small difference is rather nice. Moreover, this work treats the soft and difficult topic of diversity formally, which is a nice change of pace compared to preceding work focused on heuristics. They provide both an exact formulation of their metric, and a practical version that can be used in gradient optimization.  ", "weaknesses": "The major weakness of this work is the confusion of empirical games and what they refer to as the \"meta game\". The crucial difference being that empirical games have only estimates of the true payoffs. PSRO uses an empirical game, but meta games may be useful for best-case convergence guarantees. Unfortunately this confuses and invalidates a variety of claims throughout the paper that mix up their usage. This is easy to correct, and I am very supportive of the paper post this correction.\n\nAnother general point of weakness is the recurring claim of the problems with gamescapes. They are right, as they showed, that each iteration isn't gauranteed to lead to a monotonically improving game solution. However, this does not mean that the gamescape analysis wouldn't have long-term benefits. I suggest lightening the critique of gamescapes, and instead focus criticism only on their specific application of per-iteration policy exploration.  \n\nI would have liked to see some analysis related to diversity and/or settings of their algorithm in the results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks very much for your review. We respond to all your questions below. \n\n**Q1.** the confusion of empirical games and the \"meta game\". \n\n**A1.**  The \"meta game\" will be used more cautiously in the revision. The main purpose of our introduction of \"meta game\" was to define the meta-policy (a discrete probability distribution over policies). \n\n**Q2.** the recurring claim of the problems with gamescapes.\n\n**A2.** We agree that the critique of gamescapes appears in an excess of\nplaces in the paper (we will lighten this). Yet, what we really want to emphasize is enlarging the gamescape does not necessarily improve the approximation to a NE either in one iteration on in the long run (Theorem 3.4). By contrast, optimizing our diversity (policy space diversity) defined on the policy hull (instead of gamescape) improves the approximation to a NE (Theorem 4.2). \n\n**Q3.** Convex Hull Enlargement and Occupancy Measure Mismatching. How your methods relate to them?\n\n**A3.** There is the subtle difference between the definition of a diversity metric and the practical way of optimizing the diversity metric. \nWe would like to argue the superiority of both our definition of diversity metric and our practical way to optimize our diversity metric, in comparison to all previous diversity-enhancing PSRO methods. \n\n- Our diversity metric is defined on the policy hull, the optimization of which has theoretical and positive impact on approaching a NE (Theorem 4.2). In contrast, all previous diversity-enhancing PSROs defined their diversity metrics on the gamescape, the optimization of which does not necessarily mean a better approximation to a NE (Theorem 3.4).\n\n- To quantify the similarity of two policies, a number of previous methods focus on the f-divergence of the occupancy measure [19,26]. However, computing the f-divergence based on the occupancy measure is usually intractable and often in practice **roughly** approximated using neural networks [19,26]. By contrast, we employ the sequence form representation of a policy, which is widely used in the study of imperfect-information games. More importantly, we deduce a practical **state-based** diversity optimization objective (Eq 14) based on the Bregman divergence on the sequence form representation.\n\n**Q4.** Population exploitability appears to be similar to the metrics defined in Lanctot et al..\n\n**A4.** We will add the discussion to the revision.\n\n**Q5.** There's nothing ill-posed with the idea of enlarging a gamescape generally. I would recommend refining this claim to focus on your point: for diversity.\n\n**A5.** We agree that there is nothing ill-posed if our goal is solely about enlarging a gamescape. What we would like to emphasize is enlarging the gamescape does not necessarily lead to a better approximation to a NE (theorem 3.4) (the goal of most previous diversity-enhancing PSRO variants). PSD-PSRO improves PSRO with our policy space diversity, and its only goal is to find a NE (not for diversity).  We will make this clearer in the revision.  \n\n**Q6.** Exploitability increasing in the short-term might be OK if it facilitates better long-term exploration.\n\n**A6.** We would like to clarify that PSD-PSRO is more about a new diversity regularization that has proved benefits in approximating a NE, either in one iteration or the long term. In contrast, previous diversity metrics (mainly on gamescapes) for PSRO do not have the positive&theoretical connection to the goal of approximating a NE.  BTW, we believe Anytime PSRO is targeting reducing the exploitability at each iteration. We will make this clearer in the revision.\n\n**Q7.** If you're defining the concept of fine policy representation could you make it more clear please?\n\n**A7.** Yes, we will. \n\n**Q8.** There is something potentially confusing about your definition of the sequence-form.\n\n**A8.**  Yes, perfect recall makes all paths unique. We will make it clearer. \n\n**Q9.** This method requires a design choice of which opponent distribution diversity will be measured against.\n\n**A9.** Actually, the sequence form definition (Eq 11) does not depend on the opponent policy while the occupancy measure does (because it is a prob distribution over state-action). According to Eq 14, we do need a opponent policy $b_{-i}$ to generate the trajectories, and occupancy measure mismatch or diversity on gamescape need opponent policies as well.  In all our experiments, we set $b_{-i}$ to $\\sigma_{-i}^{t}$ (the meta NE policy from last iteration) for convenience. In the rebuttal pdf, we add ablation experiments on Leduc setting $b_{-i}$ to the uniform random policy, where PSD-PSRO still plays the best.  \n\n**Q10.** Question about AlphaStar888.\n\n**A10.** AlphaStar888 can be viewed as a zero-sum symmetric two-player game (like the rock-paper-scissors), where there is only one state $s_0$. In $s_0$, there are 888 legal actions. Any mixed strategy is a discrete probability distribution over the 888 actions. So, the diversity term in Eq 14 for AlphaStar888 reduces to the KL divergence between two 888-dim discrete probability distributions. \n\n**Q11.**  I would be interested in having the details of what makes BD&RD-PSRO to tune\n\n**A11.** The code is not available according to https://github.com/sjtu-marl/bd_rd_psro, where it says \"It is the company's internal code, which cannot be disclosed here due to the copyright issue.\". We have not tried reimplementing BD&RD-PSRO when f-divergence is approximated using prediction error of neural network (this is the reason we feel it is hard to tune).\n\n**Q12.** Question about Goofspiel.\n\n**A12.** The results on Goofspiel (8 point cards, too large to show exact exploitability in OpenSpiel) in the main paper are the comparison among final solutions produced by different methods. We have added in the rebuttal pdf the results on Goofspiel (5 point cards) with the exact convergence of exploitability of different methods. More experiment details will be added in the revision."}]

Author rebuttal:
We provide additional experiment results in the pdf. 

In the pdf, Figure 1 shows the result of continuing running on Leduc, corresponding to **Q10 by Reviewer jhEH**.

In the pdf, Figure 2 shows the result of the experiment on Goofspiel with 5 point cards (a smaller setting than the original Goofspiel (with 8 point cards) we run on in the first submission), corresponding to **Q8 by Reviewer jhEH** and **Q12 by Reviewer Mw94**. 

In the pdf, Figure 3 shows the result of PSD-PSRO with different opponent settings for generating the trajectories to optimize our diversity, corresponding to **Q9 by Reviewer Mw94**.

Meta-review: A case of clear acceptance with unanimous support from all reviewers. The authors are encouraged to address the comments/suggestions of the reviewers in improving the final version of their paper.
Decision: Accept (poster)