{"id":"0613cefc-17d1-44a0-b8cb-afe7d78439fe","arxiv_id":"2501.16600","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A reverse-KL perturbed FTRL estimator has unbiased, conditionally-zero-variance perturbation updates that improve last-iterate convergence in sampled extensive-form games.","lead":"This paper studies how adding payoff perturbation to Follow-the-Regularized-Leader helps solve imperfect-information games when payoffs are estimated from sampled game trajectories. It introduces a reverse-KL variant whose perturbation estimator has zero conditional variance, and shows empirically that this stabilizes last-iterate convergence and lowers exploitability.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Figure 3 calibration does not isolate conditional zero variance: matching only final exploitability under full traversal leaves trajectory and bias differences uncontrolled, so the RKL advantage may stem from calibration rather than variance reduction.","rationale":"The concern is load-bearing because it targets the only experiment designed to prove the causal role of Theorem 2's variance property. The theorem itself appears correct, but its practical value is established solely by Figure 3. If the calibration is confounded, the paper's specific conclusion that 'variance reduction via Reverse KL can yield tangible improvements' (Section 4) is not supported, even though the broader finding that perturbation stabilizes FTRL under sampling may remain valid. The proposed test is decisive: it removes the calibration confound by matching full-traversal dynamics more closely, and it checks whether the effect replicates in the game where the algorithm actually claims its main advantage. This does not require rejecting the paper; it asks for a sturdier experiment or a more modest claim. The reader's weakest_assumption identified the same calibration issue, and the recommended verdict remains conditional on such additional evidence.","tokens_in":22366,"tokens_out":8302,"duration_ms":92914,"concrete_test":"Repeat the Figure 3 protocol with trajectory-matched calibration: for each RKL µ, choose KL µ to minimize the maximum absolute gap in log10 exploitability over all iterations under full game-tree traversals (not just the final value), then switch to outcome sampling and compare last-iterate exploitability with per-seed error bars. If the RKL advantage persists under this stricter calibration, the zero-variance explanation is supported; if it shrinks or reverses, the Figure 3 result is an artifact of single-point calibration. Run the same trajectory-matched comparison in Leduc poker (the headlining game) to confirm the effect transfers. A complementary analytic check: at matched strategies, compute the variance of the full estimated cumulative counterfactual values (Eq.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central empirical claim—that PFTRL-RKL's conditional zero variance improves last-iterate performance under outcome sampling—rests on the controlled experiment in Figure 3. The protocol calibrates PFTRL-KL's perturbation strength so that its converged exploitability under full game-tree traversals matches that of PFTRL-RKL (Section 4, Figure 3), and then attributes any outcome-sampling difference to the perturbation form. This attribution is not justified. Matching a single scalar (final exploitability) does not ensure that the two full-traversal dynamics are otherwise equivalent: the functional forms d^{π,σ}_i differ (Eq. 4 vs Eq. 8), and the tuned KL strengths (µ=0.010147, 0.17, 0.2946) differ substantially from the RKL strengths (µ=0.05, 0.1, 0.2). Different µ changes the relative scale of perturbation to payoff, which affects how sampling noise propagates through the FTRL update; different d changes the fixed point and the transient path. The conditional zero variance of Theorem 2 only removes variance from the perturbation term, not from the non-perturbed Q-value estimator (Eq. 10), whose variance depends on the strategies visited and can differ between the two runs. Thus the observed advantage of RKL in Figure 3 could be due to differences in bias, trajectory, or noise amplification unrelated to the variance-reduction property. Moreover, the headline RKL advantage is in Leduc poker (Figure 2), yet the controlled experiment is run in Kuhn poker, where Figure 2 shows at most a modest RKL advantage; this weakens the link from the controlled result to the paper's main empirical phenomenon.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":22693,"tokens_out":6538,"duration_ms":67682,"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":[{"comment":"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.","section":"Section 4, Figure 3"},{"comment":"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.","section":"Section 3.2, paragraph after Theorem 2"},{"comment":"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.","section":"Section 4, Figures 2 and 3"}],"minor_comments":[{"comment":"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.","section":"Section 3.1, Propositions 1 and 2"},{"comment":"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.","section":"Section 4 and Figure 3 caption"},{"comment":"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.","section":"Appendix G and Theorem 2"}],"recommendation":"major_revision","confidential_remarks":"The paper's theoretical contribution is sound and the benchmark coverage is broad. The main weakness is that the experimental design—especially the calibration in Figure 3—does not yet support the causal attribution of the performance gains to conditional zero variance. If the authors can strengthen the controlled experiment and add proper variance reporting, the paper would be a solid contribution to the cs.GT literature."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the paper's real contribution is Theorem 2—the Reverse KL perturbation estimator has conditional zero variance under outcome sampling—and the paper is honest that it is not proposing a new state-of-the-art algorithm. The broader package is a clean framework, a modest but sensible set of experiments, and a controlled experiment that is not as controlled as it claims.\n\nWhat's new: The framework unifies PFTRL-KL and PFTRL-RKL, and shows the latter recovers Mutant FTRL while the former recovers Reward-Transformed FTRL. The variance analysis is the centerpiece: the RKL perturbation term, conditioned on the sampled trajectory, equals the true cumulative perturbation exactly because the future terms sum to zero. That's a simple but real observation, and the proofs in the appendix are self-contained and valid. The experiments cover six games and are reported honestly: KL is generally as good or better, and RKL's clear win is in Leduc poker. The paper explicitly says it aims at understanding rather than beating current algorithms, which is fine.\n\nWhere it's soft: The controlled experiment in Figure 3 is meant to isolate the zero-variance property, but it only matches the final exploitability under full traversal. That matches one scalar, not the dynamics. The two perturbation functions are different, and the tuned KL strengths differ from RKL's by an order of magnitude, so the outcome-sampling difference could come from the functional form, the change in bias, or noise amplification, not specifically from zero variance. Also, the experiment is run in Kuhn poker, where the main results show no real RKL advantage; the big advantage is in Leduc, so the link is weak. Error bars would help—ten seeds is enough to show variance, and the plots currently show only means. The equivalence propositions (1 and 2) are stated without proof; they are probably straightforward, but a sketch would make the paper self-contained. No code is released, which makes re-running the controlled experiment harder.\n\nBottom line: This is a solid paper for people working on last-iterate convergence in extensive-form games. It deserves a serious referee. The theoretical result is worth publishing; the empirical section needs revision to make the controlled experiment interpretable, plus error bars and proof sketches.","headline":"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.","tokens_in":23248,"tokens_out":3785,"would_cite":true,"duration_ms":37488,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A26","91A10"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["extensive-form games","last-iterate convergence","Follow-the-Regularized-Leader","payoff perturbation","outcome sampling","Reverse KL divergence","zero-variance estimator","Nash equilibrium"],"falsifier":"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.","tokens_in":22195,"feed_emoji":"🎲","tokens_out":11138,"duration_ms":95232,"temperature":0.7,"pith_summary":"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.","feed_headline":"A zero-variance trick steadies last-iterate game solving","feed_subtitle":"Reverse-KL payoff perturbation keeps FTRL from wandering when payoffs come from single sampled trajectories.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines Mutant FTRL in normal-form games, the ancestor of PFTRL-RKL whose Reverse KL perturbation is extended to extensive-form games under sampling.","marker":"Abe, Sakamoto, and Iwasaki 2022"},{"why":"Shows optimistic algorithms fail under noisy feedback and studies Mutant FTRL with noisy information, providing the motivation and the noisy-feedback baseline for perturbed FTRL.","marker":"Abe et al. 2023"},{"why":"Introduces Reward-Transformed FTRL, which the paper proves PFTRL-KL recovers, and supplies the anchoring strategy update used in the '+' variants.","marker":"Perolat et al. 2021"},{"why":"Defines Monte Carlo CFR and the outcome and external sampling estimators that the paper's OS-PFTRL estimators are built on.","marker":"Lanctot et al. 2009"},{"why":"Formalizes outcome sampling as single-trajectory bandit feedback, the setting whose high variance motivates the zero-variance RKL estimator.","marker":"Lanctot 2013"},{"why":"Shows fixed uniform sampling outperforms epsilon-greedy for estimation under outcome sampling, the sampling strategy all experiments adopt.","marker":"McAleer et al. 2023"},{"why":"Identifies last-iterate convergence under sampling as a key open problem, which the paper directly targets.","marker":"Fiegel et al. 2023"},{"why":"Studies the power of regularization in solving extensive-form games and proposes regularized CFR variants, a perturbed baseline the paper discusses for last-iterate convergence.","marker":"Liu et al. 2023"}],"fun_headline_variants":["Zero-variance perturbation steadies FTRL in games","Reverse-KL estimator clears sampling noise for FTRL","RKL perturbation yields stable last-iterate convergence","Conditionally zero variance boosts last-iterate solving","Perturbed FTRL with RKL: unbiased, zero-variance updates"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Zero-variance perturbation steadies FTRL in games","Reverse-KL estimator clears sampling noise for FTRL","RKL perturbation yields stable last-iterate convergence","Conditionally zero variance boosts last-iterate solving","Perturbed FTRL with RKL: unbiased, zero-variance updates"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000275,"raw_usage":{"total_tokens":1660,"prompt_tokens":982,"completion_tokens":678,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":598,"completion_tokens_details":{"reasoning_tokens":596}},"tokens_in":598,"tokens_out":678,"duration_ms":6707,"temperature":1.0,"reasoning_tokens":596,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T12:00:14.273259+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines Mutant FTRL in normal-form games, the ancestor of PFTRL-RKL whose Reverse KL perturbation is extended to extensive-form games under sampling."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows optimistic algorithms fail under noisy feedback and studies Mutant FTRL with noisy information, providing the motivation and the noisy-feedback baseline for perturbed FTRL."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces Reward-Transformed FTRL, which the paper proves PFTRL-KL recovers, and supplies the anchoring strategy update used in the '+' variants."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines Monte Carlo CFR and the outcome and external sampling estimators that the paper's OS-PFTRL estimators are built on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Formalizes outcome sampling as single-trajectory bandit feedback, the setting whose high variance motivates the zero-variance RKL estimator."},{"cited_title":"M.; Farina, G.; Lanctot, M.; and Sandholm, T","cited_arxiv_id":null,"evidence_quote":"Shows fixed uniform sampling outperforms epsilon-greedy for estimation under outcome sampling, the sampling strategy all experiments adopt."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Identifies last-iterate convergence under sampling as a key open problem, which the paper directly targets."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Studies the power of regularization in solving extensive-form games and proposes regularized CFR variants, a perturbed baseline the paper discusses for last-iterate convergence."}],"review_version":1}