Theoretical and Practical Advances on Smoothing for Extensive-Form Games

Introduction

Extensive-form games (EFGs) are a broad class of games; they model sequential interaction, imperfect information, and outcome uncertainty. Nash equilibria prescribe a particular notion of rational behavior in such games. In the specific case of two-player zero-sum EFGs with perfect recall, an exact Nash equilibrium can be computed in polynomial time using a Linear Program (LP) whose size is linear in the size of the game tree (von Stengel 1996). However, in practice the LP approach has two major drawbacks limiting its applicability. First, the LP may be prohibitively large and may not fit in memory. Second, even when it does, the iterations of interior-point methods or the simplex algorithm are prohibitively expensive (Sandholm 2010). Practical methods for EFG solving tackle this issue through two complementary approaches: Abstraction and iterative game solvers with low memory requirements (Sandholm 2010). In this paper we focus on the second approach. Iterative game solvers mainly fall in two categories: (i) counterfactual-regret-based methods (Zinkevich et al. 2007; Lanctot et al. 2009) achieving a convergence rate on the order of $O({1\over\epsilon^{2}})$, and (ii) first-order methods (FOMs) (Hoda et al. 2010; Kroer et al. 2015) achieving a convergence rate of $O({1\over\epsilon})$. The better convergence rate of FOMs makes them more attractive from a theoretical viewpoint. This paper investigates the acceleration of such FOMs for EFGs, from both a theoretical and a numerical perspective.

Nash equilibrium computation of a two-player zero-sum EFG with perfect recall admits a Bilinear Saddle Point Problem (BSPP) formulation where the domains are given by the polytopes that encode strategy spaces of the players. The most efficient FOMs are designed to solve this BSPP. The classical FOMs to solve BSPPs such as mirror prox (MP) (Nemirovski 2004) or the excessive gap technique (EGT) (Nesterov 2005a) utilize distance-generating functions (DGFs) to measure appropriate notions of distances over the domains. Then the convergence rate of these FOMs relies on the DGFs and their relation to the domains in three critical ways: Through the strong convexity parameters of the DGFs, the norm associated with the strong convexity parameter, and set widths of the domains as measured by the DGFs.

Hoda et al. 2010 introduced a general framework for constructing DGFs for treeplexes—a class of convex polytopes that generalize the domains associated with the strategy spaces of an EFG. While they also established bounds on the strong convexity parameter for their DGFs in some special cases, these lead to very weak bounds and result in slow convergence rates. Kroer et al. 2015 developed explicit strong convexity-parameter bounds for entropy-based DGFs (a particular subclass of DGFs) for general EFGs, and improved the bounds for the special cases considered by Hoda et al. 2010. These bounds from Kroer et al. 2015 generate the current state-of-the-art parameters associated with the convergence rate for FOMs with $O({1\over\epsilon})$ convergence.

In this paper we construct a new weighting scheme for such entropy-based DGFs. This weighting scheme leads to new and improved bounds on the strong convexity parameter associated with general treeplex domains. In particular, our new bounds are first-of-their kind as they have no dependence on the branching operation of the treeplex. Informally, our strong convexity result allows us to improve the convergence rate of FOMs by a factor of $\Omega(b^{d}d)$ (where $b$ is the average branching factor for a player and $d$ is the depth of the EFG) compared to the prior state-of-the-art results from Kroer et al. 2015. Our bounds parallel the simplex case for matrix games where the entropy function achieves a logarithmic dependence on the dimension of the simplex domain.

Finally, we complement our theoretical results with numerical experiments to investigate the speed up of FOMs with convergence rate $O({1\over{\epsilon}})$ and compare the performance of these algorithms with the premier regret-based methods CFR and CFR+ (Tammelin et al. 2015). CFR+ is the fastest prior algorithm for computing Nash equilibria in EFGs when the entire tree can be traversed (rather than sampled). Bowling et al. 2015 used it to essentially solve the game limit Texas hold’em.

CFR+ is also the algorithm used to accurately solve endgames in the Libratus agent, which showed superhuman performance against a team of top Heads-Up No-Limit Texas hold’em poker specialist professional players in the Brains vs AI event Confirmed through author communication. A slight variation This variation was chosen for implementation reasons, though, and has inferior practical iteration complexity. of CFR+ was used in the DeepStack agent Moravčík et al. 2017, which beat a group of professional players. Our experiments show that FOMs are substantially faster than both CFR algorithms when using a practically tuned variant of our DGF. We also test the impact of stronger bounds on the strong convexity parameter: we instantiate EGT with the parameters developed in this paper, and compare the performance to the parameters developed by Kroer et al. 2015. These experiments illustrate that the tighter parameters developed here lead to better practical convergence rate.

The rest of the paper is organized as follows. Section 2 discusses related research. We present the general class of problems that we address—bilinear saddle-point problems—and describe how they relate to EFGs in Section 3. Then Section 4 describes our optimization framework. Section 5 introduces treeplexes, the class of convex polytopes that define our domains of the optimization problems. Our focus is on dilated entropy-based DGFs; we introduce these in Section 6 and present our main results—bounds on the associated strong convexity parameter and treeplex diameter. In Section 7 we demonstrate the use of our results on instantiating EGT. We compare our approach with the current state-of-art in EFG solving and discuss the extent of theoretical improvements achievable via our approach in Section 7.1. Section 8 presents numerical experiments testing the effect of various parameters on the performance of our approach as well as comparing the performance of our approach to CFR and CFR+. We close with a summary of our results and a few compelling further research directions in Section 9.

