{"id":"8bf69c56-a8ae-40f1-b952-09a2edc93f78","arxiv_id":"2502.06363","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A tighter maximum posterior variance bound gives near-optimal cumulative and simple regret guarantees for GP bandits in noiseless, large-norm, and non-stationary-noise settings.","lead":"This paper proves a new bound on how fast uncertainty shrinks in Gaussian process bandit algorithms, and uses it to show near-optimal regret in noiseless settings, with respect to function norm, and under time-varying noise. A smart generalist might read it because it determines, up to log factors and conjectured lower bounds, how efficiently black-box optimization can work for smooth unknown functions.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The core Lemma 3.1 relies on Lemma 3.3, an unproved external count lemma from Flynn and Reeb; if that lemma fails or its hypotheses are not met, every main regret bound in the paper loses its foundation.","rationale":"The reader's strongest_claim correctly identifies Lemma 3.1 as the load-bearing result, and the weakest_assumption points to the unproved reliance on Lemma 3.3. My stress-test concurs: every subsequent theorem (noiseless PE/MVR bounds, RKHS-norm-optimal simple and cumulative regret, non-stationary variance bounds) flows from Eq. (4), which in turn hinges on the count lemma's |T_c| ≤ 3γ_n(λ~²I) bound. If Lemma 3.3 is invalid, the entire contribution collapses; if it is valid, the core argument is sound modulo the acknowledged discretization and argmax idealizations. The paper's own text explicitly cites Lemma 3.3 as external and provides no proof, so a reader cannot fully certify the main claim without going to the cited preprint. The secondary proof mismatch in Theorem 5.1's SE case (B = O(exp(n^{1/(d+1)})) does not imply the λ² = Ω(exp(-n^{1/(d+1)})) condition required by Corollary 3.2(1)) is real and was correctly noted by the reader, but it affects a subcase of one application rather than the central inequality itself. It strengthens the case for a conditional verdict but does not change the assessment that the paper is a serious, novel contribution whose core lemma should be verified against the cited source.","tokens_in":59287,"tokens_out":16603,"duration_ms":131593,"concrete_test":"Obtain Flynn and Reeb [2024], Lemma D.9, and verify its proof in full, checking that the refined bound |T_c| ≤ 3γ(3γ_n(λ²I), λ²) follows without hidden assumptions, and that the monotonicity requirements on γ match those stated in the paper's Lemma 3.3. Then confirm that applying it with λ = λ~_n (which may depend on n) satisfies the lemma's hypotheses for every fixed n. As a fallback, prove directly that |T_c| ≤ (2/ln 2)γ_n(λ²I) from ∑_{i≤n} ½log(1+λ^{-2}σ_{i-1}²) ≤ γ_n(λ²I) and note whether this weaker bound would break the claimed RKHS-norm and non-stationary regret rates.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central inequality, Lemma 3.1, bounds the maximum posterior variance under MVR by (4/n)√(λ~²nγ_n(λ~²I)). The proof's final step uses Lemma 3.3 to argue that the number of 'large variance' rounds is at most 3γ_n(λ~²I_n), giving |T| ≥ n/2 under the assumption n/2 ≥ 3γ_n. Lemma 3.3 is quoted from Flynn and Reeb [2024] and is not proved in the manuscript, not even sketched. This is not merely a cosmetic omission: the count lemma is exactly what converts the MVR selection rule into the |T| ≥ n/2 lower bound, and the refined form |T_c| ≤ 3γ(3γ_n(λ²I), λ²) is needed for the B-dependence in Theorem 5.3. If Lemma 3.3 is false, or if its hypotheses (fixed λ, arbitrary sequence, monotone MIG bound) are not satisfied when Lemma 3.1 applies it with λ = λ~_n and the MVR-induced sequence, then Eq. (4), Corollary 3.2, and all downstream results in Sections 4–6 fail. The paper gives no self-contained verification, and the cited result is itself a preprint. This is the single most load-bearing assumption in the manuscript, and the reader's conditional verdict is appropriate unless the lemma is independently confirmed.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Gaussian process bandits and proposes a new upper bound on the maximum posterior variance under maximum variance reduction (MVR), stated as Lemma 3.1. The bound is then applied to three settings: noiseless rewards, regret bounds that are optimal in the RKHS norm upper bound B, and non-stationary observation noise variance. The authors prove regret upper bounds for PE- and MVR-style algorithms in these settings and provide lower bounds for the non-stationary variance setting. The main technical engine is Lemma 3.1, and most downstream results are derived as corollaries of it. The proof of the stationary case of Lemma 3.1 relies on an external elliptical-potential count lemma, Lemma 3.3, which is not proved in the manuscript.","tokens_in":59583,"tokens_out":16655,"duration_ms":141843,"significance":"If Lemma 3.1 and Lemma 3.3 are valid, the paper gives a unified treatment that improves on existing noise-variance dependence, recovers the conjectured noiseless Matérn lower-bound regime, obtains RKHS-norm-optimal simple and cumulative regret bounds under restricted growth of B, and provides the first regret analysis for non-stationary variance GP bandits. The non-stationary lower bounds and the explicit extension of the MIG-based argument to heteroscedastic noise are valuable contributions. However, the central count lemma is quoted from an unreviewed preprint, and the proof of the SE case of Theorem 5.1 has a condition mismatch; these issues must be resolved before the contributions can be fully assessed.","major_comments":[{"comment":"Lemma 3.3 is load-bearing but is quoted from Flynn and Reeb [2024] and is not proved or even sketched in this manuscript. In the proof of Lemma 3.1 it is used at Eqs. (18)-(20) to obtain |T| >= n/2, and the refined form is also used in the proof of Theorem 5.3. Since Eq. (4) is the foundation for Corollary 3.2 and all theorems in Sections 4-6, the manuscript is not self-contained at its core. Please include a full proof of Lemma 3.3 or a precise verification that the MVR-induced sequences and the specific choices of lambda_tilde_n used in Sections 4-6 satisfy its hypotheses.","section":"Section 3, Lemma 3.3"},{"comment":"The SE case of Theorem 5.1 does not follow from the stated assumptions by the cited Corollary 3.2 statement 1. With lambda^2 = Theta(B^{-2}) and B = O(exp(n^{1/(d+1)} ln^{-alpha}(1+n))), one has lambda^2 = Omega(exp(-2 n^{1/(d+1)} ln^{-alpha}(1+n))), not lambda^2 = Omega(exp(-n^{1/(d+1)} ln^{-alpha}(1+n))). The proof's claim that the condition implies lambda^2 = O(exp(-(1/2) n^{1/(d+1)} ln^{-alpha}(1+n))) has the inequality reversed. The theorem may be recoverable by applying Lemma 3.1 directly, because ln(n/lambda^2) = O(n^{1/(d+1)} ln^{-alpha} n) makes gamma_n = o(n), but the proof as written is invalid and must be rewritten.","section":"Theorem 5.1 / Appendix E.2"},{"comment":"The confidence bounds in Lemma E.1 and Lemma F.1 are explicitly non-adaptive: they require the input sequence to be independent of the noise sequence. MVR satisfies this condition because its queries depend only on posterior variances, but PE and VA-PE eliminate candidates using noisy observations, so their subsequent batch designs are noise-dependent. The proofs of Theorems 5.3 and 6.3 invoke these lemmas without a conditioning argument. Please either prove a conditional version of the confidence bound for each batch or use a fully adaptive confidence bound; without this, the cumulative regret guarantees for PE and VA-PE are not established.","section":"Lemma E.1 / Lemma F.1 and Theorems 5.3, 6.3"}],"minor_comments":[{"comment":"The references for Flynn and Reeb [2024] and Kim and Sanz-Alonso [2024] list the same arXiv identifier, arXiv:2401.17037; at least one of these identifiers is incorrect.","section":"References"},{"comment":"The table mentions GP-UCB+ and EXPLOIT+ as algorithms from Kim and Sanz-Alonso, but these names are not introduced in the main text; a short explanation or pointer would help the reader.","section":"Table 2"},{"comment":"Remark 4.3 states that the exact-argmax assumption can be relaxed with an extra sqrt(ln n) factor, but no formal theorem with the discretized variant is given; stating the precise assumptions and resulting bound would make the remark more useful.","section":"Remark 4.3"},{"comment":"In Eq. (27) the notation tilde_X_{j-1} and the associated variance bound are clear, but the monotonicity step would benefit from an explicit sentence identifying that conditioning on fewer data points increases the posterior variance.","section":"Appendix C.1, proof of Lemma C.1"}],"recommendation":"major_revision","confidential_remarks":"The paper is a serious theoretical contribution, and the overall architecture of the proof is coherent. The main blocker is that Lemma 3.3, which is needed for the central variance bound, is taken from an unreviewed arXiv preprint without proof. In addition, the SE case of Theorem 5.1 has a proof gap that should be fixable by applying Lemma 3.1 directly. If the authors supply a complete proof of Lemma 3.3 and repair the Theorem 5.1 proof, I would be willing to support publication; the current version is not yet self-contained enough for a journal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth a serious referee. Lemma 3.1 is a real improvement over Eq. (7): it removes the sqrt(ln(1+lambda^{-2})) factor and replaces it with lambda, and the downstream noiseless, RKHS-norm, and non-stationary variance bounds are new uses of that inequality. The authors are transparent about limitations (Remark 4.3 on exact argmax, the finite-X assumptions, the restricted B ranges in Theorem 5.3), and the appendices give enough detail that the main derivations are checkable. The non-stationary variance setting is not just a repackaging; the VA-PE and VA-MVR analyses and the matching lower bounds are a genuine extension to GP bandits.\n\nThe soft spot is exactly where the stress test points. Lemma 3.1's proof uses Lemma 3.3, the elliptical potential count lemma from Flynn and Reeb, to get |T| >= n/2. That lemma is not proved, not sketched, and the cited source is itself an arXiv preprint. Lemma 3.3 is load-bearing: if it fails, or if its hypotheses are not met at the small lambda_tilde used in Lemma 3.1, then Eq. (4), Corollary 3.2, and every theorem in Sections 4-6 lose their foundation. The authors seem aware of the dependence but they do not lighten it. A referee should not have to chase a preprint to verify the main engine of the paper.\n\nThere is also a smaller proof mismatch in Theorem 5.1, SE case. The theorem sets lambda^2 = Theta(B^{-2}) with B = O(exp(n^{1/(d+1)} ln^{-alpha} n)), but Corollary 3.2 statement 1 requires lambda^2 = Omega(exp(-n^{1/(d+1)} ln^{-alpha} n)). The assumed bound on B only gives lambda^2 exponentially smaller than what the corollary needs. The Matern case of Theorem 5.1 looks fine, and Theorem 5.3 avoids this issue by using Lemma 3.3 directly, but the SE part of Theorem 5.1 needs repair or a different argument.\n\nNone of this is fatal to the whole paper, and I do not see circularity or inflated claims. The citation pattern is appropriate. The right outcome is conditional acceptance: send it to review, require the authors to either prove Lemma 3.3 in this paper or cite a published version with the exact statement, and fix the Theorem 5.1 SE condition. If the count lemma checks out, this is a solid contribution to the GP bandit literature. If it does not, the upper bounds collapse. I would bring it to reading group and would cite it once the lemma is sorted.","headline":"A genuinely useful variance bound and three applications, but the main theorem leans on an unproved external count lemma; referee should demand a proof before acceptance.","tokens_in":60151,"tokens_out":2508,"would_cite":true,"duration_ms":21767,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","62L05","60G15"],"pacs":[],"model":"deepseek-v4-flash","headline":"A sharper upper bound on the maximum posterior variance makes GP-bandit regret optimal in noiseless, RKHS-norm, and non-stationary-noise settings.","keywords":["Gaussian process bandits","regret bounds","maximum variance reduction","phased elimination","noiseless reward","RKHS norm","non-stationary noise","posterior variance"],"falsifier":"Run the MVR query sequence on a one-dimensional squared-exponential kernel with $\\lambda_n^2 = \\exp(-n^{1/(d+1)}\\ln^{-\\alpha} n)$, compute the set $T_> = \\{t : \\lambda^{-1}\\sigma_{t-1}(x_t)>1\\}$, and compare $|T_>|$ to the bound $3\\gamma_n(\\lambda^2 I)$. If $|T_>|$ exceeds that bound while $n/2 \\ge 3\\gamma_n(\\lambda^2 I)$, then Lemma 3.3—and with it the regret theorems that rely on Lemma 3.1—fails.","tokens_in":59079,"feed_emoji":"🎯","tokens_out":8370,"duration_ms":70643,"temperature":0.7,"pith_summary":"The paper's central aim is to sharpen Gaussian-process bandit regret bounds by proving a new uniform upper bound on the posterior standard deviation of a maximum-variance-reduction (MVR) query sequence. The bound improves how regret scales with the noise-variance parameter and with the RKHS norm of the reward, and it powers three sets of results: noiseless cumulative and simple regret that match or approach known lower bounds, RKHS-norm-optimal cumulative and simple regret, and the first regret analysis for GP bandits with time-varying observation noise. The main inequality says that after enough MVR queries the largest remaining uncertainty is at most of order $\\sqrt{\\tilde\\lambda^2 \\gamma_n / n}$, where $\\gamma_n$ is the kernel's maximum information gain. A sympathetic reader would care because these are gaps that had been left open: the noiseless cumulative regret reaches the conjectured lower bound, and the non-stationary-noise guarantees are optimal up to logarithmic factors.","feed_headline":"Tighter variance bound yields optimal GP-bandit regret in three settings","feed_subtitle":"A new maximum-posterior-variance inequality closes noiseless, RKHS-norm, and non-stationary-noise regret gaps.","key_machinery":"The load-bearing object is Lemma 3.1, a uniform upper bound on the maximum posterior variance under MVR: for $n/2 \\ge 3\\gamma_n(\\tilde\\lambda_n^2 I_n)$, one has $\\max_{x\\in \\tilde X} \\sigma_{\\lambda_n^2 I_n,n}(x; X_n) \\le \\frac{4}{n}\\sqrt{\\tilde\\lambda_n^2 n \\gamma_n(\\tilde\\lambda_n^2 I_n)}$, where $\\gamma_n$ is the maximum information gain. The proof combines MVR's defining property—the current query point has the largest posterior variance, so the final maximum variance is no larger than the average over any subset of past queries—with an information-gain summation bound and Lemma 3.3, a quoted elliptical-potential count lemma that bounds the number of rounds whose scaled posterior standard deviation exceeds one. That count forces at least $n/2$ of the first $n$ queries to be informative, which converts the averaged variance into the displayed decay.","core_discovery":"The core claim is that under the MVR selection rule, the maximum posterior standard deviation over the candidate set decays as $\\sqrt{\\tilde\\lambda_n^2 \\gamma_n / n}$ rather than at the slower rates previously known when the observation-variance parameter $\\lambda^2$ tends to zero. This is Lemma 3.1, with Corollary 3.2 giving explicit rates for squared-exponential and Matérn kernels. From this inequality, phased elimination (PE) attains $O(\\ln n)$ cumulative regret for squared-exponential kernels and the conjectured lower-bound rates for Matérn kernels in the noiseless setting, while MVR attains exponentially decaying simple regret for squared-exponential kernels and the order-optimal $n^{-\\nu/d}$ rate for Matérn kernels. The same inequality yields simple- and cumulative-regret bounds with near-optimal dependence on the RKHS norm bound $B$ for noisy rewards. Applying it to a time-varying noise-variance model gives cumulative and simple regret bounds expressed through the cumulative variance proxy $V_n=\\sum_{t}\\sigma_t^2$, matching lower bounds derived from stationary and noiseless lower-bound arguments.","pith_inferences":["The same posterior-variance bound should transfer to Bayesian GP bandits with decreasing observation noise, yielding Bayesian regret improvements not explicitly derived in the paper.","If the conjectured MIG exponent of $\\ln^{d/2}$ is established, the squared-exponential simple-regret exponent should improve from $-1/(d+1)$ toward $-2/d$, a strengthening the paper itself flags as plausible.","The non-stationary variance machinery could also apply to input-dependent heteroscedastic noise whenever the cumulative variance proxy grows sublinearly, suggesting a testable extension to drift-prone experimental settings that the paper only sketches."],"forward_implications":["Noiseless cumulative regret: PE attains $O(\\ln n)$ for squared-exponential kernels and the conjectured optimal rates for Matérn kernels, with deterministic guarantees rather than high-probability ones.","Noiseless simple regret: MVR attains $O(\\exp(-\\tfrac12 n^{1/(d+1)}\\ln^{-\\alpha} n))$ for squared-exponential kernels and $\\tilde O(n^{-\\nu/d})$ for Matérn kernels with $\\nu>1/2$.","RKHS-norm optimality: setting the GP noise parameter to $\\Theta(B^{-2})$ makes both simple and cumulative regret scale with the RKHS norm bound $B$ at the same polynomial rate as the lower bound, up to logarithmic factors, within the stated regimes of $B$-growth.","Non-stationary variance: VA-PE and VA-MVR regret bounds are governed by the cumulative variance proxy $V_n=\\sum_{t}\\sigma_t^2$ and match the derived lower bounds; when $V_n$ grows sublinearly, the algorithms beat the stationary-noise regret floor."],"supporting_citations":[{"why":"Supplies the information-gain summation bound and the GP bandit setup that the proof of Lemma 3.1 invokes.","marker":"[Srinivas et al., 2010]"},{"why":"Quoted as Lemma 3.3, the elliptical-potential count lemma that forces $|T| \\ge n/2$ in the MVR proof.","marker":"[Flynn and Reeb, 2024]"},{"why":"Introduces MVR and its posterior-variance and simple-regret analysis, which Lemma 3.1 tightens.","marker":"[Vakili et al., 2021]"},{"why":"Establishes the phased-elimination analysis and near-optimal baseline that Sections 4 and 5 refine.","marker":"[Li and Scarlett, 2022]"},{"why":"Provides the noisy-regret lower bounds that certify RKHS-norm optimality and underpin the Section 6 lower bounds.","marker":"[Scarlett et al., 2017]"},{"why":"Supplies noiseless simple-regret and expected-regret lower bounds used in the noiseless and non-stationary comparisons.","marker":"[Bull, 2011]"},{"why":"States the conjectured noiseless cumulative-regret lower bound that Theorem 4.1 matches.","marker":"[Vakili, 2022]"},{"why":"Gives the data-processing inequality used in Lemma 3.1 to replace a general variance matrix by $\\tilde\\lambda^2 I$ in the MIG bound.","marker":"[Cover and Thomas, 2006]"}],"fun_headline_variants":["Optimal GP-bandit regret via tighter variance bound","New posterior-variance bound closes three GP regret gaps","Tighter variance bound nails GP-bandit optimality","GP bandits: refined variance bound yields optimal regret","Variance-bound fix gives optimal regret in GP bandits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"A quoted counting lemma, not proved in the paper, must correctly bound how many rounds can have scaled posterior standard deviation above one; this count is what guarantees that at least half the MVR queries are informative, and every regret theorem collapses if the count is wrong.","fun_headline_variants_meta":{"raw":{"variants":["Optimal GP-bandit regret via tighter variance bound","New posterior-variance bound closes three GP regret gaps","Tighter variance bound nails GP-bandit optimality","GP bandits: refined variance bound yields optimal regret","Variance-bound fix gives optimal regret in GP bandits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000176,"raw_usage":{"total_tokens":1312,"prompt_tokens":988,"completion_tokens":324,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":604,"completion_tokens_details":{"reasoning_tokens":247}},"tokens_in":604,"tokens_out":324,"duration_ms":4488,"temperature":1.0,"reasoning_tokens":247,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T15:42:05.656189+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the MVR query sequence on a one-dimensional squared-exponential kernel with $\\lambda_n^2 = \\exp(-n^{1/(d+1)}\\ln^{-\\alpha} n)$, compute the set $T_> = \\{t : \\lambda^{-1}\\sigma_{t-1}(x_t)>1\\}$, and compare $|T_>|$ to the bound $3\\gamma_n(\\lambda^2 I)$. If $|T_>|$ exceeds that bound while $n/2 \\ge 3\\gamma_n(\\lambda^2 I)$, then Lemma 3.3—and with it the regret theorems that rely on Lemma 3.1—fails.","supporting_citations":[{"cited_title":"Gaussian process optimization in the bandit setting: No regret and experimental design","cited_arxiv_id":null,"evidence_quote":"Supplies the information-gain summation bound and the GP bandit setup that the proof of Lemma 3.1 invokes."},{"cited_title":"G aussian process bandit optimization with few batches","cited_arxiv_id":null,"evidence_quote":"Establishes the phased-elimination analysis and near-optimal baseline that Sections 4 and 5 refine."},{"cited_title":"Lower bounds on regret for noisy G aussian process bandit optimization","cited_arxiv_id":null,"evidence_quote":"Provides the noisy-regret lower bounds that certify RKHS-norm optimality and underpin the Section 6 lower bounds."},{"cited_title":"Convergence rates of efficient global optimization algorithms","cited_arxiv_id":null,"evidence_quote":"Supplies noiseless simple-regret and expected-regret lower bounds used in the noiseless and non-stationary comparisons."},{"cited_title":"Open problem: R egret bounds for noise-free kernel-based bandits","cited_arxiv_id":null,"evidence_quote":"States the conjectured noiseless cumulative-regret lower bound that Theorem 4.1 matches."}],"review_version":1}