Pith. sign in

REVIEW 3 major objections 3 minor 1 cited by

On the Power of Perturbation under Sampling in Solving Extensive-Form Games

T0 review · 3 major / 3 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper establishes that a Reverse KL-based payoff perturbation for FTRL yields an unbiased estimator with conditional zero variance in the perturbation term under outcome sampling, and that this variance reduction improves last-iterate…

desk verdict The zero-variance observation for RKL perturbation is real and worth publishing; the controlled experiment doesn't fully isolate it, but the paper is honest and deserves review. read the letter →

arxiv 2501.16600 v2 pith:RS7I422Q submitted 2025-01-28 cs.GT cs.LGcs.MA

Wataru Masaka , Mitsuki Sakamoto , Kenshi Abe , Kaito Ariu , Tuomas Sandholm , Atsushi Iwasaki This is my paper · ORCID
classification cs.GTcs.LGcs.MA MSC 91A2691A10
keywords extensive-formgameslast-iterateconvergenceFollow-the-Regularized-LeaderpayoffperturbationoutcomesamplingReverseKLdivergencezero-varianceestimatorNashequilibrium
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks whether payoff perturbation can keep Follow-the-Regularized-Leader (FTRL) algorithms from cycling or diverging when payoffs are estimated from single sampled trajectories, the noisy feedback regime in which optimistic no-regret methods are known to struggle. It proposes a unified perturbed-FTRL framework and studies two divergences: standard KL (PFTRL-KL) and Reverse KL (PFTRL-RKL). The central theoretical result is that the Reverse KL estimator is unbiased and has conditional zero variance in the perturbation term: conditioned on a sampled trajectory, the estimated cumulative perturbation equals its true value exactly (Theorem 2). Empirically, both perturbed variants stabilize last-iterate learning and lower exploitability relative to unperturbed FTRL, and a controlled experiment isolates the zero-variance property as the source of RKL's advantage, which grows with perturbation strength. The paper argues this matters because last-iterate convergence avoids storing and averaging many strategies, a real cost in large games.

What carries the argument

The central object is the RKL perturbation term $d^{\pi,\sigma}_i(h,a) = \frac{1_{i=\tau(h)}}{\pi_i(a|x(h))}(\sigma_i(a|x(h))-\pi_i(a|x(h)))$, the gradient of the Reverse KL divergence between the anchoring strategy $\sigma_i$ and the current strategy $\pi_i$. Its defining identity is that the expected cumulative perturbation is zero, $\mathbb{E}_{a\sim\pi_i(\cdot|x(h))}[\delta^{\pi,\sigma}_i(h,a)]=0$ for every history and strategy, so the sampled estimator collapses to the exact cumulative perturbation whenever the history is sampled. Theorem 2 is the formal statement of that collapse: the conditional variance is zero. The unified PFTRL framework and the anchoring-strategy update, which replaces the anchor with the current strategy every $T_\sigma$ visits, complete the mechanism.

What would settle it

Rerun the Figure 3 comparison with PFTRL-KL's perturbation strength tuned so its full-tree-traversal exploitability curve matches PFTRL-RKL's at every iteration, not only at convergence; if RKL's outcome-sampling advantage disappears, the effect is a calibration artifact, and a direct measurement of $\mathrm{Var}[\tilde{\delta}^{\pi,\sigma}_i(h,a)\mid h\in H_j]$ under outcome sampling that ever exceeds zero would violate Theorem 2.

Watch

Extended reading notes

Core claim

