Faster algorithms for extensive-form game solving via improved smoothing functions (Q2288198)

Extensive-form games are a broad class of games. They model sequential interaction, imperfect information, and outcome uncertainty. The authors investigate both the theoretical and practical performance improvement 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, they develop the first distance-generating function for the strategy spaces of sequential games that has only a logarithmic dependence on the branching factor of the player. This result improves the overall convergence rate of several first-order methods working with dilated entropy function. The authors make also some numerical experiments to investigate the speedup of first-order methods with convergence rate \(O(\frac{1}{\epsilon})\) and compare the performance of these algorithms with the premier regret-based methods CFR and CFR+, which have a theoretical convergence rate of \(O(\frac{1}{\epsilon^2})\). The authors show that classical first-order methods can be made faster than the counterfactual regret minimization algorithm in practice for large games.