{"id":"3fcc3f1c-bf13-4d68-8fde-3c4b61895859","arxiv_id":"2601.02022","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Thompson sampling's Bayesian regret in linear-Gaussian bandits is Õ(σd√T + dr√trΣ0): the prior-diffusiveness burn-in is additive, not multiplicative.","lead":"A new analysis shows that Thompson sampling's Bayesian regret in linear-Gaussian bandits is the sum of a noise-driven term and a one-time prior-uncertainty term, rather than a product. The result comes with a new elliptical-potential lemma and a lower bound showing the one-time term is unavoidable.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified — main theorem proof checks out; only minor typographical issues in lower-bound lemma.","rationale":"The reader's ACCEPT verdict is consistent with my reading. I focused on the most load-bearing components: (a) the new Lemma 3, (b) its application to term (I), (c) the event concentration, (d) the lower bound. I found no fatal gap. The generalized elliptical potential lemma's proof is non-trivial but correct: for x<=2 the log bound holds; for x>2 the trace decay via the convexity of -x^p and Lemma 5 gives the factor. The chi-square tail with beta=O(sqrt(d)+sqrt(log T)) yields the stated C1 and C2. The lower bound's proof has an off-by-one in the intermediate Lemma 12, but the final Theorem 6 formula is correct; this is a typo, not a substantive error. The only true limitations are the well-specified prior and known sigma, explicitly acknowledged in Section 6; these restrict applicability but do not invalidate the theorem. Therefore no verdict change.","tokens_in":16014,"tokens_out":40066,"duration_ms":353267,"concrete_test":"Implement Lemma 3 for d=2,3 with random PSD V0 (eigenvalues ranging from 0.01 to 100) and random unit-norm u_t, T up to 10, p in {0.25,0.5,0.75}; compute LHS vs RHS. If any violation appears, the key potential lemma fails; if none, the central bound's main dependency is empirically supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I read the proof of Theorem 1 and the supporting Lemma 3 in detail. The generalized elliptical potential lemma is the key new ingredient; its proof via the case split (17), the Sherman-Morrison trace bound (18), and Lemma 5 (Hölder) is coherent. The application to the bandit decomposition (6), the chi-square concentration for the event E(β), and the C1/C2 bookkeeping all check out. The lower bound in Section 4 has a minor off-by-one in the statement of Lemma 12 (it should be sum_{i=t+2}^d lambda_i rather than i=t+1), but the final summation in Theorem 6 is correct, so the lower bound claim stands. The main caveat is the explicit scope: this is a Bayesian bound under a well-specified Gaussian prior and known sigma; this is stated in Section 6 and does not undermine the internal correctness of the theorem.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Bayesian regret of Thompson sampling in the linear-Gaussian bandit with actions in rB_2^d and a Gaussian prior N(0, Σ0). Theorem 1 states an upper bound of order σd√T·C2 + 3r√d·Tr(Σ0^{1/2})C1 + r√(2TrΣ0), which Corollary 2 converts to Õ(σd√T + dr√Tr(Σ0)). The proof introduces a generalized elliptical potential lemma (Lemma 3) that controls sums of the form ∑∥u_t∥^{2p}_{V_t^{-1}} with an explicit burn-in term Tr(V_0^{-p})−Tr(V_T^{-p}), and combines it with a standard regret decomposition and χ² concentration for the complement event. Section 4 provides a lower bound based on prior eigenvalues, arguing that a burn-in term is unavoidable. Section 5 extends the upper bound to strongly log-concave priors and noise. The scope is explicitly Bayesian with a well-specified prior and known noise variance.","tokens_in":16200,"tokens_out":16815,"duration_ms":151367,"significance":"If correct, the result meaningfully improves on prior bounds in which prior diffusiveness multiplies the T-dependent term: the burn-in cost dr√Tr(Σ0) decouples additively from the minimax rate σd√T. The proof is self-contained and derives the bound without fitted constants; C1 and C2 are explicit functions of the problem parameters, and the generalized elliptical potential lemma appears to be a new and potentially reusable tool. The lower bound, while not optimal for every spectral shape, matches the upper bound up to logarithmic factors for polynomially scaled eigenvalue sequences. The paper is also careful in stating its limitations: Bayesian regret under a well-specified Gaussian prior and known σ, as noted in Section 6.","major_comments":[],"minor_comments":[{"comment":"The telescoping sum after applying Hölder is written with log det V_{T+1}/det V_1; the product telescopes to V_T/V_0. The displayed index is inconsistent with Lemma 3's statement and with the subsequent application to U_T/U_0. Please correct the indices.","section":"Section 3, proof of Lemma 3"},{"comment":"The displayed final bound contains an extra √2 multiplier before d√T σ C2. The derivation from inequality (11), with β=√d C1 and C2=C1√(2 log(...)), gives σd√T C2, not √2 σ d√T C2. This is a typographical inconsistency between the proof and the theorem statement.","section":"Section 2.1, final display before Theorem 1"},{"comment":"The summation in Lemma 12 should run from i=t+2 to d, not i=t+1, based on the Weyl-inequality argument preceding it. The final summation in Theorem 6 should be aligned with this index shift, with the cap at min{T,d} made explicit.","section":"Section 4, Lemma 12"},{"comment":"The basis vector u_{t,1}=μ_t/∥μ_t∥_2 is undefined when μ_t=0, which occurs at t=0 for the zero-mean prior. The proof should specify an arbitrary orthonormal basis in that case; the argument is unchanged.","section":"Section 4, Lemma 10"},{"comment":"The concentration statement says the high-probability event holds 'for all t∈{1,...,T}', but the regret sum runs over t=0,...,T−1. This is only a relabeling issue but should be corrected for consistency.","section":"Section 2.1.3"},{"comment":"The description of Kalkanli and Özgür's bound differs between the introduction (d√T(σ²+r²TrΣ0) log(1+T/d)) and the related-work paragraph (σd√T + dr√Tr(Σ0)T). Please reconcile the two descriptions and cite the exact form.","section":"Related work / Introduction"},{"comment":"Several typos should be fixed: 'trivally' near inequality (10), 'random variabels' in Appendix B.1, and 'Leinder' for Leindler in Appendix B.1.1.","section":"Throughout"}],"recommendation":"minor_revision","confidential_remarks":"The central result is sound and the paper is publishable after a light revision. The main proof checks out; the issues are local typos and index inconsistencies in the lower-bound section. No concerns about novelty or attribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Let me cut to the chase: this is a genuine advance in the linear-Gaussian bandit. The bound Reg(T) = Õ(σd√T + dr√Tr(Σ0)) finally separates the prior-diffusiveness burn-in from the long-run minimax rate, and the upper and lower bounds line up to within logs in the regimes the authors claim. I'd send it to review.\n\nThe new piece that matters is the generalized elliptical potential lemma (Lemma 3), which lets V0 be near zero and handles a flexible exponent p. The proof via the case split, Sherman-Morrison, and Hölder is coherent. I checked the application to the Thompson sampling decomposition; the χ² concentration and the E(β) event are standard and handled correctly. The lower bound in Section 4 is a clean adaptation of Rusmevichientong-Tsitsiklis, with the mild caveat that it matches the upper bound only for non-pathological eigenvalue scalings; Corollary 8 covers the polynomial case. Minor issues: Lemma 12's summation should start at i = t+2, but the final summation in Theorem 6 absorbs this, so the conclusion stands. Also, the log-concave generalization in Section 5 is sketched in the main text with the proof deferred to the appendix; the appendix argument is plausible but less polished and should be checked carefully by a referee.\n\nThe soft spots are actually scope conditions more than errors. This is a Bayesian regret bound under a well-specified Gaussian prior and known noise variance, as the authors state in Section 6. That means the additive decoupling should not be read as a frequentist guarantee under prior misspecification. Exact posterior sampling is assumed, which is standard for Thompson sampling analyses but worth flagging. None of this undermines the central theorem, which is proven with explicit constants and no fitted parameters.\n\nCitation pattern looks fine: the comparison to Kalkanli and Özgür's multiplicative bound is accurate, and the related-work discussion is honest about what each prior result does and doesn't capture. The new elliptical potential lemma is likely to be reusable beyond this specific setting.\n\nWho gets value from this? Bandit theorists, especially those working on posterior sampling or elliptical potential arguments. It deserves a serious referee: the proof is nontrivial, the result improves on prior bounds, and the lower bound gives evidence of near-optimality. My recommendation: full peer review, with attention to the log-concave appendix and the minor index typos in the lower-bound section.","headline":"A real advance: the additive decoupling of prior-diffusiveness burn-in from the noise-driven minimax rate in the linear-Gaussian bandit, with a proof that holds up on inspection.","tokens_in":16681,"tokens_out":1691,"would_cite":true,"duration_ms":19431,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62L05","68W27"],"pacs":[],"model":"deepseek-v4-flash","headline":"In the linear-Gaussian bandit, Thompson sampling's Bayesian regret is, up to log factors, the sum of the minimax rate and a prior-diffusiveness burn-in that no algorithm can avoid.","keywords":["Thompson sampling","linear bandits","Bayesian regret","regret bounds","elliptical potential lemma","prior diffusiveness","burn-in","Gaussian prior"],"falsifier":"Run Thompson sampling with exact posterior sampling on a d-dimensional linear-Gaussian bandit with action set the unit ball, prior covariance S²I, noise σ, and horizon T=d. The lower bound says any policy must have Bayesian regret at least c·S·d^{3/2} for a numerical constant c. If a policy is found whose regret is o(S d^{3/2}) on this instance, the claim that the burn-in term is unavoidable is false. Conversely, checking that regret at T=r²Tr(Σ0)/σ² is dominated by dr√Tr(Σ0), independent of σ, would confirm the additive decoupling.","tokens_in":15900,"feed_emoji":"🎯","tokens_out":4211,"duration_ms":41622,"temperature":0.7,"pith_summary":"The paper proves that for linear-Gaussian bandits, Thompson sampling's Bayesian regret is, up to log factors, the sum of two pieces: the long-run minimax rate σd√T set by observation noise, and a 'burn-in' term dr√Tr(Σ0) that reflects how diffuse the initial Gaussian prior is. In earlier bounds these two quantities multiplied each other, making the regret look worse whenever the prior is spread out. The paper shows the prior-dependent term is actually additive and unavoidable: any policy must pay it while learning the initial uncertainty across all d dimensions. This makes Thompson sampling near-optimal in most parameter regimes and clarifies what prior choice can and cannot affect.","feed_headline":"Prior spread costs only an additive burn-in term","feed_subtitle":"New bound separates the initial cost of a diffuse prior from the long-run minimax rate, making Thompson sampling near-optimal.","key_machinery":"The load-bearing tool is a generalized elliptical potential lemma. Standard versions assume the initial precision matrix is at least the identity; this one allows an arbitrary positive definite V0 and any exponent p∈[0,1], producing a bound with two terms: a log-determinant term capturing the usual exploration cost and a trace term Tr(V0^{−p}) − Tr(VT^{−p}) that exactly accounts for a diffuse starting prior. Applied with p=1/2 and V0 scaled to σ²Σ0^{−1}/r², it converts the sum of instantaneous regrets into the additive form.","core_discovery":"In the linear-Gaussian bandit with actions in an ℓ2 ball of radius r and Gaussian prior N(0,Σ0) on the unknown coefficients, Thompson sampling suffers Bayesian regret Õ(σd√T + dr√Tr(Σ0)). The proof introduces a generalized elliptical potential lemma that bounds sums of Mahalanobis norms with an explicit dependence on the initial potential, yielding the additive burn-in term. A companion lower bound shows the dr√Tr(Σ0) term is unavoidable for any policy under standard Gaussian priors, up to log factors.","pith_inferences":["The additive decoupling suggests that a practitioner can choose an aggressively diffuse prior without harming long-run regret; the only cost is a fixed burn-in that is amortized over a long horizon.","Because the burn-in depends on the trace rather than the operator norm of Σ0, a prior with many small-variance directions is cheaper than one with a single large-variance direction—a distinction that could guide prior elicitation.","For misspecified priors (where θ* is not drawn from N(0,Σ0)), the additive bound should fail; quantifying that failure could measure the value of prior knowledge, a natural extension the paper leaves open.","The lower-bound technique—combining Weyl's inequality with a variance decomposition of posterior uncertainty—might carry over to other Bayesian bandit problems with Gaussian structure, such as kernelized or Gaussian-process bandits."],"forward_implications":["Thompson sampling is near-optimal for linear-Gaussian bandits across essentially all parameter regimes: when T ≤ r²Tr(Σ0)/σ² the burn-in term dominates and matches the lower bound; when T is large the long-run rate σd√T dominates.","Prior diffusiveness affects only the early burn-in period, not the asymptotically dominant regret.","The bound extends to strongly log-concave priors and noise distributions via sub-Gaussian concentration (Theorem 9).","The generalized elliptical potential lemma is a standalone tool for linear bandit analysis with arbitrary initial precision.","The lower bound (Theorem 6) shows any policy pays a burn-in proportional to the tail eigenvalues of Σ0, so the additive term is not an artifact of the analysis."],"fun_headline_variants":["Thompson Sampling Regret: Additive Burn-In, Not Multiplicative","Diffuse Priors Cost Only an Additive Burn-In in Bandits","Regret Bound: Prior Cost Decouples From Long-Run Term","New Bound: Thompson Sampling Near-Optimal With Diffuse Priors","Additive Prior Cost: Thompson Sampling's Regret Split"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The theorem assumes the prior is well-specified—θ* really is drawn from N(0,Σ0)—and the noise variance σ² is known exactly; if either fails, the additive decoupling need not hold, since the analysis is Bayesian rather than frequentist.","fun_headline_variants_meta":{"raw":{"variants":["Thompson Sampling Regret: Additive Burn-In, Not Multiplicative","Diffuse Priors Cost Only an Additive Burn-In in Bandits","Regret Bound: Prior Cost Decouples From Long-Run Term","New Bound: Thompson Sampling Near-Optimal With Diffuse Priors","Additive Prior Cost: Thompson Sampling's Regret Split"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000199,"raw_usage":{"total_tokens":1177,"prompt_tokens":679,"completion_tokens":498,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":423,"completion_tokens_details":{"reasoning_tokens":405}},"tokens_in":423,"tokens_out":498,"duration_ms":5022,"temperature":1.0,"reasoning_tokens":405,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T12:39:37.297454+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Thompson sampling with exact posterior sampling on a d-dimensional linear-Gaussian bandit with action set the unit ball, prior covariance S²I, noise σ, and horizon T=d. The lower bound says any policy must have Bayesian regret at least c·S·d^{3/2} for a numerical constant c. If a policy is found whose regret is o(S d^{3/2}) on this instance, the claim that the burn-in term is unavoidable is false. Conversely, checking that regret at T=r²Tr(Σ0)/σ² is dominated by dr√Tr(Σ0), independent of σ, would confirm the additive decoupling.","supporting_citations":[],"review_version":1}