The paper's claim, stated on its own terms, is that choosing Reverse KL divergence as the perturbation in perturbed FTRL gives an outcome-sampling estimator that is both unbiased (Theorem 1) and conditionally zero-variance in the perturbation term (Theorem 2). Concretely, whenever a terminal history is sampled, the estimated cumulative magnitude of perturbation $\tilde{\delta}^{\pi,\sigma}_i(h,a)$ equals the exact cumulative magnitude $\delta^{\pi,\sigma}_i(h,a)$ for every visited history-action pair, so its conditional variance is zero even though the non-perturbed Q-value estimates still carry sampling noise. This rests on the identity $\mathbb{E}_{a\sim\pi_i(\cdot|x(h))}[\delta^{\pi,\sigma}_i(h,a)]=0$ for all strategies and histories, which holds because the RKL perturbation is the gradient of Reverse KL between the anchoring and current strategies. The paper further claims that this variance reduction translates into more stable last-iterate convergence under outcome sampling, most visibly in Leduc poker and at larger perturbation strengths, while PFTRL-KL, equivalent to Reward-Transformed FTRL, generally matches or beats RKL on other benchmarks.

Load-bearing premise

The controlled comparison assumes that matching the two methods' converged exploitability under full tree traversal leaves them identical except for estimator variance, so if the tuned perturbation strengths also shift bias or trajectory, the outcome-sampling advantage could be a calibration artifact.

Editorial extensions

If this is right

  • Both OS-PFTRL-KL+ and OS-PFTRL-RKL+ lower the last-iterate exploitability of FTRL under outcome sampling on the benchmark games, with the gap widening as iterations grow.
  • PFTRL-RKL+ beats PFTRL-KL+ in Leduc poker under full game-tree traversal, external sampling, and outcome sampling, while KL+ is at least as good on most other benchmarks.
  • In the controlled calibration experiment, once KL's perturbation strength is matched to RKL's converged exploitability under full traversal, RKL retains lower exploitability under outcome sampling, and the advantage increases with perturbation strength.
  • The anchoring-strategy update improves both perturbed variants, while perturbation generally does not improve average-iterate performance, where CFR and CFR+ remain stronger.
  • Last-iterate convergence removes the need to store and average a sequence of strategies, reducing memory and computation in settings where strategies are large, such as neural-network representations.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because Theorem 2 holds for any sampling scheme, the same conditional zero-variance argument should make PFTRL-RKL more stable under external sampling and other estimator choices; the paper's external-sampling results are consistent with this but do not isolate it.
  • A stricter test of the paper's causal claim would match the entire full-traversal exploitability trajectory of PFTRL-RKL, not only its converged value, when tuning PFTRL-KL, to rule out that the calibrated perturbation strengths shift bias or the learning path rather than variance.
  • The RKL advantage in Leduc poker suggests a testable prediction: the benefit grows with the asymmetry of the game tree, so a synthetic family of games varying asymmetry could quantify the effect.
  • Combining RKL perturbation with CFR+ style updates may improve last-iterate performance where CFR+ is strongest; the paper leaves this interplay open.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper studies perturbed Follow-the-Regularized-Leader (FTRL) algorithms in extensive-form games under outcome sampling. It introduces a unified framework covering PFTRL-KL and PFTRL-RKL, where the latter uses a Reverse-KL perturbation. The main theoretical results, Theorems 1 and 2, prove that the proposed estimator of the perturbed counterfactual value is unbiased and that, conditioned on a sampled trajectory, the estimated cumulative perturbation has zero variance for PFTRL-RKL. The paper also reports last-iterate exploitability experiments on Kuhn poker, Leduc poker, Goofspiel, and Liar's Dice, and a controlled experiment intended to isolate the effect of conditional zero variance. The central empirical claim is that this variance-reduction property improves last-iterate convergence under outcome sampling, especially at larger perturbation strengths.

Significance. The conditional zero-variance property of the Reverse-KL perturbation estimator is a clean and useful theoretical observation, and the proofs of Theorems 1 and 2 in Appendix A are self-contained and appear correct. The paper also provides a broad benchmark comparison, including full-traversal, external-sampling, and outcome-sampling regimes, and comparisons against CFR/CFR+ and perturbed CFR+. If the empirical attribution were fully justified, the paper would offer a valuable explanation of when and why Reverse-KL perturbation helps under sampling. However, the significance is currently moderated by the gap between the theoretical variance result and the experimental design used to support the causal claim that conditional zero variance improves last-iterate performance.

