Title: LAZY-CFR: FAST AND NEAR-OPTIMAL REGRET MIN-IMIZATION FOR EXTENSIVE GAMES WITH IMPERFECT INFORMATION

Abstract: Counterfactual regret minimization (CFR) methods are effective for solving twoplayer zero-sum extensive games with imperfect information. However, the vanilla CFR has to traverse the whole game tree in each round, which is time-consuming in large-scale games. In this paper, we present Lazy-CFR, a CFR algorithm that adopts a lazy update strategy to avoid traversing the whole game tree in each round. We prove that the regret of Lazy-CFR is almost the same as the regret of the vanilla CFR and only needs to visit a small portion of the game tree. Thus, Lazy-CFR is provably faster than CFR. Empirical results consistently show that Lazy-CFR is fast in practice.

1. INTRODUCTION:

Extensive games provide a mathematical framework for modeling the sequential decision-making problems with imperfect information, which is common in economic decisions, negotiations and security. We focus on solving two-player zero-sum extensive games with imperfect information (TEGI). In a TEGI, there is an environment with uncertainty and two players on opposite sides (Koller & Megiddo, 1992) .

Counterfactual regret minimization (CFR) (Zinkevich et al., 2008) provides a state-of-the-art approach for solving TEGIs with much progress in practice (Brown & Sandholm, 2017b; Moravčík et al., 2017; Brown & Sandholm, 2019a) . Regret minimization techniques are first introduced to solve TEGIs based on the observation that minimizing the regrets of both players makes the time-averaged strategy converge to the Nash Equilibrium (NE) (Nisan et al., 2007) . CFR (Zinkevich et al., 2008) further bounds the original regret with a summation of many immediate counterfactual regrets on each information set (infoset). These immediate counterfactual regrets are defined by the counterfactual rewards and can be iteratively minimized by existing online learning algorithms, e.g., regret matching (RM) (Blackwell et al., 1956) .

A limitation of CFR is that it requires traversing the whole game tree in each round, which is timeconsuming in large-scale games due to the fact that we have to apply RM to every immediate regret in each round. Existing works on avoiding traversing the whole game tree can be mainly divided into two categories: Pruning-based CFR (Brown & Sandholm, 2015; 2017a) and Monte-Carlo CFR (MC-CFR) (Lanctot et al., 2009) . These algorithms can significantly speed up the vanilla CFR in practice. However, pruning-based algorithms may degenerate in the worst case. And the performance of MC-CFR depends on the structure of the game and the chosen online learning algorithm.

Contributions::

In this paper, we explore another approach to address the problem.

• We present an algorithm named Lazy-CFR, which exploits a lazy update technique to avoid traversing the whole game tree. Lazy-CFR divides the time horizon into segments, i.e., disjoint subsets with consecutive elements, and updates the strategy only at the beginning of each segment and keeps the strategy the same within each segment. By this way we only need to access each infoset at the beginning of each segment.

• We then extend the analysis on the regret of the vanilla CFR in (Burch, 2018) to Lazy-CFR. We show that the regret of Lazy-CFR is almost the same as that of the vanilla CFR.

Combining with the analysis on the number of updates in Lazy-CFR, we show that Lazy-CFR converges much faster than the vanilla CFR in theory, with some extra cost of memory.

• Finally, we bound the regret from below. By comparing with the regret lower bound, we show that the regret upper bounds of Lazy-CFR and the vanilla CFR are near-optimal.

We empirically evaluate Lazy-CFR, the vanilla CFR, MC-CFR (Lanctot et al., 2009) , CFR+ (Bowling et al., 2017) and MC-CFR+ on the standard benchmarks, Leduc Hold'em (Southey et al., 2005) and heads-up flop hold'em poker (Brown et al., 2019) . It is noteworthy that the same idea of Lazy-CFR can also be applied to CFR+, and we name the resulted algorithm Lazy-CFR+. The analysis on Lazy-CFR can be directly applied to Lazy-CFR+. Experiments show that Lazy-CFR and Lazy-CFR+ works well in practice as suggested by the theory.

2. NOTATIONS AND PRELIMINARIES:

We first introduce the notations and definitions of extensive games and TEGIs. Then we introduce an online learning concept of regret minimization, followed by CFR, which is based on the connection between TEGIs and regret minimization. For clarity, most important notations appeared in this work and their descriptions are listed in the look-up table in appendix A.

2.1. EXTENSIVE GAMES:

Extensive games (see Osborne & Rubinstein, 1994, pg. 200 for a formal definition) compactly model the decision-making problems with sequential interactions among multiple agents. An extensive game can be represented by a game tree H of histories, where a history is a sequence of actions in the past. Suppose that there are N players participating in an extensive game and let c denote the chance player which is usually used to model the uncertainty in the environment. Let [N ] := {1, • • • , N }.

A player function P is a mapping from H to [N ] ∪ {c} such that P (h) is the player who takes an action after h. And each player i ∈ [N ] receives a reward u i (h) ∈ [-1, 1] at a terminal history h.

Let A(h) denote the set of valid actions of P (h) after h, that is, ∀a ∈ A(h), (h, a) ∈ H. Let A = max h |A(h)|. A strategy of player i is a function σ i that assigns h a distribution over A(h) if P (h) = i. A strategy profile σ consists of the strategy for each player, that is,

σ = {σ 1 , • • • , σ N }.

We will use σ -i to refer to all the strategies in σ except σ i . And we use the pair (σ i , σ -i ) to denote the full strategy profile. In games with imperfect information, actions of other players are partially observable to player i ∈ [N ]. So for player i, some different histories may not be distinguishable. Thus, the game tree can be partitioned into disjoint information sets (infoset). Let I i denote the collection of player i's infosets. We have that two histories h, h ∈ I ∈ I i are not distinguishable to player i. Thus, σ i must assign the same distribution over actions to all histories in infoset I ∈ I i if P (I) = i. With a little abuse of notations, we let σ i (I) denote the strategy of player i on infoset I ∈ I i . It is clear that infosets of a player also form a tree, called infoset tree.

We let π σ (h) denote the probability of arriving at history h. Obviously, we can decompose π σ (h) into the product of each player's contribution, that is,

π σ (h) = [N ]∪{c} π i σ (h).

Similarly, we define π σ (I) = h∈I π σ (h) as the probability of arriving at infoset I and let π i σ (I) denote the corresponding contribution of player i. Let π -i σ (h) and π -i σ (I) denote the product of the contributions on arriving at h and I, respectively, of all players except player i.

With the above notations, a two-player zero-sum extensive game with imperfect information (TEGI) is an extensive game with N = 2 and u 1 (h) + u 2 (h) = 0 for all terminal histories.

In game theory, the solution of a game is often referred to a Nash equilibrium (NE) (Osborne & Rubinstein, 1994) . In this paper, we concern on computing an approximation of an NE, namely an -NE (Nisan et al., 2007) . With a little abuse of notations, let u i (σ) denote the expected reward of player i if all players take actions according to σ. An -NE is a strategy profile σ such that ∀i ∈ [N ], u i (σ) ≥ max σ ,i u i ((σ ,i , σ -i )) -. And the -NE in a TEGI can be efficiently computed by regret minimization; see later in this section.

2.2. REGRET MINIMIZATION:

Now we introduce regret, a core concept in online learning (Cesa-Bianchi & Lugosi, 2006) . Many powerful online learning algorithms can be framed as minimizing some kinds of regret, therefore known as regret minimization algorithms. Generally, the regret is defined as follows: Definition 1 (Regret). Consider the case where a player takes actions repeatedly. At each round, the player selects an action w t ∈ Σ, where Σ is the set of valid actions. At the same time, the environment selects a reward function f t . Then, the overall reward of the player is T t=1 f t (w t ), and the regret is defined as

R T = max w ∈Σ T t=1 f t (w ) - T t=1 f t (w t ).

