{"id":"e87ae04c-d735-4667-9221-6d45ad7e05a1","arxiv_id":"2412.07120","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"New no-regret learning dynamics achieve external and swap regret bounds that adapt to cumulative strategy and utility corruption in games.","lead":"This paper designs learning algorithms for repeated games in which players may deviate from a prescribed strategy or receive corrupted utility information. The algorithms' regret bounds shrink as the total amount of deviation shrinks, and they match the best known rates when all players are honest.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 22's stability proof does not close: the negative term in (27) scales as m^{-1/4} after summation, while the positive quadratic term in (30) is O(1/m), so the key condition sum_a ||y_a^{t+1}-y_a^t|| <= 1/2 is not established for large m.","rationale":"The reader correctly identified Lemma 22 as the weakest assumption, and this stress-test confirms that the proof of that lemma contains a serious gap. The central claim of the paper includes Theorem 9, whose honest-regime rate and corrupted-regime bounds both depend on the stability condition sum_a ||y_a^(t+1)-y_a^(t)|| <= 1/2. The proof of Lemma 22 as written does not establish this condition: the positive quadratic lower bound is O(1/m) while the negative linear terms are O(m^{-1/4}) after summation, so the final inequality in the proof cannot hold for large m. There is also a dimension mismatch in (27), where the factor sqrt(m) from Lemma 21 is omitted. This is not merely a cosmetic issue: if the stability condition fails, the Markov-chain analysis in Lemma 24 and the RVU bound in Lemma 17 cannot be applied, and the swap-regret bound of Theorem 9 is unsupported. The reader's verdict of ACCEPT with moderate confidence should therefore be adjusted to CONDITIONAL: the paper should not be accepted in its current form; it needs either a corrected proof of Lemma 22 (e.g., with a smaller learning-rate cap of order 1/(n m) or a sharper potential argument) or a reformulation of the theorem. The two-player zero-sum results (Theorem 6) are less affected, as they use a different (Shannon-entropy) analysis, but the main novelty for general-sum games depends on the stability lemma.","tokens_in":1195,"tokens_out":3039,"duration_ms":141625,"concrete_test":"Recompute the key inequality in Lemma 22 for a concrete instance: take m=16, n=2, T=3, setting the utilities u_tilde^{(t)}=0 so the learning rate in (6) is at its cap eta=1/(256*n*sqrt(m))=1/2048, and take x_hat^{(t)} uniform over the 16 actions. Evaluate the lower bound in (28) summed over a: the negative term is about (1/2)*(3+4*sqrt(log 3))*sqrt(eta) ≈ 0.032, while the positive term from (30) is 15/(128*16) ≈ 0.0073, so the claimed G(z) >= G(y^{(t)}) fails. Then directly simulate the OFTRL updates in (6) for this instance and check whether sum_{a} ||y_a^{(2)} - y_a^{(1)}||_{y_a^{(1)}, F_a^{(2)}} <= 1/2; if this inequality is violated, Lemma 22 is false and the bound in Theorem 9 collapses.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The paper's central swap-regret guarantee (Theorem 9) rests on Lemma 22, which asserts that under the adaptive learning rate (6) the sum of local norms of successive log-barrier OFTRL iterates over all experts is at most 1/2. This condition is needed both for the RVU bound in Lemma 17 and for the Markov-chain stability lemma (Lemma 24); if it fails, the proof of Theorem 9 collapses. The proof of Lemma 22 appears not to close. It applies Lemma 20 on a product-space sphere of radius 1/(2*sqrt(m)), so the positive quadratic gain in (30) is 15/(128m). The negative linear terms in (27)-(28), however, are of order sqrt(eta) ~ m^{-1/4} after summing over the m experts, because Lemma 21 and ||grad phi|| <= sqrt(m) contribute a factor of m * sqrt(log T) * sqrt(eta/m), which cancels to sqrt(m log T) * sqrt(eta) and then to m^{-1/4}. For large m this negative term dominates the O(1/m) positive term. Additionally, the displayed bound in (27) drops the sqrt(m) factor present in Lemma 21, making the expression dimensionally inconsistent and the final inequality in the proof (which claims the negative term is at most 15/128) unjustified. Thus the stability condition sum_a mu_a^{(t)} <= 1/2 is not established as written, and with it the honest-regime rate O(nm^{5/2} log T) and the corrupted-regime bounds in Theorem 9 are unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a corrupted-regime model for learning in games in which players may deviate from the output of a prescribed OFTRL algorithm and may also observe corrupted utilities. The main claims are corruption-dependent external regret bounds for two-player zero-sum games (Theorem 6) and corruption-dependent swap regret bounds for multi-player general-sum games (Theorem 9), together with lower bounds (Theorem 10). The central technical device for the general-sum result is a stability lemma (Lemma 22) that asserts a uniform bound on the sum, over all experts, of local norms of successive log-barrier OFTRL iterates under a carefully capped adaptive learning rate. This stability bound is used to apply an RVU bound for self-concordant barriers and a Markov-chain stability lemma from prior work.","tokens_in":41503,"tokens_out":13163,"duration_ms":149633,"significance":"If the results are correct, the paper gives the first regret bounds that degrade gracefully with the amount of corruption in strategies and utilities, and it matches the best honest-regime swap regret bound while being agnostic to the corruption levels. The zero-sum external regret analysis and the lower bounds are interesting and appear largely self-contained, with no fitted parameters and no circularity. The general-sum swap regret contribution, however, is the paper's flagship extension, and its correctness rests entirely on the stability of the Markov chain under the adaptive learning rate. That stability proof does not close as written, so the swap-regret half of the paper is not yet supported.","major_comments":[{"comment":"The proof of the key stability condition does not close. After summing the linear lower bound (27) over a in A, the negative contribution is at least of the form (1/2)(3 sqrt(eta/m) + sqrt(16 eta / log T)) up to the simplex-sum bounds, because sum_a sqrt(hat x^{t-1}(a) + hat x^{t-2}(a)) <= sqrt(2m). With the cap eta <= 1/(256 n sqrt m), the second term is of order m^{-1/4}, while the positive quadratic term in (30) is 15/(128m). Thus for large m the negative term dominates the positive term, and the claimed inequality G^{(t+1)}(z) >= G^{(t+1)}(y^{(t)}) is not established. The sentence attributing the final inequality to T >= 3 and eta <= 1/256 is therefore unjustified. Consequently Lemma 20 cannot be invoked to conclude (23).","section":"E.2, Lemma 22 (Eqs. (27)-(30))"},{"comment":"Because Lemma 22 is the only supplied mechanism for proving sum_a mu_a^{(t)} <= 1/2 (Lemma 23), the applications of the RVU bound in Lemma 17 and the Markov-chain tree lemma in Lemma 24 are unsupported. The swap regret bounds in Theorem 9, including the honest-regime rate O(n m^{5/2} log T) and the corrupted-regime terms, therefore collapse unless Lemma 22 is repaired. The scaling issue in the proof of Lemma 22 is not cosmetic: with the current cap eta_{i,max} = 1/(256 n sqrt m), the negative term in the stability proof is too large relative to the positive quadratic term, so a substantially different analysis, or a smaller learning-rate cap that would likely worsen the final bound, seems necessary.","section":"5, Theorem 9 and Appendix E.4"}],"minor_comments":[{"comment":"The definition of C_i is inconsistent: Definition 3 sets C_i = 2 hat C_i + 2 tilde C_i, while Appendix D.1 defines C_x = hat C_x + 2 tilde C_x. Please reconcile this notation.","section":"Definition 3 vs. Appendix D.1"},{"comment":"The proof uses the identity bar phi(v) = bar phi(v) - bar phi(x(1)), which requires bar phi(x(1)) = 0. This holds in Algorithm 1 because the first iterate is the uniform distribution, but it is not stated as an assumption in Lemma 16; please add the needed hypothesis or adjust the argument.","section":"Lemma 16 proof"},{"comment":"Equation (23) writes the local norm with respect to F^{(t+1)}_a as (1/sqrt(eta^{(t+1)}_a)) times the norm with respect to phi, but the factor 1/sqrt(eta^{(t+1)}_a) appears outside the sum in an ambiguous way. It should be inside the sum over a.","section":"Lemma 22 statement"},{"comment":"The lower-bound proofs in parts (i) and (ii) assume that hat C_x, tilde C_x, etc. are even integers, but this integrality is not stated in the theorem; please add the standard rounding argument or state the assumption explicitly.","section":"Theorem 10 proof"}],"recommendation":"major_revision","confidential_remarks":"The zero-sum external regret results and the lower bounds are valuable and appear sound, but the general-sum swap regret contribution is not ready in its current form because the central stability lemma has a serious scaling gap. I would advise the editor to seek an independent verification of Lemma 22 before further consideration; if the lemma cannot be repaired, the paper's contribution reduces substantially, and the claims in Theorem 9 would need to be weakened or removed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the corruption model is a good idea, the zero-sum external regret part is in good shape, and the lower bounds are a nice addition. But the multi-player swap regret theorem—the headline contribution—rests on Lemma 22, and I don't think the proof of that lemma closes.\n\nWhat's new: the paper formalizes a corrupted regime where players deviate from OFTRL by a cumulative amount, and gives regret bounds that interpolate between the honest log-T regime and worst-case sqrt(T). For two-player zero-sum, Theorem 6 gives the first corrupted-regime external regret bound, and the proof via the entropy RVU bound plus a path-length argument looks solid. The matching lower bounds in Section 6 are also worthwhile, and the paper is honest that the characterization is partial.\n\nThe soft spot is Section 5. Theorem 9's swap regret bound depends on the stability condition sum_a ||y_a^{t+1}-y_a^t||_{y_a^t,φ} ≤ 1/2, established in Lemma 22. The proof tries to show that on a product-space sphere of radius 1/(2√m), the function G increases. The positive quadratic gain is 15/(128m), but the negative linear term from the adaptive learning-rate difference is of order √η/√logT ~ m^{-1/4} after summing over the m experts (using Lemma 21 and ||∇φ||_* ≤ √m). That negative term dominates the O(1/m) positive term for large m, so the claimed inequality G(z) ≥ G(y^t) is not established. The final step in the proof, which bounds the sum of negative terms by 15/128, appears to be where it goes wrong. So the honest-regime O(nm^{5/2} logT) rate and the corrupted-regime swap bounds are unsupported as written.\n\nThere is also a small notation inconsistency: Ci=2ˆCi+2~Ci in Definition 3 but Cx=ˆCx+2~Cx in Appendix D.1. That's minor and doesn't affect the core argument.\n\nThe reader's stress-test note is right on the main point. The paper is worth refereeing—if Lemma 22 can be fixed, or if the stability can be proved another way, the contribution is real. But I would not cite the swap regret result in its current form.\n\nRecommendation: send to peer review, but flag Lemma 22 for a thorough check; expect major revision.","headline":"A well-motivated corruption model with a clean external-regret result, but the swap-regret theorem rests on a stability lemma whose proof doesn't close.","tokens_in":42023,"tokens_out":11663,"would_cite":false,"duration_ms":110179,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A26","91A20","91A10","91A05","68Q32"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper shows that optimistic learning dynamics retain near-logarithmic regret in games where players deviate from the prescribed algorithm, with regret degrading only as the square root of opponents' deviations plus a linear penalty…","keywords":["regret minimization","corrupted learning","optimistic follow-the-regularized-leader","swap regret","Nash equilibrium","correlated equilibrium","adaptive learning rate","Markov chain stability"],"falsifier":"Run the proposed dynamics in a small two-player game (for example m=3, n=2, T=$10^{4}$) while injecting strategy deviations for one player that are large in total but concentrated in bursts, and compute the left-hand side of Eq. (23) over time; if it ever exceeds 1/2 under the stated learning rates, or if the other player's empirical regret exceeds the claimed bound, the proof's key stability lemma is false.","tokens_in":40968,"feed_emoji":"🎲","tokens_out":5946,"duration_ms":66022,"temperature":0.7,"pith_summary":"The paper asks whether the fast equilibrium convergence of optimistic learning in games survives when players do not fully follow the prescribed algorithm. It answers yes in a newly defined corrupted regime: OFTRL with adaptive learning rates achieves regret bounds that degrade gracefully with the cumulative strategy deviations and utility corruptions of all players. In two-player zero-sum games, the external regret is bounded by roughly the minimum of a corruption-dependent logarithmic term and a path-length term, plus the player's own deviation; in multi-player general-sum games, swap regret is similarly adaptive. The dynamics do not need to know the corruption levels, and they match the best honest-regime rates when all corruptions are zero. The paper also gives matching lower bounds showing that the square-root dependence on opponents' deviations and the linear dependence on one's own deviation are in general unavoidable.","feed_headline":"Corrupted players still learn equilibria fast","feed_subtitle":"Regret degrades smoothly with deviations, preserving log rates when play is clean","key_machinery":"The load-bearing object is OFTRL with expert-wise adaptive learning rates, using the negative Shannon entropy regularizer for the two-player case and the log-barrier regularizer for the general-sum swap-regret reduction. The crucial new step is a stability lemma, stated as Eq. (23), which bounds the sum over all experts of the local norms of successive log-barrier iterates by 1/2; this is achieved by capping each learning rate at 1/(256 n $\\sqrt$(m)) and requiring T >= 3. That stability condition lets the proof invoke an RVU bound for self-concordant barriers and the Markov-chain tree lemma to control the stationary distributions that define the suggested strategies, thereby avoiding the much worse O($nm^{8}$ log T) honest-regime bound that a naive adaptive analysis would give.","core_discovery":"The central claim is that corrupted learning can be made robust without sacrificing the fast rates of honest optimistic play. The authors prove that their adaptive OFTRL dynamics give external regret for the x-player in two-player zero-sum games of order min{$\\sqrt$((log(m_x m_y)+C_x+C_y) log m_x), $\\sqrt$((P_T^inf(~g)+log m_x) log m_x)} + C_x, and similarly for the y-player, where C_i aggregates strategy and utility corruption. For multi-player general-sum games, each player's swap regret is bounded by $nm^{{5/2}}$ log T plus a minimum of an adaptive corruption-dependent term and a sqrt{T log T}-type worst-case term, again plus a linear penalty for that player's own deviation. These are the first external and swap regret bounds for the corrupted regime, and the same dynamics match the best known honest-regime bounds when C_i=0. The argument also extends to corruption in observed expected utilities, and the lower bounds show that the main dependencies on the corruption levels cannot be improved in the worst case.","pith_inferences":["The utility-corruption setting is structurally similar to time-varying games, so the same adaptive-rates machinery may transfer to payoff or utility functions that drift, a connection the paper leaves mostly implicit.","The new RVU bound for log-barrier OFTRL with adaptive learning rates is likely to be useful outside games, for example in online convex optimization with predictable loss sequences, provided the stability condition can be verified in those settings.","A practical testable consequence of the stability lemma is that the left-hand side of Eq. (23) can be monitored online; if it ever approaches 1/2 under a given corruption pattern, that is a warning that the fast-rate proof is near its limit.","The lower bounds suggest a corruption budget interpretation: total corruption S sets a fundamental floor on equilibrium approximation error, roughly sqrt(S)/T, which could guide how much deviation a system should tolerate before switching to a purely adversarial algorithm."],"forward_implications":["If the central claim is correct, then in two-player zero-sum corrupted games the time-averaged joint play is an ~O((C_x+C_y)/T)-approximate Nash equilibrium.","In multi-player general-sum games, the time-averaged joint play is an ~O((log T + sqrt(\\hat S log T) + max_k \\hat C_k)/T)-approximate correlated equilibrium, where \\hat S is the total strategy deviation.","The bounds create an incentive to follow the prescribed dynamics: one's own deviation enters linearly into regret, while opponents' deviations enter only through a square-root term.","The algorithm is agnostic to the corruption levels, so the same dynamics work without knowing \\hat C_i or \\tilde C_i in advance.","The matching lower bounds imply that no learning dynamics can remove the square-root dependence on opponents' deviations or the linear dependence on one's own deviation in the worst case."],"supporting_citations":[{"why":"Supplies the OFTRL framework, the optimistic prediction idea, and the honest-regime O(log) regret baseline that the new bounds match and extend.","marker":"Syrgkanis et al. (2015)"},{"why":"Provides the constant-learning-rate swap-regret algorithm, the O(nm^{5/2} log T) honest-regime bound, and the Markov-chain stability analysis that the adaptive-rate proof extends.","marker":"Anagnostides et al. (2022b)"},{"why":"Gives the reduction from swap regret to external regret over experts, restated as Lemma 8 and used to define the transition matrix and stationary strategy.","marker":"Blum and Mansour (2007)"},{"why":"Contributes adaptive-learning-rate techniques used to obtain corruption-dependent bounds without fixed prior knowledge of the deviation levels.","marker":"Wei and Luo (2018)"},{"why":"Provides the path-length-dependent regret bound and adaptive learning-rate approach that the new external-regret bound improves upon.","marker":"Rakhlin and Sridharan (2013b)"},{"why":"Supplies the finite-time minimax lower bound used to prove the matching lower bound for utility-corrupted feedback.","marker":"Orabona and Pál (2015)"},{"why":"Establishes the connection between swap regret and correlated equilibrium, which translates the swap-regret bound into an equilibrium approximation rate.","marker":"Foster and Vohra (1997)"},{"why":"Establishes the connection between no-external-regret learning and approximate Nash equilibrium in two-player zero-sum games.","marker":"Freund and Schapire (1999)"}],"fun_headline_variants":["Corrupted learning still hits fast equilibria","Adaptive rates tame corruption in game learning","First regret bounds for corrupted learning in games","Corruption-robust dynamics match honest rates"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole argument rests on the claimed stability of the Markov chain: the algorithm's consecutive suggested strategies must stay close enough in an adapted metric, and a corruption pattern that violates this would break the regret bound.","fun_headline_variants_meta":{"raw":{"variants":["Corrupted learning still hits fast equilibria","Adaptive rates tame corruption in game learning","First regret bounds for corrupted learning in games","Corruption-robust dynamics match honest rates"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000493,"raw_usage":{"total_tokens":2515,"prompt_tokens":1130,"completion_tokens":1385,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":746,"completion_tokens_details":{"reasoning_tokens":1329}},"tokens_in":746,"tokens_out":1385,"duration_ms":11879,"temperature":1.0,"reasoning_tokens":1329,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T19:05:46.040462+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the proposed dynamics in a small two-player game (for example m=3, n=2, T=$10^{4}$) while injecting strategy deviations for one player that are large in total but concentrated in bursts, and compute the left-hand side of Eq. (23) over time; if it ever exceeds 1/2 under the stated learning rates, or if the other player's empirical regret exceeds the claimed bound, the proof's key stability lemma is false.","supporting_citations":[{"cited_title":"Fast convergence of regularized learning in games","cited_arxiv_id":null,"evidence_quote":"Supplies the OFTRL framework, the optimistic prediction idea, and the honest-regime O(log) regret baseline that the new bounds match and extend."},{"cited_title":"More adaptive algorithms for adversarial bandits","cited_arxiv_id":null,"evidence_quote":"Contributes adaptive-learning-rate techniques used to obtain corruption-dependent bounds without fixed prior knowledge of the deviation levels."},{"cited_title":"Schapire","cited_arxiv_id":null,"evidence_quote":"Establishes the connection between no-external-regret learning and approximate Nash equilibrium in two-player zero-sum games."}],"review_version":1}