Online Double Oracle
Authors: Le Cong Dinh
Stephen Marcus McAleer
Zheng Tian
Nicolas Perez-Nieves
Oliver Slumbers
David Henry Mguni
Jun Wang
Haitham Bou Ammar
Yaodong Yang
Venue: Accepted by TMLR ()

Abstract: Solving strategic games with huge action spaces is a critical yet under-explored topic in economics, operations research and artificial intelligence.  This paper proposes new learning algorithms for solving two-player zero-sum normal-form games where the number of pure strategies is prohibitively large.  Specifically, we combine no-regret analysis from online learning with Double Oracle (DO) from game theory. 
Our method---\emph{Online Double Oracle (ODO)}---is provably convergent to a Nash equilibrium (NE).  Most importantly, unlike normal DO, ODO is \emph{rational} in the sense that each agent in ODO can exploit a strategic adversary with a regret bound of $\mathcal{O}(\sqrt{ k \log(k)/T})$,  where $k$ is not the total number of pure strategies, but rather the size of \emph{effective strategy set}. In many applications, we empirically show that $k$ is linearly dependent on the support size of the NE. On tens of different real-world matrix games, ODO outperforms   DO,   PSRO, and no-regret algorithms such as Multiplicative Weights Update by a significant margin, both in terms of convergence rate to a NE, and average payoff against strategic adversaries. 

