Pith. sign in

REVIEW 2 major objections 6 minor 45 references

Efficient kernelized bandit algorithms via exploration distributions

T0 review · 2 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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…

desk verdict 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. read the letter →

arxiv 2506.10091 v1 pith:A4IHL7J3 submitted 2025-06-11 cs.LG

Bingshan Hu , Zheng He , Danica J. Sutherland This is my paper · ORCID
classification cs.LG MSC 68T05
keywords kernelizedbanditsGaussianprocessesregretboundsThompsonSamplingexplorationdistributionsrandomizedReproducingKernelHilbertSpaceupperconfidencebound
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 6 minor

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.

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 (2)
  1. [Appendix B, Eq. (17)] 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.
  2. [Theorems 2, 4, 6-9] 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.
minor comments (6)
  1. [Section 4.1] 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.
  2. [Section 1] The sequence '(X1, Y1), (X1, Y2), . . . , (XT , YT )' appears to be a typo for '(X1,Y1),(X2,Y2),...,(XT,YT)'.
  3. [Throughout] 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.
  4. [Figure 1] The experiments report 25 random-seed runs but show no error bars or confidence bands; please add them or explain their omission.
  5. [Proof of Theorem 8] 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.
  6. [Theorem 5] The random subset [B] is used before it is defined; please specify that the mixture indicator is drawn independently in each round.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the regret bounds are derived from closed-form properties of the exploration distributions, not from fitted parameters or self-citations.

full rationale

The paper's central claim is a generic regret bound (Theorem 2) expressed in terms of C2,T and C3,T, which are defined in equations (6)-(7) as expectations over the chosen exploration distributions. The concrete algorithm results (Theorems 6-9) follow by computing explicit upper bounds on C2,T and C3,T for specific distributions (e.g., Ber(1), Ber(p), N(0,1), categorical), using standard maximal inequalities and Gaussian anti-concentration bounds. These constants are closed-form properties of the distributions and are not fitted to observed rewards, target regret values, or any subset of the data. The analysis is self-contained relative to external, non-self-cited results: the self-normalized martingale concentration bound is cited from Whitehouse et al. [3], and the optimistic-surrogate lemma is inspired by Russo [33]; no load-bearing step reduces to a self-citation. One proof-level concern appears in Appendix B at inequality (17), where the indicator 1{E_{t-1}} is dropped when bounding the I1 and I2 terms; that step is not justified and may be false, but it is a correctness gap rather than circularity, because it does not make an output equal to an input by construction. Accordingly, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The proofs rely on standard RKHS and sub-Gaussian assumptions, plus concentration inequalities from prior work. The exploration distribution is an algorithmic abstraction, not a new physical or mathematical entity. There are no free parameters fitted to data; the quantities C2,T and C3,T are derived from the chosen distribution rather than tuned.

assumptions (6)
  • domain assumption The unknown reward f* lies in an RKHS with kernel bounded by 1 and norm bounded by D.
    Stated in Section 2; this smoothness assumption is standard for kernelized bandits and enables confidence-bound construction.
  • domain assumption Noise epsilon_t is conditionally zero-mean R-sub-Gaussian.
    Equation (3), Section 2; needed for the self-normalized concentration bound.
  • standard math Self-normalized martingale concentration (Theorem 1 from Whitehouse et al. [3]) holds for the adaptively chosen arms.
    Invoked as Theorem 1 in Section 4.2 and used in Lemmas 1 and 5.
  • standard math The maximum information gain gamma_T satisfies log det(V_t) <= 2 gamma_T (Fact 3).
    Used in the Cauchy-Schwarz steps of Lemmas 1-3; standard in kernelized bandits.
  • standard math Sub-Gaussian maximal inequality (Fact 1) and Gaussian concentration/anti-concentration (Fact 2).
    Used to bound C2,T and C3,T for Gaussian exploration distributions.
  • domain assumption The sequence of exploration distributions can depend on past data, but w_1,...,w_t remain independent given the selected distributions.
    Stated in Section 4.1; required for the martingale and optimism arguments.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Efficient kernelized bandit algorithms via exploration distributions." pith.science (2026). https://pith.science/paper/A4IHL7J3

@misc{pith2026250610091,
  author       = {Pith},
  title        = {Pith review of: Efficient kernelized bandit algorithms via exploration distributions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/A4IHL7J3}},
  note         = {Machine review of arXiv:2506.10091}
}
abstract

