{"id":"1abbb689-a7ad-4603-adc4-a0cc5cb30f78","arxiv_id":"1909.02109","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The SBE algorithm achieves O(d^(5/2) C log T / Delta + d^6 log(d log T/δ) log T / Delta^2) regret in stochastic linear bandits with adversarial corruption, with regret growing linearly in corruption C.","lead":"This paper designs an algorithm for stochastic linear bandits where an adversary can corrupt rewards, and proves a regret bound that grows only linearly in the total corruption. It is the first such extension from finite-armed bandits to linear optimization, using coordinate-wise exploration based on a Lowner-John ellipsoid.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.1 requires c_t chosen before x_t, but the protocol's 'algorithm chooses first x_t' admits an action-adaptive adversary; under that reading the martingale is not centered and the linear-in-C regret bound collapses.","rationale":"The reader identified the adversary-timing dependence of Lemma 4.1 as the weakest assumption, and my reading agrees. This is the most load-bearing concern because every subsequent lemma and the final regret bound inherit the martingale argument: if c_t may depend on the current exploration indicator, the corruption contribution to the estimate is no longer controlled by C/N_m but can be concentrated on the small set of explored rounds, breaking the linear-in-C guarantee. The attack described above shows the failure is not merely a missing constant but a qualitative change in regret. I do not think this warrants a stronger verdict than CONDITIONAL, because the standard corruption-bandit convention typically places c_t before the learner's action and the paper's definition of C as sum of max_x |c_t(x)| suggests that convention; the authors can likely repair the paper by formally specifying the timing and rewording Section 2. Secondary issues noted by the reader, such as the dimensional inconsistency in the variance bound and the ζ = d^5 vs d^6 discrepancy between Section 4 and Sections 3/6, are also real but less fundamental; they should be fixed in revision. No machine-checked proofs or reproducible code are provided, so the protocol ambiguity is not resolved by external evidence.","tokens_in":10500,"tokens_out":26664,"duration_ms":290987,"concrete_test":"Run SBE on a low-dimensional cube (e.g., d=3 or 4) with known Δ, large T, and two adversary variants. In variant A, the adversary must choose c_t before x_t; in variant B, the adversary observes x_t before choosing c_t and, during the penultimate epoch, sets c_t(s_2)=1 whenever s_2 is explored and c_t=0 otherwise, so total corruption C equals the number of s_2 explorations. Compare realized regret in variant B with the Theorem 5.1 upper bound for that C. If variant B regret is Ω(TΔ) while the promised bound is o(TΔ), the central claim depends on the missing timing assumption. Analytically, recompute the corruption term under c_t depending on ξ_t^j: the Freedman inequality would require a nonzero conditional mean, so Lemma 4.1 as printed is invalid without an explicit before-action convention.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is in Lemma 4.1, where X_t = (ξ_t^j − n_e/N_m)c_t(s_j) is treated as a martingale difference because 'ξ_t^j is independent of the corruption level c_tj conditional on F_{t−1}'. That independence is exactly the assertion that c_t is fixed before the current exploration indicator ξ_t^j is realized. Section 2, however, describes the protocol only as 'The algorithm chooses first x_t, then observes the corrupted reward r_t(x_t)+c_t(x_t)' and calls the adversary adaptive; it does not state that c_t cannot depend on x_t. If the adversary chooses c_t after seeing x_t, it can set c_t(s_2)=1 on precisely the rounds when s_2 is explored. Then E[(ξ_t^j − n_e/N_m)c_t(s_j) | F_{t−1}] is generally nonzero, so {Y_t} is not a martingale and the Freedman step in Lemma 4.1 is invalid. The failure propagates to Lemmas 4.2–4.4 and hence to Theorem 5.1. Concretely, under the action-adaptive reading the corruption incurred while exploring s_2 is averaged over n_e ≈ ζ/(d Δ²) explored pulls rather than over N_m total rounds. An adversary that spends C ≈ ζ/(d Δ²) in one epoch by corrupting all explorations of a bad basis direction leaves a constant bias in the corresponding coordinate of θhat; the next exploitation epoch can have length Θ(T), producing Ω(TΔ) regret. For T large, this exceeds the O(d² C log T / Δ + d^5 log(d log T/δ) log T / Δ²) bound promised by Theorem 5.1. If the authors intend the standard Lykouris-et-al. convention, they must state explicitly that c_t is chosen before x_t and reword the protocol; otherwise the central claim is not supported by the given proof.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper extends the stochastic linear optimization model of Dani et al. to the setting where an adaptive adversary can corrupt observed rewards by an unknown total amount C. The proposed SBE algorithm separates exploration and exploitation: at each epoch it explores the orthogonal basis given by a Löwner–John ellipsoid and exploits the action estimated from the previous epoch, with epoch lengths growing exponentially. The main result, Theorem 5.1, claims a regret bound of O(d^2 C log T / Delta + d^5 log(4d log T/delta) log T / Delta^2) with probability at least 1 - delta, and Section 6 upgrades the constants when only a weak Löwner–John ellipsoid is available. The proof proceeds by bounding the per-coordinate estimation error (Lemma 4.1), translating it to a uniform reward-estimation error (Lemma 4.2), and then controlling the estimated gap from above and below (Lemmas 4.3 and 4.4) before summing the regret over epochs.","tokens_in":10812,"tokens_out":35534,"duration_ms":307697,"significance":"The result is significant if correct: it would give the first algorithm for stochastic linear optimization with adversarial corruption whose regret grows only linearly in the total corruption C and does not require the algorithm to know C. The proof architecture is a genuinely new analysis rather than a repackaging: the coordinate-wise exploration scheme is designed to make the corruption term amenable to martingale concentration, and the epoch-doubling construction damps the effect of past corruption. The paper's claims are explicit and falsifiable, and the derivation is not circular: it relies on standard external tools such as Hoeffding and Freedman-type inequalities. However, two load-bearing points in the current manuscript need to be repaired: the timing of the adversary's corruption choice relative to the current action must be stated precisely, and the exploration regret analysis in Theorem 5.1 uses the wrong estimated-gap index. Neither issue appears fatal if the intended conventions are made explicit, but both must be fixed before the result can be accepted.","major_comments":[{"comment":"The proof of Lemma 4.1 relies on the assertion that xi_t^j is independent of c_t(s_j) conditional on F_{t-1}. This is exactly a timing assumption: the adversary must choose c_t before the algorithm's random exploration decision at time t is realized, so that c_t may depend on past history but not on the current action x_t. The protocol statement in Section 2 only says \"The algorithm chooses first x_t, then observes the corrupted reward,\" which admits the opposite reading. If c_t may be chosen after seeing x_t, the adversary can set c_t(s_j)=1 precisely on exploration pulls of one basis direction; then the centered quantity (xi_t^j - n_e/N_m)c_t(s_j) is not a martingale difference, Lemma 4.1 fails, and the regret bound collapses. For example, an adversary that corrupts every exploration pull of a single basis vector at level 1 in each epoch incurs total corruption O(M zeta Delta^{-2}/d) while inducing a constant bias, leading to Omega(T Delta) regret, which contradicts Theorem 5.1 for large T. The authors should either state explicitly that c_t is chosen before x_t (the standard Lykouris et al. convention) or revise the model and proof.","section":"Section 2 and Lemma 4.1"},{"comment":"The proof of the exploration regret R_2 states that \"the expected number of time steps in which exploration is conducted is zeta / (Delta-hat^{(m)})^2.\" According to Algorithm 1, epoch m explores with probability gamma_{m-1} and has expected exploration count zeta (Delta-hat^{(m-1)})^{-2}, not zeta (Delta-hat^{(m)})^{-2}. The subsequent case analysis therefore bounds the wrong sum; as written it does not establish the claimed bound on the actual exploration regret. The argument appears repairable by re-indexing (k = m-1) and adjusting the thresholds by constant factors, but this must be carried out explicitly.","section":"Section 5, proof of Theorem 5.1"}],"minor_comments":[{"comment":"Algorithm 1 and Section 6 set zeta = 2^{14} d^6 log(...), while Lemma 4.1 and Theorem 5.1 use zeta = O(d^5 log(...)); the exact-ellipsoid version should specify d^5 and the weak-ellipsoid version d^6, with the derivation shown.","section":"Algorithm 1 and Lemma 4.1"},{"comment":"In the variance bound, V is introduced as E[X_t^2 | F_{t-1}] but then used as the sum over t of the conditional variances; the notation should be separated to avoid ambiguity.","section":"Lemma 4.1"},{"comment":"The filtration defined in Lemma 4.1 includes eta_{t+1} in F_t; this should be justified or corrected, since it makes F_t depend on a future noise variable.","section":"Lemma 4.1"},{"comment":"The statement that uniqueness of x* is without loss of generality by perturbing the action set with random noise is not formalized; either define the perturbation or state the uniqueness as an assumption.","section":"Section 2"},{"comment":"In the exploitation regret calculation, the chain after Inequality (8) drops the d^2 and zeta factors; the final corruption term should be O(d^2 C), not \"512C\" as displayed.","section":"Section 5, inequality (8)"},{"comment":"The bibliography spells \"Grötschel\" as \"Grtschel\" and \"Lovász\" as \"Lovsz\" in the first reference; these should be corrected.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is an early arXiv version and the main technical ideas are promising, but the current text is not yet publishable. The timing issue must be resolved by an explicit protocol statement; if the authors instead intend an adversary that can react to the current action, then Theorem 5.1 is false and the paper would need a substantially different argument. I recommend asking for a careful revision addressing the index error in the exploration proof and the parameter inconsistency, in addition to the protocol clarification."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this one. It's the first attempt I know of to get corruption-robust bounds for stochastic linear bandits, and the core idea is respectable: explore along the axes of a Löwner-John ellipsoid, estimate each coordinate independently, and run epochs of increasing length so old corruption is discounted. That is a meaningful combination of Gupta et al. and Dani et al., and the regret target—linear in the total corruption C, without knowing C—is the right one.\n\nThe proof has one load-bearing ambiguity. Lemma 4.1 treats X_t = (ξ_t^j − n_e/N_m)c_t(s_j) as a martingale difference, asserting ξ_t^j is independent of c_t(s_j) given the past. That requires the adversary to choose the corruption function before seeing the algorithm's action. Section 2 is not clear on this: it says the adversary chooses a corruption function and the algorithm chooses first x_t, then observes corrupted reward. Under the natural reading where the adversary corrupts after seeing the action, the independence fails. An adversary can then corrupt exactly the pulls of one basis direction; the martingale is not centered, and a single epoch of corruption of size Θ(1/Δ²) leaves a constant bias in the estimate, which the next exploitation epoch converts into Ω(TΔ) regret—larger than the stated bound. So this has to be fixed. The authors probably mean the Lykouris convention (corruption chosen before the current action), in which case Lemma 4.1 is fine, but they have to say so explicitly and reword the protocol.\n\nTwo smaller things. Equation (2) writes V as the variance of a single X_t and then sums over t in the same bound; Freedman's inequality needs the total conditional variance, so the notation should be cleaned up. And ζ is set to d^6 in Algorithm 1 but d^5 in Lemma 4.1, with both d^5 and d^6 appearing in the advertised bounds. That needs aligning.\n\nThe rest of the argument—Lemmas 4.2–4.4, the epoch-based regret decomposition—looks coherent to me, and there are no fitted constants or circular moves. The gap analysis and the exploration/exploitation trade-off check out.\n\nBottom line: this is a serious paper that deserves a real referee. I'd send it out, with the expectation of major revision. If the timing assumption is clarified and the small inconsistencies are fixed, I think it will be a solid contribution to the bandit theory literature. As it stands, I wouldn't cite the current version.","headline":"First corruption-robust bound for stochastic linear bandits, but Lemma 4.1's martingale step depends on an unstated adversary-timing assumption that the paper must clarify before the result is citable.","tokens_in":11478,"tokens_out":9593,"would_cite":false,"duration_ms":100599,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68W27"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper gives the first stochastic linear optimization algorithm whose regret grows only linearly in the adversary's total corruption C, without the algorithm knowing C.","keywords":["stochastic linear bandits","adversarial corruption","regret bound","Löwner-John ellipsoid","support basis exploration","epoch schedule","adaptive adversary","coordinate-wise estimation"],"falsifier":"Check whether the martingale property in Lemma 4.1 holds by computing $\\mathbb{E}[(\\xi_t^j - p)c_t(s_j)\\mid\\mathcal{F}_{t-1}]$ under the protocol's ordering. If the adversary may choose $c_t$ after seeing the exploration draw, set $c_t(s_j)=-1$ on the pulled basis vector and $0$ otherwise with $C=O(1)$; the conditional mean is nonzero, the estimate is biased by a constant each epoch, and regret grows linearly in $T$, contradicting the claimed $O(C\\log T/\\Delta)$ bound.","tokens_in":10214,"feed_emoji":"🎰","tokens_out":14945,"duration_ms":128877,"temperature":0.7,"pith_summary":"The paper extends the model of stochastic bandits with adversarial corruption from finitely many arms to stochastic linear optimization, where each action is a vector in a $d$-dimensional polytope and the hidden reward vector must be learned. It presents the Support Basis Exploration (SBE) algorithm and proves that, with probability at least $1-\\delta$, its regret is $O(d^2 C \\log T / \\Delta + d^5 \\log(d \\log T/\\delta) \\log T / \\Delta^2)$, where $C$ is the total corruption and $\\Delta$ is the reward gap between the best and second-best actions. The two properties that matter are that regret grows only linearly in $C$ and that the algorithm never needs to know $C$. Prior linear-bandit methods such as confidence-ball and OFUL-style algorithms suffer linear-in-$T$ regret even under small corruption, so this is the first smooth degradation in the linear setting.","feed_headline":"Regret grows only linearly as adversarial corruption rises","feed_subtitle":"The SBE algorithm needs no knowledge of the corruption total and matches no-corruption bounds up to a log T factor.","key_machinery":"The load-bearing piece is Support Basis Exploration with a Löwner-John ellipsoid: for the polytope $D$, choose an ellipsoid $E$ with $E \\subseteq D \\subseteq dE$ and take its principal axes $S = \\{s_1,\\dots,s_d\\}$ as the exploration set. Corollary 2.2 ensures every $x \\in D$ has coefficients $|\\hat{a}_j| \\le 2d$ in this basis, so each basis pull carries the maximum possible information in its direction, and the orthogonal basis makes coordinate-wise estimation unbiased and easy to concentrate. Epochs of length $n_m = \\zeta \\cdot 4^m$ discount old corruption by a factor of $1/8$ per epoch in the gap estimates, which is what converts a $C$-sized adversary into an additive $O(C)$ regret term. The estimated-gap upper and lower bounds (Lemmas 4.3 and 4.4) are the quantitative engine that turns per-epoch estimation error into the final bound.","core_discovery":"The central claim is that an adaptive adversary's bounded reward corruption can be absorbed into stochastic linear bandit regret at a cost linear in the total corruption $C$. The proof route is: run epochs whose lengths grow exponentially; in each epoch explore each principal axis of a Löwner-John ellipsoid just enough to control estimation error, and otherwise exploit the best action according to the previous epoch's estimate. Coordinate-wise estimation on the orthogonal basis makes the exploration indicators nearly independent of the noise and lets the corruption term be bounded by a Freedman-type martingale inequality. Lemmas 4.3 and 4.4 sandwich the estimated gap between upper and lower bounds that decay with past corruption, yielding the linear-in-$C$ regret bound; Section 6 replaces the exact ellipsoid with a polynomial-time weak ellipsoid at the cost of an extra factor $d^{1/2}$ and $d$ in the two terms.","pith_inferences":["The proof's martingale step (Lemma 4.1) silently assumes the adversary's corruption for round $t$ is fixed before the algorithm's exploration draw is revealed; if the protocol instead let the adversary condition on the current action, the concentration bound would fail. A timing-robust variant could use private randomness or delayed reward observation to close this gap.","The coordinate-wise basis estimator is not tied to the ellipsoid: any exploration set whose coefficients are bounded (for example, a barycentric spanner of the polytope) could replace the Löwner-John ellipsoid with only constant-factor changes, which suggests the regret bounds are portable to other action sets.","The exponential epoch schedule discounts past corruption by $1/8$ per epoch, so the same schedule could make other optimistic linear bandit algorithms corruption-robust if their estimators are replaced by epoch-local coordinate estimates; running SBE against a confidence-ball variant under the same adversary is a direct test."],"forward_implications":["This is the first algorithm for stochastic linear optimization with adversarial corruption, answering an open question posed in the finite-arm corruption literature.","Regret grows only linearly in the total corruption $C$ even though the algorithm is agnostic to $C$; when $C = O(1)$ the bound matches known no-corruption problem-dependent regret up to logarithmic factors.","Using the polynomial-time weak Löwner-John ellipsoid, the same guarantee holds computationally efficiently with regret $O(d^{5/2} C \\log T / \\Delta + d^6 \\log(d \\log T/\\delta) \\log T / \\Delta^2)$.","Setting $\\delta = 1/T$ gives expected regret $O(d^{5/2} C \\log T / \\Delta + d^6 \\log^2 T / \\Delta^2)$, asymptotically within one $\\log T$ factor of the no-corruption lower bound."],"supporting_citations":[{"why":"Defines the stochastic bandits with adversarial corruption model that this paper extends to linear action sets.","marker":"Lykouris et al. (2018)"},{"why":"Gives the improved finite-arm corruption-robust algorithm and raises the linear-setting open question that motivates this work.","marker":"Gupta et al. (2019)"},{"why":"Establishes the stochastic linear optimization problem with bandit feedback and the confidence-ball regret baseline.","marker":"Dani et al. (2008)"},{"why":"Provides the problem-dependent regret bound and the d-polytope decision-set assumption used in this paper.","marker":"Abbasi-Yadkori et al. (2011)"},{"why":"Supplies the Löwner-John ellipsoid theorem used to construct the exploration set.","marker":"Grtschel et al. (1988)"},{"why":"Provides the polynomial-time weak Löwner-John ellipsoid that gives the computationally efficient version.","marker":"Lovász (1991)"},{"why":"Supplies the Freedman-type martingale concentration inequality used to bound the corruption term.","marker":"Beygelzimer et al. (2011)"},{"why":"Gives the Chernoff-Hoeffding bound used for the noise term in coordinate estimation.","marker":"Hoeffding (1963)"}],"fun_headline_variants":["Linear regret bound despite adversarial corruption","Adversarial corruption? Regret stays linear","Corruption cost is only linear in regret","Epoch-based strategy keeps regret linear","No corruption knowledge needed, linear regret"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the adversary chooses each round's corruption before seeing which basis vector the algorithm explores that round; if the adversary could react to the current exploration draw, the martingale step and the whole regret bound collapse.","fun_headline_variants_meta":{"raw":{"variants":["Linear regret bound despite adversarial corruption","Adversarial corruption? Regret stays linear","Corruption cost is only linear in regret","Epoch-based strategy keeps regret linear","No corruption knowledge needed, linear regret"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000868,"raw_usage":{"total_tokens":3685,"prompt_tokens":797,"completion_tokens":2888,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":413,"completion_tokens_details":{"reasoning_tokens":2825}},"tokens_in":413,"tokens_out":2888,"duration_ms":21323,"temperature":1.0,"reasoning_tokens":2825,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T05:01:42.933371+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Check whether the martingale property in Lemma 4.1 holds by computing $\\mathbb{E}[(\\xi_t^j - p)c_t(s_j)\\mid\\mathcal{F}_{t-1}]$ under the protocol's ordering. If the adversary may choose $c_t$ after seeing the exploration draw, set $c_t(s_j)=-1$ on the pulled basis vector and $0$ otherwise with $C=O(1)$; the conditional mean is nonzero, the estimate is biased by a constant each epoch, and regret grows linearly in $T$, contradicting the claimed $O(C\\log T/\\Delta)$ bound.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the stochastic bandits with adversarial corruption model that this paper extends to linear action sets."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the improved finite-arm corruption-robust algorithm and raises the linear-setting open question that motivates this work."},{"cited_title":"P., and Kakade, S","cited_arxiv_id":null,"evidence_quote":"Establishes the stochastic linear optimization problem with bandit feedback and the confidence-ball regret baseline."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the problem-dependent regret bound and the d-polytope decision-set assumption used in this paper."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Löwner-John ellipsoid theorem used to construct the exploration set."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Freedman-type martingale concentration inequality used to bound the corruption term."}],"review_version":1}