One important example of online learning is online linear optimization (OLO) in which f t is a linear function. If Σ is the set of distributions over some discrete set, an OLO can be solved by standard regret minimization algorithms, e.g., regret matching (RM) (Blackwell et al., 1956; Abernethy et al., 2011) or AdaHedge (Freund & Schapire, 1997) . As CFR employs RM or AdaHedge as a sub-procedure, we summarize them as follows: Definition 2 (Online linear optimization (OLO), regret matching (RM) and AdaHedge). Consider the online learning problem with linear rewards. In each round t, an agent plays a mixed strategy w t ∈ ∆(A), where ∆(A) is the set of distributions, while an adversary selects a vector c t ∈ R |A| . The reward of the agent at this round is w t , c t where •, • denotes the operator of inner product. The goal of the agent is to minimize the regret: R olo T = max w∈∆(A)

EQUATION

a ) > 0, and w t+1 (a) =1 |A| otherwise. According to the result in (Blackwell et al., 1956) , RM has the following regret bound: 1

EQUATION

Let s t (a) = exp(-η t t t =1 c t (a)), AdaHedge picks w t (a) = s t (a)/( a s t (a )), where η t is the learning rate that can be tuned adaptively (De Rooij et al., 2014) . According to (De Rooij et al., 2014) , Adahedge has the regret bound R olo T ≤ O log |A| T t=1 max a∈A c2 t (a) .

2.3. COUNTERFACTUAL REGRET MINIMIZATION (CFR):

CFR is developed on a connection between -NE and regret minimization. This connection is naturally established by considering repeatedly playing a TEGI as an online learning problem. It is worthy to note that there are two online learning problems in a TEGI, one for each player.

Suppose player i takes σ i t at time step t and let σ t = (σ 1 t , σ 2 t ). Consider the online learning problem for player i by setting w t := σ i t and

f i t (σ i ) := u i ((σ i , σ -i t )). The regret for player i is R i T := max σ i R i T (σ i ), where R i T (σ i ) := T t=1 u i ((σ i , σ -i t )) - T t=1 u i ((σ i t , σ -i t )

). Furthermore, consider the time-averaged strategy σi T (I) := t π i σ t (I)σ i t (I) t π i σ t (I) . Then, it is well-known that : Lemma 1 ( (Nisan et al., 2007) 

). If ∀i, 1 T R i T ≤ /2, then (σ 1 T , σ2 T ) is an -NE.

Specifically, let σ| I→σ (I) denote the strategy generated by modifying σ(I) to σ (I) and u i (σ, I) denote the reward of player i conditioned on arriving at the infoset I if the strategy σ is executed. (Zinkevich et al., 2008) decomposes the regret R i T into the summation of immediate regrets as 2 :

EQUATION

Further, (Zinkevich et al., 2008) upper bounds Eq. ( 2) by the counterfactual regret:

EQUATION

For convenience, we call π -i σt (I)u i (σ t | I→a , I) the counterfactual reward of action a at round t. Notice that Eq. (3) essentially decomposes the regret of a TEGI into O(|I|) OLOs. So that, in each round, we can apply RM directly to each individual OLO to minimize the counterfactual regret. And the original regret max σ R i T (σ) is also minimized since the counterfactual regret is an upper bound.

3. LAZY-CFR: A LAZY UPDATE ALGORITHM FOR TEGIS:

The above CFR procedure that applies RM to solve each OLO has to traverse the whole game tree, which is very time-consuming in large scale games. In this section, we present Lazy-CFR, an efficient CFR algorithm with a lazy update strategy based on the insight that updating the strategy on every infoset is not indispensable. Intuitively, this is because the regret is determined by the norm of the vector of counterfactual reward on each node (see Eq. ( 1)); and on most nodes, the corresponding norm is very small, since π -i σt is a probability (see Eq. ( 3)), thereby can be updated in a lazy manner.

3.1. LAZY UPDATE FOR OLOS:

Figure 1 : An illustration on RM with lazy update for OLOs. On the top is the standard RM; on the bottom is the RM with lazy update. Their lengths of time are 6 and 2 respectively.

We start by presenting a lazy update strategy for an OLO in Defn. 2. As illustrated in Fig. 1 , a lazy update algorithm for OLOs consists of two steps: (1) It divides the set of time steps

[T ] into n intervals, that is, {t i , t i +1, • • • , t i+1 -1} n i=1 where 1 = t 1 < t 2 • • • < t n+1 = T + 1.

(2) It updates w t at time steps t = t i for some i and keeps w t the same within each segment. That is, the OLO with T steps collapses into a new OLO with n steps and accordingly the vector selected by the adversary in the collapsed OLO at time step j is c j = tj+1-1 t=tj c t , where c t is the vector selected by the adversary in the original OLO at time step t.

Algorithm 1 Lazy-CFR Input: a constant B > 0. while t < T do for all i ∈ {1, 2} do Q = {I r } where I r is the root of the infosets tree. while Q is not empty. do Pop I from Q.

Update the strategy on I via RM.

For I ∈ γ(I), if m t (I ) ≥ B, push I into Q, i.e., Q = Q ∪ {I }. end while end for for all h ∈ H such that the strategy on some history after h has been modified. do

Update the reward vector on h. end for end while Output the time-averaged strategy.

According to the known result in Eq. ( 1), the regret of the RM with lazy update (Lazy-RM) is bounded by O( A n i=1 max a c 2 i (a)). Thus, if the segmentation rule is under a reasonable design, that is, n i=1 max a c i (a) 2 ≈ T j=1 max a c j (a) 2 , then the regrets of Lazy-RM and the vanilla RM are similar in amount. As we shall show soon, we can expect a reasonable segmentation rule in CFR.

Though Lazy-RM does not need to update the strategy at each round, a straightforward implementation of Lazy-RM still has a running time of O(AT ), which is the same as applying RM directly. This is because we have to compute ti+1 t=ti+1 c t . Fortunately, this problem can be addressed in TEGIs by exploiting the structure of the game tree (see Sec. 3.2).

3.2. LAZY-CFR:

We now use lazy update to solve TEGIs. According to Eq. ( 3), the regret minimization procedure can be divided into O(|I|) OLOs, one for each infoset. Specifically, for each infoset I ∈ I i , P (I) = i, we divide the set of time steps

[T ] into n(I) segments {t j (I), • • • , t j+1 (I) -1} n(I)

j=1 , following step Figure 2 : An illustration on how to update α. In time step t, the strategy on h 1 , h 2 , h 5 is modified with P (h 1 ), P (h 2 ), P (h 5 ) = i. β can be updated in a similar way.

(1). Let r j (I, a) =

tj+1(I)-1 t=tj (I) π -i σt (I)u i (σ t | I→a , I

) denote the summation of the counterfactual rewards over segment j, and let r j (I) = [r j (I, a)] a∈A(I) denote the vector consisting of r j (I, a). Similar to lazy update for OLOs, we only update the strategy on infoset I at t j (I). Let σ j (I) denote the strategy after the j-th update on infoset I, that is, σ t (I) := σ j (I) for t ∈ [t j (I), t j+1 (I) -1]. According to Eq. ( 1), we can bound the regret of the collapsed OLO on infoset I as R lazy

T (I) := max σ∈Σ(I) n(I) j=1 σ -σ j (I), r j (I) ≤ A n(I)

