acceptodds
Under review as a conference paper at ICLR 2027

Closing the Regret Gap for Gaussian Process Bandits with Squared Exponential Kernel

Abstract

We study minimax lower bounds for Gaussian process bandits with the squared exponential (SE) kernel over compact domains with non-empty interior, where the reward function is fixed and has a bounded norm in the known reproducing kernel Hilbert space (RKHS). A fundamental open question in this setting has been the dimension-dependent gap between existing upper and lower regret bounds. Although recently resolved on the hypersphere, closing this gap on general compact domains has remained open. In this work, we completely resolve this problem. By establishing a norm embedding from the bandlimited Sinc RKHS into the SE RKHS and utilizing the Prolate Spheroidal Wave Functions (PSWFs), we construct a hypothesis class yielding an cumulative regret lower bound and an sample complexity lower bound for -optimal point identification. These results match known upper bounds up to dimension-independent logarithmic factors.

Primary area:
learning theory
Keywords:
Gaussian process bandits, kernelized bandits, regret lower bounds, minimax optimality, reproducing kernel Hilbert spaces

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_sPVaOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

In this work, the authors study minimax lower bounds for Gaussian process bandits with the squared exponential (SE) kernel over compact domains. Previous lower bounds left a dimension-dependent (ln T)^{d/4} gap to the best known upper bounds. The authors close this gap up to dimension-independent logarithmic factors. They do so by embedding a bandlimited Sinc RKHS into the SE RKHS and building hard instances from spheroidal wave functions. The result holds on the hypercube and, by an affine argument, on any compact domain with non-empty interior.

Critical strengths

The paper resolves a well-posed open problem on the canonical hypercube domain, one that the hypersphere paper[1] explicitly left open. The paper is also well written and easy to follow.

[1] Iwazaki S. Tighter regret lower bound for Gaussian process bandits with squared exponential kernel in hypersphere. In Proceedings of the 43rd International Conference on Machine Learning, 2026

Critical weaknesses

I am not an expert in this field, and this is why I set the lowest confidence score. I could therefore not identify major weaknesses. I did notice that the authors do not cite other state-of-the-art works in the Gaussian process optimization community that rely on approximate GPs, see [1,2,3,4] and references therein.

[1] Calandriello, D., Carratino, L., Lazaric, A., Valko, M., & Rosasco, L. Gaussian process optimization with adaptive sketching: Scalable and no regret. In Conference on learning theory. PMLR.

[2] Rando, M., Carratino, L., Villa, S., & Rosasco, L. Ada-bkb: Scalable gaussian process optimization on continuous domains by adaptive discretization. In International Conference on Artificial Intelligence and Statistics.

[3] Shekhar, S. and Javidi, T. (2018). Gaussian process bandits with adaptive discretization. Electronic Journal of Statistics.

[4] Shekhar, S. and Javidi, T. (2020). Multi-scale zero-order optimization of smooth functions in an rkhs.

Questions for authors
  1. Can these results be extended to approximate GPs such as [1]?

  2. How would the approximation (in particular Nystrom) affect the regret?

[1] Calandriello, D., Carratino, L., Lazaric, A., Valko, M., & Rosasco, L. Gaussian process optimization with adaptive sketching: Scalable and no regret. In Conference on learning theory. PMLR.

3 comments

Response For Related work:

Thank you for pointing us to these relevant references. We apologize for posting our response close to the end of the discussion period, and we appreciate your time in considering it.

Calandriello et al. [1] introduce BKB, which uses adaptive kernel sketching to reduce the computational cost of GP bandit optimization while retaining a no-regret guarantee. Rando et al. [2] propose Ada-BKB, which combines approximate GP inference with adaptive discretization of continuous domains. Shekhar and Javidi [3] develop a tree-based adaptive discretization algorithm under a GP prior and establish high-probability bounds on both simple and cumulative regret. In a related RKHS setting, Shekhar and Javidi [4] propose LP-GP-UCB, combining a GP surrogate with local polynomial estimators on a multi-scale partition, and derive regret bounds that exploit function smoothness.

Our original discussion of upper bounds focused primarily on statistical regret rates and their relation to our lower bound; it did not adequately cover the complementary literature on computational upper-bound algorithms. We will add these references and clarify their relationship to our focus on algorithm-independent statistical lower bounds.

