acceptodds
Under review as a conference paper at ICLR 2027

Improved Regret Bounds for Gaussian Process Bandits under Heavy-Tailed Noise

Abstract

We study Gaussian process bandit optimization of an unknown objective function in a reproducing kernel Hilbert space (RKHS). We assume that the observation noise has a finite -moment for some . Unlike the sub-Gaussian noise assumption, this moment condition allows heavy-tailed noise and does not require finite variance when . For a horizon and maximum information gain , existing regret bounds in this setting scale as either or , both linear in . To reduce this dependence on , we propose the heavy-tailed chaining phased elimination (HT-ChainPE) algorithm, which combines regularized D-optimal design with a robust chained estimator. HT-ChainPE achieves cumulative regret of order . For , this bound retains the dependence achieved in prior work while reducing the exponent of below one. We also establish a worst-case cumulative regret lower bound on of for the squared-exponential kernel, where and . For the Matérn kernel with smoothness on , we obtain a lower bound of . Finally, experiments on synthetic and real-world benchmarks show that HT-ChainPE performs competitively against existing methods.

Primary area:
learning theory
Keywords:
Gaussian process bandits, Bayesian optimization, heavy-tailed noise, regret analysis

Reviews

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

This paper proves a new upper bound on cumulative regret for GP-based Bayesian optimization, where the noise added to the unknown function can be heavy-tailed (e.g., Student's t). Starting from Srinivas etal, such bounds come in terms of T (number of rounds) and gamma_T (maximum information gain after T rounds). Previous best results for noise with finite (1+eps) moments were O[ T^{1/(1+eps)} gamma_T ], so linear in gamma_T. The work here improves this to O [ T^{1/(1+eps)} gamma_T^{(1 + 3 eps)/(2 + 2 eps)} ], which is better for eps < 1. The result is conditioned on a particular algorithm being used to drive the choice of the next candidate in each round. While this algorithm is not realizable in practice as it is, neither are the algorithms on which earlier work was conditioned on (they all require global optimization of non-convex functions).

This is a very nice result, which not only sets a new standard, but also introduces new ideas to the ML community. While the main outcome is theoretical, the authors also provide a realizable algorithm to approximate theirs. As in earlier work, there is no strong link between the theoretical and the realizable algorithm, but clearly the authors do their best here. I'd personally be quite interested in how realistically useful the realizable algorithm is. It does not depend on heavy optimization technology (L-BFGS, multiple starts, etc.).

Critical strengths

This paper introduces substantial new technology, which seems novel at least in the ML field. This pays off, since their result is strictly better than earlier work.

While the details of the proof is far above my head, the presentation is very clear. I'd expect that with enough effort on my side, I could follow everything. Also, while the algorithm is not realizable, it seems reasonable in its steps (covering, refinement, stage-wise filtering) and does not rely on heavy concepts.

Another positive point is that few choices need to be made. There is no acquisition function, for example. The suggested realizable implementation seems quite simple, even though there is no code provided, and the complexity estimates still rely on numbers (size of C_l, J_l, n_l) that are not really specified. Experimental results are not shown.

Critical weaknesses

As far as I can judge, this seems a strong and interesting theoretical work, setting a new standard in terms of upper bound. It covers noise distributions that are more realistic than what is often assumed.

It is a bit of a shame that the authors do not go further making their algorithm practically relevant. As somebody who has worked on BO for a long while, I am not much satisfied with the current SotA implementations, which often use heavy and messy combinations of local optimization (L-BFGS) and all sorts of initialization heuristics. If insight from the theory community could lead to a better solution (where "better" means works better in practice -- more robust, simpler to implement), this would be really useful. In general, given the practical relevance of what we are talking about, I find it a bit disappointing that many theory researchers always stop where it could become interesting for practitioners. This strongly limits the impact that theory can have.

Questions for authors

I think you could have more impact by expanding the part in 4.2. Try to give the reader maximum details about this realizable algorithm. How would it be implemented? What are the most important choices and trade-offs? What algorithmic technology is needed? The current SotA in BO-HPO is rather messy, maybe also because it works in practice, so there is much prior work, also on the practical side (several major libraries, like BOTorch or Optuna). If you analyze an algorithm here that gets rid of acquisition functions, local optimization, etc., that could be quite important.

But as a practitioner, I'd want to know a lot more before I'd sit down and spend any efforts on this. I've been burned before trying to implement theoretically justified algorithms: it can end up like a major rabbit hole of high complexity techniques stacked on top of each other. If your method is not like this, then please make an effort to point this out. And if there are major hurdles for implementing and using this in practice, it would be good to be upfront about them.

Reviewer_qGWjOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This primarily theoretical paper presents an algorithm for Gaussian process bandits with heavy tailed noise with improved regret bounds. In particular, it introduces an algorithm -- HT-ChainPE -- based on phased elimination that maintains an active set of plausible maximizers, samples open loop within this active set using D-optimal design and uses a chaining technique to uniformly estimate the reward function up to a specified error tolerance which is shrunk across phases. The algorithm achieves a regret upper bound which, in contrast to prior work, depends only sublinearly on the information gain parameter. The upper bounds are complemented with sharper lower bounds for the Matern and RBF kernels. While the focus of the paper is theoretical in nature, a more practical version is presented as well, with some experiments included in the supplementary materials.

Critical strengths
  • The paper makes progress towards settling the complexity of Gaussian process bandits under heavy tailed noise. I think the paper makes a valuable contribution to the literature on Gaussian process bandits. I also appreciate the fact that the authors make the effort to derive a more practical variant of their algorithm and test it empirically despite the primarily theoretical focus.
Critical weaknesses
  • My main concern, while not critical, is that the basic ideas used in the algorithm are not particularly surprising, and while the authors improve both upper and lower bounds on the regret, a gap still remains.
Questions for authors
  • Do any of the theoretical results carry over to the practical variant of the algorithm? If not, which approximation would the authors consider most potentially problematic?
Reviewer_hZTkOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper is concerned with GP bandit optimization, whenever the function is contained in an RKHS. The results the paper derives are particularly targeting Gaussian RBF (squared exponential) kernels and their finite-dimensional counterparts, the Matern kernel (in the limit you recover Gauss). As such, the smoothness properties are of a similar nature.

The main contribution are an ever so slightly better convergence rates (see Table 1), using a kernelization of the result by Tajdini et al. (2024). My main concern regarding the paper is whether anyone cares about the result. Here's the issue: it is pretty much impossible to determine a-priori which smoothness class the functions we are interested in belong to. It is furthermore next to impossible to obtain tight practical bounds on the degree (or on the maximum RKHS norm). This makes a slightly better theoretical guarantee moot, since the practical result hinges a lot more on whether you can get a guarantee at all. In other words, I struggle to see who would care about this tighter bound and the paper doesn't really answer that. This doesn't give rise to deeper theoretical insights nor does it help with a real implementation.

Critical strengths
  • The paper is mostly technically correct, as far as the mathematical derivation is concerned.
  • The authors made a clear effort in keeping the paper readable.
  • The paper advances on the state of the art.
  • There was an effort to verify the results experimentally.
Critical weaknesses
  • There are some issues regarding the originality. The paper is a kernelization of Tajdini et al. (2025) MED-PE plus a chaining step that removes the covering term. The methodological ancestors (Camilleri et al. 2021; Bartl & Mendelson 2025) are not cited. The paper notes that its exponents match Iwazaki's on a different domain, but it does not state the Gaussian-noise corollary or credit the construction.

  • There are some concerns regarding the reported experiments. They cannot have come from the documented algorithm: Fig. 8 rules this out for any value of C_ε. I can provide additional detail upon request.

  • It's really not clear who would care about the result, since I struggle to see how this would help in theory or in experiment.

Questions for authors
  • Please have your agent review the experiments.
  • Please identify issues regarding relevance.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.