{"id":"2db9ec6e-9d9d-433c-8f63-016a68b42d16","arxiv_id":"2501.00533","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Adding negative momentum to mirror descent, FTRL, and regret matching accelerates convergence in constrained zero-sum games, and the new MoCFR+ variant reports lower exploitability than CFR+ across multiple games.","lead":"This paper adds negative momentum to standard algorithms for solving constrained zero-sum games, producing variants like MoCFR+ that converge faster in normal-form and poker-style games. The authors report that MoCFR+ reaches exploitability orders of magnitude below CFR+ across several benchmark games.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's stated parameter range is algebraically wrong, and every MoMWU experiment in Table 1 violates even the corrected bound; the claimed theoretical support for the empirical results does not hold.","rationale":"The reader's weakest_assumption points to the missing convergence theorem for MoRM+/MoCFR+, which is a real limitation: the headline practical algorithms are not covered by the entropy-regularizer theory, and the FTRL/OMD-to-RM+ correspondence is not enough to transfer the proof. My stress-test found an additional, more concrete defect in the theory that actually is stated: Theorem 2's parameter range is algebraically incorrect, and all MoMWU experiments in Table 1 lie outside the (corrected) convergent range. This matters because the paper explicitly says the theory supports the experimental results, and the exponential-convergence rate is a central advertised contribution. The error is fixable by shrinking η, but as written the theorem is false for part of its stated range and vacuous for the experimental settings. I do not think this overturns the empirical contribution: the code is available, the games are standard, and the reported speedups are large and consistent across four EFG types. However, the paper needs a corrected bound and either experiments inside the proven range or a clear separation of the empirical and theoretical sections. The reader's CONDITIONAL verdict remains appropriate, so I recommend UNCHANGED. I partially agree with the reader because the MoRM+/MoCFR+ gap is related but distinct from the parameter-range flaw I identified.","tokens_in":22556,"tokens_out":13662,"duration_ms":128657,"concrete_test":"Recompute the coefficient C = -1 - (3/2)β - 4η^2/β in the final step of the Theorem 2 proof. For β=-0.5 and η=0.2, which satisfies the paper's stated bound η ≤ sqrt(-(1+1.5β)β/2)=0.25, verify that C=0.07>0, so the proof's conclusion Dψ(z*,z_{t+1}) ≤ (1+β/2)Dψ(z*,z_t) does not follow. Then check Table 1 against the corrected bound η ≤ sqrt(-β(1+1.5β)/4): for β=-0.02, η=7, the bound is 0.0696, so the theorem's assumptions are violated by a factor greater than 100; for β=-0.06, η=1, the bound is 0.117. This one-page algebraic verification settles whether the stated range is valid and whether the experiments operate in the proven regime.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's theoretical centerpiece, Theorem 2, contains a concrete algebraic error. In the proof (Appendix D), the final inequality is Dψ(z*,z_{t+1}) ≤ (1+β/2)Dψ(z*,z_t) + C·DKL(z_{t+1},z_t), with C = -1 - (3/2)β - 4η^2/β. For contraction, C must be non-positive. The proof states this follows from -2/3 < β < 0 and η ≤ sqrt(-(1+3β/2)β/2). But substituting β=-0.5 and η=0.2 (allowed by this bound, since the bound is 0.25) gives C = -1 + 0.75 + 0.32 = 0.07 > 0, so the contraction does not follow. A correct calculation requires η ≤ sqrt(-β(1+3β/2)/4), a factor √2 smaller. Moreover, even the corrected bound is violated by every MoMWU hyperparameter in Table 1: for the random 25-action game β=-0.02 and η=7, while the corrected bound is about 0.0696 (and the paper's own bound is 0.0985); for the 3x3 game β=-0.06 and η=1, the bound is about 0.117. Thus the exponential-convergence theorem does not apply to any MoMWU experiment, despite the text asserting 'The following theoretical analysis supports the experimental results above.' In addition, Theorem 2 assumes k=∞, whereas all experiments use finite k. The MoCFR+/MoRM+ algorithms used for the headline 10^9 exploitability improvement have no convergence theorem at all; Eq. (21) is an analogy, not a consequence of the entropy-regularizer proof. The load-bearing bridge from theory to the paper's empirical claims is therefore broken.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a negative-momentum mechanism for constrained minimax games, instantiated as MoMD/MoFTRL (with entropy regularization), MoRM+, and their extensive-form counterparts MoCFR+ and DMoGDA/DMoMWU. The theoretical claims are exponential convergence of the entropy-regularized momentum algorithm to an approximate equilibrium (Theorems 2 and 3) and convergence to Nash equilibria with a sufficiently large restart interval (Theorem 4). The experimental sections report large exploitability reductions on normal-form and extensive-form benchmarks, most notably that MoCFR+ attains roughly 10^9 lower exploitability than CFR+ and outperforms PCFR+ across Kuhn Poker, Leduc Poker, Goofspiel, and Liar's Dice.","tokens_in":23030,"tokens_out":8572,"duration_ms":80272,"significance":"If the theoretical results were correct and the empirical claims reproducible, this would be a meaningful contribution: it extends negative-momentum ideas from unconstrained bilinear games to constrained decision sets, proposes a simple restarting-buffer mechanism, and demonstrates strong empirical performance across several standard game benchmarks. The paper ships code, uses standard benchmarks, and includes ablation studies for the restart interval. However, the central theorem as stated contains a parameter-range error, the proof of Theorem 4 is only a sketch, and the headline empirical algorithm MoCFR+ has no convergence theorem. The theory therefore does not currently support the paper's central claims as cleanly as the text suggests.","major_comments":[{"comment":"The final step of the proof is algebraically incorrect. The proof establishes Dψ(z*,z_{t+1}) ≤ (1+β/2)DKL(z*,z_t) + C·DKL(z_{t+1},z_t) with C = -1 - (3/2)β - 4η²/β, and contraction requires C ≤ 0. The stated condition η ≤ sqrt(-(1+3β/2)β/2) does not imply this. For example, β = -0.5 and η = 0.2 are allowed by the stated bound (which equals 0.25), yet C = -1 + 0.75 + 0.32 = 0.07 > 0. A correct condition is η ≤ sqrt(-(1+3β/2)β/4), a factor √2 smaller. Since Theorem 3 inherits this condition from Theorem 2, the theoretical guarantee as stated is invalid and must be corrected.","section":"Appendix D, proof of Theorem 2"},{"comment":"Even with the corrected bound, none of the MoMWU hyperparameters in Table 1 satisfy the theorem's conditions: for the size-25 random game, β = -0.02 and η = 7, while the corrected bound is about 0.0696; for the 3×3 game, β = -0.06 and η = 1, while the corrected bound is about 0.117. In addition, Theorems 2 and 3 assume k = ∞, whereas all Table 1 experiments use finite k. Thus the sentence 'The following theoretical analysis supports the experimental results above' is not justified by the stated theorems, and the paper should either relegate the theory to a qualitative role or select experimental hyperparameters that fall inside the proven regime.","section":"Theorems 2-3 vs. Table 1"},{"comment":"Theorem 4 asserts convergence to the set of Nash equilibria with a finite restart interval, but its proof is a sketch. It invokes Lemma 7 and Lemma 8 as 'adapted from Abe et al. (2023)' without stating or proving them for the present algorithm, and it does not show that the periodic attachment update in Algorithm 1 produces the sequence z_att^{(n)} for which Lemma 7's strict decrease holds. The compactness and continuity argument is plausible but incomplete. The paper needs a full proof of these lemmas in the current setting, or a clear statement that Theorem 4 is conjectural.","section":"Appendix D, proof of Theorem 4"},{"comment":"The headline algorithm MoCFR+ (and its normal-form counterpart MoRM+) has no convergence guarantee in the paper. The RM+/OMD correspondence in Eq. (16) and Lemma 5 is imported from Farina et al. (2023) for the unmodified regret-matching update; the paper does not prove that this correspondence remains valid after the negative-momentum term -β(R_att - R_t) is inserted in Algorithm 2 and Eq. (21). Since the paper's main empirical claim concerns MoCFR+, the connection between the proven entropy-regularized MoMD analysis and the actual headline algorithm is an analogy rather than a theorem. The empirical results can stand on their own, but the paper should not describe them as supported by the theoretical analysis.","section":"Algorithm 2 and Eq. (21)"}],"minor_comments":[{"comment":"The text refers to 'Figure 5(a)' when discussing the divergence of GDAm with non-negative momentum; this should be Figure 1(a), since Figure 5 is the ablation figure in Appendix C.","section":"Introduction, after Eq. (8)"},{"comment":"There are typos: 'Yong's inequality' should be 'Young's inequality', and in the proof of Theorem 4 there is a stray parenthesis in 'each z(n)_att )'.","section":"Appendix D"},{"comment":"The text contains 'learing rate' instead of 'learning rate' and 'The experiment results' instead of 'The experimental results.'","section":"Appendix C"},{"comment":"The phrase 'norm-form' should be 'normal-form games'.","section":"Preliminaries"},{"comment":"Use consistent notation '3×3' instead of '3*3' for the matrix game.","section":"Table 1"},{"comment":"The strong claim that this is 'the first instance where an algorithm surpasses CFR+ performance across various types of games' should be tempered or substantiated with a more precise comparison to existing strong CFR variants, since the claim goes beyond the experiments reported here.","section":"Experiments, EFG section"}],"recommendation":"major_revision","confidential_remarks":"The manuscript would be substantially improved by separating the theoretical claims from the empirical claims. The Theorem 2 parameter-range error is repairable, but as written the theory does not cover the paper's headline algorithm, and the experiments lie outside the proven regime. I recommend major revision with a request to correct the proof, complete or clearly soften Theorem 4, and rephrase the theory/experiment support relationship."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. The empirical recipe is genuinely interesting: put a negative-momentum buffer in the dual space, restart it periodically, and plug the result into RM+/CFR+. The experiments span several game types and the reported gains over CFR+ and PCFR+ are large. If the numbers are reproducible, this is a useful trick for tabular equilibrium computation. Code is provided, which is a point in its favor.\n\nThe problems start when you look at the theory. Theorem 2, the centerpiece, does not go through as written. In Appendix D the final step requires C = -1 - (3/2)beta - 4*eta^2/beta to be non-positive, and the paper claims that follows from -2/3 < beta < 0 and eta <= sqrt(-(1+3*beta/2)*beta/2). That is algebraically wrong: for beta = -0.5, eta = 0.2, C = 0.07 > 0. The correct threshold appears to be eta <= sqrt(-beta*(1+3*beta/2)/4), a factor sqrt(2) smaller. And even the corrected bound is violated by every MoMWU hyperparameter in Table 1: for the 25-action random game beta = -0.02, eta = 7 versus a bound around 0.07. So the text's claim that the theory supports the experiments is false. The theorem also assumes k = infinity; all experiments use finite k.\n\nThe other theorems inherit the issue. Theorem 3 uses Theorem 2's contraction, so its bias bound does not apply. Theorem 4 is a sketch that depends on lemmas \"adapted\" from Abe et al. without full proofs; the continuity of the map f(z_att) = z*_att is asserted, not shown. Finally, the bridge to RM+/CFR+ is analogy, not theorem. Equation (21) is not a consequence of the entropy-regularizer proof; MoRM+ and MoCFR+, which drive the headline numbers, have no convergence theorem at all.\n\nMinor points: no error bars, hyperparameters are per-game, and the appendix ablation partly addresses sensitivity but not enough to rule out that the gains come from tuning. These are minor relative to the theory gap.\n\nWho should read this: anyone working on tabular game solvers will find the empirical phenomenon worth knowing, and the algorithm is simple enough to try. But they should not rely on the paper's theorems.\n\nRecommended handling: send to a serious referee, not desk reject. The empirical contribution is potentially valuable and the paper is clear enough that a referee can pinpoint what needs fixing. The authors should either correct the parameter range and prove a real contraction, or drop the theory and present MoCFR+ as an empirical heuristic with a thorough sensitivity study. I would reject the current version, but not the underlying idea.","headline":"Empirically promising negative-momentum acceleration of RM+/CFR+, but the main theorem has a parameter-range error and the proof does not cover the algorithms that produce the headline results.","tokens_in":23487,"tokens_out":3922,"would_cite":false,"duration_ms":37424,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Negative momentum, borrowed from unconstrained games, carries over to constrained minimax solvers and yields the first algorithm reported to surpass CFR+ across multiple game types, with MoCFR+ reaching about $10^9$ times lower…","keywords":["negative momentum","minimax games","constrained optimization","regret matching","counterfactual regret minimization","extensive-form games","last-iterate convergence","exploitability"],"falsifier":"Run MoCFR+ and CFR+ on the same four games with identical alternation, averaging, and hyperparameter-selection protocols; if the exploitability gap does not remain roughly $10^9$ across seeds, the headline claim fails. A sharper check is to write the MoRM+ update from Algorithm 2 as an instance of online linear optimization: if the negative-momentum term $-\\beta(R_{\\text{att}} - R_t)$ cannot be expressed as a valid loss sequence under the FTRL/OMD-to-RM+ correspondence, then the theoretical bridge that justifies MoRM+ is broken.","tokens_in":22374,"feed_emoji":"🃏","tokens_out":11596,"duration_ms":100128,"temperature":0.7,"pith_summary":"This paper sets out to show that negative momentum, an acceleration trick known from unconstrained bilinear games, can be carried over to constrained minimax games and sharply speed up the standard solvers. The authors propose a momentum buffer kept in the dual space and updated with a negative coefficient $\\beta<0$, plus a \"Restarting Aggregated Momentum\" (RAM) pattern that periodically re-anchors the buffer; the mechanism drops into online mirror descent, FTRL, and regret matching. The theoretical part proves exponential convergence to an approximate equilibrium for the entropy-regularized momentum algorithm with an infinitely long buffer, and convergence to Nash equilibrium with a sufficiently large buffer. The experimental part reports that the regret-matching variant MoCFR+ reaches roughly $10^9$ times lower exploitability than CFR+ and outperforms PCFR+ on Kuhn Poker, Leduc Poker, Goofspiel, and Liar's Dice, which the authors describe as the first algorithm to surpass CFR+ across these game types. Because CFR+ is the standard strong solver for imperfect-information games, the result matters as a simple route to faster equilibrium finding.","feed_headline":"Negative momentum lifts game solvers 10^9 times closer to equilibrium","feed_subtitle":"A simple historical-gradient buffer makes classic game solvers overtake stronger baselines in poker and bidding games.","key_machinery":"The load-bearing object is the momentum buffer kept in the dual space, $\\mu_t = \\beta\\mu_{t-1} - F(z_t)$ with the negative coefficient $\\beta<0$, together with its \"Restarting Aggregated Momentum\" (RAM) extension that sums buffer snapshots over an interval of length $k$ and periodically re-anchors an attachment point $L_{\\text{att}}$ in the FTRL form $L_t = L_{t-1} + F(z_t) - \\beta(L_{\\text{att}} - L_{t-1})$. The negative sign turns the usual momentum extrapolation into a friction-like drag that damps oscillation in the strategy trajectory. The machinery is transferred to regret matching through the known FTRL/OMD-to-RM+ correspondence, where the attachment regret vector $R_{\\text{att}}$ plays the anchor role, producing Algorithm 2 (MoRM+).","core_discovery":"The central claim is that negative momentum, stored as a dual-space buffer $\\mu_t = \\beta\\mu_{t-1} - F(z_t)$ with $\\beta<0$, is a universal acceleration mechanism for constrained zero-sum solvers. Plugged into mirror descent or FTRL, it yields updates $z_{t+1} = \\arg\\min_z\\{\\eta\\langle z, -\\mu_t\\rangle + D_\\psi(z,z_t)\\}$; with negative entropy as the regularizer and an infinitely large buffer, the algorithm converges exponentially to the regularized equilibrium $z^*$ of a modified game (Theorem 2), that point is an $O(-\\beta/\\eta)$-Nash equilibrium of the original game (Theorem 3), and with the RAM buffer re-anchored every $k$ steps the algorithm converges to the set of Nash equilibria (Theorem 4). The same buffer is grafted onto the regret update of RM+, giving $R_{t+1} = [R_t + r(x_t) - \\beta(R_{\\text{att}} - R_t)]_+$, which defines MoRM+ and, through regret decomposition, MoCFR+; the experiments claim these variants dominate their base algorithms and state-of-the-art baselines, with MoCFR+ reaching roughly nine orders of magnitude lower exploitability than CFR+.","pith_inferences":["The paper proves convergence only for the entropy-regularized mirror-descent variant; whether the FTRL/OMD-to-RM+ correspondence survives with the negative-momentum term is left open, so the impressive MoCFR+ numbers currently rest on an analogy rather than a theorem.","An adaptive rule for the re-anchoring interval $k$ — for example, triggering a reset when exploitability stalls — could make the method free of per-game tuning, since the paper's own ablation shows a stair-step pattern when $k$ is too large.","The same dual-space buffer could be applied to Monte Carlo variants of CFR or to optimistic/predictive updates, where stochastic gradients would test whether the friction-like damping survives noise; that extension is not explored in the paper.","A protocol-stricter comparison — simultaneous updates, untuned $\\beta$, and identical averaging schemes across algorithms — would clarify how much of the reported $10^9$ advantage comes from the negative momentum itself rather than from alternation and averaging choices."],"forward_implications":["MoCFR+ reaches exploitability about $10^9$ times lower than CFR+ and outperforms PCFR+ on all four tested extensive-form games, a claimed first for any algorithm across those game types.","The negative-momentum buffer applies uniformly to OMD and FTRL instantiations such as MoMWU and DMoGDA, so existing game solvers can be upgraded by altering only the buffer/loss update.","With negative entropy regularizer and an infinite buffer, convergence is exponential to an $O(-\\beta/\\eta)$-equilibrium; with finite $k$ under RAM, the algorithm provably reaches the exact Nash set.","Larger $|\\beta|$ accelerates convergence but biases the regularized equilibrium away from Nash, exposing an explicit speed-accuracy tradeoff controlled by $\\beta$ and $k$."],"supporting_citations":[{"why":"introduced negative momentum for unconstrained bilinear games, the technique this paper ports to constrained settings","marker":"Gidel et al. 2019"},{"why":"supplies Lemma 5, the FTRL/OMD-to-RM+ regret correspondence used to justify MoRM+","marker":"Farina et al. 2023"},{"why":"defined RM+/CFR+, the base solver whose exploitability MoCFR+ improves","marker":"Tammelin 2014"},{"why":"defined regret matching, the foundational oracle that RM+ and MoRM+ modify","marker":"Hart and Mas-Colell 2000"},{"why":"provides the regret-decomposition framework for turning local regret minimizers into CFR-style extensive-form solvers","marker":"Farina, Kroer, and Sandholm 2019a"},{"why":"defines treeplexes, the sequence-form strategy spaces the extensive-form methods operate on","marker":"Hoda et al. 2010"},{"why":"introduces dilated distance-generating functions used to build the treeplex momentum variants","marker":"Farina, Kroer, and Sandholm 2019b"},{"why":"establishes the alternating-update scheme adopted by MoRM+ and MoCFR+","marker":"Burch, Moravcik, and Schmid 2019"},{"why":"introduces PCFR+, the state-of-the-art baseline MoCFR+ claims to outperform","marker":"Farina, Kroer, and Sandholm 2021b"}],"fun_headline_variants":["Negative momentum brings game solvers 9 orders closer to equilibrium","Universal negative momentum technique accelerates constrained minimax solvers","Negative momentum leads to exponential convergence in minimax games","Negative momentum beats SOTA in poker and bidding game solvers","One new buffer: negative momentum supercharges classic game solvers"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the negative-momentum trick, proven to converge in one particular regularized mirror-descent setting, still works when grafted into the different regret-matching update that the headline experiments use; no theorem in the paper covers that grafted algorithm.","fun_headline_variants_meta":{"raw":{"variants":["Negative momentum brings game solvers 9 orders closer to equilibrium","Universal negative momentum technique accelerates constrained minimax solvers","Negative momentum leads to exponential convergence in minimax games","Negative momentum beats SOTA in poker and bidding game solvers","One new buffer: negative momentum supercharges classic game solvers"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001044,"raw_usage":{"total_tokens":4383,"prompt_tokens":932,"completion_tokens":3451,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":548,"completion_tokens_details":{"reasoning_tokens":3368}},"tokens_in":548,"tokens_out":3451,"duration_ms":22987,"temperature":1.0,"reasoning_tokens":3368,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T22:49:43.079285+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run MoCFR+ and CFR+ on the same four games with identical alternation, averaging, and hyperparameter-selection protocols; if the exploitability gap does not remain roughly $10^9$ across seeds, the headline claim fails. A sharper check is to write the MoRM+ update from Algorithm 2 as an instance of online linear optimization: if the negative-momentum term $-\\beta(R_{\\text{att}} - R_t)$ cannot be expressed as a valid loss sequence under the FTRL/OMD-to-RM+ correspondence, then the theoretical bridge that justifies MoRM+ is broken.","supporting_citations":[{"cited_title":"A.; Pezeshki, M.; Le Priol, R.; Huang, G.; Lacoste-Julien, S.; and Mitliagkas, I","cited_arxiv_id":null,"evidence_quote":"introduced negative momentum for unconstrained bilinear games, the technique this paper ports to constrained settings"},{"cited_title":"Regret Matching+: (In)Stability and Fast Convergence in Games","cited_arxiv_id":"2305.14709","evidence_quote":"supplies Lemma 5, the FTRL/OMD-to-RM+ regret correspondence used to justify MoRM+"},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"defined regret matching, the foundational oracle that RM+ and MoRM+ modify"},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"defines treeplexes, the sequence-form strategy spaces the extensive-form methods operate on"},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"establishes the alternating-update scheme adopted by MoRM+ and MoCFR+"}],"review_version":1}