skip to main content
10.1145/3033274.3085131acmconferencesArticle/Chapter ViewAbstractPublication PagesecConference Proceedingsconference-collections
abstract
Public Access

Theoretical and Practical Advances on Smoothing for Extensive-Form Games

Published:20 June 2017Publication History

ABSTRACT

Sparse iterative methods, in particular first-order methods, are known to be among the most effective in solving large-scale two-player zero-sum extensive-form games. The convergence rates of these methods depend heavily on the properties of the distance-generating function that they are based on. We investigate the acceleration of first-order methods for solving extensive-form games through better design of the dilated entropy function---a class of distance-generating functions related to the domains associated with the extensive-form games. By introducing a new weighting scheme for the dilated entropy function, we develop the first distance-generating function for the strategy spaces of sequential games that only a logarithmic dependence on the branching factor of the player. This result improves the convergence rate of several first-order methods by a factor of Ω(bdd), where b is the branching factor of the player, and d is the depth of the game tree.

Thus far, counterfactual regret minimization methods have been faster in practice, and more popular, than first-order methods despite their theoretically inferior convergence rates. Using our new weighting scheme and practical tuning we show that, for the first time, the excessive gap technique can be made faster than the fastest counterfactual regret minimization algorithm, CFRP, in practice.

Skip Supplemental Material Section

Supplemental Material

10b_02kroer.mp4

Index Terms

  1. Theoretical and Practical Advances on Smoothing for Extensive-Form Games

        Recommendations

        Comments

        Login options

        Check if you have access through your login credentials or your institution to get full access on this article.

        Sign in
        • Published in

          cover image ACM Conferences
          EC '17: Proceedings of the 2017 ACM Conference on Economics and Computation
          June 2017
          740 pages
          ISBN:9781450345279
          DOI:10.1145/3033274

          Copyright © 2017 Owner/Author

          Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

          Publisher

          Association for Computing Machinery

          New York, NY, United States

          Publication History

          • Published: 20 June 2017

          Check for updates

          Qualifiers

          • abstract

          Acceptance Rates

          EC '17 Paper Acceptance Rate75of257submissions,29%Overall Acceptance Rate664of2,389submissions,28%

          Upcoming Conference

          EC '24
          The 25th ACM Conference on Economics and Computation
          July 8 - 11, 2024
          New Haven , CT , USA

        PDF Format

        View or Download as a PDF file.

        PDF

        eReader

        View online with eReader.

        eReader