Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: 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.

I 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. 

I 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)?
review_title: Official Blind Review #1

final_score: rating: 8: Accept
review_content: 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
review_title: Official Blind Review #3

final_score: rating: 8: Accept
review_content: 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.

This 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. 
review_title: Official Blind Review #3

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)