Modelling Behavioural Diversity for Learning in Open-Ended Games

Introduction

Nature exhibits a remarkable tendency towards diversity (Holland et al., 1992). Over the past billions of years, natural evolution has discovered a vast assortment of unique species. Each of them is capable of orchestrating, in different ways, the complex biological processes that are necessary to sustain life. Equally, in computer science, machine intelligence can be considered as the ability to adapt to a diverse set of complex environments (Hernández-Orallo, 2017). This suggests that the intelligence of AI evolves with environments of increasing diversity. In fact, recent successes in developing AIs that achieve super-human performance on sophisticated battle games (Vinyals et al., 2019b; Ye et al., 2020) have provided factual justifications for promoting behavioural diversity in training intelligent agents.

In game theory, the necessity of pursuing behavioural diversity is also deeply rooted in the non-transitive structure of games (Balduzzi et al., 2019). In general, an arbitrary game, of either the normal-form type (Candogan et al., 2011) or the differential type (Balduzzi et al., 2018a), can always be decomposed into a sum of two components: a transitive part and a non-transitive part. The transitive part of a game represents the structure in which the rule of winning is transitive (i.e., if strategy A beats B, B beats C, then A beats C), and the non-transitive part refers to the structure in which the set of strategies follows a cyclic rule (e.g., the endless cycles among Rock, Paper and Scissors). Diversity matters especially for the non-transitive part simply because there is no consistent winner in such part of a game: if a player only plays Rock, he can be exploited by Paper, but not so if he has a diverse strategy set of Rock and Scissor.

In fact, many real-world games demonstrate strong non-transitivity (Czarnecki et al., 2020); therefore, it is critical to design objectives in the learning framework that can lead to behavioural diversity. In multi-agent reinforcement learning (MARL) (Yang & Wang, 2020), promoting diversity not only prevents AI agents from checking the same policies repeatedly, but more importantly, helps them discover niche skills, avoid being exploited and maintain robust performance when encountering unfamiliar types of opponents. In the examples of StarCraft (Vinyals et al., 2019b), Soccer (Kurach et al., 2020) and autonomous driving (Zhou et al., 2020), learning a diverse set of strategies has been reported as an imperative step in strengthening AI’s performance.

Despite the importance of diversity (Yang et al., 2021), there is very little work that offers a rigorous treatment in even defining diversity. The majority of work so far has followed a heuristic approach. For example, the idea of co-evolution (Durham, 1991; Paredis, 1995) has drawn forth a series of effective methods, such as open-ended evolution (Standish, 2003; Banzhaf et al., 2016; Lehman & Stanley, 2008), population based training methods (Jaderberg et al., 2019; Liu et al., 2018), and auto-curricula (Leibo et al., 2019; Baker et al., 2019). Despite many empirical successes, the lack of rigorous treatment for behavioural diversity still hinders one from developing a principled approach.

In this work, we introduce a rigorous way of modelling behavioural diversity for learning in games. Our approach offers a new geometric interpretation, which is built upon determinantal point processes (DPP) that have origins in modelling repulsive quantum particles (Macchi, 1977) in physics. A DPP is a special type of point process, which measures the probability of selecting a random subset from a ground set where only diverse subsets are desired. We adapt DPPs to games by formulating the expected cardinality of a DPP as the diversity metric. The proposed diversity metric is a general tool for game solvers; we incorporate our diversity metric into the best-response dynamics, and develop diversity-aware extensions of fictitious play (FP) (Brown, 1951) and policy-space response oracles (PSRO) (Lanctot et al., 2017). Theoretically, we show that maximising the DPP-based diversity metric guarantees an expansion of the gamescape spanned by agents’ mixtures of policies. Meanwhile, we prove the convergence of our diversity-aware learning methods to the respective solution concept of Nash equilibrium and $\alpha$-Rank (Omidshafiei et al., 2019) in two-player games. Empirically, we evaluate our methods on tens of games that show strong non-transitivity, covering both normal-form games and open-ended games. Results confirm the superior performance of our methods, in terms of lower exploitability, against the state-of-the-art game solvers.

Related Work

