mlsanityData to 14 Oct 2026

Regret Bounds for Noise-Free Cascaded Kernelized Bandits

arXiv 2211.05430 ↗First posted 10 Nov 2022stat.ML cs.IT cs.LGcited by 3

Not on the map. Why?

Abstract (arXiv)

We consider optimizing a function network in the noise-free grey-box setting with RKHS function classes, where the exact intermediate results are observable. We assume that the structure of the network is known (but not the underlying functions comprising it), and we study three types of structures: (1) chain: a cascade of scalar-valued functions, (2) multi-output chain: a cascade of vector-valued functions, and (3) feed-forward network: a fully connected feed-forward network of scalar-valued functions. We propose a sequential upper confidence bound based algorithm GPN-UCB along with a general theoretical upper bound on the cumulative regret. In addition, we propose a non-adaptive sampling based method along with its theoretical upper bound on the simple regret for the Mat'ern kernel. We also provide algorithm-independent lower bounds on the simple regret and cumulative regret. Our regret bounds for GPN-UCB have the same dependence on the time horizon as the best known in the vanilla black-box setting, as well as near-optimal dependencies on other parameters (e.g., RKHS norm and network length).

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 20 of its 33 references that are in the map. First posted on arXiv 10 Nov 2022.

Builds on

20 of 33 references.

References · 20

  1. 2017On Kernelized Multi-armed Banditscited by 352
  2. 2018Gaussian Processes and Kernel Methods: A Review on Connections and Equivalencescited by 192
  3. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 158
  4. 2014Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functionscited by 95
  5. 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 78
  6. 2016Efficiency of minimizing compositions of convex functions and smooth mapscited by 59
  7. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
  8. 2021High-Dimensional Experimental Design and Kernel Banditscited by 56
  9. 2019Bayesian Optimization of Composite Functionscited by 46
  10. 2020A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performancecited by 39
  11. 2021Bayesian Optimization of Function Networkscited by 33
  12. 2020On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimizationcited by 31
8 more
  1. 2022Thinking inside the box: A tutorial on grey-box Bayesian optimizationcited by 26
  2. 2017Goal-Driven Dynamics Learning via Bayesian Optimizationcited by 19
  3. 2020No-regret Algorithms for Multi-task Bayesian Optimizationcited by 18
  4. 2021Bayesian Optimization for Cascade-type Multi-stage Processescited by 17
  5. 2020Multi-Scale Zero-Order Optimization of Smooth Functions in an RKHScited by 16
  6. 2022Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimizationcited by 15
  7. 2020Regret Bounds for Noise-Free Kernel-Based Banditscited by 11
  8. 2019Efficient Batch Black-box Optimization with Deterministic Regret Boundscited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 1.

3 papers.

  1. 2025Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Banditscited by 9
  2. 2025BILBO: BILevel Bayesian Optimizationcited by 3
  3. 2026Improved Regret Analysis for Parallel Gaussian Process Bandit Optimizationcited by 1