Stable-Predictive Optimistic Counterfactual Regret Minimization
Stable-Predictive Optimistic Counterfactual Regret Minimization
复制标题
DOI：
--
复制
发表时间：
2019-02
期刊：
影响因子：
--
通讯作者：
Gabriele Farina;Christian Kroer;Noam Brown;T. Sandholm
中科院分区：
文献类型：
--
作者：
Gabriele Farina;Christian Kroer;Noam Brown;T. Sandholm
CFR框架已经成为解决实际中大规模扩展形式游戏的有力工具。然而，过去基于CFR的算法收敛到纳什均衡的理论速度约为$O(T^{-1/2})$，其中$T$是迭代的次数。相反，一阶方法可以用来实现对迭代的$O(T^{-1})$依赖，但是这些方法在实践中不太成功。在这项工作中，我们提出了第一个打破了对迭代的平方根依赖的CFR变体。通过结合和扩展矩阵博弈环境下预测和稳定后悔最小化算法的最新进展，我们证明了利用“乐观的”后悔最小化算法在CFR内实现$O(T^{-3/4})$收敛是可能的。这是通过引入稳定预测性的新概念，并通过设置每个反事实后悔最小化器相对于其在决策树中的位置的稳定性来实现的。实验表明，尽管该算法的最坏情况是依赖于迭代次数$O(T^{-1/2})$，但仍比原CFR算法快，但不如新的算法快。
The CFR framework has been a powerful tool for solving large-scale extensive-form games in practice. However, the theoretical rate at which past CFR-based algorithms converge to the Nash equilibrium is on the order of $O(T^{-1/2})$, where $T$ is the number of iterations. In contrast, first-order methods can be used to achieve a $O(T^{-1})$ dependence on iterations, yet these methods have been less successful in practice. In this work we present the first CFR variant that breaks the square-root dependence on iterations. By combining and extending recent advances on predictive and stable regret minimizers for the matrix-game setting we show that it is possible to leverage "optimistic" regret minimizers to achieve a $O(T^{-3/4})$ convergence rate within CFR. This is achieved by introducing a new notion of stable-predictivity, and by setting the stability of each counterfactual regret minimizer relative to its location in the decision tree. Experiments show that this method is faster than the original CFR algorithm, although not as fast as newer variants, in spite of their worst-case $O(T^{-1/2})$ dependence on iterations.