An Introduction to Counterfactual Regret Minimization

http://cs.gettysburg.edu/~tneller/modelai/2013/cfr/index.html

by poppingtonic • 9 years ago

144 28 9 years ago

cs.gettysburg.edu

I'm sorry I read this?

Then next time you should skip the technical details and just read Michael Johanson's lay summary, so that you can be less sorry in the future: https://www.quora.com/What-is-an-intuitive-explanation-of-co...

semi-extrinsic• 9 years ago

This was really good, but one detail stood out to me: the average strategy found by a CFR converges to a Nash equilibrium strategy. For a two-player, zero-sum game, we know this is an optimal strategy.

But what about a game that's not two-player and zero-sum? Are CFRs still useful?

ikeboy• 9 years ago

I am now super curious to have a technical understanding of why it's the average strategy that converges and not the strategy itself.

mikebjohanson3• 9 years ago

Hey, thanks for the mention! I've read hacker news for years, this seems like a good reason do de-lurk. If anyone has questions, I'm happy to answer them. I wrote that summary for a pretty broad target audience, and the technical details are fun to explore.

kornish• 9 years ago

A warning to the reader: only a small fraction of the readings are actually available inline as PDFs; the rest seem to come from a handout which is not provided and the textbook Essentials of Game Theory.

Otherwise, seems like a cool foray for anyone interested in game theory.

Edit: I take it back! The Introduction to Counterfactual Regret Minimization pdf is actually here: http://cs.gettysburg.edu/~tneller/modelai/2013/cfr/cfr.pdf

Udo• 9 years ago

It seems to me that "regret" is just a different name for an objective/loss function that reflects the merits of an action over many events. It's something that you would consider anyway when designing certain algorithms. If that hunch is correct, I wonder how many people are using "CFR" without being aware of the proprietary name.

mijoharas• 9 years ago

I've also been struggling with this after reading a little bit about these regret minimisation models.

Can someone explain how there is any difference in these CFR model from a normal reinforcement learning algorithm where you just take your loss function as the "regret" in CFR terms?

VodkaHaze4• 9 years ago

CFR is based on the method of "regret matching", which is a policy update method. Roughly, it says every iteration, the probability you take an action is equal to the fraction of its cumulative counterfactual regret over total cumulative counterfactual regret for all actions.

The cool thing about it is that it provably converges to nash equilibrium in zero sum game, and to correlated equilibria in non-zero sum games.

mikebjohanson3• 9 years ago

Sure. Like I mentioned in a later post, I'm an author on several of the CFR papers. It is related to RL, and there are a few ways of interpreting CFR. If you have an RL background, then CFR is kind of "RL using an advantage function, but it converges in adversarial games." If you have a multiarm bandits background, then CFR is kind of "An independent multiarm bandit at each decision point, all learning at the same time."

CFR differs from standard RL in a few ways:

- Exploring the tree. CFR has many variants, many of which focus on using sampling to trade off between fast, narrow, noisy updates versus slow, broad, precise updates. The most sampling-heavy variant, called Outcome Sampling, traces a single path through the tree, as you would in RL. However, it doesn't converge nearly as quickly as other variants, like Vanilla (explore the whole tree on each iteration) or Chance Sampling (sample the cards, explore the whole action space). Since those variants consider all paths through the tree, you don't have an explore/exploit tradeoff anymore, as you normally would in RL.

- The "Counterfactual" part. Regret updates are weighted by the other agents' probability of taking you to a decision point. Or, equivalently: updates are weighted by the probability that you reach a decision, if you are trying to reach that decision (and all of your action probabilities along the way are 1). If you use Outcome Sampling (described above) then by sampling all actions that weight becomes 1, and thus less important. But for fast learning, the weighting becomes important.

- The strategy doesn't converge, but the average strategy does. Even in the limit, in an adversarial setting where all players are learning, the strategy produced from the regret values doesn't converge to Nash. If it was a single-player problem (either no opponents, or static opponents that can be treated as part of the environment), then as in RL, the strategy would converge to an optimal response to the environment. But in an adversarial setting, you also need the average strategy, which is the only part guaranteed to converge to optimal.

VodkaHaze4• 9 years ago

Not really, because CFR is not only taking regret as the loss function, but also the method of "regret matching". That is making the mixed strategy probabilities in the next iteration equal the cumulative counterfactual regret (which you keep track of while iterating).

noelwelsh• 9 years ago

Since you seem to know what I'm talking about, is the innovation here i) a new objective function (counterfactual regret) and ii) a method to optimise that objective (regret matching)? I'm familiar with bandit algorithms and reinforcement learning, and on a very quick skim could not work out the exact difference here.

usgroup• 9 years ago

Does anyone else read "counterfactual regret" and think "well that pretty much sums up most of why I'm ever anxious"?

TeMPOraL• 9 years ago

Yeah. That's the reason I actually clicked on the link.

GlennS• 9 years ago

Maybe you could try the learning program's approach?

Think about the memory that triggers regret/shame, then decide whether and what you should do differently in the future to make better decisions in similar situations.

After that, maybe you you can look back on the event as a "lesson well learned" instead of "ohmygodohmygodohmygod that's so embarassing I can't believe I did that I'll never open my stupid mouth again".

(No idea if this actually works.)

meesterdude• 9 years ago

well, its healthy to reflect on our past and try to do better in the future; it is not so to reflect on our past and use it as a means to punish us in the now or in the future.

The trouble stems from thinking you should have done something, and did not, and that you are somehow infallible. In truth, there are a lot of things one COULD do, but few are absolute SHOULD's.

My cat died very recently - and I've been working through the thinkings of if I could have been a better owner, if I reciprocated his unwavering love enough, if I could have caught his sickness sooner, if I was "good enough" and so on.

And yes. There ARE things I could have done differently. But I'm also a human being, and am not a saintly creature without fault or error or oversight. So to expect this ideal from myself in response to what I see as a faultless cat, is cruel punishment to dispense to oneself.

throwanem• 9 years ago

Darn! I was hoping for some sort of exciting new historiographical technique.

Dowwie• 9 years ago

I assume this has something to do with an AI beating world class poker champions recently..

poppingtonic• 9 years ago

Yes, I looked it up and found this source quite useful for getting a high-level idea of what the CMU team accomplished.

godmodus• 9 years ago

This gave and my Buddy a great laugh! Thank you! (were doing min max problems this semester! I will link this to my professor!)

shankun• 9 years ago

When I read "counterfactual regret minimization", I thought this would be about Kellyanne Conway.

An Introduction to Counterfactual Regret Minimization

Related Stories