We consider a kernelized bandit problem with a compact arm set ${X} \subset \mathbb{R}^d $ and a fixed but unknown reward function $f^*$ with a finite norm in some Reproducing Kernel Hilbert Space (RKHS). We propose a class of computationally efficient kernelized bandit algorithms, which we call GP-Generic, based on a novel concept: exploration distributions. This class of algorithms includes Upper Confidence Bound-based approaches as a special case, but also allows for a variety of randomized algorithms. With careful choice of exploration distribution, our proposed generic algorithm realizes a wide range of concrete algorithms that achieve $\tilde{O}(\gamma_T\sqrt{T})$ regret bounds, where $\gamma_T$ characterizes the RKHS complexity. This matches known results for UCB- and Thompson Sampling-based algorithms; we also show that in practice, randomization can yield better practical results.

Figures

Figures reproduced from arXiv: 2506.10091 by the authors.

Figure 1
Figure 1. Regret comparison of different algorithms for synthetic and real-world data [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. For the case where events B∗ t for all t ∈ [βT + 1, T] are true, we lower bound the regret for all the rounds in the blue color; for the case where there exists t ∈ [βT + 1, T] such that B∗ t is false, we lower bound the regret for all the rounds in the pink color. There exists t ∈ [βT + 1, T] such that B∗ t is false. Without loss of generality, let us say t0 is the first round such that B∗ t0 is false, i.e., we hav… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

45 extracted references · 43 canonical work pages

  1. [1]

    Gaussian process optimization in the bandit setting: no regret and experimental design

    Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. “Gaussian process optimization in the bandit setting: no regret and experimental design.”International Conference on Machine Learning. 2010, pp. 1015–1022

    work page 2010

  2. [2]

    On kernelized multi-armed bandits

    Sayak Ray Chowdhury and Aditya Gopalan. “On kernelized multi-armed bandits.”Interna- tional Conference on Machine Learning. PMLR. 2017, pp. 844–853

    work page 2017

  3. [3]

    On the sublinear regret of GP-UCB

    Justin Whitehouse, Aaditya Ramdas, and Steven Z Wu. “On the sublinear regret of GP-UCB.” Advances in Neural Information Processing Systems 36 (2023), pp. 35266–35276

    work page 2023

  4. [4]

    Survey on Applications of Multi-Armed and Contextual Bandits

    Djallel Bouneffouf, Irina Rish, and Charu Aggarwal. “Survey on Applications of Multi-Armed and Contextual Bandits.” 2020 IEEE Congress on Evolutionary Computation (CEC). 2020

    work page 2020

  5. [5]

    Bayesian Optimization

    Roman Garnett. Bayesian Optimization. Cambridge University Press, 2023

    2023

  6. [6]

    Gaussian processes for machine learning

    Matthias Seeger. “Gaussian processes for machine learning.” International journal of neural systems 14.02 (2004), pp. 69–106

    work page 2004

  7. [7]

    Finite-time analysis of the multi-armed bandit problem

    Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. “Finite-time analysis of the multi-armed bandit problem.” Machine learning 47 (2002), pp. 235–256

    work page 2002

  8. [8]

    Near-optimal regret bounds for Thompson Sampling

    Shipra Agrawal and Navin Goyal. Near-optimal regret bounds for Thompson Sampling. http: //www.columbia.edu/~sa3305/papers/j3-corrected.pdf. 2017

    work page 2017

Show all 45 references
  1. [9]

    Thompson Sampling for contextual bandits with linear payoffs

    Shipra Agrawal and Navin Goyal. “Thompson Sampling for contextual bandits with linear payoffs.” International conference on machine learning. PMLR. 2013, pp. 127–135

    2013

  2. [10]

    Contextual bandits with linear payoff functions

    Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. “Contextual bandits with linear payoff functions.” Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics. JMLR Workshop and Conference Proceedings. 2011, pp. 208–214

    2011

  3. [11]

    Finite-time analysis of kernelised contextual bandits

    Michal Valko, Nathan Korda, Rémi Munos, Ilias Flaounas, and Nello Cristianini. “Finite-time analysis of kernelised contextual bandits.” Uncertainty in Artificial Intelligence. 2013

    2013

  4. [12]

    Improved algorithms for linear stochastic bandits

    Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. “Improved algorithms for linear stochastic bandits.” Advances in neural information processing systems 24 (2011)

    2011

  5. [13]

    Lower bounds for time-varying kernelized bandits

    Xu Cai and Jonathan Scarlett. “Lower bounds for time-varying kernelized bandits.”Interna- tional Conference on Artificial Intelligence and Statistics. 2025

    2025

  6. [14]

    Lower bounds on regret for noisy gaus- sian process bandit optimization

    Jonathan Scarlett, Ilija Bogunovic, and V olkan Cevher. “Lower bounds on regret for noisy gaus- sian process bandit optimization.” Conference on Learning Theory. PMLR. 2017, pp. 1723– 1742

    2017

  7. [15]

    Random exploration in Bayesian optimization: Order-optimal regret and computational efficiency

    Sudeep Salgia, Sattar Vakili, and Qing Zhao. “Random exploration in Bayesian optimization: Order-optimal regret and computational efficiency.” International Conference on Machine Learning. PMLR. 2024, pp. 43112–43141

    2024

  8. [16]

    Gaussian process bandit optimization with few batches

    Zihan Li and Jonathan Scarlett. “Gaussian process bandit optimization with few batches.” International Conference on Artificial Intelligence and Statistics. PMLR. 2022, pp. 92–107

    2022

  9. [17]

    UCB revisited: Improved regret bounds for the stochastic multi-armed bandit problem

    Peter Auer and Ronald Ortner. “UCB revisited: Improved regret bounds for the stochastic multi-armed bandit problem.” Periodica Mathematica Hungarica 61.1-2 (2010), pp. 55–65

    2010

  10. [18]

    Using confidence bounds for exploitation-exploration trade-offs

    Peter Auer. “Using confidence bounds for exploitation-exploration trade-offs.” Journal of Machine Learning Research 3.Nov (2002), pp. 397–422

    2002

  11. [19]

    On information gain and regret bounds in gaussian process bandits

    Sattar Vakili, Kia Khezeli, and Victor Picheny. “On information gain and regret bounds in gaussian process bandits.” International Conference on Artificial Intelligence and Statistics. PMLR. 2021, pp. 82–90

    2021

  12. [20]

    Bandit optimisation of functions in the Matérn kernel RKHS

    David Janz, David Burt, and Javier González. “Bandit optimisation of functions in the Matérn kernel RKHS.” International Conference on Artificial Intelligence and Statistics. PMLR. 2020, pp. 2486–2495. 10

    2020

  13. [21]

    Gaussian process bandits with adaptive discretization

    S Shekhar and T Javidi. “Gaussian process bandits with adaptive discretization.”Electronic journal of statistics 12.2 (2018)

    2018

  14. [22]

    Instance dependent regret analysis of kernelized ban- dits

    Shubhanshu Shekhar and Tara Javidi. “Instance dependent regret analysis of kernelized ban- dits.” International Conference on Machine Learning. PMLR. 2022, pp. 19747–19772

    2022

  15. [23]

    A lower bound for linear and kernel regression with adaptive covariates

    Tor Lattimore. “A lower bound for linear and kernel regression with adaptive covariates.” Conference on Learning Theory. PMLR. 2023, pp. 2095–2113

    2023

  16. [24]

    Open problem: Regret bounds for noise-free kernel-based bandits

    Sattar Vakili. “Open problem: Regret bounds for noise-free kernel-based bandits.”Conference on Learning Theory. PMLR. 2022, pp. 5624–5629

    2022

  17. [25]

    Optimal order simple regret for Gaussian process bandits

    Sattar Vakili, Nacime Bouziani, Sepehr Jalali, Alberto Bernacchia, and Da-shan Shiu. “Optimal order simple regret for Gaussian process bandits.” Advances in Neural Information Processing Systems 34 (2021), pp. 21202–21215

    2021

  18. [26]

    Open problem: Tight online confidence intervals for RKHS elements

    Sattar Vakili, Jonathan Scarlett, and Tara Javidi. “Open problem: Tight online confidence intervals for RKHS elements.” Conference on Learning Theory. PMLR. 2021, pp. 4647–4652

    2021

  19. [27]

    Open problem: Order optimal regret bounds for kernel-based reinforcement learning

    Sattar Vakili. “Open problem: Order optimal regret bounds for kernel-based reinforcement learning.” Conference on Learning Theory. PMLR. 2024, pp. 5340–5344

    2024

  20. [28]

    Bayesian optimization under heavy-tailed payoffs

    Sayak Ray Chowdhury and Aditya Gopalan. “Bayesian optimization under heavy-tailed payoffs.” Advances in Neural Information Processing Systems 32 (2019)

    2019

  21. [29]

    Multi-scale zero-order optimization of smooth functions in an RKHS

    Madison Lee, Shubhanshu Shekhar, and Tara Javidi. “Multi-scale zero-order optimization of smooth functions in an RKHS.” 2022 IEEE International Symposium on Information Theory (ISIT). IEEE. 2022, pp. 288–293

    2022

  22. [30]

    Streaming kernel regression with provably adaptive mean, variance, and regularization

    Audrey Durand, Odalric-Ambrym Maillard, and Joelle Pineau. “Streaming kernel regression with provably adaptive mean, variance, and regularization.” Journal of Machine Learning Research 19.17 (2018), pp. 1–34

    2018

  23. [31]

    Tighter confidence bounds for sequential kernel regression

    Hamish Flynn and David Reeb. “Tighter confidence bounds for sequential kernel regression.” arXiv preprint arXiv:2403.12732 (2024)

    2024 arXiv

  24. [32]

    Enhancing Gaussian process surrogates for optimiza- tion and posterior approximation via random exploration

    Hwanwoo Kim and Daniel Sanz-Alonso. “Enhancing Gaussian process surrogates for optimiza- tion and posterior approximation via random exploration.” SIAM/ASA Journal on Uncertainty Quantification (2025)

    2025

  25. [33]

    Worst-case regret bounds for exploration via randomized value functions

    Daniel Russo. “Worst-case regret bounds for exploration via randomized value functions.” Advances in Neural Information Processing Systems (2019)

    2019

  26. [34]

    Near-optimal ran- domized exploration for tabular markov decision processes

    Zhihan Xiong, Ruoqi Shen, Qiwen Cui, Maryam Fazel, and Simon S Du. “Near-optimal ran- domized exploration for tabular markov decision processes.”Advances in neural information processing systems 35 (2022), pp. 6358–6371

    2022

  27. [35]

    A data fusion approach to optimize compositional stability of halide perovskites

    Shijing Sun, Armi Tiihonen, Felipe Oviedo, Zhe Liu, Janak Thapa, Yicheng Zhao, Noor Titan P Hartono, Anuj Goyal, Thomas Heumueller, Clio Batali, et al. “A data fusion approach to optimize compositional stability of halide perovskites.” Matter 4.4 (2021), pp. 1305–1322. 11 The ...

    2021

  28. [36]

    Appendix A presents facts, concentration and anti-concentration bounds used in this work

  29. [37]

    Appendix B presents proof of Theorem 2

  30. [38]

    Appendix C presents proof of Theorem 3

  31. [39]

    Appendix D presents proof of Theorem 4

  32. [40]

    V −1/2 t−1 K(·, Xt) · s 2R2 log q det V t−1 /δ + D !# ≤(c) p 2R2γT + 2R2 ln(1/δ) + D E TP t=1 V −1/2 t−1 K(·, Xt) ≤(d) p 2R2γT + 2R2 ln(1/δ) + D E

    Appendix E presents proof of Theorem 5. A Useful facts, concentration and anti-concentration bounds Fact 2. (Gaussian concentration and anti-concentration bounds; well-known.) For a Gaussian distributed random variable Z with mean µ and variance σ2, for any z >0, we have P {Z ...

  33. [41]

    By introducing the activation function (x)+ := max{0, x}, we use Markov’s inequality to show r(t) ≤ 2 C1,t · E " max x∈X ˜ft(x) − E max x∈X ˜ft(x) +# . (23)

  34. [42]

    ghost sample

    We use a “ghost sample” to show E " max x∈X ˜ft(x) − E max x∈X ˜ft(x) +# ≤ E [|wt| ·gt−1(Xt)] + E [|wt|] · E [gt−1(Xt)] . (24) 15 Combining the above two steps gives f ∗(x∗) ≤ E h ˜ft(Xt) i + E 2|wt| C1,t · gt−1(Xt) + E 2|wt| C1,t · E [gt−1(Xt)] , (25) which will conclude the ...

  35. [43]

    Construct a linear bandit optimization problem instance

  36. [44]

    Rewrite the learning algorithm

  37. [45]

    Construct a learning problem instance

    Lower bound the probability of pulling a sub-optimal arm when t is large enough. Construct a learning problem instance. Let X = {ei : 1 ≤ i ≤ d} be a standard basis of Rd. We construct f ∗ = (∆, 0, . . . ,0), a d-dimensional vector, where ∆ is in the order of √ R2d2+D √ d√ T w...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.