I'm currently trying to understand the counterfactual regret minimization algorithm as presented in this document: http://modelai.gettysburg.edu/2013/cfr/cfr.pdf.

I think I have a good understanding of the math and formulas used but there are still some pieces that I am struggling to understand in the whole algorithm as described in the document :

enter image description here

As far as I understand, the counterfactual regret is computed as :

$$R_{i}^{T}(I, a)=\sum_{t=1}^{T} r_{i}^{t}(I, a)$$


$$ r(I, a)=\sum_{h \in I} r(h, a) $$


$$ r(h, a)=v_{i}\left(\sigma_{I \rightarrow a}, h\right)-v_{i}(\sigma, h) $$

and finally

$$ v_{i}(\sigma, h)=\sum_{z \in Z, h \sqsubset z} \pi_{-i}^{\sigma}(h) \pi^{\sigma}(h, z) u_{i}(z) $$

In Algorithm 1, from line 15 to 21 we compute the counterfactual value using equation number 4 for each action available.

Then at line 25, we compute the counterfactual value for each action of the game state h we correspond to equation 3. However, it seems that equation 2 is missing in algorithm 1, that is, we compute regret for game state and then update the strategies instead of computing the regret for the entire Infoset (sum over all game state in the Infoset). So actually we update the strategy according to the regret of game state and not Infoset so it seems to me that we should sum the regret of the game state in the Infoset before updating. Is there something I'm missing?

Side question: in the actual C++/Python implementation at line 17 and 19, we multiply the CFR by -1. I don't understand why. Thanks in advance for any explanation.

  • $\begingroup$ Hello. Could you please put your main specific question in the title? $\endgroup$ – nbro Apr 3 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.