Solving strategic games whose action space is prohibitively large is a critical yet under-explored topic in economics, computer science and artificial intelligence. This paper proposes new learning algorithms in two-player zero-sum  games where the number of pure strategies is huge or even infinite . Specifically, we combine no-regret analysis from online learning with double oracle methods from game theory. Our method -- Online Double Oracle (ODO) -- achieves the  regret bound of \mathcal{O}(\sqrt{T k \log(k)}) in self-play setting where k is NOT the size of the game , but rather the size of \emph{effective strategy set} that is linearly dependent on the support size of the Nash equilibrium . On tens of different real-world games, including Leduc Poker that contains 3^{936 no-regret algorithms and double oracle methods by a large margin, both in  convergence rate to Nash equilibrium and average payoff against strategic adversary .
Solving strategic games with huge action space 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) methods from game theory. Our method -- Online Double Oracle (ODO) -- is provably convergent to a Nash equilibrium (NE). Most importantly, unlike normal DO methods, ODO isrationale in the sense that each agent in ODO can exploit strategic adversary with a regret bound of \mathcal{O}(\sqrt{T k \log(k)}) where k is not the total number of pure strategies , but rather the size of \emph{effective strategy set} that is linearly dependent on the support size of the NE . On tens of different real-world games, ODO outperforms DO, PSRO methods, and no-regret algorithms such as Multiplicative Weight Update by a significant margin, both in terms of convergence rate to a NE and average payoff against strategic adversaries .
R
whose
with huge
D
prohibitively large is
R
computer science
operations research
R
in
for solving
A
normal-form
R
huge or even infinite
prohibitively large
R
double oracle
Double Oracle (DO)
R
achieves the
is provably convergent to a Nash equilibrium (NE). Most importantly, unlike normal DO methods, ODO is
A
rationale
A
in the sense that each agent in ODO can exploit strategic adversary with a
D
in self-play setting
R
NOT the size of the game
not the total number of pure strategies
R
Nash equilibrium
NE
R
including Leduc Poker that contains 3^{936
ODO outperforms DO, PSRO methods, and
R
and double oracle methods by a large
such as Multiplicative Weight Update by a significant
A
terms of
R
Nash equilibrium
a NE
R
adversary
adversaries