A Generalized Training Approach for Multiagent Learning
Authors: Paul Muller
Shayegan Omidshafiei
Mark Rowland
Karl Tuyls
Julien Perolat
Siqi Liu
Daniel Hennes
Luke Marris
Marc Lanctot
Edward Hughes
Zhe Wang
Guy Lever
Nicolas Heess
Thore Graepel
Remi Munos
Venue:  (2020)
Keywords: multiagent learning
game theory
training
games

Abstract: This paper investigates a population-based training regime based on game-theoretic principles called Policy-Spaced Response Oracles (PSRO). PSRO is general in the sense that it (1) encompasses well-known algorithms such as fictitious play and double oracle as special cases, and (2) in principle applies to general-sum, many-player games. Despite this, prior studies of PSRO have been focused on two-player zero-sum games, a regime where in Nash equilibria are tractably computable. In moving from two-player zero-sum games to more general settings, computation of Nash equilibria quickly becomes infeasible.  Here, we extend the theoretical underpinnings of PSRO by considering an alternative solution concept, α-Rank, which is unique (thus faces no equilibrium selection issues, unlike Nash) and applies readily to general-sum, many-player settings. We establish convergence guarantees in several games classes, and identify links between Nash equilibria and α-Rank. We demonstrate the competitive performance of α-Rank-based PSRO against an exact Nash solver-based PSRO in 2-player Kuhn and Leduc Poker. We then go beyond the reach of prior PSRO applications by considering 3- to 5-player poker games, yielding instances where α-Rank achieves faster convergence than approximate Nash solvers, thus establishing it as a favorable general games solver. We also carry out an initial empirical validation in MuJoCo soccer, illustrating the feasibility of the proposed approach in another complex domain.

Published as a conference paper at ICLR 2020
A GENERALIZED TRAINING APPROACH FOR MULTIAGENT LEARNING
Paul Muller pmu Ter@...
Shayegan Omidshafiei somi deiidshaaiie
Mark Rowland ma markrow1 and@...........
Karl Tuyls Karltuyls@...
Julien Perolat perclate...
Siqi Liu liusiqie...
Daniel Hennes hennese...
Luke Marris marrise...
Mare Lanctot 1anctet
Edward Hughes edwa edwa rawaahhess.....
Zhe Wang zhewange...
Guy Lever guylever.....
Nicolas Heess heess@...
Thore Graepel thoreê...
Remi Munos munosê....
google.com com.
DeepMind.
ABSTRACT
This paper investigates population- bbssdd training regime based game-theoree principles called Policy-Spaced Response Oracles (PSRO). PSRO general in the that it (1) encompasses well-known algorithms such as fictitious play and double oracle as special cases, and (2) in principle applies to general-sum, many- player games. Despite this, prior studies of PSRO have been focused on two-player zero-sum games, a regime wherein Nash equilibria are tractably computable. In moving from two-player zero-sum games more general settings, computation of Nash equilibria quickly becomes infeasible. Here, we extend the theoretical underpinnings of PSRO by considering an alternative solution concept, a-Rank, which is unique (thus faces no equilibrium selection issues, unlike Nash) and applics readily to general-sum, many many-player settings. We establish convergence guarantees in several games classes, and identify links between Nash equilibria and a-Rank. We demonstrate the competitive performance of a-Rank-basee PSRO against exact Nash solver-based PSRO in 2-player Kuhn and Ledue Poker. We then go beyond the reach of prior PSRO applications by considering 3- to 5-player poker games, yielding instances where a-Rank achieves faster convergence than approximate Nash solvers, thus establishing it as favorable general games solver. We also carry out initial empirical validation in MuJoCo soccer, illustrating the feasibility of the proposed approach in another complex domain.
INTRODUCTION
Creating agents that learn to interact in large-scale systems a key challenge in artificial intelligence. Impressive results have been recently achieved in restricted settings (e.g., zero-sum, two-player games) using game-theoretic principles such as iterative best response computation (Lanctot et al. 2017). self-play (Silver al., 2018), and evolution- baase training (Jaderberg al., 2019 Liu et 2019). A key principle underlying these approaches is to iteratively train growing populatio lation of player policies, with population evolution informed by heuristic skill ratings (e.g., Elo (Elo) 1978) or game-theoretic solution concepts such Nash equilibria. A general application of this principle is embodied by the Policy-Space Response Oracles (PSRO) algorithm and its related extensions (Lanctot et al. 2017 Balduzzi et al., 2019). Given game (e.g., poker), PSRO constructs a higher- level meta- by simulating outcomes for match-ups upp of a population of players' policies. It then
trains new policies for each player (via oracle) against distribution over the existing meta-game

---