Diversity has been extensively studied in evolutionary computation (EC) (Fogel, 2006) where the central focus is mimicking the natural evolution process. One classic idea in EC is novelty search (Lehman & Stanley, 2011a), which searches for models that lead to different outcomes. Quality-diversity (QD) (Pugh et al., 2016) hybridises novelty search with a fitness objective; two resulting methods are Novelty Search with Local Competition (Lehman & Stanley, 2011b) and MAP-Elites (Mouret & Clune, 2015). For solving games, QD methods were applied to ensure policy diversification among learning agents (Gangwani et al., 2020; Banzhaf et al., 2016). Despite remarkable successes (Jaderberg et al., 2019; Cully et al., 2015), quantifying diversity in EC is often task-dependent and hand-crafted; as a result, building a theoretical understanding of how diversity is generated during learning is non-trivial (Brown et al., 2005).

Searching for behavioural diversity is also a common topic in reinforcement learning (RL). Specifically, it is studied under the names of skill discovery (Eysenbach et al., 2018; Hausman et al., 2018), intrinsic exploration (Gregor et al., 2017; Bellemare et al., 2016; Barto, 2013), or maximum-entropy learning (Haarnoja et al., 2017, 2018; Levine, 2018). These solutions can still be regarded as QD methods, in the sense that the quality refers to the cumulative reward, and dependent on the context, diversity could refer to policies that visit new states (Eysenbach et al., 2018) or have a large entropy (Levine, 2018). Two related works in RL, yet with a different scope, are Q-DPP (Yang et al., 2020b), which adopts DPP to factorise agents’ joint Q-functions in MARL, and DvD (Parker-Holder et al., 2020), which studies diversity based on the ensembles of policy embeddings.

For two-player zero-sum games, smooth FP (Fudenberg & Levine, 1995) is a solver that accounts for diversity through adopting a policy entropy term in the original FP (Brown, 1951). When the game size is large, Double Oracle (DO) (McMahan et al., 2003) provides an iterative method where agents progressively expand their policy pool by, at each iteration, adding one best response versus the opponent’s Nash strategy. Online DO (Dinh et al., 2021) considers a no-regret best response. PSRO generalises FP and DO via adopting a RL subroutine to approximate the best response (Lanctot et al., 2017). Pipeline-PSRO (McAleer et al., 2020) trains multiple best responses in parallel and efficiently solves games of size $10^{50}$. PSROrN (Balduzzi et al., 2019) is a specific variation of PSRO that accounts for diversity; however, it suffers from poor performance in a selection of tasks (Muller et al., 2019). Since computing NE is PPAD-Hard (Daskalakis et al., 2009), another important extension of PSRO is $\alpha$-PSRO (Muller et al., 2019), which replaces NE with $\alpha$-Rank (Omidshafiei et al., 2019; Yang et al., 2020a), a solution concept that has polynomial-time solutions on general-sum games. Yet, how to promote diversity in the context of $\alpha$-PSRO is still unknown. In this work, we develop diversity-aware extensions of FP, PSRO and $\alpha$-PSRO, and show on tens of games that our diverse solvers achieve significantly lower exploitability than the non-diverse baselines.

Notations & Preliminary

Nash equilibrium (NE) exists in all finite games (Nash et al., 1950); it is a joint mixed-strategy profile ${\bm{\pi}}$ in which each player $i\in\mathcal{N}$ plays the best response to other players s.t. {\bm{\pi}}^{i}\in\mathbf{BR}^{i}({\bm{\pi}}^{-i}):=\arg\max_{{\bm{\pi}}\in\Delta_{S^{i}}}\big{[}{\bm{G}}^{i}({\bm{\pi}},{\bm{\pi}}^{-i})\big{]}. For $\epsilon>0$, an $\epsilon$-best response to the ${\bm{\pi}}^{-i}$ is \mathbf{BR}_{\epsilon}^{i}({\bm{\pi}}^{-i}):=\big{\{}{\bm{\pi}}^{i}:{\bm{G}}^{i}\big{(}{\bm{\pi}}^{i},{\bm{\pi}}^{-i}\big{)}\geq{\bm{G}}^{i}\big{(}\mathbf{BR}^{i}({\bm{\pi}}^{-i}),{\bm{\pi}}^{-i}\big{)}-\epsilon\big{\}}, and an $\epsilon$-NE is a joint profile ${\bm{\pi}}\text{ s.t. }{\bm{\pi}}^{i}\in\mathbf{BR}_{\epsilon}^{i}({\bm{\pi}}),\forall i\in\mathcal{N}$. The exploitability (Davis et al., 2014) measures the distance of a joint strategy profile ${\bm{\pi}}$ to a NE, written as

