Iterative Empirical Game Solving via Single Policy Best Response
Authors: Max Smith
Thomas Anthony
Michael Wellman
Venue: ICLR 2021 Spotlight (2021)
Keywords: Empirical Game Theory
Reinforcement Learning
Multiagent Learning

Abstract: Policy-Space Response Oracles (PSRO) is a general algorithmic framework for learning policies in multiagent systems by interleaving empirical game analysis with deep reinforcement learning (DRL).
At each iteration, DRL is invoked to train a best response to a mixture of opponent policies.
The repeated application of DRL poses an expensive computational burden as we look to apply this algorithm to more complex domains.
We introduce two variations of PSRO designed to reduce the amount of simulation required during DRL training.
Both algorithms modify how PSRO adds new policies to the empirical game, based on learned responses to a single opponent policy.
The first, Mixed-Oracles, transfers knowledge from previous iterations of DRL, requiring training only against the opponent's newest policy.
The second, Mixed-Opponents, constructs a pure-strategy opponent by mixing existing strategy's action-value estimates, instead of their policies.
Learning against a single policy mitigates conflicting experiences on behalf of a learner facing an unobserved distribution of opponents.
We empirically demonstrate that these algorithms substantially reduce the amount of simulation during training required by PSRO, while producing equivalent or better solutions to the game.