Related work

Nash equilibrium computation has received extensive attention in the literature (Littman and Stone 2003; Lipton et al. 2003; Gilpin and Sandholm 2007; Zinkevich et al. 2007; Daskalakis et al. 2009; Jiang and Leyton-Brown 2011; Kroer and Sandholm 2014; Daskalakis et al. 2015). The equilibrium-finding problems vary quite a bit based on their characteristics; here we restrict our attention to two-player zero-sum sequential games.

Koller et al. 1996 present an LP whose size is linear in the size of the game tree. This approach, coupled with lossless abstraction techniques, was used to solve Rhode-Island hold’em (Shi and Littman 2002; Gilpin and Sandholm 2007), a game with $3.1$ billion nodes (roughly size $5\cdot 10^{7}$ after lossless abstraction). However, for games larger than this, the resulting LPs tend to not fit in the computer memory thus requiring approximate solution techniques. These techniques fall into two categories: iterative ${\epsilon}$-Nash equilibrium-finding algorithms and game abstraction techniques (Sandholm 2010).

The most popular iterative Nash equilibrium algorithm is the counterfactual-regret-minimization framework instantiated with regret matching (CFR) (Zinkevich et al. 2007), its sampling-based variant monte-carlo CFR (MCCFR) (Lanctot et al. 2009), and CFR instantitated with a new regret minimization technique called regret matching plus (CFR+). These regret-minimization algorithms perform local regret-based updates at each information set. Despite their slow convergence rate of $O(\frac{1}{{\epsilon}^{2}})$, they perform very well in pratice, especially CFR+. Recently, Waugh and Bagnell 2015 showed, with some caveats, an interpretation of CFR as a FOM with $O(\frac{1}{{\epsilon}^{2}})$ rate. Nonetheless, in this paper we make a distinction between regret-based methods and $O(\frac{1}{{\epsilon}})$ FOMs for ease of exposition.

Hoda et al. 2010 initially proposed DGFs for EFGs leading to $O(\frac{1}{{\epsilon}})$ convergence rate when used with EGT. Kroer et al. 2015 improved these result for the dilated entropy function. Gilpin et al. 2012 give an algorithm with convergence rate $O(\ln(\frac{1}{{\epsilon}}))$. Their bound has a dependence on a certain condition number of the payoff matrix, which is difficult to estimate; and as a result they show a bound of $O(\frac{1}{{\epsilon}})$ which is independent of the condition number. Detailed comparisons to all three algorithms discussed here are given in Section 7.1.

Finally, Bosansky et al. 2014 develop an iterative double-oracle algorithm for exact equilibrium computation. This algorithm only scales for games where it can identify an equilibrium of small support, and thus suffers from the same performance issues as the general LP approach.

In addition to equilibrium-finding algorithms, another central topic in large-scale game solving has been automated abstraction (Sandholm 2010; Sandholm 2015). Initially, this was used mostly for information abstraction (Gilpin and Sandholm 2007; Shi and Littman 2002; Zinkevich et al. 2007). Lately, action abstraction approaches have gained considerable interest (Hawkin et al. 2011; Hawkin et al. 2012; Brown and Sandholm 2014; Kroer and Sandholm 2014; Kroer and Sandholm 2016). Sequential game abstraction approaches with solution quality bounds have also emerged for stochastic (Sandholm and Singh 2012) and extensive-form (Lanctot et al. 2012; Kroer and Sandholm 2014; Kroer and Sandholm 2016) games more recently.

Problem setup

Computing a Nash equilibrium in a two-player zero-sum EFG with perfect recall can be formulated as a Bilinear Saddle Point Problem (BSPP):

This is known as the sequence-form formulation (Romanovskii 1962; Koller et al. 1996; von Stengel 1996). In this formulation, $x$ and $y$ correspond to the nonnegative strategy vectors for players $1$ and $2$ and the sets ${\mathcal{X}},{\mathcal{Y}}$ are convex polyhedral reformulations of the sequential strategy space of these players. Here ${\mathcal{X}},{\mathcal{Y}}$ are defined by the constraints $Ex=e,Fy=f$, where each row of $E,F$ encodes part of the sequential nature of the strategy vectors, the right hand-side vectors $e,f$ are $\left|\mathcal{I}_{1}\right|,\left|\mathcal{I}_{2}\right|$-dimensional vectors, and $\mathcal{I}_{i}$ is the information sets for player $i$. For a complete treatment of this formulation, see von Stengel 1996.

Our theoretical developments mainly exploit the treeplex domain structure and are independent of other structural assumptions resulting from EFGs. Therefore, we describe our results for general BSPPs. We follow the presentation and notation of Juditsky and Nemirovski 2011a; Juditsky and Nemirovski 2011b for BSPPs. For notation and presentation of treeplex structure, we follow Kroer et al. 2015.

