{"id":"9646aaf8-3075-40f9-aa5c-d415f437189a","arxiv_id":"2506.10091","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A unified algorithm class, Generic-GP, uses scalar exploration distributions to interpolate between UCB and randomized exploration, achieving \\tilde O(\\gamma_T\\sqrt T) regret in kernelized bandits.","lead":"This paper introduces Generic-GP, a family of kernelized bandit algorithms that add a scalar random perturbation, drawn from an 'exploration distribution', to the usual confidence bound before picking an arm. The framework includes UCB as a special case, obtains matching worst-case regret for several randomized variants, and reports lower empirical regret on benchmark functions.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof of Theorem 2 drops the good-event indicator in the two randomized terms of the regret decomposition; inequality (17) requires E[(f^*(x^*) - \\hat f_{t-1}(X_t)) 1{E_{t-1}^c}] >= 0, which is not stated and generally false, leaving the central regret bound unsupported.","rationale":"We agree with the reader's identification. Checking the algebra of (17): the right-hand side minus the left-hand side equals sum_t E[(f^*(x^*) - \\hat f_{t-1}(X_t)) 1{E_{t-1}^c}], so the asserted inequality is exactly the unstated nonnegativity assumption. The paper provides no argument for it, and the failure event is precisely where the noise is large, making overestimation likely; a counterexample is easy to construct. This is not a minor technicality: Theorem 2 is the central result, and Theorems 3-9 all invoke it. Without a bound on the missing term, the claimed \\tilde O(gamma_T sqrt T) regret for Simple-Gaussian and the other instances is unsupported. We also note the displayed bounds in Theorems 4 and 8 seem to have an extra sqrt(gamma_T) relative to their proofs, which would make them superlinear for Matérn kernels; this reinforces the need for a careful revision. We therefore see no reason to change the reader's REJECT verdict.","tokens_in":22568,"tokens_out":14957,"duration_ms":151531,"concrete_test":"Re-derive the regret decomposition in Appendix B without dropping indicators. Specifically, estimate M_T = sum_{t=1}^T E[(f^*(x^*) - \\hat f_{t-1}(X_t)) 1{E_{t-1}^c}]. Use sub-Gaussian tail bounds on the self-normalized martingale to show |M_T| = O(1), or exhibit a concrete kernelized/linear bandit instance (e.g., two arms, Gaussian noise) where Monte Carlo evaluation gives M_T < 0 with |M_T| not tending to 0 as T grows. If no such bound is provided, Theorem 2 remains unproven.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Appendix B, the proof of Theorem 2 decomposes regret by conditioning on the 'good' event E_{t-1} (the self-normalized martingale bound holding). Inequality (17) then bounds the conditioned term by three contributions: I3 keeps the indicator, but I2 and I1 drop it. Algebraically, (17) holds only if sum_t E[(f^*(x^*) - \\hat f_{t-1}(X_t)) 1{E_{t-1}^c}] >= 0. This condition is neither stated nor proved. On E_{t-1}^c the martingale norm exceeds the threshold, so \\hat f_{t-1}(X_t) can overestimate f^*(x^*); the product is then negative. The event E_{t-1}^c is correlated with large noise excursions, so the expectation need not be nonnegative, and in general it is not. Because Lemmas 2 and 3 bound the unconditional expectations E[\\tilde f_t - \\hat f_{t-1}] and E[f^*(x^*) - \\tilde f_t], they do not control the terms that actually appear in the decomposition. Thus Theorem 2's regret bound is not established. A secondary issue: the displayed bounds in Theorems 4 and 8 contain an extra sqrt(gamma_T) factor relative to their proofs via Theorem 2; for Matérn kernels these statements would be superlinear, suggesting typos that need correction.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces 'exploration distributions' for kernelized bandits. Algorithm 1 (Generic-GP) draws a scalar w_t from a possibly history-dependent distribution, plays the maximizer of \\tilde f_t = \\hat f_{t-1} + w_t g_{t-1}, where g_{t-1} is a GP-UCB-style confidence bonus. Theorem 2 claims a regret bound O((C2,T+C3,T)\\sqrt{T}\\gamma_T(\\sqrt{R^2\\gamma_T}+D)+\\dots), with C2,T,C3,T defined by moments of the exploration distributions, and the paper derives Simple-UCB, Simple-Bernoulli, Simple-Gaussian, and Simple-Categorical instances claimed to achieve \\tilde O(\\gamma_T\\sqrt{T}). Experiments compare these to IGP-UCB and GP-TS on synthetic benchmarks and a Perovskite dataset.","tokens_in":22875,"tokens_out":17122,"duration_ms":179824,"significance":"The proposed framework is conceptually attractive: it unifies deterministic UCB-style and randomized exploration in a single analysis, and the one-dimensional wildcard w_t is computationally much cheaper than the d-dimensional sampling in GP-TS. If the regret analysis can be made rigorous, the paper would provide a useful design space for kernelized bandits and explain when randomization helps in practice. The paper is generally readable and the empirical section, while small, supports the practical appeal of the simple randomized instances. However, the central proof currently has a serious gap and the displayed rates contain a systematic factor error, so the main theoretical claim is not yet established.","major_comments":[{"comment":"Inequality (17) drops the event indicator 1{E_{t-1}} from the second and third terms of the regret decomposition: the left side contains (f^*(x^*) - f^*(X_t))1{E_{t-1}}, while I2 and I1 are defined as unconditional expectations E[\\tilde f_t(X_t) - \\hat f_{t-1}(X_t)] and E[f^*(x^*) - \\tilde f_t(X_t)]. This step is valid only if E[(\\tilde f_t(X_t)-\\hat f_{t-1}(X_t))1{E_{t-1}^c}] + E[(f^*(x^*)-\\tilde f_t(X_t))1{E_{t-1}^c}] >= 0. No such condition is stated or proved; on E_{t-1}^c the self-normalized noise can be large, so \\hat f_{t-1} may overestimate f^*, and w_t can be negative, making the second expectation generally negative. Since Lemmas 2 and 3 bound only the unconditional expectations, they do not control the terms that actually appear in the decomposition. Theorem 2's regret bound therefore is not established by the given proof.","section":"Appendix B, Eq. (17)"},{"comment":"The displayed regret bounds contain an extra factor of \\sqrt{\\gamma_T}. For example, Theorem 2 states O((C2,T+C3,T)\\sqrt{T}\\gamma_T(\\sqrt{R^2\\gamma_T}+D)+\\dots), which is O(\\sqrt{T}\\gamma_T^{3/2}) when C2,T,C3,T=O(1), whereas the lemmas in Appendix B (e.g., Lemmas 1-3) and the abstract's claimed \\tilde O(\\gamma_T\\sqrt{T}) correspond to \\sqrt{T\\gamma_T}(\\sqrt{R^2\\gamma_T}+D)=O(\\sqrt{T}\\gamma_T). The same typo appears in Theorems 4, 6, 7, 8, and 9. As printed, the Matérn-kernel rates are superlinear, so the statements need to be corrected throughout.","section":"Theorems 2, 4, 6-9"}],"minor_comments":[{"comment":"The quantities C1,t, C2,T, and C3,T are written as deterministic, but P_{w,t} is allowed to depend on F_{t-1}; please clarify in what sense Theorem 2 holds when the exploration distributions are data-dependent, and whether the probability in (6) is conditional or unconditional.","section":"Section 4.1"},{"comment":"The sequence '(X1, Y1), (X1, Y2), . . . , (XT , YT )' appears to be a typo for '(X1,Y1),(X2,Y2),...,(XT,YT)'.","section":"Section 1"},{"comment":"There are several typos and formatting issues, including 'exmple' in Section 2, 'cane be viewed as an istance' in Section 4.3, and 'Holder T able' in Figure 1.","section":"Throughout"},{"comment":"The experiments report 25 random-seed runs but show no error bars or confidence bands; please add them or explain their omission.","section":"Figure 1"},{"comment":"Fact 2 is placed in Appendix A but is used in the main text proof of Theorem 8; consider moving it to the main text or referencing it at first use.","section":"Proof of Theorem 8"},{"comment":"The random subset [B] is used before it is defined; please specify that the mixture indicator is drawn independently in each round.","section":"Theorem 5"}],"recommendation":"major_revision","confidential_remarks":"The novelty is modest but acceptable for a specialized venue; the main blocker is the proof gap in Theorem 2. I recommend a major revision rather than a reject because the claimed rates are plausible and consistent with the lemmas once the factor typo is fixed, but the authors need to rework the conditioning argument and re-check all theorem statements. If the proof cannot be repaired, the paper should not be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe exploration-distribution idea is the real thing, and Simple-Bernoulli is the kind of simple algorithm that ought to be in the toolkit. But the paper's main theorem is not proven. Inequality (17) in Appendix B drops the good-event indicator on the two randomized terms, replacing E[(f* - \\tilde f_t)1_{E_{t-1}}] and E[(\\tilde f_t - \\hat f_{t-1})1_{E_{t-1}}] with unconditional expectations. That replacement needs the failure-event terms to be nonnegative, which is neither stated nor true in general: on E_{t-1}^c the noise is large, so \\hat f can overshoot f*, and w_t can be negative. The lemmas that follow only control the unconditional expectations, so the central bound in Theorem 2 is unsupported. This is load-bearing; every subsequent algorithm inherits it.\n\nThe paper does real work before that point. Viewing UCB and randomized schemes as instances of a single scalar exploration distribution is a clean unification, and the C2,T/C3,T accounting is a nice way to separate over- and under-exploration. Simple-Gaussian and Simple-Bernoulli are natural, easy-to-implement, and the experiments (though lacking error bars) suggest they are competitive. The linear lower bound in Theorem 3 is a genuine extra.\n\nTwo more soft spots, one minor and one cosmetic. The statements of Theorems 4 and 8 have an extra sqrt(γ_T) factor relative to what the proof via Theorem 2 would yield; for Matérn kernels that makes the stated bounds superlinear and contradicts the abstract. That is likely a typo, but it needs correction. And the figures report single runs without error bars, which undercuts the practical claims.\n\nWho this is for: kernelized bandit researchers interested in randomized exploration. The framework is worth engaging with, and the proof gap is an instructive place to look. I'd send it to review rather than desk-reject, because the idea is good and the flaw may be repairable — but I'd tell the editor that acceptance requires a correct proof of Theorem 2 and fixed statements.\n\nBest","headline":"The exploration-distribution framework is genuinely new and Simple-Bernoulli is a nice algorithm, but the central regret bound rests on an unjustified indicator-drop in inequality (17), so the main theorem is unsupported.","tokens_in":23429,"tokens_out":6103,"would_cite":false,"duration_ms":66083,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper reduces randomized exploration in kernelized bandits to choosing a one-dimensional \"exploration distribution\" per round, and shows that simple choices match the best known UCB and Thompson Sampling regret bounds of…","keywords":["kernelized bandits","Gaussian processes","regret bounds","Thompson Sampling","exploration distributions","randomized exploration","Reproducing Kernel Hilbert Space","upper confidence bound"],"falsifier":"A reader could check inequality (17) directly: construct a two-arm kernelized instance, run Generic-GP with standard Gaussian exploration, and compute $\\mathbb{E}[(f^*(x^*)-f^*(X_t))\\mathbf{1}_{E_{t-1}^c}]$ on the rounds where the martingale confidence event fails. If this quantity is negative and large enough to break the $O(1)$ allowance used in the proof, the claimed regret bound does not follow from the given argument.","tokens_in":22334,"feed_emoji":"🎲","tokens_out":7959,"duration_ms":80354,"temperature":0.7,"pith_summary":"This paper proposes a class of kernelized bandit algorithms, Generic-GP (GP-Generic), whose only tunable ingredient is a one-dimensional \"exploration distribution\" selected each round. It tries to prove that any distribution with a fixed positive probability of being at least $1$ and controlled growth of $\\max|w_t|$ yields sublinear regret, and that simple choices---a point mass at $1$, a Bernoulli variable, or a standard Gaussian---give the same $\\tilde{O}(\\gamma_T\\sqrt{T})$ regret as the best UCB and Thompson Sampling methods. The analysis unifies deterministic UCB and randomized Thompson Sampling: both are instances of adding a scalar weight times an uncertainty function to the kernel ridge estimate. If the proof is right, randomized exploration carries no theoretical price, and the paper's experiments indicate it often carries a practical benefit.","feed_headline":"Randomized kernel bandits match UCB regret with one scalar draw","feed_subtitle":"A single random scalar per round reproduces UCB-style guarantees and often improves practical regret.","key_machinery":"The central object is the exploration distribution: a distribution $P_{w,t}$ over the reals, chosen perhaps using past data, from which an independent scalar $w_t$ is drawn. It must satisfy $P(w_t \\ge 1)=C_{1,t}\\neq 0$, with $C_{2,t}=\\mathbb{E}[\\max_{s\\le t}|w_s|]$ and $C_{3,t}=\\mathbb{E}[\\max_{s\\le t}|w_s|/C_{1,s}]+\\max_{s\\le t}\\mathbb{E}[|w_s|/C_{1,s}]$ under control. The scalar multiplies the uncertainty function $g_{t-1}(x)=(\\sqrt{2R^2\\log(2\\sqrt{\\det V_{t-1}})}+D)\\lVert V_{t-1}^{-1/2}K(\\cdot,x)\\rVert$, and the algorithm plays the maximizer of the resulting randomized function. The machinery localizes the whole exploration-exploitation tradeoff in one dimension: the regret theorem depends on the chosen distributions only through $C_{2,T}$ and $C_{3,T}$. The proof of optimism uses the constant-probability event $\\{w_t\\ge 1\\}$ together with a ghost-sample argument (an independent copy of the random weight, Lemma 4) to bound the gap between the optimum and the expected randomized score.","core_discovery":"The central discovery is that exploration in a kernelized bandit can be reduced to an independent scalar $w_t$ drawn from a data-dependent distribution $P_{w,t}$. Algorithm 1 plays the maximizer of $\\hat{f}_{t-1} + w_t g_{t-1}$, where $\\hat{f}_{t-1}$ is a kernel ridge estimate and $g_{t-1}$ is an uncertainty function derived from a vector martingale confidence bound taken with constant failure probability $1/2$; the constant failure probability is what lets the random weight do extra exploration. Theorem 2 bounds the regret by $O\\big((C_{2,T}+C_{3,T})\\sqrt{T\\gamma_T}(\\sqrt{R^2\\gamma_T}+D)+(\\sqrt{R^2\\gamma_T}+R^2\\ln(TD)+D)\\sqrt{T\\gamma_T}\\big)$, with $C_{2,T}$ and $C_{3,T}$ defined from the exploration distributions. For standard Gaussian, Bernoulli, categorical, or degenerate-at-1 weights, those constants are $O(1)$, so the theorems for Simple-Gaussian and Simple-UCB deliver $\\tilde{O}(\\gamma_T\\sqrt{T})$ regret, matching the best known UCB bounds and improving on the $\\tilde{O}(\\gamma_T\\sqrt{dT})$ bound for the d-dimensional Gaussian Thompson Sampling algorithm.","pith_inferences":["Editorial inference: the proof gap around inequality (17) may be repairable by conditioning the analysis on the good event and bounding the bad event with an explicit high-probability term; until then, the theorem is a conjecture at the proof level rather than a fully established bound.","Editorial inference: the scalar-weight construction suggests a natural recipe for other exploration strategies, such as heavy-tailed weights or data-dependent adaptive scales, as long as the two constants remain $O(1)$.","Editorial inference: the same one-dimensional randomization idea could transfer to contextual bandits or reinforcement learning where sampling a full d-dimensional posterior is expensive; the paper does not claim this."],"forward_implications":["If Theorem 2 is correct, Simple-Gaussian attains $\\tilde{O}(\\gamma_T\\sqrt{T})$ regret with a one-dimensional Gaussian draw, saving a $\\sqrt{d}$ factor over the analysis of the d-dimensional Gaussian Thompson Sampling algorithm.","Simple-Bernoulli gives a practical exploration schedule: choosing a small $p_t$ once the learner is confident stays inside the $\\tilde{O}(\\gamma_T\\sqrt{T}/\\min_t p_t)$ bound, which explains the method's strong empirical regret.","UCB policies appear as the degenerate case $w_t\\equiv 1$, so the generic theorem covers deterministic confidence-bound algorithms as a special case.","For linear kernels, Theorem 3 shows the generic upper bound is within log factors of an $\\Omega(\\sqrt{dT}(\\sqrt{d}+D))$ lower bound for a constructed instance.","The conditions on $C_{2,T}$ and $C_{3,T}$ are modular: any new exploration distribution satisfying them automatically inherits a $\\tilde{O}(\\gamma_T\\sqrt{T})$ regret bound."],"supporting_citations":[{"why":"Supplies the self-normalized vector martingale concentration theorem and the information-gain sum bound used throughout the proof of Theorem 2.","marker":"[3]"},{"why":"Provides the IGP-UCB and GP-TS baselines whose $\\tilde{O}(\\gamma_T\\sqrt{T})$ and $\\tilde{O}(\\gamma_T\\sqrt{dT})$ bounds the paper compares against.","marker":"[2]"},{"why":"Supplies the linear bandit setting and the $d\\log T$ information gain used in Theorem 3's near-matching upper and lower bounds.","marker":"[12]"},{"why":"Provides the ghost-sample inequality (Lemma 4) that converts the constant-probability optimism event into a bound on the exploitation gap.","marker":"[33]"},{"why":"Shows a randomized algorithm (REDS) achieving order-optimal regret, motivating the question of whether data-dependent randomization costs anything.","marker":"[15]"},{"why":"Establishes the $\\Omega(\\sqrt{T\\gamma_T})$ regret lower bound that the paper's $\\tilde{O}(\\gamma_T\\sqrt{T})$ upper bounds approach.","marker":"[14]"}],"fun_headline_variants":["One random scalar per turn matches UCB regret in kernel bandits","Kernel bandit exploration reduced to a single random draw","Random weight matches UCB guarantees, improves kernel bandit regret","Exploration as a scalar draw: kernel bandits hit UCB regret","Data-dependent one-draw exploration ties UCB in kernel bandits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof of Theorem 2 assumes, without proving it, that the rare rounds in which the statistical error exceeds its confidence interval can do no harm to the regret; that is, it drops the failure-event indicator in inequality (17) and takes the expectation over that event to be non-negative.","fun_headline_variants_meta":{"raw":{"variants":["One random scalar per turn matches UCB regret in kernel bandits","Kernel bandit exploration reduced to a single random draw","Random weight matches UCB guarantees, improves kernel bandit regret","Exploration as a scalar draw: kernel bandits hit UCB regret","Data-dependent one-draw exploration ties UCB in kernel bandits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000164,"raw_usage":{"total_tokens":1254,"prompt_tokens":959,"completion_tokens":295,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":575,"completion_tokens_details":{"reasoning_tokens":206}},"tokens_in":575,"tokens_out":295,"duration_ms":3453,"temperature":1.0,"reasoning_tokens":206,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T04:37:19.907442+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A reader could check inequality (17) directly: construct a two-arm kernelized instance, run Generic-GP with standard Gaussian exploration, and compute $\\mathbb{E}[(f^*(x^*)-f^*(X_t))\\mathbf{1}_{E_{t-1}^c}]$ on the rounds where the martingale confidence event fails. If this quantity is negative and large enough to break the $O(1)$ allowance used in the proof, the claimed regret bound does not follow from the given argument.","supporting_citations":[{"cited_title":"On the sublinear regret of GP-UCB","cited_arxiv_id":null,"evidence_quote":"Supplies the self-normalized vector martingale concentration theorem and the information-gain sum bound used throughout the proof of Theorem 2."},{"cited_title":"On kernelized multi-armed bandits","cited_arxiv_id":null,"evidence_quote":"Provides the IGP-UCB and GP-TS baselines whose $\\tilde{O}(\\gamma_T\\sqrt{T})$ and $\\tilde{O}(\\gamma_T\\sqrt{dT})$ bounds the paper compares against."},{"cited_title":"Improved algorithms for linear stochastic bandits","cited_arxiv_id":null,"evidence_quote":"Supplies the linear bandit setting and the $d\\log T$ information gain used in Theorem 3's near-matching upper and lower bounds."},{"cited_title":"Worst-case regret bounds for exploration via randomized value functions","cited_arxiv_id":null,"evidence_quote":"Provides the ghost-sample inequality (Lemma 4) that converts the constant-probability optimism event into a bound on the exploitation gap."},{"cited_title":"Random exploration in Bayesian optimization: Order-optimal regret and computational efficiency","cited_arxiv_id":null,"evidence_quote":"Shows a randomized algorithm (REDS) achieving order-optimal regret, motivating the question of whether data-dependent randomization costs anything."},{"cited_title":"Lower bounds on regret for noisy gaus- sian process bandit optimization","cited_arxiv_id":null,"evidence_quote":"Establishes the $\\Omega(\\sqrt{T\\gamma_T})$ regret lower bound that the paper's $\\tilde{O}(\\gamma_T\\sqrt{T})$ upper bounds approach."}],"review_version":1}