major comments (3)
  1. [Section 4, Figure 3] The controlled experiment does not isolate the conditional zero-variance property. Matching the converged exploitability under full game-tree traversals by tuning PFTRL-KL's perturbation strength (reported as 0.010147, 0.17, 0.2946 against PFTRL-RKL's 0.05, 0.1, 0.2) matches only a single scalar summary of the full-traversal dynamics. The two algorithms have different perturbation functions (Eq. 4 vs. Eq. 8), different fixed points, and different transient paths, and the matched mu values differ substantially at the small-mu end. Moreover, Theorem 2 removes variance only from the perturbation estimator, not from the non-perturbed Q-value estimator in Eq. (10), whose variance depends on the visited strategies and reach probabilities. The observed RKL advantage in Figure 3 could therefore be a calibration artifact rather than a consequence of conditional zero variance. A convincing control would track full-traversal trajectories or otherwise verify that the non-perturbed sampling variance is comparable, and would check the advantage across a range of matched mu values, preferably including Leduc poker.
  2. [Section 3.2, paragraph after Theorem 2] The statement that 'the variance of the estimated counterfactual values in PFTRL-RKL is smaller than that in KL' is not established by Theorems 1 and 2. Theorem 2 gives zero conditional variance for the perturbation component delta, while the total estimator in Eq. (9) also contains the Q-value term in Eq. (10), whose variance is strategy-dependent and need not be smaller for RKL. Since this variance comparison is the stated motivation for expecting OS-PFTRL-RKL to outperform OS-PFTRL-KL, the claim should either be proved for the total estimator or explicitly weakened to a statement about the perturbation component only.
  3. [Section 4, Figures 2 and 3] The empirical evidence for the central claim is under-reported. The exploitability curves are means over 10 seeds with no error bars, confidence intervals, or statistical tests; in a high-variance setting such as outcome sampling, mean-only curves do not substantiate the claims of 'consistently outperforms' and 'stable results.' In addition, the headline RKL advantage appears in Leduc poker (Figure 2), but the controlled experiment in Figure 3 is run only in Kuhn poker, where the Figure 2 advantage is not the most pronounced. Without a controlled test in Leduc poker or a clear argument that Kuhn poker exercises the same mechanism, the connection between the Leduc result and the variance-reduction explanation remains incomplete.
minor comments (3)
  1. [Section 3.1, Propositions 1 and 2] The paper states that the proofs of Propositions 1 and 2 are omitted because they are straightforward, but the precise equivalence statements and the required conditions on the strategy space and regularization are not fully specified. Since these propositions connect PFTRL-RKL to Mutant FTRL and PFTRL-KL to Reward-Transformed FTRL, a short proof or a precise reference would improve verifiability.
  2. [Section 4 and Figure 3 caption] There are inconsistencies in the reported perturbation strengths: the text gives PFTRL-KL's calibrated value as 0.010147 while the Figure 3 caption shows 0.10147; the text states 'mu in {0.05, 0, 1, 0.2}' which should presumably be {0.05, 0.1, 0.2}; and the caption contains the typo 'oragen'. These should be corrected.
  3. [Appendix G and Theorem 2] The main experiments use anchoring strategy updates, where the anchor sigma is replaced by the current strategy every T_sigma visits, while Theorems 1 and 2 are stated for a fixed anchor. The paper should explicitly note that the unbiasedness and conditional zero-variance properties hold for the time-varying anchor used in Algorithm 1, or point to the specific place where this is demonstrated.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the conditional zero-variance theorem is a direct algebraic consequence of the RKL perturbation definition and its estimator; the Figure 3 calibration is an experimental-control concern, not a circular reduction of a prediction to its inputs.

full rationale