Response To Questions:

Questions 1: Our lower bound is algorithm-independent and applies to the original SE-kernel function class. In particular, it applies to algorithms using Nystr"om or other approximate GP computations: for any such algorithm, there exists a function in the class on which the lower bound holds.

Question 2: Regarding the effect of approximation methods on regret, approximation quality matters. An insufficient set of inducing points can introduce approximation error or underestimate uncertainty, potentially impairing exploration. On the positive side, Calandriello et al. [1] develop BBKB, which uses a Nystr"om embedding with an adaptively updated inducing-point dictionary and combines it with adaptive batching. Under their assumptions, BBKB retains a regret guarantee comparable to that of exact GP-UCB while reducing computational cost. In the setting of adversarial Gaussian Process bandit, Iwazaki [2] develops a computationally efficient kernelized Exp3 variant using recursive ridge-leverage-score Nystr"om approximation, and establishes a regret upper bound of the same order as that of the original algorithm. These results illustrate that computational savings need not worsen the order of the available regret guarantee when approximation accuracy is appropriately controlled.

Reference

[1] Daniele Calandriello, Luigi Carratino, Alessandro Lazaric, Michal Valko, and Lorenzo Rosasco. Near-linear Time Gaussian Process Optimization with Adaptive Batching and Resparsification. In Proceedings of the 37th International Conference on Machine Learning (ICML), PMLR 119, pp. 1295–1305, 2020.

[2] Shogo Iwazaki. Nearly Optimal Algorithms for Adversarial Kernelized Bandits. arXiv preprint arXiv:2605.10299, 2026.

I thank the authors for their response! It addressed the questions I raised and I have no further concerns. Although I am not an expert in this subfield (as I indicated in my review), I think the manuscript is well done (to the best of my knowledge) and thus I maintain my positive score.

We sincerely thank you for your encouraging feedback and thoughtful review. We are glad that our response has addressed your questions.

Reviewer_aD6uOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies minimax regret lower bounds for Gaussian process bandits with the squared exponential (SE) kernel. It aims to close the dimension-dependent logarithmic gap between existing upper and lower bounds on Euclidean domains.

The authors construct localized hard functions using Prolate Spheroidal Wave Functions (PSWFs) and an embedding from the Sinc RKHS into the SE RKHS. By applying an existing change-of-measure argument to the resulting hypothesis class, they derive improved lower bounds for cumulative and simple regret. These bounds match known upper bounds up to dimension-independent logarithmic factors and extend to compact domains with non-empty interior.

Critical strengths

S1. Resolution of a well-defined theoretical gap.

The paper addresses a recognized open problem in GP bandit theory. The resulting lower bounds improve the dimension-dependent logarithmic factors and match the known upper bounds up to dimension-independent logarithmic terms.

S2. Nontrivial hard-function construction.

The use of PSWFs and the Sinc-to-SE RKHS embedding provides an interesting construction of localized hard functions while controlling their RKHS norms. This is a meaningful technical contribution.

Critical weaknesses

W1. Limited methodological novelty beyond existing lower-bound techniques.

Although the improved regret bounds are significant, the information-theoretic lower-bound argument largely follows the existing change-of-measure framework of Cai and Scarlett (2021). The main advancement comes from constructing a more localized hypothesis class through PSWFs and choosing the truncation order to obtain a sharper packing rate.

Furthermore, Iwazaki (2026) has already established the same regret-rate scaling on hyperspherical domains. The main additional contribution here is therefore extending this result to Euclidean domains through a different spectral construction, rather than introducing a fundamentally new lower-bound principle.

W2. Limited generality and technical issues in the proof.

The proposed construction relies heavily on the spectral properties of the SE kernel and PSWFs. It is unclear whether the technique provides a broadly applicable framework for deriving lower bounds for other kernel families, such as Matérn kernels, or whether it is primarily a specialized construction for the remaining SE-kernel gap.

There are also technical issues requiring clarification. In Appendix A.4, the asymptotic equivalence used for the PSWF eigenvalues omits a polynomial prefactor, so the subsequent truncation-order argument requires a more careful justification. In addition, Section 5.6 specifies the grid width only through (K=\Theta(N)), without explicitly ensuring that the (\epsilon)-optimal region is contained in its designated cell.

