Counterfactual Regret Minimization (CFR) finds good strategies in imperfect information games. We'll focus on zero-sum games.
In rock-paper-scissors the equilibrium is for both players to play uniformly at random. If you play rock more than of the time, I can play more paper and win on average. At the uniform strategy there is nothing to exploit. The goal of CFR is to compute an equilibrium.
# Regret
The regret for action is what you would have earned by playing minus what you actually earned. Positive regret means would have been better; negative regret is the other way around.
Ideally, suppose we score a win as , a tie as and a loss as . Then, say you play rock and the opponent plays paper. I got . Paper would have got and scissors . So the regrets for this round are
rock:
paper:
scissors:
Let be what action would have earned against the opponent's play in round , and be what my strategy actually earned, the cumulative regret of after rounds is
# Regret matching
Regret matching plays each action with probability proportional to its positive cumulative regret,
and uniformly at random if no regret is positive. It is basically, the natural response to regret which is playing the actions you regret not playing more often. Its cumulative regret grows at most like , so average regret goes to zero like .
# Equilibrium
Suppose we let both players use regret matching against each other.
In a two-player zero-sum game, if both players have average regret at most , then their average strategies form a -Nash equilibrium.
The average strategy is
Low regret implies that no fixed action would have done much better against the opponent's play on average. If that holds for both players, neither average strategy can be exploited by much, which is approximate equilibrium.
# Counterfactual value
In most games players take turns and can't see everything. So it is quite naive to assume that a strategy is a row of a table because there would be exponentially many rows. CFR instead runs a small regret matcher at each information set , a set of game states . CFR runs regret matching separately at every information set. Each matcher needs a payoff for the actions at , which is the counterfactual value:
is the probability that play goes from to , and is player 's payoff there. Basically, the inner sum is the expected payoff from onward. ranges over the end states reachable from . The outer sum weights each by the probability that chance and the opponent play to , and adds them up. Our own reach probability is left out, so is the value of as if we had played to reach it. That is what makes it counterfactual, and it lets every information set be treated as its own regret problem, even ones we rarely reach.
# Counterfactual regret
Let be except that player always plays at . The counterfactual regret of at is Eq. 1 with payoffs replaced by counterfactual values:CFR is regret matching on these, separately at every information set:
Zinkevich et al. 1 show that the regret of the whole game is at most the sum of these local regrets, so if every information set is no-regret, so is the whole strategy. By the result in the equilibrium section, the average strategy then converges to a Nash equilibrium. As in rock-paper-scissors, it's the average you keep, not the last iterate. At each the average is weighted by our own reach , since iterations where we rarely reached barely affected how we played.
Here are some practical CFR implementations worth reading:
OpenSpiel
OpenSpiel Deep CFR: the PyTorch version.
Neller and Lanctot's tutorial: more detailed tutorial.
# References
- [1]M. Zinkevich, M. Johanson, M. Bowling and C. Piccione, Regret Minimization in Games with Incomplete Information, NeurIPS 2007.