The paper's central theoretical claim, Theorem 2, is derived from the paper's own definitions rather than from an assumed target. The proof in Appendix A starts from the RKL perturbation d^{π,σ}_i(h,a) = (σ_i(a|x) − π_i(a|x))/π_i(a|x) (Eq. 4), the cumulative perturbation δ (Eq. 5), and the estimator δ̃ (Eq. 11). It shows telescoping because Σ_a σ_i(a|x) = Σ_a π_i(a|x) = 1, yielding E_a[δ] = 0 and, conditional on a sampled history, δ̃ = δ. This is a genuine algebraic identity, not a circular definition: the zero-variance property is a consequence of the chosen perturbation form, but the form is not defined in terms of the property claimed. The paper also explicitly acknowledges that the non-perturbed Q-value estimator (Eq. 10) still has nonzero variance, so it does not overclaim total variance reduction. The equivalences in Propositions 1 and 2 (PFTRL-RKL with Mutant FTRL, PFTRL-KL with Reward-Transformed FTRL) are contextual identifications, and the citations to the authors' prior work on Mutant FTRL and anchoring-strategy updates are not load-bearing for the proof of Theorem 2. No uniqueness theorem is imported from the authors, and no ansatz is smuggled in via citation: the RKL form is presented as a deliberate construction. The empirical protocol in Figure 3 calibrates PFTRL-KL's perturbation strength so that its full-traversal converged exploitability matches PFTRL-RKL, then compares the algorithms under outcome sampling. This is a fairness calibration rather than a fit whose output is renamed as a prediction; the RKL advantage under sampling is an observed outcome and is not forced by the calibration. If matching only final exploitability fails to control trajectory or bias differences, that is an experimental-validity limitation, not circularity. Overall, the derivation chain is self-contained, so the appropriate circularity score is 0.

Assumptions & free parameters 3 free parameters · 3 assumptions · 0 invented entities

The central variance theorem is parameter-independent, so the theoretical contribution rests on standard game-theoretic axioms. The empirical contributions depend on hyperparameters (η, µ, Tσ) that are chosen by the authors, and on the unproven assumption that anchoring updates converge to exact equilibrium.

free parameters (3)
  • learning rate η = 0.0001
    Constant learning rate used in all outcome-sampling experiments; chosen by the authors, not fitted per game.
  • perturbation strength µ = 0.1 in main experiments; tuned to {0.010147, 0.17, 0.2946} for KL in the controlled Figure 3 experiment
    Controls the bias-variance tradeoff. In the controlled experiment, KL's µ is calibrated to match RKL's full-traversal exploitability, a data-dependent tuning step.
  • anchor update interval Tσ = 100,000 visits (outcome sampling), 10,000 visits (PCFR+ comparisons)
    Determines how often the anchoring strategy is reset to the current strategy; chosen by the authors.
assumptions (3)
  • domain assumption The sampling distribution has positive support on every reachable history
    The unbiasedness proof of Theorem 1 divides by p(h) and p(h, h'), requiring p(h) > 0 for all reachable histories; the paper assumes a fixed uniform sampling strategy in experiments.
  • domain assumption Anchoring strategy updates converge to an exact Nash equilibrium
    The '+' variants in the experiments reset the anchor to the current strategy every Tσ visits; the convergence guarantee is cited from Perolat et al. 2021 and Abe et al. 2023, 2024, not proved here.
  • standard math The game satisfies perfect recall and two-player zero-sum structure
    The definitions of counterfactual value, reach probabilities, and exploitability rely on the standard extensive-form game model with perfect recall.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Power of Perturbation under Sampling in Solving Extensive-Form Games." pith.science (2026). https://pith.science/paper/RS7I422Q

@misc{pith2026250116600,
  author       = {Pith},
  title        = {Pith review of: On the Power of Perturbation under Sampling in Solving Extensive-Form Games},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RS7I422Q}},
  note         = {Machine review of arXiv:2501.16600}
}
read the original abstract

We investigate how perturbation does and does not improve the Follow-the-Regularized-Leader (FTRL) algorithm in solving imperfect-information extensive-form games under sampling, where payoffs are estimated from sampled trajectories. While optimistic algorithms are effective under full feedback, they often become unstable in the presence of sampling noise. Payoff perturbation offers a promising alternative for stabilizing learning and achieving \textit{last-iterate convergence}. We present a unified framework for \textit{Perturbed FTRL} algorithms and study two variants: PFTRL-KL (standard KL divergence) and PFTRL-RKL (Reverse KL divergence), the latter featuring an estimator with both unbiasedness and conditional zero variance. While PFTRL-KL generally achieves equivalent or better performance across benchmark games, PFTRL-RKL consistently outperforms it in Leduc poker, whose structure is more asymmetric than the other games in a sense. Given the modest advantage of PFTRL-RKL, we design the second experiment to isolate the effect of conditional zero variance, showing that the variance-reduction property of RKL improve last-iterate performance.