Optimization setup

In its most general form a BSPP is defined as

The BSPP $({\mathcal{S}})$ gives rise to two convex optimization problems that are dual to each other:

with ${\hbox{\rm Opt}}(P)={\hbox{\rm Opt}}(D)={\hbox{\rm Opt}}$. It is well known that the solutions to $({\mathcal{S}})$ — the saddle points of $\phi$ on ${\mathcal{X}}\times{\mathcal{Y}}$ — are exactly the pairs $z=[x;y]$ comprised of optimal solutions to the problems $(P)$ and $(D)$. We quantify the accuracy of a candidate solution $z=[x;y]$ with the saddle point residual

In the context of EFG, ${\epsilon_{\hbox{\scriptsize\rm sad}}}(z)$ measures the proximity to being an ${\epsilon}$-Nash equilibrium.

Most FOMs capable of solving BSPP $({\mathcal{S}})$ are quite flexible in terms of adjusting to the geometry of the problem characterized by the domains ${\mathcal{X}},{\mathcal{Y}}$ of the BSPP $({\mathcal{S}})$. The following components are standard in forming the setup for such FOMs (we present components for ${\mathcal{X}}$, analogous components are used for ${\mathcal{Y}}$):

Vector norm: $\|\cdot\|_{\mathcal{X}}$ on the Euclidean space ${\mathbf{E}}$ where the domain ${\mathcal{X}}$ of $({\mathcal{S}})$ lives, along with its dual norm $\|\zeta\|_{\mathcal{X}}^{*}=\max\limits_{\|x\|_{\mathcal{X}}\leq 1}\langle\zeta,x\rangle$.

Matrix norm: $\|A\|=\max_{y}\left\{\|Ay\|_{\mathcal{X}}^{*}:\|y\|_{\mathcal{Y}}=1\right\}$ based on the vector norms $\|\cdot\|_{\mathcal{X}},\|\cdot\|_{\mathcal{Y}}$.

Bregman distance: $V(u\|x):=\omega_{\mathcal{X}}(u)-\omega_{\mathcal{X}}(x)-\langle\omega_{\mathcal{X}}^{\prime}(x),u-x\rangle$ for all $x\in{\mathcal{X}}^{\circ}$ and $u\in{\mathcal{X}}$.

Prox-mapping: Given a prox center $x\in{\mathcal{X}}^{\circ}$,

$\omega$-center: $x_{\omega}:=\mathop{\rm argmin}\limits_{x\in{\mathcal{X}}}\omega_{\mathcal{X}}(x)\in{\mathcal{X}}^{\circ}$ of ${\mathcal{X}}$.

Set width: $\Omega_{x}:=\max\limits_{x\in{\mathcal{X}}}V(x\|{x_{\omega}})\leq\max\limits_{x\in{\mathcal{X}}}\omega_{\mathcal{X}}(x)-\min\limits_{x\in{\mathcal{X}}}\omega_{\mathcal{X}}(x)$.

The distance-generating functions $\omega_{\mathcal{X}},\omega_{\mathcal{Y}}$ can be used to create smoothed approximations to $\overline{\phi},\underline{\phi}$ as follows (Nesterov 2005b):

where $\mu_{1},\mu_{2}>0$ are smoothness parameters denoting the amount of smoothing applied. Let $y_{\mu_{2}}(x)$ and $x_{\mu_{1}}(y)$ refer to the $y$ and $x$ values attaining the optima in (3) and (4). These can be thought of as smoothed best responses. Nesterov 2005b shows that the gradients of the functions $\overline{\phi}_{\mu_{2}}(x)$ and $\underline{\phi}_{\mu_{1}}(y)$ exist and are Lipschitz continuous. The gradient operators and Lipschitz constants are given as follows

Based on this setup, we formally state the Excessive Gap Technique (EGT) of Nesterov 2005a in Algorithm 1.

The EGT algorithm alternates between taking steps focused on ${\mathcal{X}}$ and ${\mathcal{Y}}$. Algorithm 2 shows a single step focused on ${\mathcal{X}}$. Steps focused on $y$ are completely analogous. Algorithm 1 shows how the alternating steps and stepsizes are computed, as well as how initial points are selected.

Suppose the initial values $\mu_{1},\mu_{2}$ in the EGT algorithm satisfy $\mu_{1}=\frac{\varphi_{\mathcal{X}}}{L_{1}(\overline{\phi}_{\mu_{2}})}$. Then, at every iteration $t\geq 1$ of the EGT algorithm, the corresponding solution $z^{t}=[x^{t};y^{t}]$ satisfies $x^{t}\in{\mathcal{X}}$, $y^{t}\in{\mathcal{Y}}$, and

Consequently, (Nesterov 2005a) proves that the EGT algorithm has a convergence rate of $O(\frac{1}{{\epsilon}})$.

Treeplexes

Hoda et al. 2010 introduce the treeplex, a class of convex polytopes that encompass the sequence-form description of strategy spaces in perfect-recall EFGs.

Basic sets: The standard simplex $\Delta_{m}$ is a treeplex.