These issues appear potentially fixable, but they should be addressed to make the lower-bound proof fully rigorous.

Questions for authors

Q1. Methodological novelty.

Beyond the new hard-function construction, what is the fundamental methodological advance over the existing change-of-measure lower-bound framework and the recent hyperspherical result of Iwazaki (2026)?

Q2. Generalizability.

Can the proposed PSWF-based construction be extended to other kernel families, particularly Matérn kernels? If not, could the authors clarify which properties are specific to the SE kernel and limit the general applicability of the technique?

Q3. Proof details.

Can the authors clarify the eigenvalue asymptotic approximation in Appendix A.4 and provide an explicit admissible choice of the truncation order and grid width that guarantees both the RKHS norm constraint and localization within a single cell?

3 comments
AuthorsOpenReview ↗

Response to W1 and Q1: Methodological Novelty

We thank the reviewer for recognizing the significance of the improved bounds and the technical contribution of the hard-function construction. And we apologize for posting our response close to the end of the discussion period, and we appreciate your time in considering it. The revised manuscript corresponding to our rebuttal is now available, the substantive changes are highlighted in blue for ease of review.

We agree that the information-theoretic framework follows Cai and Scarlett(2021), and that Iwazaki(2026) established the same regret rate on the hypersphere with the framework. We do not claim a new change-of-measure principle. Our contribution addresses the analytical bottleneck preceding that step: constructing sufficiently localized hard instances with constrained norm on Euclidean domains.

Specifically, we construct functions in an auxiliary Sinc RKHS and transfer them to the target RKHS. This avoids requiring an explicit Mercer eigensystem of the SE kernel on the hypercube. Compared with the scaled fixed Fourier bump construction (Cai and Scarlett(2021)), our construction yields a smaller localization width wϵw_\epsilon and a larger number MϵM_\epsilon of hard instances. Specifically, for Lϵ=log⁡(B/ϵ)L_\epsilon=\log(B/\epsilon), the corresponding scales improve from

\Theta(L_\epsilon^{-1/2}) \quad\longrightarrow\quad \Theta\left(\frac{\log L_\epsilon}{L_\epsilon}\right), \qquad M_\epsilon:\quad \Theta(L_\epsilon^{d/2}) \quad\longrightarrow\quad \Theta\left( \left[\frac{L_\epsilon}{\log L_\epsilon}\right]^d \right).$$ Together with the cross-region interference control, this yields $$R_T =\Omega\left( \sqrt{T}\left(\frac{\log T}{\log\log T}\right)^{d/2} \right)$$ on the hypercube and extends to compact Euclidean domains with nonempty interior. Iwazaki's spherical-harmonic construction does not directly supply these Euclidean hard instances. Thus we clarify that our main methodological advance is this auxiliary-RKHS localization construction, not a new information-theoretic framework.
AuthorsOpenReview ↗

Response to W2 and Q2: Generality beyond the SE kernel

We thank the reviewer for this question. We agree that the original presentation did not sufficiently clarify the scope of our construction. Our additional analysis shows that the PSWF-based construction is not restricted to the SE kernel: it can be transferred to other stationary-kernel RKHSs through a lower bound on their spectral densities.

For a stationary kernel kk with spectral density SkS_k, define

mk(c):=ess,inf⁡ω∈[−c,c]dSk(ω).m_k(c):=\operatorname*{ess\\,inf}_{\omega\in[-c,c]^d} S_k(\omega).

Whenever mk(c)>0m_k(c)>0, the function ff bandlimited to [−c,c]d[-c,c]^d belongs to Hk(Rd)H_k(R^d) and its RKHS norm is upper bounded by mk(c)−1/2∣∣f∣∣L2(Rd)m_k(c)^{-1/2} ||f||_{L^2(R^d)}

The spectral embedding allows us to derive lower bounds through two complementary PSWF-based constructions: one with a fixed bandwidth and one with a growing bandwidth. And their strengths depend on the rate of spectral decay of kernel kk.