When the exploitability reaches zero, all players reach their best responses, and thus ${\bm{\pi}}$ is a NE.

Computing NE in multi-player general-sum games is PPAD-Hard (Daskalakis et al., 2009). No polynomial-time solution is available even in two-player cases (Chen et al., 2009). Additionally, NE may not be unique. $\alpha$-Rank (Omidshafiei et al., 2019) is an alternative solution concept, which is built on the response graph of a game. Specifically, $\alpha$-Rank defines the so-called sink strongly-connected components (SSCC) nodes on the response graph that have only incoming edges but no outgoing edges. The SSCC of $\alpha$-Rank serves as a promising replacement for NE; the key associated benefits are its uniqueness, and its polynomial-time solvability in $\mathcal{N}$-player general-sum games. A more detailed description of $\alpha$-Rank can be found in Appendix A.

2 Open-Ended Meta-Games

In the meta-game analysis (a.k.a. empirical game-theoretic analysis) (Wellman, 2006; Tuyls et al., 2018), traditional solution concepts (e.g., NE or $\alpha$-Rank) can still be computed based on ${\bm{\mathsfit{M}}}$, even in a more scalable manner, this is because the number of “higher-level” strategies in the meta-game is usually far smaller than the number of atomic actions of the underlying game. For example, in tackling StarCraft (Vinyals et al., 2019a), hundreds of deep RL models were trained, which is a trivial amount compared to the number of atomic actions: $10^{26}$ at every time-step.

3 Game Solvers

In solving NFGs, Fictitious play (FP) (Brown, 1951) describes the learning process where each player chooses a best response to their opponents’ time-average strategies, and the resulting strategies guarantee to converge to the NE in two-player zero-sum, or potential games. Generalised weakened fictitious play (GWFP) (Leslie & Collins, 2006) generalises FP by allowing for approximate best responses and perturbed average strategy updates. It is defined by:

As $t\rightarrow\infty$, $\alpha_{t}\rightarrow 0,\epsilon_{t}\rightarrow 0$ and $\sum_{t\geq 1}\alpha_{n}=\infty$. $\{M_{t}\}_{t\geq 1}$ is a sequence of perturbations that satisfies: $\forall T>0$,

GWFP recovers FP if $\alpha_{t}=1/t$, $\epsilon_{t}=0$ and $M_{t}=0,\forall t$.

With correct choices of (meta-)policy solver $\mathcal{S}$ and Oracle $\mathcal{O}$, various types of (meta-)game solvers can be summarised in Table 1. For example, it is trivial to see that GWFP is recovered when $\mathcal{S}=\operatorname{UNIFORM}(\cdot)$ and $\mathcal{O}^{i}=\mathbf{BR}_{\epsilon}^{i}(\cdot)$. Double Oracle (D.O.) and PSRO methods refer to the cases when the (meta-)solver computes NE. Notably, when $\mathcal{S}=\alpha$-Rank, Muller et al. (2019) showed that the standard best response fails to converge to the SSCC of $\alpha$-Rank; instead, they propose $\alpha$-PSRO where the Oracle is computed by the so-called Preference-based Best Response (PBR), that is,

4 Existing Diversity Measures

Promoting behavioural diversity can lead to learning more effective strategies and achieving lower exploitability in performance. The smooth FP method (Fudenberg & Levine, 1995) incorporates the policy entropy $\mathcal{H}(\pi)$ when finding the best response to advocate diversity, written as \pi^{i}\in\mathbf{BR}_{\epsilon}^{i}({\bm{\pi}}^{-i})=\arg\max_{\pi\in\Delta_{S^{i}}}\big{[}{\bm{G}}^{i}(\pi,{\bm{\pi}}^{-i})+\tau\cdot\mathcal{H}(\pi)\big{]} where $\tau$ is a weighting hyper-parameter. In the case of $\tau\rightarrow 0$ as training goes on, smooth FP converges to the GWFP process almost surely (Leslie & Collins, 2006).