Figures

Figures reproduced from arXiv: 2501.16600 by the authors.

Figure 1
Figure 1. Illustration of the cumulative magnitude of per [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Exploitability of last-iterate π t under outcome sampling. the difference in Section 5 and, for simplicity, we adopt the uniform strategy to sample histories, unless noted. With Eq. 12, given a sampling strategy π ′ , let us rewrite the perturbed counterfactual value estimator ve π,σ i (x, a) = X h∈x∩Hj 1 ρ π′ i (ha) X h′a′⊒ha∧h′a′∈Hj ρ π i (ha, h′a ′ ) ρ π′ i (ha, h′a ′) ui(h ′ , a′ ) + µ X h∈x∩Hj 1 ρ π′ i (h)πi(a|… view at source ↗
Figure 3
Figure 3. Exploitability difference of last-iterate between OS-PFTRL-RKL and -KL in Kuhn poker, with varying tuned pertur [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figures from the paper (9 more)
Figure 4
Figure 4. Figure 4: Exploitability of last iterate π t under full game-tree traversals [PITH_FULL_IMAGE:figures/full_fig_p013_4.png]
Figure 5
Figure 5. Figure 5: Exploitability of average iterate π¯ t under full game-tree traversals. 0 100000 200000 300000 400000 −2.25 −2.00 −1.75 −1.50 −1.25 −1.00 −0.75 −0.50 −0.25 Kuhn poker 0 100000 200000 300000 400000 −2.00 −1.75 −1.50 −1.25 −1.00 −0.75 −0.50 −0.25 Goofspiel (4 cards) 0.0 …
Figure 6
Figure 6. Figure 6: Exploitability of last iterate π t under external sampling [PITH_FULL_IMAGE:figures/full_fig_p014_6.png]
Figure 7
Figure 7. Figure 7: Exploitability of average iterate π¯ t under external sampling. 0.0 0.5 1.0 1.5 2.0 2.5 3.0 1e6 −2.5 −2.0 −1.5 −1.0 −0.5 Kuhn poker 0.0 0.5 1.0 1.5 2.0 2.5 3.0 1e6 −1.75 −1.50 −1.25 −1.00 −0.75 −0.50 −0.25 0.00 Goofspiel (4 cards) 0.0 0.2 0.4 0.6 0.8 1.0 1e7 −1.6 −1.4 …
Figure 8
Figure 8. Figure 8: Exploitability of last iterate π t under outcome sampling [PITH_FULL_IMAGE:figures/full_fig_p015_8.png]
Figure 9
Figure 9. Figure 9: Exploitability of average iterate π¯ t under outcome sampling. visits under outcome sampling in all experiments. The sampling strategy is uniform sampling (McAleer et al. 2023). The exploitability is averaged across 10 random seeds for each algorithm and is presented o…
Figure 10
Figure 10. Figure 10: Exploitability of last iterate π t under outcome sampling with PCFR-plus-L2+. 0.0 0.5 1.0 1.5 2.0 2.5 3.0 1e6 −2.5 −2.0 −1.5 −1.0 −0.5 Kuhn poker 0.0 0.5 1.0 1.5 2.0 2.5 3.0 1e6 −2.5 −2.0 −1.5 −1.0 −0.5 0.0 Goofspiel (4 cards) 0.0 0.2 0.4 0.6 0.8 1.0 1e7 −2.00 −1.75 −…
Figure 11
Figure 11. Figure 11: Exploitability of average iterate π¯ t under outcome sampling with PCFR-plus-L2+ [PITH_FULL_IMAGE:figures/full_fig_p017_11.png]
Figure 12
Figure 12. Figure 12: Effect of anchoring strategy updates of last-iterate in Kuhn poker. [PITH_FULL_IMAGE:figures/full_fig_p018_12.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Beyond the PPAD hardness of Auto-bidding Auctions

    cs.GT 2026-08 conditional novelty 6.0 of 10

    Under non-atomic value distributions, auto-bidding equilibria become separately monotone generalized Nash equilibria and PRIME solves them with last-iterate linear convergence.

Reference graph

Works this paper leans on

49 extracted references · 43 canonical work pages · cited by 1 Pith paper

  1. [1]

    , " * write output.state after.block = add.period write newline

    ENTRY address archivePrefix author booktitle chapter edition editor eid eprint howpublished institution isbn journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.a...

  2. [2]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...

  3. [3]

    Abe, K.; Ariu, K.; Sakamoto, M.; and Iwasaki, A. 2024. Adaptively Perturbed Mirror Descent for Learning in Games. In ICML, volume 235, 31--80

    work page 2024

  4. [4]

    Abe, K.; Ariu, K.; Sakamoto, M.; Toyoshima, K.; and Iwasaki, A. 2023. Last-Iterate Convergence with Full- and Noisy-Information Feedback in Two-Player Zero-Sum Games. In AISTATS, 7999--8028

    work page 2023

  5. [5]

    Abe, K.; and Kaneko, Y. 2021. Off-Policy Exploitability-Evaluation in Two-Player Zero-Sum Markov Games. In AAMAS, 78--87

    work page 2021

  6. [6]

    Abe, K.; Sakamoto, M.; and Iwasaki, A. 2022. Mutation-Driven Follow the Regularized Leader for Last-Iterate Convergence in Zero-Sum Games. In UAI, 1--10

    work page 2022

  7. [7]

    Bai, Y.; Jin, C.; Mei, S.; and Yu, T. 2022. Near-Optimal Learning of Extensive-Form Games with Imperfect Information. In ICML, volume 162, 1337--1382

    work page 2022

  8. [8]

    P.; and Piliouras, G

    Bailey, J. P.; and Piliouras, G. 2018. Multiplicative weights update in zero-sum games. In EC, 321--338

    work page 2018

Show all 49 references
  1. [9]

    Bauer, J.; Broom, M.; and Alonso, E. 2019. The stabilization of equilibria in evolutionary game dynamics through mutation: mutation limits in evolutionary games. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 475(2231): 20190355

    2019

  2. [10]

    Bowling, M.; Burch, N.; Johanson, M.; and Tammelin, O. 2015. Heads-up limit hold’em poker is solved. Science, 347(6218): 145--149

    2015

  3. [11]

    Brown, N.; and Sandholm, T. 2018. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374): 418--424

    2018

  4. [12]

    Brown, N.; and Sandholm, T. 2019. Solving imperfect-information games via discounted regret minimization. In AAAI, 1829--1836

    2019

  5. [13]

    Daskalakis, C.; Ilyas, A.; Syrgkanis, V.; and Zeng, H. 2018. Training gans with optimism. In ICLR

    2018

  6. [14]

    Daskalakis, C.; and Panageas, I. 2019. Last-iterate convergence: Zero-sum games and constrained min-max optimization. In The proceedings of the 10th Innovations in Theoretical Computer Science, volume 124, 27:1--27:18

    2019

  7. [15]

    Davis, T.; Schmid, M.; and Bowling, M. 2020. Low-variance and zero-variance baselines for extensive-form games. In ICML, 2392--2401

    2020

  8. [16]

    Facchinei, F.; and Pang, J.-S. 2003. Finite-dimensional variational inequalities and complementarity problems. Springer

    2003

  9. [17]

    Farina, G.; Kroer, C.; Brown, N.; and Sandholm, T. 2019. Stable-Predictive Optimistic Counterfactual Regret Minimization. In ICML, volume 97, 1853--1862

    2019

  10. [18]

    Farina, G.; Kroer, C.; and Sandholm, T. 2021. Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent. In AAAI, 5363--5371

    2021

  11. [19]

    Farina, G.; Schmucker, R.; and Sandholm, T. 2021. Bandit Linear Optimization for Sequential Decision Making and Extensive-Form Games. In AAAI, 5372--5380

    2021

  12. [20]

    P.; and Ferguson, T

    Ferguson, C. P.; and Ferguson, T. S. 1991. Models for the Game of Liar's Dice, 15--28. Springer Netherlands

    1991

  13. [21]

    Fiegel, C.; Menard, P.; Kozuno, T.; Munos, R.; Perchet, V.; and Valko, M. 2023. Adapting to game trees in zero-sum imperfect information games. In ICML, volume 202, 10093--10135

    2023

  14. [22]

    Gilpin, A.; and Sandholm, T. 2007. Lossless abstraction of imperfect information games. J. ACM, 54(5): 25^^e2^^80^^93es

    2007

  15. [23]

    Hofbauer, J.; and Sigmund, K. 1998. Evolutionary Games and Population Dynamics. Cambridge: Cambridge University Press

    1998

  16. [24]

    Johanson, M.; Waugh, K.; Bowling, M.; and Zinkevich, M. 2011. Accelerating best response calculation in large extensive games. In IJCAI, 258--265

    2011

  17. [25]

    Kozuno, T.; Menard, P.; Munos, R.; and Valko, M. 2021. Learning in two-player zero-sum partially observable Markov games with perfect recall. In NeurIPS, 11987--11998

    2021

  18. [26]

    Kuhn, H. W. 1951. A simplified two-person poker, 97--104. Princeton University Press

    1951

  19. [27]

    Lanctot, M. 2013. Monte Carlo sampling and regret minimization for equilibrium computation and decision-making in large extensive form games. Ph.D. thesis

    2013

  20. [28]

    D.; Saeta, B.; Bradbury, J.; Ding, D.; Borgeaud, S.; Lai, M.; Schrittwieser, J.; Anthony, T.; Hughes, E.; Danihelka, I.; and Ryan-Davis, J

    Lanctot, M.; Lockhart, E.; Lespiau, J.-B.; Zambaldi, V.; Upadhyay, S.; P\' e rolat, J.; Srinivasan, S.; Timbers, F.; Tuyls, K.; Omidshafiei, S.; Hennes, D.; Morrill, D.; Muller, P.; Ewalds, T.; Faulkner, R.; Kram\' a r, J.; Vylder, B. D.; Saeta, B.; Bradbury, J.; Ding, D.; Bor...

    2019 arXiv

  21. [29]

    Lanctot, M.; Waugh, K.; Zinkevich, M.; and Bowling, M. 2009. Monte Carlo Sampling for Regret Minimization in Extensive Games. In NeurIPS, volume 22, 1078--1086

    2009

  22. [30]

    Lee, C.-W.; Kroer, C.; and Luo, H. 2021. Last-iterate Convergence in Extensive-Form Games. In NeurIPS, 14293--14305

    2021

  23. [31]

    Liu, M.; Ozdaglar, A.; Yu, T.; and Zhang, K. 2023. The Power of Regularization in Solving Extensive-Form Games. In ICLR

    2023

  24. [32]

    Lockhart, E.; Lanctot, M.; P^^c3^^a9rolat, J.; Lespiau, J.-B.; Morrill, D.; Timbers, F.; and Tuyls, K. 2019. Computing approximate equilibria in sequential adversarial games by exploitability descent. In IJCAI, 464--470

    2019

  25. [33]

    M.; Farina, G.; Lanctot, M.; and Sandholm, T

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

    2023

  26. [34]

    Meng, L.; Ge, Z.; Li, W.; An, B.; and Gao, Y. 2023. Efficient Last-iterate Convergence Algorithms in Solving Games. arXiv preprint arXiv:2308.11256

    2023 arXiv

  27. [35]

    Mertikopoulos, P.; Lecouat, B.; Zenati, H.; Foo, C.-S.; Chandrasekhar, V.; and Piliouras, G. 2019. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In ICLR

    2019

  28. [36]

    Mertikopoulos, P.; Papadimitriou, C.; and Piliouras, G. 2018. Cycles in adversarial regularized learning. In SODA, 2703--2717

    2018

  29. [37]

    Morav^^c4^^8d^^c3^^adk, M.; Schmid, M.; Burch, N.; Lis^^c3^^bd, V.; Morrill, D.; Bard, N.; Davis, T.; Waugh, K.; Johanson, M.; and Bowling, M. 2017. DeepStack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337): 508--513

    2017

  30. [38]

    Nash, J. 1951. Non-cooperative games. Annals of mathematics, 54(2): 286--295

    1951

  31. [39]

    Perolat, J.; Munos, R.; Lespiau, J.-B.; Omidshafiei, S.; Rowland, M.; Ortega, P.; Burch, N.; Anthony, T.; Balduzzi, D.; De Vylder, B.; et al. 2021. From Poincar \'e recurrence to convergence in imperfect information games: Finding equilibrium via regularization. In ICML, volum...

    2021

  32. [40]

    D.; Hennes, D.; Tarassov, E.; Strub, F.; de Boer, V.; Muller, P.; Connor, J

    Perolat, J.; Vylder, B. D.; Hennes, D.; Tarassov, E.; Strub, F.; de Boer, V.; Muller, P.; Connor, J. T.; Burch, N.; Anthony, T.; McAleer, S.; Elie, R.; Cen, S. H.; Wang, Z.; Gruslys, A.; Malysheva, A.; Khan, M.; Ozair, S.; Timbers, F.; Pohlen, T.; Eccles, T.; Rowland, M.; Lanc...

    2022

  33. [41]

    Schmid, M.; Burch, N.; Lanctot, M.; Moravcik, M.; Kadlec, R.; and Bowling, M. 2019. Variance reduction in monte carlo counterfactual regret minimization (VR-MCCFR) for extensive form games using baselines. In AAAI, 2157--2164

    2019

  34. [42]

    Z.; Loizou, N.; Lanctot, M.; Mitliagkas, I.; Brown, N.; and Kroer, C

    Sokota, S.; D'Orazio, R.; Kolter, J. Z.; Loizou, N.; Lanctot, M.; Mitliagkas, I.; Brown, N.; and Kroer, C. 2023. A unified approach to reinforcement learning, quantal response equilibria, and two-player zero-sum games. In ICLR

    2023

  35. [43]

    Southey, F.; Bowling, M.; Larson, B.; Piccione, C.; Burch, N.; Billings, D.; and Rayner, C. 2005. Bayes' bluff: opponent modelling in poker. In UAI, 550--558

    2005

  36. [44]

    Tammelin, O. 2014. Solving large imperfect information games using CFR+. arXiv preprint arXiv:1407.5042

    2014 arXiv

  37. [45]

    Timbers, F.; Bard, N.; Lockhart, E.; Lanctot, M.; Schmid, M.; Burch, N.; Schrittwieser, J.; Hubert, T.; and Bowling, M. 2022. Approximate Exploitability: Learning a Best Response. In IJCAI, 3487--3493

    2022

  38. [46]

    Wei, C.-Y.; Lee, C.-W.; Zhang, M.; and Luo, H. 2021. Linear last-iterate convergence in constrained saddle-point optimization. In ICLR

    2021

  39. [47]

    M.; Reiter, J

    Zagorsky, B. M.; Reiter, J. G.; Chatterjee, K.; and Nowak, M. A. 2013. Forgiver Triumphs in Alternating Prisoner's Dilemma. PLOS ONE, 1--8

    2013

  40. [48]

    Zhang, N.; McAleer, S.; and Sandholm, T. 2024. Faster Game Solving via Hyperparameter Schedules. arXiv preprint arXiv:2404.09097

    2024

  41. [49]

    Zinkevich, M.; Johanson, M.; Bowling, M.; and Piccione, C. 2007. Regret minimization in games with incomplete information. In NeurIPS, 1729--1736

    2007

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.