{"id":"8d7e9dd3-eb1e-4150-b6dd-9c057b249727","arxiv_id":"2607.23679","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Fixed-action linear heteroscedastic bandits admit nearly harmonic-mean simple-regret rates that break the classical √Λ barrier, via variance-aware elimination and G-optimal design.","lead":"This paper shows that for linear bandits with fixed actions and changing noise levels, simple regret can scale with the harmonic mean of the noise variances instead of the usual square-root of total variance. That tighter rate is achievable by actively exploring informative low-noise actions and is essentially optimal.","discovery_kind":"new_method","skeptic_critique":{"model":"moonshotai/kimi-k3","headline":"Theorem 6.1's lower-bound construction violates the paper's own standing assumptions (arms {−1,1}^d have norm √d > 1), and as stated the bound is literally false in a parameter regime: it can exceed 2, the maximum simple regret possible under §3's unit-norm constraints.","rationale":"The reader correctly identified the fixed-action-set assumption as the key modeling restriction; I agree it is necessary and is openly flagged (Remark 3.1), so it is a scope limitation rather than a hidden weakness, and I do not think it should move the verdict. However, the reader's ACCEPT/HIGH-confidence assessment missed a concrete statement-level error in the lower bound, which is half of the paper's \"matching upper and lower bounds\" claim. Theorem 6.1's instance class ({−1,1}^d arms, {±c}^d parameters) violates the standing unit-norm assumptions, and because simple regret is capped at 2 under those assumptions while the stated bound grows like d/√S without a regime condition, the theorem as written is literally false for small S (worked counterexample: d=64, σ≡1, T=16 predicts E[SR] ≥ 3). The repair is standard and almost certainly preserves the paper's message in all regimes where the upper bound is non-vacuous — the normalization rescales c up by √d and the per-mistake cost down by √d, leaving the rate d/√S intact once S ≳ d². So this is a correctness-of-statement problem with an obvious fix, not a collapse of the central claim. I therefore recommend CONDITIONAL: accept contingent on (a) restating Theorem 6.1 with normalized arms plus the regime condition S ≥ d²/16 or the min{2, ·} cap, and (b) fixing Algorithm 2 Line 4's argmin so unsupported arms cannot be selected. The upper-bound analysis (Lemma B.3 confidence radius, Lemma B.4's elimination-based control of ∥a_t∥_{V^{-1}}, and the implicit-equation inversion) I found internally sound on careful reading, and the case study in §4.1, while relying on a simplifying assumption, is offered as illustration rather than load-bearing proof.","tokens_in":25423,"tokens_out":8743,"duration_ms":463790,"concrete_test":"Numerically verify the falsity and the repair: (i) instantiate d=64, σ_t≡1, T=16; confirm Theorem 6.1 as stated predicts E[SR] ≥ 3 > 2 = max possible simple regret under §3's norms, and that arms {−1,1}^64 have norm 8 > 1. (ii) Re-derive Steps 1–4 of Appendix C with A = {±1/√d}^d: check KL = 2c²S/d, c = √d/(4√S), and that ∥θ∥₂ ≤ 1 iff S ≥ d²/16; conclude the valid statement is E[SR] ≥ (3/16)min{2, d/√S} (or add S ≥ d²/16 to the theorem). (iii) Check that Remark 6.2's \"matching up to log factors\" claim holds in every regime where Theorem 4.1's bound is below the trivial value 2.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Section 3 assumes ∥a∥₂ ≤ 1 for all a ∈ A and ∥θ*∥₂ ≤ 1, and Theorem 6.1 claims an instance \"satisfying our assumptions.\" But the proof (Appendix C, Step 1) uses A = {−1,1}^d and Θ = {±c}^d with c = (1/4)S^{−1/2}, S = Σ_t 1/σ_t². The arms have ∥a∥₂ = √d, and ∥θ∥₂ = c√d, violating both constraints for d ≥ 2 (and for any S < d/16 even ignoring arm norms). This is not cosmetic: the chain-rule KL computation relies on a²_{t,j} = 1 to get KL = 2c²S. Normalizing the arms to {±1/√d}^d rescales the per-coordinate mean gap by 1/√d, giving KL = 2c²S/d, which forces c = √d/(4√S); the final bound (3/16)d/√S survives, but now ∥θ∥₂ = d/(4√S) ≤ 1 requires S ≥ d²/16. The theorem states the bound \"for any d ≥ 2 and T ≥ 1\" with no such regime condition. The literal statement is false: e.g., d = 64, σ_t ≡ 1, T = 16 gives S = 16 and the theorem asserts E[SR(T)] ≥ (3/16)·64/4 = 3, while under §3's assumptions SR(T) = E[⟨θ*, a* − â_T⟩] ≤ 2∥θ*∥∥a∥ ≤ 2 pointwise. So the \"matching lower bound\" half of the headline claim rests on a construction outside the model in which the upper bounds are proved, and the true statement needs either unnormalized arms (changing the problem) or the repair E[SR] ≥ (3/16)·min{2, d·S^{−1/2}} with regime condition S ≳ d². Mitigation: in every regime where Theorem 4.1's upper bound is non-vacuous (d/√S < 1, i.e., S > d²), the repair holds, so the central harmonic-mean message almost certainly stands — but the theorem as written is incorrect and the \"nearly matching\" claim (Remark 6.2) is unverified at the boundary. Separately, Algorithm 2 Line 4's argmin over all a ∈ A of the product (Σ_{τ∈T(a)} 1/σ²_τ)·π(a) is 0 for any unsupported arm (π(a) = 0), so as written the argmin can select unsupported arms forever; Lemma D.1's identity Σ_{a∈supp} π(a)Σ_{τ∈T(a)}1/σ²_τ = Σ_t 1/σ²_t then fails. This is fixable (restrict to supp(π) or use the ratio rule) but should be corrected.","agreement_with_reader":"partial"},"referee_report":{"model":"moonshotai/kimi-k3","summary":"The paper studies best-arm identification (simple regret) in d-dimensional stochastic linear bandits with observed heteroscedastic sub-Gaussian noise, under a fixed, known action set. Prior variance-aware work achieved simple regret Õ(d√(Λ/T²)) with Λ=Σσ_t². The authors argue Λ is the wrong complexity measure and propose VAEE (variance-aware elimination with information-gain-maximizing arm selection) for large/infinite action sets, achieving Õ(d[Σ_t σ_t^{-2} − Σ_{i≤Õ(d)} σ_{(i)}^{-2}]^{-1/2}) — a harmonic-mean-type rate (Theorem 4.1). For finite action sets, VAGD (variance-adaptive approximate G-optimal design) sharpens the d-dependence to √(d log|A|) (Theorem 5.3). A two-point Le Cam argument over a hypercube instance yields a nearly matching lower bound Ω(d(Σσ_t^{-2})^{-1/2}) (Theorem 6.1). An extension to heavy-tailed noise via adaptive pseudo-Huber regression is given in Appendix E. The fixed-action-set restriction is acknowledged as necessary (Remark 3.1, citing He & Gu 2025).","tokens_in":26008,"tokens_out":3377,"duration_ms":63997,"significance":"If the results hold, this is a genuinely important contribution: it identifies the harmonic mean (total precision minus the Õ(d) largest precisions) as the correct variance-dependent complexity measure for fixed-action-set heteroscedastic linear bandits, replacing the crude Λ=Σσ_t² proxy, and shows the √Λ barrier of time-varying settings is escapable. Strengths worth crediting explicitly: the rate is derived from first principles (elliptical-potential bookkeeping plus a per-coordinate Le Cam/Pinsker argument) with no fitted constants; full proofs are supplied, including a Kiefer–Wolfowitz-based finite-action improvement and a heavy-tailed extension; and the lower bound is instance-dependent in the variance sequence rather than worst-case, which is the right notion here. The Õ(d)-subtraction term is argued to be necessary (Remark 4.3), which is honest bookkeeping.","major_comments":[{"comment":"Theorem 6.1 (Appendix C, Step 1) constructs A={-1,1}^d and Θ={±c}^d with c=(1/4)S^{-1/2}, S=Σ_t σ_t^{-2}. These arms have ||a||_2=√d>1, contradicting §3's standing assumption ||a||_2≤1, and the chain-rule KL step uses a²_{t,j}=1 to obtain KL=2c²S. Renormalizing arms to {±1/√d}^d rescales the per-coordinate mean gap by 1/√d, giving KL=2c²S/d and forcing c=√d/(4√S); the final rate (3/16)dS^{-1/2} survives, but then ||θ||_2=d/(4√S)≤1 requires S≥d²/16. As stated 'for any d≥2 and T≥1' the bound is literally false: with d=64, σ_t≡1, T=16 it asserts E[SR]≥3, while under §3's constraints SR≤2 pointwise. Please restate with normalized arms, the regime condition S≳d², and a min{2,·} cap. Note the repair preserves 'nearly matching' wherever Theorem 4.1 is non-vacuous (d/√S<1), so Remark 6.2 should carry that qualification.","section":"§6, Theorem 6.1 / Appendix C"},{"comment":"Definition (3.1) defines SR(T) as an expectation, but Theorem 4.1 (and Theorem 5.3) bound the realized gap with probability 1-δ, and §4.1 computes expected simple regret via failure-probability decay. Since |⟨θ*,a*−â⟩|≤2 under §3, converting is trivial (E[SR]≤bound+2δ for δ chosen appropriately), but the statements as written do not bound the quantity defined in (3.1). This also interacts with the comparison in §4.3, where SR_Alg1 and SR_Weighted-OFUL are compared as if both were expected simple regrets, while the cited √Λ bounds are high-probability cumulative-regret results divided by T. Please align the metric across statements and Table 1/Table 2.","section":"§3.1 Eq. (3.1) vs. Theorems 4.1/5.3"}],"minor_comments":[{"comment":"Line 7 defines C_t = {θ: ||θ−θ̂_t||²_{V^{-1}_t} ≤ β_t}, but Lemma B.3 and the entire analysis use the V_t-norm. Presumably a typo (V^{-1}→V), but as written the elimination rule uses a nonstandard confidence set.","section":"Algorithm 1"},{"comment":"Line 4's argmin over Σ_{τ∈T(a)} σ_τ^{-2}·π(a) is undefined at t=1 when all T(a)=∅ (all ties); tie-breaking and the handling of arms outside supp(π) should be stated.","section":"Algorithm 2, Line 4"},{"comment":"The closing step uses Σ_t σ_t^{-2} a_t a_t^⊤ = V_T, but V_T = I + Σ_t σ_t^{-2} a_t a_t^⊤; the inequality direction still goes through but the displayed equality should be corrected. Also 'Outout' in line 8.","section":"Lemma D.2 proof / Algorithm 2"},{"comment":"Typos: 'assumpition' in the proof of Lemma B.3; 'an variance-sequence-dependent' in Remark 6.2; 'eO(d)' in Table 2's footnote (Õ rendering); mixed 'minimises/minimizes' spellings in §5.1.","section":"Various"},{"comment":"The heavy-tailed extension imports the confidence radius of Li & Sun (2024) wholesale; a sentence on why the adaptive pseudo-Huber estimator preserves the elliptical-potential bookkeeping of Lemma B.4 (which is where the harmonic mean enters) would make the extension self-contained at the level of the key step.","section":"§E, Theorem E.3"},{"comment":"The claim 'first work that breaks the √Λ barrier' should acknowledge more precisely the fixed-action-set observation of He & Gu (2025) that motivates it; currently Remark 3.1 does this but the abstract does not.","section":"§1, contributions"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is published at ICLR 2026; the lower-bound repair is a straightforward renormalization plus a regime condition, so I do not expect the revision to be difficult. The comparison in Table 1 converts prior cumulative-regret lower bounds by dividing by T, which is not a valid conversion in general; the authors should either justify it or present the comparison only at the level of rates for the specific constructions."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The real news is that under a fixed action set the √Λ barrier is not information-theoretic. VAEE (and the finite-arm VAGD variant) get simple regret scaling like d over the square root of the harmonic sum of the precisions, minus an Õ(d) correction for the smallest variances, and they prove a matching Ω(d / √∑ 1/σ_t²) lower bound. Prior variance-aware work (Zhou, Zhao, Jia, He–Gu) all kept √Λ even when A is fixed; this is the first paper that replaces it and shows why fixed A is essential.\n\nWhat they do well is clean. The active-exploration + elimination rule is the natural variance-weighted OFUL fix, the elliptical-potential argument that produces the harmonic expression is standard and checkable, and the finite-arm G-optimal design version correctly shaves the √d down to √log|A|. The case study in §4.1 showing Weighted OFUL can be exponentially worse on anisotropic low-variance windows is useful. They flag the fixed-A assumption up front and cite the matching time-varying lower bounds, so there is no over-claim on the broader setting.\n\nTwo soft spots, both fixable. The lower-bound construction in Appendix C uses arms {−1,1}^d (norm √d) and Θ = {±c}^d, which violates the paper’s own unit-ball assumptions; as written the claimed bound can exceed the trivial maximum regret of 2. Normalizing the arms restores the same d/√S rate once S ≳ d², which is exactly the regime where the upper bound is non-vacuous, so the harmonic-mean message survives, but Theorem 6.1 and Remark 6.2 need the regime condition or the min{2, ·} repair. Separately, Algorithm 2’s argmin is written over all of A and can pick unsupported arms forever; restricting to supp(π) fixes Lemma D.1. Neither issue touches the upper-bound proofs.\n\nNo experiments, none required. Self-citations are to the authors’ earlier variance-aware upper bounds and are appropriate. This is for people who already care about second-order / variance-aware bandit rates or experimental design under heteroscedasticity. It deserves a serious referee; I would cite the upper bounds and the fixed-vs-varying distinction.","headline":"First clean break of the √Λ barrier for fixed-action heteroscedastic linear bandits via harmonic-mean simple regret, with a lower-bound statement that needs a routine norm fix.","tokens_in":26923,"tokens_out":597,"would_cite":true,"duration_ms":19374,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"When the action set is fixed, linear bandits with heteroscedastic noise obey a harmonic-mean rate, not the classical total-variance √Λ barrier.","keywords":["linear bandits","heteroscedastic noise","simple regret","harmonic mean","fixed action set","variance-aware exploration","G-optimal design"],"falsifier":"Construct a fixed action set and a variance sequence containing a long low-noise window; check whether VAEE’s simple regret decays like the claimed harmonic mean while a total-variance algorithm remains stuck at the slower √Λ rate.","tokens_in":26432,"feed_emoji":"📉","tokens_out":805,"duration_ms":17018,"temperature":0.7,"pith_summary":"Prior work on linear bandits with changing noise levels measured difficulty by the sum of variances Λ. That sum stays large even when many rounds are nearly noiseless, so the resulting simple-regret bounds look loose. This paper shows that the looseness is real once the action set never changes: the right measure is essentially the harmonic mean of the variances (after discarding a few of the smallest ones). The authors give an elimination algorithm that actively pulls the most informative remaining arm and prove a simple-regret bound that scales with that harmonic mean; a matching lower bound confirms the rate is unavoidable. The same idea, specialized to a finite action set via a variance-aware G-optimal design, improves the dimension dependence still further. The practical upshot is that quiet rounds can be exploited far more aggressively than total-variance analyses allow, provided the menu of arms stays fixed.","feed_headline":"Fixed arm sets break the √Λ barrier for noisy linear bandits","feed_subtitle":"Simple regret tracks the harmonic mean of variances, not their sum, once the menu never changes","key_machinery":"VAEE (Variance-Aware Exploration with Elimination): maintain a confidence ellipsoid with inverse-variance weighting, keep only arms that are still competitive, and always pull the surviving arm of largest elliptical norm; the resulting potential identity yields the harmonic-mean bound.","core_discovery":"For stochastic linear bandits whose action set is fixed for the entire horizon and whose noise variances are observed, simple regret is governed by a nearly harmonic-mean quantity ∑ 1/σ_t² minus the contribution of the Õ(d) smallest variances, not by √Λ. The algorithm VAEE attains this rate and a matching lower bound shows it cannot be improved in general.","pith_inferences":["If contexts are drawn i.i.d. from a fixed distribution rather than chosen adversarially, a similar harmonic-mean rate should remain attainable by the same elimination logic.","Online variance estimation could replace the paper’s assumption that σ_t is revealed after each pull, at the cost of an extra estimation term.","In linear MDPs the same idea may convert estimated transition variances into horizon-free, harmonic-mean style sample-complexity bounds."],"forward_implications":["Quiet rounds can be turned into near-exact recovery of the linear parameter when the arm set is static.","Finite-arm instances admit a further √d improvement via variance-aware G-optimal design.","Any cumulative-regret analysis that only tracks Λ is information-theoretically suboptimal on fixed action sets.","The same harmonic-mean principle extends, with a robust estimator, to heavy-tailed noise of bounded second moment."],"fun_headline_variants":["Fixed action sets break the √Λ barrier in linear bandits","Simple regret tracks harmonic mean of variances, not √Λ","VAEE hits nearly harmonic-mean rate for fixed-arm heteroscedastic bandits","Lower bound confirms harmonic-mean rate is tight for fixed sets","Variance-adaptive elimination beats total-variance barrier"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"The set of available actions must be exactly the same in every round; if an adversary can change the menu each round, the √Λ barrier returns.","fun_headline_variants_meta":{"raw":{"variants":["Fixed action sets break the √Λ barrier in linear bandits","Simple regret tracks harmonic mean of variances, not √Λ","VAEE hits nearly harmonic-mean rate for fixed-arm heteroscedastic bandits","Lower bound confirms harmonic-mean rate is tight for fixed sets","Variance-adaptive elimination beats total-variance barrier"]},"model":"grok-4.5","effort":"low","cost_usd":0.004038,"raw_usage":{"total_tokens":1308,"prompt_tokens":898,"num_sources_used":0,"completion_tokens":70,"cost_in_usd_ticks":40384000,"prompt_tokens_details":{"text_tokens":898,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":340,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":898,"tokens_out":70,"duration_ms":6749,"temperature":1.0,"reasoning_tokens":340,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-30T16:04:20.854625+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Construct a fixed action set and a variance sequence containing a long low-noise window; check whether VAEE’s simple regret decays like the claimed harmonic mean while a total-variance algorithm remains stuck at the slower √Λ rate.","supporting_citations":[],"review_version":1}