{"id":"4f52f9b2-e825-4e86-b719-472e5ab13955","arxiv_id":"2412.18789","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Under Gaussian noise, GP prediction error is bounded by a constant multiple of the posterior standard deviation, yielding improved cumulative regret rates for GP-UCB and GP-TS in the frequentist setting.","lead":"This paper proves a pointwise prediction-error bound for Gaussian-process surrogates in the frequentist setting with Gaussian noise, replacing a growing confidence parameter with a constant. The bound improves the theoretical cumulative regret guarantees for the GP-UCB and Thompson sampling algorithms, bringing them closer to known lower bounds.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"GP-UCB results appear sound, but the GP-TS proof relies on a false Gaussian tail bound (Lemma 4.11) and an omitted sqrt(T) in (4.38), so the improved TS rate is not rigorously established as written.","rationale":"The GP-UCB proof is internally sound: the pointwise bound follows from the RKHS projection inequality in Lemma 3.2 plus a Gaussian tail, and the union bound over t gives beta_T = O(sqrt(B^2 + d log T)), leading to the stated O(sqrt(T beta_T gamma_T)) regret. I checked Lemma 3.2 by writing the residual as an RKHS inner product and applying Cauchy-Schwarz; the squared norm of the residual is sigma_t^2(x) - sigma^2 ||(K + sigma^2 I)^{-1} k_t(x)||^2 <= sigma_t^2(x), so the borrowed lemma is correct. The real issue is in the Thompson sampling section: Lemma 4.11 is a false lower bound on Gaussian tails, and (4.38) drops a sqrt(T) factor. These are not mere notation slips: the false Lemma 4.11 is used to establish the constant sampling probability p, and the missing sqrt(T) is an algebraic inequality error. The TS theorem may still be true after repair, but as written the proof is incomplete. This does not change the reader's CONDITIONAL verdict, but it shifts the stated weakest link from Lemma 3.2 to the TS analysis.","tokens_in":17641,"tokens_out":27238,"duration_ms":219458,"concrete_test":"Evaluate the Gaussian tail inequality in Lemma 4.11 at w = 1 and w = 3. Since it fails, re-derive Lemma 4.12 using the exact Mills-ratio tail for w = 1 (P(Z > 1) ≈ 0.1587) and redo the last line of (4.38) with sqrt(sum_t zeta_t) <= sqrt(T zeta_T). If the corrected super-martingale bound still yields R_T = O(zeta_T^{1/2} sqrt(T gamma_T)) up to constants, then Theorem 4.19 is repairable; if not, the GP-TS rate must be weakened.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 4.11 states that for X ~ N(mu, sigma), P{(X-mu)/sigma > w} >= e^{-w^2/4}/(sqrt(pi) w) for all w > 0. This is false: at w = 1, the right-hand side is e^{-1/4}/sqrt(pi) ≈ 0.44, while the true standard normal tail is ≈ 0.159; at w = 3, the right-hand side is ≈ 0.0198, while the true tail is ≈ 0.00135. Lemma 4.12 invokes this false bound with w = 1 to conclude P_t{f_t(x) > f(x)} >= 1/(4 e sqrt(pi)) ≈ 0.052. The conclusion itself happens to be true because the exact Gaussian tail at 1 is ≈ 0.159 > 0.052, but the proof as written rests on an invalid inequality. Separately, the final line of (4.38) bounds sqrt(2 log(2/delta) * sum_t (4B+11)^2 zeta_t / p^2) by (4B+11) zeta_T^{1/2}/p * sqrt(2 log(2/delta)), omitting the factor sqrt(T) from sqrt(sum_{t=1}^T zeta_t) <= sqrt(T zeta_T). This makes the displayed inequality algebraically incorrect. Both defects affect the proof of Theorem 4.19, so the GP-TS regret rates are not rigorously proven as written. The GP-UCB argument (Theorem 4.4) does not use these lemmas; the pointwise bound Theorem 3.3 and the borrowed Lemma 3.2 are consistent with standard RKHS projection arguments and do not appear to be the weak point.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies cumulative regret of GP-UCB and GP-TS in the frequentist setting under i.i.d. Gaussian observation noise. Its main technical step is a pointwise prediction-error bound |f(x)-μ_t(x)| ≤ β^{1/2}σ_t(x) with a confidence-dependent but time-independent β, proved via a spectral argument bounding the noise-induced posterior mean by σ_t(x). From this it derives a GP-UCB regret bound O(√(Tβ_Tγ_T)) and claims GP-TS rates O(d log T √(Tγ_T)), specializing to improved squared-exponential and Matérn rates that are within logarithmic factors of existing lower bounds. The GP-UCB argument appears sound; the GP-TS proof contains several invalid steps that must be repaired.","tokens_in":18026,"tokens_out":21529,"duration_ms":173070,"significance":"The constant-β pointwise bound is the paper's core conceptual contribution: it removes the t-dependent β_t from the frequentist UCB analysis and closes the gap with the Bayesian setting. The spectral proof of ‖(K_t+σ²I)^{-1}k_t‖ ≤ σ_t(x)/σ is clean, the union-bound extension is standard, and the GP-UCB regret proof is transparent and appears correct. The claimed Thompson-sampling improvements are also of interest, but they are not established as written because the TS section relies on a false Gaussian tail bound, an incorrect summation step, and an inconsistent supermartingale definition. These defects are localized and likely repairable without changing the stated rates, but the proof must be corrected before the TS results can be accepted.","major_comments":[{"comment":"Lemma 4.11 is false. For w=1, the claimed lower bound e^{-1/4}/√π ≈ 0.44 exceeds the true standard-normal tail Φ(-1) ≈ 0.159, and for w=0.5 the right-hand side exceeds 1. Since Lemma 4.12 applies this bound with w=1 to obtain p = 1/(4e√π), the proof of Eq. (4.16) is invalid. The conclusion P_t{f_t(x) > f(x)} ≥ p can be recovered directly from Φ(-1) > p, but the false lemma must be removed or replaced. Note also that the normalization in Eq. (4.17) divides by ν_t σ_{t-1}(x), whereas f_t(x) has standard deviation ν_t^{1/2}σ_{t-1}(x); this denominator must be fixed before Lemma 4.11 could be applied.","section":"§4.1, Lemma 4.11"},{"comment":"The inequality bounding the martingale term is algebraically wrong: √(Σ_{t=1}^T ζ_t) is bounded by √(T ζ_T), not by √(ζ_T). Thus the displayed simplification in Eq. (4.38) is missing a factor √T, and the corresponding term in Eq. (4.35) is also inconsistent because it writes ζ_T where the proof yields ζ_T^{1/2}. For the SE and Matérn rates in Theorem 4.19 this omission does not change the final exponent, but Lemma 4.18 and Eq. (4.38) must be corrected before the TS regret proof is valid.","section":"§4.1, Eq. (4.38)"},{"comment":"The definition of X_t in Eq. (4.31) and the conditional expectation in Eq. (4.34) appear to have a sign error: X_t is written as \\bar r_t - 11ζ_t^{1/2}/p · σ_{t-1}(x_t) - 2B + 1/t², but Lemma 4.14 gives E[\\bar r_t] ≤ 11ζ_t^{1/2}/p · E[σ_{t-1}(x_t)] + 2B + 1/t². For the supermartingale inequality E_t[X_t] ≤ 0 to hold, the last two terms must be -(2B + 1/t²). With the displayed definition, on E_f(t) one only obtains E_t[X_t] ≤ 2/t², so Lemma 4.17 is not justified as written. The later bound in Eq. (4.36) treats 2B+1/t² as a positive summand, which confirms the intended correction, but the displayed definitions need to be fixed.","section":"§4.1, Eqs. (4.31)-(4.34)"}],"minor_comments":[{"comment":"The notation α_t^{1/2} is defined as 2 log(|C|π_t/δ), but the subsequent union-bound algebra |C|∑e^{-α_t/2}=δ requires α_t = 2 log(|C|π_t/δ), i.e., α_t^{1/2} = √(2 log(|C|π_t/δ)). The statement's β_t definition is correct, so this is a notational slip in the proof.","section":"§3.2, proof of Lemma 3.6"},{"comment":"There are several typos: 'CP-UCB' in the description of Algorithm 2.2 should be 'GP-UCB', and words such as 'acqusition', 'spetral', and 'genearlity' should be corrected.","section":"§2.3 and throughout"},{"comment":"The proof's last inequality is written as '≥ 1/(4√π e)' while the stated p is 1/(4e√π); after fixing Lemma 4.11 the constant should be rederived consistently.","section":"§4.1, Lemma 4.12"},{"comment":"In Eq. (4.42), the summation ∑_{t−1} σ_{t-1}(x_t) should read ∑_{t=1}^T σ_{t-1}(x_t).","section":"§4.1, proof of Theorem 4.19"}],"recommendation":"major_revision","confidential_remarks":"The GP-TS section is the weak point of the manuscript: the errors are concentrated there, they are numerous, and although they appear repairable without changing the stated rates, the proof as written is not valid. The GP-UCB contribution is solid, and the pointwise bound with constant β is a genuine improvement. I would ask the authors to repair the TS proofs carefully and to re-verify all constants in Eqs. (4.31)-(4.38) before resubmission."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: the GP-UCB contribution is solid and the improved rates are credible; the GP-TS section is not rigorously established as written, because the proof leans on a false Gaussian tail bound and an algebraic slip.\n\nWhat is new: the paper observes that under Gaussian noise, the posterior mean's noise-induced term is itself Gaussian, so its tail can be controlled with a constant beta rather than a growing beta_t. Theorem 3.3 gives |f(x)-mu_t(x)| <= beta^{1/2} sigma_t(x) with beta depending only on the confidence delta. The spectral argument showing ||h_t|| <= sigma_t/sigma is clean, and the discrete-set extension is standard. Given this pointwise bound, the GP-UCB regret bound O(sqrt(T) log^{(d+2)/2} T) for SE kernels and the corresponding Matérn rate follow by a standard argument. I checked the union-bound step; it holds. This closes part of the gap to the Scarlett lower bounds and is worth having.\n\nWhere it falls down: the GP-TS proof has two concrete defects. Lemma 4.11 claims P{N(0,1) > w} >= e^{-w^2/4}/(sqrt(pi) w) for all w>0, which is false (at w=1 the RHS is about 0.44, true tail 0.159). Lemma 4.12 invokes this at w=1; the conclusion is true but the proof isn't. Also in (4.38), the bound sqrt(sum_t zeta_t) is replaced by sqrt(T zeta_T), introducing a missing sqrt(T). Both affect Theorem 4.19. So the TS rates are not proven as written. A careful revision of that section could likely fix them, but right now the claim is too strong. The paper also leans on Lemma 3.2 from prior work, which is fine, but the constant beta depends on knowing sigma and sigma_epsilon.\n\nThe paper is for BO theorists. The UCB half deserves a serious referee; the TS half needs work. I'd send it to review but ask the authors to revise the TS section substantially.","headline":"The GP-UCB half of this paper is a real contribution; the Thompson sampling half is not ready as written because the proof relies on a false tail bound and an algebra slip.","tokens_in":18534,"tokens_out":2854,"would_cite":true,"duration_ms":22928,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"With Gaussian observation noise, a fixed confidence multiplier bounds GP prediction error at every point and time, improving cumulative regret rates for GP-UCB and GP-TS to near the known lower bounds.","keywords":["Bayesian optimization","Gaussian process","upper confidence bound","Thompson sampling","cumulative regret","prediction error bound","frequentist setting","Gaussian noise"],"falsifier":"Simulate the theorem directly: fix a kernel with k(x,x)=1, a function f with RKHS norm B, and Gaussian noise of variance $sigma_eps^{2}$; repeat many draws of the noise, compute mu_t(x) and sigma_t(x) at fixed x and t, and check whether the empirical 1-delta quantile of |f(x)-mu_t(x)|/sigma_t(x) exceeds B+(sigma_eps/$\\sigma$) $\\sqrt$(2 log(1/delta)). Any kernel-point choice where the bound is violated with probability greater than delta would refute Theorem 3.3; a cheaper check is to test whether Lemma 3.2 can be replaced by a t-dependent factor.","tokens_in":17474,"feed_emoji":"📉","tokens_out":7524,"duration_ms":66561,"temperature":0.7,"pith_summary":"This paper seeks to close the gap between Bayesian and frequentist regret analyses of Gaussian-process bandit algorithms. The authors prove a pointwise prediction-error bound under the frequentist assumption that the objective lies in an RKHS, with i.i.d. Gaussian observation noise: at any fixed query point and time, |f(x)-mu_t(x)| <= $beta^{{1/2}}$ sigma_t(x) with a constant $\\beta$ that depends only on the confidence level, not on t. In earlier frequentist analyses the confidence multiplier had to grow with t, which inflated regret. From the constant-$\\beta$ bound they derive cumulative regret rates for GP-UCB of O($\\sqrt$(T) $log^{{(d+2)/2}}$ T) for squared-exponential kernels and O($T^{{(nu+d)/(2nu+d)}}$ $log^{{(4nu+d)/(4nu+2d)}}$ T) for Matérn kernels, with GP-TS rates a half-log factor worse. A sympathetic reader should care because these are the closest upper bounds to the known lower bounds and they make the frequentist and Bayesian settings agree in order.","feed_headline":"Constant beta shrinks GP-UCB regret to near lower bounds","feed_subtitle":"A pointwise error bound with a time-independent confidence parameter closes the frequentist-Bayesian gap and sharpens GP-TS too.","key_machinery":"The argument's central object is the linear-smoother representation of the posterior mean, mu_t(x) = h_t(x)^T y_{1:t} with h_t(x) = (K_t + $sigma^{2}$ I)^{-1} k_t(x). The paper proves the weight vector satisfies ||h_t(x)|| <= sigma_t(x)/$\\sigma$ by a positive-semidefinite Schur-complement argument. Since the noise-induced part of the prediction error, e_t(x) = h_t(x)^T epsilon_{1:t}, is a Gaussian of variance ||h_t(x)||^2 $sigma_eps^{2}$ <= (sigma_eps/$\\sigma$)^2 sigma_t(x)^2, a standard Gaussian tail bound with a confidence-dependent threshold gives the constant-$\\beta$ pointwise error bound. The second load-bearing component is Lemma 3.2 (borrowed from references [9,18,20]), which bounds the noiseless part by B sigma_t(x).","core_discovery":"Under Assumption 2.2 (f in the RKHS with norm at most B) and Assumption 2.6 (i.i.d. Gaussian noise of variance $sigma_eps^{2}$), the paper proves that for any delta in (0,1), choosing $beta^{{1/2}}$ = B + (sigma_eps/$\\sigma$) $\\sqrt$(2 log(1/delta)) gives P(|f(x)-mu_t(x)| <= $beta^{{1/2}}$ sigma_t(x)) >= 1-delta at every fixed x and t. The novelty is that $\\beta$ is constant in t, so the prediction-error bound does not deteriorate as sampling proceeds. Lifting this pointwise bound to a discrete grid via union bounds yields GP-UCB cumulative regret R_T <= (C_1 T beta_T gamma_T)^{1/2} + 2 with probability at least 1-delta, and the corresponding GP-TS bound, which when instantiated with the maximum information gain gamma_T for SE and Matérn kernels gives the improved rates in Table 1.","pith_inferences":["Editorial inference: the same constant-beta pointwise bound should yield a simple-regret bound for the best point found at essentially the same rate, since the paper's union bound controls f(x*) - mu_{t-1}([x*]_t) at the optimum.","Editorial inference: the improvement over prior sub-Gaussian analyses is exactly the d log(T) versus gamma_T gap, so the practical gain is largest for smooth kernels in low dimension; in high dimension the log-factor savings may be negligible compared with the leading term.","Editorial inference: if sigma_eps is unknown, a practitioner can estimate it from the data, but the fixed-beta guarantee requires a valid upper bound on sigma_eps; the paper does not develop an adaptive choice, so an empirical plug-in would need its own confidence analysis."],"forward_implications":["For squared-exponential kernels, GP-UCB reduces its frequentist cumulative regret from O(sqrt(T) log^{(d+5)/2} T) to O(sqrt(T) log^{(d+2)/2} T).","For Matérn kernels, GP-UCB regret becomes O(T^{(nu+d)/(2nu+d)} log^{(4nu+d)/(4nu+2d)} T), compared with O(T^{(nu+d)/(2nu+d)} log^{(10nu+4d)/(4nu+2d)} T) in the prior state of the art.","GP-TS improves to O(sqrt(T) log^{(d+3)/2} T) for squared-exponential kernels and O(T^{(nu+d)/(2nu+d)} log^{(3nu+d)/(2nu+d)} T) for Matérn kernels, within a half-log factor of GP-UCB.","The frequentist GP-UCB regret rates now match, in order, the Bayesian-setting rates, closing that long-standing gap.","The constant-beta pointwise bound applies to any acquisition function whose analysis needs a finite confidence radius, including expected improvement under noise."],"supporting_citations":[{"why":"Supplies the GP-UCB regret framework, the maximum-information-gain lemmas, and the Bayesian pointwise prediction bound this paper transfers to the frequentist setting.","marker":"[8]"},{"why":"Introduces the sub-Gaussian-noise analysis that this paper improves on and is one of the sources cited for Lemma 3.2.","marker":"[9]"},{"why":"One of the sources for Lemma 3.2, the noiseless posterior-mean error bound that carries the RKHS norm bound B.","marker":"[18]"},{"why":"Another source for Lemma 3.2 and the prior state-of-the-art GP-UCB bound for squared-exponential kernels that the new rate beats.","marker":"[20]"},{"why":"Provides the tighter maximum-information-gain bounds for SE and Matérn kernels used to convert the general regret expression into the stated rates.","marker":"[11]"},{"why":"Establishes the lower bounds in expectation that the paper compares its upper bounds against.","marker":"[17]"}],"fun_headline_variants":["Constant beta tightens Bayesian optimization regret bounds","Gaussian noise analysis yields tighter GP regret bounds","Improved regret bounds for GP-UCB and GP-TS","Pointwise error bound improves GP optimization regret","Constant beta yields near-optimal GP regret"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the function-only part of the prediction error is bounded by B times the posterior standard deviation with one time-independent constant B (a lemma the paper imports rather than proves); if that constant must grow with the number of samples, or if the noise variance is not known well enough to set beta, the regret improvement collapses.","fun_headline_variants_meta":{"raw":{"variants":["Constant beta tightens Bayesian optimization regret bounds","Gaussian noise analysis yields tighter GP regret bounds","Improved regret bounds for GP-UCB and GP-TS","Pointwise error bound improves GP optimization regret","Constant beta yields near-optimal GP regret"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000507,"raw_usage":{"total_tokens":2451,"prompt_tokens":907,"completion_tokens":1544,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":523,"completion_tokens_details":{"reasoning_tokens":1473}},"tokens_in":523,"tokens_out":1544,"duration_ms":10578,"temperature":1.0,"reasoning_tokens":1473,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T04:29:15.525591+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate the theorem directly: fix a kernel with k(x,x)=1, a function f with RKHS norm B, and Gaussian noise of variance $sigma_eps^{2}$; repeat many draws of the noise, compute mu_t(x) and sigma_t(x) at fixed x and t, and check whether the empirical 1-delta quantile of |f(x)-mu_t(x)|/sigma_t(x) exceeds B+(sigma_eps/$\\sigma$) $\\sqrt$(2 log(1/delta)). Any kernel-point choice where the bound is violated with probability greater than delta would refute Theorem 3.3; a cheaper check is to test whether Lemma 3.2 can be replaced by a t-dependent factor.","supporting_citations":[{"cited_title":"On kernelized mu lti-armed bandits","cited_arxiv_id":null,"evidence_quote":"Introduces the sub-Gaussian-noise analysis that this paper improves on and is one of the sources cited for Lemma 3.2."},{"cited_title":"Convergence rates of efficient global optimi zation algorithms","cited_arxiv_id":null,"evidence_quote":"One of the sources for Lemma 3.2, the noiseless posterior-mean error bound that carries the RKHS norm bound B."},{"cited_title":"On info rmation gain and regret bounds in gauss- ian process bandits","cited_arxiv_id":null,"evidence_quote":"Provides the tighter maximum-information-gain bounds for SE and Matérn kernels used to convert the general regret expression into the stated rates."},{"cited_title":"Lower bounds on regret for noisy gaussian process bandit optimization","cited_arxiv_id":null,"evidence_quote":"Establishes the lower bounds in expectation that the paper compares its upper bounds against."}],"review_version":1}