j=1 max a r 2 j (I, a). The above procedure is quite straightforward. However, as discussed above, in order to have an efficient implementation, one critical step is to define a proper segmentation rule of each OLO. Below, we present one rule for Lazy-CFR, with which we can: 1) achieve a regret similar in amount to the regret of the vanilla CFR; 2) avoid updating the whole game tree; and 3) compute r j (I) efficiently. Specifically, let τ t (I) denote the last time step we update the strategy on infoset I before time t. We have τ t (h) = τ t (I) for h ∈ I. Let m t (I) := t τ =τt(I)+1 π -i στ (I) denote the summation of reach probabilities after τ t (I), which is contributed by all players except i. Let subt(I) denote the subtree rooted at infoset I. For convenience, for I ∈ I i if P (I) = i, we call I a decision point. Let γ(I) denote the set of decision points after I such that every I in the path from I to I ∈ γ(I) is not a decision point. Formally, γ(I) is a subset of subt(I) such that ∀I ∈ γ(I), P (I ) = i and ∀I ∈ subt(I), if I is an ancestor of I ∈ γ(I), then P (I ) = i or I = I. For convenience, we suppose P (I r ) = i where I r is the infoset of the empty history. Then, our segmentation rule is defined as a procedure that updates the strategies on infosets recursively as follows: 1) We update the strategy on I r in every round; 2) For infoset I, if we update the strategy on I at time step t, the time steps from τ t (I) + 1 to t forms a segment in the Lazy-RM of I. That is, we compute r j (I) for the corresponding j and then apply RM to I; 3) after updating the strategy on infoset I, we keep on updating the strategies on the infosets from γ(I) with m t ≥ B where B > 0 is a constant.

Alg. 1 presents an outline of Lazy-CFR. We'll formally analyze its performance in Sec. 4 and now we briefly discuss why Alg. 1 converges faster than CFR. Let's tentatively assume that we can compute m t and r j efficiently (See Sec. 3.2.1 for details), then the convergence rate of Lazy-CFR depends on the total number of updates on strategy and its regret. As for the number of updates on strategy, it is obviously upper bounded by 1 B T t=1 I π -i σt (I) which is much smaller than T |I| as π -i σt (I) is probability. As for the regret, it is easy to see that in Alg. 1, m t (I) ≤ d(I)B where d(I) is the depth of I in the tree. With r j (I) 2 ≤ max t m t (I) and Eq. ( 1), we can upper bound the regret of the Lazy-RM on I by O(Bd(I) An(I)) ≤ O(Bd(I)

√:

AT ). Therefore, the overall regret, i.e., Eq. ( 2), of Lazy-CFR is O(|I|DB

AT ). This regret bound is the same to the bound of CFR in (Zinkevich et al., 2008) within a gap of DB which is usually a logarithm of |I|. In Sec. 4, we further refine this bound and show it is comparable with the best known regret bound of CFR in (Burch, 2018) .

3.2.1. IMPLEMENTATION:

As mentioned in Sec. 3.1, if we compute m t (I) and r j (I) directly, we still have to spend O(AT ) time on each infoset. In this section, we show how to efficiently implement Alg. 1 by exploiting the structure of the game tree. More specifically, we define data structures (DS) used in the computations of m t , r j and then show when and how to update them. Updating these data structures can be implemented by depth first search (DFS) and we only spend O(1) time to update the DSs on each history visited by DFS. The detailed pseudo-code is in Appx E. W.L.O.G., we consider the DSs used in Lazy-CFR for player i. First, we store u i (h|σ t ) in DS U (h) and the strategy profile in Γ(I), i.e., U (h) = u i (h|σ t ), Γ i (I) = σ i t (I) at time step t. And how to update U and Σ is standard as other CFR algorithms. Recall that our target is to compute

m t (I) = h∈I m t (h) = h∈I t t =τt(I)+1 π -i σ t (h) and r j (I, a) = h r j (h, a) = h∈I t t =τt(I)+1 π -i σ t (h)u i ((h, a)|σ t )

where (h, a) denotes the successor of h after action a. It is noteworthy that we do not need to compute m t and r j for every history in every round. Instead, we just need to make sure m t (h) and r j (h, a) can be computed efficiently when Alg. 1 visits h.

Before diving into details, we intuitively explain how to efficiently compute r j (h) and m t (h). For m t (h), suppose we have stored

τt(pa(h)) t=τt(h) π -i t (h) in some data structure α(h), then we can compute m t (h) as m t (h) = h :h∈subt(h ) α(h )Γ -i (h , h)

where Γ(h , h) denotes the probability of reaching h from h contributed by Γ -i . As for r j (h), suppose the strategy on histories in subt(h)

is never modified during [τ t (h), t], then we can compute r j (h) = m t (h)U (h) in time O(1), as U (h) is also fixed in [τ t (h), t]. In Alg. 1, it is possible that the opponent's strategy on some h ∈ subt(h) is modified during [τ t (h), t],

thus, we need more data structures to maintain the cumulative reach probability and cumulative counterfactual reward.

More specifically, we use two additional DSs α(h) and β(h, a). In α(h), we store summations of reach probabilities and we store a summation of counterfactural rewards in β(h, a). These DSs should satisfy the following properties: Property 1. In round t, α, β, α should satisfy:

1. α(h) = t1(h) t =τt(h)+1 π -i σ t (h), β(h, a) = t1(h) t =τt(h)+1 π -i σ t (h)u i ((h, a)|σ t ) and α(h) = t2(h) t =t1(h)+1 π -i σ t (h) for τ t (h) ≤ t 1 (h) ≤ t 2 (h) ≤ t.

We will introduce t 1 , t 2 soon.

2.. 1) If:

h = pa(h), then t 1 (h ) = t 2 (h); 2) If h is the root, t 2 (h) = t. So that [τ t (h), t] = h :h∈subt(h ) [t 1 (h ) + 1, t 2 (h )].

3. For all h ∈ subt(h), P (h ) = i, the strategy on h is never modified on time steps between t 1 (h) and t 2 (h). So that for t

∈ [t 1 (h), t 2 (h)] and h ∈ subt(h), π -i σ t (h, h ) = π -i Γ (h, h ).

Intuitively, t 1 (h) is the last time step that U (h) is modified and t 2 (h) is the last time step that the strategy on pa(h) is modified. Before discussing how to update these DSs, we discuss how to use them to compute m t and r j . It is easy to check that Eq. ( 4) is true with Prop. 1, we have:

m t (h) = h :h∈subt(h ) α(h )π -i Γ (h , h), r j (h, a) = β(h, a) + (m t (h) -α(h))U ((h, a)) (4)

where π -i Γ (h , h) denotes the probability from h to h contributed by -i with strategy profile Γ. We postpone the derivation of Eq. (4) to Appx. E. With the fact that m t (h) = m t (pa(h))π -i Γ (pa(h), h)+ +α(h) where pa(h) is the parent of h, computing m t only spends O(1) time on each node as when visiting h, m t (pa(h)) must have been computed in DFS.

The last challenge is how to update these DSs to satisfy the desired properties in Prop 1. Specifically, let S 1,t denote the set of histories such that if h ∈ S, the strategy on subt(h) is modified at round t and S 2,t = {h : h / ∈ S 1,t , pa(h) ∈ S 1,t }. As illustrated in Fig. 2 , we only update DSs on S t = S 1,t ∪ S 2,t as:

Update on the DSs: 1) If Γ on the infoset of h is modified, set α(h) = β(h, a) = 0; else 2) for h ∈ S t , and set α(h) = m t (h), β(h, a) = m t (h)U ((h, a)).

With above update rule, it is easy to check that if Prop 1 is true at t, then it is still true at t + 1.

Lazy-CFR+ and Lazy-LCFR: We can also apply lazy update to CFR+ (Bowling et al., 2017) and LCFR (Brown & Sandholm, 2019a) , which are improvements of CFR. To get Lazy-CFR+ and Lazy-LCFR, we only need to replace RM by the corresponding OLO solvers, and use their methods of computing time-averaged strategy as in (Bowling et al., 2017) and (Brown & Sandholm, 2019a) respectively.

4. THEORETICAL ANALYSIS:

We now present the theoretical results, starting with the regret for members of CFR with lazy update.

4.1. REGRET UPPER BOUND:

We extend the regret analysis on the vanilla CFR in (Burch, 2018) to the members of CFR with lazy update. Specifically, let ξ i (σ) =

D d=1 I:d(I)=d π i σ (I), ξ = max i,σ ξ i (σ) and η(σ) = ξ i (σ) A max I,j ( tj+1(I) t=tj (I)+1 π -i σt (I)

) which are parameters depending on the structure of the game and segmentation rule. Thm. 1 provides a regret bound for a CFR algorithm with an arbitrary segmentation rule. By applying Thm. 1, we can get the regret bound of CFR and Lazy-CFR which are comparable with Corollary 2 in (Burch, 2018) .

Theorem 1. The regret of CFR with lazy update can be bounded as

R i T (σ) ≤ O( √ T η(σ)).

Lemma 2. With RM, the regret of the vanilla CFR is bounded by O(ξ √ AT ) and the regret of Lazy-CFR is bounded by O(ξ √ DAT ).

Proof. It is easy to see that for the vanilla CFR, we have η(σ) ≤ ξ i (σ) √ A and for Lazy-CFR, we have η(σ) ≤ ξ i (σ)

AD. With Thm. 1, we get the regret bounds.

4.2. TIME AND SPACE COMPLEXITY:

With the implementation in Sec. 3.2.1 and Appx E, the running time of Lazy-CFR is bounded by

O( t |S t |). Obviously, t |S t | = O(max σ t )π -i σ (h)

. Thus, we can bound Lazy-CFR's time complexity as:

Lemma 3 (Time complexity). The time complexity of Alg. 1 is O(T max σ h π -i σ (h)).

To show how small max σ I π -i σ (I) is, we make the following mild assumption which leads to Corollary 1.

Assumption 1. 1, If P (h) = i, then P ((h, a)) = i; 2, The tree of infosets for each player is a full A-ary tree; 3, Every infoset in the tree of infosets is corresponding to n nodes in the history tree.

Corollary 1. If a TEGI satisfies Assumption 1, then ∀σ,

h∈I i π -i σ (h) = O(n |I i |).

According to Lemmas 2 3 and 1, the regret of Lazy-CFR is about O( √ D) times larger than that of CFR, whilst the running time is about O( |I|) times faster than CFR per round under Assumption 1. Thus, according to Lemmas 1, 2 and with a bit algebra calculation, we know that Alg. 1 is about O( |I|/D) times faster than the vanilla CFR to achieve the same approximation error. The improvement is significant in large scale TEGIs.

Space complexity: A potential limitation of Lazy-CFR is that its space complexity is O(|H|) as we have to store the data structures α, β, α on histories. In contrast, the space complexity is O(|I|) for some popular implementation of CFR. In heads-up flop hold'em poker (FHP) (Brown et al., 2019) , we have |H| ≈ 10 12 and |I| ≈ 10 9 . Accordingly, Lazy-CFR needs about 10 TB to store the data structures while CFR needs about 10 GB, which is still affordable in common storage systems. Note that we do not optimize the space complexity in this work. It is worth of a systematical investigation to derive an algorithm as fast as Lazy-CFR without additional memories, e.g., by designing a better segmentation rule as well as a better implementation. 

4.3. REGRET LOWER BOUND:

In the analysis of lower bound, we consider the standard adversarial setting in online learning, in which an adversary selects σ -i t and a reward function

u i t : Z → [-1, 1]

where Z is the set of terminal nodes in the infoset tree of player i. Thus, to get a lower bound, we need to explicitly construct σ -i t and u i t (I), I ∈ Z. This setting is consistent with the analysis of the regret upper bound, in which we do not make any assumption on how u i t , σ -i t changes over rounds. Intuitively, by extending the lower bound analysis of OLO (Cesa-Bianchi & Lugosi, 2006) to infoset tree structured problem, we bound Eq. 2 from below as in Thm. 2 and for the proof, see Appendix D. Theorem 2. For an algorithm A generating σ i t given the history in the past, let R i T,A denote the regret of A in the first T rounds, we have

lim A→∞ lim T →∞ min A max π -i σ t ,ut R i T ,A ξ i √ T /D log A ≥ 1.

By comparing the regret lower bound in Theorem 2 and the regret upper bounds of CFR and Lazy-CFR as in Lem 2, we can see that the regret of CFR and Lazy-CFR are both near-optimal.

5. RELATED WORK:



Monte-Carlo and pruning-based methods::

There are several variants of CFR which attempt to avoid traversing the whole game tree at each round. Monte-Carlo based CFR (MC-CFR) (Lanctot et al., 2009; Burch N, 2012) uses Monte-Carlo sampling to avoid updating the strategy on infosets with small probability of arriving at. Pruning-based variants (Brown & Sandholm, 2017a; 2015) skip the branches of the game tree if they do not affect the regret, but their performance can deteriorate to the vanilla CFR in the worst case. And dynamic thresholding (Brown et al., 2017) directly prunes the branches with small reach probabilities. In this work, we do not compare with pruning-based method (Brown & Sandholm, 2019b) since the pruning technique is orthogonal to lazy update.

Existing analyses of regret: Lanctot et al. (2009) ; Burch N (2012); Burch (2018) refined the regret upper bound of CFR. Our analysis is essentially an extension of the regret analysis on the vanilla CFR in (Burch, 2018) to other variants of CFR with lazy-update.

6. EXPERIMENT:

In this section, we empirically evaluate our algorithm against existing CFR variants. We measure the exploitability of these algorithms. The exploitability of a strategy (σ 1 , σ 2 ) can be interpreted as the approximation error to the Nash equilibrium. The exploitability is defined as max σ ,1 u 1 ((σ ,1 , σ 2 )) + max σ ,2 u 2 ((σ 1 , σ ,2 )).

Experiments are conducted on variants of two common benchmarks in imperfect-information game solving: (1) the Leduc hold'em (Southey et al., 2005) which is a simplifed version of the heads-up no-limit hold'em poker with 6 cards; and (2) heads-up flop hold'em poker (Brown et al., 2019) (FHP) which is similar to heads-up no-limit Texas hold'em poker without the last two rounds of betting.

In our experiments of Leduc Hold'em poker, we restrict players not to bid more than 6 or 8 times the big blind. The number of infosets in the generated game trees are about 40000 and 455000 for each player, respectively. We run each algorithm on each Leduc Hold'em game for 30000 seconds. In the experiments of FHP, to control the size of the game, we consider a simplified game such that in the deck, there are 2 suits and 5 cards in each suit. And we restrict players not to bid more than 7 times the big blind. The size of the game is about 10 9 . We measure algorithms by the number of nodes touched which is independent with implementation and hard-ware.

We empirically compare Lazy-(CFR,CFR+,LCFR) with existing methods, including the vanilla CFR, CFR+, LCFR, MC-(CFR,CFR+,LCFR) and MC-LCFR with negative regret-pruning (MC-LCFR-P) which was used in developing Pluribus (Brown & Sandholm, 2019b) . In our experiments, we use RM (RM+) as the OLO solver. In Lazy-(CFR,CFR+,LCFR), we set B ∈ {0.1, 1.0}. We evaluate the CFR, CFR+, LCFR variants which prunes the histories with π -i σt (h) = 0 in the recursive tree walk as they don't affect the regret. For MC-(CFR,CFR+,LCFR), we use the external-sampling scheme. In the experiments on MC-LCFR-P, we use the following parameters: we run MC-LCFR in the first 20 minutes; after that, in each iteration, we run MC-LCFR with probability 0.05 and run MC-LCFR-P with probability 0.95; in MC-LCFR-P, we prune those branches with average regret less than -2 times the big blind. Fig. 3 presents the results. We can see that the performance of Lazy-CFR(+) has a similar performance to CFR(+) on the variants of Leduc Hold'em. This is because in the experiments of CFR(+) on Leduc Hold'em, there are a large portion of histories with π -i t (h) = 0 on average. And on the larger game, Lazy-CFR(+) significantly outperforms CFR(+). The performance of Lazy-LCFR is much worse than LCFR on all games. This might be because our segmentation rule is designed for OLO with a uniform weight in each iteration. And LCFR assigns more weights on later iterations.

