acceptodds
Under review as a conference paper at ICLR 2027

Exact Averaging And Discounting for Monte Carlo Counterfactual Regret Minimization

Abstract

Counterfactual regret minimization (CFR) is the standard method for solving twoplayer zero-sum games with imperfect information, and its error bound concerns an average strategy that weights iteration t at an information set by the probability that the player’s own actions lead there. Tabular CFR accumulates that average exactly, whereas outcome-sampling Monte Carlo CFR updates only the information sets on one sampled playthrough per player and iteration, while the average keeps changing at the information sets it skips. The rules in use account for them differently, and which average they return depends on where they are applied. On the player’s own playthrough the opponent does not explore, so an information set can stay unvisited while its weight keeps growing. We show that the missed weight is already recorded in the player’s tables, as the growth of the exact sum at the predecessor’s action leading to the information set. Reading it at each visit, on the way down, and once at the end returns the exact reach-weighted average of the strategies the sampled run produced, for uniform, linear and polynomial weights alike. A prefix-product table replays skipped discount factors at one subtraction. The coefficient distortion of a skipped positive-regret factor is bounded when discounted CFR’s exponent exceeds one, and unbounded below that and for the strategy sum. On nine games from 12 to 524,288 information sets, our implementation of OpenSpiel’s rule returns strategies 1.7 to 9 times as exploitable as the exact average after 107 iterations, a gap that grows with training, while the opponent’s-playthrough rule stays within five per cent and the exact rule costs 0.3–4.5% more time. Both are cheap enough to be defaults for outcome-sampling implementations.

Primary area:
reinforcement learning
Keywords:
Imperfect Information Games, Reinforcement Learning, Monte Carlo Counterfactual Regret Minimization

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_cq9VOpenReview ↗
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
  1. 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?

  2. Can you try to explain why analysing outcome sampling MCCFR is still relevant for AI progress in 2026?

  3. 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

We thank the reviewer for the precise reading and for noting three strengths. We answer each weakness, suggestion and question in turn.

W1: 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.

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).

    game (external sampling, 10^7 iterations)seedsown information sets / exactseeds worseopponent nodes / exactseeds worse
    Kuhn poker101.06810/101.0005/10
    Leduc poker102.31910/100.9992/10
    Liar's Dice(1,4)101.8309/101.0005/10
    Leduc poker, kappa = 0.252013.22920/201.0009/20
  • 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.

W2: The practical improvement over pre-existing STOCH/OPP, measured in Table 1, is non-existent, and it does not even need the extra memory.

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:

gamekappaseedsSTOCH/OPP / exact95% bootstrap interval
Leduc poker0.35201.321.24 to 1.45
Leduc poker0.30201.581.39 to 1.83
Leduc poker0.25201.841.47 to 2.32
Leduc poker0.20201.471.16 to 1.97
Leduc poker0.15201.801.36 to 2.43
Liar's Dice(1,6)0.20401.091.03 to 1.15
Liar's Dice(1,6)0.15401.231.09 to 1.40
Liar's Dice(1,6)0.10401.301.04 to 1.69

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.

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:

gameseeds reaching the target, exactSTOCH/OPPp
Leduc poker, kappa = 0.3018 of 204 of 20< 0.001
Leduc poker, kappa = 0.2516 of 205 of 20< 0.001
Leduc poker, kappa = 0.1512 of 206 of 200.070
Liar's Dice(1,6), kappa = 0.1526 of 4018 of 400.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/OWNLWA / STOCH/OWN
Kuhn poker0.990.990.0001.0091.001
Leduc poker1.421.450.0001.0171.020
Goofspiel(4)1.431.430.0001.0031.013
Liar's Dice(1,4)1.331.340.0001.0061.027
Goofspiel(5)1.982.020.0001.0211.019
Liar's Dice(1,6)1.681.720.0011.0241.020
Goofspiel(6)3.283.420.0011.0451.013
Liar's Dice(1,7)1.761.790.0021.0171.026
Liar's Dice(1,8)1.942.010.0101.0441.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.

  1. 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).
  2. 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).
  3. 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).
  4. 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) / exactseeds worseAlg. 5 verbatim / exactseeds worse
