acceptodds
Under review as a conference paper at ICLR 2027

What Does the Average Strategy of Monte Carlo CFR Actually Average?

Abstract

Counterfactual regret minimization solves two-player zero-sum games with hidden information. Its guarantee holds for the exact average, which weights each iteration at an information set by the player's own reach probability. However, outcome-sampling solvers update an information set only when a sampled traversal visits it. The original sampling algorithm adds all iterations since the previous visit at the current weight; OpenSpiel adds only the current iteration divided by its sampling probability. We follow OpenSpiel's default sampling: one traversal per player, where only the traversing player explores at a fixed rate. On three of four games, both rules are on average ten to just over fifty percent more exploitable than the exact average after a hundred thousand iterations. After ten million, both are on average two to eight times as exploitable. Since the opponent never explores on the player's traversal, an information set can stay unreached while its weight grows. Adding on the opponent's traversal instead leaves OpenSpiel's rule on average at most two percent worse than the exact average. We prove that an information set's weight between visits is the growth of the exact average's sum at the player's preceding decision, for the action leading there. Reading that growth on the player's traversal at every visit and at the end returns the exact average for at most five percent more training time in our implementation.

Primary area:
learning theory
Keywords:
counterfactual regret minimization, Monte Carlo CFR, outcome sampling, average strategy, extensive-form games, exploitability, exploration

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_XiJ9OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper analyzes the average-strategy update of MCCFR. The paper shows the code in OpenSpiel is not right and give some theory of why it works. The paper proposes the parent-read rule, and shows the advantage of the method.

Critical strengths
  1. The defect lives in a default of a widely used implementation and in the published pseudo-code; the paper characterizes it precisely and provides a fix that is essentially free.

  2. The paper gives some useful theory for MCCFR solving.

  3. The reproducibility is good.

Critical weaknesses
  1. The headline problem largely disappears under external sampling (ES). The good results comes entirely from outcome sampling (OS) with one-sided exploration. Under ES the default rule is at most 7.9% below the exact average on Openspiel, so there is nothing urgent to fix. Considering ES is a more practical method in MCCFR, the good results are not good in the real world. If the method only works on OS, it should shows the good results work beyond tabular. The paper needs to improving neural settings OS MCCFR [1] (large game), or showing its MCCFR works better than any other tabular CFR methods (small/medium game).

  2. The novelty is limited and the related-work coverage needs to be sharpened. The original MCCFR is not right has been known since 2013 [2], in which also proposed a fix method. The paper should state explicitly what was unknown beyond prior works. The pruning family [3-6] is not discussed although "deliberately skipping iterations plus compensation" is exactly the window/tail setting. Recent MCCFR sampling methods should be discussed [7].

  3. The empirical claims are narrower than the paper's framing. The good results are all shown on three small games. The largest game works not so good. And the paper's own data show rules ending below the exact average.

[1] S. McAleer, G. Farina, M. Lanctot, and T. Sandholm. ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regret. ICLR 2023.

[2] M. Lanctot. Monte Carlo Sampling and Regret Minimization for Equilibrium Computation and Decision-Making in Large Extensive Form Games. PhD thesis, University of Alberta, 2013.

[3] N. Brown and T. Sandholm. Regret-Based Pruning in Extensive-Form Games. NeurIPS 2015.

[4] N. Brown and T. Sandholm. Reduced Space and Faster Convergence in Imperfect-Information Games via Pruning. ICML 2017.

[5] N. Brown, C. Kroer, and T. Sandholm. Dynamic Thresholding and Pruning for Regret Minimization. AAAI 2017.

[6] B. Li and L. Huang. Efficient Online Pruning and Abstraction for Imperfect Information Extensive-Form Games. ICLR 2025.

[7] B. Li, Y. Chen, and L. Huang. Correlated Chance Sampling for Monte Carlo Counterfactual Regret Minimization. arXiv 2026.

Questions for authors
  1. Can you extend your method to external sampling? What does parent-read do there?

  2. Can you report gap-vs-iterations curves on the larger instances rather than a single time point, to show whether the growth trend persists?

  3. Can your method be applied to Deep CFR or Escher like method?

Reviewer_D8JUOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper explains and compares various rules to update the average strategies in outcome sampling MCCFR, a sample-based variant of Counterfactual Regret Minimization, the leading solver for two-player zero-sum games of imperfect information (and largely successful in applications to Poker AI).

