Toward Optimal Policy Population Growth in Two-Player Zero-Sum Games
Authors: Stephen Marcus McAleer
JB Lanier
Kevin A. Wang
Pierre Baldi
Tuomas Sandholm
Roy Fox
Venue: ICLR 2024 poster (2024)
Keywords: PSRO
game theory
deep RL
Nash
population
Primary area: reinforcement learning
TL;DR: We improve PSRO by not increasing exploitability and adding mixed strategies

Abstract: In competitive two-agent environments, deep reinforcement learning (RL) methods like Policy Space Response Oracles (PSRO) often increase exploitability between iterations, which is problematic when training in large games. To address this issue, we introduce anytime double oracle (ADO), an algorithm that ensures exploitability does not increase between iterations, and its approximate extensive-form version, anytime PSRO (APSRO). ADO converges to a Nash equilibrium while iteratively reducing exploitability. However, convergence in these algorithms may require adding all of a game's deterministic policies. To improve this, we propose Self-Play PSRO (SP-PSRO), which incorporates an approximately optimal stochastic policy into the population in each iteration. APSRO and SP-PSRO demonstrate lower exploitability and near-monotonic exploitability reduction in games like Leduc poker and Liar's Dice. Empirically, SP-PSRO often converges much faster than APSRO and PSRO, requiring only a few iterations in many games.