Cartesian product: If $Q_{1},\ldots,Q_{k}$ are treeplexes, then $Q_{1}\times\cdots\times Q_{k}$ is a treeplex.

Branching: Given a treeplex $P\subseteq\left[0,1\right]^{p}$, a collection of treeplexes $Q=\left\{Q_{1},\ldots,Q_{k}\right\}$ where $Q_{j}\subseteq\left[0,1\right]^{n_{j}}$, and $l=\left\{l_{1},\ldots,l_{k}\right\}\subseteq\left\{1,\ldots,p\right\}$, the set defined by

is a treeplex. In this setup, we say $u_{l_{j}}$ is the branching variable for the treeplex $Q_{j}$.

A treeplex is a tree of simplexes where children are connected to their parents through the branching operation. In the branching operation, the child simplex domain is scaled by the value of the parent branching variable. Understanding the treeplex structure is crucial because the proofs of our main results rely on induction over these structures. For EFGs, the simplexes correspond to the information sets of a single player and the whole treeplex represents that player’s strategy space. The branching operation has a sequential interpretation: The vector $u$ represents the decision variables at certain stages, while the vectors $q_{j}$ represent the decision variables at the $k$ potential following stages, depending on external outcomes. Here $k\leq p$ since some variables in $u$ may not have subsequent decisions. For treeplexes, von Stengel 1996 has suggested a polyhedral representation of the form $Eu=e$ where the matrix $E$ has its entries from $\left\{-1,0,1\right\}$ and the vector $e$ has its entries in $\left\{0,1\right\}$.

Note that we allow more than two-way branches; hence our formulation follows that of Kroer et al. 2015 and differs from that of Hoda et al. 2010. As discussed in Hoda et al. 2010, it is possible to model sequence-form games by treeplexes that use only two-way branches. Yet, this can cause a large increase in the depth of the treeplex, thus leading to significant degradation in the strong convexity parameter. Because we handle multi-way branches directly in our framework, our approach is more effective in taking into account the structure of the sequence-form game and thereby resulting in better bounds on the associated strong convexity parameters and thus overall convergence rates.

Our analysis requires a measure of the size of a treeplex $Q$. Thus, we define $M_{Q}\coloneqq\max_{q\in Q}\|q\|_{1}$.

In the context of EFGs, suppose $Q$ encodes player 1’s strategy space; then $M_{Q}$ is the maximum number of information sets with nonzero probability of being reached when player 1 has to follow a pure strategy while the other player may follow a mixed strategy. We also let

In order to illustrate $M_{Q}$ and compare it to the size of $|S_{Q}|$, let us now consider an example of an EFG and its corresponding treeplexes. Consider a game where two players take turns choosing among $k$ actions, and each player chooses actions $d$ times before leaf nodes are reached. In the treeplex $Q$ of Player $1$, each time Player $1$ chooses among $k$ actions constitutes a size $k$ branching operation, and every time Player $2$ chooses among $k$ actions constitutes a size $k$ Cartesian product operation. The total dimensionality of the treeplex, $|S_{Q}|$, is $k^{2d}$, while the value of $M_{Q}$ is $k^{d}$ (since only Cartesian products blow up). Thus, $M_{Q}$ is square root of the size of $|S_{Q}|$.

Dilated entropy functions with bounded strong convexity

In this section we introduce DGFs for domains with treeplex structures and establish their strong convexity parameters with respect to a given norm (see (2)).

The dilation operation preserves convexity, and thus we define the following convex function by dilating the entropy function over the simplexes of a treeplex:

Given a treeplex $Q$ and weights $\beta_{j}>0$ for each $j\in S_{Q}$, we define the dilated entropy function as

where we follow the treeplex notation and $p_{j}$ is the index of the branching variable preceding $\Delta^{j}$, with the convention that $q_{p_{j}}=1$ if $\Delta^{j}$ has no branching operation preceding it.

We would also like the prox-mapping associated with our DGF to be efficiently computable. Hoda et al. 2010 show that for any dilated function, its prox operator on a treeplex can be easily computed through a recursive bottom-up traversal involving the prox mappings associated with the function being dilated on individual simplexes. Since the entropy prox function can be computed in closed form on a simplex, the dilated entropy function can be computed by a single treeplex traversal involving closed-form expressions on each simplex.

Definition 3 above leads to a subset of the DGFs considered by Hoda et al. 2010. Our main theoretical result shows that by a careful selection of the weights $\beta_{j}$, we can significantly improve the strong convexity bounds associated with the dilated entropy function. We will consider weights that satisfy the following recurrence:

Intuitively, $\alpha_{j}$ represents the negative terms that the weight $\beta_{j}$ has to cancel out: the constant $1$ represents the negative term resulting from the squared norm in the strong convexity requirement; the summation term represents the amount of negative terms accumulated from the induction on simplexes descending from simplex $j$. The qualifications on $\beta_{j}$ ensure that $\beta_{j}$ is set such that it at least cancels out the negative terms; the difference $\beta_{j}-\alpha_{j}$ controls the amount of negative value the parent simplex has to make up. This is why we set $\beta_{j}=\alpha_{j}$ when $b_{Q}^{j}=0$. As part of the proof of Lemma 2 we will see why we require a strict inequality $\beta_{j}>\alpha_{j}$ for non-root simplexes.