Kuhn poker1.014/101.096/10
Leduc poker1.1210/101.2910/10
Goofspiel(4)1.168/101.428/10
Liar's Dice(1,4)1.218/101.187/10
pooled1.1230/401.2431/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.

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

This paper studies the averaging and discounting procedures in Monte Carlo Counterfactual Regret Minimization (MCCFR). The authors show that some existing averaging rules do not correctly recover the intended average strategy and propose a recurrence-based method that achieves exact averaging under perfect recall. They also introduce a prefix-product approach to account for skipped discount factors. Theoretical results establish the exactness of the proposed averaging method and analyze the behavior of existing rules. Experiments on nine imperfect-information games show improved exploitability over OpenSpiel's default averaging rule, with relatively small computational overhead.

Critical strengths

The paper identifies an interesting issue in how average strategies are accumulated in MCCFR. The proposed recurrence is simple and comes with an exactness guarantee (Theorem 1). The analysis of existing averaging rules in Propositions 1–3 is also useful. The experiments are relatively comprehensive. The authors compare several existing methods on the same regret trajectories, verify the exactness of their implementation against brute-force computation, and report relatively small computational overhead.

Critical weaknesses

My main concern is the unclear practical advantage over STOCH/OPP. Although the proposed method guarantees exact averaging, the STOCH/OPP method achieves nearly identical exploitability in most experiments (Table 1). While the authors show some cases where STOCH/OPP performs worse, it remains unclear how significant the additional practical benefit of exact averaging is over this existing alternative.

Questions for authors
  1. Could the authors further clarify the practical advantages of the proposed exact averaging method over STOCH/OPP? In particular, under what conditions does exact averaging lead to a meaningful improvement in strategy quality?

  2. The proposed recurrence relies on the unique predecessor structure under perfect recall. However, imperfect-recall abstractions are also important for reducing the complexity of large extensive-form games. Is it possible to extend the method to imperfect-recall games or abstractions?

3 comments

We thank the reviewer for the careful reading and positive assessment. Your suggestions are really helpful.

Weakness

My main concern is the unclear practical advantage over STOCH/OPP. Although the proposed method guarantees exact averaging, the STOCH/OPP method achieves nearly identical exploitability in most experiments (Table 1).

That is what we find on the nine uniform-chance benchmarks. Proposition 2 gives the reason: 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 these benchmarks exactness is a guarantee, not a speed-up. The revision splits Table 1 into an own-playthrough block and an opponent-playthrough block, and adds the paragraph "Where the placement is not enough". Together they show that moving the average repairs the stochastic increment only. The optimistic increment is the rule of the original MCCFR. At the same placement, it remains 1.06 to 1.62 times as exploitable on eight of nine games and worse on 15 to 20 of 20 seeds. Lazy-weighted averaging remains up to 1.43 times as exploitable.

While the authors show some cases where STOCH/OPP performs worse, it remains unclear how significant the additional practical benefit of exact averaging is over this existing alternative.

We added two experiments for this revision to measure that benefit. They show that under a skewed chance law, STOCH/OPP is 1.09 to 1.84 times as exploitable as the exact average. The exact rule reaches a fixed exploitability target in far more 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:

gamekappaseedsSTOCH/OPP / exact95% bootstrap interval
Leduc poker0.35201.321.24 to 1.45
Leduc poker0.30201.581.39 to 1.83
Leduc poker0.25201.841.47 to 2.32
Leduc poker0.20201.471.16 to 1.97
Leduc poker0.15201.801.36 to 2.43
Liar's Dice(1,6)0.20401.091.03 to 1.15
Liar's Dice(1,6)0.15401.231.09 to 1.40
Liar's Dice(1,6)0.10401.301.04 to 1.69

Every interval excludes one. At kappa = 0.25 on Leduc, STOCH/OPP is worse on 19 of 20 seeds. On Leduc, the ratio also grows with training. It is 1.08 to 1.14 at 10^5 iterations and 1.32 to 1.84 at 10^7.

