Faster algorithms for extensive-form game solving via improved smoothing functions
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.
- Faster algorithms for mean-payoff games
- Faster algorithm for mean-payoff games
- Faster algorithms for mean-payoff parity games
- Smoothing techniques for computing Nash equilibria of sequential games
- scientific article; zbMATH DE number 177098
- Efficient computation of equilibria for extensive two-person games
- Exact algorithms for solving stochastic games
- Faster Algorithms for Finitary Games
- Stochastic mean payoff games: smoothed analysis and approximation schemes
- An exact double-oracle algorithm for zero-sum extensive-form games with imperfect information
- DeepStack: expert-level artificial intelligence in heads-up no-limit poker
- Efficient computation of behavior strategies
- Efficient computation of equilibria for extensive two-person games
- Excessive Gap Technique in Nonsmooth Convex Minimization
- Faster algorithms for extensive-form game solving via improved smoothing functions
- First-order algorithm with \({\mathcal{O}(\ln(1/\epsilon))}\) convergence for \({\epsilon}\)-equilibrium in two-person zero-sum games
- scientific article; zbMATH DE number 1667417 (Why is no real title available?)
- scientific article; zbMATH DE number 1759693 (Why is no real title available?)
- scientific article; zbMATH DE number 3215746 (Why is no real title available?)
- Lossless abstraction of imperfect information games
- Near-optimal no-regret algorithms for zero-sum games
- Primal-dual subgradient methods for convex problems
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
- Smooth minimization of non-smooth functions
- Smoothing techniques for computing Nash equilibria of sequential games
- Solving variational inequalities with stochastic mirror-prox algorithm
- The complexity of computing a Nash equilibrium
- Faster algorithms for extensive-form game solving via improved smoothing functions
- An exact double-oracle algorithm for zero-sum extensive-form games with imperfect information
- Revisiting CFR^+ and alternating updates
- Smoothing techniques for computing Nash equilibria of sequential games
- First-order algorithm with \({\mathcal{O}(\ln(1/\epsilon))}\) convergence for \({\epsilon}\)-equilibrium in two-person zero-sum games
- HSVI can solve zero-sum partially observable stochastic games
- Automatically designing counterfactual regret minimization algorithms for solving imperfect-information games
This page was built for publication: Faster algorithms for extensive-form game solving via improved smoothing functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2288198)