Published as a conference paper at ICLR 2020
policies (typically approximate Nash equilibrium, obtained via meta-solver appends these new policies to the meta- meta-game population, and iterates. In two-player zero sum games, fictitious play (Brown 195T), double oracle (McMahan et al. 2003), and independent reinforcement learning can all be considered instances of PSRO, demonstrating its representative power (Lanctot et al. 2017).
Prior applications of PSRO have used Nash equilibria as the policy-selection distribution (Lanctot et al. 2017) Balduzzi et al.) 2019). which limits the scalability of PSRO to general games: Nash
equilibria are intractable to compute in general (Daskalakis al. 2009); computing approximate
Nash equilibria is also intractable, even for some classes of two-player games (Daskalakis) (201);;
finally, when they can be computed, Nash equílibria suffer from selection problem (Harsanyi et al.,
1988 Goldberg et al. 2013). It is, thus, evident that the reliance of PSRO on the Nash equilibrium as the driver of population growth is a key limitation, preventing its application to general games. Recent work has proposed scalable alternative to the Nash equilibrium, called a-Rank, which applies readily to general games (Omidshafiei et al.) 2019), making a promising candidate for population-baseet training. Given that the formal study of PSRO has only been conducted under the restricted settings determined by the limitations of Nash equilibria, establishing its theoretical and empirical behaviors under alternative meta-solvers remains an important and open research problem.
We study several PSRO variants in the context of general-sum, many games, providing convergence guarantees in several classes of such games for PSRO instances that use a- c-Rank as a meta-solver. We also establish connections between Nash and o-Rank in specific classes of games, and identify links between o-Rank and the Projected Replicator Dynamics employed in prior PSRO instances (Lanctot et al. 2017). We develop a new notion of best response that guarantees convergence to the a-Rank distribution in several classes of games, verifying this empirically in randomly-generated general-sum games. We conduct empirical evaluations in Kuhn and Ledue Poker, first establishing our approach as competitive alternative to Nash-base based PSRO by focusing on two-player variants of these games that have been investigated in these prior works. We subsequently demonstrate empirical results extending beyond the reach of PSRO with Nash as meta-solver by evaluating training in 3- to 5-player games. Finally, we conduct preliminary evaluations in MuJoCo soccer (Liu et al., 2019), another complex domain wherein we use reinforcement learning agents as oracles in our proposed PSRO variants, illustrating the feasibility of the approach.
2
PRELIMINARIES
Games We consider K -player games, where each player & E [K] has a finite set of pure strategies S*. Let S = II S denote the space of pure strategy profiles. Denote by S == II14 S' the set of pure strategy profiles excluding those of player k. Let Ms) = (s). (s) Ms)s))
R
denote the vector of expected player payoffs for each s E S. A game is said to be zero-sum if Ee M (s) = 0 for all s S. A game said to be symmetric if all players have identical strategy sets Sh: and for any permutation p. strategy profile (s' (s"....,s$, xk) E S. and index & E [K]. one has mixed strategy profile is defined as π E As, a tuple representing the probability distribution over pure strategy profiles E S. The expected payoff to player under a mixed strategy profile π is given by M*(T)= Eves (*)))
Ms ....,, sk) = (s(()((s()) ...., ....,,)(K))
Nash Equilibrium (NE) Given a mixed profile π, the best response for player h is de- fined BR = arg maxved gh [M* (v, π ="). A factorized mixed profile (s) = Ih n (s*)
is a Nash equilibrium (NE) if T E BR+(T) for all k E [K]. Define NASHCONV(( Ex M M (BR*(T), (TT), π k) M*(T)) roughly speaking, this measures "distance" from an NE Lanctot al. 2017). In prior PSRO instances (Lanctot et al. 2017), a variant of the replicator dynamics (Tylorr and Jonker 1978; Maynard Smith and Price 1973). called the Projected Replicator Dynamics (PRD), has been used as an approximate Nash meta- solver (see Appendix F for details on PRD).
a-Rank While NE exist in all finite games (Nash 1950). their computation is intractable in general games, and their non-uniqueness leads to an equilibriu Prrium-sllection problem (Harsanyi et al., 1988) Goldberg et al.] 2013). This limits their applicability as the underlying driver of training beyond the two-player, zero-sum regime. Recently, an alternate solution concept called a- Rank was proposed by
AA meta-solver is method that computes, or approximates, the solution concept that is heing deployed.
2

---

Published as a conference paper at ICLR 2020
Randomly initialize player
I
Player 1ss pollcy set
Player kis policy set
Player K's policy set
M
Profile distrioution
Sk
S
Mata-solver M
Oracle O
Geme simulations
M
S
S
S
Profile
(a) Complete: compute missing payoff tensor M entries via game simulations.
(b) Solve: given the updated pay- off tensor M, calculate meta-
(c) Expand: append new policy to each player's policy space us- ing the oracle O.
strategy via meta-solver M.
Figure 1: Overview of PSRO(M, O) algorithm phases.
Omidshafiei al. (2019), the key associated benefits being its uniqueness and efficient computation in many-pie many-player and general-sum games, making it promising means for directing multiagent training.
The a-Rank distribution computed by constructing the response graph of the game: each strategy profile E of the game is node of this graph: directed edge points from any profile s E S to in the graph if (1) 8 and a differ in only single player k's strategy and (2) M² > M*)s). a-Rank constructs random walk along this directed graph, perturbing the process by injecting small probability of backwards-transition from a to s (dependent on parameter, a, whose value is prescribed by the algorithm); this ensures irreducibility of the resulting Markov chain and the existence of a unique stationary distribution, π E As, called the a-Rank distribution. The masses of supported by the sink strongly-connedt OOmidsaffiei et al. 2019). For more details on o-Rank, see Appendix and Rowland et al. 2019).
components (SSCCs) of the response graph
Oracles We define oracle O abstract computational entity that, given game, computes policies with precise associated properties. For instance, best-response oracle (²(TT) BR*(T) computes the best-response policy for any player k. given a profile æ. One may also consider ceepsiimatte-eetressppoee best-response oracles that, e.g., reinforcement learning to train player k's policy against a fixed distribution over the other players' policies, π Oracles play a key role in population- based training, they compute the policies that are incrementally added to players' growing policy populations (McMahan et al.) 2003 Lanctot et al. 2017 Balduzzi et al.) 2019). The choice of oracle O also affects the training convergence rate and final equilibrium reached (c.g., Nash or a-Rank).
approximate-bee
Empirical Game-theoretic Analysis PSRO relies on principles from empirical game-theoretic analysis (EGTA) (Walsh et al. 2002 Phelps et al. 2004 Wellman 2006). Given game (e.g., poker), EGTA operates via construction of higher-level 'meta-ge meta-game' where strategies correspond to policies (e.g., 'play defensively' in poker) rather than atomic actions (e.g., 'fold'). meta-payofff table M is then constructed by simulating games for all joint policy combinations, with entries corresponding to the players' expected utilities under these policies. Game-theoretic analysis can then be conducted on the meta-game in manner analogous to the lower-level game, albeit in much more scalable manner. As the thcoretical discussion hereafter pertains to the meta-game, we use s, M, and respectively refer policies, payoffs, and distributions at the meta-level, rather than the underlying low-level game. our analysis, will be important to distinguish between SSCCs of the underlying game, and of the meta-game constructed by PSRO; refer to the latter meta-SSCCs.
POLICY-SPACE RESPONSE ORACLES: NASH AND BEYOND
We first overview Policy-Space Response Oracles (PSRO) prior to presenting our findings. Given an underlying game (c.g., Poker), PSRO first initializes the policy space using randomly-generate policies, then expands the players' policy populations in three iterated phases: complete, solve, and
3

---

Published as a conference paper at ICLR 2020
Algorithm PSRO(M, O)
1: Initialize the players' policy set = II S* via random policies
2: for iteration E {1, 21,2,- ... do
3: Update payoff tensor M for new policy profiles in S via game simulations
(Fig.
4: Compute the meta-strateyy using meta-solver M(M)
(Fig
5:
Expand the policy space for each player k E [K] via S + 5h UO)
(Fig.
Game type
M
Converges to o-Rank?
SP
a- a-Rank
BR
(Example
SP
a-Rank
PBR
V (Sub-SSCC," Proposition 3
MP
a- a-Rank
BR
x (Example
MP
a-Rank
PBR
V (With novelty-bound oracle,
Proposition Appendix A.2
SP/ MP
Uniform or Nash
BR
X (Examples 4 and ||
Table
Theory overview. SP and MP, resp.. denote single and multi- coulti-oopulatinn games. BR and PBR, resp., denote best response and preference-basee best response. Defined in the noted propositions.
expand (see Algorithm aad [i the complete phase, meta-game consisting all match-ups of these joint policies is synthesized, with missing payoff entries in M completed through game simulations. Next, in the solve phase, meta-solver M computes a profile π over the player policies (e.g., Nash, a-Rank, uniform distributions). Finally, in the expand phase, an oracle O computes least one new policy & for each player & E [K]. given profile π. As other players' policy spaces S-k and profile æ A are fixed, this phase involves solving a single-player optimization problem. The new policies appended the respective players' policy sets, and the algorithm iterates. We use PSRO(M, O) to refer to the PSRO instance using meta-solver M and oracle O. Notably, PSRO-based training for two-player symmetric games can be conducted using single population of policies that is shared by all players (i.c., S is identical for all k). Thus, we henceforth refer to two- player symmetric games as single-population games', and more generally refer to games that require player-specific policy populations as imulti-populatin solely focused on Nash-based meta-solvers and best-response based oracles (Lanctot et al., 2017] Balduzzi al.) 20119), with theory focused around the two-player zero-sum case. Unfortunately, these guarantees do not hold in games beyond this regime, making investigation of alternative meta-solvers and oracles critical for further establishing PSRO's 's generalizability.
games'. Recent investigations of PSRO have
GENERALIZING PSRO THBORY
This section establishes theoretical properties of PSRO for several usefuu classes of general games. We summarize our results in Table [ giving full exposition below.
4.1 ESTABLISHING CONVERGENCE TO RANK
Player 2
A
B
C
D
X
is well-known that PSRO(Nash, BR) will eventually return an NE in two-player zero-sum games (McMahan et al. 2003). In more general games, where Nash faces the issues outlined earlier, a-Rank appears a promis- ing meta-solver candidate as it applies to many many-player, general-sum games and has no selection problem. How- ever, open questions remain regarding convergence guarantees of PSRO when using o- aaRan,, and whether standard BR oracles suffice for ensuring these guaran- tees. We investigate these theoretical questions, namely, whether particular variants of PSRO can converge the a-Rank distribution for the underlying game.
0
Ø
Ø
Player
B
2
1
C
-1
Φ²
-
0
-
0
X
E
0
Table 2: Symmetric zero-sum game used to analyze the behavior of PSRO in Example Here, 0 < E < and > 1.
first attempt to establish convergence to o- might involve running PSRO to convergence (until the oracle returns strategy already in the convex hull of the known strategies), using a-Rank the mota-solver, and a standard best response oracle. However, the following example shows that this will not work in general for the single-population case (see Fig. A.5 for step-by-step illustration).
4

---

Published as a conference paper at ICLR 2020
Example 1. Consider the symmetric zero-sum game specified in Table 2 As X is the sole sink component of the game's 's response graph (as illustrated in Fig. A.5a), the paaell-ppulttion a-Rank distribution for this game puts unit mass on X. We now show that PSRO algorithm that computes best responses to the o-Rank distribution over the current strategy set need not recover strategy X, by computing directly the strategy sets of the algorithm initialized with the set {C).
1. The initial strategy space consists only of the strategy C; the best response against C' is D.
2. The a-Rank distribution over (,C, D} puts all mass on D; the best response against D is A.
3. The o-Rann distribution over CC D, A} puts all mass on A; the best response against A is B.
4. The a-Rank distribution over {C, A, B) puts mass (1/s, 1/s, 1/6, 1/6) on (A. B, C, respec- tively. For & sufficiently large, the payoff that C receives against B dominates all others, and since B has higher mass than C in the o-Rank distribution, the best response is C.
Thus, PSRO(c-Rank, BR) leads to the algorithm terminating with strategy set {A, C,C, D) and not discovering strategy X in the sink grongly-connecter component.
This conclusion also holds in the multi-population case, the following counterexample shows.
Example 2. Consider the game in Table 2 treating it now as a multi-population problem. It is readily verified that the mulft-population R-Rann distributions obtained by PSRO with initial strategy sets consisting solely of C for each player are: (i) a Dirac delta at the joint strategy (C, C), leading to best responses of D for both players; (üi) a Dirac delta at (D, D) leading to best responses of A for both players; (iii) a Dirac delta at (A, A). leading to best responses of B for both players; and finally (iv) a distribution over joint strategies of the 4x subgame induced by strategies A, B,C. D C, that leads to best response not equal to X; thus, the full R-Rank distribution is again not recovered.
4.2
A NEW RESPONSE ORACLE
The previous examples indicate that the use of standard best responses in PSRO may be the root cause of the incompatibility with the a-Rank solution concept. Thus, define the Preference-based Best Response (PBR) oracle, which is more closely aligned with the dynamics defining a- a-Rank, and which enables us establish desired PSRO guarantees with respect a-Rank.
Consider first the popelalopttttionn case. Given an N-strategy population {si,..., &N} and corre- sponding meta-solver distribution (T; ) E AN, a PBR oracle is defined any function satisfying
PBR( Σ. T;8:) C max, Σ. m; [M*(o.s) > Mf(a,s))]
(1)
where the arg max returns the set of policies optimizing the objective, and the optimization is over pure strategies in the underlying game. The intuition for the definition of PBR is that we would like the oracle to return strategies that will receive high mass under a-Rank when added to the population: objective ( essentially encodes the probability flux that the vertex corresponding to a would receive in the random walk over the a- a-Rank response graph (see Section Appendix Dor further details).
We demonstrate below that the use of the PBR resolves the issue highlighted in Example 1 (see Fig. A.6 in Appendix A for an accompanying visual).
Example 3. Steps 1 3 of correspond exactly those of Example 7 In step the a-Rank distribution over {C, D, A, B} puts mass (1/3, 1/3, 1/8, 1/6) on (A, B, D, respectively. A beats C and D. thus its PBR score is 1/s. B beats A and D. thus its PBR score is 1/2. C beats B, its PBR score is thus 1/3. D beats C, its PBR score is thus 1/6. Finally, X beats every other strategy, and its PBR score is thus Thus, there is only one strategy maximizing PBR, X, which is then chosen, thereby recovering the SSCC of the game and the correct RaRa distribution at the next timestep.
In the multi- population case, consider a population of N strategy profiles {si..... and corre- sponding meta-solver distribution ( Several meta-SSCCs may exist in the R-Rk response graph. In this case, we run the PBR oracle for each meta-SSCC separately, as follows. Suppose there are l meta-SSCCs, and denote by (()) the distribution π restricted to the gth meta-SSCC, for all < < L. The PBR for player i on the gth meta-SSCC is then defined by
*BR (E, प: s.)) C arg max, Σ. T. (0)
> M (0
(2)
Thus, the PBR oracle generates one new strategy for each player for every meta-SSCC in the a a-Rank response graph; we return this full set of strategies and append to the policy space accordingly, as
5

---

Published as a conference paper at ICLR 2020
in Line 3 of Algorithm]] [ Intuitively, this leads diversification of strategies introduced by the oracle, as each new strategy need only perform well against a subset of prior strategies. This hints at interesting links with the
concept of rectified-Nase BR (Balduzzi al. 2019). which also attempts to improve diversity in PSRO, albeit only in two-player zero-sum games.
We henceforth denote PSRO(a-Rank, PBR) a-PSRO for brevity. We next define a-CONV, an approximate measure of convergence to a-Rank. We restrict discussion to the multi nupti-population case here, describing the single-population case in Appendix A..4 With the notation introduced above, we M s, })],
define PBR-SCORE" (o; ()) = E. Ee T. [M* (a,, >
and
a-CONV Ex max, SERR-SCOR*((
max PBR PBR-SCORE"(2 (C)
where maNo is laken over the pure strategies of the underlying game. Unfortunately, in the multi-population case, PBR-SCORE of 0 does not necessarily imply a-partial con- vergence. We thus introduce a further measure, PCS-SCORE, defined by PCS-SCORE = a PSRO strasegy profiles the underlying game's SSCCs which assesses the quality of the a-PSRO popula- of PSRS strategy profiles in mein-SSCCs
tion. We refer readers to Appendix C.3 for pseudocode detailing how to implement these measures in practice.
4.3 a-PSRO: THEORY, PRACTICE, AND CONNECTIONS TO NASH
We next study the theoretical properties of PSRO(a-Rank, PBR), which we henceforth refer as a-PSRO for brevity. We consider that a-PSRO has converged if no new strategy has been returned by PBR for any player at the end of an iteration. Proofs of all results are provided Appendix B Definition 1. A PSRO algorithm is said to converge a-fully (resp., a-partially) to an SSCC of the underlying game if its strategy population contains the full SSCC (resp.. a sub-cycle of the SSCC, denoted 'sub-SSCC") after convergence.
We also adapt PBR to be what we cull novelty-bound by restricting the arg max in Equation T to be over strategies not already included in the population with PBR-SCORE >
Definition 2.
In particular, the -oould version of the PBR oracle is given by restricting the arg max appearing in (2) to only be over strategies not already present in the population.
These definitions enable the following results for a-PSRO in the single- and multi multi-populatie population cases.
Proposition 1. If at any point the population of a-PSRO contains member of an SSCC of the game, then a-PSRO will o-partially converge to that SSCC.
Proposition 2. If we constrain the PBR oracle used in a-PSRO to novelty-bound, then a-PSRO will a--fully converge at least one SSCC of the game.
Stronger guarantees exist for two-players symmetric (i.e., single-population) games, though the multi-population case encounters more issues, as follows.
Proposition 3. (Single populaaio))) a-PSRO converges a-partially the unique SSCC.
Proposition 4. (Multi-populltiinn) Without novelty-bound oracle, there exist games for which a-PSRO does not converge a-partially to any SSCC.
Intuitively, the lack of convergence without a novelty- oracle can occur due to intransitivities in the game (i.e., cycles in the game can otherwise trap the oracle). An example demonstrating this issue shown in Fig. B.7 with an accompanying step-by-step walkthrough Appendix [B.4 Specifically, SSCCs may be hidden by "intermediate" strategies that, while not receiving as high payoff as current copulation-pool members, can actually lead to well-performing strategies outside the population. As these "intermediate" strategies are avoided, SSCCs are consequently not found. Note also that this is related to the common problem of action/cquilibrium shadowing, as detailed in Matignon et al. (2012).
In Section 5 we further investigate convergence behavior beyond the conditions studied above. In practice, we demonstrate that despite the negative result of Proposition 4 a-PSRO does significantly increase the probability of converging to an SSCC, in contrast to PSRO(Nash, BR). Overall, we have shown that for general-sum multi-player games, it is possible to give theoretical guarantees

---

Published as a conference paper at ICLR 2020
for version of PSRO driven by a-Rank in several cireumstances. By contrast, using exact NE in PSRO is intractable in general. In prior work, this motivated the use of approximate Nash solvers generally based on the simulation of dynamical systems or regret minimization algorithms, both of which generally require specification of several hyperparameters (e.g., simulation iterations, window sizes for computing time-average policies, and entropy-injectio rates), and greater computational burden than a-Rank to carry out the simulation in the first place.
Implementing the PBR Oracle Recall from Section that the BR oracle inherently solves a single- player optimization problem, permitting use of a single-agent RL algorithm as a BR approximator, which useful in practice. As noted in Section 4.1 however, there exist games where the BR and PBR objectives are seemingly incompatible, preventing the use of standard RL agents for PBR approximation. While exact PBR is computable in small-scale (e.g., normal-form form)) games, we next consider more general games classes where PBR can also be approximated using standard RI. agents.
Definition 3. Objective A is 'compatible" with objective B if any solution to A is a solution to B.
Proposition 5. A constant-sum game is denoted as win-loss if (s) E {0, 1} for all k E [K] and E S. BR is compatible with PBR in win-loss games in the two-player Sinle-pooulation case.
Proposition A symmetric two-player game is denoted monotonic if there exists a function f S + IR and a non-decreasing function a R. + IR such that M (s, v) = off(s) - f(v)). BR is compatible with PBR in monotonic games the single -oagulltpptttioon case.
Finally, we next demonstrate that under certain conditions, there are strong connections between the PBR objective defined above and the broader field of preference- based RL (Wirth et al. 2017).
Proposition 7. Consider symmetric win-loss games where outcomes between deterministic strategies are deterministic. A preference- based RL agent (i.e., an agent aiming to maximize its probability of winning against distribution π of strategies {s1....,5w] optimizes exactly the PBR objective
Given this insight, we believe important subject of future work will involve the use of preference- based RL. algorithms in implementing the PBR oracle for more general classes of games. We conclude this section with some indicative results of the relationship between a-Rank and NE.
Proposition 8. For symmetric two-player zero-sum games where off- off-diagonal payoffs have equal magnitude, all NE have support contained within that of the single-population a- Rank distribution.
Proposition 9. In a symmetric two-player zero-sum game, there exists an NE with support contained within that of the o-Rank distribution.
For more general games, the link between a-Rank and Nash equilibria will likely require a more complex deseription. We leave this for future work, providing additional discussion in Appendix A.3
EVALUATION
We conduct evaluations on games of increasing complexity, extending beyond prior PSRO applications that have focused on two-player zero-sum games. For experimental procedures, see Appendix C
Oracle comparisons We evaluate here the performance of the BR and PBR oracles in games where PBR can be exactly computed. We consider randomly generated, K -llayer, general-sum games with increasing strategy space sizes, | Figure 2 reports these results for the 4- and 5-player instances (see Appendix C.4 for 2-3 player results). The asymmetric nature of these games, in combination with the number of players and strategies involved, makes them inherently, and perhaps surprisingly. large in scale. For example, the largest considered game in Fig. 2 involves 5 players with 30 strategies each, making for a total of more than 24 million strategy profiles in total. For each combination of K and [S*) we generate 1e6 random games. We conduct 10 trials per game, in each trial running the BR and PBR oracles starting from a random strategy in the corresponding response graph, then iteratively expanding the population space until convergence. Importantly, this implies that the starting strategy may not even be in an SSCC.
As mentioned in Section 4.2 a-CoNV and PCS-SCORE jointly characterize the oracle behaviors in these muuli--ooullatee settings. FigurePalplor plots a-CONV for both oracles, demonstrating that PBR outperforms BR in the sense that it captures more of the game SSCCs. Figures 2h and 2c respectively,
7

---

Published as a conference paper at ICLR 2020
PCS-Score
PCS-Score
PCS-Score s
0.8
0.6
0.6-
04-
0.4
0.4
0.0
0.2
0.0
0.2
0.0
20
40
50
10
20
30
50
10
20
30
50
90
19
(89)
[89)
1.0
1.0
0.8
0.4
62
10
20
[87]
(a) a-CoNV
(b) SCORE O BR
(c) PCS-SCORE for O PBR
Figure 2: Oracle comparisons for seadooll-geneeatte games with varying player strategy space sizes
Top and bottom rows, respectively, correspond to 4- and 5-player games.
10
NashConv
Unifom
Rank
PRD (rectiflee)
0
(rectified)
10
10a
10a
102
Pool Length
Pool Length
(a) Kuhn poker.
(b) Ledue poker.
Figure 3: Results for 2-player poker domains.
plot the
for BR and PBR over all game instances. The
here is typically
either (a) greater than 95%, or (b) less than 5%, and otherwise rarely between 5% to 95%. For all values of | PBR consistently discovers larger proportion of the o-Rank support in contrast to BR, serving as useful validation of the theoretical results of Section 4.3
Meta-solver comparisons We consider next the standard benchmarks of Kuhn and Leduc poker (Kuhn) 1950 Southey et al. 2005 Lanctot et al., 2019). We detail these domains in Appendix C.2 noting here that both K -player, although Leduc is significantly more complex than Kuhn. We first consider two-player instances of these poker domains, permitting use of an exact Nash meta-solver. Figure compares the NASHCONV of PSRO(M, BR) for various meta-solver M choices. Note that the x axis of Figure 3 and Figure is the Total Pool Length (The sum of the length of each player's pool in PSRO) instead of the number of iterations of PSRO, since Rectified solvers can add more than one policy to the pool at each PSRO iteration (Possibly doubling pool size at every PSRO iteration). is therefore more pertinent to compare exploitabilities at the same pool sizes rather than at the same number of PSRO iterations.
In Kuhn poker (Fig. Baj, the a-Rank, Nash, and the Projected Replicator Dynamics (PRD) meta- solvers converge essentially the same rate towards zero NASHCONV, in contrast to the slower rate the Uniform solvesolver, the very slow rate of the Rectified PRD solver, and the scemingly constant N NASHCONV of the Rectified Nash solver. We provide in Appendix C.5 walkthrough of the first steps of the Rectified Nash results to more precisely determine the cause of its plateauing NASHCONV. A high level explanation thereof is that is caused by Rectified Nash cycling through the same policies, effectively not discovering new policies. We posit these characteristics, antipodal the motivation behind Rectified Nash, come from the important fact that Rectified Nash was designed to work only in symmetric games, and is therefore not inherently well-suited for the Kuhn and Ledue poker domains investigated here, as they are both asymmetric games. We did not add the Rectified PRD results the other, greater-than-2 players experiments, as its performance remained non-competitive.
As noted in Lanctot et al. 2017), PSRO(Uniform, BR) corresponds to Fictitious Play (Brown 1951) and is thus guaranteed to find an NE in such instances two-player zero-sum games. Its slower convergence rate is explained by the assignment of uniform mass across all policies E S, implying that PSRO essentially wastes resources on training the oracle to beat even poor-pes ppor-performing strategies. While a- a-Rank does not seek to find an approximation of Nash, nonetheless reduces the NASHCONv yielding competitive results in comparison to an exact-Nash solver in these instances. Notably, the similar performance of R-Rank and Nash serves empirical evidence that RaRk can be applied
8

---

Published as a conference paper at ICLR 2020
0.9
1.6
2.0
14-
NashCarv
0.7
1.0
1.4
12
10
a-Rank
0.8
1.0
PRD
Uniform
0.2
0.0
10
10
10
10a
10a
10
10'
10a
lteration
Iteration
Iteration
Iteration
(a) 3-player Kuhn.
(b) 4- 4-player Kuhn.
(c) S-plaeey Kuhn.
(d) 3-player Leduc.
Figure 4: Results for poker domains with than 2 players.
competitively in the two-player zero-sum setting, while also showing great promise to be deployed in broader settings where Nash is no longer tractable.
We next consider significantly larger variants of Kuhn and Ledue Poker involving players, extending beyond the reach of prior PSRO results (Lanctot et al. 2017). Figure visualizes the NASHCONV of PSRO using the various meta-solvers (with the exception of an exact Nash solver, due to its intractability in these instances). In all instances of Kuhn Poker, a-Rank and PRD show competitive convergence rates. In 3-player Leduc poker, however, a-Rank shows fastest convergence, with Uniform following throughout most of training and PRD eventually reaching similar NASHCONV. Several key insights can be made here. First, computation of an approximate Nash via PRD involves simulation of the associated replicator dynamics, which can be chaotic (Palaiopanos al., 2017) even in two-player two-strategy games, making it challenging to determine when PRD has suitably converged. Second, the addition of the projection step in PRD severs its connection with NE; the thcoretical properties of PRD were left open in Lanctot et al. 2017). leaving it without any guarantees. These limitations go beyond theoretical, manifesting practice. e.g., in Fig. 4d where PRD is outperformed by even the uniform meta-solver for many iterations. Given these issues, we take first (and informal) step towards analyzing PRD in Appendix EE] For o-Rank, by contrast, we both establish theoretical properties in Section 4 and face no simulation-related challenges its computation involves solving of linear system, even in the general-sum many-player case (Omidshafiei et al. 2019). thus establishing it as favorable and general PSRO meta-solver.
than two
MuJoCo Soccer While the key objective of this paper is take first step establishing theoretically-rront grouuded framework for PSRO-based training of agents in many-player settings, an exciting question regards the behaviors of the proposed a-Rank-based PSRO algorithm in complex domains where
based policies need to be relied upon. In Appendix [F) we take first step towards conducting this investigation in the MuJoCo soccer domain introduced in Liu et al. (2019). We remark that these results, albeit interesting, are primarily intended to lay the foundation for use of a-Rank as meta-solver complex many agent domains where RI. agents serve useful oracles, warranting additional research and analysis to make conclusive insights.
6 RELATED WORK
We discuss the most closely related work along axes. We start with PSRO-based research and some multiagent deep RL. work that focuses on training of networks in various multiagent settings. Then we continue with related work that uses evolutionary dynamics (a-Rank and replicator dynamics) as solution concept to examine underlying behavior of multiagent interactions using meta-games.
Policy-space response oracles (Lanctot et al. 2017) unify many existing approaches to multiagent learning. Notable examples include fictitious play (Brown] [951] Robinson 1951). independent
reinforcement learning (Matignon et al. 2012) and the double oracle algorithm (McMahan et al.
2003). PSRO also relies, fundamentally ly, on principles from empirical game-theorene analysis (EGTA) (Walsh et al. [0022] [Phelps et al. 2004 Tuyls et al. 2018 Wellman (006)) Vorobeychik
2010 Wiedenbeck and Wellman 201 2 Wiedenbeck et al. 2014). The related Parallel Nash Memory (PNM) algorithm (Oliehoek et al. 2006), which can also be seen
generalization of the double
oracle algorithm, incrementally grows the space of strategies, though using a search heuristic rather than exact best responses. PNMs have been successfully applied to games settings utilizing func- tion approximation, notably to address exploitability issues when training Generative Adversarial Networks (GANs) (Oliehoek et al. 2019).

---

Published as a conference paper at ICLR 2020
PSRO allows the multiagent learning problem to be decomposed into sequence of Mangl-agget learning problems. A wide variety of other approaches that deal with the multiagent learning problem without this reduction are also available, such Multiagent Deep Deterministic Policy Gradients (MADDPG) (Lowe et al. 2017), Counterfactual Multiagent Policy Gradients (COMA) (Foerster et al. 2018), Differentiable Inter-Agent Learning (DIAL) (Foerster al. 2016), Hysteretie Deep Recurrett Qleaannin (Omidshafici et al. 2017), and lenient Multiagent Deep Reinforcement Learning (Palmer al. 2018 Several notable contributions have also been made in addressing multiagent learning settings, most recently including the approaches of Igbal and Sha (2019); Gupta et al. (2017): Wei et al. (2018); Peng et al. (2017): Khadka et al. (2019). We refer interested readers to the following survey of recent deep multiagent RL approaches Hernandez-Leal
challenges in continuous-come
ct al. (019).
o-Rank was introduced by Omidshafiei et al. (019 as a scalable dynamic alternative to Nash equilibria that can be applied in general-sum, many-player games and capable of capturing the underlying multiagent evolutionary dynamics. Concepts from evolutionary dynamics have long been used analysis of multiagent interactions from a meta-game standpoint (Walsh al. 2002 Tuyls
and Parsons 2007 Hennes al., 2013: Bloembergen al., 2015 Tuyls al. 2018).
DISCUSSION
This paper studied variants of PSRO using a-Rank as meta-solver, which were shown to be competitive with Nash-based PSRO in zero-sum games, and scale effortlessly to general-sum many- player games, in contrast to Nash-based PSRO. We believe there are many interesting directions for future work, including how uncertainty in the meta-solver distribution, informed by recent developments in dealing with incomplete information games (Reeves and Wellman) 2004 Walsh al. 2003 Rowland et al. 2019), can be used to inform the selection of new strategies to be added to populations. In summary, we strongly believe that the theoretical and empirical results established in this paper will play a key role in scaling up multiagent training in general settings.
ACKNOLWEDGEMEENTS
The authors gratefully thank Bart De Vylder for providing helpful feedback on the paper draft.
REFERENCES
David Balduzzi, Marta Gamelo, Yoram Bachrach, Wojciech Czamecki, Julien Pérolat, Max Jader- berg, and Thore Graepel. Open-ended learning in symmetric zero-sum games. In International Conference on Machine Learning (ICML), 2019.
Daan Bloembergen, Karl Tuyls, Daniel Hennes, and Michael Kaisers. Evolutionary dynamics of multi-agent learning: A survey. J. Artif. Intell. Res. (JAIR), 33:659-697, 2015.
George W Brown. Iterative solution of games by fictitious play. Activity Analysis of Production and Allocation, 13(1):374-376 1951.
Ross Cressman and Yi Tao. The replicator equation and other game dynamics. Proceedings of the National Academy of Sciences USA, 1011100100000 2014.
Constantinos Daskalakis. On the complexity of approximating a Nash equilibrium. ACM Transactions on Algorithms,, 93):233 2013.
Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing a Nash equilibrium. SIAM Journal on Computing, 39(1):15-225, 2009.
Arpad E Elo. The rating of chessplayers, past and present. Arco Pub., 1978.
Jakob Foerster, Ioannis Alexandros Assael, Nando de Freitas, and Shimon Whiteson. Learning to communicate with deep multi-agent reinforcement learning. In Advances in Neural Information Processing Systems (NIPS), 2016.
10

---

Published as a conference paper at ICLR 2020
Jakob N Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In AAAI Conference on Artificial Intelligence, 2018.
Paul W Goldberg, Christos H Papadimitriou, and Rahul Savani. The complexity of the homotopy solutions. ACM Transactions on Economics
method, equilibrium selection, and and Compulation, 1(2):, 2013.
Jayesh K Gupta, Maxim Egorov, and Mykel Kochenderfer. Cooperative multi-agent control using deep reinforcement learning. In International Conference on Autonomous Agents and Multiagent Systems, pages 66-83. Springer, 2017.
John Harsanyi, Reinhard Selten, et al. A general theory of equilibrium selection in games. MIT Press Books, 1, 1988.
Daniel Hennes, Daniel Claes, and Karl Tuyls. Evolutionary advantage of reciprocity in collision avoidance. In AAMAS Workshop on Autonomous Robots and Multirobot Systems (ARMS), 2013.
Pablo Hermandez-Leal, Bilal Kartal, and Matthew E Taylor. A survey and critique of multiagent deep reinforcement learning. Autonomous Agents and Multi-Agent Systems, pages 1-48, 2019.
Shariq Iqbal and Fei Sha. Actor-attention-critee for multi-agent reinforcement learning. In Interna- tional Conference on Machine Learning, pages 2961-2970, 2019.
Max Jaderberg, Wojeiech M. Czarnecki, lain Dunning, Luke Marris, Guy Lever, Antonio Garcia Castañeda, Charles Beattie, Neil C. Rabinowitz, Ari S. Morcos, Avraham Ruderman, Nico- las Sonnerat, Tim Green, Louise Deason, Joel Z. Leibo, David Silver, Demis Hassabis, Koray Kavukcuoglu, and Thore Graepel. Human-level performance in 3D multiplayer games with population-based reinforcement learning. Science, 364(6443))859-8655 2019.
Shauharda Khadka, Somdeb Majumdar, and Kagan Tumer. Evolutionary reinforcement learning for samplc-efficien multiagent coordination. arXiv preprint arXiv: 2019.
Harold W Kuhn. A simplified two-person poker. Contributions to the Theory of Games, 1:97-103, 1950.
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. Neural Information Processing Systems (NIPS), 2017.
Marc Lanctot, Edward Lockhart, Jean-Baptiste Lespiau, Vinicius Zambaldi, Satyaki Upadhyay, Julien Pérolat, Sriram Srinivasan, Finbarr Timbers, Karl Tuyls, Shayegan Omidshafiei, Daniel Hennes, Dustin Morrill, Paul Muller, Timo Ewalds, Ryan Faulkner, János Kramár, Bart De Vylder, Brennan Sacta, James Bradbury, David Ding, Scbastian Borgeaud, Matthew Lai, Julian Schrit- twieser, Thomas Anthony, Edward Hughes, Ivo Danihelka, and Jonah Ryan-Davis OpenSpiel: A framework for reinforcement learning in games. arXiv preprint ar /908:
1908.008.000 09455, 2019.
Siqi Liu, Guy Lever, Josh Merel, Saran Tunyasuvunakool, Nicolas Heess, and Thore Graepel. Emer- gent coordination through competition. In International Conference on Learning Representations (ICLR), 2019.
Ryan Lowe, Yi Wu, Aviy Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-copptttie environments. In Advances in Neural Information Processing Systems (NIPS), 2017.
Lactitia Matignon, Guillaume Laurent, and Nadine Le Fort-Piat. Independent reinforcement learners in cooperative Markov games: A survey regarding coordination problems. The Knowledge Engineering Review, 27(1):1-31, 2012.
J. Maynard Smith and G. R. Price. The logic of animal conflicts. Nature, 246:15-18, 1973.
H. Brendan McMahan, Geoffrey J. Gordon, and Avrim Blum. Planning in the presence of cost functions controlled by an adversary. In International Conference on Machine Learning (ICML), 2003.
11

---

Published as a conference paper at ICLR 2020
Anna Nagumey and Ding Zhang. Projected dynamical systems and variational inequalities with applications, volume 2. Springer Science & Business Media, 2012.
John F Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences, 36(1):48 49, 1950.
Frans A. Oliehoek, Edwin D. de Jong, and Nikos Vlassis. The parallel Nash memory for asymmetric games. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pages
337-344, July 2006. doi: 10.1 10.1145/1144 143997.1 144997, 144059. UtLhttp:/ /www cs -baam ac uk/ wbw wtt/bibblioggecce22200
htts/p333/33333 pdf
(best paper nominee in coevolution track).
Frans A. Olichoek, Rahul Savani, Jose Gallego, Elise van der Pol, and Roderich GroB. Beyond local nash equilibria for adversarial networks. In Martin Atzmueller and Wouter Duivesteijn, A Intelligence, pages 73-89, Cham, 2019. Springer International Publishing, ISBN 978-3-030-31978-6
Shayegan Omidshafiei, Jason Pazis, Christopher Amato, Jonathan How, and John Vian. Deep decen- tralized multi-task multi-agent reinforcement learning under partial observability. In International Conference on Machine Learning (ICML), 2017.
Shayegan Omidshafiei, Christos Papadimitriou, Georgios Piliouras, Karl Tuyls, Mark Rowland, Jean-Baptiste Lespiau, Wojeiech M Czarnecki, Marc Lanctot, Julien Perolat, and Rémi Munos. a-Rank: Multi-agent evaluation by evolution. Scientific Reports, 9, 2019.
Gerasimos Palaiopanos, Ioannis Panageas, and Georgios Piliouras. Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos. In Neural Information Processing Systems (NIPS), 2017.
Gregory Palmer, Karl Tuyls, Daan Bloembergen, and Rahul Savani. Lenient agent deep reinforcement learning. In Autonomous Agents and Multiagent Systems (AAMAS), 2018.
Peng Peng, Ying Wen, Yaodong Yang, Quan Yuan, Zhenkun Tang, Haitao Long, and Jun Wang. Multiagent vidirectionally-coordiii coordinated nets: Emergence of human-level coordination in learning to play starcraft combat games. arXiv preprint
2017.
Steve Phelps, Simon Parsons, and Peter McBurney. An evolutionary game-theoe theoretic comparison of two double-auction market designs. In AAMAS Workshop on Agent-Mediated Electronic Commerce, 2004.
Daniel M Reeves and Michael P Wellman. Computing best-response strategies in infinite games of incomplete information. In Uncertainty in Artificial Intelligence (UAI), 2004.
Julia Robinson. An iterative method of solving a game. Annals of Mathematics, 54(2)2996-301, 1951.
Mark Rowland, Shayegan Omidshafiei, Karl Tuyls, Julien Perolat, Michal Valko, Georgios Piliouras. and Remi Munos. Multiagent evaluation under incomplete information. To appear in Neural Information Processing Systems (NeurIPS), 2019.
Peter Schuster and Karl Sigmund. Replicator dynamics. Journal of Theoretical Biology, 100(3): 533-538, 1983.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, and Demis Hassabis. A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science, 362(6419):1140-1111 2018
Finnegan Southey, Michael Bowling, Bryce Larson, Carmelo Piccione, Neil Burch, Darse Billings. and Chris Rayner. Bayes' bluff: Opponent modelling in poker. In Uncertainty in Artificial Intelligence (UAI), 2005.
Peter D Taylor and Leo B Jonker. Evolutionary stable strategies and game dynamics. Mathematical Biosciences, 40(1-2):145-156 1978.
12

---

Published as a conference paper at ICLR 2020
Karl Tuyls and Simon Parsons. What evolutionary game theory tells us about multiagent learning. Artif. Intell., 171(7):4064415 2007.
Karl Tuyls, Julien Perolat, Mare Lanctot, Joel Z Leibo, and Thore Graepel. A generalised method for empirical game theoretic analysis. In Autonomous Agents and Multiagent Systems (AAMAS), 2018.
Yevgeniy Vorobeychik. Probabilistic analysis of simulation-based games. ACM Trans. Model. Comput. Simul., 20(3):16:1-16:25 October 2010.
William E Walsh, Rajarshi Das, Gerald Tesauro, and Jeffrey O Kephart. Analyzing complex strategic interactions in multi-agent systems. In AAAI Workshop on Game Theoretii and Decision-Theoreti Agents, 2002.
William E Walsh, David C Parkes, and Rajarshi Das. Choosing samples to compute heuristic-strategy Nash equilibrium. In International Workshop on Agent-Mediated Electronic Commerce, pages 109-123, Springer, 2003.
Ermo Wei, Drew Wicke, David Freelan, and Sean Luke, Multiagent soft q-learning. In 2018 AAAI Spring Symposium Series, 2018
Michael P Wellman. Methods for empirical game-theoretic analysis. In AAAI Conference on Artificial Intelligence, 2006.
Bryce Wiedenbeck and Michael P. Wellman. Scaling simulation- based game analysis through deviation-preserving reduction. Autonomous Agents and Multiagent Systems (AAMAS). 2012.
Bryce Wiedenbeck, Ben-Alexander Cassell, and Michael Wellman. Bootstrap statistics for empirical games. In Autonomous Agents and MultiAgent Systems (AAMAS), pages 597-604, 2014.
Christian Wirth, Riad Akrour, Gerhard Neumann, and Johannes Fürnkranz. A survey of preference- based reinforcement learning methods. The Journal of Machine Learning Research, 18(1):4945- 4990, 2017.
13

---

Published as a conference paper at ICLR 2020
APPENDICES
14

---

Published as a conference paper at ICLR 2020
A
EXAMPLES
A.1
FURTHER EXPOSITION OF EXAMPLES 1 AND
Player 2
A
B
C
D
X
A
0
E
B
6
0²
E
Player 1
C
Φ²
Φ
-
D
-
X
&
(a) Overview, Full payoff table left, full response graph on right, with values over directed edges indicating the payoff gained by deviating from one strategy to another.
Player 2
A
B
C
D
X
A
0
Ø
B
Ø
0
0
Player 1
C
-1
Ø²
0
D
-1
0
-
X
0
Consider initial strategy space consisting only of the strategy C: the best response against C is D.
Player 2
A
D
X
0
Φ
E
6
2
-
Player
C
-1
-
-
-6
X
8
0
(c) The R-Rank distribution over {C, D} puts all mass on D; the best response against D is A.
Player 2
A
B
C
D
X
A
0
B
Φ
x²
Player 1
C
-1
Ø
D
1
-
X
(d) The R-Rank distribution over (C, D, A} puts all mass on A; the best response against
Player 2
A
D
X
0
6
B
-
Player 1
C
-1
Φ
0
-
D
-1
0
-
X
8
0
(c) The a- RaRa distribution over {C, D, A, B} puts mass (1/3, 1/s, 1/8, 1/6) (A, B, C, D) respectively, For sufficiently large, the payoff that C receives against B dominates others, and since B has higher mass than the a-Rank distribution, the best response C.
Figure A.5:
Example with oracle O BR. In each step above, the o-Rank support is highlighted by the light green box of the payoff table, and the BR strategy against it in bold, dark green.
15

---

Published as a conference paper at ICLR 2020
Player 2
A
D
X
A
0
0
Ø
-
B
0
0
-
Player 1
C
1
Φ
0
D
-1
0
-
X
6
8
0
(e) The a- Ra-a distribution over {C, D, A, B} puts mass (4/s, 1/s, 1/6, 1/6) on (A, B, C, D) respectively. A beats C' and D. and therefore its PBR score is 1/3. B beats A and D. therefore its PBR score is 1/2. C' beats B, its PBR score is therefore 1/s. D beats C, its PBR score is therefore 1/6. Finally, X beats every other strategy. and its PBR score is thus There only one strategy maximizing PBR, X, which is then chosen, and the SSCC the game, recovered.
Figure A.6: Example with oracle PBR. Steps their analogs in Fig. A.5
to d are not shown as they are identical to
A.2 EXAMPLE BEHAVIOR OF PSRO(NASH, BR)
first attempt to establish convergence to o-Rank might involve running PSRO to convergence (until the oracle returns a strategy already in the convex hull of the known strategies), and then running a-Rank on the resulting meta- meta--ame. However, the following provides a counterexample to this approach when using either PSRO(Nash, BR) PSRO(Uniform, BR).
Player B
Player 2
A
X
B
A
0
1
S
A
-1
1
Player 1
B
0
-6
Player
B
X
-
E
0
X
-E/2
4xample
(b) Example
Table 3:
Illustrative games used to analyze the behavior of PSRO in Example 4 Here, 0 < & << 1.
The first game symmetric, whilst the second is zero-sum. Both tables specify the payoff to Player under each strategy profile.
Example 4. Consider the two-player symmetric game specified in Table 3a The sink strongly- connected component of the single-population response graph (and hence the a- Ra-R distribution) contains all ihree strategies, but all NE are supported on {A, B} only, and the best response to strategy supported on {A, B} is another strategy supported on {A, B}. Thus, the single-population variant of PSRO, using M {Nash, Uniform} with initial strategies contained in {A, B} will terminate before discovering strategy X; the full a- R-Rank distribution will thus not be recovered.
Example Consider the two-player zero-sum game specified in Table 3b) All strategy profiles recieve non-zero probability in the multi- malti-pppuulatin a-Rank distribution. However, the Nash equilibrium over the game restricted to actions A, B for each player has a unique Nash equilibrium of (1/2, 1/2). Player I's best response to this Nash is to play some mixture of A and B, and therefore strategy X is not recovered by PSRO,Nash, BR) in this case, and so the full a R-Rank distribution will thus not be recovered.
A.3 COUNTEREXAMPLES a- a-RANK VS. NASH SUPPORT
The Game of Chicken The Game of Chicken provides example where the support of a- a-Rank- in the multipopulation case - does not include the full support of Nash Equilibria.
This game has three Nash equilibria: Two pure, (D,C) and (C,D), and one mixed, where the population plays Dare with probability 1. Nevertheless, o-rank only puts weight on (C,D) and (D,C), effectively not putting weight the full mixed-nash support.
16

---

Published as a conference paper at ICLR 2020
Player 2
D
C
D
(0. 0)
(7,2)
Player 1
C
(2, 7)
(6,6)
Table Game of Chicken payoff table
Prisoner's Dilemma
The Prisoner's Dilemma provides counterexample that the support of a- Rank- in the multi-population case does not include the full support of correlated equilibria.
Player 2
C
D
(0,0)
(3, -1)
Player
3
(2.2)
Table 5: Prisoner's Dilemma payoff table
This game has correlated equilibria that include (C,D), (D,C) and (C,C) in their support: nevertheless, o-Rank only puts weight (D,D), effectively being fully disjoint from the support of the correlated equilibria.
A.4 POGGLE-POPULTIOO a-CONV
In analogy with the pulti-poopulaion definition in Section 4.2 we define a single-population ver- sion of a-CONV. We start by defining the single-population version of PBR-Score, given by
PBR-SCORF(;; ., S) = Σ. n. (M M then defined
M (o,, The single-population a-CoNv is
a- CONV max PBR- (CORESC max PBR (BR-SC
#ES
where max, is taken over the pure strategies of the underlying game.
17

---

Published as a conference paper at ICLR 2020
B PROOFS
B.1 PROOF OF PROPOSITION
Proposition If at any point the population of a-PSRO contains member of an SSCC of the game, then a-PSRO will o--partially converge to that SSCC.
Proof. Suppose that a member of one of the underlying game's SSCCs appears in the a-PSRO population. This member will induce its meta-SSCC in the meta-game's response graph. At least one of the members of the underlying game's ' corresponding SSCC will thus always have positive probability under the o-Rank distribution for the meta-gand game, and the PBR oracle for this meta-SSCC will always return a member of the underlying game's SSCC. If the PBR oracle returns a member of the underlying SSCC already in the PSRO population, we claim that the corresponding meta-SSCC already contains cycle of the underlying SSCC. To see this, note that if the meta-SSCC does not contain cycle, must singleton. Either this singleton is equal to the full SSCC of the underlying game (in which we have a-fully converged), or it is not, in which case the PBR oracle must return new strategy from the underlying SSCC, contradicting our assumption that has terminated.
D
B.2 PROOF OF PROPOSITION
Proposition 2.
If we constrain the PBR oracle used in a-PSRO to be novelty-bound, then a-PSRO will o-ffully converge to at least one SSCC of the game.
Proof. Suppose that a- a-PSRO has converged, and consider a meta-SSCC Since a-PSRO has con- verged, it follows that each strategy profile of the meta-SSCC is element of an SSCC of the underlying game. Any strategy profile in this SSCC which is not the meta-SSCC will obtain positive value for the PBR objective, and since a- a-PSRO has converged, there can be such strategy profile. Thus, the meta-SSCC contains every strategy profile contained within the corresponding SSCC of the underlying game, and therefore conclude that a-PSRO a-fully converges an SSCC of the underlying game.
B.3 PROOF OF PROPOSITION 3
Proposition (Single-population).. a-PSRO converges a-partially to the unique SSCC.
Proof. The uniqueness of the SSCC follows from the fact that in the response graph is fully-connected. Suppose at termination of a-PSRO, the a-PSRO population contains strategy within the SSCC, and let be strategy in the SSCC. We claim that attains higher value for the objective defining the PBR oracle than any strategy in the a-PSRO population, which contradicts the fact that a~PSRO has terminated. To complete this argument, we note that by virtue of s being in the SSCC, we have M (s. s') > M (s', s) for all s' outside the SSCC, and in particular for all s' E S, thus the PBR objective for s objective for is upper-bounded by 1 --; If π. > 0, then this shows is not selected by the oracle, since the objective value lower than that of s. If π.; = 0, then the objective value for s; is 0, and so an SSCC member will always have a maximal PBR score of 1 against a population not composed of any SSCC member, and members of that population have < 1 PBR scores. Consequently, single- population a- a-PSRO cannot terminate before it has encountered SSCC member. By Proposition the proposition is therefore proven.
case, the
In contrast, for any 8; S, the PBR
B.4 PROOF OF PROPOSITION
Proposition (Multi (ouullipopplltion) Without novelty-bound oracle, there exist games for which a-PSRO does not converge c-partially to any SSCC.
Proof. We exhibit a specific counterexample to the claim. Consider the three player, three-strategy game with response graph illustrated in Fig. B.7a note that do not enumerate all strategy profiles not appearing in the SSCC for space and clarity reasons. The sequence of updates undertaken by o-PSRO in this game is illustrated in Figs. B.7b B.7f. whilst the singleton strategy profile (3,2,
2,
18

---

Published as a conference paper at ICLR 2020
forms the unique SSCC for this game, a-PSRO terminates before reaching it, which concludes the proof. The steps taken by the algorithm are described below; again, we do not enumerate all strategy profiles not appearing in the SSCC for space and clarity reasons.
Begin with strategies [[2] [1] [4]] in the a-PSRO population (Player only has access to strategy
2, Players 2 and 3 only have access strategy 1)
2. The PBR to (2.1,1) for player 2 is 2, and no other player has a PBR on this round. We add
2 to the strategy space of player 2, which changes the space of available joint strategies to
[22, 1, 1), (2, 2, 1)]-
3. Q-Rank puts all its mass on (2,2,1). The PBR to (2,2,1) for player is 2. and no other player has
PBR on this round. We add strategy 2 to player 3's strategy space, which changes the space of available joint strategies to [22 1, 1), (2, 2, 1), (2, 2.)].
4. o-Rank puts all its mass on (2,2,2). The PBR to (2,2,2) for player 1 is 1, and no other player has PBR on this round. We add strategy to player I's strategy space, which changes the space of available joint strategies to I,), (1,1,2), (1,2, 1), (1, 2, 2), (2, 1, 1), (2, 2, 1), (2, 2, 2)].
5. Define a as the a-Rank probabilities of the meta-game. Player playing strategy 2 has PBR score of ((11, 1, 1)) + ((1, 2, 1)), and the same player playing strategy has PBR score of ((11,, 2, 1)), which is lower than the PBR Score of playing strategy 2. No other player has a valid PBR for this round, and therefore, a-PSRO terminates.
relatively weak joint strategy (Strategy (3,2,1) bars agents from finding the optimal joint strategy of the game (Strategy (3,2,3)) getting to this joint strategy requires coordinated changes between agents, and is therefore closely related the common problem of Action/Equiltrriun Shadowing mentioned in (Matignon et al. 2012)
In the above example, pictured in Fig. B.7
B.5 PROOF OF PROPOSITION 5
Proposition 5. A constant-sum sun game denoted as win-loss if Ms E 10 for all l E [K] and E S. BR is compatible with PBR in win-loss games in the two-player single-populaiin case.
Proof. We manipulate the best-response objective as follows:
M (v, π))
Σ (v,
S
(8) M (u,8) (T(1,))]
Noting that the final line is the single-population PBR objective, we done.
B.6 PROOF OF PROPOSITION 6
Proposition A symmetric two-player game is denoted monotonic if there exists function f + IR and a non-decreasing function R such that M² (s, af((s) s(T)) BR is compatible with PBR in monotonic games in the single-population case.
Proof. Rewriting the objectives given that the game is monotonic, we have that the value-based objective becomes
K
M (s, 5k) Σ TTo(f(s) - f(x)))
Given the fact that the only condition we have on a is its non-decreasing character, this objective does not reduce to maximizing fs) in the general case.
The objective for PBR is
K
Th L (s, 22
Σ
mello(((s) f(su) > a(f(su) f(6)))
19

---

Published as a conference paper at ICLR 2020
3,2.3
20.20.20
5,21
1M
4.33
222
AA3
2,11
2.11
2,2,1
1,22
10:01
11.5
(a) Full response graph.
(b) a-PSRO Step 1.
335
333
2.1
10.0.11
(c) a-PSRO Step 2.
(d) a-PSRO Step 3.
MM
1,311
1,12
333
15.
2,11
2,111
333
3.33
10/0.1
61G
10.00.
5.16
2,22
22.
11.5
1.16
(c) a-PSRO Step
a-PSRO Step
Figure B.7: The three-player, three-strategy game serving as counterexample in the proof of Proposition Strategy profiles are illustrated by gray circles, with payoff's listed beneath. All strategy profiles not pictured are assumed to be dominated, and are therefore irrelevant in determining whether a-PSRO reaches an SSCC for this game.
20

---

Published as a conference paper at ICLR 2020
Since is non-decreasing,
off(s) f(x))) > off(s)) - f(s)) f(s) > f(sN)
and conversely,
f(s) > f(sx) + o(f(s) - f(s))) 2 (f((s)) f(s))
Without loss of generality, we reorder the strategies such that if < k, f(x)) f(x))
Let Sy maximize the value objective. Therefore, by monotonicity, s, maximizes off(s) f(sk)). Three possibilities then ensue.
If there exists s such that
o(f(s) - f(sk)) > ((f(s)) - f()))
then
- -
since Su maximizes (f((s) ( f(sk)) and is non-decreasing. Consequently sy maximizes the PBR objective. Indeed, let remark that for all & S K, we have that
o(f(se) f(s))) > o(f(s)) f(s,))
since
(f(s)) - f(s))) 2 off(s.) - f(sx)) ((((k)) - f(s.)) 2 (f((sk) - f(so)
Else, there does not exist any policy such that o(f(s) f(sk)(( o(f(sx) - f()),, that is, for all
<f(()) - f(*x)) < (f((k) - f(8))
Since Sy is possible solution to the value objective,
aff(s.) f(x)) <(((k)) f(s))
Let be the integer such that Sy. arg max( 8% Population Bs s.t. off(s) f(ss)) > o(f(s)) f()))
If 8n exists, then we have that for all 8; such that f(x;) f(8x),
(f(s.) - f=x))= (s) - f(s,))
=
The PBR objective
Txl(o(f((s) f(st)) > a(f(s)) f()))
which, according our assumptions, is equivalent
Σ Tx ((s)) ((((s)) [()))]
We know that for all i S n, (f((s)) - s(si)) > (x))) (sw)), and therefore, maximizes the PBR objective.
Finally, 8n doesn't exist, then any policy is solution to the PBR objective, and therefore 8, is. Li
toy example showing the compatibility between Best Response and Preference-based Best Response is shown in Fig. B.8 The setting is that of monotonic game where every strategy is assigned number. Strategies are then dominated by all strategies with higher number than theirs. We compute initial population composed of one strategy that we choose to be dominated by
BR and PBR every other strategy. Any strategy dominating the current population a valid solution for PBR, represented in Fig. [B.cc] whereas, if consider that the game is monotonic with strictly increasing function, only one strategy maximizes Best Response, strategy and is thus the only solution of BR, shown in Fig. B.8d
As we can see, the solution of BR is part of the possible solutions of PBR, demonstrating the result of Proposition BR is compatible with PBR in monotonic games.
21

