Lazy-CFR: fast and near-optimal regret minimization for extensive games with imperfect information
Authors: Yichi Zhou
Tongzheng Ren
Jialian Li
Dong Yan
Jun Zhu
Venue:  (2020)

Abstract: Counterfactual regret minimization (CFR) methods are effective for solving two-player zero-sum extensive games with imperfect information with  state-of-the-art results.  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 to 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 significantly faster than the vanilla CFR.

Published as a conference paper at ICLR 2020
LAZY-CFR: FAST AND NEAR-OPTIMAL REGRET MIN- IMIZATION FOR EXTENSIVE GAMES WITH IMPERFECT
INFORMATION
Yichi Zhou, Tongzheng Ren, Dong Yan, Jialian Li, Jun Zhu"
Dept. of Comp. Sci. & Tech., BNRist Center, Institute for AI, Tsinghua University; RealAI (vofhqn, zt xtz19970824 sproblven @ggmall... com, 1i iijialian7811l com, dcszjetssinghua.c edu. edu.on
ABSTRACT
Counterfactual regret minimization (CFR) methods are effective for solving two- player 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, present Lazy-CFR, 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 the regret of the vanilla CFR and only needs to visit small portion of the game tree. Thus, Lazy-CFR is provably faster than CFR. Empirical results consistently show that Lazy-CFR fast in practice.
INTRODUCTION
Extensive games provide 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-ther approach for solving TEGIs with much progress in practice (Brown & Sandholm, (2016]] Moravčík al.) 2017 Brown & Sandholm, 2019a). Regret minimization techniques are first introduced to solve TEGIs based on observation that minimizing the regrets of both players makes the time-averaged strategy converge the Nash Equilibrium (NE) (Nisan al.) (007). CFR (Zinkevich et al., 2008 further bounds the original regret with a summation of many immediate counterfactual regrets on each information (infoset). These immediate counterfactual regrets defined by the counterfactual rewards and can be iteratively minimized by existing online learning algorithms, e.g., regret matching (RM) (Blackwell al. 1956).
limitation of CFR is that it requires traversing the whole game tree in each round, which is time- consuming in large-scale games due to the fact that we have apply RM every immediate regret in each round. Existing works on avoiding traversing the whole game tree can be mainly divided into two categories: Pruning-baas based CFR (Brown & Sandholm 2015 2017a) and Monte-Carlo CFR (MC-CFR) (Lanctot et al., 2009). These algorithms can sigmificanly speed up the vanilla CFR in practice. However, pruning-basse 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 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.c., 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 heginning of each segment.
"J.Z.is the corresponding author.

---

Published as a conference paper at ICLR 2020
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. (207)) and MC-CFR+ on the standard benchmarks, Leduc Hold em (Southey et al. heads-up flop hold'em 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.
2005) and
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 based on the connection between TEGls 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 Docision-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 sequence of actions in the past. Suppose that there are N players participating in an extensive game and let e denote the chance player which is usually used to model the uncertainty in the environment. Let [N] == {1. .N.. player function P is 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² (h) E [-1, at terminal history h.
Let A(h) denote the set of valid actions of P(h) after h. that is, Va E A(h). (h,a) E H. Let A = maxx [A(h)]- A strategy of player is function of that assigns h a distribution over A(h) if P(h) = i. A strategy profile a consists of the strategy for each player, that is, o = (o! ................................ .o.N We will use o to refer all the strategies in except o². And we use the pair (a',a=)) to denote the full strategy profile. In games with imperfect information, actions of other players are partially observable to player E [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' denote the collection of player i's infosets. We have that two histories h, h I I' are not distinguishable to player i. Thus, o¹ must assign the same distribution over actions to all histories in infoset E I if P(]) = i. With a little abuse of notations, we let (I) denote the strategy of player i on infoset E It is clear that infosets of a player also form tree, called infoset tree.
We let no (h) denote the probability of arriving at history h. Obviously, we can decompose No (h) into the product of each player's contribution, that is, To (h) = [[]jjt T/' (h). Similarly, we define n. (4) Σner To (h) as the probability of arriving at infoset I and let कं (4) denote the corresponding contribution of player i. Let ... ( and mT) denote the product of the contributions on arriving at h and 1, respectively, of all players except player i.
With the above notations, two-player zero-sum extensive game with imperfect information (TEGI) is an extensive game with N 2 and n² (h) + u² uh) 0 for all terminal histories.
In game theory, the solution of game is often referred to a Nash equilibrium (NE) (Osborne & Rubinstein| (994). In this paper, we concern computing approximation of an NE, namely an c-E (Nisan et al. 2007). With a little abuse of notations, let u² (a) denote the expected reward of player if all players take actions according to a. An c-NE is strategy profile such that Vi E [M], a² (a) 2 max u (('",,, o 1)) e. And the eE in a TEGI can be efficiently computed by regret minimization; see later in this section.
2

---

Published as a conference paper at ICLR 2020
2.2 REGRET MINIMIZATION
Now we introduce regret, a core concept in online learning "Cea--Bianch & Lugosi 2006). Many powerful online learning algorithms can be framed minimizing some kinds of regret, therefore known as regret minimization algorithms. Generally, the regret is defined as follows:
Definition (Regret), Consider the case where a player takes actions repeatedly. At each round, the player selects an action Wa E E. where Σ is the set of valid actions. At the same time, the environment selects reward reward function ft. Then, the overall reward of the player Σ fe(we), and the regret defined as Rr = max Et= (e(w[(((w))))))))))))()))) -i= Je(ws))
One important example of online learning online linear optimization (OLO) in which fs is linear function. If Σ is the set of distributions over some discrete set, OLO can be solved by standard regret minimization algorithms, c.g., regret matching (RM) (Blackwell et al. 1956; Abernethy et al. 2011) or AdaHedge (Freund & Schapire 1997). As CFR employs RM or AdaHedge sub-procedure we summarize them as follows:
Definition (Online linear optimization (OLO), regret matching (RM) and AdaHedge). Consider the online learning problem with linear rewards. In each round t, an agent plays mixed strategy we E (A), where ((A) is the set of distributions, while an adversary selects a vector es E IR A), The reward of the agent at this round is (wx, ca) where (:,-) denotes the operator of inner product. minimize the regret: R9p maxxEe(A) _t= (W,C,) Ca) -Et (wis Ct).
The goal of the agent
Let Helh (a) = max (0, Ets ce(a) (t=r c.), in RM, (a+ = 14 (a)) Eg Reg (a'), max.' Rogl (a') O, and We+ 1++1(a) (a) 1956). RM has the following regret bound
[ otherwise. According to the result in (Blackwell et al.
Rolo 50
A Σ max c((a)
Let sa(a) = =ex((-H Ev=r Cr((a), AdaHedge picks we w.(a) learning rate that can be tuned adaptively (De Rooij al.
8y (a / /Ed st(a"), where th is the
2014). According (ee Rooij al.
20 log |A| Σ max.e (o((
2014),
Adahedge has the regret bound Rejo S SO
2.3
COUNTERFACTUAL REGRET MINIMIZATION (CFR)
CFR is developed connection between c-NE and regret minimization. This connection is naturally established by considering repeatedly playing TEGI as an online learning problem. is worthy note that there two online learning problems in TEGI, one for each player.
Suppose player i takes of at time step & and let a: = (ol.o?). Consider the online learning problem for player i by setting wi = of and fi == u' ((a", o. o.))). The regret for player is Ry max, (at), where (a*) = Σr w² ((a',00
Σt u'(lo,, Furthermore,
= (1)0(1) Then, is well-known that consider the time-averaged strategy (1) =
E, 2,,0,01
Lemma (Nisan et al. 2007)). Vi, Ri S e/2, then (øt, o is an e-NE.
Specifically, let a (-)o((1) denote the strategy generated by modifying (I) (I() and u' (a, denote the reward of player i conditioned on arriving at the infoset I if the strategy a executed. (Zinkevich al. 2008) decomposes the regret R2 into the summation of immediate regrets as
(+) -
Σ t P()=
Ttes
u'( T))
second-order bounds of RM and AdaHedge. These hounds can be casily derived from known results, and we put the derivation them in Appendix
In this work,
(Zinkevich et al. 2008) directly upper bounded R7 by the counterfactual regret, i.c., Eq. ( and omitted
the derivation of Eq. 2 So present the derivation of Eq. (2) in Appendix C
3

---

Published as a conference paper at ICLR 2020
Further, Ziinkevich al. 2008) upper bounds Eq. 2 by the counterfactual regret:
(o)
Σ
Σ max(0, To. (z) (orl I) u' (or, ()),
P(T))(T))ii
For convenience, we call T.. (T:(()"((orl 7) the counterfactual reward of action a at round t. Notice that Eq. (3) essentially decomposes the regret of a TEGI into O(IZ) 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, (o) is also minimized since the counterfactual regret is an upper bound.
LAZY-CFR: 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. this section, we present Lazy-CFR, an efficient CFR algorithm with lazy update strategy based 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. (T): and on most nodes, the corresponding
norm is very small, since म प.. is a probability (see Eq. (3 thereby can be updated in a lazy manner.
3.1 LAZY UPDATE FOR OLOS
The original OLO
C2
C3
4
C5
C
We start by presenting lazy update strategy for an OLO in Defn. - As illustrated in Fig. [ lazy update algorithm for OLOs consists of two steps: (1) It divides the set of time steps [2'] into intervals, that is, {t,, 4 + +1,
1
1
1
Time
4
6
d2 03
4
+
cs C6
li+1 1) J==1 where
1 t < 12 ... < fn+1 = T + 1. (2) It updates Wy at time steps = I, for some i and keeps w; the same within each segment. That is, the OLO with 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 cf Ens Ct, where is the vector selected by the adversary in the original OLO at time step
The collapsed OLO with & 1,t2 3
Figure 1: An illustration on RM with lazy up- date for OLOs. On the top is the standard RM; the bottom is the RM with lazy update, Their lengths of time are 6 and 2 respectively.
According to the known result in Eq. ①.
the regret of the RM with lazy update (Lazy-
Algorithm Lazy-CFR
RM) is bounded by O(y A Ex= max, of (a)). Thus, if the segmentation rule is under a rea- sonable design, that is, Σ max, ca)) R
Input: a constant while < T do
for all E {1, do
{T,} where I, is the root of the infos-
ΣJ=1 max, (a)) then the regrets of Lazy- RM and the vanilla RM are similar in amount. As we shall show soon, we can expect a reason- able segmentation rule in CFR.
ets tree.
while Q not empty. do
Pop / from Q.
Update the strategy 1 via RM.
Though Lazy-RM does not need update the strategy at each round, a straightforward imple- mentation of Lazy-RM still has a rumning time of O(AT), which is the same applying RM directly. This is because we have to compute E Ct. Fortunately, this problem can be addressed in TEGIs by exploiting the structure of the game tree (see Sec. 3.2
For I' >(), if mi (I') 2 B, push I'
into Q, i.c. Q QU
end while end for for all h E 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 aime-ave strategy.
3.2 LAZY-CFR
We now lazy update to solve TEGIs. According Eq. 3) the regret minimization procedure can be divided into ((Z)) OLOs, one for each infoset. Specifically, for each infoset I E T', P(T) = i,
divide the set of time steps [7] into rTT) segments (T) (T)+1(T) 1)521 following step
4

---

Published as a conference paper at ICLR 2020
Histories on which I' are modified
Game tree
Historics on which a are mocified
a
(h2y
ahh)) 0
d2
a(hh))
x2
a(hz)
a(hh)) 0
21
22
a2
a (h3) X3
a (hs) =0
a(4))
a(hg) += (x1 + a2)
a(hy) == ((x, 1)) x2 (2bg(())))))
a(hs)
a(h?)
a(ha)
a(ha) a(h;)
a(ha)* + (((x; 1)r(h, a,) +xy)) (.)g + Xx3 r(hg.ag)
Time step
Time step t+1
Figure 2: An illustration on how to update a. In time step I, the strategy on hn, h2, hi is modified with P(h2), P(hs)= # i. 3 can be updated in a similar way.
(I). Let (I,, E -1100-1
Et=t(() naj (T) denote the summation of the counterfactual
rewards segment j, and let (T) [ry(T, (r3(T,a)JosAAn denote the vector consisting of (T)
Similar to lazy update for OLOs, we only update the strategy infoset at (T). Let a (1) denote
the strategy after the j-th update infoset I, that is, or (I) (I for t E [t), (f))tt+11()) 1].
According to Eq.
1 we can bound the regret of the collapsed OLO on infoset I as R (I) =
max,ex()) Σ (L() == (a-o)(0),r
V mll)
max, (2
The above procedure quite straightforward. However, discussed above, in order to have an efficient implementation, one critical step is define proper segmentation rule of each OLO. Below, we present one rule for Lazy-CFR, with which we can: 1) achieve regret similar amount to the regret of the vanilla CFR; 2) avoid updating the whole game tree; and 3) compute (7) efficiently.
Specifically, let (T) denote the last time step we update the strategy on infoset I before time t.
We have (h) = (I) for E I. Let mI) == EE T. (I) denote the summation of reach probabilities after (T), which is contributed by all players except i. Let subt( (7) denote the i, we call a decision point.
subtree rooted infoset I. For convenience, for I E I' if P(T) Let y() denote the set of decision points after I such that every I' in the path from I to I" E Y() not decision point. Formally, r()) is a subset of subl(I) such that V/' E P(T)) = and v/" E subl( if 7" is an ancestor of 1' 7!),, then P(!") & or I" I. For convenience, we suppose P(L)) = where I, is the infoset of the empty history. Then, our segmentation rule is defined procedure that updates the strategies on infosets recursively as follows: 1) We update the strategy on I, in every round; 2) For infoset J, we update the strategy on at time step f, the time steps from (T) + to t forms segment in the Lazy-RM of T. That is, compute r, (7) for the corresponding j and then apply RM to I; 3) after updating the strategy on infoset /, we keep on updating the strategies on the infosets from (() with m, 2 where B is constant.
Alg. I presents an outline of Lazy-CFR, We'll formally analyze its performance in Sec. 4 and now we briefly discuss why Alg. converges faster than CFR. Let's tentatively assume that we can compute and ry efficiently (See Sec. 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,
obviously upper bounded by $ E'=1 E, -T. (I) which much smaller than T|Z| as (Z) is probability. As for the regret, it is easy to see that in Alg. 1 m of I in the tree. With (I)]( & max; (I) and Eq. T. we can upper bound the regret of the Lazy-RM on I by ((B((T) Ann(T) s ((B((T) VAT). Therefore, the overall regret, i.e., Eq. of Lazy-CFR O(IZ) 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 [Z]. In Sec. we further refine this bound and show it is comparable with the best known regret bound of CFR in Burrch] 2018).
d(I)B where d( ((]) is the depth
5

---

Published as a conference paper at ICLR 2020
3.2.1 IMPLEMENTATION
As mentioned in Sec. 3.1 if we compute m)(1) and (1) directly, we still have to spend (AAT) time on each infoset. In this section, we show how to efficiently implement Alg. by exploiting the structure of the game tree. More specifically, we define data structures (DS) used in the computations of m.,ry 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 ((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 í. First, we store u' (hl in DS (h) and the strategy profile in I((), i.e. (hh = u'(hloz),
of( at time step t. And how to update U and is standard as other CFR algorithms. Recall that our target to compute mz(1) = Ener
= Ener E Ev=n.(T)+1 Top. (h) and ry(1,a) = = r,, a) = Ener Ei=1((++1 (h) ((h, (or) where (), denotes the successor of h after action a. It is noteworthy that we do not need to compute my and ry for every history in every round. Instead, we just need to make sure mh)h) and (y(h,a) a) can be computed efficiently when Alg. Visits h.
Before diving into details, we intuitively explain how to efficiently compute ry(h) and mi(h). For m²(h), suppose we have stored Σ Enl Te (h) in some data structure o<hh), then we can compute (h) as mh) = (hrshe (-'') h) where T(K, It) denotes the probability of reaching h from h'' contributed by r As for ry (h), suppose the strategy on histories in subl (h) is never modified during [Te (h),, 4). then we can compute ry (4)) m, (h) in time 0(1), as U U(h) also fixed in (h), f). In Alg. [ it is possible that the opponent's strategy on some h" subt(h) is modified during [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 ahh) and 3(h, a). In a(h), we store summations of reach probabilities and we store a summation of counterfactural rewards in 3(h, a). These DSs should satisfy the following properties:
Property 1. In round I, a, B, & should satisfy:
(1)) 1. a(h) = Ei=m(()) (1)+1 क (h), ((h, a) (ty(h) (x) (b)-1 (h)'' a)lor) and a(h)
Σ (1)) (k)= Top (b),for (h) S (1) S (2h) S We will introduce tı, l2 soon.
2. 1) If = (h), then L (W)) = l2(h;; 2) If h is the root, l2(h) = L. So that [Te(h), (] = wnuthernba(te)lli (1') + (1)))
(,)))
3. For all h' E subt(h), P(h)) # i, the strategy on h' is never modified on time steps between ti (h) and (h)).. So that for t' (a)),t(h)) and h' subt(h), T58 (h, h²) " (h, ' h').
Intuitively, 4 (h) is the last time step that (h) is modified and (2(h) is the last time step that the strategy on (h) is modified. Before discussing how to update these DSs, we discuss how to use them to compute my and ry. It is easy to check that Eq. (4p is true with Prop. I we have:
(h) = Σ a(H)==''
Tz(h, a) = 3(h,a) + (m,(h) aah))UU(h))) (4)
(i:hEsube(hh)
where "h'', h) denotes the probability from h' to h contributed by -i with strategy profile P. We postpone the derivation of Eq. 4 to Appx. E With the fact that m m. (pu(h)) (pa(h)) ht) +a(h) where pa(h) is the parent of h. computing m, only spends O(1) time on each node as when visiting h, m. (p)(h)) must have been computed in DFS.
The last challenge is how to update these DSs to satisfy the desired properties in Prop I Specifically, let S1, denote the set of histories such that if h E S. the strategy on subt (h) is modified at round t and S2, = {h- : h & S1,1, E Sr,e) As illustrated in Fig. 2 we only update DSs on
S. = S U S2, as:
Update on the DSs: 1) I on the infoset of h is modified, set (th) = 3(h, a) = 0; else 2) for h E St, and set (h) mh),,, 3(h, a) m. (h)) a)).
6