In short, the ED in PSROrN encourages players to amplify its strengths and ignore its weaknesses in finding a new policy. On symmetric zero-sum games, if both players play their Nash strategy (this assumption will be removed by our method), then Eq. (8) guarantees to enlarge the gamescape.

Nonetheless, focusing only on the winners can sometimes be problematic, since weak agents may still hold the promise of tackling niche tasks, and they can serve as stepping stones for discovering stronger policies later during training. For example, when training StarCraft AIs, overcoming agents’ weaknesses was found to be more important than amplifying strengths (Vinyals et al., 2019b), a completely opposite result to PSROrN. Another counter example that fails PSROrN is the RPS-X game (McAleer et al., 2020):

In RPS-X, if the initial strategy pool of PSROrN starts from either {R}, {P} or {S}, then the algorithm will terminate without exploring the fourth strategy because the best response to {R,P,S} is still in {R,P,S}; however, the fourth strategy alone can still exploit the population of {R,P,S} by getting a positive payoff of $2/5$. Also see in Appendix C how our method can tackle this problem.

Our Methods

Instead of choosing between amplifying strengths or overcoming weaknesses, we take an altogether different approach of modelling the behavioural diversity in games. Specifically, we introduce a new diversity measure based on a geometric interpretation of games modelled by a determinantal point process (DPP). Due to the space limit, all proofs in this section are provided in Appendix D.

Originating in quantum physics for modelling repulsive Fermion particles (Macchi, 1977; Kulesza et al., 2012), a DPP is a probabilistic framework that characterises how likely a subset of items is to be sampled from a ground set where diverse subsets are preferred. Formally, we have

2 Expected Cardinality: A New Diversity Measure

Our target is to find a population of diverse policies, with each of them performing differently from other policies due to their unique characteristics. Therefore, when modelling the behavioural diversity in games, we can naturally use the payoff matrix to construct the DPP kernel so that the similarity between two policies depends on their performance in terms of payoffs against different types of opponents.

Expected Cardinality vs. Matrix Rank. There is a fundamental difference between using expected cardinality and using the rank of a payoff matrix as the diversity measure. The matrix rank is the maximal number of linearly independent columns, though it can measure the difference between the columns, it cannot model the diversity. For example, in RPS, a strategy of [$99\%$ Rock, $1\%$ Scissor] and a strategy of [$98\%$ Rock, $2\%$ Scissor] are different but they are not diverse as they both favour playing Rock. If one strategy is added into the population whilst the other already exists, the rank of the payoff matrix will increase by one, but the increment on expected cardinality is minor. In Fig. (1), adding the green strategy only contributes to the expected cardinality by $0.21$. This property is particularly important for learning in games, in the sense that finding a diverse policy is often harder than finding just a different policy. To summarise, we show the following proposition.

Maximising the diversity in Eq. (15) also maximises the Frobenius norm of $\|{\bm{\mathsfit{M}}}\|_{F}$, but NOT vice versa.

Notably, it is worth highlighting that the opposite direction of Proposition 6 is not correct, that is, maximising $\|{\bm{\mathsfit{M}}}\|_{F}$ will NOT necessarily lead to a large diversity. A counter-example in Fig. (1) is that, if one of the orange lines is long but the rest are short, though the Frobenius norm is large, the expected cardinality is still small. Thus, the diversity metric in Eq. (15) cannot simply be replaced by $\|{\bm{\mathsfit{M}}}\|_{F}$. We also provide empirical evidence in Appendix F.

3 Diverse Fictitious Play

With the newly proposed diversity measure of Eq. (15), we can now design diversity-aware learning algorithms. We start by extending the classical FP to a diverse version such that at each iteration, the player not only considers a best response, but also considers how this new strategy can help enrich the existing strategy pool after the update. Formally, our diverse FP method maintains the same update rule as Eq. (4), but with the best response changing into

where $\tau$ is a tunable constant. A nice property of diverse FP is that the expected cardinality is guaranteed to be a strictly concave function; therefore, Eq. (16) has a unique solution at each iteration. We have the following proposition:

