Blog
About

7
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Lazy-CFR: a fast regret minimization algorithm for extensive games with imperfect information

      Preprint

      , , , ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          In this paper, we focus on solving two-player zero-sum extensive games with imperfect information. Counterfactual regret minimization (CFR) is the most popular algorithm on solving such games 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 of CFR is that CFR has to traverse the whole game tree in each round, which is not tolerable in large scale games. In this paper, we present a novel technique, lazy update, which can avoid traversing the whole game tree in CFR. Further, we present a novel analysis on the CFR with lazy update. Our analysis can also be applied to the vanilla CFR, which results in a much tighter regret bound than that proved in \cite{zinkevich2008regret}. Inspired by lazy update, we further present a novel CFR variant, named Lazy-CFR. Compared to traversing \(O(|\mathcal{I}|)\) information sets in vanilla CFR, Lazy-CFR needs only to traverse \(O(\sqrt{|\mathcal{I}|})\) information sets per round while the regret bound almost keep the same, where \(\mathcal{I}\) is the class of all information sets. As a result, Lazy-CFR shows better convergence result compared with vanilla CFR. Experimental results consistently show that Lazy-CFR outperforms the vanilla CFR significantly.

          Related collections

          Most cited references 5

          • Record: found
          • Abstract: not found
          • Article: not found

          An analog of the minimax theorem for vector payoffs

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            The complexity of two-person zero-sum games in extensive form

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              Lossless abstraction of imperfect information games

                Bookmark

                Author and article information

                Journal
                10 October 2018
                Article
                1810.04433

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                Custom metadata
                cs.LG stat.ML

                Machine learning, Artificial intelligence

                Comments

                Comment on this article