Smoothing Method for Approximate Extensive-Form Perfect Equilibrium

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.

(-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

1. 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 .
2. 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

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.