Regret Minimization in Games with Incomplete Information
- Martin Zinkevich
- Michael Johanson, University of Alberta
- Michael Bowling, University of Alberta
- Carmelo Piccione, Department of Computing Science, University of Alberta
Extensive games are a powerful model of multiagent decision-making scenarios with incomplete information. Finding a Nash equilibrium for very large instances of these games has received a great deal of recent attention. In this paper, we describe a new technique for solving large games based on regret minimization. In particular, we introduce the notion of counterfactual regret, which exploits the degree of incomplete information in an extensive game. We show how minimizing counterfactual regret minimizes overall regret, and therefore in self-play can be used to compute a Nash equilibrium. We demonstrate this technique in the domain of poker, showing we can solve abstractions of limit Texas Holdâem with as many as 10^12 states, two orders of magnitude larger than previous methods.
Citation
M. Zinkevich, M. Johanson, M. Bowling, C. Piccione. "Regret Minimization in Games with Incomplete Information". Neural Information Processing Systems (NIPS), (ed: J.C. Platt, D. Koller, Y. Singer, S. Roweis), pp 1729--1736, December 2007.| Keywords: | game theory |
| Category: | In Conference |
BibTeX
@incollection{Zinkevich+al:NIPS07,
author = {Martin Zinkevich and Michael Johanson and Michael Bowling and
Carmelo Piccione},
title = {Regret Minimization in Games with Incomplete Information},
Editor = {J.C. Platt, D. Koller, Y. Singer, S. Roweis},
Pages = {1729--1736},
booktitle = {Neural Information Processing Systems (NIPS)},
year = 2007,
}Last Updated: August 19, 2009Submitted by Michael Johanson
