{"id":"24e89af1-a488-4473-8d58-7711bea8cb38","arxiv_id":"2601.23164","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For ℓ_p unit ball action sets (p ≤ 2), parameter-noise linear bandits have minimax regret Θ~(√(dT σ_q²)), achieved by a simple explore-exploit algorithm and strictly better than the d√T additive-noise bound.","lead":"In an online decision problem where the hidden reward vector is re-sampled at every step, this paper proves that on round, curved action sets the best achievable regret scales with the reward variance—and that a very simple explore-then-exploit rule attains it. This separates the 'parameter noise' setting from the classical additive-noise model, where the same action set costs a factor √d more in regret.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claimed Θ~(√(dT σ_q²)) is not supported: Theorem 3.7 has an extra √q factor that Theorem 4.1's lower bound does not match, and the lower bound proof contains an inconsistent ε setting.","rationale":"The reader's verdict is CONDITIONAL, and the reader's rationale already notes the extra √q factor in Theorem 3.7. My stress-test confirms that this is the most load-bearing issue: the central 'minimax optimal' claim requires the upper and lower bounds to match up to logarithmic factors, but they differ by √q, which can grow with d when p is close to 1. I additionally found an internal inconsistency in the proof of Theorem 4.1 regarding the choice of ε; this is a concrete proof-level gap that should be fixed before the lower bound can be accepted as written. These concerns affect the statement of optimality, not the basic soundness of the upper-bound algorithm, so the appropriate disposition remains conditional: the paper should be revised to either strengthen the lower bound, weaken the abstract's Θ claim to explicitly include the q factor, or justify treating q as a constant for the intended regime. This does not change the reader's verdict, hence UNCHANGED.","tokens_in":30504,"tokens_out":21150,"duration_ms":203869,"concrete_test":"Re-derive Theorem 4.1 with a consistent ε = c·d^{1/2−1/q}σ/√T, choosing c<1/√2 so the Pinsker bracket is positive, and compute the exact constant in the resulting lower bound. Then compare the q-dependence with Theorem 3.7. Separately, attempt to construct a lower-bound instance (e.g., placing θ* near a coordinate hyperplane so that the optimal-action map a*(θ) has sensitivity (q−1)/∥θ*∥_q, as in Lemma B.13) and check whether the induced regret is Ω(√(dT q σ_q²)). If no such instance exists, the √q factor in the upper bound is either removable or must be explicitly acknowledged as a gap in the claimed Θ statement.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that V ALEE is minimax optimal on ℓ_p balls, p∈(1,2], with regret Θ~(√(dT σ_q²)). The upper bound Theorem 3.7 states regret Õ(d + √(dT q log(1/δ) σ_q²)), while the matching lower bound Theorem 4.1 proves only Ω(√(dT σ²)) with σ_q²=σ². The gap is a factor √q. This is not a logarithmic factor: for p=1+1/log d, q≈log d, so √q grows with d. The abstract and Table 1 omit the q factor entirely, overstating the optimality claim. Additionally, the proof of Theorem 4.1 is internally inconsistent: it defines ε=d^{1/2−1/q}σ/√T, but later resets ε=d^{1/2−1/q}σ/(2√2 T). With the initially stated ε, the key bracket (1 − √2 ε d^{1/q−1/2}√T/σ) equals 1−√2 < 0, making the displayed lower bound vacuous. With the reset ε (as written, with T in the denominator), the resulting bound is only O(σ√d), not Ω(√(dT σ²)). Unless this is a typo and the intended ε is d^{1/2−1/q}σ/(2√2√T), the lower bound proof as written does not go through; with that correction, the lower bound still lacks the √q factor present in the upper bound. Thus the 'minimax optimal up to logarithmic factors' claim is not established as stated.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies stochastic linear bandits with parameter noise, where the reward of action a is a^T θ_t and θ_t is sampled i.i.d. from a fixed distribution with mean θ* and covariance Σ. Two algorithms are proposed: V ASE, a variance-aware successive-elimination algorithm for general finite action sets, and V ALEE, a simple explore-exploit algorithm for ℓ_p unit balls with p∈(1,2]. The central advertised result is that on ℓ_p balls with p∈(1,2], the minimax regret with known covariance is Θ~(√(dT σ_q²)), where σ_q²=(∑_i Σ_ii^{q/2})^{2/q}≤4, in contrast to the additive-noise rate d√T. For unknown covariance, an additional d^{2/3+2/(3q)}T^{1/3} term is claimed. Lower bounds are also provided for ℓ_p balls with p>2. The appendices contain detailed proofs, and the proof structure is mostly transparent.","tokens_in":30901,"tokens_out":11018,"duration_ms":121339,"significance":"If the main claims hold, the paper would establish a qualitatively interesting phenomenon: in the parameter-noise model the learner can control reward variance through action choice, and on curved action sets such as ℓ_p balls with p≤2 a simple explore-exploit algorithm attains the minimax rate, which can be much smaller than the additive-noise d√T. The variance-dependent quantity σ_q² is natural, and the comparison with adversarial and additive-noise benchmarks is conceptually valuable. The detailed appendices and the explicit algorithms are strengths. However, the current manuscript does not establish the headline optimality claim: the stated upper bound contains an extra √q factor that the lower bound does not match, and the lower-bound proof has an inconsistent ε setting. These issues are load-bearing and must be resolved before the central claims can be accepted.","major_comments":[{"comment":"Theorem 3.7 states an upper bound of Õ(d + √(dT q log(1/δ) σ_q²)), while Theorem 4.1 proves only Ω(√(dT σ²)) with σ_q²=σ². The gap is √q, which is not a logarithmic factor: for p=1+1/log d, q≈log d, so the gap grows with d. Despite this, the abstract, Table 1, and Remark 3.8 all state the matching rate as Θ~(√(dT σ_q²)) without the q factor. The q factor enters the upper proof through the choice of α in Algorithm 3 and the exploration/exploitation balance, and no lower-bound evidence for it is supplied. As written, the claim of minimax optimality up to logarithmic factors is therefore not established. Either the upper bound must be improved to remove √q, or the lower bound must be strengthened to include it, and the statements in the abstract/table/remark must be corrected accordingly.","section":"Theorem 3.7, Remark 3.8, Table 1, Theorem 4.1"},{"comment":"The lower-bound proof is internally inconsistent in its choice of ε. The proof begins with ε=d^{1/2−1/q}σ/√T, but later states 'Setting ε=d^{1/2−1/q}σ/(2√2 T)'. With the original ε, the bracket (1 − √2 ε d^{1/q−1/2}√T/σ) equals 1−√2 < 0, making the displayed lower bound vacuous. With the later ε (with T in the denominator rather than √T), the factor |T|εd^{1/q} is only O(σ√d), not Ω(√(dT σ²)). The proof appears to be repairable by taking ε=d^{1/2−1/q}σ/(2√2√T) consistently, but as written the derivation does not go through. This is a load-bearing issue because Theorem 4.1 is the lower-bound pillar for the central optimality claim.","section":"Appendix C, proof of Theorem 4.1"},{"comment":"The introduction states that for a general finite action set, the V ASE bound 'is optimal up to logarithmic factors, as shown by Theorem 4.4.' However, Theorem 4.4 is restricted to ℓ_p unit balls with p>2 and dual norm q∈[1,2); it is not a lower bound for a general finite action set. The abstract's phrasing 'lower bound ... which is tight whenever log(K)≈d' is also not supported by the theorems in Section 4. If a general finite-action lower bound is intended, it must be stated and proved; otherwise the overclaim should be removed.","section":"Section 1, contribution (i); Theorem 4.4"}],"minor_comments":[{"comment":"The row for unknown-covariance V ALEE states eO(dT^{1/3} + √(dT σ_q²)), while Theorem 3.9 gives eO(d^{2/3+2/(3q)} log^{2/3}(1/δ) (Tq)^{1/3} + √(dT q log(1/δ) σ_q²)). The table is an upper-bound simplification, but it also drops the q factor from the main term, which is misleading in light of Major Comment 1.","section":"Table 1"},{"comment":"Theorem 4.1 states 'any σ²>0', but Lemma B.3 implies σ_q²≤4 for distributions supported on the ℓ_q unit ball in the relevant sense. The theorem should quantify σ² over the feasible range, or explain the rescaling/truncation that permits larger σ².","section":"Lemma B.7 / proof of Theorem 4.1"},{"comment":"There is a formatting/typo artifact at the start of Section 3.2 ('Ω(ϵ−d)' appears as a standalone fragment). This should be cleaned up.","section":"Section 3.2"},{"comment":"The paper uses Õ to hide logarithmic factors but does not state explicitly whether factors depending on d (such as q≈log d) are considered logarithmic. Given the √q gap, the convention should be stated precisely.","section":"Notation"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses an interesting and timely question, and the high-level idea that variance control in the parameter-noise model can beat additive-noise rates is plausible. However, the central minimax claim is not supported by the stated theorems: the upper bound has an unexplained √q factor, and the lower-bound proof has a concrete inconsistency. For the revision, the authors should either remove √q from the known-covariance upper bound (the q appears to enter through Algorithm 3's α, not through a matching lower bound) or prove a matching √q lower bound. If the latter is not possible, the main claims must be weakened to an upper/lower pair with an explicit gap. The general finite-action optimality claim also needs to be reconciled with the fact that Theorem 4.4 is only for ℓ_p balls with p>2."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. This paper studies stochastic linear bandits where the reward is a^T θ with θ drawn i.i.d. from a fixed distribution, and it gives variance-dependent regret bounds, including a near-optimal bound for ℓ_p balls with p≤2. The main message—parameter noise is strictly easier than additive noise, and a very simple explore-exploit rule captures the improvement—is new and basically right. It deserves a serious referee, but the headline Θ is overstated as written.\n\nWhat is genuinely new: the σ_q² quantity, the matching upper/lower bounds for known covariance in the main regime, and the observation that the simple explore-exploit rule is near-optimal. The σ_q² quantity is an honest, model-derived parameter, not a fitted constant. The proofs are detailed and mostly careful, and the relation to prior work is handled honestly: the lower-bound constructions are borrowed from Shamir and from Bubeck et al. with clear attribution.\n\nThe soft spots are real, though. Theorem 3.7's upper bound carries an extra √q factor: Õ(d + √(dT q log(1/δ) σ_q²)). Theorem 4.1's lower bound is only Ω(√(dT σ²)). For q fixed (e.g. the ℓ_2 ball) that is a constant gap, but for p close to 1, q can be log d and √q is not a log-T factor. The abstract and Table 1 state the Θ without the q, so the optimality claim is stronger than what the proofs support. Relatedly, the lower-bound proof has what looks like a typo: it sets ε = d^{1/2−1/q}σ/(2√2 T) when the algebra requires the same quantity divided by √T; as written the bracket is vacuous and the bound collapses to O(σ√d). The preceding line uses √T, so this is fixable, but it is a gap in the written proof. The sharp result also depends on the action set containing the basis directions and on curved geometry; the paper is upfront that p=1 and p>2 behave differently, and the unknown-covariance theorem has an additive d^{2/3+2/(3q)}T^{1/3} term, so the fully general minimax statement is narrower than the abstract implies.\n\nNet: the central qualitative claim holds up; the quantitative Θ needs restating, and the lower-bound proof needs a corrected ε. This is a solid subfield contribution, not a reshaping result. Send it to review. With those fixes it deserves to appear.","headline":"Parameter-noise linear bandits: a solid subfield paper with a real variance-dependent improvement, but the claimed Θ is overstated by a √q factor and the lower-bound proof has a fixable typo.","tokens_in":31365,"tokens_out":5202,"would_cite":true,"duration_ms":55896,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"On ℓ_p balls, parameter-noise bandits achieve regret √(dT σ_q²), not d√T.","keywords":["stochastic linear bandits","parameter noise","minimax regret","explore-exploit","variance-dependent bounds","ℓ_p unit ball","lower bounds"],"falsifier":"Run V ALEE on the ℓ₂ ball after deleting a few coordinate basis vectors from the action set, keeping the same Gaussian parameter-noise distribution; if regret degrades from √(dT σ_q²) toward d√T, the basis-exploration step is essential. Alternatively, evaluate the same setting on the probability simplex (flat, p=1), where the curvature-based gap lemma should fail and a matching lower bound should force the d√T rate.","tokens_in":30396,"feed_emoji":"📉","tokens_out":5344,"duration_ms":53061,"temperature":0.7,"pith_summary":"The paper studies stochastic linear bandits in which the hidden parameter θ_t is sampled i.i.d. from a fixed distribution, instead of being fixed with additive noise. Its central claim is that this 'parameter noise' model is strictly easier than the classical additive-noise model on ℓ_p unit balls with p≤2: the minimax regret is Θ~(√(dT σ_q²)) for a variance quantity σ_q²≤4, compared with d√T for additive noise. Moreover, the optimal rate is reachable by a deliberately simple explore-exploit algorithm that only ever pulls the coordinate axes. The paper also gives a general finite-action bound of order d² + √(dT log(K/δ) σ_max²) and lower bounds showing both results are tight up to logarithmic factors.","feed_headline":"Parameter noise slashes linear-bandit regret to √(dT)","feed_subtitle":"On ℓ_p balls with p≤2 the paper proves this rate is optimal — additive noise still costs d√T.","key_machinery":"The central quantity is σ_q²=(Σ_i Σ_ii^{q/2})^{2/q}, which measures the reward distribution's variance along the coordinate directions and satisfies σ_q²≤4. V ALEE's exploration pulls only the basis vectors e_i; the crucial concentration step gives coordinate-wise error √Σ_ii ε̂, and Hölder duality combines these into ‖θ̂−θ⋆‖_q ≤ √σ_q² ε̂. The curvature of the ℓ_p ball (p≤2) then converts this into a suboptimality gap for the committed action proportional to σ_q² ε̂²/‖θ⋆‖_q. For general finite sets, V ASE uses a G-optimal design with inverse-variance weighted least squares to scale the exploration with arm variances instead of the dimension.","core_discovery":"On an action set that is an ℓ_p unit ball with p∈(1,2] and dual norm q, the minimax regret in the parameter-noise model is Θ~(√(dT σ_q²)), where σ_q²=(Σ_i Σ_ii^{q/2})^{2/q} is a variance functional that is always at most 4. This is achieved by a two-phase algorithm (V ALEE) that explores only the coordinate basis vectors, estimates θ⋆ per coordinate via median-of-means, and then commits to the action sign(θ̂_i)|θ̂_i|^{q-1}/‖θ̂‖_q^{q-1}. The paper further proves a lower bound matching this rate and shows optimality up to logarithmic factors; when the covariance is unknown, the regret becomes √(dT σ_q²)+d^{2/3+2/(3q)}T^{1/3}.","pith_inferences":["The gap between additive and parameter noise is a factor of roughly √d in high dimensions when σ_q² is constant; the paper does not state this dimension-factor interpretation explicitly.","The coordinate-axis exploration is the load-bearing trick: on action sets that exclude all basis vectors, such as capped ℓ₂ balls or rotated ellipsoids, the improvement likely disappears, so the results probably do not extend without new ideas.","One could test whether exploring along the eigenvectors of Σ, rather than the standard basis, improves the bound for anisotropic covariance matrices.","The lower bounds rely on Gaussian distributions supported on the ball; relaxing the almost-sure boundedness assumption may change the minimax rate."],"forward_implications":["On ℓ_p balls with p≤2, parameter noise yields regret at most about 2√(dT), and much less when coordinate variances are tiny, whereas additive noise costs d√T regardless.","The simple explore-exploit scheme V ALEE is minimax optimal up to log factors, unlike in multi-armed bandits where a fixed exploration schedule is suboptimal.","With unknown covariance, the bound degrades by an additive d^{2/3+2/(3q)}T^{1/3} term; the paper leaves open whether a non-explore-exploit algorithm can remove it.","For p>2 the paper proves only a lower bound of order d√(T σ_max²) and leaves the matching algorithm open; its general V ASE algorithm comes within logarithmic factors."],"fun_headline_variants":["Parameter noise cuts linear-bandit regret to √(dT)","Sticky parameters make linear bandits simpler: √(dT) regret","On ℓ_p balls, parameter noise yields optimal √(dT) regret","Noisy θ? Bandit regret drops to √(dT) on ℓ_p sets"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The sharp √(dT σ_q²) rate rests on the action set being an ℓ_p unit ball with p∈(1,2], which contains the coordinate basis directions and has a curved surface; without these two geometric properties the explore-exploit analysis and the matching lower bound do not go through.","fun_headline_variants_meta":{"raw":{"variants":["Parameter noise cuts linear-bandit regret to √(dT)","Sticky parameters make linear bandits simpler: √(dT) regret","On ℓ_p balls, parameter noise yields optimal √(dT) regret","Noisy θ? Bandit regret drops to √(dT) on ℓ_p sets"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000226,"raw_usage":{"total_tokens":1347,"prompt_tokens":829,"completion_tokens":518,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":573,"completion_tokens_details":{"reasoning_tokens":433}},"tokens_in":573,"tokens_out":518,"duration_ms":5465,"temperature":1.0,"reasoning_tokens":433,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T06:11:52.843103+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run V ALEE on the ℓ₂ ball after deleting a few coordinate basis vectors from the action set, keeping the same Gaussian parameter-noise distribution; if regret degrades from √(dT σ_q²) toward d√T, the basis-exploration step is essential. Alternatively, evaluate the same setting on the probability simplex (flat, p=1), where the curvature-based gap lemma should fail and a matching lower bound should force the d√T rate.","supporting_citations":[],"review_version":1}