Published in Transactions on Machine Learning Research (10/2022)
Online Double Oracle
Le Cong Dinh University of Southampton
Lc.dinh@solon.cc. uk
Stephen McAleer
smealeer@uci edu
University of California, Irvine
Zheng Tian ShanghaiTech University
tianzheng@shangghattcch edu.ccr
Nicolas Perez-Nieve Imperial College London
micolas.peree11 uk
Oliver Slumbers University College London
1 10w.cl.....ccccc....o.o
David Henry Mguni Huawei RED UK
duvidmgunishotmmii..cm
Jun Wang Huawei R&D UK
w. w.jBHeuawess.omm
Haitham Bou Ammar
haitham, www.eaaaaaaaaaei..ooom
Huawei RED UK
Yaodong Yang Institute for AI, Peking Universily
wuodong.yanng@pkuu.
Reviewed on OpenReview: https: // openreview. net/ forum? id= TTMKKNNNN
Abstract
Solving strategic games with huge action spaces critical yet under-explored topic in economics, operations research and artificial intelligence. This paper proposes learning algorithms for solving two-player zero-sum normal-form games where the number of pure strategies is prohibitively large. Specifically, we combine no-regret analysis from online learning with Double Oracle (DO) from game theory. Our (ODO) is provably convergent to a Nash equilibrium (NE). Most importantly, unlike normal DO, ODO is rational in the sense that each agent in ODO can exploit strategic adversary with regret bound of O (oggk))))) where k is not the total number of pure strategies, but rather the size of effective strategy set. In many applications, we empirically show that & is linearly dependent matrix games, ODO outperforms DO, PSRO, and no-regret algorithms such as Multiplicative Weights Update by a significant margin, both in terms of convergence rate to a NE, and average payoff against strategic adversaries 1.
Double Oracle
the support size of the NE. On tens of different real-world
1 Introduction
Understanding games with large action spaces is critical topic in a variety of fields from economics to operations research and artificial intelligence. A key challenge is in computing a Nash equilibriun (NE) (Nash
If: Corresponding author. Part of this work was done as Huawei R&D UK advised by Yaodong Yang.

---

Published in Transactions on Machine Learning Research (10/2022)
Table I: Propertics of cxisting solvers on two-player zero-sum games Auxm. *:DO in the worst case has to solve all sub-games till reaching the full game, so the time complexity one order magnitude larger than LP (van den Brand, 2020). f; Since PSRO uses approximate best-response, the total time complexity is unkuown. Note that the regret bound ODO can not be directly compared with the time complexity of DO, which are two different notions. 9 Games with prohibitively large action spaces.
Rational
No Need to Know Time Complexity (Ó)
Method
Large Games
(No-regret)
the Full Matrix A / Regret Bound (0)
Linear Programming
O(nexp(-T/n29m)
Generalised Fictitious Play
O(T-1/aatm2))
Multiplicative Weight Up-
0 O(Vlog(n)/T)
date
Double Oracle
(nexpl-TT/1>
Policy Space Response Oracle
xt
/
Online Double Oracle
0 ((V+log(b))T)
et al., 1950), where no player is better off by deviating from their current strategy. Unfortunately, finding NE is generally intractable, and computing a two-player NE is known to be PPAD-hard (Chen & Deng, 2006). This holds true also for stochastic games (Deng et al., 2021). An exception is two-player zero-sum games where an NE can be tractably solved as a linear program (LP) (Morgenstern & Von Neumann, 1953). Despite the polynomial time complexity of solving an LP (van den Brand, 2020), LP solvers are not adequate for games with prohibitively large action spaces. As result, rescarchers have shifted their focus towards finding efficient approximation solutions (McMahan el al., 2003; Brown, 1951b; Zinkevich et al., 2007), or seek other solution concepts other than NE (Yang et al., 2020; 2018).
Double Oracle (DO) algorithm (McMahan et al., 2003) and its extension Policy Space Response Oracles (PSRO) (Lanctot et al., 2017) are efficient approaches to finding an approximate NE in games where the support of a NE is relatively small. In DO (McMahan et al., 2003), players are initialised with a subset of the full strategy space, thus playing only a sub-game of the original game; then, at each iteration, a best-respouse strategy to the NE of the last aub-game, which is assumed to be given by an Oracle, is added into each agent's strategy pool. The process stops when the best-response is already in the strategy pool the performance improvement of the sub-game NE becomes trivial. When exact best-response strategy is not available, approximate solution is often adopted. For example, PSRO (Lanctol et al., 2017) applies reinforcement learning (RL) (Sutton& & Barto, 2018) and multi-agent RL (Yang & Wang, 2020) oracles to approximate a best response.
Whilst DO and PSRO both provide an efficient. way to approximate the NE in large-scale zero-sum games, they still face two open challenges. Firstly, they require both players coordinate in order to solve the NE in sub-games and update the strategy set; both players have to follow the same learning dynamics such Fictitious Play (FP) (Brown, 1951a) implement LP to solve the sub-game NE together. This contradicts many real-world scenarios where an opponent can play any (non-stationary) strategy in sub-games.
Secondly, and more importantly, DO methods are not rational (Bowling & Veloso, 2001), in the sense that they do not provide a learning scheme that can exploit an adversary (i.e., achieving no-regret). Whilst a NE strategy guarantees the best performance in the worst scenario, it can be too pessimistic as a strategy compared a rational strategy, sometimes lacking strategic diversity (Sanjaya 2021). For example, in repeated Rock- Rock-Paper-Sai Paper-Scissors (RPS) game, playing the NE of (1/3, 1/3) every iteration makes one player un-exploitable. However, if the adversary acts irrationally and sticks to one strategy, say "Rock", then the player should exploit the adversary by consistently playing "Paper" to achieve larger rewards than playing the NE. No-regret algorithms (Cesa-Bianchi & Lugosi, 2006; Shalev-Shwartz et al., 2011) prescribe a learning scheme in which a player is guaranteed to achieve minimal regret against the best fixed strategy in hindsight when facing an unknown adversary (either rational or irrational). Notably, if both players follow no-regret algorithms, then it is guaranteed that their time-average policies will converge to NE in zero-sum games (Blum& & Monsour, 2007) However, the regret bounds of popular no-regret.
al., 2021; Yang al.,
2

---

Published in Transactions on Machine Learning Research (10/2022)
algorithms (Freund & Schapire, 1999; Auer et al., 2002) usually depend on the game size; for example, Multiplicative Weights Update (MWU) (Freund & Schapire, 1999) has regret bound of Of ((yoog()/TT) and EXP3 (Auer et al., 2002) in the bandit setting has regret of O(v' log(n)/T) where is the number of pure strategies (i.e., experts). As result, directly applying no-regret algorithms, though rational, is not computationally feasible in solving large-scale games.
In this paper, we present a scalable solution to two-player zero-sum normal-form games where the game size (i.e., the number of pure strategies) is prohibitively large. Our main analytical tool is no-regret analysis from online learning (Shalev-Shwarte et al., 2011). Specifically, by conducting no-regret analysis (Freund & Schapire, 1999) within the DO framework (McMahan et al., 2003), we propose the Online Double Oracle (ODO) algorithm which inherits the key benefits from both sides. It is the first. DO method that enjoys the no-regret property and can exploit unknown adversaries during game play, Importantly, ODO achieves a regret of O( k (og( where k, the size of effective strategy set, is upper-bounded by the total number of pure strategies n and often k < n holds in practice. We test our algorithm on tens of games including random matrix games, real-world matrix games (Czarnecki et al., 2020), and Kuhn and Leduc Poker. Results show that in almost all games, ODO outperforms both DO and PSRO variants (Lanctot et al., 2017; McAleer et al., 2020), and the online learning baseline: MWU (Freund & Schapire, 1999) in terms of exploitability (i.e., distance to an NE) and average payofis against different types of strategic adversaries.
2 Related Work
ODO contributes to both the game theory and online learning domains. To summarise our contribution, we present a list of existing game solvers for comparison in Table 1.
Approximating a NE has been extensively studied in the game theory literature. Fictitious Play (FP) (Brown, 1951b) and generalised FP (Leslie & Collins, 2006) are classical solutions where each player adopts a strategy that best responds to the time-average strategy of the opponent. Although FP is provably convergent to NE in zero-sum games, it is prohibited from solving large games due to the need to iterate through all pure strategies at each iteration; furthermore, the convergence rate depends exponentially on the game size (Brandt et al., 2010). In lerms of large-scale zero-sum games, DO (McMahan et al., 2003; McAleer el al., 2021) and PSRO methods (Lanctot et al., 2017; McAleer et al., 2020; Feng et al., 2021; Perez-Nieves et al., 2021; Liu et al., 2021) have shown remarkable empirical success. For example, a distributed implementation of PSRO can handle games of size 50 (McAleer et al., 2020). Yet, both FP and DO methods offer no knowledge about how to exploit an adversary in a game (i.e., no-regret property) (Hart & Colel, 2001), and thus are regarded as not rational (Bowling & Veloso, 2001). Modern solutions that are rational such as CFR methods (Zinkevich et al., 2007; Lanctot et al., 2009) are efficiently designed for extensive-form games only.
A Algorithms with the no-(external) regret property can achieve guaranteed performance against the best-fixed strategy in hindsight (Shalev-Shwartz et al., 2011; Cesa-Bianchi & Lugosi, 2006), thus they are commonly applied to tackle adversarial environments. However, conventional no-regret algorithms such as Follow the Regularised Leader (Shalev-Shwartz et al., 2011), Multiplicative Weights Update (MWU) (Freund & Schapire, 1999) or EXP-3 (Auer et al., 2002) have regret bounds that are based on the number of pure strategies (i.e., experts). Moreover, these algorithms consider the full strategy set during updates, which hinders their applicability to large-scale games. In this paper, we leverage the advantages of both DO and no-regret learning to propose ODO, ODO enjoys the benefits of both being applicable to solving large games, and being able to maintain the no-regret property (i.e., being rational).
3 Notations & Preliminaries
A two-player zero-sum normal-form game is often described by a payoff matrix A of size n X m. The rows and columns of A are the pure strategies of the row and the column players, respectively, and we consider n and m to be prohibitively large numbers. We denote the set of pure strategies for the row player as II == (al a² ...,.,),, and C = {el, ce ,..... cm for the column player.
3

---

Published in Transactions on Machine Learning Research (10/2022)
The set of mixed strategies for the row-player is An { -i= 2,a', =1 2 2, E [n]] and for the column player it is Ac == {clc = >i= Va E== 1i = 1, 2 0, E [m]). The support of a mixed strategy is written as supp(T) ;= {a' E 11|2; + 0}, with its size being |supp(>)).
We consider Ar E [0, 1] to represent the (normalised) loss of the row player when playing a pure strategy a' against the pure strategy el of the column player. At the 1-th round, the expected payoff for the joint-strategy profile (T, E Ån, Ct Ac) is (- Act, मं Act). In this paper, we consider the online setting in which players do not know the matrix A, or the adversary's policy, but instead only receive a loss value after their strategy is played: e.g., timestep t ++ 1, the row player observes 4, Ac, from the environment and plays new strategy T++1- The goal of the players is to reach Nash equilibrium.
Nash Equilibrium. A NE of a two-player zero-sum game can be defined by the minimax theorem (Neumamn, 1928):
min max π Ac max min π Ac = cEAo TEAn
(1)
REAn cEAp
for some R. The (T', c²) that satisfies Equation (1) is NE of the game. In general, one apply LP solvers to find the NE in small games (Morgenstern & Von Neumann, 1953). However, when and m are large, the time complexity is not affordable. A more general solution concept is the e-Nash equilibrium.
e-Nash Equilibrium. For E > 0, we call a joint strategy (TT, c) E An X Ac an e-NE if it satisfies
max π T Ac - c c π Ac S min π T Ac. AE
(2)
TEAn
3.1 Double Oracle Method
The pseudocode for DO (McMahan el. al., 2003) is listed in Appendix A.1. The DO method approximales NE in large-scale zero-sum games by iteratively expanding and solving series of sub- sub-games (i.e., games with restricted set of pure strategies). Since the sets of pure strategies of the sub-game are often much smaller than the original game, the NE of the sub-games can be easily solved via approaches such as FP. Based on the NE the sub-game, each player finds a best-response to said NE, and expands their strategy set with this best-response. PSRO methods (Lanctot et al., 2017; McAleer et al., 2020) are a generalisation of DO in which RL methods (c.g., Actor Critic) are adopted to approximate the best-response strategy. In the worst case scenario (e.g-, the support size of NE is large), DO may end up restoring the original game and will maintain no advantages over LP solutions.
Although DO can solve large-scale zero-sum games, it requires both players to coordinate by finding NE in the sub-games; this is a problem for DO when applied in real-world scenarios, as it cannot exploit the opponent who can play any non-stationary strategy (see the example of RPS in the Introduction). ODO addresses this problem by combining DO with tools in online learning.
3.2 Online Learning
Solving for a NE in large-scale games is demanding, so an alternative approach is to consider learning-based methods. We believe that by playing the same game repeatedly, a learning algorithm can approximate the NE asymptotically. A common metric, (erternal)-regret, quantify the performance of learning algorithm is compare its cumulated payoff with the best fixed strategy in hindsight.
Definition (No-Regret Algorithuns). Let C2,... be a sequence of mixed stralegies played by the column player, an algorithm of the row player that generates a sequence of mixed strategies πT, ...... is called no-regret algorithm if we have the following property hold.
RT T
lim T0000
O, RT max #EAn
Σ
[ ATA T AAA)).
If both players in game follow no-regret algorithm (not necessarily the same one), then the average strategies of both players converges to NE (Cesa-Bianchi & Lugosi, 2006; Blum & Monsour, 2007). For
4

---

Published in Transactions on Machine Learning Research (10/2022)
example, a well-known learning algorithm for games that has this no-regret property is the MWU algorithm (Freund & Schapire, 1999):
Definition 2 (Multipliaaiive Weights Update). Let 01, C2, be sequence of mixed strategies played by the column player. The row player is said to follow MU if Te+1 is updated as follows
Te (x)()xp((pu u:aa Aci)
(i)
Vi [n]
(3)
-i=1 (1)
Ac))
where 14 > 0 is parameter, To = [1/n,.... 1/nl and n is the number of pure strategies (a.k.a. experts).
When T is known in advance, by fixing the learning rate Me v /loggn)/TT, can achieve the optimal regret bound for MWU (Theorem 2.2 in (Cesa- (Cesa-Biande) Bianchi & Lugosi, 2006)):
log(n))
(4)
When T' unknown, we can apply the Doubling Trick to achieve the regret bound of:
(V2/(V22 Tlgg(//))))
which is worse than the optimal one by a factor of v2/(v2 - 1). Rooij et al. (De Rooij et al., 2014) proposed AdaHedge, a variant of MWU with adaptive learning rate μlr = log(n)/ A, where A, denotes the cumulative mixability gap 2. Then following Theorem in (De Rooij al., 2014), the regret for AdaHedge will be bounded by:
log(()) log(n) 2
which is the worse than the optimal one by factor of /2.
In our paper, w.l.o.g we use the optimal regret bound of MWU when T is known to derive our theoretical results. In the case T is unknown, following exactly the same argument with the Doubling Trick or AdHedge algorithm, we can derive similar regret bound up to constant factor for our algorithms.
Note that since MWU requires updating the whole pure strategy set (of size n) at each iteration, it is not applicable solving large-scale games.
4 Online Single Oracle
In this section, we introduce Online Single Oracle (OSO), a no-regret algorithm followed by individual players that can strategically exploit any non-stationary opponent unlike DO. Compared to the MWU algorithm, OSO can be applied solving large zero-sum games as il only considers a smaller subset of the full pure strategy space. The following section is organised as follows: we start by setting out OSO, the key component of ODO. We then discuss the bound the effective strategy set k the key clement in the regret bound of OSO. Finally, we set out two different questions on the effectiveness and efficiency of the best-response oracle, and analyse OSO's performance when the player only has access to less-frequent or approzimate best-responses oracles.
4.1 Online Single Oracle Algorithm
One can think of OSO can achieve the no-regret property. In contrast to classical no-regret algorithms such MWU (Freund & Schapire, 1999) where the whole set of pure strategies needs considering at each iteration, i.e., Equation (3), we propose OSO that only considers a subset of the whole strategy set. The key operation is that, at each round t, OSO only considers adding a new strategy if it is the best-response to the average loss in a time window (defined formally in the following paragraph). As such, OSO can save on exploration costs by ignoring the pure strategies that have never been the best-response any, so far observed, average losses,
online counterpart to the Single Oracle in DO (McMahan et al., 2003) which
28ee Appendix A.2 and A.3 for more details about Doubling Trick and AdaHedge algorithm.
5

---

Published in Transactions on Machine Learning Research (10/2022)
Algorithm 1: Online Single Oracle Algorithm
Input: Player's pure strategy II Init. effective strategies set: 11g 111 {al}, al
for t = to T do
if -1,=-1- 11,-1 then
5:
Compute n. by the MWU in Equation (3)
6: clse if II, + 1 then
7:
Start a new time window T,+1 and
Reset क. = [T/ 1/[TT]], 0
end if
Observe 4 and update the average loss in TN: 1= Even, 4/[l
10:
Calculate the best-response: a; = arg min
11:
Update the set of strategies: 1I++1 = II, U {a.}
12:
end for
13:
Output: TT, TT
Our OSO is listed in Algorithm We initialise the OSO algorithu with random strategy subset Ho from the original strategy set ТI. Without loss of generality, we assume that Th starts from only one pure strategy (line 2). We call subset 11, the effective strategy set at the timestep t, and define the period of consecutive iterations as one time window T; in which the effective strategy set stays fixed, i.c., T; := {t [Iyl] = =}. At iteration I, we update गe (line 5) whilst only considering the effective strategy set πT, (rather than whole set II); and the best-response is computed against the average loss within the current time window T; (line 9). Adding a new best-response that is not in the existing effective strategy set will start a new time window (line 7). Notably, despite the design of effective strategy sets, the exact best-response oracle in line 10 still needs search over the whole strategy set II, which is property that relax through best-response approximation later.
We now present the regret bound of OSO as follows,
Thcorem 3 (Regret Bound of OSO). Let 1 l2...., , br be a sequence of loss vectors played by an adversary, and ( be the dol product, OSO in Algoritim is a no-regred algorilhm with
T
T
log(k)
To 4)
min
(TT, S
2T
where [lT| the size of the effective strategy set in the final time window.
Proof. W.l.o.g, we assume the player uses the MWU as the no-regret algorithm and starts with only one pure strategy HI in Algorithm 1. Since in the final time window, the effective strategy set has k elements, there exactly time windows. Denote [T 12 [Tg] be the lengths of time windows during each of which the subset of strategics the no-regret algorithm considers does not change. In the case of finite set of strategies, & will be finite and we have
k
T = T
In the time window with length [T,], following the regret bound of MWU in Definition we have:
Teaa
Thaal Σ
Tr 2
Σ (me. 4e)
min
(T,, 4. S
log(i).
where [T]| = Σ T₁
(5)
mell 12 t= +1/++1
t= +11+1
f=1

---

Published in Transactions on Machine Learning Research (10/2022)
In the time window T, consider the full strategy set when calculate the best response strategy in step 11 of Algorithm 1 and it stays in pp..1+1- Therefore, the inequality (5) can be expressed as:
panl Σ
IT 1
7 2
(Te, be)
min Σ [=17++11
b1) S
log
(6)
[-/+++1
Sum up the inequality (6) for i 1,... ts we have:
T
log(t)
TT, 42)
min
Σ (T,
1=/2i|+1
Ti41l
T
n
min #ell
(
Σ
(Te (2)
min Σ (T,44) 4).
(7a)
t=
+|,+++1
Inequality (7a) is due to Σ min < min >
Using the Cauchy-Sehwarz inequality we have:
I: T 2
k
Tk log(k)
log (1) S
log(1)) =
log(i) 1
2
2
2
Along with Inequality (7a) we can derive the regret:
Tk log(())
The 4e)
min * *Ell
TT, lt)
2
We note here that in line 7 of Algorithm 1, each time OSO enters a new time window, it sets equal weight for every pure strategy in the current effective strategy. Since we assume a fully adversarial environment, the historical data that the agent learnt in the previous time window does not provide any advantages over the current time window, thus in order to avoid any exploitation, the agent needs to reset the strategy as stated in Algorithm 1. In situations where priority knowledge can be observed through historical data, our OSO algorithm can exploit this knowledge by updating the starting strategy in each time window. We leave this important extension to our future work.
Remark 1 (Worst-Case Regret Bound). Similar to all existing DO type of met in the worst-case scenario, OSO has to find all pure strategies, i.e., k = [II]. Thus, the regret in the worst case scenario will be: VIII Il) /2T. However, we believe < [I]] holds in many practical cases such as against strategic adversary (Dinh al., 2021a;b; Dinh, 2022). In later sections, we provide both theoretical and empirical evidence that wal-world games tend have l < IT].
In the next section, we discuss the relationship between the effective strategy set size k and the full game size.
4.2 Size of Effective Strategy Set
Heuristically, the practical success of ODO and other discussed methods (c.g., DO (MeMahan al., 2003) / PSRO (Lanctot et al., 2017)) is based on the assumption that the support size of the NE is small. Intuitively, since OSO is no-regret algorithm, should the adversary itself follow no-regret algorithm, the adversary's average strategy would converge to the NE. Thus, the Iearner's best-responses with respect to the average loss will include all the pure strategies in the support of the learner's NE. Therefore, under the assumption of DO and PSRO that the support size of NE is small, the effective strategy set size k is potentially a far smaller number than the game size (i.e., n).
Note that the assumption of a NE having small support size holds true in many situations. In symmetric games with random entries (i.e., see Theorem 2.8 in Jonasson al. (2004)), has been proved that the
7

---

Published in Transactions on Machine Learning Research (10/2022)
expected support size of a NE will be (2 + (1))) where is the game size; showing that the support size of NE strategy is only half of the game size. In asymmetric games with disproportionate action spaces (e.g., n > m), we provide the following Jemma under which the support of a NE is small.
Lemma 1. In asymmetric games Auxm E m, if the NE , is unique, then the support size of the NE will follow supp(>>)] |supp(c") S m.
(We provide the full proof in the Appendix C.1.)
In situation where an asymmotric game Anxm, n > m does not has unique NE but it is nondegenerate 3 then following Proposition 3.3 in (Roughgarden, 2010), we can similarly bound the support of NE by m.
Empirically, we also show that the small support of a NE assumption holds on tens of real-world zero-sum games (Czarnecki ct al., 2020) (sce Table 2 in Appendix D) and randomly generated games (sce Figure 1).
In the case when dominant strategy exists, we can theoretically bound k by the following lemma: Lemma 2. Suppose there erists strictly dominant strategy for the player 4, then the size of the effective strategy set will be bounded by 2.
As highlighted in Appendix C.4, OSO is theoretically more computationally efficient than MWU in convergence to NE when & S Vn. Thus Lemma 1 with m S vn and Lemma 2 provide subclasses of game in which OSO can theoretically outperform MWU.
Despite the practical success of our method and the DO/PSRO lines of work, there is no theoretical guarantee about the relationship between the support size of a NE and the performance of the algorithm. In this paper, provide negative result by constructing example such that the size of the effective strategy set equals the size of the full strategy set, even when the support of NE is small.
AI,1 and the game matrix A of the two-players zero-sun Lemma 3. Suppose the players start with the entry
game is designed such as
0.1i
A, 0.5 +
vi Vi
A..+1 = 0.9 [n 1]: [m];
n
0 2n
A. - 0.8 2 2 [n], Aij Ai,i
i [n].
where is the size of the pure strategy set for both players. Then the game has unique Nash equilibrium with support size of (i.e., the enlry Ann) and the effective strategy set in both DO and OSO will reuch the size of pure strategy set, that is, k == =n..
We provide the full proof in Appendix C.3. The idea is that the the matrix A is designed such that the sub-game NE will change from A to Ai,4 for E [n], thus OSO will need to consider the full pure strategy set before reaching the game NE at An,x- Following the same argument, when the players start with the entry A.,; the effective strategy set will be n n-i+1 and thus when the players choose the starting entry as uniformly random, the expected size of effective stratetgy set will be: E(k) (n + 1)/2. We would like to highlight that this negative result not only applies to our method, but also to all existing DO/PSRO algorithms and their variations.
However, as described in our experiments, we find that the extreme situation shown in Lemma 3 rarely occurs in practice. Later in Figure 1, we provide empirical evidence to support our claim that k < [ and that there exists a linear relationship between and the Nash support size in many rorl-world applications.
4.3
OSO with Less- Fisss-Freuent Best- Rest-Response
The first adaptation to the best-response process that we consider is to make calls to the best-response oracle less frequently. Obtaining a best-response stratogy can be computationally expensive (Vinyals et al., 2019), and OSO considers adding a new best-response strategy al every ileration. A practical solution is consider
No mixed strategy of support size à has more than pure best responses
4 we rigorously define Appendix C.2.
8

---

Published in Transactions on Machine Learning Research (10/2022)
adding new strategy when the regret in the current time window exceeds predefined threshold a. To make OSO account for this, we denote |7:] := Σi= [Tal as the starting point of the time window Ti, and write the threshold at 7; as ii1 where t [T denotes the relative position of round & in the time window T; We can make OSO add a new strategy only when the following condition is satisfied:
min TET
min
4 2 a 1-T.1"
(8)
TEl
1=17A
j=17:
Note that the larger the threshold a, the longer OSO takes to add a new strategy into 14, However, choosing large a will prevent the learner from acquiring the actual best-response, thus increasing the total regret Ry by a. In order maintain the no-regret property, the a needs satisfy
E O7 = 0.
lim T-400
(9)
T
7.1 = V -t [Til- We list the pscudo-code of OSO utilising
One choice of a that satisfies Equation (9) is af Equation (8) and derive its regret bound of O (lo)(k))/T) in Appendix B.1.
4.4 Considering e-Best Responses
The second adaptation brings OSO more closely in line with the work of PSRO by considering non-exact best-response oracle. So far, OSO agents compute the exact best-response to the average loss function l (i.e., line 10 in Algorithm 1). Since calculating the exact best-response is often infeasible in large games, an alternative way is to consider an e-best response (e.g., through RL subroutine similar to PSRO (Lanctot et al., 2017)) to the average loss.
By first analysing the convergence of DO, we can derive the regret bound as well as convergence guarantoes for an OSO learner in the case of an e-best response oracle.
Theorem 4. Suppose an OSO agent can only access the e-best response each iteration when following Algorithm 1, is the adversary follows no-regret algorithm, then the average stralegy of the agent will converge. to e-NE, Furthermore, the algorithm is e-regret:
PT Se T
lim T-0
RT max TEan
n Ac: - π AAA.)..
(We provide the full proof in Appendix B.2.)
Theorem 4 justifies that in the case of approximate best-responses, OSO learners can still approximately converge to a NE. This results allows for the application of optimisation mothods to approximate the best-response, which paves the way to use RL algorithm in solving complicated zero-sum games such as StarCraft (Vinyals al., 2019; Peng al., 2017). Now that we have introduced the algorithms the individual player will follow, we can now discuss the outcomes when both competing players follow such algorithms.
5 Online Double Oracle
Recall that if both players follow a no-regret algorithm, then the average strategies of both players converge to the NE in two-player zero-sum games (Cesa-Bianchi & Lugosi, 2006; Blum & Monsour, 2007). Since OSO has the no-regret property, it is then natural to study the self-play setting where both players utilise OSO, which, we call Online Double Oracle (ODO), and to investigate its convergence rate to a NE in large games.
There are two major benefits of using ODO in comparison to DO: Firstly, ODO does not need to compute a NE in each sub-game which can become computationally expensive for large sub-games. Secondly, ODO produces rational agents which can exploit an adversary to achieve the no-regret property. The convergence rate of ODO to NE follows:
9

---

Published in Transactions on Machine Learning Research (10/2022)
Algorithm 2: Online Double Oracle Algorithm
Input: Full pure strategy set II, C
Init. effective strategies set: 1I 11, Co C1 for t= 1 to T do
Each player follows the OSO in Algorithm 1 with their respective elfective strategy sets II, C2
5: end for
6: Output: TT, ITy, Cr. Cr
Theorem 5. Suppose both players opply OSO. Let kı, l2 denote the size of the effective strategy set for each player. Them, the overage stralegies of both players converge to the NE with the rale;
l log(
K2 log(k2) V
ET
27
2T
the siluation where both players follow OSO with a Less- Mass-Prequent Best- Resl-Rss as in Equalion (8) and of a1-111 vt -- [Ti], | the converyence rate to NE will be
11 (kg
k2 (k2)
vki + Vb2
CT
2T
2T
vT
Sketch Proof. Using the regret bound of OSO derive that
T
log((1)
ho log(
h log(k1)
Ae min π
well
Ae
T
ai
Ac -
27
max T Ac
CEC
27
27
1=1
Similarly, we have
Ae max ग Ac S
1
Σ
n, Ac,
hs log(ks)
min π Ač mell
h1 log(As)
ky (k2)
CEC
T
2T
2T
Thus, with ET
V
(og(k))
log(ka) 21
we have
21
Σ ; Ac ET Ae T min π Ač ET.
max CEC
1=1
By definition, (f, is er-Nash equilibrium. Similarly, we can derive the convergence rate for OSO with Less-Frequent Best-Responis, The full proof can be found in Appendix C.5.
Theorem 5 suggests that, similar to OSO, the convergence rate ODO will not depend on the game size, but rather the size of the effective stralegy set of both players. As we studied in the OSO section, although can not theoretically prove the linear relationship between the size of the effective strategy set and the size of the NE support, in many practical applications, such linear relationship holds true (shown in Figure 1). Thus, in the same way as DO, ODO will prove effective in solving large games where the size of the NE support is indeed much smaller than the full game size (e.g., also see Table 2 in Appendix D).
We note that the convergence of ODO and other baselines in our paper (i.e., MWU, CFR, XFP) are on average sense and recently many researchers have designed new algorithms that achieves last iterated convergence to NE, which is a stronger concept than average convergence (e.g., LRCA in (Dinh al., 2021b), OMWU (Daskalakis & Panageas, 2019)). However, these new algorithms inherit the computational complexity of conventional no-regret algorithms such as MWU and thus unable to apply in large-scale games.
10

---

Published in Transactions on Machine Learning Research (10/2022)
5.1 ODO vs. Double Oracle with MWU
It is important to highlight that ODO is markedly different from simply implementing DO with MWU to solve for the sub-game NE (i.e., rumning MWU till convergence in the sub-game). Firstly, ODO checks for a best-response that is outside of the current effective strategy set per MWU update, whereas DO adds a best-respouse every time a sub-game NE is solved, which often requires thousands of MWU iterations. Most importantly, the best-response target in ODO (i.c., the time-average loss 1) is not necessarily a NE; this is in contrast to DO where the best-response computed with respect to exact NE. Intuitively, the convergence of DO only requires the best-response target in the last sub-game to be NE, thus calculating the NEs in every sub-game to update the strategy set is not necessary. ODO tackles this problem by using the time-average loss as the new best-response target. As a result, ODO performs much better compared to DO in Figure 3. Finally, even if DO implements MWU to solve the sul-game NE, it is still not a no-regret. algorithm. This also explains the performance gap between OSO and DO with MWU in Figure 4.
6 Experiments & Results
In this section, we aim to demonstrate the ef-
Size of effective strategy set (k)
60
feetivencss of our practical use algorithms, OSO
and ODO, However, we begin by looking the
50
major assumption of this work, and verify the lin-
40
ear dependence between the size of the effective strategy set and the NE support size in random matrix games. Next, over multiple real-world matrix games (Czarnecki et al., 2020), we evalu- ate OSO in both the self-play setting (i.e., ODO) and when playing against strategic adversary. Finally, to validate performance on very large games, we show the performance of ODO on Kuhn and Ledue Poker which have huge size of pure strategies. As we benchmark on OSO iterations against other baselines, for fair comparison, we implement plain OSO in Algorithm 1 without the less- fresufre best-respouse mentioned in Equa- tion (8) for our experiments. All hyperparameter setting can be found in Appendix D.
30
20
10
Nash supp:10
Nash supp:30
Nash supp:20
Nash supp:50
0
2x10²
4x10²
6x10²
8x102
1x10a
Size of full strategy set
Figure 1: Sizes of effective strategy set (i.e., k) in cases of OSO agent playing against an MWU opponent with different sizes of full strategy set and NE support. This plot shows that the size of OSO's effective strategy set. docs not inerease drastically with the full strategy size, but rather depends on the support size of the NE.
6.1 Size of is vs. Support Size of NE
We consider a set of zero-sum normal-form games different sizes, the entries of which are sampled from uniform distribution U(0, 1). We run OSO as the row player against a no-regret column player until convergence, and plot the size of the OSO player's effective strategy set against its full strategy size. We run 20 seeds for each setting, As we achieved by fixing the number of columns while increasing the nunber of rows in the game matrix, the size of the effective strategy set k grows as the size of the full strategy set increases, but plateaus quickly. The larger the size of the NE support (not the full strategy sot!), the highor this plateau will reach. Clcarly, we can tell that the size of OSO's effective strategy set does not increase drastically with the full strategy size, but rather depends on the support size of the NE. This result confirms Theorem in which we prove that OSO's regret bound depends on k; which is related to the size of the NE support but not the game size. Economically, this is desired property OSO potentially avoid unnecessary computation, in contrast. to other no-regret methods that require looping over the full strategy set at each iteration.
see from Figure given fixed support size of the NE, which is
We choose MWU for column player our experiment, but expect other negregret algorithms would give similar result.
11

---

Published in Transactions on Machine Learning Research (10/2022)
Leduc Poker
Kuhn Poker
100
PSRO P2PSRO
DD
XFP
PSRO
DD
XFP
ODO (Ours)
CFR
P2PSRO
DDD (Ours)
CFR
100
Exploitability
Exploitability
10-1
1
-0-2
10
10-3
0
50
100
150
200
250
300
350
50
150 Number of BR computed
100
200
250
Number of BR computed
(a) Exploitability on Ledue Poker
(b) Exploitability on Kuhn Poker
Figure 2: Performance comparisons in exploitability on Poker games.
Online Do.ble Orade
Ondine Couble drade
Online Couble Drade
Online Doache Crecke
Online Do Oracie
Restrouu Play
Fisst oux Play
Fictoou Play Hassplicattv eeaggts
nottoiuu Pay
Rotrrcuu Play
Muttillcatvv Welggtt
Humphoattv Welgtts
Sulti icstive Weights
Vulto konthe Velghht
Cia Curree + N 1
Els Gamte
Combearthlte- 2, (omiis 5)
Mauessgamm-- te lac towt')
Normal Semoull Game
315
thuclt
Destec
Destee pustipiiaaiin meggins uo HoM.
Dearic Doant Chuukt sutt wiihee Uo wi M00
Oriend Chuckt
puttp seig mo (G) wi MiU
Hurtt pliaati seig it. UV wi Hevt)
Vulla kieve Wagee U0 el MMU
Trangula
Deline Drcide Dtadle Petti costoooste Pay
Ordire Doodle Gradee Picitios Pay
Pellic Das the ordtl Reciious May
Deliic Distk thacke
Dellie Brat diack
hittlices Ply
Riltieus Pay
018-
medigtts
nnarpeictive Woights
Mudieiicativ Weiges
Witpkcate Weigens
Vullyk wagges
barelions
Barsllone
Barstore
baretors
Figure 3: Performance comparisons under self-plays
6.2 Performance on Real-World Empirical Games
We investigate ODO in terms of convergence rate to a NE. To demonstrate its applicability to real-world problems, we replace the randomly generated normal-form games with 15 popular real-world zero-sum empirical games from Czarnecki el al. (2020). We compare the exploitabilily 6 (Davis et al., 2014) of ODO with other baseline methods (MWU, FP and DO 7). We run each game with 20 seeds. In Figure 3, ODO outperforms the basclines in almost all 15 games. The advantage of ODO in terms of convergence rate over MWU and FP match our expectation as the support sizes of the NEs in these games are much smaller than the game sizes (reported in Table 2 in Appendix D). For DO with MWU, since it takes many iterations in each sub-game to converge to the NE, it performs poorly in comparison to ODO.
Apart from the self-play setting, we also look at the setting of playing against an MWU adversary in Figure 4. We can see that OSO outperforms MWU and DO baselines in average performance in almost all 15 games, which confirms the effectiveness of our design. Notably, MWU achieves a constant payoff; we believe this is because these games are symmetric and since both players follow MWU with the same learning rate, the
"cxploitability= 0 implics the algorithm reaches the true NE.
Following the discussion in the Online Double Oracle section and for fair comparisons, we implement DO by adopting MWU as the sub-game NE solver and report the total number of MWU iterations DO needs to achieve a low exploitability.
12

---

Published in Transactions on Machine Learning Research (10/2022)
3-move parity game
5.4-Blotto
Alpha
four
game
1.00
MIN
VINU
Avarage Payoff
o6a KrNWU
050
0So
050
0.50
HMM
wt MNU
DC w/ HIV
MIU
0.00
-0.15
-1.00
Elo game noise=D.1
Ello game
golboard_ solbbard_siee_33333 jize=3,kamii6...
tic_ _ac_tac_u toe
Normal Berouuli game
Average Phycff
0.75
MWW
cso
Nwl csa
250
MMU
oso
VNU
050
HMM
vl Niw
00 w/ MNlU
DO w/ HWW))
00 w/ MMN
0.25
0.00
-0.50
qucridor/board sizz-izzz
Random game skill
Transitive game
Triangular game
misere/game-tic. tac.tataccaaccc......ao -ic_tac tocll)
1.00
Average Payoff
-0.25
-0.75
-1.00
23120' Swtt /axte 1.0var 23x10 axid" tadit Lixurb
25x12" bideil kad Ueto
Zaxcpl S.tii /axte" Jakkbl
Zantt"saaip 75x12 sitecp! Iterations
iterations
Itarations
Iterations
Iterations
Figure 4: Performance comparisons against MWU adversary
payoff will always be the value of the game (thus the ground truth), which OSO will eventually converge to as well.
6.3 Performance on Poker Games
To further investigate ODO's effectiveness, we test ODO on Kuhn and Ledue Poker. Since ODO is designed only for normal-form games, adopt the tabular setting (McAleer et al., 2020; Lanetot et al., 2017) in which exact best-response is computed by a tree-traversal oracle (see OpenSpiel (Lanctot et al., 2019) or MALib (Zhou et al., 2021)), and for PSRO methods, we perturb the exact best-response with random noise. We benchmark how many times such a best-response oracle is called by different methods. We compare against the state-of-the-art PSRO method: P2SRO 8 (McAleer et al., 2020), and two extensive- form game solvers, CFR (Zinkevich et al., 2007) and XFP (Lanctot et al., 2019). As shown in Figure 2, ODO shows a significant improvement in exploitability compared to all existing DO and PSRO baselines, and it almost catches up with the CFR solver in Leduc Poker, and it outperforms CFR on Kuhn Poker. Importantly, ODO uses the fewest best-response calls to achieve the lowest exploitability, We believe these are promising results, since ODO is not designed for extensive-form games, but experimentally it matches up with efficient extensive-form methods. In our future work, we hope to use the idea of ODO and Regret Matching (Hart & Mas-Colell, 2000) to create a state-of the-artttterrtteeee solver in extensive-form games.
7 Conclusion
We propose a novel solver for two-player zero-sum games where the number of pure strategies is huge. Our method, Online Double Oracle, absorbs the benefits from both online learning methods and Double Oracle methods; it achieves the regret bound of O( k log(k)/T) where k is the size of the effective strategy set rather than the game size n. Importantly, ODO can exploit opponents during game play. In tens of real-world games, we show that ODO outperforms a series of algorithms including MWU, DO and PSRO both in terms of convergence rate to NE and average payoff against strategic adversaries.
We have discounted the fact that P2SRO uses multiple workers (we use two) to compute rest-responses.
13

---

Published in Transactions on Machine Learning Research (10/2022)
References
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1))48-77, 2002.
Avrim Blum and Yishay Monsour. Learning, regret minimization, and equilibria. Algorithmic Game Theory, 2007.
HF Bohnenblust, S Karlin, and LS Shapley. Solutions of discrete, (wo-person games. Contrduutions to the Theory of Games, 1:51-72, 1950.
Michael Bowling and Manuela Veloso. Rational and convergent. learning stochastic games. In International joint conference on artificial intelligence, volume 17, pp. 1021-1026. Citesoer, 2001.
Felix Brandt, Felix Fischer, and Paul Harrenstein. On the rate of convergence of fictitious play. In International Symposium on Algorithmic Game Theory, pp. 102-113. Springer, 2010.
George W Brown. Iterative solution of games by fictitious play. Activity analysis of production and allocation, 13(1):374-31) 376, 1951a.
GW Brown. Iterative solution of games by fictitious play. Activily Analysis of Production and Allocalion (TC' Koopmans, Ed pp. 374-376, 1951b.
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Xi Chen and Xiaotie Deng. Settling the complexity of two-player nash equilibrium. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS pp. 261-272. IEEE, 2006.
Wojeiech M Czarnecki, Gauthier Gidel, Brendan Traccy, Karl Tuyls, Shayegan Omidshafici, David Balduzzi, and Max Jaderberg. Real world games look like spinning tops. Advances Neural Information Processing Systems, 33, 2020.
C Daskalakis and Ioannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. In 10th Innovations in Theoretical Computer Science (ITCS) conference, ITCS 2019, 2019.
Trevor Davis, Neil Burch, and Michael Bowling. Using response functions measure strategy strength. In Proceedings of the AAAI Conference Artificial Intelligence, volume 28, 2014.
Steven De Rooij, Tim Van Erven, Peter D Grünwald, and Wouter M Koolen. Follow the leader if you can, hedge if you must. The Journal of Machine Learning Research, 15(1):121--1316, 2014.
Xiaotie Deng, Yuhao Li, David Henry Mguni, Jun Wang, and Yaodong Yang. On the complexity of computing markov perfect equilibrium in general-sum stochastic games. arXiv preprint vxXiv:2109.01790 2021.
Le Cong Dinh. Online learning against strategic adversary. Proceedings of the 21st. International Conference on Autonomous Agents and Multiogent Systems, pp. 1841 1841-1842, 2022.
Le Cong Dinh, David Henry Mguni, Long Tran-Thanh, Jun Wang, and Yaodong Yang. Online markov decision processes with non-oblivious strategic adversary. arXiv preprint ar Xrx::22110.038 2021a.
Le Cong Dinh, Tri-Dung Nguyon, Alain B Zemhoho, and Long Tran-Thanh. Last round convergence and no-dynamic regret in asymmetric repeated gamess In Algorithamic Learning Theory, pp. 553 577. PMLR, 2021b.
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. Aduances in Neural Information Processing Systems, 34, 2021.
Yoav Freund and Robert E Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1-2):79-1M) 103, 1999.
14

---

Published in Transactions on Machine Learning Research (10/2022)
Sergiu Hart and Andreu Mas- Colell. A simple adaptive procedure leading to correlated equilibrium. Econo- metrica, 68(5):1127-11500 2000.
Sergiu Hart and Andreu Mas-Coleld A general class of adaptive strategies. Journal of Economic Theory, (1):26-5p) 54, 2001.
Johan Jonasson et al. On the optimal strategy in a random game. Electronic Communications in Probability, 9:132-139, 2004.
Mare Lanctot, Kevin Waugh, Martin Zinkevich, and Michael H Bowling. Monte carlo sampling for regret minimization in extensive games. In NIPS, pp. 1078-1086, 2009.
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 reinforeement learning. In Advances in neural informalion processing systems, pp. 4203, 2017.
Mare Lanctot, Edward Lockhart, Jean- Baptiste Lespiau, Vinicius Zambaldi, Satyaki Upadhyay, Julien Pérolat, Sriram Srinivasan, Finbarr Timbers, Karl Tuyls, Shayegan Omidshafiei, et al. Openspiel: A framework for reinforcement learning in games. arXiv preprint (XXi:1908.09455 2019.
David S Leslie and Edmund J Collins. Generalised weakened fictitious play. Games and Economic Behavior, 56(2):285 298, 2006.
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-sun games. Advances in Neural Information Processing Systems, 34:941-95 11222,, 2021.
Stephen McAleer, John Lanier, Roy Fox, and Pierre Baldi. Pipeline PSRO: scalable approach for finding approximate nash equilibria large games. Advances in Neural Information Processing Systems (NeurIPS), 2020.
Stephen McAleer, John Lanier, Pierre Baldi, and Roy Fox. XDO: A double oracle algorithm for extensive-form games. Advances in Neural Information Processing Systems (NeurIPS), 2021.
H Brendan McMahan, Geoffrey J Gordon, and Avrim Blum. Planning in the presence of cost functions controlled by an adversary. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pp. 536 543, 2003.
Oskar Morgenstern and John Von Neumann. Theory of gomes and economic behavior. Princeton university press, 1953.
John F Nash al. Equilibrium points in n-person games. Proceedings of the national academyy of sciences, 36(1):48 49, 1950.
Neumann. Zur theorie der gesellschaftsspiele. Mathematische annalen, 100(1):295 290- 1928.
P Peng, Q Yuan, Y Wen, Y Yang, Z Tang, H Long, and J Wang. Multiagent bidircttionlll-ccordnaaee nets for learning to play starcraft combat games. arxiv 2017. arXio preprint arXiv: 103. 10069, 2017.
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.
Tim Roughgarden. Algorithmic game theory. Commanications of the ACM, 53(7):78 86, 2010.
Ricky Sanjaya, Jun Wang, and Yaodong Yang. Measuring the non-transitivity in chess, 2021.
Shai Shalev-Shwariz et al. Online learning and online convex optimization. Foundations and Irends in Machine Learning, (22):1071144, 2011.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
15

---

Published in Transactions on Machine Learning Research (10/2022)
Jan van den Brand. A deterministic linear program solver in current matrix multiplication time. In Proceedings of the Fourleenth Annual ACM-STAM Symposium on Discrele Algorithms, pp. SIAM, 2020.
Oriol Vinyals, Igor Babuschkin, Wojeiech M Czarnecki, Michaäl Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 375(77882:350--322 2019.
Yaodong Yang and Jun Wang. An overview of multi-agent reinforcement learning from game theoretical perspective. arXiv preprint arXiv:201 wxX::2011.00583, 1.00583, 2020.
Yaodong Yang, Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang. Mean field multi-agent reinforcement learning. In International Conference on Machine Learning, pp.
PMLR, 2018.
Yaodong Yang, Rasul Tutunov, Phu Sakulwongtana, and Haitham Bou Ammar. aa-rank: Practically scaling o-rank through stochastic optimisation. In Proceedings of the 19th International Conference Aulonomous Agents and MultiAgent Systems, pp.
2020.
Yaodong Yang, Jun Luo, Ying Wen, Oliver Slumbers, Daniel Graves, Haitham Bou Ammar, Jun Wang, and Matthew E Taylor. Diverse auto-curriculm is critical for succossful real-world multiagent learning systems. In Proceedings of the 20th International Conference on Aulonomous Agenls and MulliAgent Systems, pp. 51-56, 2021.
Ming Zhou, Ziyu Wan, Hanjing Wang, Muning Wen, Runzhe Wu, Ying Wen, Yaodong Yang, Weinan Zhang, and Jun Wang- Malib: A parallel framework for population-based multi-agent reinforcement learning. arXiv preprint 05k:21006.0753... 2021.
Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information. Advances in neural information processing systems, 20:1729-1736, 2007.
16

---

Published in Transactions on Machine Learning Research (10/2022)
A Appendix: Double Oracle and Variant of MWU
A.1 Double Oracle
Algorithm 3: Double Oracle Algorithm (McMahan et al., 2003)
1: Input: Full strategy set II, C
2: Initialise sets of strategies Ilo, Co
3: for == 1 to oo do
4: if II, + I1-11 or C. C,-1 then
Solve the NE of the sub-game G₁: (TT ct) arg enn, maxeeλc, πτ Ac
Find the best response a++1 and c++1 to c():
a++1 arg minaen a Act
C++1 = arg maxeeC it Ac
7:
11 = II, U [(a+1),,C00 C++1 C {c+11}
8: else if II, = I1 and C. = C--1 then
Terminate
10: end if
11: end for
The pseudocode of DO algorithm (McMahan al., 2003) listed in Algorithm 3. The DO method approximates NE in large-size zero-sum games by itcratively creating and solving series of sub-games (ie., game with restricted set of pure strategies). Specifically, at time step 1, the DO learner solves the NE of a sub-game G,. Since the sets of pure strategies of the sub-game G, = (II, C,) are often much smaller than the original game, the NE of sub-game Ge can be easily solved in line 5. Based on the NE of the sub-game: (T,, cf), each player finds a best response to NE (line 6), and expand their strategy set (line 7). PSRO methods (Lanctot al., 2017; McAleer et al., 2020) are variants of DO met which RL meds are adopted approximate the best response strategy. For games where small support size assumption does not hold, DO methods restore to solve the original game and have no advantages over LP solutions.
Although DO can solve large-scale zero-sum games, it requires to coordinate both players to consistently find the NE (see line 5 in Algorithm 3); this renders an disadvantage of DO that when applied in real-world games, it cannot exploit the opponent who can play any non-stationary strategy (see the example of RPS in Introduction). Our ODO solution address this problem by combining DO with tools in online learning.
Algorithm 4: Online Double Oracle Algorithm
Input: Full pure strategy set IT, C Init. effective strategies set: 1lg 1I1, Co C1
3: for t- 1 to T do
4: Each player follows the OSO in Algorithm 1 with their respective effective strategy sets II, C.
5: end for
6: Output: TT, II,, CT, Cr
Recall that if both players follow no-regret algorithm, then the average strategies of both players converge to the NE in two-player zero-sum games (Cesa-Bianchi & Lugosi, 2006; Blum & Monsour, 2007). Since OSO has the no-regret property, it is then natural to study the self-play setting where both players utilise OSO, which, we call Online Double Oracle (ODO), and to investigate its convergence rate to a NE in large games.
There are two major benefits of using ODO in comparison to DO: Firstly, ODO does not need to compute a NE in each sub-game which can become computationally expensive for large sub-games. Secondly, ODO produces rational agents which can exploit adversary to achieve the no-regret property.
17

---

Published in Transactions on Machine Learning Research (10/2022)
A.2 Doubling Trick
Definition 6 (The Doubling Trick). For algorilium with the regrel av with paromeler depends the time-horizon T. The Doubling Trick restarts the algorithm at round 2 for m=0,1,2...
Follow the doubling trick for an algorithm with regret ovT, the total regret is not bigger than the sum of the regret in each part. We then have:
(T)]
1 27
V2
RT S
av
<
aVT.
1- v2
V2-1
A.3 AdaHedge: MWU with Adaptive Learning Rate
Definition 7 (AdaHedge (De Rooij et al., 2014)). Let Cı, C1,02, be a sequence of mixed strategies played by the column player. The row player is said to follow AdaHeddge if TT+1 is updated as follows
exp (-re (-HE
Ei= a² Ac,)
(1) = Ei= exp Ei
[n]
(10)
T Ac,)
where n is the number of pure strategies and μt is an adaptive learning rate such as: pt = loo(n)))/e A, denoles the cumulative mizability gop, which can derived from historical data (Equation (5) in (De Rooij et al., 2014)).
Then applying Theorem 8 in (De Rooij al., 2014) to setting with 5= L L T we have:
[I+ [T,) 1.-)
16
R1 Add
2
-+-L- log(n) log(n) +
(11)
L - 1-12/4 1, 1.- log(n) log(n) +2 2 /log(n) +
16
16 log(n) + 2.
2
3
B Online Single Oracle
B.1 OSO with Less-Frequent Best Response
Theorem 8 (Regret Bound of OSO with Less-Frequen Best Response). Let L, 12.2..,,,77 lr be sequence of loss vectors played by an adversary. Then, OSO in Algorithm 5 is no-regret algorithm with:
1
(
min xEll
Σ (TT
(olgg())
Ei= a
2T
where = [[ is the size of effective strategy set in the final time window.
Proof. W.l.o.g, we assume the player uses the MWU as the no-regret algorithm and starts with only one pure strategy in II, in Algorithm 1. Since the final time window, the effective strategy set has k elements, there are exactly time windows. Denote [ [Tg] be the lengths of time windows during each of which the subset of strategies the no-regret algorithm considers does not change. In the case of finite set of strategics, & will be finite and we have
Ta =T.
In the time window with length [T,], following the regret bound of MWU we have:
Teaa
Thaal Σ
Tr log(i),
Σ ( 4))
min
(TT, 4) S
where [T|= =
Σ j=1
TT--
(12)
mell 12 t= +
2
t= +11+1
18

---

Published in Transactions on Machine Learning Research (10/2022)
Algorithm 5: OSO with Less-Frequent Best Response
Input: A set pure strategy of player
11 11; initial set of effective strategies;
for 1 to do
if -1,-11, - then
5: Following the MWU update in Equation (3)
6: clse if IT, + 4-1 then
7: Start a new time window T1+1
Reset the MWU update in Equation (3) with new initial strategy m
end if
10: Obscrve 4 and update the average loss in the current time window TІ
1= [T. Ex.eT, 4
11:
Calculate the best response:
arg min (T, 1)
12:
if pp (T,, 1 4)) - min (TT, Ej=1a 4)) 2 of 1-17 then
13:
Update the strategy set: l1+11 II, Ua
14:
else
15:
11++1 = 11,
16:
end if
17:
Output the strategy at round t for the player
18:
end for
Since in the time window Tú the size of the effective strategy set does not change, thus we have:
ITal
ihtl
min TEll 17 (
Σ
(T,4))
min wen
Σ
(T ()) S a'n.
(13)
t= +|1++1
From Inequalities (12) and (13) we have:
Tr+1l
Ti41
Ti
Σ
(TT,
min well
Σ
(n, 40) I V
log(t) + aam
(14)
2
1=/A+41
t=/G
Sum up the inequality (14) for = 1,... we have:
T 2 Σ
Tyyil
log(i) + aa/T
(T, Le)
min well
Σ t=/Ti/+1
{ le)
2
t=1
Tital
T
T
(T,, 4
min #ell
(T,4)
Σ
( 4.)
min Tell
(7,, 4e)
(15a)
t=|T++1
i=1
Tk log(
T
aiz
Σ [=1
(TT 4e)
min
Σ (T,, le).
(15b)
2
Inequality (15a) is due to Σ min min D.
Inequality (15b) comes from Cauchy-Schwarz inequality and Stirling' approximation. Thus, we have the derived regret bound.
B.2 Proof of Theorem 4
Before provide the proof for the Theorem, we need the following lemma:
Lemma 4. DO will converge to e-NE if players can only access to an e-best response in each round.
19

---

Published in Transactions on Machine Learning Research (10/2022)
Proof. We first prove in the case of single oracle algorithm. The double oracle proof will be similar. Since the number of strategies is finite, by the same argument in the the case of exact best response, the process will converge. Suppose that at time step t, the process stops. Since we use e-best response, we have the following relationship:
A.4
min AL S
well
If we set the weight of pure strategies does not appear in n. to be zero to make T/ then it is obvious that
π. A4 = n.
Thus, have the following relationship:
Tt AL. min π
Ale Se
(16)
*ell
Further, since 4, is Nash equilibrium of A,, we also have
max 7.. Al 7/ Ale max T. A,l Ti T Arhi = 0 TEA;
(17)
IEA;
From inequalities (16) and (17), by definition conclude that (T) is e-NE of the game A.
Now, we can prove Theorem 4:
Theorem 9. Suppose OSO agent can only access the e-best response in each iteration when following Algorithm 1, if the adversary follows a no-regret algorithm, then the average strategy of the agent will converge to an e-NE. Purthermore, the algoritlom is e-reyrel:
RJ T RT
lim T
Se
max
n Ac; - T AAt))
mEAn
Proof. Suppose that the player uses the Multiplicative Weights Update in Algorithm with e-best response. Denote [Ti], [T....... [Tkl be the lengths of time windows during each of which the subset of strategies the no-regret algorithm considers does not change. Furthermore,
Ts = T.
In time window T;, the regret with respect to the bost fixed stratogy in the effective strategy set is:
Taal
Tatpl Σ
Ti
Σ
(Tt, 42)
min #Ell T,141
4) S
log(t),
(18)
2
[1/++
[=/1+11
where [T,| - Ejj=Ej=loo [Tyl.
Since in the time window T, the e-best response strategy stays in II and therefore
we have:
min *ell T.l
Σ
(T,4)
min wEll
Σ
(T,4)
c|T,
1=|TT|+1
t=|T.|1
Then, from the inequality (18) we have:
Perpl
Pl
T2 (T, L.) $ V
T 4)
min
Σ
log(1) + +e[Tal.
(19)
menl
2
+
[=1+++1
20

---

Published in Transactions on Machine Learning Research (10/2022)
Sum up the inequality (19) for 1,... k have:
T log(t)
min
(TT 4
e|Tal,
T log(t)
Try b))
min
Σ
(T, S ET +
(20a)
Tell
1= Ti|+1
(T. bi)
min TEll
k < +
log(i)
2
1=1
T 2
(T 4)
min
Σ (T. b) S cT + V
v h log(A))
(20b)
flll
Inequality (20a) is due to Σ min min Σ. Inequality (20b) comes from Cauchy-Schware incquality and
Stirling' approximation. Using inequality (20b), we have:
k log(k)
min(#, ( 1) #Ell
T (T, 4.)
Σ
(21)
2T
That is, the OSO algorithm is e-regret in the case of c-best response.
Since the adversary follows a no-regret algorithm, we have:
T
TT
max
T
Te, 1+) S V 2
Vlog(T)
IEAL
1=1
(22)
T
LL)
max ( 1)
<
(T 11) +
jeAr
T
27
Using the inequalities in (21) and (22) we have:
k log (k)
1) min
n 1)
2 T
(1)
2T
1=1
log(L) (L)
k log(() (k)
2 max ( 1)
JeAz
2T
2T
Similarly, we also have:
log(L)
( < max ( 1) < T
Σ TTe, 4.)
V
IEA;
2T
< min (T,, 1} + v #ell
1 klog(k)
log(I)) L))
2T
2T
Take the limit T + co, we then have:
max (7, 1) - - (T S min (T, te LEAL
Thus (+,() is the e-Nash equilibrium of the game.
C Bound on the size of effective strategy set k
C.1 Proof of Lemma
Lemma In asymmetric games Anxm, n >> m, if the NE (TT* c²)) is unique, then the support size of the NE will follow (supp(x") |supp(c") S m
21

---

Published in Transactions on Machine Learning Research (10/2022)
Proof. Since the size of n and c* and m respectively, the size of the support of NE can not exceed the size of the game:
support(x*) S n: |support(c")) m.
In the case the game A has a unique Nash equilibrium, following Theorem 1 in (Bohnenblust et al., 1950), we have:
support * |support(c") S min(n, m)
Thus, we have proved the lemma.
C.2 Proof of Lemma
Definition 10 (Strictly Dominant Strategy). strategy is called a strictly dominant strategy for the row player if:
# Ac π Ac VT C.C.
Lemma 6. Suppose there erists a striclly dominant stralegy for the player, then the size of the effective strategy set will be bounded by 2.
Proof. First we show that strictly dominant strategy in two-player zero-sum game is a pure strategy. Let tt the strictly dominant strategy. By definition of strictly dominant strategy we have:
T Ac < π Ac VT C.
Let a be pure strategy such that:
a argmin a Ac',
aell
where et is constant vector. If a is mixed strategy then we have # a and
Ac Ac A
contradicts with the definition of strictly dominant strategy. Thus, the strictly dominant strategy two-player zero-sum game is pure strategy
Now, after the first iteration, the OSO algorithm will add the best response to the effective strategy set. Since there exists strictly dominant strategy á and it is pure strategy, म will be added to the effective strategy set.. From the second iteration, since the strietly dominant strategy is already in the effective stratogy set, the best response to any average loss is always in the effective stratogy set. Thus, the effective strategy set will not be expanded after iteration 2. In other words, the size of the effective stralegy set will be bounded by 2.
C.3 Proof of Lemma
Lemma 7. Suppose the plagers start with the entry A1,1 and the game matrix A of the two-players zero-sum game is designed such as
0.1i
A. 0.5
Vi [n];
A 0.9 Vi [n-1] 1],
n
A,, 0.8 vj 2, [n].
0.1 vj < iiiE [n),
A.j A. +
2n
where is the size of the pure strategy set for both players. Then the game has unique Nash equilibrium with support size of 1 (L.e,, the entry Ann) and the effective strategy set both DO and OSO method will reach the size of pure strategy set: k = n.
Witt the argument, a strictly dominant strategy in any normal- normal-form game is pure strategy.
22

---

Published in Transactions on Machine Learning Research (10/2022)
Proof. First, we show that the game A has unique Nash equilibrium at entry Ann- Following the design of matrix A we have:
a" = argmin a' Ac"; c² arginax a"! Ac eEC
eell
Thus by definition, (a", c")) is the NE of the game and An, is the minimax value of the game. Suppose there is another NE of the game (á, é) such that à + a 10 Then, by definition of the NE we have:
à Ac à Ać
An,
since the minimax value v is unique in two-player zero-sum game. However, by the design of matrix A, a Ac 2 Va E II and the equal sign holds true only if a". This leads to contradiction. Thus, the gain A has unique pure NE with respect to the entry An,.
Next, we show that Double Oracle method with the NE as best response target will recover the whole pure stratogy set in this game.
By definition, the game start with the entry AI, and the initial effective strategy sets are Th = {a²} and Co= = (c Since, A1,1 = argminge|m| A,, and A1.2 2 = argmax,ejal A1.j: : the new sub-game created with the corresponding effective strategy set: II, = { and C = c²"). Note that the effective strategy set of the row player remains unchanged in this iteration. The NE the sub-game 2 is the with respect to entry A1,, thus the next itcration, the best response targets for the column and row player are with respect at and e², respectively. Now, in iteration 3, since 22. = argmingg(n) Ar, and A1,2 = argmax JE[m] Ai,j, the new sub-game 3 is created with the corresponding effective strategy set: 1l₂ = {aa, a²} and C1 = cd), Note that in this round, the effective strategy set of the column player remains unchanged. Following the same process, the effective strategy set of the row player will add the a' pure strategy in iteration 2;-1 while the effective strategy set of the column player will add the pure strategy e at iteration 2: 2. Thercfore, the DO method will add the whole pure strategy set until converging to the NE in this example.
For the OSO method, we can follow the same process in the above DO case. That is, for the adversary, we allow to play the NE of the sub-game in the same order as DO. Since OSO is a no-rogret algorithm and the average loss will remain the same for each lime window (since we fix the adversary in this case), the OSO algorithm will converge to the best response with respect to the current average loss. Since we design the game such that in each sub-game, the Nash Equilibrium will be a pure strategy, the best response with respect to the NE of the adversary will also be the NE of the player in the current sub-game. After the player (i.e., following OSO method) converges to the NE of the sub-game, the adversary will move to play the NE of the next sub-game. That way, the OSO algorithm will need to add the whole pure strategy set when playing against this type of adversary.
In more specific way, the adversary can play the following policy. In the first iteration, the adversary plays c². Since the best reponse with respect to cº is at, at will be added to the effective strategy set. Then iteration 2, the adversary plays c². Then, a² is the best response with respect to the current average loss (ie., Ac + Ac?). Thus, a² is added to the effective strategy set. In the next iteration, by the design of the game matrix A, we have the following relationship:
h
+h = aarmmin T A v') a
aell
J=1
Thus, by letting the adversary plays el to c sequentially, the effective strategy set of the agent will need to recover the whole pure strategy set. Note that the policy used by the adversary is also a no-regret algorithm since in the later rounds, the adversary can just follows the pure strategy c and achicving the value of the game, thus deducting any negative payoffs from the first rounds.
10 same argument holds true the case #
23

---

Published in Transactions on Machine Learning Research (10/2022)
C.4 Computation Comparison between ODO and MWU
Lemma 8. when the size of effeclive stralegy set k salisfies
S vT,
then ODO is more computationally efficient than MWU in finding Nash Equilibrium in two-player zero-sum games.
Proof. In order to find e-NE, ODO requires
k kk)
k log(k)
T>
T
where T is the number of rounds. Since each round requires ( computation, the total computation of ODO will be &² (k)
Similarly, to find c-N,, MWU requires Vlog(n/TT < c and computation for cach round is O(n). Therefore, the overall computation of MWU will be approximately:
n log(n)
Therefore, ODO is more computationally efficient than MWU when
k log(k)
n log(n)
2
which can be satisfied when k S
C.5 Convergence Rate of ODO
Theorem 11. Suppose both players apply OSO. Let k1, hy denote the size of the effective strategy set for each player. Then, the average strategies of both plagers converge to the NE with the rate:
ln log(R1)
+ -Vho 1i log(k2)
CT
2T
2T
In the situation where both players follow OSO with Less- Less-Frequent Best- Rest-Response in Equation (8) and at T.l = V - [Ti], the convergence rate to NE will
11 log(k1)
K2 log(k2)
Vh + Voz VT
CT
+
2T
2T
Proof. Using the regret bound of OSO algorithm in Theorem 3 we have:
Tki log(ks)
T Σ
Tk2 log(k))
Σ n Ac
min
Ac
π
Ac
π Ac; <
cEC
1=1
[=1
From the above incqualitics we can derive that
T Σ
ki log(k))
h2 logooo))
ki log(k))
म Ac min π Ac > xell
n.
Act
max π T Ac - cEC
T
2T
2T
2T
1=1
Similarly, we have
1 T
h2 log(k2)
ki log(k1)
ko (k2)
π Ae < max ग. Ac < CEC
Σ
Ac, +
min π Ač + mell
T
2T
2T
27
[=1
24

---

Published in Transactions on Machine Learning Research (10/2022)
Table 2: Size of the Nash Support of Games
Game
Total Strategies
Size of Nash support
3-Move Parity Game
160
5,4-Blotto
56
AlphaStar
888
3
Connect Four
1470
23
Disc Game
1000
27
Elo game + noise=0.1
1000
Elo game
1000
Go 3
1933
13
Misere (game=tic tac toe)
926
Normal Bernoulli game
1000
Quoridor (boardsize=3)
1404
Random game of skill
1000
Tic Tac Toe
880
Transitive game
1000
Triangular game
1000
Thus, with eT V
log(k))
log(
we have
21
21
T
max
π
T Ac
S
ET
Ac min π T Ac+ 6r. Tell
CEC
By definition, (Ø, Z) is er-Nash equilibrium
situation where both players follow OSO with Less- Bess-Frequent Best Response, following Theorem 6 Appendix B.1 we have:
T
Tki log(k))
A1
Thi log(ki)
T Ac
min TEll
π
T Ac I
a/T
S
+ VKIVT
2
2
1=1
Tk2 log(k2)
hg
T Tkk log(k2)
T
Ac
T. Ac. S
S
VVVT.
2
2
1m
tml
Thus, using the same above arguments in the case of OSO, with eT have:
ki log(k))
ky log(kz)
tkit
27
27
/T
T T
Ac ET S T Ae min π Ač ET.
max CEC
π
REll
t=1
D Additional Experimental Results
We provide further experiments demonstrate the performance of the Online Single Oracle and Online Double Oracle algorithms. All the codes for the experiments attached supplementary.
25

---

Published in Transactions on Machine Learning Research (10/2022)
Leduc Poker with restricted opponent
Kuhn Poker with restricted opponent
0.00
Expected payoff
Expected payoff
-0.05
0
00.00
-0.15
-2
PSRO Online Single Oracle
Online Single (Ours)
-0.20
500
1000
1250
1750
10000
15000
20000
Iterations
Iterations
(a) Leduc Poker.
(b) Kuhn Poker.
Figure 5: Performance comparisons against imperfect opponent on Poker games.
Learning Rate of MWU. When facing a MWU adversary, we set the learning rate of the adversary to be optimal (i.e., 14 = v 8 log( (A)/T). That is, we eliminate the case when one can exploit MWU adversary with wrong learning rate. For DO-MWU algorithm, we allow the algorithm update to next subgame when it achieves c-Nash Equilibrium with 0.01. Therefore, subgame to be 14 0.01 so that the DO-MWU can achieve 0.01-Nash Equilibrium in subgames in al most O(log(k)/e) steps. For fair comparison with DO methods, we also choose the same learning rate f 0.01 for our ODO in the experiments.
optimally choose the learning rate of MWU in a
Small Support Size of NEs in Real-Worle Zero-Sum Games. Along with the theoretical guarantee in Lemma 1, we demonstrate that small support size assumption holds true for many real-world games. To do that, we report the total strategies (i.e., number of pure strategy for each player) and the size of Nash support for 15 popular real-world games (Czarnecki et al., 2020) in Table 2. As we of the game we tested, the support size of NEs is a fraction of the game size, reassuring the accuracy of small support size assumption. Notably, in the game with pure NEs (i.c., size of Nash support equals to 1), ODO outperforms other baselines by a large margin, both in exploitability and average payolI.
in Table 2, in all
Finally, we want to test the no-regret property of OSO when the opponent imperfect and plays restricted set. We created such an opponent in both Pokers by restricting its strategy set to only 20 pure strategies, and then let it play MWU. We apply our OSO with e-best response as the row player, and compare its perform against PSRO. We run each setting for 10 random seeds. As we can see from Figure 5, OSO quickly achieves positive expected payoff and outperforms PSRO, which is expected because OSO can actively exploit its opponent while PSRO behaves conservatively by playing NE and not exploiting (thus achieving almost constant payoff).. Notably, the average expected payoff of OSO decreases slightly in later iterations, we believe it is because the opponent is following MWC, which is also no-regret method, and both players will converge towards an NE of such restricted game.
Can OSO Exploit an Imperfect Opponent?
26


Reviews:
[{"review_id": "WzbJq96UEZ", "reviewer": "Reviewer_tPpz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n* The proposed ODO algorithm combines advantages from two disparate lines of algorithms for learning NE: DO type algorithms (which grows support size incrementally and thus handles large action space), and no-regret algorithms (who performs well against adversarial opponents when deployed by a single agent). Notably, it is a standard result that MWU can be used to learn NE too via self-play, but MWU cannot handle large action spaces. The very promise of DO is to get around that by growing support size one at a time, but DO loses no-regret when deployed by a single agent. In this sense, ODO gives sort of a best-of-both-worlds. As the core claim of the paper, this is a nice contribution in my opinion.\n\n* Theorem 3 shows that the regret bound of OSO scales only with $k$, the support size of the final output policy. The proof of this fact appears not to be technically challenging, and follows directly from summing the standard regret bounds for MWU over the $k$ periods. But logically, it gives a justification of why ODO should be used when regret is the main consideration (i.e. why not just use MWU in that case). \n\n* I like the experiments section a lot. First of all I think the *designs* of the three experiments in Sections 6.1-6.3 are already nice and accurately test the main claims of the paper, in particular Section 6.1 which tests the support size of the final output policy when true game has small support. The experiments are well executed and complete enough (though probably not super extensive). The results look promising and reasonably justify the main claims in my opinion.\n\n* Overall the presentation and logical structure of the paper is nice too. The related works and various discussions are quite clear. (e.g. I like having Section 5.1 which compares ODO with DO+MWU; I had exactly that question in mind before reaching there :) I also like Lemma 3 which gives a negative result about the support size of ODO’s final output policy in the worst case. \n\n\nWeaknesses:\n\n* A main concern is that the choice of the stepsize in MWU algorithms / subroutines seem to be unspecified. If they are indeed not properly chosen, this could affect many of the main theoretical and empirical claims:\n  - The stepsize of MWU is unspecified in both the ODO algorithm box (Algorithm 1) and Theorem 3, whose proof uses the standard fact that MWU with $A$ actions achieves $\\sqrt{\\log A\\cdot T}$ regret. However, this requires careful choice of the stepsize: (1) Either $T$ is known in advance and the stepsize is chosen as $\\sqrt{\\log A/T}$, or (2) if an anytime algorithm (i.e. with changing learning rate) is used. The former cannot hold for ODO algorithm because the algorithm could not know the length of the current period in advance. The later is a potential remedy, e.g. by using the anytime FTRL algorithm (cf. Exercise 28.13 in Szepesvari and Lattimore, “Bandit Algorithms”), but that would substantially change the algorithm (FTRL with changing learning rate is no longer equivalent to MWU). \n\n  - In the experiments, I did not spot how the stepsizes for MWU are chosen. This importantly affects conclusions about both ODO (which uses MWU as subroutine), as well as other baselines such as DO+MWU, and an opponent who plays an MWU. In particular, this makes the claim in Section 6.3 that ODO > MWU slightly fishy (e.g. an MWU algorithm with the correct learning rate already beats an opponent who runs MWU with the wrong learning rate, e.g. too small).\n\n  - A related question about DO-MWU: how many MWU iterations are performed in each DO loop? I think being careful here, e.g. by choosing different #iterations per loop, may substantially improve the DO-MWU baseline?\n\n* Aren’t Lemma 1 and 2 or results of similar nature known in the literature? For example, Lemma 1 shows that for an $n\\times m$ game with $n\\ge m$ and a unique NE, the support size of the NE for both players is bounded by $m$. However, isn’t this just a corollary of the fact that all NE of nondegenerate $n\\times m$ games has equal support sizes for both players (Proposition 3.3, “Algorithmic Game Theory”, Nisan et al. 2007)? If that’s the case, perhaps proper citations around these Lemmas would be deserved. \n\n\n* The empirical result that the final output policy has a small support size when true game has a sparse NE in Section 6.1, is claimed as an advantage of ODO. How does this compare with the Regret Matching algorithm, which also has some “pruning” effect and maintains a sparse strategy in later iterations, if there are only so many good actions? (Though, I understand Regret Matching does not handle large action spaces as nicely as ODO.)\n\nGiven the above, I am positive about the core contribution and overall execution of the paper, provided the above concerns (especially the one about stepsize) can be addressed. \n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a new algorithm Online Double Oracle (ODO) for finding Nash Equilibria (NE) in two-player zero-sum normal-form games with a large number of actions. \n\nOn the theoretical side, the paper shows that ODO achieves both convergence to NE and handles large action spaces like Double Oracle (DO) type algorithms, as well as no-regret against adversarial opponents when deployed by a single agent as Online Single Oracle (OSO). The regret can be better than standard Multiplicative Weights Update (MWU) if the learned policy at termination has a small support size.\n\nOn the empirical side, the paper shows that ODO often outperforms standard DO when used as self-play to learn NE, as well as better payoff than MWU when played against an (adversarial) opponent who runs their own MWU algorithm.\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Please find my questions in the Weaknesses part above.\n\nAdditional questions / minor suggestions about writing and discussions:\n\n* Page 1, “Firstly” and “Secondly”, in my opinion they are really just one thing and “Secondly” is the main thing. “Firstly” was talking about required coordination to learn NE, but in a weaker sense, coordination is almost always required, e.g. with self-play + no-regret type algorithms, at least the two players each need to deploy a no-regret algorithm. It’s only that DO seems to be a stronger coordination requirement (very precise algorithm steps) where no-regret could be a weaker requirement (any no-regret algorithm suffices).\n\n* Table 1, “Large Games”, perhaps good to briefly explain what that means in the caption, to make the table self-contained (even though it’s already explained in the main paper).\n\n* Section 3.1 (Page 3), “RL methods are adopted to approximate the best-response strategy”, what does “RL methods” refer to? e.g. perhaps good to add “(e.g. those with neural net function approximation)” if that’s what the authors meant?\n\n* Section 4.2 (Page 6), “Generally”, the argument about effective strategy set sounds a bit hand-wavy to me; in a strict sense it lacks considerations about sensitivity (e.g. if the opponent only plays $\\epsilon$-NE and we are learning their $\\epsilon$-best response, then we may still end up getting a policy with large support. If the paragraph was meant to be a heuristic argument, it may be good to be explicit about that (e.g. say “heuristically, …”).\n\n* Lemma 2 (Page 7), what is a “strictly dominant strategy”? Maybe add a definition in Appendix C.2 and then add a pointer here?\n\n* Theorem 5 (Page 9), may be good to shorten or put to appendix, and mention it is just the standard online-to-batch argument for converting regret to Nash.\n\n* Section 5.1, “every time a sub-game NE is solved, which often requires thousands of MWU iterations”... sounds too hand-wavy? For example, why can’t I carefully chose the precision parameter in each iteration of DO-MWU in a decaying fashion, so that overall number of MWU iterations are controlled yet DO-MWU algorithm still performs well? (cf. the same question in the “weakness” part about experiments).\n\n* Section 5.1, “even if DO implements MWU to solve the sub-game NE, it is still not a no-regret algorithm”, why is that (good to add a reference?)\n\n* Section 6.2, “exploitability (i.e., the distance to a true NE)”, the description could be misleading (e.g. regarded as parameter-space distance). Consider changing to a more rigorous description of exploitability?\n", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "cdI1DjEe9y", "reviewer": "Reviewer_HYLZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n- The proposed idea is simple (in terms of both algorithms and analysis) yet effective. \n- Experiments are extensive and demonstrates the benefits of the proposed algorithm. \n\nWeakness\n- The theoretical advantage of the proposed algorithm over MWU is unclear. The main reason is that k (the effective support used by the algorithm) may not scale down with the support of the NE if the initial strategy set is not carefully chosen. The authors did not propose solutions (even a heuristic one) to try to make k closer to the true support size. \n- While Lemma 3 provides a negative example for a particular initial strategy set (i.e., start with A_{1,1}), it would be desirable to investigate a more reasonable algorithm in which the initial strategy is uniformly chosen from all pure strategies. \n\nOverall, while the idea proposed by the paper is elegant and effective, I feel that some deeper questions (e.g., those stated above) could be further discussed or investigated. \n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes Online Double Oracle, which combines the ideas of no-regret online learning (e.g., multiplicative weight update) and Double Oracle (for fast computation of NE with small NE support), thus achieving the best of both worlds: no-regret in the adversarial setting and fast convergence to NE in the self-play setting when NE support is small. Experiments on synthetic and real games are provides, showing the advantages of the proposed algorithms over previous ones. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "It would be good to include a discussion on when ODO can find NE in a computationally more efficiently way than MWU+MWU. Below is my discussion that could be added to the paper (but not necessary): \n\nTo find a $\\epsilon$ NE using ODO, we need $\\sqrt{\\frac{k\\log k}{T}}\\leq \\epsilon$, where $T$ is the number of rounds. That is, $T\\gtrsim \\frac{k\\log k}{\\epsilon^2}$. Since each round requires $O(k)$ computation, the overall computation is roughly $\\frac{k^2\\log k}{\\epsilon^2}$. \n\nTo find a $\\epsilon$ NE using MWU, we need $\\sqrt{\\frac{\\log n}{T}}\\leq \\epsilon$. That is, $T\\gtrsim \\frac{\\log n}{\\epsilon^2}$. Since each round requires $O(n)$ computation, the overall computation is roughly $\\frac{n\\log n}{\\epsilon^2}$. \n\nTherefore, ODO is more computationally efficient than MWU when $k\\lesssim \\sqrt{n}$. \n(Of course it would be great to provide conditions under which this inequality will hold, or even conditions under which the support of NE is less than $\\sqrt{n}$)", "broader_impact_concerns": "There is no concern on ethical implications. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "bJtvsjv08W", "reviewer": "Reviewer_CEob", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The combination of DO and MWU is reasonable, and probably gets the best of both algorithms. I am a bit unsure about restarting MWU each time after a new strategy is added (especially if the effective size is reasonably large), but that is probably useful to simplify the theoretical analysis.\n\nI am not sure if the ideas are scalable for larger games, but that is left for the future, and I think the results of the paper are of interest for researchers working on no-regret algorithms for normal-form games.\n\nConvergence results being provided only for time-averaged strategies seems a bit weaker result than converging to a NE strategy set. This limitation should be made more clear, and discussed clearly when the guarantees of different algorithms are compared.\n\nThere are some lesser issues regarding clarity and soundness (listed below) that should be corrected, but these seem easy to fix.  \n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers two-player zero-sum normal-form games. The authors propose an algorithm (ODO) that combines the Double Oracle (DO) and the Multiplicative Weight Update (MWU) algorithm. The resulting algorithm keeps the no-regret flavor of MWU, and converges to Nash equilibrium with a rate that depends on the size of the effective strategy set (like DO). The regret bounds of ODO are proven for a time averaged strategy pair.\n\nEmpirical work show that the size of the effective strategy set is growing approximately linearly with the the NE support size\nin random matrix games, which indicate that ODO could be effective even if the size of the game is large. The algorithm is compared favorably against several baselines on a large number of real (toy) games, including Leduc and Kuhn poker.\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Proof of Theorem 3, equation (4): it is not clear to which Theorem/Corollary in Freund & Schapire (1999) the authors refer, when stating the the regret bound of MWU. In Corollary 4 (FS99), the regret bound is \\sqrt{2ln(n)/T} + ln(n)/T. It is possible to obtain \\sqrt{ln(n)/(2T))}, but the result should be cited and used precisely.\n\nStep in (6b) should be expanded at least in the appendix, with a clear indication of exactly which inequalities being used.\n\nIt should be more explicit in the discussion of the bounds that only the time-averaged strategies converge to a Nash equilibrium, and not the strategies played at any given time. In fact, the bound allows a situation in which at no time the strategies would be even close to a NE (like in a rock-paper-scissors scenario, where each player is playing a pure strategy that beats the opponent's previous action).\n\nIn the comparison between bounds, O(\\sqrt{log(n)/T}) is regraded as unfavorable to O(\\sqrt{k log(k)/T}), when k<<n. But, they are similar when k=log(n), which still can be regarded as k much smaller than n.\n\nIn the experiments, Kuhn and Leduc Poker are described as \"very large games\", but these are toy games that are easy to 'solve' by traditional means. They may have a large number of pure strategy set (it would have been useful to add them in Table 2), but still are fairly small compared to games that are regularly played by humans, or games that have been solved in the last few decades.  \n\n\n\nSection 3:\n\t\"We consider A_{i,j} to represent the (normalised) loss of the row player when playing a mixed strategy\": isn't it pure strategy?\n\nSection 4 title: Oralce -> Oracle\n\npage 9, proof, following \"From the above...\":\n     in \"max_{c \\in C} \\sum ... \" the \\sum should be deleted\n\nAppendix, Alg. 3, line 5:\n\t  \"arg min arg max\" looks a bit strange, even if the intention is clear\n", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: I thank the authors for a very diligent rebuttal - all the reviewers were satisfied with it and therefore I suggest to accept ODO as is.
Decision: Accept (poster)