Iterations to a target (new Table 2). For each game, the target is 1.2 times the median exploitability of the exact rule at 10^7 iterations. For each seed, both rules share one trajectory. We report p from the exact McNemar test:

gameseeds reaching the target, exactSTOCH/OPPp
nine uniform-chance games14 to 20 of 2013 to 20 of 20>= 0.25
Leduc poker, kappa = 0.3018 of 204 of 20< 0.001
Leduc poker, kappa = 0.2516 of 205 of 20< 0.001
Leduc poker, kappa = 0.1512 of 206 of 200.070
Liar's Dice(1,6), kappa = 0.1526 of 4018 of 400.021

The exact rule costs 0.3 to 4.5% more per iteration, so these are wall-clock comparisons within that margin.

The discount axis (Table 24). Under linear weighting, the exact average on the single-current-factor trajectory is 1.5 to 6.5 times as exploitable as on the replay trajectory. On either trajectory, STOCH/OPP stays within 0.99 to 1.01 of its own exact average. The placement therefore cannot recover the error made by the single-factor shortcut. In iterations to a target, the replay trajectory reaches 1.2 times its median in 17 to 20 of 20 seeds on four games. The single-factor trajectory reaches this in 0 to 2 (p < 0.001).

Questions

Q1: Could the authors further clarify the practical advantages of the proposed exact averaging method over STOCH/OPP? In particular, under what conditions does exact averaging lead to a meaningful improvement in strategy quality?

The condition is a chance law where rare deep branches keep their weight. The opponent's playthrough then visits them too rarely for the martingale error of Proposition 2 to average out within the budget. Under the uniform chance of the standard benchmarks, the error averages out. Leduc is the strongest instance. Its public card is dealt after the first betting round, so the tilt removes weight from the branches that carry the error. Liar's Dice(1,6) reproduces the effect at 40 seeds. Two further conditions do not depend on the chance law. For any weighted or discounted average, the exact weighted sum is the only well-defined target. In that case, the shortcut is 1.5 to 6.5 times as exploitable. For any increment other than the stochastic one, the placement does not help (1.06 to 1.62 on the standard benchmarks). Outside these cases, the exact rule provides a guarantee, at a cost of 0.3 to 4.5% more time and one number per information set. The revised Sections 1, 6 and 7 now state this directly.

Q2: The proposed recurrence relies on the unique predecessor structure under perfect recall. However, imperfect-recall abstractions are also important for reducing the complexity of large extensive-form games. Is it possible to extend the method to imperfect-recall games or abstractions?

Partly. We explain which part in new Appendix A.1 ("Imperfect recall", Proposition 7). The recurrence uses perfect recall twice. First, perfect recall gives every information set a single own-action predecessor, so the missed weight is the growth of one stored sum. Second, that predecessor lies on every playthrough that visits the set, so its table is current when read.

  • The identity survives. Suppose I can be entered through several own-action predecessors (J, b). Under two structural assumptions stated in the appendix, the weight accrued between two visits equals the summed growth of the stored sums at all predecessors. One watermark per information set then gives the exact average if the predecessor tables are current when read and the strategy at I has not changed since its last update. Proposition 7 gives this result with unchanged memory and one read per predecessor. A sweep over all information sets once per iteration satisfies both conditions. One predecessor is not enough. In a three-information-set example in the appendix, the exact sum at the shared set is (1.520, 1.330). Reading all predecessors returns this sum. Reading one returns (1.360, 0.940), an L1 error of 0.12 in the average.
  • Single-playthrough exactness does not. A playthrough that enters I does not visit predecessors on other branches, so their tables can be stale when read. In the same example, the visit-based rule returns (1.745, 1.105), an L1 error of 0.16. To obtain exactness from Proposition 7, a sampled implementation would also have to keep the unvisited predecessors current. We do not claim such a rule.
  • We do not run abstraction experiments because CFR's equilibrium guarantee is proved under perfect recall. Under imperfect recall there is no guaranteed target against which an averaging error could be measured. Extending both the guarantee and the rule to imperfect-recall abstractions is future work. The appendix states this boundary.

We thank the reviewer again for feedback that improved the paper on both counts. We would be glad to clarify anything further during the discussion period.

