- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper thoroughly studies various methods for computing the average strategy in the Outcome Sampling MCCFR family of game solving algorithms. It generalizes it to CFR variants with non-uniformly weighted iterations and provides an empirical comparison of different averaging variants on a range of smaller imperfect information games. It analyzes the existing methods in more depth and introduces a cleaned up, theoretically correct version of the averaging that is reasonably cheap so that it might be used as the default in Outcome Sampling MCCFR variants that explicitly store the game tree. The sufficiently wide empirical evaluation shows that even though the proposed method is more theoretically correct than the pre-existing ones, it does not translate to better empirical performance.
Critical strengths
- The paper brings a very thorough and clean analysis of MCCFR averaging.
- It identifies limitations in the existing variants and proposes a new variant of averaging that is proven to be theoretically correct and with lower memory overhead than previous proposal.
- The experimental evaluation is on a wide range of different games.
Critical weaknesses
- The paper studies outcome sampling MCCFR in a tabular setting, an algorithm that is certainly interesting theoretically, but has never been empirically useful and has not been considered for any practical purposes for more than 5 years. The algorithm has been superseded by other game solving approaches.
- The practical improvement over pre-existing STOCH/OPP, measured in Table 1, is non-existent, and it does not even need the extra memory.
- The paper is rather unclear about what exactly is new and what has been known already. Most of the results are cleaned-up versions of the known facts. They are certainly executed much more thoroughly, but the few novel pieces are hard to find among the many clean-ups of the known ones.
This is not a "Critical Weakness", but I did not find another place to write suggestions:
- Consider adding LWA to the timing table and state the memory difference for completeness
Questions for authors
-
Given that STOCH/OPP matches the exact average to within 1% in exploitability at equal cost, what is the practical case for using Algorithm 1 with extra memory cost?
-
Can you try to explain why analysing outcome sampling MCCFR is still relevant for AI progress in 2026?
-
The paper describes LWA as running "on the opponent's playthrough, its original placement" (line 368). The thesis prose does say averages are updated "on the opponent's turns" (p. 47). But Alg. 5 as printed updates s_I on both branches: line 22 at the update player's nodes and line 30 at the opponent's nodes. Which version did the authors implement and why?
8 comments
Iterations to a target (new Table 2). The target is 1.2 times the exact rule's median exploitability at 10^7 iterations. For each seed, both rules share one trajectory. Here, p comes from the exact McNemar test:
| game | seeds reaching the target, exact | STOCH/OPP | p |
|---|---|---|---|
| Leduc poker, kappa = 0.30 | 18 of 20 | 4 of 20 | < 0.001 |
| Leduc poker, kappa = 0.25 | 16 of 20 | 5 of 20 | < 0.001 |
| Leduc poker, kappa = 0.15 | 12 of 20 | 6 of 20 | 0.070 |
| Liar's Dice(1,6), kappa = 0.15 | 26 of 40 | 18 of 40 | 0.021 |
The placement also repairs only the stochastic increment and only the uniform weighting (new paragraph "Where the placement is not enough" and the split Table 1). The optimistic increment at the same placement is the rule of the original MCCFR (Alg. 3). This rule remains 1.06 to 1.62 times as exploitable on eight of nine uniform-chance games. It is worse than the exact average on 15 to 20 of 20 seeds. Lazy-weighted averaging also remains up to 1.43 times as exploitable. Under linear weighting, STOCH/OPP tracks its own exact average within 0.99 to 1.01. However, that average is 1.5 to 6.5 times as exploitable as the replayed one, so the placement cannot recover a discount.
W3: The paper is rather unclear about what exactly is new and what has been known already. Most of the results are cleaned-up versions of the known facts. They are certainly executed much more thoroughly, but the few novel pieces are hard to find among the many clean-ups of the known ones.
We apologise that the boundary was unclear. The revision draws it in two places. Table 4 in Appendix A lists what was known and what is new, with the location of each item. The contribution list in the revised Section 1 states each contribution as a specific result.
Known before this paper, and not claimed by us:
- the reach-weighted target and the unbiasedness of sampled regrets (Lanctot et al., 2009)
- the optimistic increment on the opponent's turns (thesis, Alg. 3)
- lazy-weighted averaging and its 50% memory cost (Alg. 5, Section 4.4)
- OpenSpiel's own-playthrough placement
- discounted CFR's per-iteration factors in full-tree runs
New in this paper:
- The missed weight at an information set equals the growth of the stored exact sum at its predecessor. This gives a visit-based rule that is exact for the run produced (Lemma 1, Theorem 1).
- The same rule is exact for weighted and polynomial averages, with no factor applied to the table (Section 4.2).
- Skipped discount factors are replayed with a prefix product. The single-factor shortcut has a bounded error in some regimes and an unbounded one in others (Propositions 4 and 5).
- We identify what the stochastic increment targets on each playthrough (Propositions 1 and 2) and give a concentration bound (Proposition 3).
- The rule has a read-out for sparse tables (Proposition 6).
- All rules are measured on one shared trajectory, with the exact rule checked against brute force. We also measure the consequence in OpenSpiel's own solver.
- Lazy-weighted averaging is not exact, and we identify the term that breaks it (Appendix A).
Every sentence in the revision that calls a result new now points to one of these items.
Suggestion: Consider adding LWA to the timing table and state the memory difference for completeness
We added LWA to the timing experiment (Table 26, new last column). The two rules cost the same time, at 1.001 to 1.033 times STOCH/OWN for LWA and 1.003 to 1.045 for the recurrence. However, the recurrence needs half the extra memory. It uses one number per information set (21 to 25% of the tables), compared with one weight per state-action pair (50%) for LWA. The text accompanying the table now states this memory usage.
| game (10^6 iterations, median of 5 runs) | STOCH/OWN (s) | recurrence, training (s) | closing pass (s) | recurrence / STOCH/OWN | LWA / STOCH/OWN |
|---|---|---|---|---|---|
| Kuhn poker | 0.99 | 0.99 | 0.000 | 1.009 | 1.001 |
| Leduc poker | 1.42 | 1.45 | 0.000 | 1.017 | 1.020 |
| Goofspiel(4) | 1.43 | 1.43 | 0.000 | 1.003 | 1.013 |
| Liar's Dice(1,4) | 1.33 | 1.34 | 0.000 | 1.006 | 1.027 |
| Goofspiel(5) | 1.98 | 2.02 | 0.000 | 1.021 | 1.019 |
| Liar's Dice(1,6) | 1.68 | 1.72 | 0.001 | 1.024 | 1.020 |
| Goofspiel(6) | 3.28 | 3.42 | 0.001 | 1.045 | 1.013 |
| Liar's Dice(1,7) | 1.76 | 1.79 | 0.002 | 1.017 | 1.026 |
| Liar's Dice(1,8) | 1.94 | 2.01 | 0.010 | 1.044 | 1.033 |
Q1: Given that STOCH/OPP matches the exact average to within 1% in exploitability at equal cost, what is the practical case for using Algorithm 1 with extra memory cost?
There are four cases. In each, the exact rule costs 0.3 to 4.5% more time and one number per information set.
- When a guarantee is needed. The exact rule is exact for every increment, placement, weighting and chance law, and we checked it against brute force to 10^-9 on all nine games. The agreement of STOCH/OPP is an empirical property of uniform-chance benchmarks (Weakness 2 above).
- Under a skewed chance law. STOCH/OPP is 1.09 to 1.84 times as exploitable and reaches a fixed target in a minority of seeds (Table 2, Table 19).
- For any weighted or discounted average. The single-factor shortcut is 1.5 to 6.5 times as exploitable as the exact weighted average, and STOCH/OPP at that placement tracks the shortcut's target (Table 24, Section 6).
- For any other increment. The optimistic and lazy-weighted rules at the same placement are 1.06 to 1.62 times as exploitable on the standard benchmarks (Table 1, right block).
Q2: Can you try to explain why analysing outcome sampling MCCFR is still relevant for AI progress in 2026?
The problem is not tied to one solver. Every sampled CFR method updates an information set only when it visits it, and must decide how much weight the average receives for the iterations in between. As shown under Weakness 1, this decision affects external sampling, linear and discounted CFR under sampling, and the default solver of a widely used library. The paper measures the error of the rules in use and gives the exact rule.
Q3(a): The paper describes LWA as running "on the opponent's playthrough, its original placement" (line 368).
The phrase "its original placement" refers to the placement prescribed for the averaging rules in the thesis prose (p. 47, "on the opponent's turns") and used in Alg. 3. It does not refer to a property of Alg. 5 as printed. The revised Section 6 (Setup) now reads "the opponent branch of Alg. 5, lines 25 to 32". Appendix A (p. 14, blue paragraph) gives the full account.
Q3(b): The thesis prose does say averages are updated "on the opponent's turns" (p. 47). But Alg. 5 as printed updates s_I on both branches: line 22 at the update player's nodes and line 30 at the opponent's nodes.
Both lines are as the reviewer reads them. They do not conflict. Each line updates the strategy sum of the player who owns the information set at that node. Line 22 maintains the update player's sum on its own branch. Line 30 maintains the opponent's sum on the opponent branch. Our LWA column runs lines 25 to 32. As a result, each player's sum is accumulated on the other player's playthrough. This matches the placement in the thesis prose and in Alg. 3. Lines 13 to 24 were not implemented in the submitted experiments.
Q3(c): Which version did the authors implement and why?
The opponent branch, for the reason above. For this revision, we also implemented Alg. 5 verbatim (both branches). We checked it against an independent implementation, which returns identical tables. Neither version is exact. The verbatim algorithm is further from the exact average than the branch we reported. Pooled over four games, it is 1.24 times as exploitable, compared with 1.12. Appendix A reports the comparison. Table 3 now carries both rows.
| game (10^7 iterations, 10 seeds) | opponent branch (lines 25 to 32) / exact | seeds worse | Alg. 5 verbatim / exact | seeds worse |
|---|---|---|---|---|
| Kuhn poker | 1.01 | 4/10 | 1.09 | 6/10 |
| Leduc poker | 1.12 | 10/10 | 1.29 | 10/10 |
| Goofspiel(4) | 1.16 | 8/10 | 1.42 | 8/10 |
| Liar's Dice(1,4) | 1.21 | 8/10 | 1.18 | 7/10 |
| pooled | 1.12 | 30/40 | 1.24 | 31/40 |
We thank the reviewer for the time spent on the paper. In particular, the question on Alg. 5 led to a cleaner statement than the one we submitted. We would be glad to run any further check during the discussion period. We hope the revised framing and the new measurements are enough for the reviewer to reconsider the rating.
We thank the reviewer for the precise reading and for noting three strengths. We answer each weakness, suggestion and question in turn.
Thank you for pointing out that the submitted introduction could be read as a study of one solver. Our subject is a problem that every sampled CFR solver faces. An information set is updated only when visited, so each visit must decide how much weight the average receives for the iterations it missed. The errors we measure and the rule we propose apply to this problem. Outcome sampling is the setting where we can isolate it. Outcome sampling follows one playthrough per iteration, so every averaging rule can run on the same regret trajectory. Any difference between two rules is then caused by the averaging alone.
Three facts show that the problem reaches beyond tabular outcome sampling.
It appears under external sampling, with the same placement effect. We added an external-sampling experiment for this revision (new Tables 14 and 15). A per-visit average on the traversing player's own information sets is 1.07 to 2.32 times as exploitable as the exact average, and 13.2 times under a skewed chance law. The standard average at the opponent's nodes stays within 0.1%. Our analysis explains why that placement is sound. Our rule is exact there as well (new Corollary 1).
It appears in linear and discounted CFR under sampling. This is the setting of the Pluribus blueprint (Brown and Sandholm, 2019). Applying only the current discount factor at a visit is 1.5 to 6.5 times as exploitable as replaying the skipped factors (Table 24). Our rule replays them with one subtraction per visit.
It is in shipped code. OpenSpiel's own outcome-sampling solver returns a Leduc average 1.41 times as exploitable as the exact average of the same run (Table 13).
Model-free deep methods such as DREAM approximate outcome-sampling CFR (Steinberger et al., 2020), so they face the same accounting question. We make no claim for function approximation. The revised Section 1 (paragraph 3) now states this scope.
On the nine uniform-chance benchmarks, STOCH/OPP is within 0.99 to 1.05 of the exact average at every checkpoint. It stores nothing extra, as the submitted paper reports (Section 6, "The opponent's playthrough fixes the stochastic rule"). Proposition 2 explains why: on the opponent's playthrough, the visit probability is proportional to the weight, and the error is a martingale. The revised abstract now says that on uniform-chance benchmarks, exactness is a guarantee, not a speed-up. The exact rule adds one number per information set to memory. On the nine games, this added memory is 21 to 25% of the regret and strategy-sum tables (4.2 MB on top of 16.8 MB for Liar's Dice(1,8)). It is half of what lazy-weighted averaging stores (revised cost paragraph in Section 6 and Table 26).
We added two experiments for this revision. They show that the agreement in Table 1 is specific to one increment under uniform chance. When the chance law is skewed, STOCH/OPP is 1.09 to 1.84 times as exploitable as the exact average and reaches a fixed target in far fewer seeds.
Skewed chance law (Table 18 and new Table 19). Ratio of STOCH/OPP to the exact average of the same run at 10^7 iterations:
Every interval excludes one. On Leduc, the ratio also grows with training. At 10^5 iterations it is 1.08 to 1.14, and at 10^7 it is 1.32 to 1.84.