Published as a conference paper at ICLR 2024
TOWARD OPTIMAL POLICY POPULATION GROWTH IN TWO-PLAYER ZERO-SUM GAMES
Stephen McAleer"I JB Lanier", Kevin A. Wang?, Pierre Baldi², Tuomas Sandholm' and Roy Fox2
Department of Computer Science, Carnegie Mellon University 2 Department of Computer Science, University of California, Irvine "oorresponding author: amcalecr@cs.cmu..co
ABSTRACT
In competitive two-agent environments, deep reinforcement learning (RL) methods like Policy Space Response Oracles (PSRO) often increase exploitability between iterations, which is problematic when training in large games. To address this issue, we introduce anytime double oracle (ADO), an algorithm that ensures exploitability does not increase between iterations, and its approximate extensive-form version, anytime PSRO (APSRO). ADO converges to a Nash equilibrium while iteratively reducing exploitability. However, convergence in these algorithms may require adding all a game's ' deterministic policies. To improve this, we propose Self-Play PSRO (SP-PSRO), which incorporates approximately optimal stochastic policy into the population in each iteration. APSRO and SP-PSRO demonstrate lower exploitability and near-monotonic exploitability reduction in games like Leduc poker and Liar's ' Dice. Empirically, SP-PSRO often converges much faster than APSRO and PSRO, requiring only few iterations in many games.
INTRODUCTION
In competitive two-agent environments, also known as zero-sum games, deep reinforcement learn- ing (RL) methods based on the double oracle (DO) algorithm (McMahan et al. (2003), such Policy Space Response Oracles (PSRO) (Lanetot et al. 2017), are some the most promising methods for finding approximate Nash equilibria large games. One reason is that such methods simple to use with existing RL methods and naturally provide a measure of approximate exploitability. The exploitability of a policy is defined as the performance against worst-case opponent, and it is optimal at zero when the policy a Nash equilibrium. A second reason is that these methods effectively prune the game tree by only considering mixtures over policies that are already trained to be effective best responses. Finally, they can be used in games with large or continuous action spaces because they do not require full game-tree traversals. Methods based PSRO such as AlphaStar (Vinyals) et al. (2199) and Pipeline PSRO (MeAleer et al. 2020) have achieved state-of sate--of-the-ar performance on Starcraft and Barrage Stratego, respectively.
PSRO-based methods iteratively add RL best-response policies to a population. The best response for each player trains against a restricted distribution over the opponent's 's existing population of policies. To find this restricted distribution, a Nash equilibrium (a pair of mutually best-responding policies) is computed in a restricted single-step game where each action corresponds to choosing a policy from the population. As PSRO iterations progress, an optimal distribution over these population policies will approximate a Nash equilibrium in the full game.
In practice, however, PSRO is terminated carly in large games. This can be a problem because the PSRO restricted distribution over the population policies is not guaranteed to decrease in exploitability every iteration. As result, if PSRO is terminated early, the final restricted distribution could potentially be arbitrarily more exploitable than the initial one.
In this paper, first propose iteration, finds the least-exploitable restricted distribution over the population policies of each player. This algorithm is called anytime, in the sense that it can be stopped in any iteration and return
double oracle variant, anytime double oracle (ADO) that, in each

---

Published as a conference paper at ICLR 2024
solution that is not worse than the previous iteration. We then present approximate extensive-form RL version called anytime PSRO (APSRO).
Anytime double oracle (ADO) can be viewed as modification of the range of skill (ROS) algo- rithm (Zinkevich et al. 2007) that finds a restricted Nash equilibrium over two restricted games, one per player. Each player's s restricted game is defined such that their strategies are restricted to be within their population, but the opponent is unrestricted. For each player, ADO adds to the opponent's population best response to the player's 's NE restricted distribution. ADO is guaranteed not to increase exploitability from one iteration to the next, while also being guaranteed to converge to a Nash equilibrium in a number of iterations at most equal to the number of pure strategies in the game,
Anytime sppicy-space response oracles (APSRO) updates the restricted distribution using a no-regret algorithm trained against single approximate best response from the opponent. This opponent approximate best response is itself being continually trained via reinforcement learning against the restricted distribution. We find empirically that APSRO tends not to increase exploitability as much as PSRO and can greatly outperform PSRO in some domains.
However, because common implementations of PSRO add pure-strategy (i.e. deterministic) best responses in each iteration, PSRO may still need to add many policies to the population before they can support a Nash equilibrium. In fact, in certain games, all pure strategies will be added before finding a Nash equilibrium. This is because many games require mixing over a large number of pure strategies to arrive at a Nash equilibrium. Furthermore, before termination, the restricted distribution over population policies can be arbitrarily exploitable, even if it decreases monotonically until then.
In addition to introducing APSRO, we also build on APSRO by adding to the population in each iteration a stochastic policy that is trained via an off policy procedure. A key insight is that mixed strategies (i.e. stochastic policies) can lower the exploitability of a population more than pure strategies. To see this, note that Nash equilibrium strategy is optimal strategy to add because the least-exploitable distribution over the resulting population will also be Nash equilibrium strategy. If all Nash equilibria are mixed, is often the case, then no pure strategy can be added the population that reduces exploitability as much as the mixed strategy Nash equilibrium.
Although finding the optimal strategy to add is as hard as solving the original game, we find that adding rough approximation to the optimal strategy can offer striking empirical benefits in quickly reducing the exploitability of the restricted distribution. We present Self-Play PSRO (SP-PSRO). which, similarly to APSRO, learns restricted distribution over the population via no regret against the opponent's 's best response. Additionally, SP-PSRO trains off-policy a new strategy against the opponent's 's best response. At the end of each iteration, SP-PSRO adds two strategies to the population: (I) the time-average of this new strategy and (2) the best response to the opponent's 's restricted distribution. Section 5 clarifies this algorithm using formal notation. In large games like dark chess and Starcraft, where PSRO may never converge, the early performance holds paramount importance. Our approach with SP-PSRO is tailored to this reality, ensuring robust performance from the outset. Recognizing that the completion of the full training procedure in such extensive games is a rare occurrence, the anytime property of our proposed method takes on critical role, delivering viable strategies at any stage of the iterative process.
By training the new strategy off-policy, SP-PSRO requires the same amount of experience in each iteration as APSRO and PSRO. Experiments on normal-form games and extensive-form games such as Liar's Dice, Battleship, and Ledue Poker suggest that SP-PSRO can learn policies that are dramatically less exploitable than APSRO and PSRO. Our empirical results demonstrate SP-PSRO's superior performance reducing exploitability before convergence across various games, a testament to its practical effectiveness. While APSRO serves foundational concept in our research, the leap to SP-PSRO marks significant advancement, particularly in terms of reducing exploitability before PSRO has neared convergence.
To summarize, our contributions are as follows:
We introduce a version of double oracle that does not increase in exploitability, called any- time double oracle (ADO) and its extensive-form approximation, anytime PSRO (APSRO).
We present an enhancement APSRO, termed Self-Play PSRO PSR-P. In each iteration, without requiring extra environment steps, it incorporates an additional mixed strategy aimed at reducing our population's exploitability.
2

---

Published as a conference paper at ICLR 2024
2 BACKGROUND
We consider extensive-fore form games with perfect recall (Hansen et al. 2004). An extensive-form game progresses through a sequence of player actions and has a world state E W at each step. In an N V-player game, AA = A₁ x x... AN is the space of joint actions for the players. A((w) S A denotes the set of legal actions for player E .V' = (1,- ... .) at world state and (a1, (a1,..., (N)) E A denotes a joint action. At each world state, after the players choose a joint action, a transition function T(w, a) E W determines the probability distribution of the next world state w'. Upon transition from world state w to w' via joint action a. player makes an observation Og = Oww,, a, w'). In each world state w. player i receives reward R2 (wr). The game ends when the players reach a terminal world state. In this paper, we consider games that are guaranteed to end in finite number of actions.
history is sequence of actions and world states, denoted = (w aa, w aa',a', ..... w²), where wD is the known initial world state of the game. (h) and (A) are, respectively, the reward and set of legal actions for player in the last world state of history player i, denoted by si. is sequence of that player's observations and actions up until that time s((h) = (af, of. af....,of) of). Define the set of all information sets for player to be I,. The set of histories that correspond to an information set 8; is denoted H(s:) = (h sh) si). and it is assumed that they all share the same set of legal actions (s+(())) = (hh).
An information ser for
A player's strategy n; is function mapping from information set to probability distribution over actions. A strategy profile π is a tuple (#1...., n)). All players other than are denoted -i, and their strategies are jointly denoted --x. A strategy for history h is denoted n; (h) n, (s,(h) (h)) and (h) is the corresponding strategy profile. When a strategy me is learned through RL., we refer to the learned strategy as a policy.
The expected value (EV) uf (h) for player is the expected sum of future rewards for player in history h. when all players play strategy profile æ. The EV for an information set 8; is denoted v." (s:) and the EV for the entire game is denoted (T). A two-player zero-sum game has U1 (T) + D2 (7)) (T)= 0
for all strategy profiles x. The EV for an action in an information set is denoted u, (3), a.). A Nash equilibrium (NE) is strategy profile such that, if all players played their NE strategy, no player could
achieve higher EV by deviating from it. Formally, ' is a NE if (;(TT) )- = max+, 0; π m",) for each player i.
The exploitability e(xx) of strategy profile π is defined as <(xx) EIEN max+; (1 T-:). A best response (BR) strategy (T-;) for player to strategy æ=; strategy that maximally exploits - (T. = arg max=, 0/ (m; -- An 6-best response (E-BR) strategy (R for player to a strategy π is a strategy that is at most e worse for player i than the best response: uy (BBR)(TT)) m= 2 e (BRR(T m-)) E. An e-Nash equilibrium (E-NE) is a strategy profile in which, for each player i, n, is an B-BR to --
A normal-form game is simultancous-ne move single-step extensive- form game. An extensive-form game induces a normal-form game in which the legal actions for player i are its deterministic strategies X,,ez, As(s)). These deterministic strategies are called pure strategies of the normal-form game. A mixed strategy is a distribution over a player's pure strategies.
3 ANYTIME DOUBLE ORACLE ALGORITHM (ADO)
is guaranteed to converge because in the worst case, it will expand all pure strategies, at which point it terminates a Nash equilibrium (NE). Unfortunately. before convergence, there is no guarantee on the exploitability of the restricted-gane NE. In fact, DO can increase exploitability arbitrarily from one iteration to the next.
Double oracle (DO) (described in B.1
To see this, consider the game in Figure T If both players start with a population consisting only of the first strategy (top row and left column), then the best response for each player is the second strategy, giving that player value 1, for a total exploitability of 2. In the next iteration (Figure when both the first and second strategies are in the population for both players, the restricted restricted-game NE of DO will give probability 1 to the second strategy for each player. This restricted NE has exploitability of 4. In Appendix D we show empirically that DO does indeed increase exploitability arbitrarily before terminating this class of games. PSRO inherits this property.
3

---

Published as a conference paper at ICLR 2024
Full Game
Restricted Game
Restricted Distribution n
Exploitability
0
0
0
DO
1
0
-2
1
0
-2
1
0
-2
e(it) =4
0
0
0
0
1
0
-2
0
0
ADO
1
-2
-2 e(T)
0
0
0
-2
0
Figure Top: In DO, a single restricted game created and solved in gray. Since this restricted game does not consider strategies outside of the population, it can lead to exploitable restricted distributions. In this example, the DO restricted distribution и places all mass on the second strategy, resulting in total exploitability of 4. Bottom: Conversely, ADO creates two restricted games where the opponent unrestricted, player I's restricted game is shown in green and player 2's restricted game is shown in red. Solving these modified restricted games results in the least-exploitable restricted distributions. In this example, the restricted distribution æ for ADO puts mass on the first strategy and 3 mass on the second strategy, resulting in the optimal exploitability for this restricted game of 4 3.
Algorithm 1 Anytime Double Oracle (ADO)
Result: Nash Equilibrium
Input: Initial population I1o
repeat (for / 0, 1,
for E {1. 2} do
Tς <- NE restricted game G' (eq.
for i E {1, 2} do
Find novel best response 3; f- BIR, (T"
I = IT; {
until No novel best response exists for either player Return: x²"
In this paper, we introduce anytime double oracle (ADO) (Algorithm I.. which is guaranteed not increase exploitability from one iteration to the next. ADO primarily serves as a foundational element for the development of our subsequent algorithm, APSRO. This foundational role is crucial lays the groundwork for APSRO's 's convergence guarantees, Like DO, ADO maintains population 11Ş for player iteration and in each iteration computes a Nash equilibrium on a restricted game and adds to each population a best response to the restricted NE. However, unlike DO, ADO creates different restricted game for each player. The restricted game G' for player is created by restricting that player to only play strategies included in their population II, while the opponent can play any strategy the full game. The game value of G for player is
max min Us (TT n-))) EIE
The restricted game G for player is then solved for both players to get NE for each restricted game. We refer to player i's NE strategy their restricted game as their restricted NE π.. The restricted NE for player is the least exploitable mixed strategy supported by player i's population. Note that in large games this restricted game will be prohibitively large to solve and will require approximation with APSRO, introduced later in this paper.
4

---

Published as a conference paper at ICLR 2024
Next, a best response 3; strategy of the restricted opponent, and is added to the player's population. If there are multiple best responses, novel best response B; II. is chosen that is not currently in that player's population.
=B)("".) is computed for each player i against the restricted-NE mixed
ADO is guaranteed to terminate because there are finitely many pure strategics the original game. When ADO terminates, the restricted NE is NE in the original game (Proposition 2 Unlike DO, the exploitability the restricted NE does not increase from iteration to iteration (Proposition) [
Proposition 1. The exploitability of ADO is monotonically non-increasing.
Proof. All proofs are contained in Appendix H
To illustrate this property of ADO, consider the algorithm dynamics on the DO bad case given in Figure [ Similar to DO, ADO adds the second strategy to the population in the first iteration. Now, however, instead of taking the second strategy with probability 1 as DO does, ADO solves the restricted game where one player is restricted to the first two strategies and the other is unrestricted and can play any of the three strategies. The Nash equilibrium of this game for the restricted player to play the first strategy with probability Ehf and the second strategy with probability 1. This strategy results in total exploitability of 4 3. compared with the DO exploitability of 4 and the initial ADO exploitability of 2. In addition to this property of never-increasing exploitability, ADO is guaranteed converge a Nash equilibrium, as shown below.
Proposition 2. When ADO terminates, the restricted NE of both players is Nash equilibrium in the full game.
4 ANYTIME PSRO ALGORITHM (APSRO)
In this section introduce scalable extensive-form version of ADO, which coin anytime PSRO (APSRO) (Algorithm 2) Rather than computing the exact NE for each player's ADO restricted game G¹, APSRO approximates this solution by simultaneously optimizing each player's 's restricted distribution x. via a regret minimization algorithm against continuously trained RL best response
8_ In this work, update oं via the exponential-weight algorithm (Exp3) (Auer et al. 2002)
or the Multiplicative Weights Update (MWU) algorithm (Cesa-Biance) & Lugosi 2006 Freund &
Schapire 1999).
Algorithm 2 Anytime PSRO
Result: c-Nash Equilibrium Input: Initial population ITo
while Not Terminated {l (6=00 -,=0, 0, 1,...) do
Initialize o. to uniform over II; for i E (1,2) Initialize policies 3r for {1.2)
for i E 2} do for n inner iterations do for iterations do Update policy 3-; toward (R_;(x;) (e.g. via Q-learning) Update n.. via regret minimization vs. 8_; (e.g. via Exp3 or MWU)
IT( = IT; J [3:} for i E (1,2)
Return: n²
Instead of recomputing an exact best response between regret minimization updates, APSRO main- tains an approximate best response RL policy 8_, for each player and updates for small number m of steps in each inner-loop iteration. We allow 8_, to be an approximate best response, and we set the hyperparameter m to smaller value than may be necessary to fully converge to BR_.((])) In practice, this trades off the theoretical guarantees of exact best responses with considerable computational speedup. We include details about the no-regret procedure in Appendix C The updates to the best response be made through variety of algorithms. In this paper show experiments with updates via tabular Q-learning as well as experiments via the deep reinforcement learning algorithm DDQN (Van Hasselt al. 2016). Importantly, compared PSRO, APSRO uses the same
5

---

Published as a conference paper at ICLR 2024
amount of episodes and environment interactions. The only difference is that APSRO changes the restricted distribution dynamically during training via a no-regret procedure.
4.1 APSRO THEORY
In this section present theory for APSRO where assume the best response is exact in every inner iteration. We show that under this assumption APSRO converges to an approximate Nash equilibrium and never increases exploitability by much. The following proposition shows that APSRO with exact best responses approximately finds the least-exploitable restricted distribution.
Proposition 3. Assume B-: (==((=;) in every inner iteration of APSRO. Then APSRO with regret minimizing algorithm that has regret R3 at inner iteration j will outpur a policy x" such that e(TT) B.
By this proposition we know that APSRO with exact best responses will ap- proximately find the least-exploitable restricted distribution for each player in each outer iteration. Since the population grows in every iteration, the least-exploitable distribution of later iteration is never more exploitable than the least-exploitable distribution of an earlier iteration, simply because exploitability is later minimized a superset of population mixtures. The following proposition formalizes this intuition.
0
0
1
0
-1
0
0
0
-1
0
Proposition 4. Assume APSRO with exact inner-loop best responses runs sufficiently many inner-loop updates in each iteration such that the ex- ploitability in each restricted game is most Then the exploitability of APSRO will never increase by more than 2e from one iteration to the next.
0
0
-1
Big RPS Game. Any algorithm that only adds pure best responses, such as com- mon implementations of PSRO or APSRO, will expand all pure strate- gies before converging.
Figure 2:
SELF-PLAY PSRO
Although ADO and APSRO mitigate increases in exploitability from one iteration to the next by adding to each player's population the pure-strategy best response 3, to the opponent's restricted distribution T-,, they are not guaranteed to decrease exploitability. 33 may not be the myopically op- timal pure strategy whose addition to II, decreases exploitability the most. Moreover, adding mixed strategies can generally reduce exploitability faster than adding pure strategies.
For example, consider the generalized Rock-Paper-Scisson game shown in Figure 2 In this game, the NE mixes equally over all pure strategies. As result, any DO method that only adds pure strategies, such as common implementations of PSRO, will have to enumerate all pure strategies in the game before supporting the NE.
Ideally, would like to add mixed strategy that decreases exploitability the most. single-iteration objective would then be able to find the strategy such that after it is added to the population and the least-exploitable distribution computed over this new population, the exploitability the resulting distribution is the lowest. In this example game, mixed strategy that mixes over the pure strategies equally is optimal and will lower exploitability more than any pure strategy.
In general, the Nash equilibrium of the original game would be the optimal mixed strategy to add to the population, however finding Nash equilibrium of the original game is very expensive and our main goal in the first place.
By trying to add rough approximation of Nash equilibrium of the original game our population, can still expect to improve our population exploitability great deal. The closer this new mixed strategy is to being a Nash equilibrium of the original game, the more we would expect it to lower the resulting exploitability of the population.
Motivated by this, we propose Self-Play PSRO, PSRO method that learns and adds to the population additional new mixed strategy each iteration. This strategy is learned by best-responding to the opponent best response via off-policy reinforcement learning in self play fashion and calculating mixed-strategy time-average of it. While this self play process won't necessarily produce Nash

---

Published as a conference paper at ICLR 2024
0
-1
0
0
1
0
0
0
1
0
-1
-1
0
-1
-1
0
0
0
1
0
-1
0
0
0
1
0
-1
-1
-1
0
0
0
0
-1
0
0
0
0
Inner Iteration
Inner Iteration 10
Time-Averaged New Strategy
Fixed
New Strategy
Opponent
Strategies
Response
Figure 3: SP-PSRO. In this diagram we show how SP-PSRO works within an iteration from the perspective of the column player. The fixed population is shown in blue and the new strategy is shown in green. Every inner iteration, three things happen. (1) The opponent best response updates toward best response the current distribution over both the fixed population and the new strategy. (2) The new strategy updates toward best response against the opponent best response. (3) The restricted distribution updates via no regret against the opponent best response. In the final iteration, the time-average of the new strategy and the player's best response to the opponent's restricted distribution (which is trained in a symmetric manner) are added to the population, and the cycle starts again.
equilibrium, this additional strategy can serve as an inexpensive heuristic approximation of one to dramatically reduce our population's exploitability, especially in earlier PSRO iterations.
Algorithm 3 Self-Play PSRO
Result: Approximate Nash Equilibrium
Input: Initial population 11 while Not Terminated {t = 0, do
for E (1,2) do
Initialize new strategy arbitrarily
Initialize oे to uniform over II; {w,}
for iterations do for m iterations do
Update policy 8_ toward (R_((TT)) (e.g. via Q-Leaning) Update new strategy D4 toward (3_s) (e.g. via Q-Learning) Update n. via regret minimization B_, (e.g. via Exp3 MWU) II (3;, 72) for i (1,2)
II
Return: x²
SP-PSRO works by maintaining restricted distribution o. over population. Unlike PSRO, where o. is the NE of the restricted game, SP-PSRO trains गद the same way as APSRO, via regret minimization. In addition, at the beginning of each iteration, a new strategy v is initialized and added the population.
During an iteration, three training processes unfold concurrently. First, as in APSRO, the opponent's best response B, takes multiple update steps toward best response the current restricted distribution BR_.(TT). Second, the new strategy is updated toward best response to the opponent best response (3_.). Third, the restricted distribution गद is trained via regret minimization; this includes updating the probability of the new population strategy Vi, even as is also trained. This procedure can be thought of form of self-play, in which the new strategy is updating against the opponent best response, while the opponent best response is updating against the restricted distribution, which also contains the new strategy. When the iteration is finished, the time-average 17; of v; is added to the population. We include further details SP-PSRO in Appendix L.3
7

---

Published as a conference paper at ICLR 2024
Big w/ 50 Actions
Hex Boerd
Restricted
2.0
5P PSPS (Ouns)
SP PSRO (Durs)
Balktrabbitt
1.5
APSRC (Ours)
215
SP PS-S (Durs) APSRO (Ours)
Esoluraabith
1.5
APSRO (Ours)
2.0
1.0
0.5
0.5
0.5
0.0
0.0
10
40
50
10 beretion
15
0.0
2.5
7.5 Itraaion
10.0
12.5
lteration
(a) Big RPS with 50 Actions
(b) Hex-3 Restricted Game
(c) AlphaStar Restricted Game
Figure 4: Normal-form games
Averaging over the updates of v4 can be accomplished by checkpointing the policy over time and uniformly sampling checkpoints, or by training a neural network to distill a buffer of experience generated by as it trains. Since the new strategy is trained via off-policy reinforcement learning, SP- PSRO uses the same amount of environment experience as APSRO, but does require more compute to train the new network. Additionally, since it still adds best responses B, similar to APSRO and PSRO, it will also converge to an optimal population that supports a NE.
6 EXPERIMENTS
6.1 NORMAL FORM EXPERIMENTS
In this section we describe experiments on normal form games. To emulate the process of a strategy learning best response to another policy n'. in every inner loop iteration we update by the following learning rule: T++1 = (1 A)m + À x HT, We show three normal form games. The first, described in Figure 4a large generalized Sook-PPper-Scissee
game. The second is Hex restricted game (Perez-Nieves et al. 2021). The third game is the final restricted game of the AlphaStar population (Vinyals et al. 2019). More normal form games are included Appendix E As shown in Figure 4 SP-PSRO vastly outperforms both PSRO and APSRO. Note that APSRO and SP-PSRO only reach an e-NE because they use finite number of regret minimization updates to determine the restricted distribution, while PSRO is able to exactly compute NE. We have included further details the Appendix.
6.2 TABULAR EXPERIMENTS
We evaluated SP-PSRO with tabular methods in variety of games. We applied tabular SP-PSRO to the domains of Leduc Poker (9,457 states), a tiny version of Battleship (1 (1,573 states), and 4x-Repeated Rock Paper Seissors (9,841 states). The experiments used game implementations and tools from the OpenSpiel library (Lanctot et al. 2019).
In extensive form tabular experiments, the new population strategy v; and the best response 3_, are represented by tabular Q-learning agents. When training the Q-lcarning agent for 8- experience from the same episodes also used to train the agent for μ4 an off-policy manner. The tabular Q-learning agents are e-greedy, and we use constant value of e for both agents. Because experience for 3-; and 2/ shared from the same episodes, experience is collected against e-greedy versions of some opponent policies. Compared to collecting separate episodes for each player, we found that using the same episodes to train policies for both players despite small amounts of action exploration reduces the required sample complexity by two without affecting performance very much. In these 3 games, we collect the same amount of experience per iteration for PSRO, APSRO, and SP-PSRO.
Similar to normal form results, we find that APSRO does not increase exploitability by much from one iteration to the next and SP-PSRO drastically reduces exploitability compared to baselines. Interestingly, in tiny battleship, the exploitability of APSRO had higher variance compared to that of PSRO. We hypothesize that this is due to the APSRO iterations not being long enough for the no-regret process to converge. We have included further details in the Appendix.
8

---

Published as a conference paper at ICLR 2024
Tiny Bellleship
4-Repeated RPS
2.0
5P PSRC (Ouns) APSRO (Ours)
1.00
50-1550
1.5
00.75
PS3D
(Ou
SFPSRO
1.0
0.50
APSRO (Ours)
0.25
0.0
20 lteration
0.00
100
Eoration
Iteration
(a) Ledue Poker
(b) Battleship
(c) Repeated RPS
Figure 5: Extensive-form games with tabular Q-learning best responses
DOON
Repeateed DOON
UUOO, Eutatioon
siusaD (Dura)
SE-0URD (Dun)
brer Dest dаppaise
Stnd
PAID
02
044
10 1b
15
(a) DRL Liars Dice
(b) DRL Battleship
(c) DRL Repeated RPS
(d) Repeated RPS mo
Figure 6: Extensive-form games with DDQN best responses
SP-PSRO outperforms APSRO and PSRO in each of the three games: Ledue Poker (Figure Sap. the small Battleship game (Figure 5b and 4-repeated Rock Paper Scissors (Figure 5c). In each game, we see drastic improvement performance starting in the first iteration.
6.3 DEEP REINFORCEMENT LEARNING EXPERIMENTS
When using deep reinforcement learning best- restoresp operators with DDQN (Van Hasselt et al. 2016), SP-PSRO outperforms APSRO and PSRO in terms of sample efficiency (Figure 6). Tested on Liar's 's Dice, a small version of Battleship, and 4x- Ex-Repeated RPS. SP-PSRO sees a significant im- provement against other baselines in early-iteration exploitability. This early exploitability advantage seen by SP-PSRO is especially present in repeated RPS (Figure(6c) (6)). where the relative performance seen with deep RL methods roughly matches that of tabular methods. Examining player's final restricted distribution after 5 iterations of SP-PSRO in repeated RPS (Figure we also see that the time-averaged new strategies have significantly more support than the standard best-responses, demonstrating their contribution towards exploitability improvements.
7
FUTURE WORK
SP-PSRO opens up exciting connections to the literature regarding learning approximate Nash equilibria in large games. In particular, although introduce unprincipled self play method for approximating a Nash equilibrium, future work can find better ways of creating a new strategy that will better approximate Nash equilibrium and therefore result in lower exploitability every iteration. For example, the data collected via the the opponent best response training against the restricted distribution can be used in a Monte-Carlo CFR-type algorithm to minimize regret on information sets visited during training. These directions also open up the possibility of deriving the first regret bounds for double oracle algorithms that do not rely on the size of the effective pure strategy set DDinh et al., (021). It also introduces the possibility of combining the deep reinforcement learning from the best response with methods based on deep CFR. For example, perhaps the Q networks learned from the best responses can be used to minimize regret for the new strategy. Finally, our algorithm is a normal-form algorithm in that it mixes at the root of the game tree. McAleer et al. (202I) showed that this can be exponentially bad in the worst case, and introduced tabular (XDO) and deep (NXDO) algorithms to fix this problem. An interesting future direction is combining SP-PSRO with XDO and NXDO.

---

Published as a conference paper at ICLR 2024
REFERENCES
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-17) 2002.
Ronen Brafman and Moshe Tennenholtz. R-max-a general polynomial time algorithm for near- optimal reinforcement learning. Journal of Machine Learning Research, 3(0ct):213-231, 2002.
George W. Brown. Iterative solution of games by fictitious play. Activity analysis of production and allocation, pp. 374-376, 1951.
Noam Brown, Adam Lerer, Sam Gross, and Tuomas Sandholm. Deep counterfactual regret mini- mization. In International Conference Machine Learning, pp. 793 802, 2019.
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Constantinos Daskalakis, Dylan Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. Advances in neural information processing systems, 33: 5527-5540, 2020.
Dongsheng Ding, Chen- Yu Wei, Kaiging Zhang, and Mihailo R Jovanović. Independent policy gradient for large-scale markov potential games: Sharper rates, function approximation, and game-agnostic convergence. arXiv preprint arXiv: 2022.
Le Cong Dinh, Yaodong Yang. Zheng Tian, Nicolas Perez Nieves, Oliver Slumbers, David Henry Mguni, Haitham Bou Ammar, and Jun Wang. Online double oracle. arXiv preprint arXiv:2103.07789. 2021.
Xidong Feng, Oliver Slumbers, Ziyu Wan, Bo Liu, Stephen McAleer, Ying Wen, Jun Wang, and Yaodong Yang. Neural auto-curricula in two-player zero-sum games. Advances in Neural Informa- tion Processing Systems, 34, 2021.
Roy Fox, Stephen M Mcaleer, Will Overman, and Ioannis Panageas. Independent natural policy gradient always converges in markov potential games. In International Conference on Artificial Intelligence and Statistics, pp. 4414-4425, PMLR, 2022.
Yoav Freund and Robert E Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1 (911-9)79-1 1999.
Eric A Hansen, Daniel S Bernstein, and Shlomo Zilberstein. Dynamic programming for partially observable stochastic games. Conference on Artificial Intelligence (AAAI), 2004.
Thomas Dueholm Hansen, Peter Bro Miltersen, and Troels Bjerre Sørensen. On range of skill. Conference Artificial Intelligence (AAAI), 2008.
Johannes Heinrich and David Silver. Deep reinforcement learning from self-play in imperfect- information games. arXiv preprint 103 2016.
Daniel Hennes, Dustin Morrill, Shayegan Omidshafiei. Rémi Munos, Julien Perolat, Mare Lanctot, et al. Neural
Audrunas Gruslys, Jean- Baptiste Lespiau, Paavo Parmas, Edgar replicator dynamics: Multiagent learning via hedging policy gradients. In Proceedings of the 19th International Conference Autonomous Agents and MultiAgen Systems, pp. 492-501, 2020.
Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu. V-learning simple, efficient, decentralized algorithm for multiagent rl. arXiv preprint 20X.v:2110.14555, 2021.
Michael Johanson, Nolan Bard, Neil Burch, and Michael Bowling- Finding optimal abstract strategies in extensive form games. In Conference on Artificial Intelligence (AAAI), 2012.
Patrick R Jordan, L Julian Schvartzman, and Michael P Wellman. Strategy exploration in empirical games. In 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS). Citeseer, 2010.
10

---

Published as a conference paper at ICLR 2024
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
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. Advances in Neural Information Processing Systems (NeurIPS), 2017.
Marc Lanctot, Edward I. Lockhart, lean-Baptiste Lespiau, Vinicius Zambaldi, Satyaki Upadhyay, Julien Pérolat, Sriram Srinivasan, Finbarr Timbers, Karl Tuyls, Shayegan Omidshafici, et al. Openspiel: A framework for reinforcement learning in games, arXiv preprint
2019.
Stefanos Leonardos, Will Overman, Ioannis Panageas, and Georgios Piliouras. Global convergence of multi-agent policy gradient markov potential games. arXiv preprint arXiv:2106. 01969, 2021.
Eric Liang, Richard Liaw, Robert Nishihara, Philipp Moritz, Roy Fox, Ken Goldberg, Joseph Gonzalez, Michael Jordan, and lon Stoica. Rlli:: Abstractions for distributed reinforcement learning. In International Conference Machine Learning, pp. 3053-3062. PMLR, 2018a.
Eric Liang, Richard Liaw, Robert Nishihara, Philipp Moritz, Roy Fox, Ken Goldberg, Joseph Gonzalez, Michael Jordan, and Ion Stoica. Rllib: Abstractions for distributed reinforcement learning. In International Conference on Machine Learning, pp. 3053-3062, 2018b.
Xiangyu Liu, Hangtian Jia, Ying Wen, Yujing Hu, Yingfeng Chen, Changjie Fan, Zhipeng Hu, and Yaodong Yang. Towards unifying behavioral and response diversity for open-ended learning in zero-sum games. Advances in Neural Information Processing Systems, 34:941-952 2021.
Luke Marris, Paul Muller, Marc Lanctot, Karl Tuyls, and Thore Graepel. Multi-agent training beyond zero-sum with correlated equilibrium meta-solvers. In International Conference on Machine Learning, pp. 7480-7491. PMLR, 2021.
Stephen McAleer, John Lanier, Roy Fox, and Pierre Baldi. Pipeline PSRO: A scalable approach for finding approximate Nash equilibria in large games. In Advances in Neural Information Processing Systems, 2020.
Stephen McAleer, John Banister Lanier, Kevin A Wang, Pierre Baldi, and Roy Fox. XDO: A double oracle algorithm for extensive-form games, Advances in Neural Information Processing Systems (NeurIPS), 2021.
Stephen McAleer, Gabriele Farina, Mare Lanetot, and Tuomas Sandholm. Escher: Eschewing importance sampling in games by computing history value function to estimate regret. arXiv preprint arXiv:2206.04412) 2022.
H Brendan McMahan, Geoffrey J Gordon, and Avrim Blum. Planning in the presence of cost functions controlled by an adversary. Proceedings of the 20th International Conference on Machine Learning (ICML), 2003.
David H Mguni, Yutong Wu, Yali Du, Yaodong Yang, Ziyi Wang, Minne Li, Ying Wen, Joel Jennings. and Jun Wang. Learning in nonzero-sum stochastic games with potentials. International Conference on Machine Learning, pp. 7688-7699. PMLR, 2021.
Paul Muller, Shayegan Omidshafiei, Mark Rowland, Karl Tuyls, Julien Perolat, Siqi Liu, Daniel Hennes, Luke Marris, Mare Lanctot, Edward Hughes, et al. A generalized training approach for multiagent learning. International Conference on Learning Representations (ICLR), 2020.
Nicolas Perez-Nieves, Yaodong Yang, Oliver Slumbers, David H Mguni, Ying Wen, and Jun Wang. Modelling behavioural diversity for learning in open-ended games. In International Conference on Machine Learning, pp. 8514-8524. PMLR, 2021.
Julien Perolat, Bilal Piot, and Olivier Pietquin. Actor-critic fictitious play in simultancous move multistage games. In International Conference on Artificial Intelligence and Statistics, pp. 919-928. PMLR, 2018.
11

---

Published as a conference paper at ICLR 2024
Julien Perolat, Remi Munos, lean-Baptiste Lespiau, Shayegan Omidshafiei, Mark Rowland, Pedro Ortega, Neil Burch, Thomas Anthony, David Balduzzi, Bart De Vylder, et al. From Poincaré recurrence to convergence in imperfect information games: Finding equilibrium via regularization. In International Conference on Machine Learning, pp. 8525-8535. PMLR, 2021.
Julien Perolat, Bart de Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome Connor, Neil Burch, Thomas Anthony, et Mastering the game of stratego with model-free multiagent reinforcement learning. arXiv e-prints, pp. arXiv-2206, 2022.
Oliver Slumbers, David Henry Mguni, Stephen McAleer, Jun Wang, and Yaodong Yang. Learning risk-averse equilibria in multi-agent systems. arXiv preprint arXiv:2205. 15434, 2022.
Samuel Sokota, Ryan D'Orazio, J Zico Kolter, Nicolas Loizou, Mare Lanctot, loannis Mitliagkas, Noam Brown, and Christian Kroer. A unified approach to reinforcement learning, quantal response equilibria, and two-player zero-sum games, arXiv preprint urXiv:2206.05825 2022.
Sriram Srinivasan, Mare Lanctot, Vinicius Zambaldi, Julien Pérolat, Karl Tuyls, Rémi Munos, and Michael Bowling. Actor-critic policy optimization in partially observable multiagent environments. Advances in neural information processing systems, 31, 2018.
Eric Steinberger, Adam Lerer, and Noam Brown. Dream: Deep regret minimization with advantage baselines and model-free learning. arXiv preprint arXiv:2006. 10410, 2020.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. In AAAI conference on artificial intelligence, volume 30, 2016
Oriol Vinyals, Igor Babuschkin, Wojeiech M Czamneki. Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in StarCraft using multi-agent reinforcement learning. Nature, 575(7782)350-3554 2019.
Jeffrey S Vitter. Random sampling with a reservoir. ACM Transactions on Mathematical Software (TOMS), 11(1):37-57, 1985.
Yongzhao Wang, Qiurui Ma, and Michael P Wellman. Evaluating strategy exploration in empirical game-theoretic analysis. International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2022.
Chen-Yo Yu Wei, Yi-Te Hong, and Chi-Jen Lu. Online reinforcement learning stochastic games. Advances in Neural Information Processing Systems, 30, 2017.
Michael P Wellman. Methods for empirical game-theoretic analysis. AAAI conference artificial intelligence, 2006.
Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang. Learning zero-sum simultaneous- move markov games using function approximation and correlated equilibrium. In Conference on learning theory, pp. 3674-3682. PMLR, 2020.
Runyu Zhang, Zhaolin Ren, and Na Li. Gradient play in stochastic games: stationary points, convergence, and sample complexity. arXiv preprint arXiv:2 200iv:20060000 00088, 2021.
Martin Zinkevich, Michael Bowling, and Neil Burch. A new algorithm for generating equilibria in massive zero-sum games. In Swenty-Second Conference Artificial Intelligence (AAAI), 2007.
12

---

Published as a conference paper at ICLR 2024
A LIMITATIONS
One limitation of SP-PSRO that if the new strategies happen to not be useful, including the new strategy hurt the performance of the restricted distribution. This is primarily because it is harder to learn a no-regret distribution when one the arms is changing, and secondly because including more actions (strategies) makes it harder for the no-regret algorithm as well. A related limitation of SP- PSRO is that because including the new strategy makes it harder to learn the restricted distribution, we find that SP-PSRO tends to plateau higher than APSRO and can even slightly increase exploitability, To mitigate this, one can switch over to APSRO after some iterations. but we have not introduced principled method of determining when is a good time to switch. A third limitation of our method is that extra compute needs to be used to train the new strategy v. Also, if the average strategy is computed via supervised learning on a replay buffer of experience, this adds additional memory requirements to the algorithm. Also, while ideas from this paper can potentially be applied to solution concepts beyond Nash equilibrium, we did not explore those directions in this paper.
B RELATED WORK
Many recent works study the intersection of reinforcement learning and game theory. QPG (Srinivasan et al. 2018) is an algorithm based on policy gradient that empirically converges to a NE when the learning rate is annealed. NeuRD (Hennes et al.) (020). Magnetic Mirror Descent (Sokota al. 2022), and F-FoRel. (Perolat et al., (021)) approximate replicator dynamics, mirror descent, and follow the regularized leader, respectively, with policy gradients. DeepNash, which based on F-FoReL and NeuRD has achieved expert level performance at Stratego (Perolat et al., 2022). Markov games generalize MDPs where players take simultaneous actions and observe the ground state of the game. Recent literature has shown that reinforcement learning algorithms converge to Nash equilibrium in two-player zero-sum Markov games (Brafman & Tennenholtz/ 2002] Wei et al. 2017]
Perolat et al.
2018 Xie et al. 2020 Daskalakis et al. 22000] Jin 20021) and in multi-playee
general-sum Markov potential games (Leonardos et al. 2021 Mguni et al. 2021 I Fox et al. 2022]
Zhang al.
2021 Ding et al. 2022). Deep methods based CFR (McAleer al. 2022 Steinberger
et al., 20020 Brown et al.) (219)) are another promising direction for scaling to large games. In this work we focus on different set of deep RL algorithms for games based PSRO. Advances made to
PSRO can potentially be combined with the above methods via XDO (McAleer et al. 2021)
B. DOUBLE ORACLE (DO) AND POLICY SPACE RESPONSE ORACLES (PSRO)
Double oracle (McMahan et al. 2003) is an algorithm for finding a Nash equilibrium (NE) in normal-form games. The algorithm works by keeping a population of strategies IIf time t. In each iteration, a NE x is computed for the game restricted to strategies in II'. Then, a best response to this restricted NE for each player (R,( 2 is computed and added to the population IT(+1 IT ( for i E (1, 2). Although in the worst case DO must add all pure strategies, in many games DO empirically terminates early and outperforms alternative approaches.
Algorithm 4 Policy Space Response Oracle (PSRO) Lanctto et al. 2017)
Result: Nash Equilibrium Input: Initial population IIo
repeat (for / = 0, 1, 1,...
n² <- NE game restricted to strategies ITe
for i E 21. do
for m iterations do
Update policy 3_ toward BR_;(T))
II IIŞ U { for i {1,2}
until No novel best response exists for either player Return: n²
Policy-Spare Space Response Oracles (PSRO) (Lanctot al. 2017) scales DO large games by using reinforcement learning to approximate best response. The restricted-gant NE is computed on the restricted game matrix (/1l, generated by having each policy in the population IT play each opponent
13

---

Published as a conference paper at ICLR 2024
policy and tracking average utility in a II I2 payoff matrix (Wellman 2006). PSRO is described in Algorithm
Several methods related to PSRO have been published in recent years. AlphaStar ( (Vinyals et al. (019) trains a population of policies through a procedure that is somewhat similar to PSRO. AlphaStar also uses some elements of self-play when constructing its population, and outputs population-restrictt NE at test time. NXDO (McAleer et al. 2021) iteratively adds reinforcement learning policies to a population but solves an extensive-form restricted game, which has been shown be more efficient than solving a matrix-form restricted game as in PSRO. P2SRO (McAleer et al., 2020) parallelizes PSRO with convergence guarantees. Other work has looked at incorporating diversity (Liu al. 2021; Perez-Nieves et al., 2021) in the best response objective. However, since the best response still pure in most implementations, these methods suffer from the same problems of PSRO and APSRO as previously described. Other methods generalize PSRO to more players (Muller et al. al. 202T). and meta-learn the restricted-NE: population distribution (Feng et al. 2021). Slumbers al. (022) propose PSRO-like approach for learning risk-averse equilibria.
Marris 2020,Marris
2020,
B.2
MINIMUM-REGREE CONSTRAINED PROFILE
The concept of finding a low-explottability distribution a restricted game was also explored in Jordan al. (010)) and Wang al. (2022), which define the minimum regret constrained profile as the distribution over a restricted population that achieves the lowest exploitability. In this paper, we use the term exploixxll restricted distribution for the same concept because we believe better emphasizes the fact that this restricted distribution is the least-exploitable distribution over the restricted population.
B.3 RANGE OF SKILL ALGORITIIM (ROS)
This paper presents ADO, which be viewed as modification to the range of skill (ROS) algorithm introduced by Zinkevich et al. (2007) and further explored in Hansen et al. (2008). ROS is a variant of the DO algorithm that likewise produces series of restricted games by iteratively adding new strategies. As in ADO, ROS defines in each iteration two separate restricted games, in each of which one player is restricted play strategies in their population while the other player is unrestricted. The similarity between ROS and ADO continues in computing a Nash equilibrium strategy profile for each restricted game, such that the restricted player's 's strategy is the least-exploitable restricted distribution.
However, ADO and ROS differ in the strategy that they then add to the unrestricted player's 's population. ADO adds best response to the restricted distribution, while ROS adds strategy that is part of the unrestricted player's NE strategy the restricted game.
This difference proves crucial when scaling up to large games. In large games, solving the restricted game where one player is unrestricted infeasible and as a result methods based on ROS cannot scale to large games. Alternatively, since ADO only adds best responses, it naturally scales to large games via APSRO where the best responses are learned through RL.
Additionally, while ROS, like ADO, decreases exploitability monotonically and performs well in practice, the only known convergence guarantees for ROS are asymptotic with a convergence rate that is exponential in the size of the game (Hansen et al. 2008). In contrast, ADO is guaranteed to converge in a number of iterations at most the number of pure strategies in a game.
14

---

Published as a conference paper at ICLR 2024
C APSRO AND SP-PSRO NO-REGRET ALGORITHMS
In the inner loops APSRO and SP-PSRO, we update of via regret minimization against [3,,. To do this, we use two different no-regret algorithms, the exponential-weight algorithm (Exp3) (Auer it al. 2002) for tabular extensive-form experiments and the Multiplicative Weights Update (MWU) algorithm (Cesa-Bianchi Bianchi & Lugosi 2006 Freund & Schapire 1999) for deep RL extensive-form experiments.
C.I ExP3
Exp3, shown in Algorithm is an adversarial bandit method that has sublinear regret. We use Exp3 no-regret restricted game solver in tabular APSRO and SP-PSRO experiments. We perform batches of multiple RL updates in alternation with batches of multiple Exp3 updates. Exploitability evaluated using the final Exp3 sampling distribution P, for each APSRO/SP-PSRO iteration.
Algorithm 5 Exp3
Input: iterations, & actions, parameter Initialize cumulative rewards So (0,0,...))
for / 1,..., n do
expln 2.1/k)
Calculate the sampling distribution Pt.: Pt.i (1 7) En 1op(781-1.//1 E for each
E [1..A] Sample action A, Pi and observe reward X₁
Calculate Se.: St, S,-1, X,1(A,=1)
Pe,
C.2 MULTIPLICATIVE WEIGHTS UPDATE
The Multiplicative Weights Update (MWU) algorithm is online learning method which converges in time-average to Nash equilibrium (Cesa- & Lugosi [006 Freund & Schapire 1999). We use MWU, shown in Algorithm 6 as our no-regret restricted game solver in deep RL APSRO and SP-PSRO experiments. For all games, perform a metasolver update once after multiple iterations of our RL best response algorithm. When measuring exploitability, we evaluate the final output x as the time-average of the MWU sampling distribution P. over single APSRO/SP- PSRO iteration.
Algorithm 6 Multiplicative Weights Update
Input: n iterations, k actions, learning rate 7) Initialize cumulative rewards S. (0.0....0)
for t 1,... n2 do
eapinS. for each i [1..k]
Calculate the sampling distribution Pt,s: Pt,s ES cap(nSi-1.))
Observe reward Xt,s for each action [1..k] for i 1....k do Calculate St, St, S + X
15

---

Published as a conference paper at ICLR 2024
D DOUBLE ORACLE VS ANYTIME DOUBLE ORACLE
To demonstrate how DO can increase exploitability in every iteration except the last, consider generalization of the game presented in Figure [ where all values are except if the row index is one more than the column index c, in which case the value for the row player is 2. 2 + 2i, or if the column index is one more than the row index in which case the value for the row player is Ei= 22' + 2i. We plot the performance of DO and ADO in this game with 10 actions in Figure 7a and show that DO increases exploitability in every iteration except the last, while ADO does not increase exploitability.
Figure 7b also compares DO and ADO on random normal-form games with 500 actions. We see that ADO greatly outperforms DO and tends not to increase exploitability. To create random normal-form games, we sample payoff values from Uni.
DO Bad Case with 10 Actions
Random Normal Form Games
DO
1.00
D0
150
ADO
ADO
Exploitability
Exploitability
0.75
100
0.50
0.25
0.00
6
10
0
20
40
60
80
100
Iteration
Iteration
(b)
Figure 7: (a) DO can arbitrarily increase exploitability before convergence, whereas ADO monotoni- cally decreases exploitability and guarantees convergence to Nash equilibrium. (b) Random Normal
Form Games with 500 Actions
16

---

Published as a conference paper at ICLR 2024
E ADDITIONAL NORMAL-FORM EXPERIMENTS
In this section we report additional normal form game experiments. All games in this section are from Perez-Nieves et al. (202T). Note that the zeroth iteration is not included in the plots. Similar to the main results in the paper we find that SP-PSRO achieves much lower exploitability than existing PSRO based methods and does so much faster, across all games studied. We include an ablation, labeled SP-PSRO Not Anytime, that is the same as SP-PSRO in that it trains new strategy to be a best response to the opponent best response, but unlike SP-PSRO does not update the restricted distribution via no-regret as in anytime PSRO. As shown in the figures, anytime PSRO is a crucial piece of SP-PSRO, and excluding this aspect results in much worse performance. We find that when anytime PSRO is excluded, the opponent best response will be best responding to a static opponent, and the best response to this best response will tend to be a pure strategy. As a result, we do not get to explore the strategy space, and the average new strategy will simply be another pure strategy. In some games we see that SP-PSRO Not Anytime and PSRO converge to lower exploitability than SP-PSRO and anytime PSRO. This is because SP-PSRO Not Anytime and PSRO both use exact meta-solvers, which return the exact Nash equilibrium upon convergence, while SP-PSRO and APSRO use an approximate no-regret procedure to find the least-cxploitable restricted distribution.
Random Games with 30 Actions
Elo Game Noise D.1
Elo Game Noise 0.5
1.00
SP-PSRO (Ours)
SP-PSRO
(Ours)
Siblotabiity
0.75
0.50
SP-PSRO Not Anylime
APSRO
PSRD
Explottabiiity
3.0
1.5
SP-P5RO Not Anytima
APSRO
PSRC
Exploitebiiit
1.0
APSRO
PSRO
SP-P5RO Not Anytime
0.25
0.3
0.5
0.00
0.0
0
5
20
15
20
25
0.0
0.5
1.0
1.5
2.0
2.5
3,0
0.0
0.5
1.0
1.5 Beration
2.0
2.5
3.0
Iteration
ationn
(a) Random Games with 30 Actions
(b) Elo Game Noise 0.1
(c) Elo Game Noise 0.5
Elo Game + Noise 1.0
Kuhn Poker
Normal Bernoulli Game
1.5
SP-P5RO (Ours)
0.6
SP PSRO [Ours)
SP-PSRC (Ours)
Expleitabiiity
1.0
SP PSRO Not Anytime
PSRO
Sgglorabiiity
0.4
SP PSRO Anytime
PSRO
Expletabiity
1.0
PSRO
APSRO
PSRC Not Anytime
0.5
0.2
0.0
0.0
0.0
0.0
2.5
7.5
12.5
Ieeation
Itoration
Earation
(d) Elo Game + Noise 1.0
(e) Kuhn Poker
(f) Normal Bernoulli Game
Go Board Size 3
15
Random Game of Skill
SP PSRO (Durs)
2.0
Quoridor Board Size
SI-PSRO (Ours)
Egletabiity
1.5
SP-PSRO (Ours)
Expletaaiiit
1.0
APSRO
Selotabitty
1.5
APSRO
PSRO
1.0
APSRO
PSRO
0.5
SI-PSRO Anytime
1.0
SP-P5RD Not Anytime
SP PSRO Not Anytime
0.3
0.0
0.0
0.0
10
15 Reration
20
25
30
Rteraiio
Reration
(g) Go Board Size
(h) Random Game Skill
(i) Quoridor Board Size 4
Hex Board Size
Triange Game Size 1000
Triange Game Size 120
2.0
SP-PSRO (Curs)
2.0
pgletablig
1.5
PSRO
APSRO
155
SP-PSRO (Ours)
Exploitabiity
1.5
1.0
SP-P5RO Anytime
10
PSRO
APSRO
1.0
SP PSRD (Ours)
0.5
SP-PSRD Not Anytime
APSRO
PSRO
PSRO Anytima
0.0
0.0
7.5
12.5
0.0
2.5
5.0
7.5
10.0
12.5
0
10
15
20
25
30
Reration
Iteration
Iteration
(i) Hex Board Size 3
(k) Triangle Game Size 1000
(l) Triangle Game Size 120
Figure& 8: Additional Normal-Form Game Experiments
17

---

Published as a conference paper at ICLR 2024
E. NORMAL-FORM ABLATIONS
In this section we run ablations with different levels of À for updating the best response. As shown in these experiments, the relative performance does not change much.
AlphaStar with Lambda
AlphaStaar with Lambda
AlphaiStar Lambda
AP3RO
APSRO
APSRO SP PSRO
Selotabilty
1.5
SP PSRD
Explortatite
1.5
PSR0
SP PSRD
Spportebiigg
1.5
PSRO
2.0
0.0
0.0
0.0
0.0
2.5
5.0
7.5
10
12.5
15.0
0.0
2.5
5.0
7.5 Iteration
10.0
12.5
15.0
0.0
2.5
5.0
7.5
10.0
12.5
15.0
Iteration
Reeraion
Figure 9: Changing the À parameter does not change the results very much.
E.2 PSRO-RECTIFIED NASH
We additionally compare to PSRO-Rectified Nash baseline. Since we only focus on methods that are guaranteed to converge to Nash equilibrium, and since PSRO Rectified Nash has been shown not to converge to NE McAleer et al. (2020), do not include this baseline in the main text. As shown here, is able to outperlorm DO while underperforming ADO in random games.
Random Normal-Form Games with 5C0 Actions
Exploiabilitty
PSRO RN
1.
ADO
10
35
Reration
Figure 10: ADO outperforms PSRO-Rectified Nash on random normal form games.
F ADDITIONAL TABULAR EXPERIMENT ON GOOFSPIEL
We additionally compare SP-PSRO and APSRO against PSRO on Goofspiel with tabular Q-learning best responses. As shown in figure I1 like in other games, SP-PSRO heavily outperforms APSRO and PSRO early-iteration exploitability. APSRO outperforms PSRO in carly-iteration exploitability but not by as much SP-PSRO. The high cecaaion-over-iteratioo variance and final exploitability that APSRO exhibits is likely due to APSRO's approximate solution to its restricted game. The accuracy of APSRO's ' no-regret solution for n" dependent on the number of inner-loop iterations and the ratio of approximate best-response updates to no-regret updates. The optimal values for each game may vary, and these hyperparameters were kept constant across all games on tabular experiments.
Goofspiel
SP-PSRO (Ours)
0.75
(Durs)
PSRO
0.50
0.25
0.00
20
60
100
meration
Figure 11: Extensive-form Goofspiel with tabular Q-leaming best responses
18

---

Published as a conference paper at ICLR 2024
G ADDITIONAL DEEP RL EXPERIMENTS
G.1 LAST-ITERATE SP-PSRO
We compare an alternate last-iterate version of SP-PSRO against the default SP-PSRO method and other baselines in Figure 12 In the SP-PSRO last-iterate variant, we add the pure-strategy weights of V in its final RL iteration to the population rather than calculating and adding the time average 1/:- Exploitability is also calculated using Vi rather than VG SP-PSRO last-iterate improves upon APSRO and PSRO due to the additional, potentially useful, population policy. However, vs less able to roughly approximate NE because it represents single pure-strategy approximate best-response to B_, rather than a mixture of multiple approximate best-responses distributed across each time-slice of an SP-PSRO iteration. Because of this, still see an additional gain in exploitability versus sample-efficiency when transitioning from SP-PSRO last-iterate to the default time-average version of SP-PSRO.
Liar's Dice DDON
Small Ballleship DOON
Reppeeledd
1.0
SP-PSRO (Ours)
SP-PSRG (Ours)
PSRO
AMSRD
Explo
Expertailiyy
PSRO
A/5RO
0.6
PSRO last-itoreto
APSILL
PSRC lest itersto
PSRC
0.0
SP PSRO last Atorto
0.2
1.-
0.0
0.4
0.6
1.2
14
3.2
1.0
En sodes
167
Episodes
leb
Epicodes
l07
(a) DRL Liars Dice
(b) DRL Battleship
(c) DRL Repeated RPS
Figure 12: SP-PSRO last-iterate on extensive-form games with DDQN best responses
G.2 SP-PSRO NOT ANYTIME
Similar to the additional normal-form experiment in Appendix E. we compare against a variant of SP-PSRO denoted as SP-PSRO Not Anytime. In this variant, the Nash equilibrium for the restricted game over 11f is used as n², similar to PSRO. By ablating the no-regret restricted-gant SP-PSRO Not Anytime has phases in which it dramatically increases exploitability as iterations progress in Small Battleship and 4-Repeated RPS. We note that because the training dynamics of 3 and v/ are affected by the choice of π it is possible that SP-PSRO Not Anytime will learn less effective population strategies. We find that SP-PSRO Not Anytime outperforms PSRO and APSRO but underperforms SP-PSRO. This lends evidence to the hypothesis that the success of SP-PSRO is due to both the new strategy and the anytime regret- segeret-iniiizttion procedure working together.
solver,
Liar's Dice DDON
Small Battleship COON
4 Rappatted RPS DDON
1.0
PSRD (Ours)
SP SP-PSRO (Oum) PSRO
..n
PSRO SP-IS0D Aoydmm
(Ours)
Broastaaitty
2.0
SP PSRD (Burs) Apudo (Ours)
Brpistaality
0.6
SIMPRO Not-Anytire
Pello
0.0
0.2
0.0
0.2
0.4
0.6
0.8
1.0
1.2
14
0.0
0.2
0.4
0.6
0.8
1.0
Eu sodas
Episodes
Episodes
Figure 13: Additional ablation demonstrating the exploitability of a Not Anytime variant of SP-PSRO in deep RL experiments.
G.3 HEAD-TO-HEAD VS RANDOM PERFORMANCE
For each primary algorithm tested, we compare the performance of n" against opponent that selects actions randomly. In games where playing randomly isn't 't an NE like Liar's 's Dice and Small Battleship. performance against a fixed random opponent is roughly anticorrelated with exploitability. Each method performs equally against random in 4-Repeated RPS because playing randomly aligns with the NE in this game, random opponent is not exploitable.
19

---

Published as a conference paper at ICLR 2024
Small Battleship
4- A-Repeated DDON
0.0
Buedoon
AP580 (UT5)
SR PSRD (Durs)
SPasno (Curs) APSRO (0urs)
Unaitt vs
300 Ac
APSRO
Numany
Anytime
-03
0.0
0.0
0.2
0.4
10.6
0.8
10
12
14
0.0
0.2
01.4
0.6
0.8
1.
167
Episndea
105
Eprandes
107
Figure 14: Performance Random for each Deep RL method as function of experience collected on Liar's Dice, Small Battleship, and 4 4-Repeated RPS.
G.4 PSRO KEEP BEST NE
As an additional baseline, we evaluate a variant of PSRO where one keeps the least-exploitable meta- NE seen so far. By construction, this algorithm does not increase exploitability, but still performs slightly worse than APSRO.
Liar's Dice DDON
Small Battleship DOON
4 Repeated RPS DDON
1.0
ERRP (Curs)
SP PSRD (Ouns) APSRO (Durs)
0.0
APSRO
Explottabitty
(Ours) APSRC (Durs)
keep
PSRC
0.
1.0
PERO Koop 4ist
1o5
Figure 15: Exploitability of methods including baseline where PSRO keeps the best meta-NE each iteration.
20

---

Published as a conference paper at ICLR 2024
H PROOFS
H.1 PROOF OF PROPOSITION 1
Proof. Let nr' be the restricted NE in ADO iteration f. Then for player i, since IT; C m
U/ (T BR,,(((
max min (a(m, T-1)
=:ent n-t
< max min mine, m-:) =
(2)
-,( (R_
Since each player's value is monotonically non-decreasing, the value of the best response is non- increasing, and the exploitability of n³ is also non-increasing:
(x*t1)===
Σ cn(mlt BR (T?+t(?
(3)
s - Σ (t( (B))(T))) = e(
H.2 PROOF OF PROPOSITION 2
Proof. Let 75) and (T1, m5) be the NE in the restricted games G and G2 for player and respectively, termination. If ni or TT have support outside the population, ADO would not terminate, because there would exist another novel best response. Hence, at termination, the support of both アं and T/y are inside the population and they feasible for their respective player's restricted game. Then
01 (Ti, T²)
S 6e (TÍ, mb)
S < m5))
S (n m3))
< vi (
The four inequalities follow, in order, because: (a) player doesn't want to deviate from zí to of in G2; (b) player 2 doesn't 't want to deviate from nH Ty in G2; (c) player doesn't 't want to deviate from o. to γं in G¹; and (d) player doesn't want to deviate from Th to TH in G¹.
Therefore, ii (T[, m 0i (Ti. m5) which implies that player has no incentive to deviate from mf to oi or any other strategy against Tz. A symmetric argument holds for player 2, implying that n" is Nash equilibrium in the full game.
H.3 PROOF OF PROPOSITION 3
Proof. The proof follows the same argument as used in Theorem of Johanson et al. (2012). By a folk theorem of game theory, know that algorithms with regret 1?; and R2 play each other in self play in a two-player zero-sum normal-form game, their average joint strategy at time n, T", will have exploitability less than or equal to R + So it remains to show that the best responder has negative regret. To see this, note that changing the action at all time steps to be any one action for best responder would be no better than the actual action, which was the best response.
H.4 PROOF OF PROPOSITION 4
Proof. Let nr be the restricted NE of APSRO at iteration t. Then
0i (mf (R)) < max min o;( m-1) * n-
(5)
max min v. (T m_x)
(6)
S u (mf+) ( C,
21

---

Published as a conference paper at ICLR 2024
where 5 follows from oद being feasible for player i's restricted game in iteration t, whose value is on the right-hand side; ( from population monotonicity 11; S I1 and 7 from the e-exploitability of mt in the restricted game in iteration t 1. The proposition now follows from
c(n 1+1 == Σ (i(m (R.
(8)
S Σ (vi(T) (T()((()) -c) = =e(TT) + 2e.
22

---

Published as a conference paper at ICLR 2024
I ANALYSIS OF RESTRICTED GAME DISTRIBUTIONS
In this section, qualitatively analyze the learned restricted game distributions n' over the pop- ulations of PSRO, APSRO, and SP-PSRO. We examine checkpoints from a single seed of each of deep reinforcement learning experiments in section 6.3 on Liar's Dice, Small Battleship, and 4-Repeated RPS. Given these checkpoints, we observe the first player's learned restricted distribution To for the first 7 iterations of each algorithm. For PSRO, x" is the NE the restricted game, whereas in APSRO and SP-PSRO, x" is an approximate no-regret solution for each player to the restricted game with an unrestricted opponent.
each iteration, PSRO and APSRO add single new best response 3_ for each player to y- In addition to B_s. SP-PSRO adds a time-average of the new-strategy V7 II, in each iteration. These distributions zi over the first player's 's population are shown for Liar's Dice in figure 16 for Small Battleship in figure 17 and for 4- 4-Repeated RPS in figure
18
1997 3pw FS10 VaRAAi 2enri drona Fach 00 Aworiie
Llan' Dere 2/5BD Petvcciunn DuttOatTINN UnN Doltenatin
Larrs Date -24550 socorise DiA Fart DO twweiin
1S04 Nov Boys
32
11
(a) PSRO
(b) APSRO
(c) SP-PSRO
Figure 16: PSRO. APSRO, and SP-PSRO mixed strategy solutions for Liar's Dice in the first 7 iterations of each algorithm.
23

---

Published as a conference paper at ICLR 2024
featidrrs
Cancee diner
12
2003
Fre Soeteettrr
(a) PSRO
(b) APSRO
(c) SP-PSRO
Figure 17: PSRO, APSRO, and SP-PSRO mixed strategy solutions for Small Battleship in the first 7 iterations of each algorithm.
The NE to the restricted games, provided by PSRO in figures 16a 17a and 18a strongly favor the latest-added best responses early iterations of the algorithm. While the latest best response likely to be strong strategy in restricted game, an NE to the restricted game in early iterations of PSRO may not be the least exploitable mixed strategy against strategies outside the population. APSRO, shown in figures 66b 17b and T8b) optimizes for no-regret solution to each restricted game where opponent can use any strategy the full game. By reducing exploitability against any possible opponent strategy rather than just those in 1I, APSRO learns notably distinct mixed strategy n² compared to PSRO that's safer for carly-stopping.
SP-PSRO, in figures 16c 17c and 18c also optimizes for no-regret restricted-game mixed strategy against an unrestricted opponent. Like APSRO. SP-PSRO adds a best response 33 for each player to the population in each iteration. In each iteration, SP-PSRO also adds the time-averaged new strategy D; to the population. Unlike the best responses, i is included in the restricted distribution π. for the same iteration that it is trained. i; is intended very roughly approximate the strategy which most
24

---

Published as a conference paper at ICLR 2024
reduces the exploitability of the population against an unrestricted opponent. In figures 16c 17c and
18c we see that by their high weight in zo that the io we learn are indeed strong against unrestricted opponents. In each iteration, the no-regret mixed strategy z puts the most weight the "Current Iee New Strat" in strategy that was trained in that iteration. 'hee "Population New Strat" strategies Po also assigned equal higher weight in oo than the "Population Best Response" strategies 3g. showing that the time-averaged new strategies still serve as high-quality population strategies in iterations after those in which they are trained.
The houd
38.
Truuttio Sersoy
7e0. Sewser
(a) PSRO
(b) APSRO
(c) SP-PSRO
Figure 18: PSRO, APSRO, and SP-PSRO mixed strategy solutions for 4-Repeteed RPS in the first iterations of each algorithm.
25

---

Published as a conference paper at ICLR 2024
J EXTENSIVE-FORM GAME ENVIRONMENTS
All extensive-form games tested with are from the OpenSpiel framework (Lanctot et al. 2019), and can be loaded using OpenSpiel with the following parameters:
Ledue Game Name: leduc_poke Parameters: ("players": 2
Goofspiel Game Name: goofspiel
Parameters: ("imp_ ("imp_info* info": True, "num_cards" 5,
Tiny Battleship Game Name: battleship
Parameters: @hoard_width? 2, "board_heigg" heighth: 2,
"ship_sizes": [[1]', semip_values"; ' [11', "num_shots": 2, "alloo_reppeteessshot""" False, }
Small Battleship Game Name: battleship
Parameters: ("board_width") 2, "board_height", 2, "ship_sizes" "[1;2]", "num_shote 4, "allow belloo_repeetee_shhteee False)
"[1;2]",
4x Repeated RPS Game Name: repeated_game game
Parameters: ("num "aaau__rppeiiionss. 4, "enable iiaableeinfsttate" True,
"stage_game": "matrix_rps")
Liar's Dice Game Name:
dice
Parameters: None
Goofspiel and Repeated RPS are converted from simultancous-move games into turn-based games using OpenSpiel's convert_to tetotto___assseeeeeeeeeeeeeeeeee game transform. Repeated RPS is created from the matrix_rpa rps game using the rrreate_repeated game transform.
K TABULAR TRAINING DETAILS
For PSRO, APSRO, and SP-PSRO experiments with tabular Q-learning BRs, we used OpenSpiel's Python implementation rameters were OpenSpiel defaults and were constant between PSRO, APSRO, and SP-PSRO; step size 0.1 and epsilon 0.2.
tabular epsilon-greeds Q-learner. For games, Q-learning hyperpa-
In all tabular experiments, when calculating the payoff for strategy profile (1,(T)), the payoff is calculated exactly using a full tree traversal.
K.1 PSRO
In each iteration of tabular PSRO experiments, we first compute the restricted game payoff matrix, and we then use linear programming to find the NE of the restricted game. We train Q-learning agents for each player against the other's restricted game NE and add these to the population.
K.2 SP-PSRO AND APSRO
We performed hyperparameter sweep to find the number of episodes per iteration and number of Exp3 updates per iteration which minimize exploitability in Ledue poker after 35 iterations of SP- PSRO (Table T]. We used these hyperparameters for SP-PSRO and APSRO for tabular experiments in all games.
(e-1)9 where is an estimated upper bound on the total cumulative regret upon completion of the algorithm. In each iteration, we split the Q- learning training and Exp3 updates into 600 equally-sized batches each and alternate between a batch of Exp3 updates and a batch of Q-learning episodes until the end of the iteration. We target total of 800, 000 episodes and 20, 000 Exp3 updates per iteration, and we repeat the following 600 times: for each player, perform 1800, 000/600 1333 Q-lannning episodes followed by [20, 000/600 = 33
Each APSRO/SP- iteration, we set y to min (1, Aologg
26

---

Published as a conference paper at ICLR 2024
Exp3 updates. While target 800, 000 episodes and 20, 000 Exp3 updates per iteration, due to rounding, the actual amounts performed are smaller:
episodes per iteration
799,800
Exp3 updates per iteration
19,800
Q-learning learning
0.025
Q-learning exploration
Constant, 0.2
Table I:
Tabular experiment details
For each Q-learning episode: sample policy for player from the distribution xi and then the sampled policy πy and the opponent Q-learning agent for 3_; play an episode against each other. If the sampled policy n, corresponds to the strategy vs, it plays with e-greedy exploration. The opponent Q-learning agent always plays with c-greedy exploration. The episode used to update the Q-learning agent for B_i. The episode is also used update the Q-learning agent for v4, regardless of whether or not the chosen π. is Vi.
For tabular APSRO, create new policy V/.
the code for SP-PSRO, with the difference being that do
L DEEP RL TRAINING DETAILS
For deep RL experiments, we the same RL best response hyperparameters in PSRO, APSRO, and SP-PSRO. When RL best responses are calculated, an independent best response learning process is performed for each player. RL hyperparameters for each game were selected based sample efficiency and final performance against fixed opponent.
Our deep RI. code built top of the RLlib framework (Liang et al. 2018b), and any hyperpa- rameters not specified are the version 1.0.1 defaults.
L.1 PSRO
The PSRO restricted payoff matrix estimated using 3000 evaluation rollouts per policy matchup, and the meta-game NE is calculated using 2000 iterations of Fictitious Play (Brown 1951). APSRO and SP-PSRO skip calculating the restricted payoff matrix. We do not count experience used to generate payoff matrix utilities in comparisons with PSRO.
L.2 APSRO
In deep RL experiments, & Lugosi 2006); Freund & Schapire (1999) as our no-regret solver for APSRO with a learning rate 0.1, updating every 10th RL iteration. Action payoffs for MWU corresponding to expected utilities for population policies in II; against the current 9_ are estimated by averaging the empirical payoffs from the 1000 rollouts which each population policy was sampled. Exploitability measured against the time-average of the MWU mixed-strategy from each APSRO iteration.
the Multiplicative Weights Update (MWU) algorithm Cesa-Bianchi
L.3 SP-PSRO
For SP-PSRO, we use the same MWU no-regret solver and parameters as we do with APSRO, where the actively-learning new strategy v; included as an action for the no-regret solver. Because vs would by default only collect experience when the no-regret solver samples it, additionally provide is with off-policy experience from all other policies the population 11 when they are sampled and generate experience well.
We train the time-average 17, of Di as a neural network, and to do so, we save all experience generated by 1/2 to a buffer using reservoir sampling (Vitter 1985 Heinrich & Silver 2016) with maximum capacity of 266 samples. After BR training is complete, we use supervised learning to train a softmax policy the reservoir buffer data with cross-entropy loss actions given observations distill the
27

---

Published as a conference paper at ICLR 2024
time-average of the policy 14- To ensure that enough experience from 14 is always generated and added to the reservoir buffer, a small fixed portion p of all experience rollouts in the BR training matchup between V4 and non-exploring evaluation copy of B-
process is forced to be played
For Liars Dice, = 0.05, and for Small Battleship and 4x Repeated RPS, = 0.1. We train each 1; the reservoir buffer data with learning rate of 0.1 for 10,000 SGD batches. We MLP with three 128-umit layers and ReLu activations for D; in all games.
Exploitability is measured against the time-average of the MWU strategy from each SP-PSRO iteration where ii is used to represent the new strategy.
When the population strategy v; and the BR 8-, collect experience against each other, unless otherwise stated, they both use and play against exploring c-greedy versions each other.
L.4 BEST RESPONSES
Hyperparameters train deep RL best responses for each game are provided below. We use DDQN (Van Hasselt et al. 2016) to train RL best responses for all deep RL experiments. Any hyperparameters not listed are default values in RLlib (Liang et al. 2018a) version 1.0.1.
algorithm
DDQN
circular replay buffer size prioritized experience replay
50,000
No
total rollout experience gathered each iter
2048 steps
learning rate
0.0026
batch size
4096
optimizer
Adam KKngmaa & Ba 2014
TD-error loss type
MSE
target network update frequency
every iteration
MLP layer sizes
[128, 128]
activation function
ReLu
discount factor
1.0
best response RL process stopping condition exploration
7.5e5 timesteps
Linearly annealed from 0.06 to 0.001 over 2e5 timesteps
Table 2: Liar's s Dice Deep RL Best Response Hyperparameters
algorithm
DDQN 200,000 No
circular replay buffer size
prioritized experience replay
total rollout experience gathered each iter
1024 steps
learning rate
0.0019
batch size
2048
optimizer TD-error loss type target network update frequency
Adam Kingma & Ba 2014
MSE
every le5 timesteps
MLP layer sizes
[128, 128, 128]
activation function
ReLu 1.0
discount factor
best response RI. process stopping condition
3e5 timesteps (Repeated RPS) &
7.5e5 timesteps (Battleship)
exploration
Linearly annealed from 0.06 to 0.001 over 2e6 timesteps
Table 3: 4x Repeated RPS and Small Battleship Deep RL Best Response Hyperparameters
28

---

Published as a conference paper at ICLR 2024
M COMPUTATIONAL COSTS
Experiments were run on local machine with 128 logical CPU cores, Nvidia RTX 3090 GPUs, and 512GB of RAM. Each tabular experiment run used a single core, and each deep RL experiment run used up to 5 CPU cores per player to train best responses and up to 4 CPU cores to evaluate meta-game empirical payofts, for maximum total of 14 cores per deep RL experiment. All deep RL experiments individually used less than 5GB of VRAM. Tabular and deep RL experiments had durations between and days.
Concerning storage requirements, although PSRO-based methods need to store network weights for generated population policies on disk, we found disk-space usage to non-issue as population sizes were generally on the order of at most hundred policies. Table describes the final population size and disk usage for each game tested in deep RL experiments. SP-PSRO generates twice as many policies as PSRO and APSRO because SP-PSRO also saves and adds each iteration's 's average new strategy to the population.
Final Population Size
Disk Usage Per Policy
Total Disk Usage
PSRO
32, 26, 74
152KB, 152KB, 148KB 152KB, 152KB, 148KB
4.864MB, 9,25MM, 10.952MB 4.864MB, 3.952MB, 10.952MB 9.728MB, 7.904MB, 21.904MB
APSRO
32, 26, 74
SP-PSRO
64, 52, 148
152KB, 152KB, 148KB
Table 4: Population sizes and policy disk-space usage for Liar's Dice, Small Battleship, and Repeated RPS
N
CODE
Code for deep RL experiments is available at htttp:://github. com/ wtt.:ooo/iiinnyann attaab//ppppr-- under the MIT license. Our code is built on top of the OpenSpiel (Lanctot et al. 22119) and RLlib
(Liang et al. 20) frameworks, both of which are open source and available under the Apache-2.0 license.
29


Reviews:
[{"review_id": "u3y9y6CRrr", "reviewer": "Reviewer_xLd8", "summary": "The authors consider the problem of approximating a Nash equilibrium in a two-player zeros-sum imperfect information games with perfect recall. They propose a new double oracle algorithm, the anytime double oracle (ADO) algorithm that builds a population of policies by adding the best response against an optimal policy of restricted games (restricted by using only a mixture of policies present in the population). They show that the exploitability of ADO, contrary to the one of DO, decrease at each iteration. They also propose the APSRO algorithm an approximation of ADO tailored for extensive games.  Then they propose the SP-PSRO algorithm that enhances APSRO by adding at each iteration a well-chosen mixed strategy.", "questions": "#General comments:\n\n- The SP-PSRO  involves many different components: Q-learning for BR, regret minimization for solving the restricted games, potential reservoir sampling and additional supervised learning to train the mixed policy which results in a rather involved algorithm. Maybe it could be interesting to identify the key components of the SP-PSRO \n\n- It could be useful to describe in details what is the restricted games and how the Nash equilibrium of these games is approximated by regret minimization. And maybe you could also provide more details for the proof of Theorem 3.\n\n- What is the average size of the population in the different experiments? Because one possible drawback of the presented methods is that we have to store all the polices of the populations (and possibly for the average in SP-PSRO). Could you comment on this point?\n\n#Specific comments:\n\n- P3, beginning of Section 3: It is a bit hard to follow this part without knowing in advance what is DO and PSRO.\n\n- P3, (1): It is not completely clear with the current notations if the policy \\pi_i \\in \\Pi_i could be a mixture of the policies in the population or should be exactly one of them. The introduction suggested that the first statement is the correct one? It could be also interesting to remark that a mixture of policy is also a policy somewhere.\n\n- P5 beginning of Section 4: Can you describe precisely how you do regret minimization among the the population of policies in the restricted game? In particular how do you deal with an increasing number of policies?\n\n- P7 bottom: Can you define precisely the time average \\bar{\\nu}_i. Th whole procedure looks quite involved. i do not really see the motivation behind the averaged best response.\n\n- P8, Section 6.1: It would be interesting to compare also with ADO to see what the new Double oracle brings over PSRO and how well APSRO approximate ADO. Which hyper-parameters did you use and which regret minimizer did you use in APSRO and SP-PSRO? (pointers to the appendix). Why not use the same horizon for all the games? How many seeds did you use in the experiments?\n\n- P8, Section 6.2: Same remark it would be clearer to add reference to the appendix about the details of the experiments. How do you explain intuitively the gap between SP-PSRO and the other algorithms? It seems that that  SP-PSRO converges quickly but then get stuck to a sub-optimal solution, e.g. in Leduc Poker it converges to an exploitability of ~0.4 which is not that good for this game. It is not very clear in Fig 5 that the exploitability of APSRO decrease more monotonically than the one of PSRO contrary to what is claim in the previous sections (in particular for tiny battleship. Could you comment on this point? \n\n- P8, Section 6.2: Same question as above. And would it be possible to use larger horizon in Fig 6 and 5 to see if the exploitabilities of SP-PSRO and APSRO cross or not. How do you compute the average strategy in the experiments?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "-The new ADO algorithm improves over the DO algorithm by guarantying a monotonically non-increasing exploit ability.\n\n-The two new practical algorithms APSRO and SP-PSRO seem to improve empirically over their direct competitor the PSRO algorithm.", "weaknesses": "-While the text is globally easy to read I think that more pointers to the appendix, in particular for the experiments, could improve the clarity of the presented work. Some additional explanations about the computation of $\\pi^r$ in the different algorithm is missing at least in the main text.\n\n-The improvement in terms of monotonically of the exploitability curve that motivates the introduction of the different new algorithms is not completely clear in the experiments, especially for the APSRO algorithm vs PSRO algorithm.", "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": "", "extra_scores": {}}, {"review_id": "eTgxBTydzv", "reviewer": "Reviewer_C3x7", "summary": "I have read the author's rebuttal, and I have decided to keep my score unchanged. The main reason is the resource consumption issue of PSRO-like methods in large-scale problems. The author mentioned Barrage Stratego, which is still too small for me (as a RL researcher). I acknowledge that large-scale problems, multi-player games, and multi-agent issues often do not guarantee convergence to Nash equilibrium, but the vast majority of problems we actually face are of this kind. Therefore, I encourage the author to try PSRO-like methods in these problems to expand the impact of the article.\n\n========================================================================================================\n\nThis paper addresses the issue of increased exploitability in deep reinforcement learning methods, such as Policy Space Response Oracles (PSRO), in competitive two-agent environments. The authors propose anytime double oracle (ADO), an algorithm that ensures exploitability does not increase between iterations, and its approximate extensive-form version, anytime PSRO (APSRO). Furthermore, the paper introduces Self-Play PSRO (SP-PSRO), which incorporates an approximately optimal stochastic policy into the population in each iteration. Experiments demonstrate that APSRO and SP-PSRO have lower exploitability and near-monotonic exploitability reduction in games like Leduc poker and Liar's Dice, with SP-PSRO converging much faster than APSRO and PSRO.", "questions": "Similiar to the weaknesses:\n\nCan the authors provide more insights into the scalability of the proposed algorithms, particularly in the context of larger games or more complex environments, such as limit Texas Hold'em or Atari games?\n\nHow do the proposed algorithms compare to other state-of-the-art methods, including non-PSRO methods such as population-based training and league training (e.g., AlphaStar), in terms of exploitability reduction and convergence speed?\n\nAre there any plans to extend the proposed algorithms to multi-agent or cooperative settings? If so, what challenges do the authors foresee in adapting the algorithms to these settings, where exploitability is harder to compute but more general problems are commonly encountered?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality: The paper presents novel algorithms (ADO, APSRO, and SP-PSRO) that address the exploitability issue in competitive two-agent environments, which is a significant contribution to the field of deep reinforcement learning.\nQuality: The proposed algorithms are well-motivated, theoretically grounded, and empirically validated through experiments on various games.\nClarity: The paper is well-written, with clear explanations of the algorithms and their motivations, making it easy to understand the authors' contributions.\nSignificance: The proposed algorithms have the potential to significantly improve the performance of deep reinforcement learning methods in large games, making them more applicable to real-world problems.", "weaknesses": "Scalability: While the proposed algorithms show promising results in the tested games, it is unclear how they would scale to even larger games or more complex environments, such as limit Texas Hold'em or Atari games. The paper could provide more insights into the scalability and potential limitations of the proposed algorithms in these settings.\n\nComparison: The paper could benefit from a more comprehensive comparison with other state-of-the-art methods, including non-PSRO methods such as population-based training and league training (e.g., AlphaStar). This would provide a clearer understanding of the relative performance of the proposed algorithms and their advantages over existing approaches.\n\nGeneralization: The paper focuses on competitive two-agent environments, but it would be interesting to see how the algorithms could be adapted or extended to handle multi-agent or cooperative settings, where exploitability is harder to compute but more general problems are commonly encountered.", "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": "", "extra_scores": {}}, {"review_id": "nlwhHqGUX2", "reviewer": "Reviewer_EJCG", "summary": "This paper considers the redesign of Policy-Space Response Oracles (PSRO) as an _anytime algorithm_---designed so that it can stop at any time and return the best result found so far, for two-player zero-sum games. The authors begin by extending the Double Oracle (DO), the precursor of PSRO, to the anytime setting. They accomplish this through their proposed algorithm Anytime Double Oracle (ADO) that considers differing restricted games per-player that leave the opponent always unrestricted. They show theoretically that ADO inherits the limit convergence properties of DO. This is followed by their introduction of Anytime PSRO (APSRO), an algorithm that \"never increases exploitability by much\" when compared to PSRO. APSRO works by continually computing the estimated solution using a regret minimization algorithm. Finally, they introduce Self-Player PSRO (SP-PSRO) that modifies APSRO to add the BR(BR) at each iteration instead of just a BR. SP-PSRO and APSRO are evaluated against PSRO on a suite of small two-player zero-sum games.", "questions": "- \"In addition to introducing APSRO, we also build on APSRO by adding to the population in each iteration an approximation of the myopically optimal policy, that is, the stochastic policy that maximally lowers the exploitability of the least-exploitable distribution of the resulting population.\"\n  - If I understand this claim correctly, this is not a new insight, and the work discussed in A.2 presented this idea?\n- I would suggest the authors consider a different name than Self-Play PSRO. This makes me think of PSRO with the MSS set to Self-Play, and doesn't really hint at all as to the nature of the underlying algorithm. \n- Why bother forcing SP-PSRO to train off policy?\n  - The focus of this work is on anytime stopping not on computational efficiency.\n  - Have the authors tried using on-policy algorithms? This could result in further benefits. \n- \"Moreover, adding mixed strategies can generally reduce exploitability faster than adding pure strategies.\"\n\t- Is another way to make this argument that adding mixed strategies enables us to add multiple pure-strategies per iteration; therefore, we can generally solve the game quicker---by the measure of number of iterations?\n\t- This seems to suggest a degenerate solution of just immediately solving the full game, which of course we can't generally do.\n- \"Why the episode is terminated, the time average of v is added to the population.\" Why is episode used here? Do you only train your policy for a singular episode?\n- Limitations should discuss that while SP-PSRO uses same budget as APSRO, they're both way more expensive than PSRO.\n- Limitations need to also discuss that this analysis is on NE, PSRO is more general\n\n\nExp 6.1\n- You've had to add lambda to apply your algorithms to these games. What is the impact of lambda on the performances you've demonstrated?\n- \"As shown in Figure 4, unlike PSRO, APSRO tends not to increase exploitability\" I don't think eyeballing Fig 4 or 5 really provides enough evidence to support this claim. \n\t- PSRO only looks guilty of a large exploitability increase in Leduc Poker, and all other both algorithms are erratic.\n- \"Note that APSRO and SP-PSRO only reach an ϵ-NE because they use a finite number of regret minimization updates to determine the restricted distribution, while PSRO is able to exactly compute a NE.\"\n\t- I would have preferred the authors to have included an analysis of this.\n\t- A/SP-PSRO with exact equilibrium computation. \n\t- PSRO with regret minimization for computing equilibrium.\n\t- Would help better understand where the benefits are coming from.\n\nExp 6.2\n- \"We hypothesize that this is due to the APSRO iterations not being long enough for the no-regret process to converge.\"\n\t- Thank you for including this point.\n\t- I was wondering if you had any insights into how we could know when we should apply APSRO based on this?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The anytime property in game-solving algorithms is important as more heuristics for strategy exploration are being considered. This is particularly true because adding best responses at each iteration is a heuristic method, resulting in the increasing exploitability sometimes observed in PSRO. \n- Visualizations of didactic examples of the algorithm are very welcome and clear.\n- Evaluated on a diversity of games --- albeit, all small games presumably to compute exact exploitability.", "weaknesses": "- The premise of the paper, PSRO/DO can result in increases in exploitability between iterations, is not sufficiently justified or explained. Wouldn't a more straightforward approach to just be take the best-found-so-far solution across PSRO iterations? With this slight modification on the return statement, you obtain the desired anytime property.\n- Another premise of the paper is that \"PSRO and APSRO add pure-strategy (i.e. deterministic) best responses in each iteration.\" PSRO _does not_ have this requirement, and in fact, begins by adding a uniformly stochastic policy to the strategy set. As it is relatively common for implementations of PSRO to include only deterministic policies, I am fine with this being used as a premise, but I think this needs to be directly discussed in the text. This fact also has side-effect of suggesting an alternative simpler approach to APSRO/SP-PSRO in differing methods of computing stochastic policies.\n- ADO is marginally novel compared to Range of Skill (RoS) and DO, and I think its limitations are not discussed well enough. To me, the main intuition behind DO/PSRO is when you cannot consider analytical solutions to game reasoning, and instead need to consider a restricted/empirical version of the game. ADO considers a partially restricted version of the game (only expanding a single players policy-space), and as a result is intractable and bears common complaints to direct game reasoning. The authors should discuss this and the complexity trade-offs more directly. \n- The authors should address the focus on NE, when PSRO is flexible to any chosen solution concept. They should also state for all of their algorithms if they are constraining this aspect of PSRO. \n- Very limited analysis of the design of APSRO/SP-PSRO. Consider including ablation-style experiments.\n- Restricted games and empirical games are used interchangeably when they are not interchangeable objects. \n\n\n- This is more minor, but I think is very important: the language and notation are more posed to a game theory audience than to the ML audience of ICLR. Following the notation and definitions in say the PSRO paper for example would make this paper significantly more approachable by this community. I personally find trouble whenever the RL definitions/notations are conflated with the notations used within the game-theoretic reasoning. For example, when you see \\pi, is it a single policy, or a distribution over policies (i.e., solution)?", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)