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

• 成果类型: Article
• 署名作者: Farina, Gabriele; Kroer, Christian; Sandholm, Tuomas
• 署名单位: Columbia University; Carnegie Mellon University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2021.0633
• 发表日期: 2025
• 关键词: efficient computation; convex; Poker

摘要

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.