7. CONCLUSIONS:

In this work, we propose a new framework to develop efficient variants of CFR with an analysis shows that our algorithm is provably faster than the vanilla CFR. The final algorithm runs fast in practice, but with some extra cost on space complexity. It is worth of a systematical study to reduce the space complexity.

A THE TABLE OF NOTATIONS:

We provide a table of some important notations in our paper in this section.

Notation Explanation:

[n] the set {1, 2, • • • , n} [a, b] the set {a, a + 1, • • • , b} H

The tree of histories I Infomation set D the depth of the game tree d(I) and d(h) the depths of I and h c the chance player h history Z ⊆ H the set of leaves of the game tree (h, a)

the successor of h after action a (I, a)

the successor of I after action a I i , I I i is the infoset tree of player i and

I = I 1 ∪ I 2 P

The player function, i.e., P (h) and P (I) are the players who take actions on h I, respectively. σ i the strategy of player i; σ the strategy of all players; σ -i the strategy of all players except player i σ(h), σ(I) σ(h) = σ P (h) (h) and σ(I) = σ P (I) (I)

π σ (h), π σ (I)

the reach probability of h and I contributed by all players π i σ (h), π i σ (I) the reach probability of h and I contributed by player i π -i σ (h), π -i σ (I) the reach probability of h and I contributed by all players except i π -i (h , h) the reach probability from h to h contributed by all players except i if h ∈ subt(h ) u i (h), h ∈ Z the reward received by player i at leaf h u i (σ) the reward received by player i with strategy profile σ u i (h|σ) the reward received by player i at h with strategy profile σ σ| I→σ (I)

the strategy profile generated from σ by replacing σ(I) by σ (I) pa(h), pa(I) the parents of h and I respectively subt(h), subt(I) the subtree rooted at h and I respectively γ(I), I ∈ I i a subset of subt(I) such that for all I ∈ γ(I) then P (I ) = i; consider I ∈ subt(I), if I is an ancestor of I , then P (I ) = i a, b the inner product of vectors a and b w t the action selected by the player at time step t c t the reward vector at time step t R olo T the regret of the OLO, i.e., R olo T = max w∈∆(A) T t=1 w, c t -

T t=1 w t , c t ∆(A) the set of distributions over set A R i T (σ i ) R i T (σ i ) = T t=1 u i (σ i , σ -i t ) - T t=1 u i ((σ i t , σ -i t )) R i T the regret of player i, i.e., R i T = max σ i R i T (σ i ) σi T the time-averaged strategy with σi T (I) = T t=1 π i σ t (I)σt(I) T t=1 π i σ t (I) τ t (I), τ t (h)

the last time step we update the strategy on infoset I (history h) before time t m t (h) the sum of reach probabilities,

m t (h) = t t =τt(h)+1 π -i σ t (h) m t (I) m t (I) = h∈I m t (h) r j (h, a)

the sum of counterfactural rewards over the j-th segment of h r j (I, a) r j (I, a) = h∈I r j (h, a) U (h) data structure with U (h) = u i (h|σ t ) at time step t Σ data structure with Σ(I) = σ t (I) at time step t α, β, α data structures such that, at time step t, m t (h) = α(h)

+ h :h∈subt(h) α(h)π -i Γ (h) and r j (h, a) = β j (h, a) + U ((h, a)) h :h∈subt(h ) α(h)π -i Γ (h) ξ i (σ)

a parameter depends on the structure of the game tree with ξ i (σ) = I∈I i ,P (I)=i π i σ (I)

ξ ξ = max i,σ ξ i (σ) η(σ)

a parameter depends on the segmentation rule with η(σ) = Aξ i (σ) max I,j (

tj+1(I) t=tj (I)+1 π -i σt (I))

B DERIVATION OF REGRET BOUNDS OF RM AND ADAHEDGE:

The regret upper bound of RM and AdaHedge used in this work can be easily derived from previous works. We include their derivations only for completeness.

Derivation of Eq. (1). The standard analysis of RM in Cor 2.1 on pg. 13 in (Cesa-Bianchi & Lugosi, 2006) shows the regret of RM is bounded by:

R olo T ≤ O     T t=1 |A| a=1   |A| a =1 w t (a )c t (a ) -c t (a)   2     Obviously, we have | |A| a =1 w t (a )c t (a )| ≤ max a |c t (a)

| since w t is a vector of probability. We have:

|A| a=1   |A| a =1 w t (a )c t (a ) -c t (a)   2 ≤ a 4 max a c 2 t (a) = 4|A| max a c 2 t (a).

We finished the proof.

Derivation of the regret bound of AdaHedge. Let v t denote the variance of reward if we take a random action according to the distribution w t defined in AdaHedge. Theorem 6 in (De Rooij et al., 2014) provides a second-order bound as:

R olo T ≤ κ log |A| t v t + 4 3 log |A| + 2

where κ is a constant. It is known that for a random variable x ∈ [a, b], its variance is no more than (a -b) 2 /4. Thus, v t ≤ max a c 2 t (a). We finished the proof.

C PROOF OF THEOREM 1:

We now extend the proof of the Theorem 1 in (Burch, 2018) to CFR with lazy update. We first introduce some additional terminology. Consider B ⊆ I i , let ξ(B) = max σ -i I∈B h∈I π -i σ -i (h). Now we prove Theorem 1.

Proof. Let κ denote the constant involved in Eq. ( 1). With Eq. ( 2) and the regret bound of RM, we have

1 T R i T (σ) = 1 T t I∈I i ,P (I)=i π i σ (I)π -i σt (I)(u i (σ t | I→σ(I) , I) -u i (σ t , I)) ≤ κ I∈I i ,P (I)=i   π i σ (I) n(I) j=1 A max a (r j (I, a)) 2 /T 2  

And then apply Jensen's inequality and with some calculations, we have

1 T R i T (σ) ≤ κ I∈I i   π i σ (I) A n(I) j=1 max a r 2 j (I, a)/T 2   = κ D d=1 I ,t,d(I)=d π i σ (I )π -i σt (I ) I ,t,d(I )=d π i σ (I )π -i σt (I ) • I:d(I)=d   π i σ (I) A n(I) j=1 max a r 2 j (I, a)/T 2   = κ D d=1   I ,t,d(I )=d π i σ (I )π -i σt (I )   I:d(I)=d π i σ (I) I ,t,d(I )=d π i σ (I )π -i σt (I )   A n(I) j=1 max a r 2 j (I, a)/T 2   = κ D d=1   I ,t,d(I )=d π i σ (I )π -i σt (I )   I:d(I)=d π i σ (I) t π -i σt (I) I ,t,d(I )=d π i σ (I )π -i σt (I )   A n(I) j=1 max a r 2 j (I, a) t π -i σt (I) 2 T 2   = κ D d=1   I ,t,d(I )=d π i σ (I )π -i σt (I )   I:d(I)=d t π i σ (I)π -i σt (I) I ,t,d(I )=d π i σ (I )π -i σt (I )   A n(I) j=1 max a r 2 j (I, a) t π -i σt (I) 2 T 2   ≤ κ D d=1   I ,t,d(I )=d π i σ (I )π -i σt (I )     A I:d(I)=d t π i σ (I)π -i σt (I) I ,t,d(I )=d π i σ (I )π -i σt (I ) • n(I) j=1 max a r 2 j (I, a) t π -i σt (I) 2 T 2  

The Jensen's inequality applies here, in which we move the term of probability outside the square root into it.