Eq. (15) is a strictly concave function. The resulting best response in Eq. (16) has a unique solution.

Intuitively, the diverse FP process will almost surely converge to a GWFP process as long as $\tau\rightarrow 0$ and thus will enjoy the same convergence guarantees as GWFP (i.e., to a NE in two-player zero-sum or potential games). However, in order to prove such connection rigorously, we need to show the sequence of expected changes in strategy, which is induced by finding a strategy that maximises Eq. (16) at each iteration, is actually a uniformly bounded martingale sequence that satisfies Eq. (5). We show the below theorem:

The perturbation sequence induced by diverse FP process is a uniformly bounded martingale difference sequence; therefore, diverse FP shares the same convergence property as GWFP.

4 Diverse Policy-Space Oracle

When solving NFGs, the total number of pure strategies is known and thus a best response in Eq. (16) can be computed through a direct search, and the uniqueness of the solution is guaranteed by Proposition 7. When it comes to solving open-ended (meta-)games, the total number of policies is unknown and often infinitely many. Therefore, a best response has to be computed through optimisation subroutines such as gradient-based methods or RL algorithms. Here we extend our diversity measure to the policy space and develop diversity-aware solvers for open-ended (meta-)games.

With the ground set at each iteration, we can compute the diversity measure by Eq. (15). Subsequently, the objective of an Oracle can be written as

where ${\bm{\pi}}^{2}(\cdot)$ is the policy of the player two; depending on the game solvers, it can be NE, $\operatorname{UNIFORM}$, etc.

Based on Eq. (17), we can tell that the diversity of policies during training comes from two aspects. The obvious aspect is from the expected cardinality of the G-DPP that forces agents to find diverse policies. The less obvious aspect is from how the opponents are treated. Although the (meta-)policy of player $2$ is determined by ${\bm{\pi}}^{2}(\cdot)$, the learning player will have to focus on exploiting certain aspects of ${\bm{\pi}}^{2}(\cdot)$ in order to acquire diversity. This is similar in manner to selecting a diverse set of opponents. Theoretically, we are able to show that our diversity-aware Oracle can strictly enlarge the gamescape. Unlike PSROrN (see Proposition 6 in Balduzzi et al. (2019)), we do NOT need to assume the opponents are playing NE before reaching the result below.

Adding a new best-response policy $S_{\bm{\theta}}$ via Eq. (17) strictly enlarges the gamescape. Formally, we have

Implementation of Oracles. When the game engine $\phi$ is differentiable, we can directly apply gradient-based methods to solve Eq. (17). In general, many real-world games are black-box, thus we have to seek for gradient-free solutions or model-free RL algorithms. To tackle this, we provide zero-order Oracle and RL-based Oracle as approximation solutions to Eq. (17), and list their pseudocode and time complexity in Appendix H.

5 Diverse Oracle for α𝛼\alpha-Rank

The resulting diversity-aware Oracle that suits $\alpha$-Rank is:

The following theorem shows the convergence result of our diverse $\alpha$-PSRO to SSCC on two-player symmetric NFGs.

Diverse $\alpha$-PSRO with the Oracle of Eq. (18) converges to the sub-cycle of the unique SSCC in the two-player symmetric games.

Experiments & Results

