Theoretical and Practical Advances on Smoothing for Extensive-Form Games
Theoretical and Practical Advances on Smoothing for Extensive-Form Games
复制标题
广义博弈平滑的理论和实践进展
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
T. Sandholm
中科院分区：
文献类型：
--
作者：
Christian Kroer;K. Waugh;F. Kılınç;T. Sandholm
已知稀疏迭代方法，特别是一阶方法，是解决大规模二人零和广泛形式博弈最有效的方法之一。这些方法的收敛速度在很大程度上取决于它们所基于的距离生成函数的性质。我们通过更好地设计扩展熵函数（一类与广泛形式博弈相关的域相关的距离生成函数）来研究求解广泛形式博弈的一阶方法的加速。通过引入扩展熵函数的一种新的加权格式，我们开发了序列博弈策略空间的第一个距离生成函数，该策略空间仅对玩家的分支因子有对数依赖。该结果通过Ω（bdd）因子提高了几种一阶方法的收敛速度，其中b是玩家的分支因子，d是游戏树的深度。到目前为止，反事实遗憾最小化方法在实践中比一阶方法更快，更受欢迎，尽管理论上它们的收敛速度较低。利用我们的新加权方案和实际调整，我们首次表明，在实践中，过度间隙技术可以比最快的反事实遗憾最小化算法（CFRP）更快。
Sparse iterative methods, in particular first-order methods, are known to be among the most effective in solving large-scale two-player zero-sum extensive-form games. The convergence rates of these methods depend heavily on the properties of the distance-generating function that they are based on. We investigate the acceleration 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, we develop the first distance-generating function for the strategy spaces of sequential games that only a logarithmic dependence on the branching factor of the player. This result improves the convergence rate of several first-order methods by a factor of Ω(bdd), where b is the branching factor of the player, and d is the depth of the game tree. Thus far, counterfactual regret minimization methods have been faster in practice, and more popular, than first-order methods despite their theoretically inferior convergence rates. Using our new weighting scheme and practical tuning we show that, for the first time, the excessive gap technique can be made faster than the fastest counterfactual regret minimization algorithm, CFRP, in practice.