---

Published as a conference paper at ICLR 2020
(a) Full response graph of monotonic game.
(b) Starting population (green).
(c) Current population (green) and possible solutions (d) Current population (green) and possible solution of BR (yellow).
of PBR (yellow)
Figure B.8: Toy example of compatibility between PBR and BR: The solution returned by BR is one of the possible solutions of PBR.
B.7 PROOF PROPOSITION
Proposition 7. Consider symmetric win-loss gumes where outcomes between deterministic stralegies are deterministic. A preference- bareeeence-baeedd RL agent (i.e., an agent aiming to maximize its probability of winning against distribution of strategies {$1...., optimizes exactly the PBR objective (1.
Proof. Commencing with the above preference-based RL objective, we calculate as follows,
arg max
a beats Σ T;S;
arg max Eg (P beats s, jindex selected)]
N
arg max
T (a beats s;)
arg max
la receives a positive expected payoff against s;)
with the final equality whenever game outcomes between two deterministic strategies are deterministic. Note that this is precisely the PBR objective (
B.8 PROOF OF PROPOSITION
Proposition 8. For symmetric two-player zero-sum games where off-diagonal payoffs have equal magnitude, all NE have support contained within that of the single-population a-Rank distribution.
Proof. In the sagglloopulation case, the support of the a-Rank distribution is simply the (unique) sink strongly-connecte component of the response graph (uniqueness follows from the fact that the response graph, viewed as an undirected graph, fully-connected). We will now argue that for strategy in the sink strongly-connected component and strategy outside the sink strongly- connected component, we have
(s,a) > Σ (
(3)
aES
aES
This inequality states that when an opponent plays according π. the expected payoff the row playeria is greater if they defect to whenever they would have played z. This implies that if a supposed symmetric Nash equilibrium contains strategy outside the sink strongly-connected component in its support, then it could receive higher reward by playing instead, which contradicts the fact that it an NE. We show Firstly, since is the sink strongly-connected component and is not, beats and so M (s, M (s = M' (z, 2) > M (z, s). Next, if {s. 2 is in the sink strongly-connecter component, then beats and so M (s.a) M (2, a) if beats a, and M (s, a) M (z, a) otherwise. Finally, if * s, 2 is not in the sink strongly-comme connected component, then M (s, a) = M (2, a) beats 0, and M a) M a) otherwise. Thus, is proven, and the result follows.
3 by proving stronger result - namely, that s dominates z as strategies.
22

---

Published as a conference paper at ICLR 2020
B.9 PROOF OF PROPOSITION
Proposition 9. In a symmetric two-player zero-sum game, there exists an NE with support contained within that of the o-Rank distribution.
Proof. Consider the restriction of the game to the strategies contained in the sink strongly-connectee component the original game. Let π be an NE for this restricted game, and consider this as distribution over all strategies in the original game (putting 0 mass strategies outside the sink component). We argue that this an NE for the full game, and the statement follows. To see this, note that since any strategy outside the sink strongly-conneet connected component receives a non non-positive payoff when playing against strategy in the sink strongly-connectee component, and that for at least one strategy in the sink strongly-connected component, this payoff is negative. Considering the payoffs available to the row player when the column player plays according to π, we observe that the expected payoff for any strategy outside the sink trrongl-coonnctedd component is negative, since every strategy in the sink strongly-conneeted component beats the strategy outside the component. The payoff when defecting strategy in the sink srrongly-connecee component must non-positeee poni-oosiive, since an NE for the restricted game.
23

---

Published as a conference paper at ICLR 2020
C ADDITIONAL DETAILS ON EXPERIMENTS
C.I EXPERIMENTAL PROCEDURES
The code backend for the Poker experiments used OpenSpiel (Lanctot et al. 2019), Specif- ically, we used OpenSpiel's Kuhn and Leduc poker implementations, and exact best responses were computed by traversing the game tree (see implementation details in open sippen_speel________eee_eeee___e wython/algoriitass/Berrs wttpbbessterrrpseeeeeeeeeeeeeeee py). 100 game simulations were used to estimate the payoff matrix for each possible strategy pair.
Although the underlying Kuhn and Ledue poker games are stochastic (due to random initial card deals), the associated meta-games are essentially deterministic (as, given enough game simulations, the mean payoff's are fixed). The subsequent PSRO updates are, thus, also deterministic.
Despite this, we report averages over 2 runs PSRO M, primarily capture stochasticity due to differences machine-specific rounding errors that occur due to the distributed computational these experiments
platforms
For experiments involving a- e-Rank, we conduct full sweep over the ranking-intensinn parameter, a, following each iteration of --RO We implemented version of a- a-Rank (building the Open- Spiel implementation htttp::/ ceten_spee/ppyttee http http//lppaaaaaaaaa py) that used sparse representation for the underly- ing transition matrix, enabling scaling-up up to the large-scale NFG results presented in the experiments.
com/ deepmi pepemmnndi// hediiin/ppenn /epennpen__eeeeeeeeeeeeeeeeeeeee harp/oppe_sppceeee spiel/bl ob/ ab/mass ster/
For experiments involving the projected replicator dynamics (PRD), used uniformly initiiiit meta-distributions, running PRD for 5e4 iterations, using a step-size dt = 1e - 3, and exploration parameter 7 1e 10. Time-averaged distributions computed the entire trajectory.
C.2 DOMAIN DESCRIPTION GENERATION
C.2.1 NORMAL FORM GAMES GENERATION
Algorithms to provide overview of the procedure use randomly-generate normal-form games for the oracle comparisons visualized Fig.
Algorithm 2 GenerateTranssiiv(CAcioon, Players, meanvalue [0.0, 1.0), mcanproaabliityy [0.5, 0.5).
var 0.1)
1: T=
2: for Player do
3: Initialize fa [0] Actions
4: for Action a S Actions
5:
Randomly sample mean from meanvalue according to mealpobahiliy
6: fula] ~ (p, var)
7: for Player & do
8:
T[k]
Players -I Eiqz fr
9: Return T
Algorithm 3 GenerateCCyliccAAttionn, Players, var = 0.4)
1: C=1
2: for Player do
3: Initialize Ckk] ~ (O, var), Shape(C'[k) =
(ace))=(AAAiinss (Actionsyin Players
Actions Last Player)
4: for Player do
5: Sum = Actions a; of player if Ciki[ai,.... : 0k-1; ; ...t1....]
6: Shape(Sum) = (1...., ., Actionsp ky 1, 1,
7: C[k] = C(k] Sum
8: Return C
24

---

Published as a conference paper at ICLR 2020
Algorithm 4 General Normal Form Games Generation(Actions, Players)
1: Generate matrix lists T Generate TemeeaateTransiiive(AAcioo Players), C GenerateCyylicc(Attionn
Players)
2: Return [T[]] C[k] for Player k]
C.2.2 KUHN AND LEDUC POKER
K K-player Kuhn poker is played with deck of K + cards. Each player starts with 2 chips and 1 face-down card, and antes chip to play. Players either bet (raise/call) or fold iteratively, until each player is either in (has contributed equally the pot) has folded. Amongst the remaining players, the one with the highest-ranked card wins the pot.
Leduc Poker, in comparison, has significantly larger state-space. Players in Leduc have unlimited chips, receive face-down card, ante chip to play, with subsequent bets limited to 2 and chips in rounds I and 2. A maximum of two raises are allowed in each round, and public card revealed before the second round.
C.3 PBR COMPUTATION IN NORMAL FORM GAMES
The algorithms used to compute PBR and PBR-SCORE the games generated by the algorithm described in Section C.2.1 is shown in Algorithms Sand Note that they compute the multipopulation version of PBR. PCS-SCORE Score computed by pre-computing the full game's 's SSCC, and computing the proportion of currently selected strategies in the empirical game that also belongs the full game's s SSCC.
Note that the PBR-SCORE, and PCS-SCORE useful measures for assessing the quality of con- vergence in our examples, in a manner analogous to NASHCONV. The computation of these scores is, however, not tractable in general games. Notably, this is also the case for NASHCONY (as it requires computation of player-wise best responses, which can be problematic even in moderately- sized games). Despite this, these scores remain useful way to empirically verify the convergence characteristics in small games where they can be tractably computed.
Algorithm 5 PBR Score(Strategy S, Payoff Tensor, Current Player Id, Joint Strategies, Joint Strategy Probability)
1: New strategy score = 0
2: for Joint strategy J, Joint probability Joint Strategies, Joint Strategy Probability do
3: New strategy J
4: New Errategy[Curree Player S
5: New strategy payoff Payoff [ensor[New Strategy]
6: Old strategy payoff = Payoff Tensor[J]
7: New strategy score += * (New Strategy Payoff Old Strategy Payoff)
8: Return New strategy score
Algorithm 6 PBR(Payoff Tensor list LM, Joint Strategies per player PJ, Alpharank Probability per Joint Strategy PA, Current Player)
1: max 0
2: maXstrat = None
3: for Strategy S available to Current Player among all possible strategies do
4: score PBR Score(S, LM[Current Player Id], Current Player Id, PJ, PA)
5: if New Strategy Score > max then
6: maxpBR = New Strategy Score
7: maXstrat = S
8: Return maxęви, max,trat
25

---

Published as a conference paper at ICLR 2020
C.4 ADDITIONAL ORACLE COMPARISON RESULTS
We present additional oracle comparisons in Fig. C.9
all of these in the multi-populltion case.
C:: BR
C: PBR
PCS-Sc PCS-Score 0.95
PCS-Score (0.05, 0.95)
PCS-Score 0.05
04
0.0
0.0
0.2
0.0
02
200
400
600
800
1000
200
400
600
500
1000
200
400
600
800
1000
(9*
(89)
(87)
1.0
0.0
0.2
0.0
0.2
0.0
20
40
50
84
70
83
90
120
10
20
30
40
50
60
100
90
300
10
30
50
70
80
100
1.0
1.0
0.8
0.8
0.8
0.4
10
30
[8*]
0.8
0.8
0.5
0.6
0.6-
0.4
0.4
0.2
0.0
0.0
10
15
20
[69]
[65]
(a) Co-C
(b) PESPPCCSSRRRS for BR
(c) -CS-SCCOE for PBR
Figure C.9: Oracle comparisons for vandomly-generate normal-form games with varying player
strategy space sizes | The rows, order, correspond to 5 5-player games.
C.5 NOTES ON RECTIFIED NASH PERFORMANCE
This section provides additional insights into the Rectified Nash results detailed Section We begin with an important disclaimer that Rectified Nash was developed solely with symmetric games in mind. As Kuhn Poker and Leduc Poker are not symmetric games, they lie beyond the theoretical scope of Rectified Nash. Nevertheless, comparing the performance of rectified and non-rectified approaches from an empirical perspective yields insights, which may be useful for future investigations that seek potentially extend and apply rectified training approaches more general games.
As noted the main paper, the poor performance of PSRO using Rectified Nash (in Fig. 3 is initially the players'
surprising indicates premature convergence to high-NA Cong-N distribution policy pools. Investigating this further led to a countcrintuitive result for the domains evaluated: Rectified Nash was, roughly speaking, not increasing the overall diversity of behavioral policies added to each player's population pool. In certain regards, it even prevented diversity from emerging.
To more concretely pinpoint the issues, we detail below the first 3 iterations PSRO(Rectified Nash, BR) in Kuhn Poker. Payoff matrices at each PSRO iteration are included in Tables 6a to (6c For clarity, we also include the best responses trained by Rectified Nash and the policies they were trained against, in their order of discovery: 2 policies for Player (in Fig. C.11 and 3 policies for Player (in Fig. C.
1. Iteration 0: both players start with uniform random policies.
2. Iteration 1:
Player trains best response against Player 2's uniform random policy; its policy set now the original uniform policy, and the newly-computed best response.
Player 2 trains best response against Player I's uniform random policy; its policy
now the original uniform policy, and the newly-computed best response.
Player 2's best response beats both of Player I's policies.
Payoff values represented in Table 6a
26

---

Published as a conference paper at ICLR 2020
NashConv
1.0
Diversity
Unform
Rank
10
0.5
PRD Nash
PRD (recified) (fectffeed)
0.0
10a
10a
10a
10a
Total Pool Length
Total Pool Length
(a) Kuhn poker Exploitability.
(b) Kuhn poker Diversity.
Figure 10: Policy Exploitability and Diversity in 2-player Kuhn for a given seed and 100 simulations per payoff entry.
3. Iteration 2:
By Rectified Nash rules, Player I only trains policies against policies it beats; i.e., only against Player 2's random policy, and thus it adds the same policy as in iteration to its pool.
Player 2 trains a best response against the Nash mixture of Player I's first best response and random policy. This policy also beats all policies of player 1.
Payoff values are represented in Table 6b
4. Iteration 3:
Player only trains best responses against Player 2's random policy.
Player 2 only trains best responses against the Nash of Player I's two unique policies.
This yields the same policies for player 2 as those previously added to its pool (i.e.,
loop occurs).
Payoff values are represented in Table 6c
5. Rectified Nash has looped.
As noted above, Rectified Nash loops at iteration 3, producing already-existing best responses against Player I's policies. Player is, therefore, constrained to never being able train best responses against any other policy than Player 2's random policy. In turn, this prevents Player 2 from training additional novel policies, and puts the game in a deadlocked state.
Noise in the payoff matrices may lead to different best responses against the Nash Mixture of policies, effectively increasing diversity. However, this effect did not seem to manifest in our experiments. To more clearly illustrate this, we introduce means of evaluating the policy pool diversity, counting the number of unique policies in the pool. Specifically, given that Kuhn poker is a finite state game, comparing policies is straightforward, and only amounts to comparing each policy's 's output all states of the games. If two policies have exactly the same output on all the game's states, they are equal; otherwise, they distinct. We plot in Fig. C. policy diversity of each meta-solver, where we observe that both Rectified Nash and Rectified PRD discover a total of different policies. We have nevertheless noticed that in few rare seeds, when using low number of simulations per payoff entry (Around 10), Rectified Nash was able to converge to low exploitability scores, suggesting relationship between payoff noise, uncertainty and convergence of Rectified Nash whose investigation we leave for future work. We also leave the investigation of the relationship between Policy Diversity and Exploitability for future work, though note that there appears to be a clear correlation between both. Overall, these results demonstrate that the Rectified Nash solver fails to discover as many unique policies as the other solvers, thereby platcauing at a low NASHCONV.
Finally, regarding Rectified PRD, which performs better in terms of NASHCONV when compared to Rectified Nash, we suspect that payoff noise in combination with the intrinsic noise of PRD, plays key factor- but those two not enough to deterministically make Rectified PRD converge to O exploitability, since in the seed that generated Fig. C.10 actually doesn't 't (Though it indeed converges in Fig. 3). We conjecture this noisier behavior may enable Rectified PRD to free itself from deadlocks more easily, and thus discover more policies on average. more detailed analysis of Rectified PRD is left future work.
27

---

Published as a conference paper at ICLR 2020
PCLl Duazi
8.50
8.00
0.00
8.50
5.50
2.00
0.50
5.00
VUSI
5.50
5.00
5.30
6.00
0050
6000
8.00
5:00
020
5.50
1:00000
430
2.30
500
L3
6.90
2.30
0.3
455
626
0:0 K00
E9 1.50
3.50
(a) Initial (uniform) policies.
ou
(b) Player I's first best response indicated in blue, and the policy best-responded against in red.
Figure 1.11: Game tree with both players' policies visualized. Player 1 decision nodes and action probabilities indicated, respectively, by the blue square nodes and blue arrows. Player 2's are likewise shown via the red counterparts.
28

---

Published as a conference paper at ICLR 2020
8.30
14
39
(a) Initial (uniform) policies.
Bd
Rss
Bi:
Pow 10
Plue
Fas
Srac Dec
Pash Se
Fam Dkc
De:
FLR Bx
Pack Ee:
(b) Player 2's first best response indicated in red, and the policy it best-responded against in blue.
Dati
Deuld
0/5
6J5
0.25
4/S
1m0
5:30
100
1:30
100
100
te
000
10100 W0
100 mnB
80
mm
5.00
(c) Player 2's second best response indicated in red, and the policy it best-responded against in blue.
Figure 12: Game tree with both players' policies visualized. Player 1 decision nodes and action probabilities indicated, respectively, by the blue square nodes and blue arrows. Player 2's are likewise shown via the red counterparts.
29

---

Published as a conference paper at ICLR 2020
0. 0.1014 0.4903
-0.4287
-0.1794
(a) Iteration 1.
10.1014
-0.4287
-0.2461
-0.22847
0.4903
-0.1794
-0.4988
-0.5228
0.5169
-0.1726
-0.4946
-0.5
0.5024
-0.1832
-0.4901
-0.5066
(b) Iteration
10.1014
00.2287
-0.2461
-0.2284
-0.264
-026602
-0.2505
0.4903
-0.1994
-0.4988
-0.5228
-0.5055
-0.5501
-0.5159
0.5169
-0.1726
-0.4946
-0.5
-0.5261
-0.5279
-0.4979
0.5024
-0.1832
-0.4901
-0.5066
-0.5069
-0.4901
-0.5033
0.4893
-0.1968
-0.5084
-0.4901
-0.5015
-0.4883
-0.4796
0.4841
-0.1496
-0.8992
-0.491
-0.4724
-0.4781
-0.5087
0.5179
-0.1769
-0.033
00.21
-0.4991
-0.4739
-0.4649
0.4959
-0.1613
0.5123
0.518
-0.5126
-0.5039
-0.4853
(c) Iteration
Table 6: PSRO(Rectified Nash, BR) evaluated 2-player Kuhn Poker. Player I's payoff matrix shown for each respective training iteration.
30

---

Published as a conference paper at ICLR 2020
D Q-RANK IN DETAIL
In this section we give further details of o-Rank; for a full deseription, see Omidshafiei et al. (2019). Essentially a-Rank defines directed response graph over the pure strategy profiles of the game under study, by indicating when a player has an incentive to make a unilateral deviation from their current strategy. An irreducible (noisy) random walk over this graph is then defined, and the strategy profile rankings are obtained by ordering the masses of this Markov chain's 's unique invariant distribution æ.
The Markov transition matrix C that specifies this random walk is defined as follows for the multi- population case; see (eeidsshaiii et al. (2019) for the single-population case. Consider pure strategy profile & E S, and k, which uses strategy oḥ E S instead of s* Let C..o denote the transition probability from s to and C..a the self-transition probability 8, with each defined as:
= (o* s >> be the pure strategy profile which equal to s, except for player
1-exp(- -app--a(p (M)
Cs
! 11-exp( (c)
if (o) # (s) otherwise
Σ C.a: KE[K]
C2,5 =
ola* ola"Est\\6')
where 77
- -1) If two strategy profiles and s' differ in more than player's strategy, then C.,s' = 0. Here a 2 and m E are parameters to specified; the form of this transition probability is described by evolutionary dynamics models from evolutionary game theory and is explained more detail in Omidshafiei et al.] (2019). Large values of a correspond to higher selection pressure in the evolutionary model under consideration; the version of a-Rank used throughout this paper corresponds to the limiting invariant distribution as a - oo, under which only strategy profiles appearing in the sink strongly-connected components of the response graph have positive mass.
31

---

Published as a conference paper at ICLR 2020
E TOWARDS THEORETICAL GUARANTEES FOR THE PROJECTED REPLICATOR DYNAMICS
Computing Nash equilibria is intractable for general games and can suffer from a selection problem (Daskalakis et al.) 2009); therefore, it quickly becomes computationally intractable to employ an exact Nash meta-solver in the inner loop of PSRO algorithm. To get around this, Lanctot al. (201)) use regret minimization algorithmss to attain an approximate correlated equilibrium (which is guaranteed to be an approximate Nash equilibrium under certain conditions on the underlying game, such as two-player zero-sum) A dynamical system from evolutionary game theory that also converges to equilibria under certain conditions is the replicator dynamics (Taylor and Jonker 1978) Schuster and Sigmund 1983 Cressman and Tao 2014 Bloembergen et al. 2015), which defines
dynamical system over distributions of strategies (t)
1 [K]. S*), given by
(t) = -T (s π * (t)) - M (TT (t))
for all & E [K]. SE E
(4)
with an arbitrary initial condition. Lanctot et al. (2017) introduced a variant of replicator dynamics, termed projected replicator dynamics (PRD), which projects the flow of the system so that each distribution π (t) lies in the set A3 = { E As π. 2 7/([5*1 | + 1), Vs E S* see, e.g., Nagumny and Zhang (2012) for properties of such projected dynamical systems. This heuristically enforces additional "exploration" relative to standard replicator dynamics, and was observed to provide strong empirical results when used as a meta- solvrr within PSRO. However, the introduction of projection potentially severs the connection between replicator dynamics and Nash equilibria, and the theoretical -heerethc properties of PRD were left open in Lanctot et (2017).
Here, we take a first step towards investigating theoretical guarantees for PRD. Specifically, we highlight a possible connection between a-Rank, the calculation of which requires no simulation, and a constrained variant of PRD, which we denote the single-mutatiin PRD' (or s-PRD), leaving formal investigation this connection for future work.
Specifically, s-PRD is dynamical system over distributions (1)k E [K], E S*) that follows the replicator dynamics (equation with initial condition restricted so that each To lies on the 1-skeleton A g
(1) { E As EsEst I S 2). Further, whenever a strategy distribution of enters a 8-corner of the simplex, defined by A = f E A the non-zero element of π (t) with mass most 5 is replaced with uniformly randomly chosen strategy after a random time distributed according to Exp(μ). for some small μ >> O. This concludes the description of s-PRD. We note at this stage that s-PRD defines, essentially, dynamical system on the 1-skeleton (or edges) of the simplex, with random mutations towards a uniformly-sami randomly strategy profile at the simplex vertices. At high-level, this bears close resemblance to the finite-population a-Rank dynamics defined in Omiidsaaiiii et al. (2019); moreover, we note that the connection between s-PRD and true a-Rank dynamics becomes even more evident when taking into account the correspondence between the standard replicator dynamics and a-Rank that is noted in Omidshatici al. (2019) Theorem 2.1.4).
3s E S* s.t. π. 2 1 5}.
We conclude by noting a major limitation of both s-PRD and PRD, which can limit their practical applicability even assuming a game- theoretic grounding can be proven for either. Specifically, with all such solvers, simulation of a dynamical system is required to obtain an approximate equilibrium, which may be costly in itself. Moreover, their dynamics can be chaotic even for simple instances of two-player two-strategy games (Palaiopanos et al. 2017). In practice, the combination of these two limitations may completely shatter the convergence properties of these algorithms in practice, in the sense that the question of how long wait until convergence becomes increasingly difficult (and computationally expensive) to answer. By contrast, a- a-Rank does not rely on such simulations, thereby avoiding these empirical issues.
We conclude by remarking again that, albeit informal, these results indicate a much stronger theoretical connection between a- R-Rank and standard PRD that may warrant future investigation.
32

---

Published as a conference paper at ICLR 2020
F MUJoCo SOCCER EXPERIMENT
While the key objective of this paper is to take a first step in establishing a poanetticall-grronndde framework for PSRO-basee training of agents in many-player settings, exciting question concerns the behaviors of the proposed a-Rank-based PSRO algorithm in complex domains where function- approximation-based policies need to be relied upon for generalizable task execution. In this section, we take preliminary step towards conducting this investigation, focusing in particular on the MuJoCo soccer domain introduced in Liu al. (2019) (refer httpt:
com/ deepmind, for the corresponding
3mm_onttrd /teee//te//ee//eeeeeeeeeeeeeeeet pareeemaases wtaasterr/e / htmmmmmmmmcco/ wwt0mmmoooorrroooe domain code).
In particular, we conduct two sets of initial experiments. The first set of experiments compares the performance of PSRO(a-Rands RL) and PSRO(Uniform, RL) in games of vs. 3 MuJoCo soccer, and the second set compares PSRO(a-Rank, RL) against a population-based training pipeline in 2 vs. 2 games.
F.1 TRAINING PROCEDURE
For each of the PSRO variants considered, we compose hierarchical training procedure composed of two levels. At the low-level, which focuses on simulations of the underlying MuJoCo soccer game itself, we consider a collection of 32 reinforcement learners (which we call agents) that are all trained at the same time, as in Liu et al. (2019). We compose teams corresponding to multiple clones of agent per team (yielding homogeneous teams, in contrast to (Liu et al. 2019), which evaluates teams of heterogeneous agents) and evaluate all pairwise team match-ups. Note that this yields 2- ""playerr meta-game (where each "player" is actually a team, i.e., a team-vs. vs.-team setting), with payoffs corresponding to the average win-rates of each team when pitted against each other.
The payoff matrix is estimated by simulating matches between different teams. The number of simulations per entry is adaptive based on the empirical uncertainty observed on the pair-wise match outcomes. In practice, we observed an average of 10 to 100 simulations per entry. with fewer simulations used for meta-payoffs with higher certainty. For the final evaluation matrix reported in Appendix (Fig. F. F,10), which was computed after the conclusion of PSRO-basee training. 100 simulations used per entry. Additionally, instead of adding one policy per PSRO iteration per player we add three (which corresponds to the 10% best RL agents).
Several additional modifications were made standard PSRO to help with the inherently more difficult nature of Deep Reinforcement Learning training:
Agent performance, used choose which agents out of the 32 add to the pool, measured by the u--ank-average for PSRO(a-Rank, RL) and Nash-average for PSRO(Uniform, RL) of agents in the (Agents, Pool) vs (Agents, Pool) game.
Each oracle step in PSRO is composed of billion learning steps of the agents. After each step. the top 10% of agents (the 3 best agents) are added to the pool, and training of the 32 agents continues:
We 50% probability of training using self-play (the other 50% training against the distribution of the pool of agents).
F.2 RESULTS
In the first set of experiments, we train the PSRO(a-Rank, RL) and PSRO(Uniform, RL) agents independently (i.e., the two populations never interact with one another). Following training, we compare the effective performance of these two PSRO variants by pitting their 8 best trained agents against one another, and recording the average win rates. These results are reported in Fig. F.13 for games involving teams of 3 vs. 3. It is evident from these results that PSRO(a- Rank, RL) significantly outperforms PSRO(Uniform, RL). This is clear from the colorbar on the far right of Fig. F.13 which visualizes the post-training alpharank distribution over the payoff matrix of the metagame composed of both training pipelines.
In the second set of experiments, we compare a- PPRO-basee training to self-play- training (i.c., sampling opponents uniformly at random from the training agent population). This provides means
33

---

Published as a conference paper at ICLR 2020
Alpharank
Uniform
Alpharank
Uniform
Figure F.13: a-PSRO versus PSRO(Uniform, BR) in the MuJoCo Soccer domain. Left is the matrix representing the probability of winning for a-PSRO and PSRO(Uniform, BR)'s best agents. Right is the a-Rann distribution over the meta-game induced by these agents. Yellow are high probabilities, dark-blue low probabilities. The diagonal taken be
of gauging the performance improvement solely due PSRO; these results reported in Fig. F.14 for games involving teams of vs. 2.
We conclude by remarking that these results, although interesting, primarily intended lay the foundation for use of a-Rank as meta-solver in complex many agent domains where RI. agents serve as useful oracles; additionally, more extensive research and analysis is necessary to make these results conclusive in domains such as MuJoCo soccer. We plan to carry out several experiments along these lines, including extensive ablation studies, in future work.
34

---

Published as a conference paper at ICLR 2020
Self pay training
sipha trairing
Sellspaay training
ap training
Figure F.14: a-PSRO training pipeline training pipeline without PSRO.
35


Reviews:
[{"review_id": "r1xBh9CaYS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Review Update (18/11/2019)\nThank you for the detailed replies and significant updates to the paper in response to all reviewers. You have comfortably addressed all of my concerns and so I have updated my score. I think the paper has improved significantly through the rebuttal stage and therefore the update in my score is also significant to match the far larger contribution to the community that the paper now represents.\n\n--\nThis paper considers alpha-rank as a solution concept for multi-agent reinforcement learning with a focus on its use as a meta-solver for PSRO. Based on theoretical findings showing shortcomings of using the typical best response oracle, the paper finds a necessity for a new response oracle and proposes preference-based best response.\n\nThe theoretical contributions help further the community's understanding of alpha-rank but the method remains somewhat disconnected from other recent related literature. Therefore, I think the paper's subsequent impact could be significantly improved by making more direct comparison to recent results. Specifically:\n\n1) In the 2-player games comparisons are currently made to PRD based on its use in Lanctot et al (NeurIPS, 2017) instead of the more recent PSRO Rectified Nash approach proposed by Balduzzi et al. (ICML, 2019). Please make this direct comparison or justify its exclusion.\n\n2) The preliminary MuJoCo soccer results in Appendix G significantly increase the relevance of this work to the ICLR community given the prior publication of this environment at ICLR 2019. However, the results are currently incomplete. In particular, to again strengthen the link to existing work, comparison of the method proposed in this paper to the agents trained by population based training in Liu et al. (ICLR, 2019) would be a more informative comparison than the preliminary results presented in comparison to the naïve uniform meta-solver.\n\n3) Appendix A includes a brief literature survey. This is important material to position the paper in relation to existing work, particularly for readers not familiar with the area that will rely on this to understand the paper as a self contained reference. Please move this section into the main body of the paper and expand to fully credit the work this paper builds upon.\n\n\nMinor Comments:\nIn Appendix C.4 should the reference to Figure C.7 be to Figure C.7a specifically? and the reference to Figure C. 7a be to Figure C. 7b-f inclusive? If so, I believe the available joint strategies in step 4 is missing (1,1,2) as shown in Figure C. 7f.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1eXzEgTtS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper extends the original PSRO paper to use an $\\alpha$-Rank based metasolver instead of the projected replicator dynamics and Nash equilibria based metasolvers in the original. To this end, the paper modifies the original idea of Best-Response (BR) oracle since it can ignore some strategies in $\\alpha$-Rank defining SSCC to introduce the idea of _preference-based_ Best-Response (PBR) oracle. The need for a different oracle is well justified especially with the visualization in the Appendix. The main contributions that the paper seems to be going for is a theoretical analysis of $\\alpha$-Rank based PSRO compared to standard PSRO. From the PBR's description (especially in Sec 4.3) it seems the paper is intereseted in expanding the population with novel agents rather than finding the \"best\" single agent which is not well defined for complex games with intransitivities. Nevertheless, it seems that BR is mostly compatible with PBR for symmetric zero-sum two-player games.\nThe paper performs empirical experiments on different versions of poker. First set of experiments compare BR and PBR with $\\alpha$-Rank based metasolver on random games and finds that PBR does better than BR at population expansion as defined. The second set of experiments compare the metasolvers. $\\alpha$-Rank performs similarly to Nash where applicable. Moreover it's faster than Uniform (fictitious self-play) on Kuhn. Then the paper tacks on the MuJoCo soccer experiment as a teaser for ICLR crowd.\n\nOverall the paper is quite interesting from the perspective of multiagent learning and I would lean towards accepting. However the paper needs to clarify a lot of details to have any chance of being reproducible.\n\n** Clarifications needed:\n\n- Tractability of PBR-Score and PCS-Score\nIt's unclear how tractable these are. Moreover these were only reported for random games. What did these scores look like for the Poker games? Could you clarify how exactly these were computed?\n\n- It's somewhat unclear what the lack of convergence without novelty-bound oracle implies. Does this have to do with intransitivities in the game?\n\n- Dependence of $\\alpha$?\nThe original $\\alpha$-Rank paper said a lot about the importance of choosing the right value for $\\alpha$. How were these chosen? Do you do the sweep after every iteration of PSRO?\n\n- Oracle in experiments?\nThe paper fails to mention the details about the Oracles being used in the experiments. They weren't RL oracles but more details would be useful. \n\n- BR not compatible with PBR, albeit not the other way around, meaning one of the solutions you get from PBR might be BR, but can we say which one?\n\n- For MuJoCo soccer was it true PSRO or cognitive hierarchy. In general, the original PSRO paper was partly talking about the scalable approach via DCH. This paper doesn't mention that at all. So were the MuJoCo experiments with plain PSRO? What was the exact protocol there? From the appendix it's unclear how the team-vs-team meta game works with individual RL agents. Moreover how are the meta-game evaluation matrices computed in general? How many samples were needed for the Poker games and MuJoCo soccer?\n\n- The counterexamples in Appendix B3 are quite interesting. Do you have any hypotheses about the disjoint support from games' correlated equilibria?", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1lMGBlhtH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies α-Rank, a scalable alternative to Nash equilibrium, across a number of areas. Specifically the paper establishes connections between Nash and α-Rank in specific instances, presents a novel construction of best response that guarantees convergence to the α-Rank in several games, and demonstrates empirical results in poker and soccer games. \n\nThe paper is well-written and well-argued. Even without a deep understanding of the subject I was able to follow along across the examples and empirical results. In particular, it was good to see the authors clearly lay out where their novel approach would work and where it would not and to be able to identify why in both cases. \n\nMy only real concern stems from the empirical results compared to some of the claims made early in the paper. Given the strength of the claims comparing the authors approach and prior approaches, it seems that the empirical results are somewhat weak. The authors make sure to put these results into context, but given the clarity of the results in the toy domains I would have expected clearer takeaways from the empirical results as well. \n\nEdit: The authors greatly improved the paper, addressing all major reviewer concerns.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper analyzes and extends learning methods based on Policy-Spaced Response Oracles (PSRO) through the application of alpha-rank.  In doing so, the paper explores connections with Nash equilibria, establishes convergence guarantees in multiple settings, and presents promising empirical results on (among other things) 3-to-5 player poker games.

Although this paper originally received mixed scores, after the rebuttal period all reviewers converged to a consensus. A revised version also includes new experiments from the MuJoCo soccer domain, and new poker results as well.  Overall, this paper provides a nice balance of theoretical support and practical relevance that should be of high impact to the RL community. 
Decision: Accept (Talk)