Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria

We study the application of iterative first-order methods to the problem of computing equilibria of large-scale extensive-form games. First-order methods must typically be instantiated with a regularizer that serves as a distance-generating function (DGF) for the decision sets of the players. In this paper, we introduce a new weighted entropy-based distance-generating function. We show that this function is equivalent to a particular set of new weights for the dilated entropy distance–generating function on a treeplex while retaining the simpler structure of the regular entropy function for the unit cube. This function achieves significantly better strong-convexity properties than existing weight schemes for the dilated entropy while maintaining the same easily implemented closed-form proximal mapping as the prior state of the art. Extensive numerical simulations show that these superior theoretical properties translate into better numerical performance as well. We then generalize our new entropy distance function, as well as general dilated distance functions, to the scaled extension operator. The scaled extension operator is a way to recursively construct convex sets, which generalizes the decision polytope of extensive-form games as well as the convex polytopes corresponding to correlated and team equilibria. Correspondingly, we give the first efficiently computable distance-generating function for all those strategy polytopes. By instantiating first-order methods with our regularizers, we achieve several new results, such as the first method for computing ex ante correlated team equilibria with a guaranteed 1 / T rate of convergence and efficient proximal updates. Similarly, we show that our regularizers can be used to speed up the computation of correlated solution concepts.