We compare our diversity-aware solvers with state-of-the-art game solvers including self-play, PSRO (Lanctot et al., 2017), Pipeline-PSRO (McAleer et al., 2020), rectified PSRO (Balduzzi et al., 2019), and $\alpha$-PSRO (Muller et al., 2019). We investigate the performance of these algorithms on both NFGs and open-ended games. Our selected games involve both transitive and non-transitive dynamics. If an algorithm fails to discover a diverse set of policies, it will be trapped in some local strategy cycles that are easily exploitable (e.g., recall the illustrative example of the RPS-X game in Section 3.4, and see how our method can tackle this game in Appendix C. Therefore, we focus on the evaluation metrics of exploitability in Eq. (1) and how extensively the gamescapes are explored. We note that the confidence intervals represented in Figs. (2, 4a, 4b) represent the standard deviation in the exploitability at each iteration over multiple seeds, where the number of seeds is reported in Appendix G. One exception is the comparison between $\alpha$-PSRO and diverse $\alpha$-PSRO, since the solution concept is $\alpha$-Rank, instead of exploitability that measures distance to a NE, we apply the metric of PCS-score (Muller et al., 2019) – the number of SSCC that has been found – for fair comparison. We provide an exhaustive list of hyper-parameter and reward settings in Appendix G.

Real-World Meta-Games. We test our methods on the meta-games that are generated during the process of solving 28 real-world games (Czarnecki et al., 2020), including AlphaStar and AlphaGO. In Fig. (2), we report the results over the AlphaStar game that contained the meta-payoffs for $888$ RL policies, and report the results of the other 27 games in Appendix E. We used Algorithm 2 in Appendix H where agents are defined at the metagame level and correspond to mixed strategies of the underlying game. The results show that our diverse-PSRO method will, at worst, perform as well as existing PSRO baselines, but in many cases (e.g., Fig 2,3,4) will outperform in terms of exploitability, and will always outperform in terms of diversity. In particular, we believe that the performance advantage comes from the fact that without accounting for behavioural diversity, PSRO baselines tend to enter into a cyclic phase where repetitive strategies already in the population are found, whereas our diversifying measure can help discover novel strategies that consequently lead to lower exploitability. While many of the baselines have saturated in finding diverse strategies, our method keeps finding novel effective strategies which leads to a near zero exploitability in almost all $28$ games. In AlphaStar, our method achieves the best performance by only using less than $50$ out of $888$ RL policies, and with the population size growing, the exploitability keeps approaching zero while other methods saturate.

Non-Transitive Mixture Model. This game consists of seven equally-distanced Gaussian humps on the 2D plane. Each strategy corresponds to a point on the 2D plane, which, equivalently, represents the weights that each player puts on the humps, measured by the likelihood of that point in each Gaussian distribution. The payoff of the game that includes both non-transitive and transitive components is given by:

Since there are infinite number of points on the 2D plane, this game is open-ended. A winning player must learn to stay close to the Gaussian centroids whilst also exploring all seven Gaussians to avoid being exploited. In Fig. (3), we show the exploration trajectories for different algorithms along with the plot of exploitability vs. diversity. Results suggest that both PSRO and PSROrN fail to complete the task; we believe it is due to the same reason as RPS-X where strategy cycling occurs. In contrast, DPP-PSRO solves the task almost perfectly, reaching zero exploitability, by generating a population of diverse and effective strategies.

Colonel Blotto. Blotto is a classical resource allocation game that is widely analysed for election campaigns (Roberson, 2006). In this game, two players have a budget of coins which they simultaneously distribute over a fixed number of areas. An area is won by the player who puts the most coins, and the player that wins the most areas wins the game. We report the results on the game with $3$ areas and $10$ coins over $10$ games. We test how a diverse PSRO player performs in terms of exploitability against a PSRO and a PSROrN player, respectively. Fig. (4a) shows that our method (dark colours) consistently achieves a lower exploitability than the opponent player of either PSRO or PSROrN (light colours).

Diverse $\alpha$-PSRO. As the PBR in Eq. (6) requires looping through all strategies in $S^{i}$, we test our method on randomly generated zero-sum NFGs with varying dimensions. We do not employ the novelty-bound suggested in Muller et al. (2019) to illustrate how the original $\alpha$-PSRO displays strong cyclic behaviour, which stops it from finding even a few underlying SSCC elements. Results in Fig. (4b) suggest that our diverse $\alpha$-PSRO can effectively prevent the learner from exploring the same strategic cycles during training; it is therefore able to find more SSCCs of $\alpha$-Rank, and outperform $\alpha$-PSRO on the PCS-score.

Conclusion

We offer a geometric interpretation of behavioural diversity for learning in games by introducing a new diversity measure built upon the expected cardinality of a DPP. Based on the diversity metric, we propose general solvers for normal-form games and open-ended (meta-)games. We prove the convergence of our methods to NE and $\alpha$-Rank in two-player games, and show theoretical guarantees of expanding the gamescapes. On tens of games, our methods achieve lower exploitability than PSRO variants by finding both effective and diverse strategies.

References