We give the proofs of Theorems 1 and 2 in Section 6.2. Based on Theorem 2, we get the following corollary:

Corollary 1 follows easily from Theorem 2 and a recursive interpretation of the weights, which is presented as Fact 2 in the next section. In particular, a specific choice of weights in Fact 2 immediately satisfies the recurrence (6) and leads to Corollary 1.

In Theorem 3 we use our strong convexity result to establish a polytope diameter that has only a logarithmic dependence on the branching factor. As a consequence, the associated dilated entropy DGF when used in FOMs such as MP and EGT for solving EFGs leads to the same improvement in their convergence rate.

We start with some simple facts and a few technical lemmas that are used in our proofs.

The first inequality was established in Kroer et al. 2015. The second follows by using $M_{Q}=\sum_{j}q_{i}$ for some $q$, and inductively replacing terms belonging to simplexes j at the bottom with $M_{Q_{j}}$. The result follows because branching operations cancel out by summing to $1$. o

Our next observation follows from Fact 1(a) and is advantageous in suggesting a practically useful choice of the weights $\beta_{j}$ that can be used for Theorem 2 to arrive at Corollary 1.

Given a twice differentiable function $f$, we let $\nabla^{2}f(z)$ denote its Hessian at $z$. Our analysis is based on the following sufficient condition for strong convexity of a twice differentiable function:

For simplexes $\Delta^{j}$ at depth $1$, there is no preceding branching operation; so the variables $h_{p_{j}},q_{p_{j}}$ do not exist. We circumvent this with the convention $h_{p_{j}}=0,q_{p_{j}}=1$ for such $j\in S_{Q}$.

In our proofs we will use the following expression for $h^{\top}\nabla^{2}\omega(q)h$.

Given a treeplex $Q$ and a dilated entropy function $\omega(\cdot)$ with weights $\beta_{j}>0$, we have

We provide the proof of Lemma 1 in the appendix. It simply follows from taking the second-order partial derivatives and rearranging terms.

2 Proofs of our main theorems

The majority of the work for our strong-convexity results is performed by the following lemma, from which our strong convexity results follow easily.

For any treeplex $Q$, the dilated entropy function with weights satisfying recurrence (6) satisfies the following inequality:

We will first show the following inductive hypothesis over the set of non-root simplexes $\widehat{S}_{Q}=\left\{j\in S_{Q}:~b_{Q}^{j}>0\right\}$ for any depth $d\geq 0$:

We begin with the inductive step, as the base case will follow from the same logic. Consider a treeplex $Q$ of depth $d>0$. By applying the inductive hypothesis we have

where the last inequality follows from the definition of $\alpha_{j}$.

Hence, the induction step is complete. For the base case $d=0$ we do not need the inductive assumption: Because ${\mathcal{D}}_{j}^{i}=\emptyset$, $\alpha_{j}=1$, and we get (10) by definition; we can then apply the same convexity argument. This proves our inductive hypothesis.

The first inequality follows from the fact that $h_{p_{j}}=0$ for all $j\in S_{Q}$ such that $b_{Q}^{j}=0$, and for all $j\in S_{Q}$ such that $b_{Q}^{j}>0$, we used our induction. The last inequality follows from (6) and $q_{i},h_{i}^{2}\geq 0$. This then proves (8). o

We are now ready to prove our two main theorems, which we restate before proving them. See 1

This analysis is tight: By choosing a vector $q\in\{0,1\}^{|Q|}$ such that $\|q\|_{1}=M_{Q}$, and setting $h_{i}=\frac{\beta_{j}}{\beta_{j}-\alpha_{j}}\frac{q_{i}}{q_{p_{j}}}h_{p_{j}}$ for all indices $i$ such that $q_{i}=1$ and $h_{i}=0$ otherwise, every inequality in the proof of Lemma 2 becomes an equality. o

where the first inequality follows from the fact that $M_{Q}$ is an upper bound on $\|q\|_{1}$ for any $q\in Q$, and the second inequality follows from the Cauchy-Schwarz inequality.

3 Treeplex width

The convergence rates of FOMs such as MP and EGT algorithms depend on the diameter-to-strong convexity parameter ratio $\frac{\Omega}{\varphi}$, as described in Section 4.1. In order to establish full results on the convergence rates of these FOMs, we now bound this ratio using Corollary 1 scaled by $M_{Q}$.

For a treeplex $Q$, the dilated entropy function with simplex weights $\beta_{j}=M_{Q}(2+\sum_{r=1}^{d_{j}}2^{r}(M_{Q_{j},r}-1))$ for each $j\in S_{Q}$ results in $\frac{\Omega}{\varphi}\leq M_{Q}^{2}2^{d_{Q}+2}\mathop{{\rm log}}m$ where $m$ is the dimension of the largest simplex $\Delta^{j}$ for $j\in S_{Q}$ in the treeplex structure.

EGT for extensive-form game solving

We now describe how to instantiate EGT for solving two-player zero-sum EFGs of the form (1) with treeplex domains. Below we state the customization of all the definitions from Section 4 for our problem.