---

Published as a conference paper at ICLR 2020
With above update rule, it is easy to check that if Prop 1 is true at t, then it is still true 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- Lazy-CFR+ CFR+ and Lazy-LCFR, we only need to replace RM by the corresponding OLO solvers, and use their methods of computing time-averaged strategy 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 (²(0) = Ed V V T
max;, ('(a) and r7(a) =
/ A m (E (T)+ Tot(())
which are parameters depending on the structure of the game and segmentation rule. TThm [ provides regret bound for a CFR algorithm with an arbitrary segmentation rule. By applying Thm. I we can get the regret bound of CFR and Lazy-CFR which are comparable with Corollary in (Burch 2018).
Theorem 1. The regret of CFR with lazy update can be bounded as Riz(o) S <O(TTT(O)).
Lemma With RM, the regret of the vanilla CFR is bounded by O(EVAT) and the regret of Lazy-CFR bounded by O(TVDAT).
Proof. It is easy to see that for the vanilla CFR, we have r)(a) I { and for Lazy-CFR, we have m)r)= & (AD. With Thm. 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 [, Obviously, Σ, [Spl Omax, Do (h). Thus, can bound Lazy-CFR's time complexity as:
Lemma 3 (Time complexity). The time complexity of Alg. 7 is O(T max, (h))
To show how small max, ( is, we make the following mild assumption which leads to Corollary
Assumption 1. 1, if = i, then P((h, + The tree of infosets for each player 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 then Vo, Σnez' म. -(h) (nn
According to Lemmas and the regret of Lazy-CFR is about O(VD) times larger than that of CFR, whilst the running time is about O ((v[Z) times faster than CFR per round under Assumption Thus, according to Lemmas I and with a bit algebra calculation, we know that Alg. [ is about O( O(VIZ)/D D) times faster than the vanilla CFR achieve the same approximation error. The improvement is significant in large scale TEGIs.
Space complexity: potential limitation of Lazy-CFR that space complexity is O(HH) as we have to store the data structures 3, á on histories. In contrast, the space complexity is O []) for CFR. heads-up flop hold'en em poker (FHP) (Brown al. 2019). we have H R 10 and Σ| ss 10". 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 well better implementation.
some popular implementation
7

---

Published as a conference paper at ICLR 2020
Leduc-6
Leduc-8
FHP-7, 2 suits, 5 cards
Expleitabiig (lag 10)
Explottabilly (lgg 100
Explotrablity Deg
Uo bi Ue
seconds (loq
secands [loq 101
Nodes (c) FHP
floq 10)
(a) Leduc-6
(b) Leduc-8
Figure 3: Convergence for LaZY- CFR+, LCFR), MC-(CER, CFR+, LCFR), CFR, CFR+, LCFR and MC-LCFR-P.
4.3 REGRET LOWER BOUND
In the analysis of lower bound, consider the standard adversarial setting in online learning, in which an adversary selects o, and reward function ui 2 - [-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 o, and ut (T), I E Z. This setting is consistent with the analysis of the regret upper bound, in which we do not make any assumption on how ut, o, changes over rounds. Intuitively, by extending the lower bound analysis of OLO (Cesa-Bianchi & Lugosi, 2006) to infoset tree structured problem, we bound Eq. from below as Thm. 2 and for the proof, see Appendix D
Theorem 2. For an algorithm & generating of given the history in the past, let Ri denote the
regret of & in the first T rounds, have limA-+0 limr- ming max / log
1.
By comparing the regret lower bound in Theorem and the regret upper bounds of CFR and that the regret of CFR and Lazy-CFR are both near-optimal.
Lazy- Lazy-CFR as Lem 2
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-Carla sampling to avoid updating the strategy on infosets with small probability of arriving at. Pruning-based based variants (Brown & Sandholm) 201 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., (017)) 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. (200)); Burch Ni (2012): Burch (2018) refined the regret upper bound of CFR. Our analysis is essentially an extension the regret analysis on the vanilla CFR in (Burch 2018) to other variants of CFR with lazy-update.
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 (o .²) can be interpreted as the approximation error to the Nash equilibrium. The exploitability is defined as max... ut ((o'2 ((o'2,a²))) max w² ((a), r2))
Experiments are conducted on variants of two common benchmarks in Imperfect-informattee game solving: (1) the Ledue hold' em (Southey et al. (2055) which is simplifed version of the heads-up no-limit hold'em em poker with 6 cards; and (2) heads-up flop hold'en em poker (Brown et al. (019)) (FHP) which is similar to heads-up no-limit Texas hold" hold'em poker without the last two rounds of betting.
In our experiments Ledue Hold' em poker, we restrict players not to bid more than or 8 times the big blind. The number of infosets in the generated game trees about 40000 and 455000 for each player, respectively. We run each algorithm on each Ledue Hold' em game for 30000 seconds. In the experiments of FHP, to control the size of the game, consider simplified game such that in the
8

---

Published as a conference paper at ICLR 2020
deck, there are 2 suits and cards in each suit. And restrict players not to bid more than 7 times the big blind. The size the game about 10". We measure algorithms by the number nodes touched which is independent with implementation and hard-ware.
We empirically compare Lazy-(CFF,CFR,,LL and MC-LCFR with negative regret-pruning (MC-LCFR-P)
with existing methods, including the vanilla CFR,
CFR+, LCFR, MCC-CCFR,CRR+,CCCN which was used in developing Pluribus (Brown Sandholm| (019b). In our experiments, we use set B {0.1, 1.0]. We evaluate the CFR, CFR+, LCFR variants which prunes the histories with To, (h) = in the recursive tree walk as they don't 't affect the regret. For MC-(CFR, LCFRR, we use the external -ameling scheme. In the experiments on MC-LCFR-P, P,, we use the following parameters: we run MC-LCFR in the first 20 minutes; after that, in each iteration, we run MC-L.CFR with probability 0.05 and run MC-LCCR-P with probability 0.95; in MC-LCFR-P, we prune those branches with average regret less than -2 times the big blind.
RM (RM+) as the OLO solver. In LCF))
Fig. 3 presents the results. We can see that the performance of Lazy-CFR(+) has 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 म. (hh = on average. And on the larger game, I Lazy-CFR(+) significantly outperforms CFR(+). The performance of Lazy-LCFR is much worse than LCFR on all games. This might because our segmentation rule is designed for OLO with uniform weight in each iteration. And LCFR assigns more weights on later iterations.
CONCLUSIONS
In this work, we propose a new framework to develop efficient variants of CFR with an analysis shows that algorithm is provably faster than the vanilla CFR. The final algorithm runs fast in practice, but with some extra cost on space complexity. is worth of systematical study to reduce the space complexity.
ACKNOWLEDGEMENT
This work was supported by the National Key Research and Development Program of China (No. 2017YFA0700904), NSFC Projects (Nos. 61620106010, U19B2034, U181 1461), Beijing NSF Project (No. L172037), Beijing Academy of Artificial Intelligence (BAAI), Tsinghua-Huawei Joint Research Program, grant from Tsinghua Institute for Guo Qiang, Tiangong Institute for Intelligent Computing, the JP Morgan Faculty Research Program and the NVIDIA NVAIL Program with GPU/DGX Acceleration.
REFERENCES
Jacob Abernethy, Peter L Bartlett, and Elad Hazan. Blackwell approachability and no-regret learning are equivalent. In Proceedings of the 24th Annual Conference on Learning Theory, pp. 27- 2011.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. Gambling rigged casino: The adversarial multi-armed bandit problem. In focs, pp. 322. IEEE, 1995.
David Blackwell et al. An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathematics, 6(1):1-8, 1956.
Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Heads-up limit hold' em poker is solved. Communications of the ACM, 60(1 1):81888, 2017.
Noam Brown and Tuomas Sandholm. Regret-based pruning in extensive-form games. In Advances in Neural Information Processing Systems, pp. 1972-1980, 2015.
Noam Brown and Tuomas Sandholm. Reduced space and faster convergence in immerfecttinformaaiee games via regret-based pruning. In Workshops at the Thirty-First AAAI Conference on Artificial Intelligence, 2017a.

---

Published as a conference paper at ICLR 2020
Noam Brown and Tuomas Sandholm. Safe and nested subgame solving for imperfect-informatiie games. In Advances in Neural Information Processing Systems, pp. 689-699, 2017b.
Noam Brown and Tuomas Sandholm. Solving imperfect-information games via discounted regret
minimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 1829-1836, 2019a.
Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456): 885-890, 2019b.
Noam Brown, Christian Kroer, and Tuomas Sandholm. Dynamic thresholding and pruning for regret minimization. In T'hirty-Frrs AAAI Conference on Artificial Intelligence, 2017.
Noam Brown, Adam Lerer, Sam Gross, and Tuomas Sandholm. Deep counterfactual regret min- imization. In Kamalika Chaudhuri and Ruslan Salakbutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learn- ing Research, pp. 793-802, Long Beach, Califormia, USA, 09-15 Jun 2019. PMLR. URL htttp:/prrcceel ngs mlr. wttess//v7/bboww/ 9b. html
Neil Burch, Time and space: Why imperfect information games are hard. 2018.
Szafron Burch N, Lanetot M. Efficient monte carlo counterfactual regret minimization in games with many player actions. In Advances in Neural Information Processing Systems. 2012, 2012.
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Varsha Dani, Sham M Kakade, and Thomas P Hayes. The price of bandit information for online optimization. In Advances in Neural Information Processing Systems, pp. 345-352, 2008
Steven De Rooij, Tim Van Erven, Peter D Grünwald, and Wouter M Koolen. Follow the leader if you can, hedge if you must. The Journal of Machine Learning Research, (5(1):121--131, 2014.
Yoav Freund and Robert E Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):119-1)) 1997.
Daphne Koller and Nimrod Megiddo. The complexity of two-person zero-sum games in extensive form. Games and economic behavior, 4(4):528-552 1992.
Marc Lanctot, Kevin Waugh, Martin Zinkevich, and Michael Bowling. Monte carlo sampling for regret minimization in extensive games. In Advances in neural information processing systems, pp. 1078-1086, 2009.
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisy. Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no- no-limit poker. Science, 356(6337):508 -13, 2017.
Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V Vazirani. Algorithmic game theory. Cambridge University Press, 2007.
Martin Osborne and Ariel Rubinstein. course in game theory. MIT press, 1994.
Finnegan Southey, Michael Bowling, Bryce Larson, Carmelo Piccione, Neil Burch, Darse Billings, and Chris Rayner. Bayes' bluff: opponent modelling in poker. In Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence, pp. 550-558. AUAI Press, 2005.
Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information. Advances in neural information processing systems, pp. 1729-1736 2008
10

---

Published as a conference paper at ICLR 2020
A
THE TABLE OF NOTATIONS
We provide table of some important notations in our paper in this section.
Notation
Explanation
n
the set 11, n.
la,
6]
the set {a, 1, 1, ,b
H
The tree of histories Infomation set the depth of the game tree the depths of and h the chance player history
I
D
d(I) and d(h)
h
z ZCH
the set leaves of the game tree the successor of h after action the successor of after action a I' is the infoset of player and I UT²
(h,a)
(I,a)
D.I
P
The player function, i.e., P(h) and P(T) are the players who take actions on h and I, respectively. the strategy of player i; the strategy of all players;
o'
the strategy of all players except player i
(h))o(1)
PPhh) (hh) o (h) and o(1) = (I)
(h),
the reach probability of h and contributed by players
(1)
the reach probability of h and I contributed by player
To T
the reach probability of h and / contributed by all players except i the reach probability from h'' to contributed by all players except if E subt(h") the reward received by player at leaf
u((h),hEZ
ul(a)
the reward received by player with strategy profile the reward received by player at h with strategy profile a the strategy profile generated from by replacing (T)) by o' the parents of h and I respectively
(h(l))
alror())
pa(h),pa()
subt(h), subt(T)
the subtree rooted at h and I respectively subset of subt such that for all I' E (I) then P(I') i;; consider I" E subt(I) (T), if I" an ancestor of I', then P(I") # the inner product of vectors and b the action selected by the player at time step
r(I),
(a,b)
we
c
the reward vector time step
nelo
the regret the set of distributions over set A (o') Di= u'(o', o, -T u'((o), the regret of player i, i.e., R2 max,i (ot)
OLO, i.e., Rglo max Et-r (w, ct) )
A(A)
(ot)
RG
the time-averaged strategy with (f)(1) =5
or
Σl (T)
(T()).T(h))
the last time step update the strategy infoset (history h) before time t the of reach probabilities, mh)h) Σt. Ev=n( कo (h)
(h)
mi(I)
m!()) Ener mh)
r,(h,a)
the sum of counterfactural rewards over the j-th segment of h (I, Σner ry (h, a)
r,(
U(h)
data structure with U(h) w² (h)or) time step i data structure with Σ(T) a, (T) at time step t
a,8,à
data structures such that, at time step t, my m² = a(h) + En Enthhesshe(())) a(h)=T(()) and
ry a) (h, a) + ((h, a)) Enieeswbrr â(h) (11h)mm-'(() (h)
e((o)
parameter depends the structure of the game with ( EIET,
g
{ 5a
n(()
parameter depends on the segmentation rule with n)()) = Agi(a) maxi,j
( (لا1
(2tth()++111 (
11

---

Published as a conference paper at ICLR 2020
B DERIVATION OF REGRET BOUNDS OF RM AND ADAHEDGE
The regret upper bound RM and AdaHedge used in this work can be easily derived from previous works. We include their derivations only for completeness.
Derivation of Eq. ① The standard analysis of RM in Cor 2.1 pg. 13 in (Cesa-Bianchl & Lugosi 2006) shows the regret of RM is bounded by:
2
A Σ
Regho 5o
Σ
wu(a')a((d))aa -
Obviously, have
Σi |AI we(la)c((a)) s maxa [c{(a) since wy is vector of probability, We
have:
2
Σ
Σ w((d')a((a') c((a)
4 max (a) 4|A max (a))
We finished the proof.
Derivation of the regret bound of AdaHedge. Let U2 denote the variance of reward if we take a ran- dom action according to the distribution wy defined AdaHedge. Theorem in (De Rooij al.) 2014) provides second-order bound as:
4 log AA Σ v + log |A| +
Rg
where K is constant. It is known that for random variable x E [a, b), its variance is no more than (a - 6)//4. Thus, v, S max, (a)) We finished the proof.
12

---

Published as a conference paper at ICLR 2020
C PROOF OF THEOREM 1
We now extend the proof of the Theorem in (Burch 2018 to CFR with lazy update. We first intro- duce some additional terminology. Consider B _ T let { (B) = max,- EIEB " - (n). Now we prove Theorem
Proof. Let ń. denote the constant involved in Eq. have
I With Eq. 2 and the regret bound of R.M, we
+ -
E
wor,
P()=)())=i
n
SK Σ P(D=
To(1)
Σ
(max(r((T,)))271
And then apply Jensen's 's inequality and with some calculations, we have
1
(o)
T
n(l)
<
(T((),
A
Σ j=l
max of (I,
TET1
EP Ttds |=
n
Σ
(1)
A
max (l,
Er =dd Ti. (1')
I:d(T)=d
j=1
D
(T)
n(1) max 12 (I, T2
K
Σ
Ta(T')=Ti(1))
E T=d(T)md
Em T3 (T') (T))TTo((T)
A
d=1
j=1
Tyd T1 E, -.
n( Σラ max, (1, 0)
Σ
(((TTTT)))
Σ
A
Σ Er T (T')
(Ee no, (T)) T
d=1
P.td(P))dd
T=d(T)md
Σ. =f) (T)
m( j= max, (T(
Σ
(((')TTT'(''))
Σ
En Tod Taa (1')
(Er To. (1)) 2 T
P.td((''=dd
I=d(1i=d
E. Entt(()mo(()) +
Inl)) max, rT a)
S R
Σ
(T')aa))))))))
Σ
(E, मनं (1)) (1))² 2
P.Ad(P'=dd
I:d(I)=d
The Jensen's inequality applies here, in which move the term of probability outside the square root into it.
(()) 1= max, 13 13(1,0)
Σ Ty((()=oi(1')
Tt. (T)
21=1
Σ, To: (1)T2
T:d(T)=d
ml)) Es=1 max, (1,
A Σ (T) IddT)=d
S KRI
Σ Tor (T)
d=1
The last inequality utilizes the fact that Er m (T')=(((())) < T =T)(()) (T) is the probability of arriving at infoset under strategy (a or and there is at most infoset been arrived at each level.
13

---

Published as a conference paper at ICLR 2020
It is easy that max, r](1,a) s ( (4(())
(1))(1)++ To. With straight-forward computations,
we finish the proof:
(++((1) j= (1) To (1))
A Σ (1) I:d()==d
E (1)
E Ej 42
A Σ I:d(I)=d
Ty (1) max
To. (I), this is because
maxx; if 2 0, Σ a; >
(=
G++
S A Σ To(
Σ 1-+(1+
कeं (T)
max
VETI
D THE REGRET LOWER BOUND ANALYSIS
Recall that the analysis 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 o, and u.. 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 arg max,: Tit=IEer,,Pun ())) Let D (1 I' 3o Ç. ( 0}. can be shown that D forms subtree of I'. Intuitively, our construction on o, and uf can be divided into two stages:
(ō T
1. For E 2, & D. (T) -1 for all L. This enforces player i take actions D, otherwise, it will always receive reward- -1
2. In each round I, for E DD. Z, P(T) # i, we first generate a random variable a(T) ~ Multinomial(1, Ato)): and then set o, (4, a()) = 1, and o, (1, a) = for a * a(I). Intuitively, this step separates R2 into )() isolated OLOS, each of which is of A actions and would be repeated for about O(T)((')) rounds, since only one of them will be triggered on in each time step according to our construction o, Thus, combined with the lower bound proved by (Cesa-Bianche & Lugosi 2006), each OLO incurs a regret of about CT log A/g'). and can informally provide lower bound of (((EE)) /T log A) VT VTTloggg A), which formally described in Theorem 2
Before proving Theorem 2 we first address some trivial cases and show some intuitions on the way construct the worst case of o, and ut.
Let (a()) EiEI (I). It is easy to see that ('(o) > (g'(D))2/D. And we are going to show that 1- 4om min& max,-1,u R pp A 1. To start, make implicit assumption that [A(T) 2 e I,, P(T) = 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, assume i and -i take actions alternatively.
We now show that it is sufficient to focus on the subtree D (Note that D is subtree rooted at I,). By setting (I) = -1 for I E Z and I & D, we know that player 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 (Tpa(T)) 1T Z. Otherwise, we can merge the subtree rooted at pa T), E Z into one single leaf node (i.e. an infoset 7 E Z after the mergence), and P(pa(T)) = VI E Z in the new merged infoset tree.
"This step is informal here. See later in this section for formal construction.
14

---

Published as a conference paper at ICLR 2020
The following property will be useful in our proof.
Lemma 4, Let (D(('))= -IED T (I). Moreover, let 5² fo' oI, for P(T) = i, (T, D). Then Yo (ob)) E EC', we have that P v D(bb)"
Proof. To start, let Pb(o;, 1) N,. EE (T'), D, where subt(I) means
the subtree rooted at (Note that it's possible that I' E subl(T), I' & D). Let (b(1) = max, pb I), and of arg m Pb(lo'.). We first show that, II E D.P(I) (z))) (b(((T,)))) j,k [Ab(T) where Ab(T) consists of a E A(T) such that a) E D.
With the definition of D, 4A E D. Fot E G, s.t. mg (1) > 0. (1, * (b(J)(
W.L.O.G. we assume p ( a,)) (D((J( then Voy such that m² (l) 0, we have
pb(o, 1) =1+ Σ
all,a)) J (1,
aEA(T)
< + Σ
aEA(I)
<1+1
Σ
(X4.0 [of(1,,;) + ob aJ)(,
With the last inequality, we can construct a (agy with pb((())', I,) 2 vb(at. I,) and (T) # (T') only if I' subt(I). Formally, we define (og) as:
(o))(7)) = (T)), & subl(T)
(d") = /²* (T'), l' E subt(T),
(4) (1, a). + aj. ap
(d)))(T,a))
(o6) = ob(T, az) + (T(
As ob E ç. (b((a)) : I,) = pb I.), which means a)(,,a)) = 0, due to ==; (1) > 0. Thus, Vor such that -/. (I) > 0, we have Ty (Ji(I, = 0, which means Ji(I,az) $ D (notice that M'
(1) (1) = 0. a (J)(L))))) = 0), that is contradict to our assumption (', E D. Thus
(1, =b (x)) ag AD()).
Now can show that ( 1) (T),) Vol, VT with mathematical induction.
Let D denotes the depth of D. As we assume (Tpa(T)) = i, E Z, P(T,) = if is odd and P(I,) -i if D is even. We separately discuss them follows:
= 1: Obviously (b Ir) = (pD(L,)= =1
D is even: Va E AD(Ir), Js J'(Ir, a) satisfies that , (((,, = (D(J)(I,,a)).
then
Pblo' 1,) Σ
Polo', ((()
aEAp(1)
Σ
(I
aEAp(()
=T)(T,)
Thus we get ob (o', T,) (b.(T.)
15

---

Published as a conference paper at ICLR 2020
D is odd and D 1: If Va e AD(I,) (),, satisfies that , J((, (p(J((Tra))) then Vo ES'
Pblo',1, ..)
=1+
Σ
(L ((..a)))
"EAp(T)
=1+ Σ
d(
"EAp(T)
=1 =1+1
Σ
o'(Lr, (b vaz Ap(I) (due to pb((,,)) (bb(,, Vaj. On Ap()))
aEAp(!)
=1 =1 =b++)((((raa))
=pb((+) (as Vo', ( ,,,) + (L, AD(I) is independent of o²)
We can get ( = (b,())) as well.
So Yo,, (o", (+) <b(T)) As D.. (b 1) =TD(T) is independent from of, finally prove this lemma.
As PD, is independent of the choice of o², we will drop the subscript o², that is, we will use ypb instead of D.. in the following proof.
Now prove Theorem 2
Proof. As we discussed before, it's sufficient to focus on the subtreee D, so of the terms (e.g. regret) in the following proof are defined D. not I'.
For D, P(pa(T)) i, 1T Z, we use the following procedure to generate o, and ut for each round:
ue(I) ~ (ernoull((O.5), V Z.
VT E P(T) # i, we define (T( as:
(b
PD( 1 LoEA PD (I,,a))
"EeeAoi (I(((a)))
Notice that this term only depends D, this (I). Each turn we first sample a(T) from Multinomia((1ppo(() then let (7) a(I).
determine D, immediately get
In the following proof we denote this generating procedure as M and use the notation EyI[-] as the expectation over this generating procedure.
Let (T), I E 'D denotes the cumulative arriving time player arrives at in the first rounds. With little abuse of notation, use the term (T), D to represent the regret of the subtree rooted at in the first T turns, i.e.
T
(T) max ,' - ((ot, IED
We will prove that limo limy EM Ri alg//
FbTlog A > 1, V alg with mathematical induc- tion, where Hir,atg is defined Theorem Notice that under the assumption that P(pa(I) = i, VI E Z, P(I,) = i is odd while P(I,) = -i D is even. In our proof we will discuss them separately.
16

---

Published as a conference paper at ICLR 2020
D 1: As (Auer al. 1995: Freund & Schapire 1997
Cesa-Bianchi & Lugosi Dani et al. 2008) have shown, for K-arm online linear optimization problem.
2006;
lim limy-+00
2 1, V alg, which is consistent to our proposition with TIE
p
even:
From the definition we can get that (b = EoeAD(I.)
4 lim EM (M (5(U((,,a))To 2 1, E Ap(L,), Valg.
then
EM R2g
Tagg (I))
lim lim
10000 T-050
(b(1.)) 17 log
2
Σ AoEAoll)) BM R ay (J)()..))) (J'
lim lim
A-000 T-+30
Fi (1, log
2
( (M..)) at (r:
lim [o (EA
Σ
lim
lim
A uy (J
/ (b( log
PD (D(J"(ra)) (J'(
Pb(L)T
1x Pb(J((Ta))) EneAD(I.) (L)
lim lim
Σ
A T-000
aEAp(1r)
In the first equation, we decompose the overall expected regret to the summation of regrets subtrees. This decomposition be derived in similar way to that of Eq. 2 in Appendix C
In the second equation
transform the limitation of T into limitation of
nr nr (J'((",, a)), Ya E AD([r). As the adversary selects action aj with probability PD [T); 0 where Pp(T,), denotes the j-th element of pD (I,), when T co, the co, Va AD(I,) well.
ny (J,(((,,,)))
The inequality is from induction and limr- nT (J'(I, pD(1),, e AD(Ir) due to the strong law of large numbers.
D is odd and D * 1: max ΣT= u1(0rli-ta I,) (a I,) denote the immediate regret on the root node for algorithm alg. We first show that under our construction EE EM alggiimm (1+) 2 0, V alg.
For convenience, let alg (T,)
proves that for K-arm online linear optimization problem, however the supremum only get with K and T/K - they use the property of maximum of infinite normal random variable and central limit theorem (CLTT) corre- spondingly. Here for clarity we cquivalently change supremum into limit in proof.
*Cosa- Bianchi & Lugosi
2006)
Bily.oty
supr,K K max /Tlog K/2
17

---

Published as a conference paper at ICLR 2020
Notice that in our construction, EM Et= ue(oell.-a:11 1,) 0.5T, Va E Ap(lr) Mean- while, EM Ei=1 ur(or, = 0.5l' as well. Thus,
T EM
Ue (o 1.) BEAD(I,)
1
Σ
t=1
=IM A
1
Σ
ue I+)
aEAp(Ie)
SEM max u100rl1,-as I,) aEAn(I.)
This inequality is true for all o (i.e. alg), and get
EM RTMRT,alg alg. imm (I+) E.M
max a (1+)
Σ
u( I,) uclor, (0) 20,
Valg
Then, similar to the case when even, we can get:
Ry alg (I))
lim lim
A-+00 T-+00
ein (r. log
2
M alg. (T+) + EoeA (1))))))) (Tr:a)))
lim lim
/bbll))Toon
EM (Ir()() (J((Tra))
20+ + lim lim 4 T-o0
Σ
oe pi.l.)Tlog 2
EM Bi nr (J (J'(Traa)
lim
Σ
lim A ny (J.,,a)))
lim
[o(l.) aE (F
2
(D (L. (L
Σ
20+0+ lim lim
A-000 T
(b.(1)T
EnEAa(l))m((())))) Pb (J (()
lim lim
A0000 T'
(L,)T
(T) -1 (I,(T)
lim 4
Similarly, we decompose the overall expected regret to each subtree in the first equation.
Notice that alg, limr EneAA(th).m(((())))))))))) E EM R (J) limr- (F EMR or (T(()).)))
oo, VT = Thus the second in- equality is true. The last inequality is true by E, Va, E,a,
Notice that ELEAD(I.) 1b (J'((rr ()) this by (T((((Ir,)) oi (I,, and Vt, E.EAD(..) (L) (I,)) (p,) - which can be simply derived by the definition of up and P(I,) = i), and lim Eosssllsnn limitation of T 00.
(vb(I.) 1)T (We can see
(1,)T = 0. Thus we can get the
18

---

According to Published as a conference paper at ICLR 2020
Thus, with mathematical induction, we prove that linn Aoo EM
1, while with
Tlg
get 4ob yo², thus can get the mini-max lower bound in the definition of 'D and Lemma
Theorem
E
THE DETAILS OF IMPLEMENTATION
We now discuss the detailed implementation of Lazy-CFR. To start, we derive Eq. have:
Property [
(h) =
Top (h)
(1)++))+
t2(h')
= Σ
Σ
Tor (h)
Wthhsub((hh) (
t2(h")
Σ
Σ
Tay
(h' )oo= (N, h)
Nrtheebb((h)) (IP) (M)-1
Σ
T (h', (h',))a('')
Wchheube(he))
The first equation the definition of my; the second line according to Prop 12 the third line is derived from the definition of a and म. and the last line is due to Property I Similarly, we can write ry as:
a1(,
Σ
To (1)
(k)+(
(a()
Σ
To (h)u ((h, a)lor)
hthhsabt(hh)) (h1)-(
(2(h')
=a(h) +
Σ
Σ
no. (h' ITo (h', h)u ((h, a)lor)
I W*Hcchouub(()) (+)
= ah) + a))
Σ
T (h,n))((1))))
If (h)h
We now present how implement of the ideas in 3.2.1
19

---

Published as a conference paper at ICLR 2020
Algorithm 2 A detailed implementation of Lazy-CFR
1: A two-player zero-sum extensive game.
2: Randomly initialize
3: vh E H, E 21, compute the counterfactual reward (*(h) = (lag()) -1.
4: VI E I, s(I) = 0, Va E A(I)) =
5: while < T do
6: for all i E (1,2) do
7:
a²hh)) = 1.0.
8:
UPDATE1(T;, where 1 is the root of infoset tree T
9:
end for
10: Vi E (1,2) UPDATE2(hr,, i, where h, denotes the root of the history tree.
end while
12: RETURN 5.
Algorithm 3 iPDATEI(L,,t)
1: m(l) =0
2: for all h E I do
3: ('(h) (6' (pa(h)) + á' (pa(()))) x (pa())))
4: m([)+ = (h) + (h)
5: end for
6:
if m(T) 2 then
7:
if P(I) = then
8:
for all a E A(T) do UPDATEI([I,)..) ().
9:
10:
end for
11:
Vh E I, (p, t, Va E ((T))rrrT,,n) = 0.
12:
13:
for all a E A(T), E do
r(I,a)+= a(h, (b))((()))))
15:
end for
(T) -RM(r(I))
17: else
Va E A(I.. U 1).
19: end if
end if
Algorithm 4 aa,flag(h,t,,
1: if h is not the root of history tree and flag' (h) * t then
2: flag' (h) = t.
3: updflag(po (h), t)
4: end if
Algorithm 5 iPDATE2(h,
1: Let denote the opponent of player
2:
if (h) = then
3:
Va E A(h) (H,,
4:
update U (h) and (h).
5:
('(h)= 0.
6:
(k(h)-0)
7:
Va E A(h), 3 (h.
0.
8:
else
a (h)++ = (0' (pa(h)) + az (pa(h))) कيे h)).
9:
10:
a²()+ = (0" (pa(h)) + at (pa(h))) म. (pa(h),
11: Va A(h), 3d (h,a)+ U (0, (pa(h)) + az (pa(h))) कन. (pa(t)))))
12: end if
20


Reviews:
[{"review_id": "Syx6tQccKB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe 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. \n\nThat being said, I follow up with some questions/criticism.\n1.\tImplementation in Section 3.2.1 and Appendix E is rather hard to follow. Is there any intuition on how the segment [\\tau_t(h), t] is divided, i.e. what does t_1, t_2 and \\tau’(h) mean? Also, clarity could be increased if these variables would be defined before they are used.\n2.\tHow 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?\n3.\tSection 3.2: “following step (1)”. (1) is an equation for RM in OLO, probably some other reference was meant.\n4.\tRecently, 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.\n5.\tThe 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+.\n\nUPD: score updated", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HyeDKG10KH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a variant of the counterfactual regret minimization (CFR) algorithm called Lazy-CFR for two-player zero-sum imperfect information games. The idea is to postpone visiting an information set as long as the sum of the (opponent) reach probabilities for the information set after the last strategy update is lower than a certain threshold. This pruning strategy allows one to avoid traversing the whole game tree and significantly speeds up the computation of approximate Nash equilibria. The authors provide detailed theoretical analysis of the proposed algorithm and show that the bound of the overall regret of the proposed algorithm is comparable to that of the original CFR. They conduct experiments using Leduc hold’em and show that the proposed approach gives significantly better results than existing CFR-based algorithms. The downside of the proposed algorithm is that it requires a memory of O(|H|) for bookkeeping, which can be very large and makes it difficult for the algorithm to be applied to large games.\n\nI feel ambivalent about this paper. On the one hand, the paper presents a promising idea for significantly speeding up the CFR algorithm with detailed theoretical justifications, but on the other hand, the (potentially huge) requirement for memory makes me unsure about the strength and practical merit of the algorithm compared to other CFR variants. \n\nI am a bit disappointed that the authors did not compare their algorithm with existing pruning methods on the ground that they do not have theoretical guarantee on running time. I think empirical comparison to the state of the art is always useful and should be conducted whenever possible. Would it be difficult to compare the proposed method with, for example, Brown and Sandholm (2019)?", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "HJly7LIcYS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces lazy-CFR, a CFR algorithm that updates only a subset of information sets each round (but notably differs from pruning and Monte Carlo methods). The paper offers a nice review of online linear optimization and its relationship to CFR, making its proposed algorithm easily digestible. The paper establishes convergence guarantees for lazy-CFR and shows experimentally that lazy-CFR+ outperforms CFR+, a formidable baseline, in Leduc poker. As is discussed in the paper, a major drawback of lazy-CFR is that its space complexity is on the order of the number of histories in the game. This will be an important direction for future work.\n\nThis is a nice paper. The writing is strong and its main idea is both novel and appears to be effective in practice. I have no major criticisms. What I would most like to see is more extensive experimental results. Does lazy-CFR offer similarly strong results other small imperfect information games (Kuhn poker, liar’s dice, etc.)? Additionally, it would be interesting to see how the how lazy-CFR performs compared 1) against discounted-CFR and 2) when combined with discounted-CFR. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposed an regret based approach to speed up counterfactural regret minimization. The reviewers find the proposed approach interesting. However, the method require large memory. More experimental comparisons and comparisons pointed out by reviewers and public comments will help improve the paper. 
Decision: Accept (Poster)