I thank the authors for their responses. The advantages over STOCH/OPP are convincing, and the discussion about extending the method to imperfect-recall games is helpful.

I have no further questions and will maintain my original score of weak acceptance.

Reviewer_s4mPOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how to compute the average strategy in outcome-sampling Monte Carlo Counterfactual Regret Minimization (MCCFR). An information set may still need to contribute to the average even when it is not visited. The paper proposes a simple update rule that recovers these missing contributions from the stored sum at the player’s previous decision point. It also gives a way to apply discount factors that were skipped between visits. The method computes the exact average of the strategies produced by the sampled run, rather than changing the learning rule itself.

Critical strengths
  1. The exact averaging method is simple and useful. The method reuses information already stored by the solver and needs only one extra number per information set. The paper proves that it recovers the exact average, including linear and polynomial weighted averages. It removes the error from estimating the average without changing the underlying regret updates.

  2. The experiments separate averaging errors from differences in training. The averaging rules share the same strategy sequence and sampled visits. This is a strong design because differences in the returned strategies can be traced to the averaging rules rather than different training runs.

Critical weaknesses
  1. The added practical benefit over STOCH/OPP is small on the main benchmarks. The large reported improvement over STOCH/OWN should be separated from the improvement over STOCH/OPP. In Table 1, after 10710^7 iterations, STOCH/OPP’s exploitability is only 0.99–1.01 times that of the exact method across all nine game settings. Thus, most of the measured improvement can already be obtained by changing where the stochastic average is updated. Exactness is valuable in itself, but the main benchmarks do not show a clear further improvement in strategy quality. A direct comparison of the time needed to reach the same exploitability would better establish the added practical value over this strong baseline.
  2. Limited evaluation on large-scale games. Although the proposed method is theoretically sound and computationally efficient, the experiments are limited to relatively small, tabular games. It remains unclear whether the method can be efficiently applied to large-scale imperfect-information games or modern function-approximation-based approaches such as Deep CFR, where maintaining exact strategy averages may be substantially more challenging.
Questions for authors

see weakness

2 comments

We thank the reviewer for an accurate summary and for singling out the shared-trajectory design. That design makes the new comparison below possible. We answer Weakness 1 sentence by sentence and Weakness 2 in its three parts.

Weakness 1

The added practical benefit over STOCH/OPP is small on the main benchmarks.

On the nine uniform-chance benchmarks, it is. By Proposition 2, on the opponent's playthrough, the visit probability is proportional to the weight. The error is therefore a martingale that averages out within the budget. The revised abstract says that on uniform-chance benchmarks, exactness is a guarantee, not a speed-up. The revised Section 7 states the condition under which exactness is more than a guarantee.

The large reported improvement over STOCH/OWN should be separated from the improvement over STOCH/OPP.

Table 1 now has two blocks: own playthrough (STOCH/OWN, OPT/OWN) and opponent's playthrough (STOCH/OPP, OPT/OPP, LWA). The placement effect is read across the blocks. The increment effect is read within the right block. The revised introduction and Section 6 report these two effects separately.

In Table 1, after (10^7) iterations, STOCH/OPP's exploitability is only 0.99–1.01 times that of the exact method across all nine game settings.

It is, at every checkpoint (0.99 to 1.05 at 10^5 and 10^6, Table 6). The submission reports it in those words in Section 6.

Thus, most of the measured improvement can already be obtained by changing where the stochastic average is updated.

For the stochastic increment, yes. The revision shows that this is a property of that one increment, not of the placement. At the same placement, the optimistic increment (the rule of the original MCCFR) is still 1.06 to 1.62 times as exploitable on eight of nine games. It is worse than the exact average on 15 to 20 of 20 seeds. Lazy-weighted averaging reaches up to 1.43 (Table 1, right block). Under a skewed chance law, the stochastic rule itself leaves its band. With 40 seeds per level, it reaches 1.32 to 1.84 on Leduc and 1.09 to 1.30 on Liar's Dice(1,6) (new Table 19). Under linear weighting, it tracks a target that is 1.5 to 6.5 times as exploitable as the replayed one (new paragraph "Where the placement is not enough").