= κ D d=1    A   I ,t,d(I )=d π i σ (I )π -i σt (I )   I:d(I)=d π i σ (I) n(I) j=1 max a r 2 j (I, a) t π -i σt (I)T 2    ≤ κ D d=1   A 1 T I:d(I)=d π i σ (I) n(I) j=1 max a r 2 j (I, a) T t=1 π -i σt (I)  

The last inequality utilizes the fact that I ,t,d(I )=d π i σ (I )π -i σt (I ) ≤ T as π -i σt (I)π i σ (I) is the probability of arriving at infoset I under strategy (σ i , σ -i t ) and there is at most 1 infoset been arrived at each level.

It is easy to see that max a r 2 j (I, a) ≤ ( tj+1(I) t=tj (I)+1 π -i σt (I)) 2 . With straight-forward computations, we finish the proof:

A I:d(I)=d π i σ i (I) n(I) j=1 ( tj+1(I) t=tj (I)+1 π -i σt (I)) 2 t π -i σt (I) ≤ A I:d(I)=d π i σ i (I) max j ( tj+1 t=tj (I)+1 π -i σt (I)), this is because i x 2 i i x i ≤ max i x i if x i ≥ 0, i x i > 0 ≤ A I∈I i π i σ (I) max I,j   tj+1 t=tj (I)+1 π -i σt (I)   D THE REGRET LOWER BOUND ANALYSIS

Recall that the analysis on the regret upper bound is under the standard adversarial setting in online learning, that is, it does not depend on how the opponent's strategy and the utility vary over time steps. So we here make the same adversarial assumption that there is an adversary choose both σ -i t and u i t . It is worthy to note that in our construction of the adversary, the utility function may also vary over time.

For convenience, let -i denote all the players except i, and let ζ = { σ i :

σ i = arg max σ i D d =1 I∈I i ,P (I)=i π i σ i (I)}. Let D := {I ∈ I i : ∃σ i ∈ ζ, π i σ i (I) > 0}.

It can be shown that D forms a subtree of I i . Intuitively, our construction on σ -i t and u i t can be divided into two stages:

1. For I ∈ Z, I / ∈ D, u i t (I) = -1 for all t. This enforces player i take actions on D, otherwise, it will always receive reward -1. 2. In each round t, for I ∈ D, I / ∈ Z, P (I) = i, we first generate a random variable a(I) ∼ Multinomial(1, 1 A(I) ),3 and then set σ -i t (I, a(I)) = 1, and σ -i t (I, a) = 0 for a = a(I). Intuitively, this step separates R i T into O((ξ i ) 2 ) isolated OLOs, each of which is of A actions and would be repeated for about O(T /(ξ i ) 2 ) rounds, since only one of them will be triggered on in each time step according to our construction on σ -i t . Thus, combined with the lower bound proved by (Cesa-Bianchi & Lugosi, 2006) , each OLO incurs a regret of about Ω( √ T log A/ξ i ), and we can informally provide a lower bound of Ω(

(ξ i ) 2 /ξ i √ T log A) = Ω(ξ i √ T log A), which is formally described in Theorem 2.

Before proving Theorem 2, we first address some trivial cases and show some intuitions on the way we construct the worst case of σ -i t and

u i t . Let ϕ i (σ) = I∈I i π i σ (I).

It is easy to see that ϕ i (σ) > (ξ i (σ)) 2 /D. And we are going to show that lim A→∞ lim T →∞ min A max π -i ,u R i T,A / ϕ i T log A ≥ 1. To start, we make an implicit assumption that |A(I)| ≥ 2, ∀I ∈ I i , P (I) = i. Otherwise we can merge these infosets as we have no choice but choose the only action, which contributes nothing to the regret. In addition, we assume i and -i take actions alternatively.

We now show that it is sufficient to focus on the subtree D (Note that D is a subtree rooted at I r ). By setting u t (I) = -1 for I ∈ Z and I / ∈ D, we know that player i will not take actions to go out of D. And if player -i goes out of D, this round will contribute nothing to the regret as player i will always receive reward -1.

Moreover, we assume P (pa(I)) = i, ∀I ∈ Z. Otherwise, we can merge the subtree rooted at pa(I), I ∈ Z into one single leaf node (i.e. an infoset I ∈ Z after the mergence), and P (pa(I)) = i, ∀I ∈ Z in the new merged infoset tree.

The following property will be useful in our proof. 

∈ ζ, s.t. π i σ i 0 (I) > 0. If ϕ i D (J i (I, a j )) = ϕ i D (J i (I, a k )), W.L.O.G. we assume ϕ i D (J i (I, a j )) < ϕ i D (J i (I, a k )), then ∀σ i 0 such that π i σ i 0 (I) > 0, we have ϕ i D (σ i 0 , I) =1 + a∈A(I) σ i 0 (I, a)ϕ i D (σ i 0 , J i (I, a)) ≤1 + a∈A(I) σ i 0 (I, a)ϕ i D (J i (I, a)) ≤1 + [ a∈A(I),a =aj ,a k σ i 0 (I, a)ϕ i D (J i (I r , a))] + [σ i 0 (I, a j ) + σ i 0 (I, a k )]ϕ i (J i D (I, a k ))

With the last inequality, we can construct a

(σ i 0 ) with ϕ i D ((σ i 0 ) , I r ) ≥ ϕ i D (σ i 0 , I r ) and (σ i 0 ) (I ) = σ i 0 (I ) only if I ∈ subt(I)

. Formally, we define (σ i 0 ) as:

• (σ i 0 ) (I ) = σ i 0 (I ), I / ∈ subt(I)

• (σ i 0 ) (I ) = σ i, * (I ), I ∈ subt(I), I = I • (σ i 0 ) (I, a) = σ i 0 (I, a), a = a j , a k

• (σ i 0 ) (I, a j ) = 0

• (σ i 0 ) (I, a k ) = σ i 0 (I, a j ) + σ i 0 (I, a k ) As σ i 0 ∈ ζ, ϕ i D ((σ i 0 ) , I r ) = ϕ i D (σ i 0 , I r )

, which means σ i 0 (I, a j ) = 0, due to π i σ i 0 (I) > 0. Thus,

∀σ i 0 such that π i σ i 0 (I) > 0, we have π i σ i 0 (J i (I, a j )) = 0, which means J i (I, a j ) / ∈ D (notice that if π i σ i 0 (I) = 0, π i σ i 0 (J i (I, a j )) = 0)

, that is contradict to our assumption J i (I, a j ) ∈ D. Thus

ϕ i D (J i (I, a j )) = ϕ i D (J i (I, a k )), a j , a k ∈ A D (I). Now we can show that ϕ i D (σ i , I) = ϕ i D (I)

, ∀σ i , ∀I with mathematical induction. Let D denotes the depth of D. As we assume P (pa(I)) = i, ∀I ∈ Z, P (I r ) = i if D is odd and P (I r ) = -i if D is even. We separately discuss them as follows:

• D = 1: Obviously ϕ i D (σ i , I r ) = ϕ D (I r ) = 1. • D is even: If ∀a ∈ A D (I r ), J i (I r , a) satisfies that ϕ i D (σ i , J i (I r , a)) = ϕ D (J i (I r , a)), then ϕ i D (σ i , I r ) = a∈A D (I) ϕ i D (σ i , J i (I r , a)) = a∈A D (I) ϕ i D (J i (I r , a)) =ϕ i D (I r )

Thus we get ϕ i D (σ i , I r ) = ϕ i D (I r ).

• D is odd and D = 1:

If ∀a ∈ A D (I r ), J i (I r , a) satisfies that ϕ i D (σ i , J i (I r , a)) = ϕ D (J i (I r , a)), then ∀σ i ∈ ζ , ϕ i D (σ i , I r ) =1 + a∈A D (I) σ i (I r , a)ϕ i D (σ i , J i (I r , a)) =1 + a∈A D (I) σ i (I r , a)ϕ i D (J i (I r , a)) =1 + [ a∈A D (I) σ i (I r , a)] • ϕ i D (J i (I r , a j )), ∀a j ∈ A D (I) (due to ϕ i D (I r , a j ) = ϕ i D (I r , a k ), ∀a j , a k ∈ A D (I)) =1 + ϕ i D (J i (I r , a j )) =ϕ i D (I r ) (as ∀σ i , ϕ i D (σ i , I r ) = 1 + ϕ i D (J i (I r , a)), a ∈ A D (I) is independent of σ i )

We can get ϕ i D (σ i , I r ) = ϕ i D (I r ) as well.

So ∀σ i , ∀A, ϕ i D (σ i , I r ) = ϕ i D (I r ). As ϕ i D,σ i = ϕ i D (σ i , I) = ϕ i D (I)

is independent from σ i , we finally prove this lemma.

As ϕ i D,σ i is independent of the choice of σ i , we will drop the subscript σ i , that is, we will use ϕ i D instead of ϕ i D,σ i in the following proof. Now we prove Theorem 2.

Proof. As we discussed before, it's sufficient to focus on the subtreee D, so all of the terms (e.g. the regret) in the following proof are defined on D, not I i .

For D, P (pa(I)) = i, ∀I ∈ Z, we use the following procedure to generate σ -i t and u i t for each round:

• u t (I) ∼ Bernoulli(0.5), ∀I ∈ Z.

• ∀I ∈ D, P (I) = i, we define p D (I) as:

p D (I) = [ ϕ i D (J i (I, a 1 )) a∈A D (I) ϕ i D (J i (I, a)) , • • • , ϕ i D (J i (I, a |A D (I)| )) a∈A D (I) ϕ i D (J i (I, a)) ]

Notice that this term only depends on D, so once we determine D, we can immediately get this p D (I). Each turn we first sample a(I) from Multinomial(1, p D (I)), then let σ -i t (I) = a(I).

In the following proof we denote this generating procedure as M and use the notation E M [•] as the expectation over this generating procedure.

Let n t (I), I ∈ D denotes the cumulative arriving time player i arrives at I in the first t rounds. With a little abuse of notation, we use the term R i T (I), I ∈ D to represent the regret of the subtree rooted at I in the first T turns, i.e.

R i T (I) = max σ i T t=1 u i ((σ i , σ -i t ), I) -u i ((σ i t , σ -i t ), I)), I ∈ D We will prove that lim A→∞ lim T →∞ E M R i T,alg / ϕ i D T log A 2

≥ 1, ∀ alg with mathematical induction, where R i T,alg is defined in Theorem 2. Notice that under the assumption that P (pa(I)) = i, ∀I ∈ Z, P (I r ) = i if D is odd while P (I r ) = -i if D is even. In our proof we will discuss them separately.

• D = 1: As (Auer et al., 1995; Freund & Schapire, 1997; Cesa-Bianchi & Lugosi, 2006; Dani et al., 2008) have shown, for K-arm online linear optimization problem,

lim K→∞ lim T →∞ E M R i T ,alg √ T log K 2

≥ 1, ∀ alg, which is consistent to our proposition with

ϕ i D = 1 4 .

• D is even: From the definition we can get that ϕ i D (I r ) = a∈A D (Ir) ϕ i D (J i (I r , a)).

If lim A→∞ lim T →∞ E M R i T (J i (I r , a))/ ϕ i Z (J i (Ir,a))T log A 2 ≥ 1, ∀a ∈ A D (I r ), ∀alg, then lim A→∞ lim T →∞ E M R i T,alg (I r ) ϕ i D (Ir)T log A 2 = lim A→∞ lim T →∞ a∈A D (Ir) E M R i n T (J i (Ir,a)),alg (J i (I r , a)) ϕ i D (Ir)T log A 2 = lim |A D (Ir)|→∞ a∈A D (Ir) lim A→∞ lim n T (J i (Ir,a))→∞ E M R i n T (J i (I,a)),alg (J i (I r , a)) ϕ i D (J i (Ir,a))n T (J i (Ir,a)) log A 2 × ϕ i D (J i (I r , a))n T (J i (I r , a)) ϕ i D (I r )T ≥ lim A→∞ lim T →∞ a∈A D (Ir) 1 × ϕ i D (J i (I, a)) a∈A D (Ir) ϕ i D (J i (I, a)) =1

In the first equation, we decompose the overall expected regret to the summation of regrets on subtrees. This decomposition can be derived in a similar way to that of Eq. ( 2) in Appendix C.

In the second equation we transform the limitation of T into limitation of n T (J i (I r , a)), ∀a ∈ A D (I r ). As the adversary selects action a j with probability p D (I r ) j > 0 where p D (I r ) j denotes the j-th element of p D (I r ), when T → ∞, the n T (J i (I r , a)) → ∞, ∀a ∈ A D (I r ) as well.

The inequality is from induction and lim T →∞ n T (J i (I r , a))/T = p D (I) j , a j ∈ A D (I r ) due to the strong law of large numbers.

• D is odd and D

= 1: For convenience, let R i T,alg,imm (I r ) = max a∈A D (Ir) T t=1 u t (σ t | Ir→a , I r ) -u t (σ t , I r

) denote the immediate regret on the root node for algorithm alg.

We first show that under our construction E M R i T,alg,imm (I r ) ≥ 0, ∀ alg.

Published as a conference paper at ICLR 2020 Notice that in our construction, E M T t=1 u t (σ t | Ir→a , I r ) = 0.5T, ∀a ∈ A D (I r ). Meanwhile, E M T t=1 u t (σ t , I r ) = 0.5T as well. Thus,

E M T t=1 u t (σ t , I r ) = 1 A a∈A D (Ir) E M u t (σ t | Ir→a , I r ) =E M 1 A a∈A D (Ir) u t (σ t | Ir→a , I r ) ≤E M max a∈A D (Ir) u t (σ t | Ir→a , I r )

This inequality is true for all σ t (i.e. alg), and we can get

EQUATION

Then, similar to the case when D is even, we can get: 