Note that $\|A\|$ is not at the scale of the maximum payoff difference in the original game. The values in $A$ are scaled by the probability of the observed nature outcomes on the path of each sequence. Thus, $\|A\|$ is exponentially smaller (in the number of observed nature steps on the path to the maximizing sequence) than the maximum payoff difference in the original EFG.

Theorem 3 immediately leads to the following convergence rate result for FOMs equipped with dilated entropy DGFs to solve EFGs (and more generally BSPPs over treeplex domains).

Consider a BSPP over treeplex domains ${\mathcal{X}},{\mathcal{Y}}$. Then EGT algorithm equipped with the dilated entropy DGF with weights $\beta_{j}=2+\sum_{r=1}^{d_{j}}2^{r}(M_{{\mathcal{X}}_{j},r}-1)$ for all $j\in S_{{\mathcal{X}}}$ and the corresponding setup for ${\mathcal{Y}}$ will return an ${\epsilon}$-accurate solution to the BSPP in at most the following number of iterations:

This rate in Theorem 4, to our knowledge, establishes the state-of-the-art for FOMs with $O({1\over{\epsilon}})$ convergence rate for EFGs.

The ratio ${\Omega\over\varphi}$ of set diameter over the strong convexity parameter is important for FOMs that rely on a prox function, such as EGT and MP. Compared to the rate obtained by (Kroer et al. 2015), we get the following improvement: for simplicity, assume that the number of actions available at each information set is on average $a$, then our bound improves the convergence rate of (Kroer et al. 2015) by a factor of $\Omega(d_{\mathcal{X}}\cdot a^{d_{\mathcal{X}}}+d_{\mathcal{Y}}\cdot a^{d_{\mathcal{Y}}})$.

As mentioned previously, Hoda et al. 2010 proved only explicit bounds for the special case of uniform treeplexes that are constructed as follows: 1) A base treeplex $Q_{b}$ along with a subset of $b$ indices from it for branching operations is chosen. 2) At each depth $d$, a Cartesian product operation of size $k$ is applied. 3) Each element in a Cartesian product is an instance of the base treeplex with a size $b$ branching operation leading to depth $d-1$ uniform treeplexes constructed in the same way. Given bounds $\Omega_{b},\varphi_{b}$ for the base treeplex, the bound of Hoda et al. 2010 for a uniform treeplex with $d$ uniform treeplex levels (note that the total depth of the constructed treeplex is $d\cdot d_{Q_{b}}$, where $d_{Q_{b}}$ is the depth of the base treeplex $Q_{b}$) is

Then when the base treeplex is a simplex of dimension ${m}$, their bound for the dilated entropy on a uniform treeplex $Q$ becomes

Even for the special case of a uniform treeplex with a base simplex, comparing Theorem 3 to their bound, we see that our general bound improves the associated constants by exchanging $O(\left|S_{Q}\right|^{2}d_{Q}^{2})$ with $O(M_{Q}^{2}2^{d_{Q}})$. Since $M_{Q}$ does not depend on the branching operation in the treeplex, whereas $|S_{Q}|$ does, these are also the first bounds to remove an exponential dependence on the branching operation (we have only a logarithmic dependence). In Example 1 we showed that there exist games where $M_{Q}=\sqrt{|S_{Q}|}$, and in general $M_{Q}$ is much smaller than $|S_{Q}|$. Consequently, our results establish the best known convergence results for all FOMs based on dilated entropy DGF such as EGT, MP, and stochastic variants of BSPP algorithms.

CFR, CFR+, and EGT all need to keep track of a constant number of current and/or average iterates, so the memory usage of all three algorithms is of the same order; when gradients are computed using an iterative approach as opposed to storing matrices or matrix decompositions, each algorithm requires a constant times the number of sequences in the sequence-form representation. Therefore, we compare mainly the number of iterations required by each algorithm. Since the theoretical properties of CFR and CFR+ are comparable, we compare to CFR, with all statements being valid for CFR+ as well.

CFR has a $O(\frac{1}{{\epsilon}^{2}})$ convergence rate; but its dependence on the number of information sets is only linear (and sometimes sublinear (Lanctot et al. 2009)). Since our results have a quadratic dependence on $M_{Q}^{2}$, CFR sometimes has a better dependence on game constants and can be more attractive for obtaining low-quality solutions quickly for games with many information sets. MCCFR and CFR+ have a similar convergence rate (Lanctot et al. 2009), though MCCFR has cheaper iterations.