Exactness is valuable in itself, but the main benchmarks do not show a clear further improvement in strategy quality.

We added that sentence to the abstract and the conclusion. We also added the complementary finding that the exact rule gives a measured advantage under a skewed chance law, the optimistic increment, or linear weighting.

A direct comparison of the time needed to reach the same exploitability would better establish the added practical value over this strong baseline.

We added this experiment (new Table 2 and the paragraph "Iterations to a target"). On the nine uniform-chance games, the exact rule and STOCH/OPP reach every target in the same seeds. This is the tie Proposition 2 predicts. Under a skewed chance law, the tie breaks. The exact rule reaches the target in 18 of 20 Leduc seeds, against 4 for STOCH/OPP.

For each game, we take the median over seeds of the exact average's exploitability at 10^7 iterations. The target is tau_c = c times this median, with c in {1.2, 1.5, 2, 3}. A seed reaches the target if its running minimum does so within the budget. On each seed, the two rules share one trajectory. We therefore compare them with the exact two-sided McNemar test on the discordant seeds. On the same runs, the exact rule costs 1.009 to 1.043 times as much as STOCH/OPP per iteration. Iterations to a target thus match wall-clock time to a target within that margin.

gametau_1.2reach Exact / STOCH/OPP / OPT/OPPp (Exact vs STOCH/OPP)tau_2reachp
Kuhn poker7.7e-416/13/160.251.3e-320/20/201
Leduc poker3.7e-219/19/1416.2e-220/20/201
Goofspiel(4)1.2e-315/13/40.502.0e-319/18/131
Liar's Dice(1,4)3.1e-314/14/815.2e-320/20/171
Goofspiel(5)8.5e-318/17/411.4e-220/20/201
Liar's Dice(1,6)5.9e-219/19/1819.8e-220/20/201
Goofspiel(6)3.3e-218/19/1615.4e-220/20/201
Liar's Dice(1,7)1.1e-120/20/2011.8e-120/20/201
Liar's Dice(1,8)1.6e-120/20/2012.6e-120/20/201
Leduc, kappa = 0.309.9e-318/4/1< 0.0011.7e-220/14/150.031
Leduc, kappa = 0.256.5e-316/5/1< 0.0011.1e-220/12/60.008
Leduc, kappa = 0.158.0e-412/6/10.0701.3e-319/10/20.004
Liar's Dice(1,6), kappa = 0.15 (40 seeds)9.0e-426/18/230.0211.5e-333/29/330.22

On the uniform-chance games, p >= 0.25 at every c. OPT/OPP reaches tau_1.2 in 4 of 20 seeds on Goofspiel(4) and (5). Under the skewed chance law, the exact rule reaches 1.2 times its median in 18 of 20 Leduc seeds against 4 for STOCH/OPP at kappa = 0.3. At kappa = 0.25, the counts are 16 against 5. On Liar's Dice(1,6) at kappa = 0.15, the counts are 26 of 40 against 18. On four games, we apply the same protocol on the discount axis (Section 6, "Weighted and discounted averages"). This gives 17 to 20 of 20 seeds for linear-CFR replay, against 0 to 2 for the single-factor shortcut.


Weakness 2

Limited evaluation on large-scale games. Although the proposed method is theoretically sound and computationally efficient, the experiments are limited to relatively small, tabular games.

We added an experiment on Goofspiel(7), the largest tabular instance we can expand (new Table 16 and one sentence in Section 6). It has 47,506,635 histories, 667,896 information sets, and 1,433,586 strategy-sum entries. The results of the nine smaller games carry over to this scale. At 10^7 iterations, OpenSpiel's default rule is 1.33 times as exploitable as the exact average, worse on every seed and still growing. The exact rule costs 1.040 times as much time as the default rule.

iterations (Goofspiel(7), 10 seeds)STOCH/OWN / exactseeds worseSTOCH/OPP / exactseeds worseOPT/OPP / exactseeds worse
10^51.0509/100.9994/100.9923/10
10^61.10310/101.0036/101.0096/10
10^71.33210/101.0039/101.0238/10

