Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria
研究用一阶方法计算大规模扩展式博弈的均衡，提出新的加权熵距离生成函数，实现更优强凸性并保持高效近端映射，首次实现以1/T速率收敛的ex ante关联团队均衡计算方法。
The paper studies the application of first-order methods to the problem of computing equilibria of large-scale extensive-form games. It introduces a new weighted entropy-based distance-generating function for instantiating first-order methods. The new 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. The paper then generalizes our new entropy distance function, as well as the whole class of dilated distance functions, to the scaled extension operator. This yields the first efficiently computable distance-generating function for the decision polytopes capturing correlated and team solution concepts for extensive-form games. By instantiating first-order methods with these regularizers, several new results are achieved, such as the first method for computing ex ante correlated team equilibria with a guaranteed 1/T rate of convergence and efficient proximal updates.