Due to MCCFR being a sample-based version of CFR, and outcome-sampling being the most aggressively sampled variant, how the average is updated can have a significant effect on the exploitability of the approximated average. The paper compares several different rules, proving theoretical properties and demonstrating the effects in practice.

Critical strengths

The knowledge of the strengths of the various choices of average strategy in outsome sampling MCCFR have not been well-communicated in the literature on MCCFR, so having a paper directly addressing this in detail is a valuable contribution. To the best of my knowledge, experiments comparing the effects in practice are limited to comparing only the two standard rules in Lanctot 2013 and Gibson's thesis, and none have been compared to the exact average. Hence, the results in this paper directly point to a best choice for averaging in outcome sampling MCCFR which should be adopted as the default (with one small caveat on the novelty... see Questions For Authors section).

With presentation issues fixed, this paper is a valuable exposition of the properties and effects of the different rules for average strategy computation in outcome-sampling MCCFR.

Critical weaknesses

While I think the content of this paper is valuable to the computational game theory community and should be made public, it's not clear that the target community is well-represented at ICLR which is has a broad machine learning audience. This paper may be a niche topic and set of results at ICLR.

Presentation is a bit rough. The authors assume too much of the reader (especially for the ICLR audience, which may not be intimately familiar with these formalisms and algorithms.)

Examples:

  • second sentence of the abstract: "Its guarantee holds for the exact average, which weights each iteration at an information set by the player’s own reach probability" Exact average what? Weights what each iteration? There are specific answers to these that are impossible to explain in the second sentence of the abstract.

  • "In that average each iteration counts at a set in proportion to the player’s own reach: the probability of the player’s own earlier actions on the path there, leaving out the opponent’s actions and chance" This is awkward, unclear, and much too early. Each probability of the average strategy \bar{\sigma}^(I,a) is a weighted sum where each weight is a product of probabilities up to I of that player's strategy at time t. This is cumbersome to explain informally; I suggest just waiting until there's more formality. The first line is not correct; it's referring to a specific decision point I but expressed as a weight for the entire strategy"

  • Similarly for page 2. This entire example should be presented only after the EFG definition on page 3, and ideally after CFR or MCCFR is described. Assuming the ICLR audience is familiar with extensive-form games or (MC)CFR is a bit too difficult. A reader unfamiliar with information sets, strategies, how to average strategies in behavioral strategies will be unable to follow this.

  • Start of Section 3: "where the tail weight w_{tail} is the same sum over the tail". I think there's an assumption here that K is the last timestep that I is reached/updated (i.e. that it's not reached between K and T) but that's never stated.

Questions for authors

Question: could the impact of this paper be similar if this paper was published as a technical report and shared with MCCFR authors and OpenSpiel maintainers? I would like the authors to justify their choice of ICLR for this paper.

Not a question, but a comment (in particular, this is not a criticism -- hence including in this section rather than Strengths / Weaknesses): The fact that the updating the average strategy on the opponent's history was largely known among MCCFR practicitioners, thanks to Gibson et al. 2012. In fact, most implementations of outcome sampling did have the update on the opponent's history (even in OpenSpiel, originally the Python implementation had the average strategy update on the opponent's history, e.g. see https://github.com/google-deepmind/open_spiel/blob/v0.2.0/open_spiel/python/algorithms/outcome_sampling_mccfr.py, however it is indeed a bug/oversight in the C++ implementation had it on the exploring player's own history.. I suspect this was not intended by the original contributor). Given these results, both OpenSpiel implementations should be reverted back to updating on the opponent's history. I encourage the authors to do this and to cite this paper in the code once it is widely available.

Reviewer_y1LkOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies update rules that have been proposed for outcome-sampling MCCFR. It raises interesting issues with careful small examples, and proves which of the rules are correct and which aren't. It then shows with appropriate standard benchmark games how the incorrectness manifests in practice and how it scales.

Critical strengths

The paper raises interesting careful points about outcome-sampling MCCFR rules that have been presented in prior literature but which have not been fully understood.

This seems like a sound contribution that the community should know.

Critical weaknesses

No critical weaknesses as far as I can tell based on a quick read. I did not check the proofs.

I would have liked to see an expanded version of Section 6, that is, more elaboration of how the new understanding from the present paper affects (if at all) the results of the papers discussed in Section 6. That said, I do understand the space constraint.

Questions for authors

How does the new understanding from the present paper affect (if at all) the results of the papers discussed in Section 6?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.