--- title: "Smoothing Method for Approximate Extensive-Form Perfect Equilibrium" authors: - "Christian Kroer" - "Gabriele Farina" - "Tuomas Sandholm" doi: "10.24963/ijcai.2017/42" url: "https://ijcai.org/proceedings/2017/42" pdf: "https://ijcai.org/proceedings/2017/0042.pdf" venue: "Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence" year: 2017 pages: "295-301" track: "Main track" keywords: - "Agent-based and Multi-agent Systems: Multi-agent Learning" - "Knowledge Representation, Reasoning, and Logic: Game Theory" --- # Smoothing Method for Approximate Extensive-Form Perfect Equilibrium Christian Kroer, Gabriele Farina, Tuomas Sandholm *Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence*, pages 295-301. DOI: [10.24963/ijcai.2017/42](https://doi.org/10.24963/ijcai.2017/42) ## Abstract Nash equilibrium is a popular solution concept for solving imperfect-information games in practice. However, it has a major drawback: it does not preclude suboptimal play in branches of the game tree that are not reached in equilibrium. Equilibrium refinements can mend this issue, but have experienced little practical adoption. This is largely due to a lack of scalable algorithms.Sparse iterative methods, in particular first-order methods, are known to be among the most effective algorithms for computing Nash equilibria in large-scale two-player zero-sum extensive-form games. In this paper, we provide, to our knowledge, the first extension of these methods to equilibrium refinements. We develop a smoothing approach for behavioral perturbations of the convex polytope that encompasses the strategy spaces of players in an extensive-form game. This enables one to compute an approximate variant of extensive-form perfect equilibria. Experiments show that our smoothing approach leads to solutions with dramatically stronger strategies at information sets that are reached with low probability in approximate Nash equilibria, while retaining the overall convergence rate associated with fast algorithms for Nash equilibrium. This has benefits both in approximate equilibrium finding (such approximation is necessary in practice in large games) where some probabilities are low while possibly heading toward zero in the limit, and exact equilibrium computation where the low probabilities are actually zero. ## Full text ## 1 Introduction Nash equilibrium is the basic solution concept for noncooperative games, including extensive-form games (EFGs), a broad class of games that model sequential and simultaneous interaction, imperfect information, and outcome uncertainty [Sandholm, 2010; Bowling et al., 2015; Brown et al., 2015; Moravˇc´ık et al., 2017]. Nash equilibrium was the solution concept used 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 in January 2017 [Brown and Sandholm, 2017a]. It was also used in the DeepStack agent [Moravˇc´ık et al., 2017], which beat a group of professional players. It has also been dominant in the Annual Computer Poker Competition [ACPC], where the winning agents have all been based on Nash equilibrium approximation for many years. In spite of this popularity, Nash equilibria suffer from a major deficiency: they might not play reasonably in parts of the game tree that are reached with zero probability in equilibrium. In particular, the only guarantee that Nash equilibrium gives in these parts of the game tree is that it does not give up more utility than the value of the game. Thus, if the opponent makes a big mistake, Nash equilibrium might give back all the utility gained from the opponent making that mistake, since it is only maintaining the value of the game (Miltersen and Sørensen [2010] show nice examples of such behavior). The above shows that Nash equilibrium is not satisfactory in extensive-form games, and is the motivation for equilibrium refinements [Selten, 1975]. When information is perfect, the classical solution concept of subgame-perfect equilibrium (SPE) can be satisfactory, while it is not when information is imperfect. In this latter case, refinements are usually based on the idea of perturbations representing mistakes of the players. In a quasi-perfect equilibrium (QPE) [van Damme, 1984], a player maximizes her utility in each decision node taking into account the future mistakes of the opponents only, whereas, in an extensive-form perfect equilibrium (EFPE), players maximize their utility in each decision node taking into account the future mistakes of both themselves and their opponents [Selten, 1975; Hillas and Kohlberg, 2002]. Computation of Nash equilibrium refinements in EFGs has received some attention in the literature. Von Stengel et. al. [2002] give a pivoting algorithm for computing normal-form-perfect equilibria in EFGs. Miltersen and Sørensen [2010] give an algorithm for computing quasiperfect equilibria. Miltersen and Sørensen [2008] show how to compute a normal-form-proper equilibrium. Farina and Gatti [2017] give an algorithm for computing extensive-form perfect equilibria. All these results rely on linear programming (LP) (in the zero-sum case) or linear complementary programming (LCP). In zero-sum games, several of these solution concepts can be computed in polynomial time using an LP or a series of LPs. However, even for the easier case of Nash equilibria, the LP approach is not scalable for large games (beyond roughly 108 nodes in the game tree [Gilpin and Sandholm, 2007]). Each iteration of an LP-solving algorithm is expensive, and the LP might even be too large to fit in memory. In practice, iterative methods are preferred, even for games of modest size. These methods have iteration costs that are usually linear, or better, in the game size, but converge to a Nash equilibrium only in the limit. The most prominent of these methods are counterfactual regret minimization (CFR) [Zinkevich et al., 2007] and its variants [Lanctot et al., 2009; Tammelin et al., 2015; Brown and Sandholm, 2015; 2017b], and general first-order methods (FOMs) such as the excessive gap technique (EGT) [Nesterov, 2005a] instantiated with an appropriate EFG smoothing technique [Hoda et al., 2010; Kroer et al., 2015; 2017]. Farina et al. [2017] show how to extend CFR to approximate EFPEs. In this paper, we show how to extend FOMs to the computation of an approximate variant of EFPE. Miltersen and Sørensen [2010] and Farina and Gatti [2017] presented perturbed polytopes of EFGs that capture equilibrium refinements where each action has to be played with positive probability. We prove that recent results on smoothing techniques for EFGs based on dilating the entropy function can be modified to provide smoothing for such perturbed games, where the perturbations are with respect to behavioral strategies. We then instantiate this method for the perturbed game of Farina and Gatti, which leads to our approximate EFPE. We then experimentally validate our method. We show that it is effective at obtaining low maximum regret at each information set of the game-even ones that have low probability of being reached-while simultaneously achieving the same practical convergence rate that FOMs and the best CFR variants traditionally achieve for just Nash equilibrium. This has benefits both in approximate Nash equilibrium finding (such approximation is necessary in practice in large games) where some probabilities are low while possibly heading toward zero in the limit, and exact Nash equilibrium computation where the low probabilities are actually zero. ## 2 Preliminaries We assume that the reader is familiar with the classical concept of extensive-form game. We invite the reader unfamiliar with the topic to refer to Shoham and Leyton-Brown [2008] or any classic textbook on the subject for further information and context. Briefly, an extensive-form game Γ is defined over a game tree. In each non-terminal node a single player moves and each edge corresponds to an action available to the player. Each leaf node is associated with a payoff vector, representing the utility for the two players when the game finishes in the leaf. A Nash equilibrium is defined in Definition 2. Definition 1. An ϵ-NE is a strategy profile (π1, π2) for the players, such that no player can gain more than ϵ by unilaterally deviating from their strategy. Definition 2. A Nash equilibrium (NE) is a 0-NE. However, Nash equilibria might not be satisfactory when dealing with EFGs, independently of whether the game has perfect or imperfect information, and whether it is generalor zero-sum. A Nash equilibrium π might prescribe irrational play in those information sets that are visited with zero probability when playing according to π (e.g., [Miltersen and Sørensen, 2008]). In the general-sum case, consider the left example of Figure 1: the strategy profile (π1, π2) where player 1 always chooses action x and player 2 always chooses action y is a NE. However, this strategy profile is irrational: Player 2 is "threatening" to play a suboptimal action, and Player 1 is caving in to the threat. Yet, the threat is not credible: if Player 1 were to actually play action y, it would be irrational for Player 2 to honor the threat. Figure 1: General-sum (left) and zero-sum (right) games where Nash equilibrium prescribes irrational play. Numbers in parentheses denote the payoffs to Players 1 and 2. ![Image](https://ijcai.org/proceedings/2017/fulltext/42/image_000000_7984bc1e51df40cabcc9610ad52a0c257ae283bd97500652b29de545b69c20a9.png) (-5, 5) (0, 0) The right example in Figure 1 shows that even in zero-sum games, a NE can fail to capture (sequential) rationality. In this game, the same strategy profile as in the previous game is again a NE. If Player 2 plays according to this profile, she gives up a potential payoff of 5 if Player 1 plays action y. ## 2.1 Perturbations and Extensive-FormPerfection A way to mend the issue just described is to introduce the idea of "trembling hands": each player cannot fully commit to a pure strategy, and ends up making mistakes with a small (yet strictly positive) probability. This guarantees that the whole game tree gets visited. More formally, let l(h, a) be the perturbation of the game, a (positive) function defining the minimum amount of probability mass with which the player playing at information set h in the game will select action a when playing in h. Let Γl be the game where players are subject to such perturbation: an extensive-form perfect equilibrium of the game Γ is any limit point of the sequence of Nash equilibria of the game Γl, as l vanishes [Selten, 1975]. In this paper, we deal with the simplest form of perturbation - a uniform perturbation lξ for ξ > 0, defined as lξ(h, a) = ξ for all a and h. We will denote the game Γlξ as Γξ. ## 2.2 Bilinear Saddle-Point Problems and the Sequence Form It is well-known that the strategy spaces of an extensiveform game can be transformed into convex polytopes that allow a bilinear saddle-point formulation (BSPP) of the Nash equilibrium problem as follows [Romanovskii, 1962; von Stengel, 1996; Koller et al., 1996]. Our approach for computing equilibrium refinements will be based on constructing a perturbed variant of X and Y. ## Sequence Form It is well-known that the strategy spaces of an extensiveform game can be transformed into convex polytopes that allow a bilinear saddle-point formulation (BSPP) of the Nash equilibrium problem as follows [Romanovskii, 1962; ALGORITHM 1: EGT Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17) setup, we formally state EGT Nesterov, 2005a as Algorithm 1. input : !-center z!, DGF weights µ1, µ2, and ✏ > 0 input : !-center z!, DGF weights µ1, µ2, and ✏ > 0 output: zt (= [xt ; yt ]) x0 = rd⇤X (µ-1 1 rfµ2 (x!)) , y0 = yµ2 (x!); t = 0; z1 := z!; ## ALGORITHM 1: EGT output: zt (= [xt ; yt ]) x0 = rd⇤X (µ-1 1 rfµ2 (x!)) , y0 = yµ2 (x!); t = 0; z1 := z!; while ✏sad(zt ) > ✏ do ⌧t = 2 t+3 ; ⌧t = 2 t+3 ; (µt+1 1 , xt+1 , yt+1 ) = Step(µt1 , µt2 , xt , yt , ⌧) ## while ✏sad(zt ) > ✏ do if t is even then if t is even then (µt+1 1 , xt+1 , yt+1 ) = Step(µt1 , µt2 , xt , yt , ⌧) else(µt+1 2 , yt+1 , xt+1 ) = Step(µt2 , µt1 , yt , xt , ⌧) t = t + 1; else(µt+1 2 , yt+1 , xt+1 ) = Step(µt2 , µt1 , yt , xt , ⌧) t = t + 1; ## ALGORITHM 2: Step ## ALGORITHM 2: Step input : µ1, µ2, x, y, ⌧ input : µ1, µ2, x, y, ⌧ output: µ+1 , x+, y+ ˆx = (1- ⌧) x+ ⌧xµ1 (y), y+ = (1- ⌧) y + ⌧yµ2 (ˆx); ˜x = Proxxµ1 (y) ⇣ ⌧ (1-⌧ )µ1 rfµ2 (ˆx)⌘; output: µ+1 , x+, y+ ˆx = (1- ⌧) x+ ⌧xµ1 (y), y+ = (1- ⌧) y + ⌧yµ2 (ˆx); ˜x =rd⇤X ⇣rdX(xµ1 (y)) - ⌧ (1-⌧ )µ1 rfµ2 (ˆx)⌘; x+ = (1 - ⌧ ) x + ⌧ ˜x; µ+1 = (1- ⌧)µ1; x+ = (1 - ⌧ ) x + ⌧ ˜x; µ+1 = (1- ⌧)µ1; The EGT algorithm alternates between taking steps focused on X and Y. Algorithm 2 shows a single step focused on 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 µ1, µ2 in the EGT algorithm satisfy µ1 = 'X The EGT algorithm alternates between taking steps focused on X and Y. Algorithm 2 shows a single step focused on X. Steps focused on y are analogous. Algorithm 1 shows how the alternating steps and stepsizes are computed, as well as how initial points are selected. Suppose the initial values µ1, µ2 in EGT satisfy µ1 = 'X L1(fµ2 ) . Then, at every iteration t ≥ 1 of EGT, the correzt = [xt ; yt ] satisfies xt ∈ X, yt ∈ Y, and max y∈Y (xt )T Ay - min x∈X xT Ayt = ϵsad(zt ) ≤ 4‖A‖ T + 1 √ ΩXΩY ϕX ϕY . Consequently, EGT has a convergence rate of O( 1ϵ ) [Nesterov, 2005a]. terov, 2005a]. Definition 4. Treeplexes are defined recursively: L1(fµ2 ) . Then, at every iteration t ≥ 1 of the EGT algorithm, the corresponding solution zt = [xt ; yt ] satisfies xt 2 X, yt 2 Y, and f(xt ) - φ(yt ) = ✏sad(zt )  4kAk T + 1 s ⌦X⌦Y 'X 'Y . sponding solution zt = [xt ; yt ] satisfies xt 2 X, yt 2 Y, and max y2Y (xt )T Ay - min x2X xT Ayt = ✏sad(zt )  4kAk T + 1 s ⌦X⌦Y 'X 'Y . Consequently, EGT has a convergence rate of O( 1⇠ ) [Nes2.3 Treeplexes Hoda et al. [2010] introduce the treeplex, a class of convex polytopes that captures the sequence-form of the strategy spaces in perfect-recall EFGs. Consequently, [Nesterov, 2005a] proves that the EGT algorithm has a convergence rate of O( 1⇠ ). 2.3 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. Definition 4. Treeplexes are defined recursively: 2.3 Treeplexes Hoda et al. [2010] introduce the treeplex, a class of convex polytopes that captures the sequence-form of the strategy spaces in perfect-recall EFGs. Definition 4. Treeplexes are defined recursively: 1. Basic sets: The standard simplex ∆m is a treeplex. 1. Basic sets: The standard simplex ∆m is a treeplex. 2. Cartesian product: If Q1, . . . ,Qk are treeplexes, then Q1 × · · · ×Qk is a treeplex. 3. Branching: Given a treeplex P ⊆ [0, 1]p , a collection of treeplexes Q = {Q1, . . . , Qk} where Qj ⊆ [0, 1]nj , and l = {l1, . . . , lk} ⊆ {1, . . . , p}, the set defined by 3. Branching: Given a treeplex P ✓ [0, 1]p , a collection of treeplexes Q = {Q1, . . . , Qk} where Qj ✓ [0, 1]nj , and l = {l1, . . . , lk} ✓ {1, . . . , p}, the set defined by treeplexes Q = {Q1, . . . , Qk} where Qj ✓ [0, 1]nj , and is a treeplex. We say xlj is the branching variable for the treeplex Qj . 1. Basic sets: The standard simplex ∆m is a treeplex. 2. Cartesian product: If Q1, . . . ,Qk are treeplexes, then Q1 ⇥ · · · ⇥Qk is a treeplex. 2. Cartesian product: If Q1, . . . ,Qk are treeplexes, then Q1 ⇥ · · · ⇥Qk is a treeplex. 3. Branching: Given a treeplex P ✓ [0, 1]p , a collection of P l Q := {(x, y1, . . . , yk) ∈ Rp+∑j nj : x ∈ P, y1 ∈ xl1 · Q1, . . . , yk ∈ xlk · Qk } P l Q := n(x, y1, . . . , yk) 2 Rp+Pj nj : x 2 P, y1 2 xl1 · Q1, . . . , yk 2 xlk · Qk o For a treeplex Q, we denote by SQ the index set of the set of simplexes contained in Q (in an EFG SQ is the set of information sets belonging to the player). For each j ∈ SQ, the treeplex rooted at the j-th simplex ∆j is referred to as Qj. Given vector q ∈ Q and simplex ∆j , we let Ij denote the set of indices of q that correspond to the variables in ∆j and define qj to be the subvector of q corresponding to the variables in Ij. For each simplex ∆j and branch i ∈ Ij, the set Dij represents the set of indices of simplexes reached immediately after ∆j by taking branch i (in an EFG, Dij is the set Several FOMs with attractive convergence properties have been introduced for BSPPs [Nesterov, 2005b; 2005a; Nemirovski, 2004; Chambolle and Pock, 2011]. These methods rely on having some appropriate distance measure over X and Y, called a distance-generating function (DGF). Generally, FOMs use the DGF to choose steps: given a gradient and a scalar stepsize, a FOM moves in the negative gradient direction by finding the point that minimizes the sum of the gradient and of the DGF evaluated at the new point. In other words, the next step can be found by solving a regularized optimization problem, where long gradient steps are discouraged by the DGF. For EGT on EFGs, the DGF can be interpreted as a smoothing function applied to the best-response problems faced by the players. 2.2 Bilinear Saddle-Point Problems and the Sequence Form It is well-known that the strategy spaces of an extensiveform game can be transformed into convex polytopes that allow a bilinear saddle-point formulation (BSPP) of the Nash equilibrium problem as follows [Romanovskii, 1962; von Stengel, 1996; Koller et al., 1996] min x2X max y2Y hx, Ayi = max y2Y min x2X hx, Ayi. (1) Our approach for computing equilibrium refinements will be based on constructing a perturbed variant of X and Y. Given a BSPP, several first-order methods with attractive convergence properties have been introduced [Nesterov, 2005b; 2005a; Nemirovski, 2004; Chambolle and Pock, 2011]. However, these methods all rely on having some appropriate distance measure over X and Y, called a distancevon Stengel, 1996; Koller et al., 1996]. min x2X max y2Y hx, Ayi = max y2Y min x2X hx, Ayi (1) Our approach for computing equilibrium refinements will be based on constructing a perturbed variant of X and Y. Several first-order methods with attractive convergence properties have been introduced for BSPPs [Nesterov, 2005b; 2005a; Nemirovski, 2004; Chambolle and Pock, 2011]. However, these methods all rely on having some appropriate distance measure over X and Y, called a distance-generating function. Generally, FOMs use the DGF to choose steps: given a gradient and a scalar stepsize, a FOM moves in the negative gradient direction by finding the point that minimizes the sum of the gradient and of the DGF evaluated at the new point. For EGT on EFGs, the DGF can be interpreted as a smoothing function applied to the best-response problems Given a twice differentiable function f , we let ∇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: lus ' w.r.t. k·k: 8x0 , x00 2 X ◦ : hd0 (x0 ) -d0 (x00 ), x0 -x00 i ≥ 'kx0 -x00 k2 . (2) Distance-generating functions for Y are defined analogously. analogously. Given a twice differentiable function f , we let r2 f(z) denote its Hessian at z. Our analysis is based on the following sufficient condition for strong convexity of a twice differentiable function: Definition 3. A distance-generating function for X is a function d(x) : X → R which is convex and continuous on X, admits continuous selection of subgradients on the set X ◦ = {x ∈ X : ∂d(x) ̸= ∅}, and is strongly convex modulus ϕ w.r.t. ‖·‖. Distance-generating functions for Y are defined analogously. generating function . Definition 3. A distance-generating function for X is a function d(x) : X ! R which is convex and continuous on X, admits continuous selection of subgradients on the set X ◦ = {x 2 X : @d(x) 6= ;}, and is strongly convex modufaced by the players. Definition 3. A distance-generating function for X is a function d(x) : X ! R which is convex and continuous on X, admits continuous selection of subgradients on the set X ◦ = {x 2 X : @d(x) 6= ;}, and is strongly convex modulus ' w.r.t. k·k. Distance-generating functions for Y are defined Fact 1. A twice-differentiable function f is strongly convex with modulus ϕ with respect to a norm ‖·‖ on nonempty convex set C ⊂ Rn if h⊤∇2 f(z)h ≥ ϕ‖h‖, ∀h ∈ Rn , z ∈ C ◦ . Given a twice differentiable function f , we let r2 f(z) denote its Hessian at z. Our analysis is based on the following sufficient condition for strong convexity of a twice differentiable function: Fact 1. A twice-differentiable function f is strongly convex with modulus ' with respect to a norm k·k on nonempty convex set C ⇢ Rn if h>r2 f(z)h ≥ 'khk, 8h 2 Rn , z 2 C ◦ . fµy (x) = max y∈Y 〈x, Ay〉 - µY dY , (2) Given DGFs dX , dY for X , Y with strong convexity modulus 'X , 'Y , we now describe EGT [Nesterov, 2005a] applied to (1). EGT forms two smoothed functions using the DGFs fµy (x) = max y2Y hx, Ayi - µY dY , (2) Given DGFs dX , dY for X , Y with strong convexity moduli ϕX and ϕY respectively, we now describe the Excessive Gap Technique (EGT) [Nesterov, 2005a] applied to (1). EGT forms two smoothed functions using the DGFs Fact 1. A twice-differentiable function f is strongly convex with modulus ' with respect to a norm k·k on nonempty convex set C ⇢ Rn if h>r2 f(z)h ≥ 'khk, 8h 2 Rn , z 2 C ◦ . Given DGFs dX , dY for X , Y with strong convexity moduli 'X and 'Y respectively, we now describe the Excessive Gap Technique (EGT) [Nesterov, 2005a] applied to (1). EGT forms two smoothed functions using the DGFs ∇fµ2 (x) = a1 +Ayµ2 (x), ∇φµ1 (y) = a2 +A⊤xµ1 (y), These functions are smoothed approximations to the optimization problem faced by the x and y player, respectively. The scalars µ1, µ2 > 0 are smoothness parameters denoting the amount of smoothing applied. Let yµ2 (x) and xµ1 (y) refer to the y and x values attaining the optima in (2) and (3). These can be thought of as smoothed best responses. Nesterov [2005b] shows that the gradients of the functions fµ2 (x) and φµ1 (y) exist and are Lipschitz continuous. The gradient operators and Lipschitz constants are given as follows φµx (y) = min x2X hx, Ayi + µX dX . (4) These functions are smoothed approximations to the optimization problem faced by the x and y player respectively. The scalars µ1, µ2 > 0 are smoothness parameters denoting the amount of smoothing applied. Let yµ2 (x) and xµ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 [Nesterov, 2005b] shows that the gradients of the functions fµ2 (x) and φµ1 (y) exist and are Lipschitz continuous. The gradient operators and Lipschitz constants are given as These functions are smoothed approximations to the optimization problem faced by the x and y player, respectively. The scalars µ1, µ2 > 0 are smoothness parameters denoting the amount of smoothing applied. Let yµ2 (x) and xµ1 (y) refer to the y and x values attaining the optima in (2) and (3). These can be thought of as smoothed best responses. Nesterov [2005b] shows that the gradients of the functions fµ2 (x) and φµ1 (y) exist and are Lipschitz continuous. The gradient operators and Lipschitz constants are given as follows rfµ2 (x) = a1 +Ayµ2 (x), rφµ1 (y) = a2 +A>xµ1 (y), L1 (fµ2 ) = kAk2 and L2 (φµ1 ) = kAk2 . ϕY µ2 ϕX µ1 Let the convex conjugate of d : Q → R be denoted by d∗ (q) = maxq∈Q gT q - d(q). Based on this setup, we formally state EGT [Nesterov, 2005a] as Algorithm 1. L1 (fµ2 ) = kAk2 'Y µ2 and L2 (φµ1 ) = kAk2 'X µ1 . Let d⇤ denote the convex conjugate of d. Based on this setup, we formally state EGT [Nesterov, 2005a] in Algo- The EGT algorithm alternates between taking steps focused on X and Y. Algorithm 2 shows a single step focused on X. Steps focused on y are analogous. Algorithm 1 shows how the alternating steps and stepsizes are computed, as well as how initial points are selected. rithm 1. Suppose the initial values µ1, µ2 satisfy µ1 = ϕX L1(fµ2 ) . Then, at every iteration t ≥ 1 of EGT, the corresponding solution of potential next-step information sets for the player). Given a vector q ∈ Q, simplex ∆j , and index i ∈ Ij , each child simplex ∆k for every k ∈ Dij is scaled by qi. For a given simplex ∆j , we let pj denote the index in q of the parent branching variable qpj scaling ∆j . We use the convention that qpj = 1 if Q is such that no branching operation precedes ∆j . For each j ∈ SQ, dj is the maximum depth of the treeplex rooted at ∆j , that is, the maximum number of simplexes reachable through a series of branching operations at ∆j . Then dQ gives the depth of Q. We use bjQ to identify the number of branching operations preceding the j-th simplex in Q. We say that a simplex j such that bjQ = 0 is a root simplex. Our analysis requires a measure of the size of a treeplex Q. Thus, we define MQ := maxq∈Q‖q‖1. In the context of EFGs, suppose Q encodes player 1's strategy space; then MQ 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 Intuitively, MQ,r gives the maximum value of the ℓ1 norm of any vector q ∈ Q after removing the variables corresponding to simplexes that are not within r branching operations of the root of Q. We let Qξ refer to a ξ-perturbed variant of a treeplex Q, for the perturbed game Γξ. Qξ is the intersection of Q with the set of constraints qj ≥ ξqpj for all j ∈ SQ. By constructing perturbed polytopes X ξ , Y ξ and using these rather than X , Y in (1), we get an approximate variant of EFPEs. ## 3 Distance-Generating Functions for the ξ-Perturbed Game Let ds be a DGF for the n-dimensional simplex ∆n. We construct a DGF for Q by dilating ds for each simplex in SQ and take their sum: d(q) = ∑j∈SQ βjqpj ds( qj qpj ). This class of DGFs for treeplexes was introduced by Hoda et. al. [2010] and has been further studied by Kroer et. al. [2015; 2017]. We show that ds and d can be used to implement a smoothing function for Qξ and reason about its properties. To construct a smoothing function for Qξ , we first construct a smoothing function for an ξ-perturbed simplex ∆ξn = {qs : ‖qs ‖1= 1, qs ≥ ξ}, with ξ > 0. We construct a smoothing function for ∆ξn by composing ds with a simple affine mapping φ(˜ qs ) = ˜ qs-ξ 1-nξ , which sets up a one-to-one mapping between ∆n and ∆ξn . The inverse of this function is φ-1 (qs ) = (1 - nξ)qs + ξ. We let dξs = ds(φ(˜ qs )). We will show that dξs retains all nice DGF properties of ds. Since ds is continuously differentiable, we can apply the chain rule to get For our new DGF to be practical we need the conjugate and its gradient to be easily computable. We show that this reduces to a simple transformation of the conjugate of ds: Lemma 1. For a simplex DGF ds and its ξ-perturbed variant dξs , the convex conjugate and its gradient for dξs can be computed as Proof. Follows by the definition of conjugate and the chain rule for gradients. Thus computing our conjugate reduces to computing the conjugate for ds coupled with simple linear transformations. Hoda et. al. [2010] showed that the conjugate for a treeplex based on a sum over dilated simplex DGFs is easy to compute. Combined with Lemma 1, their result shows that the conjugate of a treeplex DGF consisting of a sum over dilated perturbed simplex DGFs is easy to compute, as long as the same holds for the individual conjugates. We now focus on the case where ds is the entropy DGF for a simplex, that is, ds(qs ) = ∑i qs i log(qs i ). Formally, we get the following DGF for a perturbed treeplex: Kroer et. al. [2017] showed strong convexity and convergence results for the class of dilated entropy functions for treeplexes. We now show how their result can be leveraged to prove strong convexity bounds for the perturbed entropy DGF. Theorem 2. The dilated perturbed entropy DGF on a treeplex with weights that satisfy the following recurrence is strongly convex modulus 1 with respect to the ℓ2 norm and modulus 1 MQ with respect to the ℓ1 norm. Proof. We will show that the quadratic over the Hessian of dξQ can be expressed as a constant times the quadratic over the unperturbed dilated entropy DGF for Q. This will allow us to invoke the strong convexity theorem of Kroer et. al. [2017]. Consider q ∈ ri (Qξ ) and any h ∈ Rn . For each j ∈ SQ and i ∈ Ij, the second-order partial derivates of dξQ(·) with respect to qi are: Also, for each j ∈ SQ, i ∈ Ij, the second-order partial derivates with respect to qi, qpj are given by: Then equations (6) and (7) together imply Given j ∈ SQ and i ∈ Ij, we have pk = i for each k ∈ Dij and for any k ∈ Dij , there exists some other j ′ ∈ SQ corresponding to k in the outermost summation. Then we can rearrange the following terms: Using this equality in (8) leads to Now we can view the three terms inside the brackets as a convex function of hi. First-order optimality implies that this function is nonnegative. Furthermore, since qi ≥ ξqpj we have qi qi-ξqpj ≥ 1. Combined, this gives The last step follows because qi qpj form simplex weights. By Lemma 1 in Kroer et. al. [2017] this is exactly the expression for the quadratic of the Hessian of the unperturbed dilated entropy function on Q with weights βj. Since our weights satisfy the requirements in Theorems 1 and 2 of Kroer et. al., the unperturbed dilated entropy function with these weights is strongly convex on Q, and thus we get (10) ≥ c‖h‖2 where c = 1 when ‖·‖ is the l2 norm (by Theorem 1 of Kroer et. al.) and c = 1 MQ when ‖·‖ is the l1 norm (by Theorem 2 of Kroer et. al.). By Fact 1 this proves our theorem. Using Theorem 2 we can use the perturbed dilated entropy function to instantiate EGT. Since the value of the perturbed entropy on ∆ξn can be lower-bounded by log(n) exactly the same way as with the unperturbed entropy, we can apply Theorem 3 of Kroer et. al. [2017], to bound EGT convergence rate as follows: Theorem 3. For a perturbed treeplex Qξ , the dilated perturbed entropy function with simplex weights βj = MQ(2 + ∑dj r=1 2r (MQj,r - 1)) for each j ∈ SQ results in Ωϕ ≤ M 2Q2dQ+2 logmwhere m is the dimension of the largest simplex ∆j for j ∈ SQ in the treeplex structure. Theorem 3 immediately leads to the following convergence rate result for EGT equipped with dilated perturbed entropy DGFs to solve perturbed EFGs. Theorem 4. The EGT algorithm equipped with the dilated perturbed entropy DGF with weights βj = 2 + ∑dj r=1 2r (MXj,r - 1) for all j ∈ SX and the corresponding setup for Y will return a ϵ-accurate solution to the perturbed variant of (1) in at most the following number of iterations: where the matrix norm is given by: To our knowledge, this is the first result for FOMs that compute an approximate Nash equilibrium refinement. ## 4 Experiments We conducted experiments to investigate the practical performance of our smoothing approach when used to instantiate the EGT algorithm. We compare EGT with our smoothing approach to EGT on an unperturbed polytope using the smoothing technique by Kroer et. al. [2017] and CFR+ [Tammelin et al., 2015]. We conducted the experiments on Leduc hold'em poker [Southey et al., 2005], a widely-used benchmark in the imperfect-information game-solving community, except we tested on a larger variant of the game in order to better test scalability. In our enlarged version, Leduc 5, the deck consists of 5 pairs of cards 1 . . . 5, for a total deck size of 10. 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 that both players have the same private card, they draw and split the pot. Kroer et. al. [2017] point out that the theoretically sound scale at which the overall weight on the DGF should be set is too conservative. We tune an overall weight on each DGF by choosing the weight that performs best with EGT and ξ = 0 among 1, 0.1, 0.05, 0.01, 0.005 on the first 20 iterations. We test our approach on ξ-perturbed polytopes of the strategy spaces for ξ ∈ {0.1, 0.05, 0.01, 0.005, 0.001}. The first experiment measures convergence to Nash equilibrium (Figure 2). The x-axis shows the number of tree ✏-approximation of NE in Γ0 100 10-1 10-2 10-3 10-4 Figure 2: Regret as a function of the number of iterations for EGT with various ⇠ perturbations (denoted in parentheses) and CFR+. The y-axis is on a log scale. Figure 2: Regret as a function of the number of iterations for EGT with various ⇠ perturbations (denoted in parentheses) and CFR+. The y-axis is on a log scale. Figure 2: Regret as a function of the number of iterations for EGT with various ξ perturbations (denoted in parentheses) and CFR+. Both axes are on a log scale. Figure 2: Regret as a function of the number of iterations for EGT with various ⇠ perturbations (denoted in parentheses) and CFR+. The y-axis is on a log scale. ![Image](https://ijcai.org/proceedings/2017/fulltext/42/image_000001_96161f935c4c14212cf4a60616e2904cb1a4923103dddd30e6c0044463dc096b.png) ![Image](https://ijcai.org/proceedings/2017/fulltext/42/image_000002_cfd8fb419292e53f72e6babbdd59dcdc297f87ee8f4c781c6ea8d3e6496b0c9e.png) traversals performed per algorithm. The y-axis shows the sum of player regrets in the full (unperturbed) game. We find that the ⇠ perturbations have almost no effect on overall convergence rate until convergence within the perturbed polytope, at which point the regret in the unperturbed game stops decreasing, as expected. This shows that our approach can be utilized in practice: there is no substantial loss of convergence rate. Later in the run once the perturbed algorithms have bottomed out, there is a tradeoff between exploitability in the full game and refinement (i.e., better performance in low-probability information sets). player regrets in the full (unperturbed) game. We find that the ⇠ perturbations have almost no effect on overall convergence rate until convergence within the perturbed polytope, at which point the regret in the unperturbed game stops decreasing, as expected. This shows that our approach can be utilized in practice: there is no substantial loss of convergence rate. Later in the run once the perturbed algorithms have bottomed out, there is a tradeoff between exploitability in the full game and refinement (i.e., better performance in low-probability information sets). The second experiment shows a measure of refinement convergence (Figure 3). The x-axis shows the number of traversals performed per algorithm 1 . The y-axis shows the sum of player regrets in the full (unperturbed) game. We find that the ξ perturbations have almost no effect on overall convergence rate until convergence within the perturbed polytope, at which point the regret in the unperturbed game stops decreasing, as expected. This shows that our approach can be utilized in practice: there is no substantial loss of convergence rate. Later in the run once the perturbed algorithms have bottomed out, there is a tradeoff between exploitability in the full game and refinement (i.e., better performance in low-probability information sets). player regrets in the full (unperturbed) game. We find that the ⇠ perturbations have almost no effect on overall convergence rate until convergence within the perturbed polytope, at which point the regret in the unperturbed game stops decreasing, as expected. This shows that our approach can be utilized in practice: there is no substantial loss of convergence rate. Later in the run once the perturbed algorithms have bottomed out, there is a tradeoff between exploitability in the full game and refinement (i.e., better performance in low-probability information sets). The second experiment shows a measure of refinement convergence (Figure 3). The x-axis shows the number of tree traversals performed per algorithm. The y-axis shows the The second experiment shows a measure of refinement convergence (Figure 3). The x-axis shows the number of tree traversals performed per algorithm. The y-axis shows the maximum regret at any individual information set. Information set regret is calculated assuming that the information set is reached with probability one and applying Bayes' rule to get a distribution over nodes at the information set; the regret is the increase in expected utility from best-responding throughout all information sets in the subtrees rooted at the information set. Both CFR+ and unperturbed EGT perform badly with respect to this measure of refinement. Both have maximum regret two orders of magnitude worse than the perturbed approach. The maximum regret one can possibly cause in an information set in Leduc 5 is 22, so CFR+ and unperturbed EGT also do poorly in that sense. In contrast to this, we find that our ⇠-perturbed solution concepts converge to a strategy with low regret at every information set. The choice of ⇠ is important: for ⇠ = 0.001, the smallest perturbation, we see that it takes a long time to converge at low-probability information sets, whereas we converge reasonably quickly for ⇠ = 0.01 or ⇠ = 0.005; for ⇠ = 0.1 and ⇠ = 0.05 the perturbations are too large, and we end up converging with relatively high regret (due to being forced to play every action with probability ⇠). Thus, within this set of experiments, ⇠ 2 [0.005, 0.01] seems to be the ideal amount of perturbation. tree traversals performed per algorithm. The y-axis shows the maximum regret at any individual information set. Information set regret is calculated assuming that the information set is reached with probability one and applying Bayes rule to get a distribution over nodes at the information set; the regret is the increase in expected utility from best-responding throughout all information sets in the subtrees rooted at the information set. Both CFR+ and unperturbed EGT perform badly with respect to this measure of refinement. Both have maximum regret two orders of magnitude worse than the perturbed approach. The maximum regret one can possibly cause in an information set in Leduc 5 is 22, so CFR+ and unperturbed EGT also do poorly in that sense. In contrast to this, we find that our ⇠-perturbed solution concepts converge to a strategy with low regret at every information set. The choice of ⇠ is important: for ⇠ = 0.001, the smallest perturbation, we see that it takes a long time to converge at low-probability information sets, whereas we converge reasonably quickly for ⇠ = 0.01 or ⇠ = 0.005; for ⇠ = 0.1 and ⇠ = 0.05 the perturbations are too large, and we end up converging with relatively high regret (due to being forced to play every action with probability ⇠). Thus, within this set of experiments, ⇠ 2 [0.005, 0.01] seems to be the ideal amount of perturbation. 5 Conclusion and future research The second experiment shows a measure of refinement convergence (Figure 3). The x-axis shows the number of tree traversals performed. The y-axis shows the maximum regret at any individual information set. Information set regret is calculated assuming that the information set is reached with probability one and applying Bayes' rule to get a distribution over nodes at the information set; the regret is the increase in expected utility from best-responding throughout all information sets in the subtrees rooted at the information set. Both CFR+ and unperturbed EGT perform badly with respect to this measure of refinement. Both have maximum regret two orders of magnitude worse than the perturbed approach. The maximum regret one can possibly cause in an information set in Leduc 5 is 22, so CFR+ and unperturbed EGT also do poorly in that sense. In contrast to this, we find that our ξperturbed solution concepts converge to a strategy with low regret at every information set. The choice of ξ is important: for ξ = 0.001, the smallest perturbation, we see that it takes a long time to converge at low-probability information sets, whereas we converge reasonably quickly for ξ = 0.01 or ξ = 0.005; for ξ = 0.1 and ξ = 0.05 the perturbations are too large, and we end up converging with relatively high regret (due to being forced to play every action with probability ξ). Thus, within this set of experiments, ξ ∈ [0.005, 0.01] seems to be the ideal amount of perturbation. maximum regret at any individual information set. Information set regret is calculated assuming that the information set is reached with probability one and applying Bayes rule to get a distribution over nodes at the information set; the regret is the increase in expected utility from best-responding throughout all information sets in the subtrees rooted at the information set. Both CFR+ and unperturbed EGT perform badly with respect to this measure of refinement. Both have maximum regret two orders of magnitude worse than the perturbed approach. The maximum regret one can possibly cause in an information set in Leduc 5 is 22, so CFR+ and unperturbed EGT also do poorly in that sense. In contrast to this, we find that our ⇠-perturbed solution concepts converge to a strategy with low regret at every information set. The choice of ⇠ is important: for ⇠ = 0.001, the smallest perturbation, we see that it takes a long time to converge at low-probability information sets, whereas we converge reasonably quickly for ⇠ = 0.01 or ⇠ = 0.005; for ⇠ = 0.1 and ⇠ = 0.05 the perturbations are too large, and we end up converging with relatively high regret (due to being forced to play every action with probability ⇠). Thus, within this set of experiments, ⇠ 2 [0.005, 0.01] seems to be the ideal amount of perturbation. 5 Conclusion and future research We studied the extension of FOMs to the computation of Nash-equilibrium refinements. We developed a smoothing We studied the extension of FOMs to the computation of Nash-equilibrium refinements. We developed a smoothing 1 Game tree traversals are equally expensive for all the algorithms studied. Treeplex traversal for each player is slower in EGT than CFR due to requiring exponentiation exp( · ), but the algorithms spend significantly less time on treeplex traversals than tree traversals, so this difference between the algorithms is insignificant. Figure 3: Maximum regret at any individual information set, as a function of the number of iterations, for standard EGT as well as with various ⇠ perturbations (denoted EGT(⇠)) and CFR+. Both axes are on a log scale. Figure 3: Maximum regret at any individual information set, as a function of the number of iterations, for standard EGT as well as with various ⇠ perturbations (denoted EGT(⇠)) and CFR+. Both axes are on a log scale. Figure 3: Maximum regret at any individual information set, as a function of the number of iterations, for standard EGT as well as with various ⇠ perturbations (denoted EGT(⇠)) and CFR+. Both axes are on a log scale. Figure 3: Maximum regret at any individual information set, as a function of the number of iterations. 5 Conclusion and future research 5 Conclusion and future research We studied the extension of FOMs to the computation of scheme based on perturbations of smoothing schemes for standard EFG solving, and proved that the convergence rate is comparable to that of solving the original game for Nash equilibrium. We performed numerical simulations on 5-card Leduc hold'em, where we showed that our approach has an overall convergence rate that is comparable to that of state-ofthe-art methods such as EGT and CFR+ for Nash equilibrium. At the same time, we showed that our approach leads to solutions that have substantially better performance in subsets of the game tree that are reached with low probability. This has benefits both in approximate Nash equilibrium finding (such approximation is necessary in practice in large games) where some probabilities are low while possibly heading toward zero in the limit, and exact Nash equilibrium computation where the low probabilities are actually zero. Our work suggests several research directions. It would be interesting to find a way to systematically decrease the ⇠- perturbations over time, so that we eventually converge to an exact Nash equilibrium in the full game. This requires at least two extensions. First, FOMs usually assume static domains, whereas this would involve a slowly expanding domain. Second, the ⇠ would need to be decreased at a rate that is simultaneously fast enough that it converges at a reasonable rate, and slow enough that we actually converge to a refinement. We showed how to compute approximate EFPE refinements using methods that scale to large games. It would be interesting to find a way to instantiate scalable methods such as FOMs or CFR+ for other equilibrium refinement concepts as well. The perturbed polytope due to Miltersen and Sørensen could be used to construct a notion of approximate QPE that would lead to an optimization setup similar to ours. However, this will require constructing a DGF for the perturbedQPE polytope, which has ⇠-perturbations on the realization plans. Our approach relied on ⇠-perturbations to the behavioral strategies, and so it is likely that a different DGF class is needed to handle approximate QPE. We studied the extension of FOMs to the computation of Nash-equilibrium refinements. We developed a smoothing scheme based on perturbations of smoothing schemes for standard EFG solving, and proved that the convergence rate is comparable to that of solving the original game for Nash equilibrium. We performed numerical simulations on 5-card Leduc hold'em, where we showed that our approach has an overall convergence rate that is comparable to that of state-ofthe-art methods such as EGT and CFR+ for Nash equilibrium. At the same time, we showed that our approach leads to solutions that have substantially better performance in subsets of the game tree that are reached with low probability. This has benefits both in approximate Nash equilibrium finding (such approximation is necessary in practice in large games) where some probabilities are low while possibly heading toward zero in the limit, and exact Nash equilibrium computation where the low probabilities are actually zero. Our work suggests several research directions. It would be interesting to find a way to systematically decrease the ⇠- perturbations over time, so that we eventually converge to an exact Nash equilibrium in the full game. This requires at least two extensions. First, FOMs usually assume static domains, whereas this would involve a slowly expanding domain. Second, the ⇠ would need to be decreased at a rate that is simultaneously fast enough that it converges at a reasonable rate, and slow enough that we actually converge to a refinement. We showed how to compute approximate EFPE refinements using methods that scale to large games. It would be interesting to find a way to instantiate scalable methods such as FOMs or CFR+ for other equilibrium refinement concepts as well. The perturbed polytope due to Miltersen and Sørensen could be used to construct a notion of approximate QPE that would lead to an optimization setup similar to ours. However, this will require constructing a DGF for the perturbedQPE polytope, which has ⇠-perturbations on the realization plans. Our approach relied on ⇠-perturbations to the behavioral strategies, and so it is likely that a different DGF class is needed to handle approximate QPE. scheme based on perturbations of smoothing schemes for standard EFG solving, and proved that the convergence rate is comparable to that of solving the original game for Nash equilibrium. We performed numerical simulations on 5-card Leduc hold'em, where we showed that our approach has an overall convergence rate that is comparable to that of state-ofthe-art methods such as EGT and CFR+ for Nash equilibrium. At the same time, we showed that our approach leads to solutions that have substantially better performance in subsets of the game tree that are reached with low probability. This has benefits both in approximate Nash equilibrium finding (such approximation is necessary in practice in large games) where some probabilities are low while possibly heading toward zero in the limit, and exact Nash equilibrium computation where the low probabilities are actually zero. Our work suggests several research directions. It would be interesting to find a way to systematically decrease the ⇠- perturbations over time, so that we eventually converge to an exact Nash equilibrium in the full game. This requires at least two extensions. First, FOMs usually assume static domains, whereas this would involve a slowly expanding domain. Second, the ⇠ would need to be decreased at a rate that is simultaneously fast enough that it converges at a reasonable rate, and slow enough that we actually converge to a refinement. We showed how to compute approximate EFPE refinements using methods that scale to large games. It would be interesting to find a way to instantiate scalable methods such as FOMs or CFR+ for other equilibrium refinement concepts as well. The perturbed polytope due to Miltersen and Sørensen could be used to construct a notion of approximate QPE that would lead to an optimization setup similar to ours. However, this will require constructing a DGF for the perturbedQPE polytope, which has ⇠-perturbations on the realization plans. Our approach relied on ⇠-perturbations to the behavioral strategies, and so it is likely that a different DGF class is needed to handle approximate QPE. Nash-equilibrium refinements. We developed a smoothing scheme based on perturbations of smoothing schemes for standard EFG solving, and proved that the convergence rate is comparable to that of solving the original game for Nash equilibrium. We performed numerical simulations where we showed that our approach has an overall convergence rate that is comparable to that of state-of-the-art Nash equilibrium methods. At the same time, we showed that our approach leads to solutions that have substantially better performance in subsets of the game tree that are reached with low probability. This has benefits both in approximate Nash equilibrium finding (such approximation is necessary in practice in large games) where some probabilities are low while possibly heading toward zero in the limit, and exact Nash equilibrium computation where the low probabilities are actually zero. Our work suggests several research directions. It would be interesting to find a way to systematically decrease the ξperturbations over time, so that we eventually converge to an exact Nash equilibrium in the full game. This requires at least two extensions. First, FOMs usually assume static domains, whereas this would involve a slowly expanding domain. Second, the ξ would need to be decreased at a rate that is simultaneously fast enough that it converges at a reasonable rate, and slow enough that we actually converge to a refinement. We showed how to compute approximate EFPE refinements using methods that scale to large games. It would be interesting to find a way to instantiate scalable methods such as FOMs or CFR+ for other equilibrium refinement concepts as well. The perturbed polytope due to Miltersen and Sørensen could be used to construct a notion of approximate QPE that would lead to an optimization setup similar to ours. However, this will require constructing a DGF for the perturbedQPE polytope, which has ξ-perturbations on the realization plans. Our approach relied on ξ-perturbations to the behavioral strategies, and so it is likely that a different DGF class is needed to handle approximate QPE. ## Acknowledgments This work was supported by NSF grants IIS-1617590, IIS1320620, IIS-1546752 and ARO award W911NF-17-1-0082. The first author is supported by a Facebook Fellowship. ## References 1. [Bowling et al., 2015] Michael Bowling, Neil Burch, Michael Jo- hanson, and Oskari Tammelin. Heads-up limit hold'em poker is solved. Science, 347(6218), January 2015. 2. [Brown and Sandholm, 2015] Noam Brown and Tuomas Sand- holm. Regret-based pruning in extensive-form games. In Pro- ceedings of the Annual Conference on Neural Information Pro- cessing Systems (NIPS), 2015. 3. [Brown and Sandholm, 2017a] N. Brown and T. Sandholm. Safe and Nested Subgame Solving for Imperfect-Information Games. ArXiv preprint arXiv:1705.02955, May 2017. 4. [Brown and Sandholm, 2017b] Noam Brown and Tuomas Sand- holm. Reduced space and faster convergence in imperfect- information games via pruning. In International Conference on Machine Learning (ICML), 2017. 5. [Brown et al., 2015] Noam Brown, Sam Ganzfried, and Tuomas Sandholm. Hierarchical abstraction, distributed equilibrium com- putation, and post-processing, with application to a champion no-limit Texas Hold'em agent. In International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 2015. 6. [Chambolle and Pock, 2011] Antonin Chambolle and Thomas Pock. A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of Mathematical Imaging and Vision, 2011. 7. [Farina and Gatti, 2017] Gabriele Farina and Nicola Gatti. Extensive-form perfect equilibrium computation in two-player games. In AAAI Conference on Artificial Intelligence (AAAI), 2017. 8. [Farina et al., 2017] Gabriele Farina, Christian Kroer, and Tuo- mas Sandholm. Regret minimization in behaviorally-constrained zero-sum games. In International Conference on Machine Learn- ing (ICML), 2017. 9. [Gilpin and Sandholm, 2007] Andrew Gilpin and Tuomas Sand- holm. Lossless abstraction of imperfect information games. Jour- nal of the ACM, 54(5), 2007. 10. [Hillas and Kohlberg, 2002] John Hillas and Elon Kohlberg. Foun- dations of strategic equilibrium. Handbook of Game Theory with Economic Applications, 2002. 11. [Hoda et al., 2010] Samid Hoda, Andrew Gilpin, Javier Peña, and Tuomas Sandholm. Smoothing techniques for computing Nash equilibria of sequential games. Mathematics of Operations Re- search, 35(2), 2010. 12. [Koller et al., 1996] Daphne Koller, Nimrod Megiddo, and Bern- hard von Stengel. Efficient computation of equilibria for exten- sive two-person games. Games and Economic Behavior, 14(2), 1996. 13. [Kroer et al., 2015] Christian Kroer, Kevin Waugh, Fatma Kılınc ¸- Karzan, and Tuomas Sandholm. Faster first-order methods for extensive-form game solving. In Proceedings of the ACM Con- ference on Economics and Computation (EC), 2015. 14. [Kroer et al., 2017] Christian Kroer, Kevin Waugh, Fatma Kilinc- Karzan, and Tuomas Sandholm. Theoretical and practical ad- vances on smoothing for extensive-form games. In Proceedings of the ACM Conference on Economics and Computation (EC), 2017. 15. [Lanctot et al., 2009] Marc Lanctot, Kevin Waugh, Martin Zinke- vich, and Michael Bowling. Monte Carlo sampling for regret minimization in extensive games. In Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS), 2009. [Miltersen and Sørensen, 2008] Peter Bro Miltersen and Troels Bjerre Sørensen. Fast algorithms for finding proper strategies in game trees. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008. 16. [Miltersen and Sørensen, 2010] Peter Bro Miltersen and Troels Bjerre Sørensen. Computing a quasi-perfect equi- librium of a two-player game. Economic Theory, 42(1), 2010. 17. [Moravčík et al., 2017] Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deep- stack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337), 2017. 18. [Nemirovski, 2004] Arkadi Nemirovski. Prox-method with rate of convergence o(1/t) for variational inequalities with lipschitz con- tinuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1), 2004. 19. [Nesterov, 2005a] Yurii Nesterov. Excessive gap technique in non- smooth convex minimization. SIAM Journal of Optimization, 16(1), 2005. 20. [Nesterov, 2005b] Yurii Nesterov. Smooth minimization of non- smooth functions. Mathematical Programming, 103, 2005. 21. [Romanovskii, 1962] I. Romanovskii. Reduction of a game with complete memory to a matrix game. Soviet Mathematics, 3, 1962. 22. [Sandholm, 2010] Tuomas Sandholm. The state of solving large incomplete-information games, and application to poker. AI Magazine, 2010. Special issue on Algorithmic Game Theory. 23. [Selten, 1975] Reinhard Selten. Reexamination of the perfectness concept for equilibrium points in extensive games. International journal of game theory, 1975. 24. [Shoham and Leyton-Brown, 2008] Yoav Shoham and Kevin Leyton-Brown. Multiagent systems: Algorithmic, game- theoretic, and logical foundations. Cambridge University Press, 2008. 25. [Southey et al., 2005] Finnegan Southey, Michael Bowling, Bryce Larson, Carmelo Piccione, Neil Burch, Darse Billings, and Chris Rayner. Bayes' bluff: Opponent modelling in poker. In Proceed- ings of the 21st Annual Conference on Uncertainty in Artificial Intelligence (UAI), July 2005. 26. [Tammelin et al., 2015] Oskari Tammelin, Neil Burch, Michael Jo- hanson, and Michael Bowling. Solving heads-up limit Texas hold'em. In Proceedings of the 24th International Joint Con- ference on Artificial Intelligence (IJCAI), 2015. 27. [van Damme, 1984] Eric van Damme. A relation between perfect equilibria in extensive form games and proper equilibria in nor- mal form games. International Journal of Game Theory, 1984. 28. [von Stengel et al., 2002] Bernhard von Stengel, Antoon Van Den Elzen, and Dolf Talman. Computing normal form perfect equilibria for extensive two-person games. Econometrica, 70(2), 2002. 29. [von Stengel, 1996] Bernhard von Stengel. Efficient computation of behavior strategies. Games and Economic Behavior, 14(2), 1996. 30. [Zinkevich et al., 2007] Martin Zinkevich, Michael Bowling, Michael Johanson, and Carmelo Piccione. Regret minimization in games with incomplete information. In Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS), 2007.