StablePredictive Optimistic Counterfactual Regret Minimization
[edit]
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:18531862, 2019.
Abstract
The CFR framework has been a powerful tool for solving largescale extensiveform games in practice. However, the theoretical rate at which past CFRbased algorithms converge to the Nash equilibrium is on the order of $O(T^{1/2})$, where $T$ is the number of iterations. In contrast, firstorder 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 squareroot dependence on iterations. By combining and extending recent advances on predictive and stable regret minimizers for the matrixgame 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 stablepredictivity, 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 worstcase $O(T^{1/2})$ dependence on iterations.
Related Material