To illustrate how the spectral decay affects the resulting lower bound, we consider the following three classes of stationary kernels:

  1. Polynomial decay: Sk(ω)≍(1+∣ω∣2)−r/2S_k(\omega)\asymp(1+\\|\omega\\|^2)^{-r/2} for r>dr>d. This class includes the Matérn kernel, with r=2ν+dr=2\nu+d.

  2. Stretched-exponential decay: Sk(ω)≍exp⁡(−τ∣ω∣γ)S_k(\omega)\asymp\exp(-\tau\\|\omega\\|^\gamma) for τ>0\tau>0 and 0<γ≤10<\gamma\leq1.

  3. Super-exponential decay: Sk(ω)≍exp⁡(−τ∣ω∣γ)S_k(\omega)\asymp\exp(-\tau\\|\omega\\|^\gamma) for τ>0\tau>0 and γ>1\gamma>1. This class includes the SE kernel, for which γ=2\gamma=2.

Both constructions can be applied to these classes and their resulting bounds differ: fixed bandwidth construction gives the stronger bound in the super-exponential case, whereas growing bandwidth construction gives stronger bounds in the polynomial and stretched-exponential cases.

1. Fixed bandwidth. Adapting the fixed-bandwidth construction in our original papar. For Lϵ=log⁡(B/ϵ)L_\epsilon=\log(B/\epsilon), we construct the Christoffel-Darboux kernels and determine the truncation order as Nϵ=Θ(Lϵ/log⁡Lϵ)N_\epsilon=\Theta(L_\epsilon/\log L_\epsilon). Under the same localization and interference argument, this yields lower bound

\sqrt{T}\left(\frac{\log T}{\log\log T}\right)^{d/2} \right).$$ This bound applies to all three spectral classes considered above, thus, the fixed-bandwidth construction is not specific to the SE kernel. For SE kernel and, more generally, for kernels with **Super-exponential decay**, this rate is the best known lower bound. For **polynomial and stretched-exponential spectral decay**, however, this fixed-bandwidth bound is weaker than existing lower bounds. In particular, for the Matérn kernel with smoothness parameter $\nu>0$, the classical lower bound is $$R_T=\Omega\left(T^{(\nu+d)/(2\nu+d)}\right)$$ Another growing-bandwidth construction below adapts to the spectral decay and recovers the stronger bounds for these two classes. **2. Growing bandwidth.** Alternatively, we can allow the bandwidth $c_T$ to increase with the time horizon $T$ and determine the truncation order of Christoffel-Darboux kernels as \$ N(c_T)=\max\\{n:\lambda_n(c_T)\ge 1/2\\} =\frac{2c_T}{\pi}+O(\log c_T) \$. The resulting PSWF-based construction gives $M_c=\Theta_d(c^d)$ localized alternatives of width $O(c^{-1})$, satisfying $$\\|f_{\epsilon,c}\\|_{\mathcal H_k} \lesssim_d \frac{\epsilon}{\sqrt{c^d m_k(c)}},$$ The RKHS norm constraint therefore requires $\epsilon\lesssim_d B\sqrt{c^d m_k(c)}$. Balancing this with the change-of-measure condition $T\lesssim_d\sigma^2c^d/\epsilon^2$, we choose $\epsilon\asymp_d\sigma\sqrt{c^d/T}$ and this gives $$R_T\gtrsim_d\sigma\sqrt{T}\\,c^{d/2}.$$ For **polynomial spectral decay** $S_k(\omega)\asymp(1+\\|\omega\\|^2)^{-r/2}$ with $r>d$, taking $c\asymp T^{1/r}$ recovers $R_T^\star=\Omega(T^{(r+d)/(2r)})$. In particular, for a Matérn kernel, $r=2\nu+d$, giving $$R_T=\Omega\left(T^{(\nu+d)/(2\nu+d)}\right).$$ For **stretched-exponential decay** $S_k(\omega)\asymp\exp(-\tau\\|\omega\\|^\gamma)$ with $0<\gamma\leq1$, taking $c\asymp(\log T)^{1/\gamma}$ gives $$R_T=\Omega\left( \sqrt{T}(\log T)^{d/(2\gamma)} \right).$$ These growing-bandwidth rates recover existing lower-bound benchmarks, including the classical Matérn lower bound. But achives sub-optimal result in **super-exponential case**. We will clarify these constructions and provide the proofs in the revised manuscript.
AuthorsOpenReview ↗

Response to W2 and Q3: Technical issues in the proof

