Monte Carlo Sampling for Regret Minimization in Extensive Games

Michael Bowling, Martin Zinkevich, Kevin Waugh, Marc Lanctot

2009 · 197 citations · 7 references

DOIFull text

Open access

Concepts

Abstract

One efficient method for computing Nash equilibria in large, zero-sum extensive games is counterfactual regret minimization (CFR). In the domain of poker, CFR has proven effective, particularly when using a domain-specific augmentation involving chance outcome sampling. In this paper we introduce MCCFR, a Monte Carlo version of the algorithm capable of applying equivalent updates (in expectation) on sampled histories which has bounded overall regret with high probability. We show empirically that, although MCCFR requires more iterations, its lower cost per iteration results in overall faster convergence, particularly as the game size increases. 1

References

7