Gilpin et al. 2012 give an equilibrium-finding algorithm presented as $O(\ln(\frac{1}{{\epsilon}}))$; but this form of their bound has a dependence on a certain condition number of the $A$ matrix. Specifically, their iteration bound for sequential games is $O(\frac{\|A\|_{2,2}\cdot\ln(\|A\|_{2,2}/{\epsilon})\cdot\sqrt{D}}{\delta(A)})$, where $\delta(A)$ is the condition number of $A$, $\|A\|_{2,2}=\sup_{x\neq 0}\frac{\|Ax\|_{2}}{\|x\|_{2}}$ is the Euclidean matrix norm, and $D=\max_{x,\bar{x}\in{\mathcal{X}},y,\bar{y}\in{\mathcal{Y}}}\|(x,y)-(\bar{x},\bar{y})\|_{2}^{2}$. Unfortunately, the condition number $\delta(A)$ is only shown to be finite for these games. Without any such unknown quantities based on condition numbers, Gilpin et al. 2012 establish a convergence rate of $O(\frac{\|A\|_{2,2}\cdot D}{{\epsilon}})$. This algorithm, despite having the same dependence on $\epsilon$ as ours in its convergence rate, i.e., $O({1\over\epsilon})$, suffers from worse constants. In particular, there exist matrices such that $\|A\|_{2,2}=\sqrt{\|A\|_{1,\infty}\|A\|_{\infty,1}}$, where $\|A\|_{1,\infty}$ and $\|A\|_{\infty,1}$ correspond to the maximum absolute column and row sums, respectively. Then together with the value of $D$, this leads to a cubic dependence on the dimension of $Q$. For games where the players have roughly equal-size strategy spaces, this is equivalent to a constant of $O(M_{Q}^{4})$ as opposed to our constant of $O(M_{Q}^{2})$.

Numerical experiments

We carry out numerical experiments to investigate the practical performance of EGT on EFGs when instantiated with our DGF.

We test these algorithms on a scaled up variant of the poker game Leduc holdem (Southey et al. 2005), a benchmark problem in the imperfect-information game-solving community. In our version, the deck consists of $k$ pairs of cards $1\ldots k$, for a total deck size of $2k$. Each player initially pays one chip to the pot, and is dealt a single private card. After a round of betting, a community card is dealt face up. After a subsequent round of betting, if neither player has folded, both players reveal their private cards. If either player pairs their card with the community card they win the pot. Otherwise, the player with the highest private card wins. In the event both players have the same private card, they draw and split the pot.

First, we investigate the impact of applying the weights used in recurrence (6), as compared to the previous scheme introduced in Kroer et al. 2015. To instantiate recurrence (6) we have to choose a way to set $\beta_{j}$ relative to $\alpha_{j}$. Experimentally, we found that the best way to instantiate the recurrence is to use $\beta_{j}=\alpha_{j}$ for all $j$, in spite of the strict inequality required for our proof. This scheme will henceforth be referred to as new weights. We compare these new weights to the weights used in Kroer et al. 2015 (henceforth referred to as old weights).

Figure 2 shows the result of running EGT with the old and the new weights. For both the old and the new weights, we found that the scalars $M_{Q}$ and $|S_{Q}|$ applied to each DGF in order to achieve strong convexity modulus $1$ according to Corollary 1 and Theorem $5.4$ of Kroer et al. 2015, respectively, are too conservative. Instead, we show the results after tuning these parameters for the corresponding algorithms to yield the best results for each weight scheme. Anecdotally, we found that the old weights are more sensitive and more difficult to tune. The performance also seems more jittery; this is evident even in the strongest parameter we found (especially noticeable on 10, 16, and 30-card Leduc in Figure 2).

We compare the performance of EGT to that of CFR and CFR+ algorithms on a scaled up variant of the poker game Leduc hold’em (Southey et al. 2005), a benchmark problem in the imperfect-information game-solving community. In our version, the deck consists of $k$ pairs of cards $1\ldots k$, for a total deck size of $2k$. Setting $k=3$ yields the standard Leduc game. Each player initially pays one chip to the pot, and is dealt a single private card. After a round of betting, a community card is dealt face up. After a subsequent round of betting, if neither player has folded, both players reveal their private cards. If either player pairs their card with the community card, they win the pot. Otherwise, the player with the highest private card wins. In the event both players have the same private card, they draw and split the pot.

The results are shown in Figure 3. Each graph is a loglog plot that shows the results for a particular instance of Leduc with $6,10,16$ and $30$ card decks, respectively. For each graph, we show the performance of all three algorithms, with the x-axis showing the number of tree traversals, and the y-axis showing the sum of regrets over the two players. We note that tree-travels is a good proxy for overall computational effort because the majority of the time in FOMs is spent on gradient computations, which in our case directly translates into tree-traversals. We find that EGT instantiated with our DGF significantly outperforms both CFR and CFR+ across all four variants of Leduc. This is the case across all iterations; EGT finds a stronger initial point in $x^{0},y^{0}$ (see Algorithm 1), and maintains a stronger convergence rate across all iterations.

The performance we get from EGT relative to CFR and CFR+ is surprising due to what the conventional wisdom in the field has been. In Kroer et al. 2015 it was found that, while EGT has better convergence rate, CFR (which performs worse than CFR+) had better initial performance, and it was only after a certain number of iterations that EGT took over. Furthermore, the switch point where EGT is preferable was found to shift outward on the x-axis as the Leduc game size was increased. This sentiment has been mirrored by Brown and Sandholm 2016. In contrast to this, we find that our DGF along with proper initialization leads to EGT performing better than not only CFR, but also CFR+, at every point on the x-axis. Furthermore, scaling up the game size does not seem to adversely affect this relationship.