lim A→∞ lim T →∞ E M R i T,alg (I r ) ϕ i D (Ir)T log A 2 = lim A→∞ lim T →∞ E M [R i T,

E THE DETAILS OF IMPLEMENTATION:

We now discuss the detailed implementation of Lazy-CFR. To start, we derive Eq. ( 4). According to Property 1, we have:

m t (h) = t t =τt(h)+1 π -i σ t (h) = h :h∈subt(h ) t2(h ) t =t1(h )+1 π -i σ t (h) = h :h∈subt(h ) t2(h ) t =t1(h )+1 π -i σ t (h )π -i σ t (h , h) = h :h∈subt(h ) π -i σΓ (h , h)α(h )

The first equation is the definition of m t ; the second line is according to Prop 1.2; the third line is derived from the definition of α and π -i σ and the last line is due to Property 1.3. Similarly, we can write r j as: 

π -i σΓ (h , h)α(h )

We now present how to implement of the ideas in 3.2.1.

Algorithm 2 A detailed implementation of Lazy-CFR 1: A two-player zero-sum extensive game. 2: Randomly initialize Γ.

3: ∀h ∈ H, i ∈ {1, 2}, compute the counterfactual reward U i (h) = u i (h|Γ), f lag i (h) = -1. 4: ∀I ∈ I, s(I) = 0, ∀a ∈ A(I), r(I, a) = 0. 5: while t < T do 6:

for all i ∈ {1, 2} do 7:

α i (h r )+ = 1.0.

8::

UPDATE1(I i r , i) where I i r is the root of infoset tree I i . 9:

end for 10:

∀i ∈ {1, 2} UPDATE2(h r , i, t) where h r denotes the root of the history tree. 11: end while 12: RETURN σ.

Algorithm 3 UPDATE1(I, i, t)

1: m(I) = 0 2: for all h ∈ I do 3:

θ i (h) = (θ i (pa(h)) + αi (pa(h))) × π -i Γ (pa(h), h).

4::

m(I)+ = α i (h) + θ i (h) 5: end for 6: if m(I) ≥ 1 then end if 20: end if Algorithm 4 updflag(h, t, i) 1: if h is not the root of history tree and f lag i (h) = t then 2: f lag i (h) = t.

3::

updf lag(pa(h), t, i). 4: end if Algorithm 5 UPDATE2(h, i, t) 1: Let i denote the opponent of player i. 2: if f lag i (h) = t then 3: ∀a ∈ A(h) UPDATE2((h, a), i, t).

update U 1 (h) and U 2 (h). α i (h)+ = (θ i (pa(h)) + αi (pa(h))) × π -i Γ (pa(h), h).

10::

αi (h)+ = (θ i (pa(h)) + αi (pa(h))) × π -i Γ (pa(h), h).

11::

∀a ∈ A(h), β i (h, a)+ = U i (h, a)(θ i (pa(h)) + αi (pa(h))) × π -i Γ (pa(h), h). 12: end if

:

In this work, we use second-order bounds of RM and AdaHedge. These bounds can be easily derived from known results, and we put the derivation of them in Appendix B

(Zinkevich et al., 2008) directly upper bounded R i T by the counterfactual regret, i.e., Eq. (3), and omitted the derivation of Eq. (2). So we present the derivation of Eq. (2) in Appendix C.

This step is informal here. See later in this section for a formal construction.

(Cesa-Bianchi & Lugosi, 2006) proves that for K-arm online linear optimization problem,sup T,K maxu t ER T ,alg √ T log K/2≥ 1, however the supremum can only get with K → ∞ and T /K → ∞ as they use the property of maximum of infinite normal random variable and central limit theorem (CLT) correspondingly. Here for clarity we equivalently change supremum into limit in our proof.

Figures and Tables:

Figure 3: Convergence for Lazy-(CFR, CFR+, LCFR), MC-(CFR, CFR+, LCFR), CFR, CFR+, LCFR and MC-LCFR-P.

Let ϕ i D (σ i ) = I∈D π i σ i (I). Moreover, let ζ = {σ i : σ i (I, a) = 0, for P (I) = i, I ∈ D, (I, a) / ∈ D}. Then ∀σ i D , (σ i D ) ∈ ζ , we have that ϕ i ∈subt(I),P (I )=i π i σ i (I ), I ∈ D, where subt(I) means the subtree rooted at I (Note that it's possible that I ∈ subt(I), I / ∈ D). Let ϕ i D (I) = max σ i ϕ i D (σ i , I), and σ i, * = arg max σ i ϕ i D (σ i , I). We first show that, ∀I ∈ D, P (I) = i, ϕ i D (J i (I, a j )) = ϕ i D (J i (I, a k )), j, k ∈ |A D (I)| where A D (I) consists of a ∈ A(I) such that J i (I, a) ∈ D. With the definition of D, ∀I ∈ D, ∃σ i 0

alg,imm (I r ) + a∈A D (Ir) [R i n T (J i (Ir,a)),alg (J i (I r , a))]] a∈A D (Ir),n T (J i (Ir,a))<∞ E M R i n T (J i (Ir,a)),alg (J i (I r , a))ϕ i D (Ir)T log A 2 + lim |A D (Ir)|→∞ a∈A D (Ir),n T (J i (Ir,a))→∞ lim A→∞ lim n T (J i (Ir,a))→∞, E M R i n T (J i (Ir,a)),alg (J i (I r , a)) a∈A D (Ir),n T (J i (Ir,a))→∞ ϕ i D (J i (I r , a))n T (J i (I r , a)) ϕ i D (I r )T ≥ lim A→∞ lim T →∞ a∈A D (Ir),n T (J i (Ir,a))→∞ ϕ i D (J i (I r , a))n T (J i (I r , adecompose the overall expected regret to each subtree in the first equation.Notice that ∀ alg, limT →∞ a∈A D (Ir),n T (J i (Ir,a))<∞ E M R i n T (J i (Ir,a)),alg < ∞, lim T →∞ a∈A D (Ir),n T (J i (Ir,a))<∞ E M R i n T (J i (Ir,a)),alg / √ T = 0. Thus the second inequality is true. The last inequality is true by i √ a i ≥ i a i . Notice that a∈A D (Ir) ϕ i D (J i (I r , a))n T (J i (I r , a)) = (ϕ i D (I r ) -1)T (We can see this by n T (J i (I r , a)) = T t=1 σ i t (I r , a) and ∀t, a∈A D (Ir) ϕ i D (J i (I r , a))σ i t (I r , a) = ϕ i D (I r ) -1, which can be simply derived by the definition of ϕ i D and P (I r ) = i), and lim T →∞ a∈A D (Ir),n T (J i (Ir,a))<∞ ϕ i Z (J i (Ir,a))n T (J i (Ir,a)) ϕ i Z (Ir)T = 0. Thus we can get the limitation of T → ∞.Thus, with mathematical induction, we prove that lim T →∞,A→∞ E M D and Lemma 4, we can get ϕ i D = ϕ i , thus we can get the mini-max lower bound in Theorem 2.

, updflag(h, t, i).

for all a ∈ A(I), h ∈ I do 14: r(I, a)+ = β(h, a) + θ i (h)U i ((h, a)).

(I), UPDATE1((I,a),i, t).

(h), β i (h, a) = 0. 8: else 9:

Peer review (iclr2020):
The paper proposes an improvement to Counterfactual Regret Minimization, avoiding traversing the whole tree on each iteration. The idea is not to change the strategy in those infosets, where the reach probability of opponents is low. The strategy in such infosets is only updated once in several iterations, when the sum of reach probabilities over these iterations if higher than the threshold. The straightforward implementation of the idea still has the same running time as CFR. Therefore, the paper presents an efficient implementation, exploiting the structure of the game tree. However, this implementation comes at the cost of additional memory requirements. Overall, the paper proves the theoretical result of about O(sqrt(|I|)/D) times faster than CFR to achieve the same approximation error, while the memory requirements increase by a factor of O(|H|/|I|). Here |I| is the number of infosets, D is the depth of the game tree and |H| is the number of histories. The idea of eliminating unnecessary computations for infosets with low probability is a valuable contribution. The presented theoretical analysis takes an important place in the series of works refining the regret upper bound of CFR and its variants. The experiment confirms performance of the idea. That being said, I follow up with some questions/criticism. 1. Implementation in Section 3.2.1 and Appendix E is rather hard to follow. Is there any intuition on how the segment [	au_t(h), t] is divided, i.e. what does t_1, t_2 and 	au’(h) mean? Also, clarity could be increased if these variables would be defined before they are used. 2. How is a segmentation rule for Lazy-RM in OLO designed in such a way, that equation sum_{i=1}^n max_a c’_i(a)^2 approx sum_{j=1}^T max_a c_j(a)^2 holds? 3. Section 3.2: “following step (1)”. (1) is an equation for RM in OLO, probably some other reference was meant. 4. Recently, Linear Cfr was introduced, which outperforms Cfr+. Thus, citation is needed Brown, Noam and Sandholm, Tuomas “Solving Imperfect-Information Games via Discounted Regret Minimization”. Worth to mention, LazyCfr is straightforwardly compatible with Linear Cfr. 5. The specified space requirements significantly limit the applicability of the presented Lazy-RM implementation. For example, in state-of-art approaches to solve/resolve No-Limit Holdem (Libratus, DeepStack, Pluribus), either the game tree is too large, making the space requirements unrealistic, or the game tree is small enough for getting a good equilibrium approximation fast even with CFR+. UPD: score updated