The timing comes from separate runs of 10^6 iterations with each rule implemented alone. The run uses 2.9 GiB of memory including the tree. The cost ratio of the nine small games therefore holds at 1.4 million entries.

It remains unclear whether the method can be efficiently applied to large-scale imperfect-information games

The cost is one stored number per information set, one read of the predecessor's row per visit, and one closing pass over the visited sets. Proposition 6 gives the read-out for sparse tables, where never-visited sets are not materialised. Goofspiel(7) shows that this cost is affordable at 47.5 million nodes. For imperfect-recall abstractions, Appendix A.1 gives the multi-predecessor identity and a proposition for the full-table setting. It also explains why single-playthrough exactness does not carry over.

or modern function-approximation-based approaches such as Deep CFR, where maintaining exact strategy averages may be substantially more challenging.

We do not claim the recurrence for function approximation. We did not run Deep CFR because the recurrence has no quantity to read there. The recurrence reads the exact partial sum that a predecessor row accumulated between two visits. Deep CFR's average is a regressor fitted to a reservoir of sampled (information set, strategy, weight) tuples. Neither the reservoir nor the network stores the predecessor's growth. The diagnosis still transfers: a per-visit accumulator gives the wrong weight to the iterations in which an information set was not visited. This can be tested on any sampler whose average is a table. We added an experiment testing this on external sampling, the sampler Deep CFR's traversals are built on (new Tables 14 and 15). The same placement effect appears there. On the traversing player's own information sets, a per-visit average is 1.05 to 2.13 times as exploitable as the exact average. It reaches a fixed target in 0 of 20 Leduc seeds, versus 20 for the exact average. At the opponent's nodes, the standard average stays within 0.1% of the exact one. Our rule is exact under external sampling as well (new Corollary 1).

game (external sampling, 10^7 iterations, 20 seeds)own-information-set per-visit average / exactseeds worseseeds reaching 1.2 times the exact median, exactper-visit
Kuhn poker1.0519/2020 of 2020 of 20
Leduc poker2.1320/2020 of 200 of 20
Liar's Dice(1,4)1.8619/2019 of 207 of 20

We thank the reviewer once more. The paper now includes the time-to-target comparison. We would be glad to add anything further during the discussion period. We hope the new results encourage the reviewer to reconsider the rating.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General response to all reviewers and the Area Chair: summary of revisions

We thank the three reviewers for their careful reading and for converging on the same question: what does the exact average buy over the opponent-playthrough stochastic rule (STOCH/OPP), and when? The revised PDF answers it directly with the new experiments the reviewers asked for. Substantive changes are marked in blue.

One-paragraph answer. Changing where the stochastic average is accumulated fixes one increment on uniform-chance benchmarks. There, STOCH/OPP and the exact average stay within 0.99 to 1.05 of each other. Proposition 2 explains why. On the opponent's playthrough, the visit probability is proportional to the weight, and the error is a martingale. The exact rule is the only rule that is exact for every increment, placement, weighting and chance law. The revision reports three settings in which this exactness is also a measured advantage. (i) At the same placement, the optimistic increment (the original MCCFR rule) stays 1.06 to 1.62× as exploitable on eight of nine games. It is worse on 15 to 20 of 20 seeds. (ii) Under a skewed chance law, STOCH/OPP reaches 1.32 to 1.84× on Leduc (20 seeds per level) and 1.09 to 1.30× on Liar's Dice(1,6) (40 seeds per level), growing with training. (iii) Under linear weighting, the single-current-factor discount is 1.5 to 6.5× as exploitable as exact replay. STOCH/OPP cannot recover it because it tracks the wrong target. On uniform-chance benchmarks, exactness is a guarantee that costs 0.3 to 4.5% more time and one number per information set.

AuthorsOpenReview ↗

Changes to the paper (all in blue)

