Lazy-CFR: fast and near-optimal regret minimization for extensive games with imperfect information
Yichi Zhou, Tongzheng Ren, Jialian Li, Dong Yan, Jun Zhu
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.
BibTeX
@inproceedings{
Zhou2020Lazy-CFR:,
title={Lazy-CFR: fast and near-optimal regret minimization for extensive games with imperfect information},
author={Yichi Zhou and Tongzheng Ren and Jialian Li and Dong Yan and Jun Zhu},
booktitle={International Conference on Learning Representations},
year={2020},
url={https://openreview.net/forum?id=rJx4p3NYDB}
}