{"id":"3d5b2706-6eba-4010-8b59-fb9223dae771","arxiv_id":"2505.05609","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A repeated retraining algorithm with robust gradient estimation converges to an approximately stable policy in performative RL under Huber contamination, with approximation error scaling as the square root of the corruption level.","lead":"This paper studies reinforcement learning in environments that change in response to the agent's own policy, when part of the training data is corrupted by an adversary. It proposes robust optimization and robust gradient estimation methods and proves convergence to an approximately stable policy with error growing like the square root of the corruption fraction.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The +c occupancy shift in Algorithm 2 breaks the Bellman-flow fixed point; Theorem 5's contraction assumes PO(d_S)=d_S, which fails for c>0, and no bound links the actual deployed occupancy to the auxiliary \\bar d.","rationale":"I read the central claim as Theorem 5: under Assumptions 1-3, Algorithm 2's outputs converge to a 4\\bar C(\\delta/N)-neighborhood of a performatively stable policy. For that claim to hold, the repeated-retraining operator implemented by Algorithm 2 must be a contraction on the relevant state, and its fixed point must be near d_S. The proof in the appendix attempts this via an operator PO on \\bar d_n, but Algorithm 2's deployed policy is \\pi^{\\downarrow}(\\bar d_n+c). Because \\tilde d_n = \\bar d_n+c is not a valid occupancy measure, the actual occupancy measure d^{\\pi^{\\downarrow}\\tilde d_n} can differ from \\tilde d_n by an amount that is never bounded; the Bellman-flow violation is exactly (1-\\gamma)cA per state. Consequently, the asserted identity PO(d_S)=d_S is false for c>0, and the contraction argument does not apply to the sequence the algorithm actually generates. The c\\sqrt{SA} term in \\bar C only bounds the Euclidean distance between \\bar d and \\tilde d; it does not account for the distribution shift induced by deploying \\pi^{\\downarrow}\\tilde d. The reader's concern about Theorem 3 (trimming breaks i.i.d. and introduces unaccounted bias) is a valid proof gap, and I agree it should be fixed, but it is an estimator-level issue; even with a correct robust gradient bound, the Theorem 5 update remains unverified because the state variable in the contraction is not the actually deployed occupancy measure. I therefore keep the reader's conditional verdict, but the conditions must include either a projection/feasibilization step in Algorithm 2 or a bound on \\|d^{\\pi^{\\downarrow}(\\bar d+c)} - (\\bar d+c)\\| and a corrected fixed-point analysis. Without that, the central convergence claim is not established.","tokens_in":39830,"tokens_out":25070,"duration_ms":290549,"concrete_test":"Take a single-state, two-action performative MDP with reward r^\\pi(s,a)=r_0 - c_p d^\\pi(s,a), \\gamma=0.99, and any c>0. Compute d_S from the fixed point d_S\\in\\argmax L(\\cdot,\\cdot,M(\\pi^{\\downarrow}d_S)). Then compute PO_c(d_S)=\\argmax_{d\\in D} L(d,h,M(\\pi^{\\downarrow}(d_S+c))). If \\|PO_c(d_S)-d_S\\| is not bounded by the advertised 4\\bar C(\\delta/N), Theorem 5 is quantitatively false; if it is O(c\\sqrt{SA}), the proof still needs a derivation of this bias term and a contraction argument on the actual deployed occupancy measures rather than on \\bar d_n.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Algorithm 2 line 5 adds a positive constant c to every entry of the OFTRL output \\bar d_{n+1}. If \\bar d_{n+1} were a valid occupancy measure of M_n, the shifted vector \\tilde d_{n+1} violates the Bellman flow constraint by exactly (1-\\gamma)cA per state. The deployed policy is \\pi_{n+1}=\\pi^{\\downarrow}\\tilde d_{n+1}, and as the Preliminaries state, d^{\\pi^{\\downarrow}d} and d may differ; hence the actual occupancy measure d_{n+1} of the deployed policy is not \\tilde d_{n+1}. The proof of Theorem 5 nevertheless treats \\bar d_n as the state, asserts PO(d_S)=d_S and a contraction for PO. With c>0, PO(d_S) is the optimum in M(\\pi^{\\downarrow}(d_S+c)), not in M(\\pi_S), so d_S is not a fixed point of the implemented operator. No bound is supplied for \\|d^{\\pi^{\\downarrow}(\\bar d_n+c)} - (\\bar d_n+c)\\|, nor for the shift of the fixed point caused by c; the c\\sqrt{SA} term in \\bar C only accounts for the Euclidean shift between \\bar d and \\tilde d, not for the Bellman-flow violation or the resulting distribution shift. This gap is independent of, and more immediate than, the i.i.d.-after-trimming issue in Theorem 3.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies performative reinforcement learning in the finite-sample regime under Huber's epsilon-contamination model. It proposes a repeated-retraining algorithm (Algorithm 2) that combines a robust variant of Optimistic Follow the Regularized Leader (OFTRL) with a coordinate-wise trimmed mean estimator for the gradients of a regularized MDP Lagrangian. The main theoretical claim is last-iterate convergence to an approximately performatively stable policy, with approximation error linear in sqrt(epsilon). The paper also provides an analysis of robust OFTRL for convex-concave optimization, an information-theoretic lower bound on the terminal error, and a gridworld simulation study comparing the proposed robust estimator with naive gradient averaging.","tokens_in":40090,"tokens_out":6850,"duration_ms":76228,"significance":"If the central convergence claim were established, the paper would be a meaningful step toward making performative RL robust to data poisoning: the setting is well motivated, the idea of combining repeated retraining with robust mean estimation is natural, and the explicit lower bound for convex-concave optimization under bounded gradient noise is of independent interest. The paper also makes a useful practical contribution by demonstrating, through experiments, that naive gradient averaging is significantly more sensitive to corruption than the proposed trimming-based estimator. However, the main theoretical result is not established as written: the deployed occupancy measure is not the object to which the contraction argument is applied, and the proof of the robust gradient estimator applies an i.i.d. concentration lemma to a dataset that is no longer i.i.d. after trimming. These are load-bearing gaps in the central claim, so the paper needs substantial revision before it can be accepted.","major_comments":[{"comment":"The contraction argument in the proof of Theorem 5 is applied to the wrong state. Algorithm 2 sets \\tilde d_{n+1} = \\bar d_{n+1} + c and deploys \\pi_{n+1} = \\pi^{\\downarrow}\\tilde d_{n+1}. As the Preliminaries explicitly note, d^{\\pi^{\\downarrow} d} and d may differ, and the \\bar d produced by robust OFTRL is not guaranteed to satisfy the Bellman flow constraints. The proof nevertheless defines POC(\\bar d_n) as the quantity that includes the addition of c, then states the update rule as \\bar d_{n+1} = POC(\\bar d_n), and applies the fixed-point property PO(d_S) = d_S and the contraction of PO. For c > 0, PO(d_S) is the optimum in M(\\pi^{\\downarrow}(d_S + c)), not in M(\\pi_S), so d_S is not a fixed point of the implemented operator. No bound is supplied for \\|d^{\\pi^{\\downarrow}(\\bar d_n + c)} - (\\bar d_n + c)\\|, and the c\\sqrt{SA} term in \\bar C accounts only for the Euclidean distance between \\bar d and \\tilde d, not for the Bellman-flow violation or the resulting distribution shift. Thus Theorem 5 is not established as written.","section":"Algorithm 2, line 5; Appendix, Proof of Theorem 5"},{"comment":"The proof applies Lemma 6 to the dataset after coordinate-wise trimming in Algorithm 3, but Lemma 6 requires the good samples to remain i.i.d. draws from the original distribution with expectation \\bar x. Keeping the samples closest to the median makes the retained clean samples dependent and changes their conditional mean; this bias is not bounded anywhere in the proof. Consequently the stated high-probability bound for \\hat g_d is not justified. Because Lemma 1, Theorem 4, and Theorem 5 all rely on the gradient error bound E_2 from Theorem 3, the central convergence claim inherits this gap. A correct proof would need to control the bias of the coordinate-wise trimmed mean or replace the estimator with one whose analysis does not require the retained samples to be i.i.d.","section":"Theorem 3; Appendix, Proof of Theorem 3"},{"comment":"The step \"after some iterations (suppose this is less than N, without loss of generality, since we did not assume anything for N)\" does not prove the existence of a finite N. The theorem asserts that there exist \\lambda and N such that the stated guarantee holds, and the proof should provide a concrete threshold for N in terms of the contraction constant, the initial distance, and \\bar C(\\delta/N). Citing the proof of Theorem 1 from prior work is not sufficient here, because the operator and the convergence criterion differ.","section":"Appendix, Proof of Theorem 5"}],"minor_comments":[{"comment":"Assumption 1 states that every D_n can be split into 2T batches with corruption level at most \"epsilon < 0.\"; the intended bound is epsilon < 0.5, which is used throughout the proofs.","section":"Assumption 1"},{"comment":"The caption says that panels (a) and (d) use naive gradient averaging and (b) and (c) use robust gradient estimation, but the panel labels show (a) and (c) as naive and (b) and (d) as robust; the caption should be corrected to match the labels.","section":"Figure 1 caption"},{"comment":"The proof states that the median at each coordinate is equal to one uncorrupted sample for epsilon < 0.5; this ignores the even-cardinality tie case and the exact rounding convention in Algorithm 3, though this is a patchable issue if the rest of the estimator analysis is repaired.","section":"Theorem 3 proof"},{"comment":"There are several typographical errors, including \"perfomrative,\" \"convergce,\" \"Robust OFTR,\" and inconsistent spellings of \"convex-concave\"; these should be cleaned up in revision.","section":"Throughout"},{"comment":"The lower bound statement would be clearer if it specified the norm used for the distance to the saddle point and if the condition on Z_X, Z_Y relative to D were stated before the theorem rather than inside the proof.","section":"Theorem 2 statement"}],"recommendation":"major_revision","confidential_remarks":"Both major concerns identified by the reader land on reading the manuscript. The c-shift issue in Algorithm 2/Theorem 5 is particularly severe because the proof's state variable is not the actual occupancy measure of the deployed policy, and no analysis connects the two. The trimming issue in Theorem 3 is also central, since it invalidates the gradient error bound on which the later theorems depend. The paper's core idea is promising and the experimental illustration is useful, but the theoretical results need to be reworked rather than merely patched. If the authors can supply a corrected analysis of the implemented operator and of the robust mean estimator, the paper could be suitable for acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nShort version: this paper is worth reading but not yet worth trusting. The core idea—combining robust OFTRL with a coordinate-wise trimmed mean to make performative RL work under Huber contamination—is a legitimate new contribution, and the high-level claim (last-iterate convergence to within O(sqrt(epsilon)) of a stable policy) is the right kind of target. But two gaps in the proofs need to be closed before the main theorem is established.\n\nWhat's genuinely good: the robust OFTRL analysis (Theorem 1) and the lower bound (Theorem 2) are clean and self-contained. They show the dependence on gradient noise is optimal, and that part is solid. The problem-specific estimator for d-gradients is also a reasonable design, and providing a lower bound rather than just an upper bound is to their credit.\n\nThe soft spots are load-bearing. First, the proof of Theorem 3 applies Lemma 6 to the trimmed dataset, but the retained clean samples are no longer i.i.d. with the original mean. Trimming by proximity to the median conditions the sample, and the conditional mean can shift; that bias is never bounded. This is not a minor bookkeeping issue—Lemma 1, Theorem 4, and Theorem 5 all inherit the gradient error bound from Theorem 3.\n\nSecond, and more immediately, the +c shift in Algorithm 2 breaks the fixed-point argument in Theorem 5. The proof treats the OFTRL output \\bar{d} as the state and claims PO(d_S)=d_S, but with c>0 the actual deployed occupancy is \\tilde{d}=\\bar{d}+c, and the induced MDP is not the one in which d_S is stable. The proof does not bound the difference between the actual occupancy of \\pi^{\\downarrow}(\\bar{d}+c) and \\bar{d}+c; the c\\sqrt{SA} term only accounts for the Euclidean shift, not the Bellman-flow violation or the resulting distribution shift. So the contraction step in Theorem 5 is not established as written.\n\nThe experiments are illustrative and the lack of error bars/code is a minor issue. There's also a typo in Assumption 1 (epsilon < 0 instead of epsilon < 0.5).\n\nMy verdict: the paper deserves a serious referee—the problem is timely and the robust OFTRL part is worth publishing independently. But the performative RL convergence claim should not be accepted until the trimming bias and the +c fixed-point issue are resolved. If you send it to review, the referee will need to ask for a significant revision of the proofs of Theorem 3 and Theorem 5.","headline":"Solid robust-OFTRL analysis under corruption, but the performative RL convergence proof has two load-bearing gaps: the trimmed-mean bias in Theorem 3 and the +c fixed-point break in Algorithm 2.","tokens_in":40657,"tokens_out":4215,"would_cite":false,"duration_ms":41456,"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":"The paper claims that a repeated-retraining algorithm for performative reinforcement learning retains its convergence guarantee when an epsilon fraction of data is adversarially corrupted, ending near a performatively stable policy with…","keywords":["performative reinforcement learning","corruption robustness","Huber contamination","robust mean estimation","convex-concave optimization","repeated retraining","OFTRL","occupancy measures"],"falsifier":"A targeted test: generate a clean set of gradient samples from the MDP Lagrangian, apply Algorithm 3's trimming step with an epsilon-fraction of large adversarial outliers, and compare the mean of the retained clean samples to the true gradient. If the bias is not O(epsilon) for fixed finite sample size, Theorem 3's proof fails at its load-bearing step; at the system level, a simulation exhibiting last-iterate cycling with final error above O(sqrt(epsilon)) under Assumptions 1-3 would falsify Theorem 5.","tokens_in":39590,"feed_emoji":"🛡️","tokens_out":7293,"duration_ms":74554,"temperature":0.7,"pith_summary":"The paper asks whether repeated retraining in performative reinforcement learning—where the reward and transition functions shift in response to the deployed policy—can still converge when an adversary corrupts a fraction epsilon of the training data. It claims yes: under Huber's epsilon-contamination model, a retraining scheme built from robust convex-concave optimization converges in its last iterate to a policy close to a performatively stable one, with approximation error growing only as the square root of epsilon. The difficulty is that naive gradient averaging in the saddle-point formulation fails badly under corruption, while a coordinate-wise trimmed-mean estimator combined with a robust version of Optimistic Follow-the-Regularized-Leader keeps the estimation error bounded. A sympathetic reader should care because recommendation systems, chatbots, and other policy-dependent systems are exposed to data poisoning, and this provides finite-sample convergence guarantees for performative RL in that regime.","feed_headline":"Robust retraining reaches near-stable policy despite poisoned data","feed_subtitle":"Repeated retraining with trimmed gradients provably lands within O(sqrt(epsilon)) of a stable policy.","key_machinery":"The load-bearing machinery is a robust version of Optimistic Follow-the-Regularized-Leader (OFTRL), an online-learning algorithm that updates by alternately minimizing regularized objectives with optimistic gradient predictions, paired with a coordinate-wise trimmed-mean estimator. For each coordinate of the gradient, the estimator keeps the (1-epsilon)m samples closest to the coordinate-wise median and averages them, cutting arbitrarily large adversarial corruption down to a bounded bias that scales linearly with epsilon. This estimator feeds gradients of the Lagrangian of the regularized reinforcement learning problem over occupancy measures, turning each retraining round into a convex-concave saddle-point optimization; the resulting gradient error bounds are what Lemma 1, Theorem 4, and Theorem 5 use to convert per-round accuracy into last-iterate convergence to a near-stable policy.","core_discovery":"On its own terms, the central discovery is Theorem 5: robust repeated retraining (Algorithm 2) has last-iterate convergence to a nearly performatively stable policy. Concretely, under Assumption 1 (bounded corruption in each batch), Assumption 2 (epsilon-sensitivity of rewards and transitions), and Assumption 3 (boundedness of an instance-specific constant), there exist a regularizer lambda and a number of rounds N such that with probability at least 1-delta the final occupancy measure lies within a ball of radius O(sqrt(epsilon)) around a performatively stable occupancy measure d_S. The sqrt(epsilon) dependence enters because the gradient-estimation error in Theorem 3 is linear in epsilon, and the distance-to-stability bound in Theorem 4 takes a square root of that error. The same analysis shows that the robust OFTRL optimizer alone attains O(1/T) duality-gap convergence and information-theoretically optimal terminal error under bounded gradient noise, matching the lower bound of Theorem 2.","pith_inferences":["A natural next step is to replace coordinate-wise trimming with a joint or covariance-aware robust estimator; that could reduce the dimension factors in the gradient error bound and possibly tighten the final O(sqrt(epsilon)) radius without changing the contraction argument.","The proof's reliance on retained clean samples staying i.i.d. after trimming suggests a testable variant: design a filtering rule that provably preserves the clean conditional distribution, or explicitly bound the trimming bias, and the gradient error analysis would rest on a fully stated premise.","The same robust-OFTRL machinery could plausibly be imported to other decision-dependent optimization problems with corrupted gradients, such as performative prediction with poisoned labels, since only the gradient estimator and the contraction step are specific to performative RL.","The paper leaves open whether O(sqrt(epsilon)) is the best possible dependence; constructing a matching lower bound for the stable-policy approximation error would settle the tightness of the guarantee."],"forward_implications":["If Theorem 5 is right, repeated retraining can be used in performative RL settings where an epsilon-fraction of feedback is poisoned, and the price is only an O(sqrt(epsilon)) radius around the stable policy instead of losing convergence entirely.","The robust OFTRL component gives O(1/T) convergence of the duality gap to an approximate saddle point under bounded gradient corruption, so it is usable outside performative RL in any smooth convex-concave optimization with corrupted first-order oracle feedback.","The coordinate-wise trimmed-mean estimator converts unbounded adversarial corruption of rewards and next states into bounded gradient noise, assuming the coverage condition on occupancy measures is maintained.","With sufficiently large regularization and number of rounds, the return of the deployed approximately stable policy in its own environment is worse than that of a performatively stable policy by only an instance-dependent constant, as shown in the appendix."],"supporting_citations":[{"why":"It introduces the performative RL framework, the repeated-retraining formulation, and the contraction argument used to prove Theorem 5.","marker":"Mandal, Triantafyllou, and Radanovic 2023"},{"why":"It provides the offline-RL minimax reformulation that the finite-sample Lagrangian inherits.","marker":"Zhan et al. 2022"},{"why":"It supplies the robust-gradient-estimation and batch-splitting methodology that the robust OFTRL analysis relies on.","marker":"Prasad et al. 2020"},{"why":"It gives the Huber-contamination robust mean estimation guarantees used to justify filtering unbounded corruption.","marker":"Diakonikolas, Kane, and Pensia 2020"},{"why":"It is the OFTRL regret analysis extended by Theorem 1 to noisy gradients.","marker":"Orabona 2019"},{"why":"It provides the Hoffman bound used to relate approximate occupancy measures to Bellman-flow constraints in Theorem 4.","marker":"Garber 2019"}],"fun_headline_variants":["Robust retraining withstands corruption in performative RL","Near-stable policy despite poisoned data: O(√ε) error","Performative RL robust to corrupted gradients via trimmed means","Last-iterate convergence to stable policy under adversarial corruption","Robust mean estimator enables resilient performative RL"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that after Algorithm 3 trims each coordinate by keeping samples closest to the coordinate-wise median, the remaining clean gradient samples are still i.i.d. draws from the original clean distribution, so the standard concentration bound applies; trimming actually makes the retained clean samples correlated and shifts their conditional mean, and the proof does not bound that shift.","fun_headline_variants_meta":{"raw":{"variants":["Robust retraining withstands corruption in performative RL","Near-stable policy despite poisoned data: O(√ε) error","Performative RL robust to corrupted gradients via trimmed means","Last-iterate convergence to stable policy under adversarial corruption","Robust mean estimator enables resilient performative RL"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000575,"raw_usage":{"total_tokens":2706,"prompt_tokens":932,"completion_tokens":1774,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":548,"completion_tokens_details":{"reasoning_tokens":1704}},"tokens_in":548,"tokens_out":1774,"duration_ms":12336,"temperature":1.0,"reasoning_tokens":1704,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T23:01:20.372748+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A targeted test: generate a clean set of gradient samples from the MDP Lagrangian, apply Algorithm 3's trimming step with an epsilon-fraction of large adversarial outliers, and compare the mean of the retained clean samples to the true gradient. If the bias is not O(epsilon) for fixed finite sample size, Theorem 3's proof fails at its load-bearing step; at the system level, a simulation exhibiting last-iterate cycling with final error above O(sqrt(epsilon)) under Assumptions 1-3 would falsify Theorem 5.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It introduces the performative RL framework, the repeated-retraining formulation, and the contraction argument used to prove Theorem 5."},{"cited_title":"S.; Balakrishnan, S.; and Ravikumar, P","cited_arxiv_id":null,"evidence_quote":"It supplies the robust-gradient-estimation and batch-splitting methodology that the robust OFTRL analysis relies on."},{"cited_title":"M.; and Pensia, A","cited_arxiv_id":null,"evidence_quote":"It gives the Huber-contamination robust mean estimation guarantees used to justify filtering unbounded corruption."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It provides the Hoffman bound used to relate approximate occupancy measures to Bellman-flow constraints in Theorem 4."}],"review_version":1}