#Location in revised PDFChangeRaised by
1Abstract"within five per cent" replaced by the measured 0.99 to 1.05 (uniform chance) and 1.32 to 1.84 (skewed chance). Added "on uniform-chance benchmarks exactness is a guarantee, not a speed-up"cq9V W2/Q1, hQEs W, s4mP W1
2Abstract. Section 1. Section 4 (after Theorem 1)The scope is stated as Monte Carlo CFR: the problem is how a visit-based average accounts for the iterations an information set missed. The analysis is under outcome sampling, and both the gap and the exact rule carry over to external sampling (proof remark in Section 4, check against brute force in Appendix B)cq9V W1/Q2
3Section 1, contribution list. Appendix A, Table 4Contributions restated as specific results. New table separating prior material (K1 to K5) from what the paper adds (N1 to N9)cq9V W3
4Section 6, Table 1Split into an own-playthrough block and an opponent-playthrough block, so the placement effect and the increment effect are read separatelys4mP W1
5Section 6, new paragraph "Where the placement is not enough"Optimistic increment at the opponent placement 1.06 to 1.62× (15 to 20/20 seeds). Skewed chance on Liar's Dice(1,6) with 40 seeds (Table 19). Ratio growing with training on Leduc. Discount axis. External samplingcq9V W2/Q1, hQEs W/Q1, s4mP W1
6Section 6, new paragraph and Table 2 "Iterations to a target"The direct comparison s4mP asked for: seeds reaching a fixed exploitability target, exact McNemar test, nine uniform-chance games and four skewed cells. Per-iteration costs4mP W1, hQEs W
7Section 6, "Weighted and discounted averages"Iterations-to-target reading of the discount axis (linear CFR replay vs single factor, four games)cq9V W1, s4mP W1
8Section 6, cost paragraphMemory account (exact +1 number per information set, 21 to 25%, LWA +50%, STOCH/OPP +0). Goofspiel(7) at 47.5 M nodes, 10 seeds (Table 16)cq9V W2/S2, s4mP W2
9Section 7Closing sentence stating the condition under which exactness is a measured advantages4mP W1
10Appendix A, "Lazy-weighted averaging" (p. 14) and Table 3What Alg. 5 lines 22 and 30 each do. Which branch our LWA column runs. The verbatim two-branch implementation and its result (1.24 against 1.12 times as exploitable as the exact average)cq9V Q3
11Appendix A.1 "Imperfect recall", Proposition 7Multi-predecessor identity under two structural assumptions, a proposition stating when one watermark per information set is exact, a three-information-set example, and what does not carry over to sampled playthroughshQEs Q2
12Section 4 and Appendix A (Corollary 1). Appendix B, Tables 14 and 15The recurrence is exact under external sampling (corollary with proof, checked against brute force). Table 14: a per-visit average on the traversing player's own information sets against the exact one, 20 seeds, three games. Table 15: the same placement effect as under outcome sampling, with the standard opponent-node average within 0.1% of exactcq9V W1/Q2, s4mP W2
13Appendix B, Table 16Goofspiel(7), 10 seeds, three checkpoints and timings4mP W2
14Appendix B, Table 19 and the tilt paragraphLiar's Dice(1,6) under skewed chance, 40 seeds. Growth with training on LeduchQEs W/Q1
15Appendix B, Table 26LWA timing column and memory sentencecq9V suggestion
16Figures 1, 2, 4 and 5Re-exported at their placed width so the type is legible. Figure 2 is now at full text width, and Figures 4 and 5 use a 3 by 3 grid. Figures 2 and 4 now show exploitability on a linear axis from 10^5 iterations on, where the rules separate. The data are unchangedcq9V, s4mP (Presentation)
17Section 6 (one sentence). Appendix B, new paragraph "More than two players" and Table 27Added during the discussion: seven games with three to six players (Kuhn poker with three to six players, three-player Leduc poker and three-player Goofspiel). The average of OpenSpiel's outcome-sampling solver against the exact average of the same run, 40 seeds per gamecq9V (follow-up)
18Appendix B, new paragraph "Neural averaging" and Figure 6Added during the discussion: a diagnostic on our reimplementation of DREAM and outcome-sampling Deep CFR. Deep CFR's average network against the exact average of the iterates at twelve checkpoints of the same runs, 10 seedscq9V (follow-up)

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.