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.
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 [\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.
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