Published as a conference paper at ICLR 2021
ITERATIVE EMPIRICAL GAME SOLVING VIA SINGLE POLICY BEST RESPONSE
Max Olan Smith University of Michigan mxsmi th@umi ch. edu
Thomas Anthony
Michael P. Wellman
Deepmind twa Zwa@google ee. e com
University of Michigan we 1 1 ma nê umi .accchee
ABSTRACT
Policy-Space Response Oracles (PSRO) is a general algorithmic framework for learning policies in multiagent systems by interleaving empirical game analysis with deep reinforcement learning (Deep RL). At each iteration, Deep RL is invoked to train a best response to a mixture of opponent policies. The repeated application of Deep RL poses an expensive computational burden as we look to apply this algorithm more complex domains. We introduce two variations of PSRO designed to reduce the amount of simulation required during Deep RL training. Both algorithms modify how PSRO adds new policies to the empirical game, based on learned responses opponent policy. The first, Mixed-Oracles, transfers knowledge from previous iterations of Deep RL, requiring training only against the opponent's 's newest policy. The second, SixxedOOpponent,, constructs a pure-strategy opponent by mixing existing strategy' 's action-value estimates, instead of their policies. Learning against single policy mitigates variance state outcomes that is induced by an unobserved distribution opponents. We empirically demonstrate that these algorithms substantially reduce the amount of simulation during training required by PSRO, while producing equivalent or better solutions to the game.
single
INTRODUCTION
In (single-agent) reinforcement learning (RL), an agent repeatedly interacts with an environment until it achieves mastery, that is, can find no further way improve performance (measured by reward). In multiagent system, the outcome of any learned policy may depend pivotally on the behavior of other agents. Direct search over a complex joint policy space for game solutions daunting, and so more common in approaches combining RI. and game theory is to interleave learning and game analysis iteratively.
In empirical game-theoretic analysis (EGTA), game reasoning is applied to approximate game models defined over restricted strategy sets. The strategies are selected instances drawn from a large space of pos- sible strategies, for example, defined terms of a fundamental policy space: mappings from observations to actions. For given set of strategies (policies) I we estimate empirical game via simulation over combinations of these strategies. In iterative approaches to EGTA, analysis of the empirical game informs decisions about the sampling of strategy profiles additions of strategies to the restricted sets. [Schvartzman & Wellman (2009b) first combined RL with EGTA, adding new strategies by learning a policy for one agent (using tabular Q-leaming). fixing other agent policies Nash equilibrium of the current empirical game.
Lanctot et al. (2017) introduced a general framework, Policy-Space Response Oracles (PSRO), interleaving empirical game analysis with deep RL. PSRO generalizes the identification of leariing targets, employing an abstract method termed meta-strutegy solver (MSS) that extracts a strategy profile from an empirical game. At each epoch of PSRO, player uses RL to derive a new policy by training against the opponent- strategies in the
profile.
particular challenge for the RL step in PSRO is that the learner must derive a response under uncertainty about opponent policies. The profile returned by the MSS is generally a mixed-strategy profile, as in strategically complex environments randomization is often a necessary ingredient for equilibrium. The opponent draws from this mixture are unobserved, adding uncertainty to the multiagent environment.
'The term policy employed in the RL. context corresponds exactly to the game-theoretic notion of strategy our setting, and use the terms interchangeably.

---

Published as a conference paper at ICLR 2021
We address this challenge through variants of PSRO in which all RL is applied to environments where opponents play pure strategies. We propose and evaluate two such methods, which work in qualitatively different ways: Mixed-Oraete learns separate best-responses (BR) to each pure strategy in mixture and combines the results from learning to approximate a BR to the mixture. Mixed-Opponents constructs a single pure opponent policy that represents an aggregate of the mixed strategy and learns BR to this policy. Both of our methods employ the machinery of Q-Mixing (Smith et al. (020), which constructs policies based on an aggregation of Q-functions corresponding to component policies of mixture.
Our methods promise advantages beyond those of learning in a less stochastic environment. Mixed-Oracles transfers leaming across epochs, exploiting the Q-functions learned against particular opponent policy in constructing policies for any other epoch where that opponent policy is encountered. Mixed-Opponent applies directly over the joint opponent space, and so has the potential to scale beyond two-player games.
We evaluate our methods in series of experimental games, and find that both Mixed-Oracles and Mixed- Opprodettss are able to find solutions at least as good as an unmodified PSRO, and often better, while providing a substantial reduction in the required amount of training simulation.
2 PRELIMINARIES
An RL agent at time & E T receives the state of the environment s' E S, partial state called an observation o' E O. The agent then chooses an action a' according to its policy, x: m:O++((A)) effecting the environment and producing a reward signal r¹ E R. An experience is a (s* ,a" ,a,,r"++1 , ) and a sequence of experiences ending in a terminal state is an episode T. How the environment changes as result of the action is dictated by the environment's transifion dynamics p:8 said to act optimally when it maximizes return G oy=>X -/- (7 is discount factor). In value-based RL, agents use return as an estimate of the quality of a state V(o')=E, Ir aattt)] and/or taking an action in state Q(o',a ar)==r(o'd)) (a)) eo [V(o+t)).
S. The agent is
A normal form games (NFG) I 1'= (11,U,)) describes one-shot strategic interaction among n players. When there is more than one agent, we denote agent-specific components with subscripts (e.g., m)). Negated subscripts represent represen the joint elements of all other agents (e.g., x-2). Each of the players has set of policies II, (1==....., } from which may choose. Player i may select a pure strategy nT E EII, or may randomize play by sampling from mixed strategy o; (T,). At the end of the interaction, each player receives payoff 11"""" An empirical NFG (ENFG) - is NFG induced by simulation of strategy profiles. An ENFG approximates an underlying game I', estimating the payoffs through simulation. ENFGs are often employed when the strategy set too large for exhaustive representation, for example when the strategies are instances from complex space of policies.
The quality of a strategy profile in an ENFG can be evaluated using regret: how much players could gain by deviating from assigned policies. Regret is measured with respect to set of available deviation policies. The regret of solution o to player when they are able to deviate to policies in II, C I1, is: Regret,(o,II.)- maxx, en, (i; -U,,,, Example deviation sets I1 employed in this paper are 11 the strategies accumulated through run of PSRO, and LEAAL denoting a static set of held-out evaluation policies. The sum of regrets across all players SumRegret(a. IT) = Σien Regret, IT.) sometimes called the Nash convergence, a measure of how stable a solution
3 METHOD
At each epoch e of the PSRO algorithm a new policy is constructed for each player by best-responding to an opponent profile a a-; -1 from the currently constructed ENFG: रH E BR( ( These policies then added to each player's strategy set, IIş < II; (mT]), and the new profiles are simulated to expand the ENFG. Algorithm I presents the full PSRO algorithm as defined by Lanctot et al. (2117).
One of the key design choices in iterative empirical game-solving is choosing which policies to add to the ENFG. This was first studied by |Schvartzman & Wellman (2009a), who termed the strategy exploration problem. We want to add policies that both bring the solution to the ENFG closer to the solution of the full game and that can be calculated efficiently. In PSRO, the strategy exploration problem is decomposed into two steps: solution and BR via RL. In the solution step, PSRO derives profile oº* *.e from the currett
2

---

Published as a conference paper at ICLR 2021
empirical game. The method for choosing this profile is termed the meta- metaa-strateyy-solvrr (MSS), formally function from empirical games to solution profiles MSS: - For example, the MSS might compute Nash equilibrium of I' In the BR step, PSRO generates new policy via RL (the response oracle), training against the target opponent profile computed by the MSS. The choice of MSS and response oracle algorithm constitutes strategy exploration approach and determines the convergence speed of PSRO.
We observe and address two main problems with the standard version of PSRO (Algorithm T. First, note that the only thing that changes from one epoch to the next is the other-agent strategy profile a- the transition dynamics remain the same, and the mixed profile a-; itself likely contains other-agent policies encountered in previous epochs. This suggests compelling opportunity to transfer learning across epochs; however, the BR calculation step works by training anew. Furthermore, because it is responding to some of the same strategies, the new policy learnt may be similar the strategies added in previous epochs, and so not the most useful addition to the ENPG. Secondly, the opponent profiles are mixtures (i.e., distribution over opponent policies). This makes the environment dynamics more stochastic from the perspective of the RI. agent, making learning more difficult. In Section [31 we propose an algorithm that transfers knowledge between iterations, and only trains against the single new opponent. In Section (32 we present second algorithm that avoids responding to similar opponent strategies on subsequent iterations, while also addressing the opponent variance issue and providing scalability to multiple other agents.
3.1 MIXED-ORACIES
The first problem address is that during BR calculation there is missed opportumity for transferring previously learned information. In each epoch, each player leams a BR to a mixed profile of opponent policies. This mixture typically involves the newly added strategies (one per player) for this epoch, but may also include strategies from previous epochs. Training in previous epochs already captured experience against those strategies, so including them further training entails some redundancy.
The Mixed-Oracles algorithm is a variant of PSRO for two-player games, with a modified BR oracle designed to transfer learning across epochs. This method works by learning and maintaining a collection of BRs to each opponent policy A; = {>! (.....) ). where X is the BR to __; During each epoch of Mixed- Oracles, a BR is learned for the single new opponent policy, rather than for the mixed opponent-pin proffilee generated by the MSS. A BR to the MSS-generated target mixture is then constructed from the collection of BR results for constituent policies in the mixture. Constructing the new policy is done through a general Combine-Responses function that maps a set of policies and distribution over the policies into single policy. The resulting policy should approximately aggregate the behavior of the policies.
By reusing leamned behaviors from previous epochs. Mixed-Oracles allows to focus training exclusively on new opponent policies. The key design choice is how to combine knowledge from the BRs to individual policies into BR to any distribution of said policies. We provide general description of where the Combine- Resoonsss method is abstract, as Algorithm 2
Smith et al. (2200) propose Q-Mixing as an approach for constructing policies against any mixture of opponent strategies. The method employs Q-values learned against each individual opponent strategy, and thus can support the transfer sought here. Specifically, Q-Mixing averages the Q-values learned against each opponent policy T-i, weighted by their likelihood in the opponent mixture a..:
Qi(oras (o-,)=/---)>)) Σ 10,0==la,000)0(0000 T-));
(1)
where vi determines the relative likelihood of playing an opponent uh. O4: In this study, we use Q-Mixing as our Combine- Response,,,, where v is the prior over the opponent distribution as given by an MSS.
3.2 MIXED-OPPONENTS
We next examine PSRO's objective defined by BR to the opponent profile generated by an MSS. Consider the Rock-Paper-Scissson (R-P-S) game in figure |
Player I's initial strategy क. mostly plays S, which
2 Use of NE as MSS corresponds (for two- swo-player games) to the popular double oracle algorithm McMahan et al. 2003). A variety of other MSSs have been proposed, and assessing their relative merits is topic of active research (Balduzzi al. 2019) In experiments reported here, we adopt NE: as the baseline MSS; however, our methods readily apply to any MSS.
3

---

Published as a conference paper at ICLR 2021
Algorithm 1: Policy-Space Response Oracles
Algorithm 2: Mixed-Oracle
(Lacctot al. 2017)
Input: Initial policy sets for all players 17 Simulate utilities Ü for each joint EII Initialize solutions of Uniform(11))
Input: Initial policy sets for all players 170
Simulate utilities ~ for each joint 7 IIIo
Initialize solution o + = U-iforn (11))
Initialize aure-strategy BRs =0 while epoch in [1.2...] } do
while epoch e in [1.2.... do
for player i E [m]]] do for many episodes do
Best respond to euch new opponent. for player E [[n] do
Th N-~~0--
for many episodes do
Train nf over T mT)))
Train X over T~ (Af
IT [m
A (
Simulate missing entries in O from IIf
# Generate new policies. for player i [[n]] do
Compute a solution α^x from I Output: Current solution o; ee for player
TT 4- Combinne-Rssooseesee xe-11
11 11=11;--((7
Simulate missing entries in U" from 11e
Compute solution ~^e from i Output: Current solution o, for player i.
induces best response of R. Player I's second strategy xf is approximate best response to R, scoring 80% against it. The best response to πî is P. This leads to an empirical game similar to matching penmies, with player 2 playing even mixture of Rock and Paper; in particular, player 2's meta-strategy never plays S, despite it being good against both player strategies so far.
If, in PSRO, player then adds their BR this meta-strategy, which is P, then their strategy set still does not contain the Nash equilibrium of the game. The problem is that there are already strategies in the empirical game that can defeat player 2's strategies, so the new strategy is not useful. This can be detected by inspecting player 2's O-functions: Q2 has a very low valuation of P. and Q2 has a very low valuation of R. Responding to S, which is moderately highly valued by both opponent Q functions, is more relevant. To achieve this, we can mix the opponent strategies through their action-valus estimates, rather than their action distributions (Figure 1. The BR to this is R, which more usefully extends player I's strategy set [
This example motivates our second algorithm: Mixed-Opponents This method also employs a combination method, but instead of combining results from training against previously encountered opponents, combines the strategies of the opponent mixture themselves to construct single new opponent policy as a target for training. We refer to the method for generating a new opponent policy from a mixture of opponents the Combine- Oppoonnt,,,,,, and it has the same functional form as the Combine-Responses. The our Mixxed-Opponent algorithm is shown in Algorithm 3 We employ Q-Mixing (Equation I In contrast to Mixed-Oracles, which uses Q-Mixing transfer Q-values across epochs, here we apply it to average Q-values to define a variant training objective.
generalized Mixed-
3.3 ENVIRONMENTS
We evaluate our algorithms on the Gathering (Perolat et al. 2017) and Leduc Poker (Southey et 2005 games, both of which are commonly used in the multiagent reinforcement learning field.
Gathering is a gridworld rragedy-of-thecoommee Agents compete to harvest apples that regrow at a rate proportional to the number of nearby apples. The individual's 's interest in harvesting conflicts with the group's interest in regrowth creating the dilemma. We investigate two versions of this game that differ in the configuration of the map (apple locations, spawn points, etc.): (1) Gathering-Smal Small has all apples in a dense grove central in the map, and (2) Gathering- Openinng----nnn-n is a larger map with many spread-out apple groves. The former environment will be used to force two agents to interact, while the latter will allow the study of interactions between more than two players. Further details and images of the environments are included in Section D.I
game that is partially observable and general-sum.
In Appendix F. we give precise strategies and Q-values that realize this example.
4

---

Published as a conference paper at ICLR 2021
PSRO
Algorithm 3: Mixed-Oppp Oppeenn-pponntss
Input: Initial policies for all players 17 Simulate U for each joint e ETT Initialize solutions o Uniform while epoch in {1.2....} do
BR
Mixed-OOpponntt
for player i [[]]] do
Q-Mixing
m
-=
Combine- Srabbinn-Opponens((TTT o 11-1
for many episodes do Train over T~ (Tf
BR
Figure 1: Mixed- opponent targeted in PSRO (top) and corresponding Q-Mixed opponent (bottom). (Left) shows the opponent policy Q-values, and (right) shows the resulting opponent policies and their BRs. Mixed Oppo- nents, the BR expands the strategy space to include the Nash equilibrium of RPS (green dot), but in PSRO does not.
IT: -
Simulate missing entries in Ü: Compute a solution d= from Fe Output: Solution o²"² for player
Ledue Poker a reduced version Poker, designed capture the important characteristics of full game of Poker. The game proceeds similarly to Poker, where each player chooses to raise/call/fold through two rounds betting. In this version, we examine the 2-player versions of Leduc Poker. More detailed information about this environment is included in Section D.2
3.4 HYPERPARAMETERS
The objective of this study is minimize the number of timesteps spent training RI. agent across all epochs of PSRO. To this end, how timesteps are counted is critical the comparison of methods. The number of timesteps used for training is typically hyperparameter for the RL agent. This presents challenging dilemma, because (I) we must select this before running PSRO, and (2) any particular setting may not work against all opponent-profiie chosen by the MSS.
To address these issues we take a two-step approach (detailed in Section B). First, we select preliminary hyperparameters by searching for their setting that performs best against random opponent policy. Then we use these hyperparameters to generate a set of opponent ppooniit-poliies (via PSRO) to use as an objective for selecting final hyperparameters. A subset of the generated policies are used opponent test-bed to collect two sets of hyperparameters: pure-hparams performed best on-average against each individual test-opponent, and mix-hparams performed best against uniform mixture of the test-opponents. These settings are meant to represent the high- and low-variance situations encountered when training mixed and pure strategies.
In this work, our Deep RL algorithm is Double Q-Leaming (Hasslet et al, 2016), and policies have two hidden layers with ReLU activations. 300 hyperparameter settings are sampled in each environment. Complete details are provided in Section
EXPERIMENTS
Regret as a measure depends on the policies that are available for deviation; therefore, it may be misleading to compare across PSRO runs directly. As more equitable comparison, we instead measure regret when deviating to both the run's discovered policies ISROO and a held-out set of evaluation policies IAAL The evaluation policies' provide standard lower-boum bound regret across all runs. These policies constructed by independent PSRO runs, not included the results here, by sampling from the solution's 's support. Payoff's are estimated for 30 episodes for 6 policies in all environments, except Gathering- with 9.
4.1 MIXED-ORACLES
The first research question address is: does Mixed-Oracles result in similar quality solution compared to PSRO while utilizing fewer simulation timesteps? We begin by running both algorithms on the Gathering- Small and I Leduc-Poke games. We record regrets PSRO epochs and cumulative training timesteps.
5

---

Published as a conference paper at ICLR 2021
200
PSRO
PSRO
175-
Mixod. Oracles
Mixed-Oracles
SamRogred
SumRegrel
100-
75-
75
50
30-
25-
25-
0
10
25
35
0
PSRO Epochs
Timestops
Figure 2: PSRO compared against Mixed-Oracke on the Gathering-Smie Small game. SumRegret over
UUTSOOUTTEWA compared over PSRO epochs (left) and training timesteps (right).
10
10
PSRO
Mixed Mixed-Oracles
Mixed-Oracles
SumRegrei
SumRegree
8-
00
PSRO Epuchs
Timesteps
x10"
Figure 3: PSRO compared against Mixed-Oracles on the Leduc-Poker game.
SumRegret over
11 UIIROUIIEAAL compared over PSRO epochs (left) and training timesteps (right).
Figure 2 compares the convergence speed both algorithms on the Gathering Small environment. We found that -fxeelOracles converged in roughly half the number of epochs while utilizing quarter of the number simulations. Moreover, the solution discovered by Mixed-Oracles had approximately 30% less regret. Figure shows the result on Leduc-Poker where we observe Mixed-Oracle finding a comparable solution in dramatically fewer cumulative timesteps. These results confirm our hypothesis that Mixed-Oracles will find comparable solutions to PSRO in fewer training timesteps.
4.2 MIXED-OPPONENTS
Next, address the question: does Mixed-Opponent result in better quality solution compared to PSRO while utilizing fewer simulation timesteps? The methodology this experiment follows the previous experiment: measuring SumRegret both the Gathering- Small and Leduc-Poker games.
PSRO
PSRO
Mixed-Opponents
Mixed- Opponents
150
SumRegrel
125
Sugreg
125
100-
100-
75-
75-
50
50-
25-
25
0-
0
10
1.5
20
2.5
35
PSRO Epochs
Timesteps
x10
Figure 4: PSRO compared against Mixed-Opponent on the Gathering- Smalll game. SumRegret over [ is compared over PSRO epochs (left) and training timesteps (right).

---

Published as conference paper at ICLR 2021
10
PSRO Mixed-OOponentt
PSRO
Mixed Opponents
8-
SumRegret
SumRagret
2-
0
10
30
40
50
60
70
80
PSRO Epochs
Timesteps
x1009
Figure 5: PSRO compared against Mixed- Eexee-Opponents on the Leduc-Poker game. SumRegret over PI U11VAL is compared over PSRO epochs (left) and training timesteps (right).
comparees the convergence speed of both algorithms on the Gathering-Oper game. Both algorithms appear converge initially after 25 epochs. and this point, Mixed Opponents had discovered solution with 50% less regret. However, while PSRO remained converged as time went on. Mixed- Mixeed-Opponenss continues improve and nearly solves the game. Figure shows the results on Ledue-Poker. Similar to Mixed-Oracles, we also find that Mixed-Opponent, finds similar solution to PSRO in dramatically fewer timesteps. Together these results confirm our second hypothesis that Mixed-Opponnnts may find comparable solution to PSRO in less training simulations.
4.3 2 PLAYER GAMES
An advantage of fixeedOppponent over Mixed-Orackee is that it can be applied to games with more than two players. Does Mixed Lixed-Opponent reduce praining-sinulatii when compared to PSRO in games where there are more than two players? We run both algorithms on the Gathering- limit each profile in the ENFG three simulations, handle the combinatorial explosion of profiles. Fig- ure shows our results where
game with three players. We
finds a similar quality solution to PSRO in half of the time.
4.4 SHARED HYPERPARAMETERS
An important choice these experiments has been how to measure timesteps elapsed. We used two sets of hyperparameters: specialized for low- and high-variance outcomes of state, which result of facing pure- and mixed-strategy opponents respectively. This was motivated by the assumption that lower variance would require less training. In this section, question that assumption and ask: do Mixed-Oracles and Mixed-Ore -ixee-Opponents perform at least well as PSRO when given the same RL hyperparameters?
To answer this question we run all three algorithms with the same of hyperparameters, forcing all to adopt the same simulation budget. We report results for the Gathering- -mall game in Figure The trends observed in the previous experiment reoccur: Mixed-Oracles and Mixed- Opponnntssssnss find solutions at least as good as PSRO in fewer timesteps, confirming our hypothesis. In particular, under the pure-hparams, where simulations are more limited, Mixed-One Oreed-Onponents find better solution than PSRO in half the simulation timesteps.
5 RELATED WORK
The first published paper to explicitly estimate ENFG from an agent-based simulation was study by Walsh et al.) (2002) on pricing games auctions. They analyzed symmetric games with up to twenty players small number of hand-crafted heuristic strategies. A few additional works in succeeding years explored the approach, which was developed into an algorithmic framework under the EGTA label by Well- man (0006). The strategy exploration problem within EGTA was first identified and studied by Schvartzman Wellman (2009)). this work, they explored three heuristic solutions and found that BR was the most effective method. They also illustrated situations where equilibrium response had poor performance.
Before this formalization, Phelps et al. (2006) were the first to utilize automated strategy generation. Their approach is still seen in PSRO today, where iterative BRs to equilibrium used to build empirical

---

Published as a conference paper at ICLR 2021
500
200
PSRO Opponetts
PSRD
400-
175-
Mixod--Up Oppend-O
150
Mixedl-Orach Oraccess
SumRogrot
SumRegret.
3000
125-
100-
200-
75-
50-
wwww
100
0
6.0
0.2
0.4
0.8
Timesteps
Timestops
x10
(a) Mixed-Opponnets evaluated on the Gathering-Oper (b) Comparison of algorithms when set to the same Deep game with players.
RL hyperparameters.
Figure 6: Experiments on extension beyond two players and using shared hyperparameters.
game. They utilized small parametric policy space and used genetic search as their approximate oracle method. [Schvartzman Wellman (20096) followed this up by introducing reinforcement learning as the approximate oracle method. These algorithms, alongside a trend of deep reinforcement learning being used to solve difficult games, set the stage for the PSRO framework. PSRO highlighted a subclass of EGTA algorithms where iterative construction of an empirical game is built through iterative BR to an opponent- poponenn-profile.. profile. At each epoch, the opponent profile is determined by a chosen meta- meta-strategy solver (MSS). The PSRO algorithm builds heavily upon the Double-Oracle (DO) algorithm, which iteratively solves for the Nash Equilibrium in two-player zero-sum sub-games (McMahan et al.) 20033.
This has culminated in interest in discovering good strategy-explorate methods within PSRO. PSRO's strategy exploration happens in two phases: first, a MSS produces an opponent-profile as a learning objective, then reinforcement learning used as approximate oracle to best-respond the objective. Many popular algorithms for computing strategies in game theory have been adapted as MSS: linear- programming, asplicatorddnammiss Taylor & Jonker (1978), regret-minimization (Blum & Mansour 2007). and regret- mateeing (Hart& & Mas-Colell) 20000. Moreover, popular came--olving algorithms can also be viewed through the lens of a MSS. Fictitious play (Brown 1951) is a MSS where the resulting profile is uniform-strategy. Similarly, self-play's 's resulting profile is pure strategy containing only the newest policy.
Prompting recent work to leverage the additional information gleaned through the empirical game to construct new MSSs. |Wright et al.] (2019) extends DO's MSS to return a decay-weighte linear combination of the current and previous solutions. Omidshafici et al. (2019) proposes Markov-Conley Chains (MCC) as a solution concept that relates to their new proposed quality measure of policy called a-Rank, and Muller et al. (020) investigated its use as a MSS.
McAleer al. (2020) also tackles the problem of the compute requirements of PSRO by addressing its nuntime. Their Pipeline-PSRR Prpeiine-PSROeeeoe algorithm enables the RL process across epochs to be trained in parallel. The parallel technology could be leveraged to reduce runtime of both Mixed-Oracke and Mixed-Opponents.
CONCLUSIONS
In this study, we investigate PSRO's approach to strategy exploration and extensions that focus on reducing the time spent on training new policies. PSRO's strategy exploration occurs two steps: solution and BR via RL. We first propose Mixed-Oracles which approximates the solution step by training separate BRs to each opponent policy and then combining the results into an approximate BR to the solution. This affords algorithm the ability to transfer learning about previously encountered opponents. Next, we introduce fixeedOppponets. which modifies the BR training by constructing a single opponent policy that represents an aggregate of the mixed strategy and learns response to this new opponent. Mixed fixed-Opponent also trivially scales to games with more than two players. Both of these methods further mitigate the variance in state outcomes, by removing an unobserved distribution of opponents, easing learning.
8

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGMENT
Work at the University of Michigan was supported in part by MURI grant W911NT-11-1-042) from the US Army Research Office.
REFERENCES
David Balduzzi, Marta Gamelo, Yoram Bachrach, Wojciech M. Czamecki, Julien Perolat, Max Jaderberg, and Thore Graepel. Open-ended learning in symmetric zero-sum games. In 36th International Conference on Machine Learning, 2019.
A. Blum and Y. Mansour. Learning. regret minimization, and equilibria. In Algorithmic Game Theory, chapter Cambridge University Press, 2007.
George W. Brown. Iterative solution of games by fictitious play. In Activity Analysis of Production and Allocation, pp. 374-376. 1951.
Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68:1127-1150, 2000.
Hado van Hasslet, Arthur Guez, and David Silver. Deep reinforcement learning with double Q-learning. In 30th AAAI Conference on Artificial Intelligence, pp. 2094-2100, 2016.
Marc Lanctot, Vinicius Zambaldi, Audrūnas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. A unified game- theoretic approach multiagent reinforcement learning. In 31st International Conference on Neural Information Processing Systems, pp. 4193-4206, 2017.
Stephen McAAler, John Lanier, Roy Fox, and Pierre Baldi. Pipeline psro: A scalable approach for finding approximate nash equilibria in large games. In 34th International Conference on Neural Information Processing Systems, 2020.
H. Brendan McMahan, Geoffrey J Gordon, and Avrim Blum. Planning in the presence of cost functions controlled by an adversary. 20th International Conference on Machine Learning. pp. 536 536-543, 2003.
Paul Muller, Shayegan Omiisshafiii, Mark Rowland, Karl Tuyls, Julien Perolat, Siqi Liu, Daniel Hennes, Luke Marris, Mare Lanctot, Edward Hughes, Zhe Wang, Guy Lever, Nicolas Heess, Thore Graepel, and Remi Munos. generalized training approach for multiagent learning. In International Conference on Learning Representations, 2020.
Shayegan Omidshafiei, Christos Papadimirriou, Georgios Piliouras, Karl Tuyls, Mark Rowland, Jean-Baptiste Lespiau, Wojciech M. Czamecki, Mare Lanctot, Julien Perolat, and Remi Munos. a-rank: Multi-agent evaluation by evolution. Scientific Reports, 9, 2019.
Julien Perolat, Joel 7.. Leibo, Vinicius Zambaldi, Charles Beattle, Karl Tuyls, and Thore Graepel. A multi-agent reinforcement learning model common-pool resource appropriation. 31st Conference on Neural Information Processing Systems, 2017.
S. Phelps, M. Marcinkiewicz, and S. Parsons. A novel method for automatic strategy acquisition in N-player non non-zero-sum zero-sum games. In Fifth International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 705-712. 2006.
L. Julian Schvartzman and Michael P. Wellman. Exploring large strategy spaces in empirical game modeling. AAMAS-09 Workshop on Agent- Agent-Mediated Electronic Commerce, 2009a.
L. Julian Schvartzman and Michael Wellman. Stronger CDA strategies through empirical game-theoretic analysis and reinforcement leaming. In 8th International Conference Autonomous Agents and Multiagent Systems, pp. 249-256, 256922562220 2009b.
Max Olan Smith, Thomas Anthony, Yongzhao Wang, and Michael P. Wellman. Learning to play against any mixture of opponents. CORR, 2020. URL htttts:////axii/ org/ abs /2009.000... 14180
Finnegan Southey, Michael Bowling, Bryce Larson, Carmelo Piccione, Neil Burch, Darse Billings, and Chris Rayner. Baye's bluff: Opponent modelling in poker. In 2/st Conference on Uncertainty in Artificial Intelligence, 2005.

---

Published as a conference paper at ICLR 2021
Peter D. Taylor and Leo B. Jonker. Evolutionarily stable strategies and game dynamics. Mathematical Biosciences, 156, 1978.
William Walsh, Rajarshi Das, Gerald Tesauro, and Jeffrey Kephart. Analyzing complex strategic interactions in multi-agent systems, In AAAI-02 Workshop on Game Theoretic and Decision Theoretic Agents, 2002.
Michael Wellman. Methods for empirical same-theoretic analysis. In 2 National Conference on Artificial Intelligence, pp. 3552-1555, 2006.
Mason Wright, Yongzhao Wang, and Michael P. Wellman. Iterated deep reinforcement learning in games. History-aware training for improved stability. In 20th ACM Conference on Economics and Computation, pp. 617-636, 2019.
10


Reviews:
[{"review_id": "sWhWE4aOqus", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\nThe paper proposes two new methods in the Policy-Space Response Oracle framework. These approaches permit to reuse past knowledge in order to reduce the amount of data required for the RL training. The first algorithm Mixed-Oracles transfers the previous iteration of Deep RL, instead of the second one, Mixed-Opponents, transfers existing strategy action-value estimates.\n\nStrengths\nThe paper proposes two convincing alternatives to reuse previous knowledge in the PSRO framework. The two ideas are based on Q-mixing approach: the first one uses this method to transfer Q-values across epochs, the second one to design a new training objective. \nThe experiments show that the proposed methods find a good solution using less simulation than the original PSRO framework. \n\nWeakness\nThe paper is not very novel, since it uses previous approaches (PSRO and Q-mixing) to transfer knowledge for the PSRO framework. \nI am not aware of recent works in this framework but could be useful to compare the proposed approaches with P2RO [1].\nThe Mixed-Opponent section needs a better explanation of the use of Q-mixing as a training objective.\n\n[1]  McAleer, S., Lanier, J., Fox, R., & Baldi, P. (2020). Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Games. arXiv preprint arXiv:2006.08555.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Pn3wHo_VxfN", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper focuses on resolving the computational and sample efficiency challenges with current PSRO style approaches. To this end it proposes two different modifications to the standard PSRO setup: 1) Mixed Oracles, and 2) Mixed Opponents. These approaches allow avoiding resetting learning after each outer loop epoch and reduce the stochasticity of dynamics during training. Thee efficacy is demonstrated on relatively simple games but using Deep RL policies where the proposed approaches are at least on par with standard PSRO approach in terms of final performance while drastically improving the sample efficiency.\n\n\nAlthough the paper has quite a few typos and unclear writing in places, it has a fantastic setup with clear description of the problems with standard PSRO it's trying to resolve. The paper points out the clear computational deficiencies with current PSRO style approaches: 1) starting anew everytime, 2) slower exploration of strategy space, 3) stochastic dynamics making learning difficult.\n\n\nThe paper is mostly focused on two-player zero sum games.\nApproach heavily dependent on efficacy of Q-mixing approach (although the idea is more general), so currently limited to discrete action problems.\nMoreover, since there are no alternatives to Q-mixing, we don't actually get any understanding/intuition for why this works and how important is the performance of \"TransferOracle\" or \"OpponentOracle\".\n\nAlthough section 4.4 suggests that the two stage hyperparameter selection wasn't as important, results in Fig 6b are too noisy to fully accept. It's unclear how much compute/samples were required for the hyper parameter selection. In general the results are a lot more noisier for the proposed approaches vs standard PSRO.\n\n**Minor** \n- Environment dynamics should be SxA rather than OxA\n- Algorithm 4.1 does not exist?\n- Fig 1. Is it because of PSRO with Nash. Would a different MSS work differently?\n- \"proposes MCC as a solution concept\": not everyone would know what MCC refers to. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "ICQ1OuijJGk", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper suggests two techniques to improve the calculation of empirically figuring out a Nash equilibrium using an iterative application of best-response dynamics. One method learns the best-response to the previously used strategy. The other uses that technique to model the opponent, and then best-responds to the modeled opponent. The experiments show a faster reaching to NE than without these changes.\n\nThe paper is well-written and explained, and is accessible even to researchers not well-versed in ML topics. While, the suggested changes are rather straightforward, they do indeed lead to the expected advance (shorter times to reach NE). I was convinced by further introspection that this is a significant enough contribution, to merit acceptance.\n\nOf course, a more significant change to the algorithm, leading not only to a shorter time but to convergence to better equilibria (in cases where multiple exist) would be far more compelling.", "extra_scores": {}, "extra_text": {}}, {"review_id": "BGxzL7l0hbm", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\nSummary:\n \nThe paper provides an interesting approach to speeding up the convergence time of the Policy-Space Response Oracles framework by re-using the Q-functions of past best-responses to transfer knowledge across epochs.\n##########################################################################\nReasons for score: \n \nOverall, I am low confidence on my assessment of this paper due to the exposition in the algorithm section being relatively confusing. The experimental results are interesting which suggests that the method has value but there is key missing information on how the best response policies are constructed that make it difficult to assess the paper and lead to my not wanting to recommend its acceptance. I would highly recommend being more detailed in Sec. 3 to allow me to reassess the paper. I would certainly be willing to update my score if the paper was clearer to read.\n ##########################################################################Pros: \n \n1. The experimental results on Leduc Poker are very speedy in terms of time-steps. \n\n2. The idea of reusing the prior Q functions and just mixing them together rather than re-learning all of the policies is very good. \n\n \n##########################################################################\nCons: \n\n1. The algorithm boxes are so high level that I am struggling to understand how the algorithms work. I would not be able to implement it from reading the paper. \n\n#########################################################################\nThings that would improve readability:\n\n- It would be nice in the algorithm boxes to connect Q-mixing to how the best policy is explicitly output. I was not able to understand how Q-mixing was connected to either Algorithm 2 or 3 and subsequently had difficulty following the paper.\n- \\lambda does not appear to be defined anywhere but appears in the Mixed Oracles algorithm box\n- What is the OpponentOracle and the TransferOracle? They are defined in the algorithm boxes but are not clearly defined elsewhere.\n- The specific example of RPS in section 3.2 does not provide useful intuition by going through the numerics, it may be more helpful to walk through a more high level description. \n- It would probably be useful to move more of the experimental results to an appendix to leave room for the exposition of the algorithms.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a method to improve the convergence time of PSRO. The paper was well received by all reviewers and is likely to be of interest to a similar sub-community within ICLR, but may be of less relevance to the wider community not focused on multi-agent learning. 

A number of issues were raised by reviewers regarding the clarity of the originally submitted version of the paper. I encourage the authors to consider all constructive feedback given and revise the paper to maximise its impact. This will be of particular help in reaching a wider audience than those with pre-existing experience with the methods this work builds on.
Decision: Accept (Spotlight)