2019 · 80 citations · 26 references
ComputingComputer ScienceDecision SciencesAlgorithmsDecision TheoryGame TheoryAlgorithmic Game TheoryIterative SolversReinforcement LearningReinforcement Learning FoundationsImperfect Information GamesLearning With Imperfect InformationOptimistic UpdatesPolicy Iteration With DiscountingRegret Optimization
Counterfactual regret minimization (CFR) is a family of iterative algorithms that are the most popular and, in practice, fastest approach to approximately solving large imperfectinformation games. In this paper we introduce novel CFR variants that 1) discount regrets from earlier iterations in various ways (in some cases differently for positive and negative regrets), 2) reweight iterations in various ways to obtain the output strategies, 3) use a non-standard regret minimizer and/or 4) leverage “optimistic regret matching”. They lead to dramatically improved performance in many settings. For one, we introduce a variant that outperforms CFR+, the prior state-of-the-art algorithm, in every game tested, including large-scale realistic settings. CFR+ is a formidable benchmark: no other algorithm has been able to outperform it. Finally, we show that, unlike CFR+, many of the important new variants are compatible with modern imperfect-informationgame pruning techniques and one is also compatible with sampling in the game tree.
26
The Weighted Majority Algorithm
N. Littlestone, Manfred K. Warmuth · Information and Computation · 1994 · 2K citations
A Simple Adaptive Procedure Leading to Correlated Equilibrium
Sergiu Hart, Andreu Mas‐Colell · Econometrica · 2000 · 1.1K citations · Full text
DeepStack: Expert-level artificial intelligence in heads-up no-limit poker
Matej Moravčík, Martin Schmid, Neil Burch et al. · Science · 2017 · 812 citations · Full text
Superhuman AI for heads-up no-limit poker: Libratus beats top professionals
Noam Brown, Tüomas Sandholm · Science · 2017 · 559 citations