{"id":"3a1bb75f-4aac-4000-a006-8e328e26dd67","arxiv_id":"2505.15454","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Optimistic no-regret learning converges pointwise to a Nash equilibrium in games with non-negative weighted regret, including harmonic games, when the equilibrium set is discrete.","lead":"This paper introduces non-negative weighted regret, a generalization of non-negative regret for strategic games, and shows that optimistic no-regret algorithms converge to approximate Nash equilibria and, under a discrete equilibrium set, pointwise to a Nash equilibrium. The framework covers harmonic games and several zero-sum game classes, and the authors claim the first pointwise convergence result of this kind.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corruption section is ill-posed: the update x^{t+1} = \\tilde x^{t+1} + c^{t+1} can leave the simplex, so Theorems 7.1-7.5 do not define a legal game dynamic or an approximate Nash equilibrium.","rationale":"The non-corrupted pointwise-convergence claim (Theorems 6.1-6.3) appears internally sound: the weighted-regret bound yields a uniform bound on the sum of squared update sizes, Theorem 6.2 extracts Nash limits, and Lemma B.5 converts a finite limit set plus vanishing increments into pointwise convergence. I do not find a fatal flaw there. The reader's weakest_assumption about the fixed weight vector is a legitimate scope condition, but for harmonic games it is proven in Lemma 5.1, so it is not an internal inconsistency. The load-bearing defect I find is in Section 7: the corruption model does not keep played strategies in the simplex, so the robustness results are ill-defined. This should be fixed before accepting the advertised robustness claim; it does not overturn the non-corrupted theorems, so the reader's CONDITIONAL verdict is appropriate.","tokens_in":19999,"tokens_out":26345,"duration_ms":229640,"concrete_test":"Analytical check: specialize to the matching-pennies game of Section 8 with entropy OMD. At any round t take the uncorrupted iterate \\tilde x^t_1 = (0.1, 0.9) and set c^t_1 = (-0.2, 0.2), with all other corruption zero. The total corruption is finite and no condition in Definition 7.1 is violated, but x^t_1 = (-0.1, 1.1) \\notin \\Delta(A_1), so v_1(x^t) and the approximate-NE predicate for x^t are undefined. A second check: add the explicit feasibility constraint \\tilde x^{t+1}_i + c^{t+1}_i \\in \\Delta(A_i) for all i,t and re-derive the display after Eq. (D.2); if the bound in Theorem 7.1 still follows, the issue is a missing assumption rather than a deeper algebraic error.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Definition 7.1 and the corrupted OMD/OFTRL updates impose only \\sum_t \\|c^t_i\\|_1 \\le C_i < \\infty. They never require \\tilde x^{t+1}_i + c^{t+1}_i \\in \\Delta(A_i). A finite-\\ell_1 vector can have negative coordinates or entries exceeding 1, so the 'played strategy' x^{t+1}_i can lie outside the simplex. Every subsequent object in Section 7 is then undefined or game-theoretically meaningless: v^{t+1}_i = v_i(x^{t+1}) is evaluated outside \\Delta(A), the regret mReg^T_i is taken with respect to a non-strategy, and the statement 'x^t is an \\epsilon-approximate Nash equilibrium' is only defined for x^t \\in \\Delta(A). This is not a missing technical detail: the robustness theorem advertised in the abstract depends on these corrupted dynamics, and the proof of Theorem 7.1 uses \\|v^t_i\\|_\\infty \\le 1 and the approximate-NE predicate for x^t. The gap can likely be repaired by adding a feasibility constraint c^t_i \\ge -\\tilde x^{t+1}_i and \\sum_j c^t_{i,j} \\le 1 - \\sum_j \\tilde x^{t+1}_{i,j}, or by projecting back to the simplex, but as written the corruption theorems are internally inconsistent.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a class of games with non-negative weighted regret, a weighted generalization of the non-negative regret property of Anagnostides et al. It shows that optimistic mirror descent (OMD) and optimistic follow-the-regularized-leader (OFTRL) reach an epsilon-approximate Nash equilibrium in O(1/epsilon^2) iterations in such games, and that their iterates converge pointwise to a Nash equilibrium when the equilibrium set is discrete. Harmonic games are shown to have non-negative weighted regret, which yields the paper's advertised first pointwise convergence results for harmonic games, alongside extensions to several zero-sum classes. A final section claims the same convergence guarantees persist under finite cumulative corruption of the played strategies, and the theoretical results are supplemented by small experiments on matching pennies and a harmonic game.","tokens_in":20279,"tokens_out":15353,"duration_ms":127301,"significance":"If the technical gaps are repaired, this is a valuable contribution: the non-negative weighted regret framework plausibly unifies previously disparate convergence results for harmonic and zero-sum games, and the tail-summability argument leading to pointwise convergence under a discrete equilibrium set is a clean and non-obvious step. The OMD proof is largely coherent and follows standard optimistic-regret machinery with an independent algebraic verification of the harmonic-game property in Lemma 5.1. The paper also makes a concrete falsifiable prediction about the behavior of OMD and OFTRL in harmonic games, supported by experiments. However, the corruption model is currently not well-posed, and the OFTRL results depend on an equivalence proof with a genuine technical gap, so the advertised robustness and OFTRL contributions are not yet established as written.","major_comments":[{"comment":"The corrupted update x^{t+1}_i = \\tilde x^{t+1}_i + c^{t+1}_i imposes no constraint that x^{t+1}_i lies in the simplex \\Delta(A_i), so the 'played strategy' may have negative coordinates or coordinate sum different from 1. Because the paper defines utilities, payoff fields, regret, and approximate Nash equilibrium only for probability distributions, the objects v_i(x^{t+1}), mReg^T_i, and the statement 'x^t is an epsilon-approximate Nash equilibrium' are undefined for such iterates; the proof of Theorem 7.1 also uses \\|v_i^t\\|_\\infty \\le 1, which can fail outside the simplex. This gap affects every robustness theorem in Section 7 and the abstract's claim that convergence persists under finite deviations. The section can be repaired by constraining c^t_i so that x^t_i stays in the simplex (for example, c^t_i \\ge -\\tilde x^{t+1}_i and \\sum_j c^t_{i,j} \\le 1 - \\sum_j \\tilde x^{t+1}_{i,j}) or by projecting the corrupted point back onto the simplex, but as written the corruption theorems are internally inconsistent.","section":"Section 7 (Definition 7.1; Theorems 7.1-7.5)"},{"comment":"The base case of the claimed OMD/OFTRL equivalence asserts \\nabla R_i(g^0_i)=0 because g^0_i = \\arg\\min_{x_i \\in \\Delta(A_i)} R_i(x_i). The constrained first-order condition only gives a normal-cone condition; for an interior minimizer of a Legendre regularizer, \\nabla R_i(g^0_i) is a constant multiple of the all-ones vector (or, more generally, lies in the normal cone), not necessarily zero. If \\nabla R_i(g^0_i) is not constant on the simplex, the maximizers \\hat x^1_i and x^1_i need not coincide, and the induction establishing \\hat x^t = x^t collapses. Since Theorems 6.4 and 6.5 rely entirely on this equivalence, the OFTRL convergence results are not established as written; a normal-cone argument or a different initialization is needed.","section":"Appendix C (proof of Theorem 6.4)"},{"comment":"Even after enforcing feasibility, the corruption analysis should clarify which strategy the regret benchmark is taken against. Lemma D.2 begins with a decomposition involving \\tilde x^t_i and x^t_i, but Definition 5.1 for mReg^T_i is stated for the played sequence x^t. The decomposition itself is algebraically valid, but the text does not explicitly define the corrupted regret with respect to the actually played strategies; this ambiguity, combined with the Definition 7.1 notation swap described in the minor comments, makes the corruption theorems difficult to verify as stated.","section":"Appendix D (Lemma D.2 and Theorem 7.1)"}],"minor_comments":[{"comment":"The abstract is truncated: 'even if the players deviate Our theoretical findings are supported...' needs to be completed.","section":"Abstract"},{"comment":"The notation is inconsistent with the updates: the text calls \\tilde x the 'committed' strategy and x the 'algorithm output', but in the OMD and OFTRL updates x is the corrupted played strategy and \\tilde x is the uncorrupted algorithm output; the variables should be swapped or the wording clarified.","section":"Definition 7.1"},{"comment":"The proof cites Theorems 7.3 and 7.2; it should refer to the corresponding OMD/OFTRL results, presumably Theorem 6.4 and Theorem 6.2.","section":"Proof of Theorem 6.5"},{"comment":"Several cross-references appear to be off after renumbering: the proof of Theorem 7.2 refers to 'Theorem 8.1' and 'Theorem B.1', and Appendix D refers to 'Lemma C.1', 'Theorem D.2', and 'Theorem D.3' rather than the actual theorem numbers.","section":"Cross-references in Appendices B-D"},{"comment":"The displayed iteration bound is typeset with missing plus signs, making the formula unreadable; for example the terms involving \\sum_i M_i C_i and \\sum_i C_i are not visibly separated.","section":"Theorems 7.1 and 7.4"},{"comment":"There is a typo 'Norm-form game' in Definition 3.3, and in Lemma 5.2 the phrase 'Takem_i = 1' is missing a space; these should be corrected during revision.","section":"Sections 3 and 5"}],"recommendation":"major_revision","confidential_remarks":"The core idea is promising and the OMD pointwise-convergence argument is an elegant contribution. However, the corruption section is currently not well-posed because the corrupted iterates leave the simplex, and the OFTRL equivalence proof has a genuine first-order-condition gap at the base case. Both issues are local and repairable within the scope of a revision, so I recommend major revision rather than rejection. The paper would also benefit from a careful pass over all appendix cross-references before resubmission."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear —,\n\nThe main result is worth knowing: Theorem 6.3 gives the first pointwise convergence to an actual Nash equilibrium for optimistic mirror descent (and OFTRL) in harmonic games when the equilibrium set is finite. Lemma 5.1 correctly places harmonic games inside their new non-negative weighted regret class, and the proof of the main theorem is a clean RVU-style optimistic regret bound followed by a short argument that sequences with vanishing increments cannot oscillate between isolated limit points. I checked the algebra in Lemma 5.1 and the averaging step in Theorem 6.1; both go through. The extension from APFS22 is mathematically mild (player-specific positive weights), but it is exactly what lets harmonic games in, and the pointwise convergence result is a genuine improvement over LMP+24a's convergence-to-the-set.\n\nThe soft spot is the corruption section. The stress-test note is right: Definition 7.1 and the update rule define x^t = \\tilde x^t + c^t with only a finite-l1 budget on c^t, so x^t can leave the simplex. Then v_i(x^t), the regrets, and the approximate-NE predicate are not defined for out-of-simplex points, and the proof's step ||v^t_i||_inf <= 1 fails. This is repairable — add a feasibility constraint or project back — but as written Theorems 7.1–7.5 are not meaningful. It is a real gap, but it does not affect the main non-corrupted results.\n\nMinor points: the experiments are two small games with no code or error bars, and the writing has several typos and a truncated abstract. The proof of Lemma B.5 drops a factor of 2 in the triangle inequality, but the argument survives by adjusting epsilon.\n\nBottom line: the paper's central contribution is sound and worth a serious referee. I would encourage the authors to fix the corruption definition and clean up the presentation.\n\nRecommendation: peer review, with the corruption rewrite as a condition.","headline":"Pointwise convergence for harmonic games is real and new; the corruption section is ill-posed as written, but repairable without touching the main theorem.","tokens_in":20812,"tokens_out":9900,"would_cite":true,"duration_ms":80547,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A10","91A26"],"pacs":[],"model":"deepseek-v4-flash","headline":"Optimistic no-regret play converges pointwise to Nash equilibria","keywords":["non-negative weighted regret","harmonic games","zero-sum games","optimistic mirror descent","optimistic follow the regularized leader","pointwise convergence","Nash equilibrium","corrupted learning dynamics"],"falsifier":"Run OMD or OFTRL with a constant learning rate in a finite game whose non-negative weighted regret property has been verified directly from Definition 5.2, and record the first iteration at which the joint strategy is an $\\epsilon$-approximate Nash equilibrium. If the required number of iterations is not $O(1/\\epsilon^2)$, or if the iterates fail to converge to the equilibrium set while the certificate holds, Theorems 6.1 and 6.2 are false. A more local test targets Lemma 5.1: for a small harmonic game, use the weights constructed in the lemma and search over strategy sequences for a negative value of $\\sum_{i=1}^n m_i\\mathrm{Reg}^T_i$, which would contradict the claimed certificate.","tokens_in":19768,"feed_emoji":"🎯","tokens_out":11342,"duration_ms":86893,"temperature":0.7,"pith_summary":"This paper introduces a property it calls non-negative weighted regret: there is a fixed vector of positive player weights $m$ such that, for every finite sequence of strategy profiles, the weighted sum of the players' regrets is non-negative. It argues that this property covers harmonic games and several classes of zero-sum games, and that under it the optimistic algorithms OMD and OFTRL reach an $\\epsilon$-approximate Nash equilibrium in $O(1/\\epsilon^2)$ iterations and converge to the set of Nash equilibria. When the set of Nash equilibria is discrete, meaning finitely many equilibria, the iterates converge to a single Nash equilibrium rather than merely to the set. Convergence to the equilibrium set, and to a single equilibrium when the set is discrete, also survives finite cumulative deviations by players from their prescribed strategies. If the arguments are right, this supplies the first pointwise convergence guarantees for harmonic games and for games with non-negative regret.","feed_headline":"Optimistic no-regret play converges pointwise to Nash equilibria","feed_subtitle":"New weighted-regret condition covers harmonic and zero-sum games; finite equilibria make iterates settle.","key_machinery":"The central objects are the weighted individual regret $m_i\\mathrm{Reg}^T_i = \\max_{x^*\\in\\Delta(A_i)}\\sum_{t=1}^T m_i\\langle x^*-x_i^t, v_i^t\\rangle$ and the game property $\\sum_{i=1}^n m_i\\mathrm{Reg}^T_i \\ge 0$ for one fixed positive vector $m$, required to hold for every finite sequence of strategy profiles. The engine of the proof is an optimistic-regret inequality that bounds each player's weighted regret by a Bregman-divergence telescope plus the cumulative variation of the payoff field, minus the squared distances between the played strategy, the optimistic state, and the previous optimistic state. Summing these inequalities and invoking non-negative weighted regret gives a uniform bound on $\\sum_{i=1}^n\\sum_{t=1}^T(\\|x_i^t-g_i^t\\|^2+\\|x_i^t-g_i^{t-1}\\|^2)$, which forces the iterates to become approximate equilibria and consecutive updates to vanish. The final step is a lemma about sequences in a compact set: a bounded sequence that converges to a finite set $E$ and whose consecutive terms get arbitrarily close must converge to one point of $E$.","core_discovery":"The central claim is that conflicting-interest games can be analysed through a single weighted-regret certificate, and that optimistic no-regret learning has pointwise convergence in exactly the games that carry it. Concretely, Theorem 6.1 gives an $O(1/\\epsilon^2)$ bound on the number of OMD iterations needed to produce an $\\epsilon$-approximate Nash equilibrium, and Theorem 6.2 upgrades the conclusion to convergence of the whole sequence to the equilibrium set; Theorems 6.4 and 6.5 state the parallel guarantees for OFTRL. The pointwise step, Theorem 6.3, says that if the equilibrium set is discrete, then the iterates converge to one Nash equilibrium, not just to the set. The proof route is a regret bound whose summing yields a uniform bound on the squared sizes of the optimistic updates, followed by a compactness argument showing that a bounded sequence with vanishing consecutive differences that accumulates at finitely many Nash equilibria must settle on one of them. The corruption theorems extend the same two-stage argument to play that deviates finitely from the algorithmic output.","pith_inferences":["The proof only uses the weighted-regret certificate through the summed bound on update sizes, so other optimistic or regularized dynamics that admit the same type of inequality should inherit both the $O(1/\\epsilon^2)$ rate and the pointwise convergence in this game class.","Because the certificate quantifies over all finite sequences, one could in principle search for a witnessing weight vector $m$ computationally for small games, turning non-negative weighted regret into a checkable sufficient condition rather than an assumed property.","The finite-corruption result suggests a natural testable extension toward vanishing but non-summable noise: the stated proofs rely on finite total corruption, so decaying errors that still sum to infinity would be the next boundary case.","Potential games sit outside the framework as the paper notes; testing whether any potential game with multiple equilibria can have non-negative weighted regret would clarify exactly where the certificate stops."],"forward_implications":["In every finite normal-form game that satisfies non-negative weighted regret, both OMD and OFTRL find an $\\epsilon$-approximate Nash equilibrium in $O(1/\\epsilon^2)$ iterations; the bound depends on the weights, regularizers, and norm constants.","If the game has finitely many Nash equilibria, the actual sequence of play converges to one of them; no uniqueness or condition-number assumption is needed.","For two-player zero-sum games with a unique equilibrium this recovers earlier pointwise convergence results as a special case of the discrete-equilibrium theorem.","Finite cumulative deviations by players do not destroy convergence: the iterates still approach the Nash equilibrium set, and with finitely many equilibria they still converge to an equilibrium.","In harmonic games, the result strengthens the known asymptotic convergence to the equilibrium set into pointwise convergence to an equilibrium whenever the equilibrium set is discrete."],"supporting_citations":[{"why":"Supplies the base notion of non-negative regret, the zero-sum game classes used in Lemma 5.2, and the remark that its own technique stops short of pointwise convergence.","marker":"[APFS22]"},{"why":"Provides the harmonic-game definition used here and the asymptotic convergence to the equilibrium set that this paper strengthens to pointwise convergence.","marker":"[LMP+24a]"},{"why":"Gives last-iterate convergence for optimistic multiplicative weights in two-player zero-sum games, the baseline recovered by the discrete-equilibrium theorem.","marker":"[DP19]"},{"why":"Supplies the optimistic no-regret framework and the regret-versus-variation bounds underlying the OMD and OFTRL analysis.","marker":"[SALS15]"},{"why":"Introduces online learning with predictable sequences, the template for the optimistic regret inequality in Lemma B.2.","marker":"[RS13]"},{"why":"Gives the harmonic/potential decomposition and the harmonic-game characterization used in Lemma 5.1.","marker":"[APSV22]"},{"why":"Provides the corruption-level definition and the prior OFTRL variant for corrupted dynamics that this paper extends to Nash equilibria.","marker":"[TIL24]"}],"fun_headline_variants":["Weighted regret condition yields pointwise Nash convergence","Optimistic mirror descent converges pointwise to Nash","No-regret learners find Nash in conflicting games","Finite Nash set implies pointwise convergence","OMD and OFTRL achieve pointwise Nash equilibrium"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the existence of one fixed positive weight vector $m$ such that every finite sequence of strategy profiles in the game has non-negative weighted total regret; the harmonic-game special case constructs such an $m$ from the harmonic weights, but for the general theorem the property is assumed, and if it fails the uniform bound on squared update sizes collapses.","fun_headline_variants_meta":{"raw":{"variants":["Weighted regret condition yields pointwise Nash convergence","Optimistic mirror descent converges pointwise to Nash","No-regret learners find Nash in conflicting games","Finite Nash set implies pointwise convergence","OMD and OFTRL achieve pointwise Nash equilibrium"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000296,"raw_usage":{"total_tokens":1705,"prompt_tokens":918,"completion_tokens":787,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":534,"completion_tokens_details":{"reasoning_tokens":715}},"tokens_in":534,"tokens_out":787,"duration_ms":6891,"temperature":1.0,"reasoning_tokens":715,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T15:19:32.044072+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run OMD or OFTRL with a constant learning rate in a finite game whose non-negative weighted regret property has been verified directly from Definition 5.2, and record the first iteration at which the joint strategy is an $\\epsilon$-approximate Nash equilibrium. If the required number of iterations is not $O(1/\\epsilon^2)$, or if the iterates fail to converge to the equilibrium set while the certificate holds, Theorems 6.1 and 6.2 are false. A more local test targets Lemma 5.1: for a small harmonic game, use the weights constructed in the lemma and search over strategy sequences for a negative value of $\\sum_{i=1}^n m_i\\mathrm{Reg}^T_i$, which would contradict the claimed certificate.","supporting_citations":[],"review_version":1}