While the experiments in Figure 3 are very interesting from the perspective of which algorithm to use for large-scale EFG-solving in practice going forward, there are some caveats to keep in mind. First, we only considered number of tree traversals in our performance calculations. However, CFR algorithms have the ability to avoid parts of the tree traversal. For games where accelerated best-response calculation (Johanson et al. 2011) can be applied, e.g., poker-like games, this is unlikely to have a big effect. But, for some other games, this aspect can be important, though note that Brown et al. 2017 showed experimentally that pruning can be used in EGT as well. Second, to get superior performance from EGT, we had to hand-tune initialization parameters relating to our DGF, whereas CFR+ requires no tuning. Development of an algorithmic scheme for choosing this tuning parameter in EGT can make it significantly easier to apply the tuned variant of EGT in practice. Third, on another practical aspect, CFR+ is a conceptually very simple algorithm, and thus also easy to implement. In contrast to this, EGT and our DGF requires a safe-guarded numerical implementation because the prox operator associated with our DGF requires taking exponentials.

Conclusions

We have investigated FOMs for computing Nash equilibria in two-player zero-sum perfect-recall EFGs. On the theoretical side, we analyzed the strong convexity properties of the dilated entropy DGF over treeplexes. By introducing specific weights that are tied to the structure of the treeplex, we improved prior results on treeplex diameter from $O(|S_{Q}|M_{Q}d2^{d}\mathop{{\rm log}}{m})$ to $O(M_{Q}^{2}2^{d_{Q}+2}\mathop{{\rm log}}{m})$, thereby removing all but a logarithmic dependence on branching associated with the branching operator in the treeplex definition. These results lead to significant improvements in the convergence rates of many FOMs that can be equipped with dilated entropy DGFs and used for EFG solving including but not limited to EGT, MP, and Stochastic MP.

We numerically investigated the performance of EGT and compared it to the practical state-of-the-art algorithms CFR and CFR+. Our experiments showed that EGT with the dilated entropy DGF, when tuned with a proper scaling, has better practical, as well as theoretical, convergence rate than CFR+, the current state-of-the-art algorithm in practice. While our scaling parameter for the DGF did not require extensive tuning, we believe a more principled way of setting it is worthy of further future investigation.

Theorems 1 and 2 establish bounds for a general class of weights $\beta_{j}$ satisfying the recurrence (6). Then in Corollary 1, we have selected a particular weighting scheme for $\beta_{j}$ satisfying (6) and performed our numerical tests. There may be other interesting choices of $\beta_{j}$ satisfying the recurrence (6). Thus, finding a way to optimally choose among the set of weights satisfying (6) to minimize the polytope diameter for specific games is appealing.

On a separate note, in practice CFR is often paired with an abstraction technique (Sandholm 2010) such as those mentioned in Section 2. This is despite the lack of any theoretical justification. Effective ways to pair FOMs such as MP and EGT with practical abstraction techniques (Brown et al. 2015) or abstraction techniques that achieve solution-quality guarantees (Lanctot et al. 2012; Kroer and Sandholm 2014; Kroer and Sandholm 2016) are also worth further consideration.

References

Appendix A Omitted proofs

Then equations (11) and (12) together imply

Using these two equalities in (13) leads to (7) and proves the lemma. o

A.2 Proof of Theorem 3

For our choice of scaled weights $\beta_{j}$, Corollary 1 implies that the resulting dilated entropy function is strongly convex with modulus $\varphi=1$. Hence, we only need to bound $\Omega$.

Any vector $q\in Q$ satisfying $q_{i}\in\{0,1\}$ for all $i$ maximizes $\omega(q)$ and results in $\max_{q\in Q}\omega(q)=0$. For the minimum value, consider any $q\in{\mathop{\rm ri}\,}(Q)$. Applying the well-known lower bound of $-\mathop{{\rm log}}m$ for the negative entropy function on an $m$-dimensional simplex, we have

where the last inequality follows because for each $j\in S_{Q}$ with $d_{j}=0$, the definition of $M_{Q}$ implies $\sum_{j\in S_{Q}:d_{j}=0}q_{p_{j}}\leq M_{Q}$, and for each $j\in S_{Q}$ with $d_{j}=d\geq 1$, we have $2+\sum_{r=1}^{d}2^{r}(M_{Q_{j},r}-1)\leq\sum_{r=1}^{d}2^{r}M_{Q_{j},r}\leq\sum_{r=1}^{d}2^{r}M_{Q_{j}}$ since $M_{Q_{j,r}}\leq M_{Q_{j}}$. Also, from Fact 1(b), we have $\sum_{j\in S_{Q}:d_{j}=d}q_{p_{j}}M_{Q_{j}}\leq M_{Q}$. Then we arrive at

where the last inequality follows because for $d_{Q}=0$ we have $2^{d_{Q}+2}=4>2$ and for $d_{Q}\geq 1$ we have $2d_{Q}\geq 2$.

This lower bound on the minimum value, i.e., $\min_{q\in Q}\omega(q)\geq-M_{Q}^{2}(\mathop{{\rm log}}m)2^{d_{Q}+2}$, coupled with $\max_{q\in Q}\omega(q)\leq 0$, establishes the theorem. o