Lazy-CFR: fast and near optimal regret minimization for extensive games with imperfect information

Understand

Counterfactual regret minimization (CFR) is the most popular algorithm on solving two-player zero-sum extensive games with imperfect information and achieves state-of-the-art performance in practice.

• However, the performance of CFR is not fully understood, since empirical results on the regret are much better than the upper bound proved in \cite{zinkevich2008regret}.
• Another issue is that CFR has to traverse the whole game tree in each round, which is time-consuming in large scale games.
• In this paper, we present a novel technique, lazy update, which can avoid traversing the whole game tree in CFR, as well as a novel analysis on the regret of CFR with lazy update.