We thank the reviewer for identifying these issues. We agree that the passage from the eigenvalue asymptotics to the truncation condition in Appendix A.4 was not sufficiently justified, and that the statement K=Θ(N)K=\Theta(N) alone does not ensure that the ϵ\epsilon-optimal region is contained in its designated cell. We will correct these points and make the parameter choices explicit in the revised manuscript.

For the calculation of truncation condition, We will replace the eigenvalue asymptotics

\left(\frac{c}{4}\right)^{2n+1}= \exp\left(-2n\ln\left(\frac{4n}{ec}\right)+ O(\ln n)\right).$$ with the following lower bound valid for all sufficiently large $n$: $$\lambda_n(c) \ge \frac{c}{8n} \left(\frac{ec}{4n}\right)^{2n}.$$ And we retain the normalization factor: $$\lVert f_{\epsilon,N}\rVert_{\mathcal H_{\mathrm{Sinc}}}^{2} \le \frac{4\epsilon^2} {[\lambda_N(c)K_N(0,0)]^d}.$$ Since $K_N(0,0)\ge N/(2\pi)$ for sufficiently large $N$, this bound accounts for the polynomial prefactor and yields $$\lVert f_{\epsilon,N}\rVert_{\mathcal H_{\mathrm{SE}}} \le 2\epsilon q_{\theta,c}^{d} \exp\left(dN\log\frac{4N}{ec}\right),$$ where $$q_{\theta,c}= \left(\frac{16\pi}{c}\right)^{1/2} (\pi\theta)^{-1/4}e^{\theta c^2/8}.$$ Define $$L_\epsilon= \log\frac{B}{2q_{\theta,c}^{d}\epsilon}, \qquad D_c=\frac{4}{ec},$$ and choose $$N_\epsilon= \left\lfloor \frac{L_\epsilon}{d\log(D_cL_\epsilon)} \right\rfloor.$$ for sufficiently small $\epsilon$, this choice gives an RKHS norm of at most $B$.
Reviewer_n52JOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies minimax lower bounds for Gaussian process bandits with the squared exponential (SE) kernel on compact Euclidean domains, where the reward function has bounded norm in the SE RKHS. Existing lower bounds (Scarlett et al., 2017; Cai & Scarlett, 2021) leave a (ln⁡T)d/4(\ln T)^{d/4} gap to the best upper bounds. Iwazaki (2026) recently closed this gap on the hypersphere, but not on [0,1]d[0,1]^d. The authors circumvent the lack of a closed-form Mercer eigensystem for the SE kernel on the hypercube.

Critical strengths

I think the main strength of the paper lies in its construction. Working in the Sinc RKHS, where the eigensystem on [−1,1]d[-1,1]^d is explicit, and then transferring the norm bound to the SE RKHS through the chain in equation 25 is a clean way around the obstacle that Iwazaki (2026) identified for the hypercube. The idea of using PSWF Christoffel-Darboux kernels with a fixed bandwidth and letting the truncation order NN, rather than the bandwidth, control the peak width seems new to me.

Critical weaknesses

My main concern is that the paper overstates the tightness of its result. The phrases "completely resolve" and "definitively settled" suggest a full minimax characterization. However, the upper bound TγT\sqrt{T\gamma_T} with γT=O((ln⁡T)d+1(ln⁡ln⁡T)−d)\gamma_T=O\big((\ln T)^{d+1}(\ln\ln T)^{-d}\big) still carries an extra ln⁡T\sqrt{\ln T} factor. The hidden constants also grow exponentially in dd, through CdC_d and other constants, and depend on θ\theta through exp⁡(dθc2)\exp(d\theta c^2). The bounds therefore hold only for fixed dd and θ\theta and for sufficiently small ϵ/B\epsilon/B. The abstract and discussion should state these limitations more carefully.

Similarly, in the introduction/related work section, the stated upper bound is O(TγT)O(\sqrt{T \gamma_T}). I have an objection to these kinds of statements, which are adopted by this paper as well as prior work. Any GP-UCB style upper bound on the domain [0,1]d[0,1]^d should ideally state explicit dimension dependence -- a careful look into the existing analysis would suggest a bound of the form O(dTγT)O(\sqrt{ d T \gamma_T}). Consequently, any lower bound should be compared against this rate.

Questions for authors

