Lazy-CFR: Fast and Near-Optimal Regret Minimization for Extensive Games with Imperfect Information
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.
Cite
Text
Zhou et al. "Lazy-CFR: Fast and Near-Optimal Regret Minimization for Extensive Games with Imperfect Information." International Conference on Learning Representations, 2020.Markdown
[Zhou et al. "Lazy-CFR: Fast and Near-Optimal Regret Minimization for Extensive Games with Imperfect Information." International Conference on Learning Representations, 2020.](https://mlanthology.org/iclr/2020/zhou2020iclr-lazycfr/)BibTeX
@inproceedings{zhou2020iclr-lazycfr,
title = {{Lazy-CFR: Fast and Near-Optimal Regret Minimization for Extensive Games with Imperfect Information}},
author = {Zhou, Yichi and Ren, Tongzheng and Li, Jialian and Yan, Dong and Zhu, Jun},
booktitle = {International Conference on Learning Representations},
year = {2020},
url = {https://mlanthology.org/iclr/2020/zhou2020iclr-lazycfr/}
}