My question is about the remaining ln⁡T\sqrt{\ln T} gap between the lower bound and the upper bound TγT\sqrt{T\gamma_T}. Do the authors believe this gap comes from the upper bound or the lower bound? It would also help if the authors could state the explicit dependence of the constants on dd, since that would show for which dimensions and horizons the bound is meaningful in practice.

I also believe this paper is better suited to more learning-theory-oriented venues than to ICLR. I would encourage the authors to submit this to COLT after incorporating the above comments.

1 comment

Thank you for the careful review. We apologize for posting our response close to the end of the discussion period, and we appreciate your time in considering it. Your comments have prompted us to clarify the scope of our result and make its parameter dependence explicit. We summarize our main conclusions below, full proofs will be included in the revised appendix. The revised manuscript corresponding to our rebuttal is now available, the substantive changes are highlighted in blue for ease of review

Response to the remaining regret gap.

We agree that “completely resolve” and “definitively settled” overstate our result, and we will revise these phrases. Let qT=log⁡T/log⁡log⁡Tq_T=\log T/\log\log T. For fixed d,θ,B,σ>0d,\theta,B,\sigma>0, our lower bound scales as TqTd/2\sqrt{T}q_T^{d/2}. Since γT([0,1]d)=Θd,θ,σ(qTdlog⁡T)\gamma_T([0,1]^d)=\Theta_{d,\theta,\sigma}(q_T^d\log T), comparison with the TγT\sqrt{T\gamma_T} benchmark leaves a factor of log⁡T\sqrt{\log T}. Existing algorithmic guarantees may include additional confidence or logarithmic factors. We will state the remaining gap and the fixed-parameter scope clearly in the revised manuscript.

Based on our further investigation of improved algorithms, we believe that the remaining gap can be closed by strengthening the upper bound, and that the dependence on TT in our lower bound is optimal.

Response to explicit dependence on dimension and the kernel parameter.

For each fixed d,θ,B,σ>0d,\theta,B,\sigma>0, further investigation in our lower bound yields

lim inf⁡T→∞RTσT[qT/(Ld)]d/2≥κ>0,\liminf_{T\to\infty}\frac{R_T}{\sigma\sqrt{T}[q_T/(Ld)]^{d/2}}\geq\kappa>0,

where LL and κ\kappa are universal constants independent of d,θ,B,σd,\theta,B,\sigma, and TT. This makes explicit a d−d/2d^{-d/2}-type factor in the lower bound obtained from our construction.

Although θ\theta does not appear explicitly in the normalized bound above, it may affect the horizon beyond which the bound becomes effective. Specifically, for every 0<c<κ0<c<\kappa, there exists T0=T0(d,θ,B,σ,c)T_0=T_0(d,\theta,B,\sigma,c) such that the corresponding lower bound with coefficient cc holds for all T≥T0T\geq T_0. Thus the asymptotic statement does not establish uniformity over growing dd or varying θ\theta.

Dimension dependence in upper-bound comparisons.

We agree that comparisons between upper and lower bounds should make dimension dependence explicit. As one example, the grid-based BPE algorithm of Li and Scarlett [1] has a high-probability upper bound of the form O∗(ΛTTγT)O^*(\Lambda_T\sqrt{T\gamma_T}), where

ΛT=B+d2log⁡T+log⁡1δ.\Lambda_T=B+\sqrt{\frac d2\log T+\log\frac1\delta}.

This illustrates a dimension-dependent confidence factor outside γT\gamma_T; the O∗O^* notation suppresses additional dimension-independent logarithmic factors. To clarify the dimension dependence within the information-gain term, for the SE kernel and fixed d,θ,σ2>0d,\theta,\sigma^2>0, we establish that

lim⁡T→∞γT([0,1]d)(ln⁡T)d+1/(ln⁡ln⁡T)d=12(d+1)!.\lim_{T\to\infty}\frac{\gamma_T([0,1]^d)}{(\ln T)^{d+1}/(\ln\ln T)^d}=\frac{1}{2(d+1)!}.

These results above clarify the dimension dependence of our lower-bound construction and of the information-gain term, they do not establish dimension-tight minimax bounds. An important direction for future work is to establish tighter, more explicit upper and lower bounds in terms of the dimension.

[1] Zihan Li and Jonathan Scarlett. Gaussian Process Bandit Optimization with Few Batches. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS), PMLR 151, pp. 92–107, 2022.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.