mlsanityData to 14 Oct 2026

Gaussian Process Bandit Optimization with Few Batches

arXiv 2110.07788 ↗First posted 15 Oct 2021stat.ML cs.IT cs.LGcited by 57

Not on the map. Why?

Abstract (arXiv)

In this paper, we consider the problem of black-box optimization using Gaussian Process (GP) bandit optimization with a small number of batches. Assuming the unknown function has a low norm in the Reproducing Kernel Hilbert Space (RKHS), we introduce a batch algorithm inspired by batched finite-arm bandit algorithms, and show that it achieves the cumulative regret upper bound O^ast(√TγT) using O(loglog T) batches within time horizon T, where the O^ast(·) notation hides dimension-independent logarithmic factors and γT is the maximum information gain associated with the kernel. This bound is near-optimal for several kernels of interest and improves on the typical O^ast(√TγT) bound, and our approach is arguably the simplest among algorithms attaining this improvement. In addition, in the case of a constant number of batches (not depending on T), we propose a modified version of our algorithm, and characterize how the regret is impacted by the number of batches, focusing on the squared exponential and Mat'ern kernels. The algorithmic upper bounds are shown to be nearly minimax optimal via analogous algorithm-independent lower bounds.

Key facts. Cited by 57 papers in the map (data through 14 Oct 2026). Builds on 14 of its 31 references that are in the map. First posted on arXiv 15 Oct 2021.

Builds on

14 of 31 references.

References · 14

  1. 2017On Kernelized Multi-armed Banditscited by 352
  2. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  3. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 158
  4. 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 78
  5. 2013Online Learning with Switching Costs and Other Adaptive Adversariescited by 61
  6. 2018High-Dimensional Bayesian Optimization via Additive Models with Overlapping Groupscited by 59
  7. 2021High-Dimensional Experimental Design and Kernel Banditscited by 56
  8. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 54
  9. 2019Regret Bounds for Batched Banditscited by 49
  10. 2020Bandit optimisation of functions in the Mat'ern kernel RKHScited by 40
  11. 2020A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performancecited by 39
  12. 2020On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimizationcited by 31
2 more
  1. 2020Multi-Scale Zero-Order Optimization of Smooth Functions in an RKHScited by 16
  2. 2021Lenient Regret and Good-Action Identification in Gaussian Process Banditscited by 12

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 4; 2022: 13; 2023: 9; 2024: 10; 2025: 11; 2026: 10.

57 papers.

Sort:

By area:

  1. 2022Sample-Then-Optimize Batch Neural Thompson Samplingcited by 25
  2. 2022On Kernelized Multi-Armed Bandits with Constraintscited by 23
  3. 2021Lipschitz Bandits with Batched Feedbackcited by 21
  4. 2023Kernelized Reinforcement Learning with Order Optimal Regret Boundscited by 20
  5. 2022Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learningcited by 18
  6. 2022An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledgecited by 17
  7. 2023Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiencycited by 17
  8. 2025Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variancecited by 15
  9. 2021Open Problem: Tight Online Confidence Intervals for RKHS Elementscited by 13
  10. 2021Collaborative Pure Exploration in Kernel Banditcited by 13
  11. 2025Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimizationcited by 13
  12. 2023Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for Martingale Mixturescited by 12
38 more
  1. 2023Quantum Bayesian Optimizationcited by 12
  2. 2022A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Banditscited by 11
  3. 2022Bayesian Optimization under Stochastic Delayed Feedbackcited by 10
  4. 2022Graph Neural Network Banditscited by 10
  5. 2023Delayed Feedback in Kernel Banditscited by 10
  6. 2023A Lipschitz Bandits Approach for Continuous Hyperparameter Optimizationcited by 9
  7. 2025Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Banditscited by 9
  8. 2023Sample Complexity of Kernel-Based Q-Learningcited by 8
  9. 2024Tighter Confidence Bounds for Sequential Kernel Regressioncited by 8
  10. 2024Near-Optimal Algorithm for Non-Stationary Kernelized Banditscited by 8
  11. 2024Transition Constrained Bayesian Optimization via Markov Decision Processescited by 7
  12. 2022Provably and Practically Efficient Neural Contextual Banditscited by 6
  13. 2022Collaborative Learning in Kernel-based Bandits for Distributed Userscited by 6
  14. 2024Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithmcited by 6
  15. 2024Constrained Multi-objective Bayesian Optimization through Optimistic Constraints Estimationcited by 6
  16. 2021Adversarial Attacks on Gaussian Process Banditscited by 5
  17. 2022Instance-Dependent Regret Analysis of Kernelized Banditscited by 5
  18. 2024Lower Bounds for Time-Varying Kernelized Banditscited by 5
  19. 2026Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hyperspherecited by 4
  20. 2022Regret Bounds for Noise-Free Cascaded Kernelized Banditscited by 3
  21. 2023(Private) Kernelized Bandits with Distributed Biased Feedbackcited by 3
  22. 2025Differentially Private Kernelized Contextual Banditscited by 3
  23. 2025Distributionally Robust Active Learning for Gaussian Process Regressioncited by 3
  24. 2025Bayesian Optimization from Human Feedback: Near-Optimal Regret Boundscited by 3
  25. 2026Batched Kernelized Bandits: Refinements and Extensionscited by 3
  26. 2024Batched Stochastic Bandit for Nondegenerate Functionscited by 2
  27. 2024Open Problem: Order Optimal Regret Bounds for Kernel-Based Reinforcement Learningcited by 2
  28. 2025Consequences of Kernel Regularity for Bandit Optimizationcited by 2
  29. 2026Randomized Kriging Believer for Parallel Bayesian Optimization with Regret Boundscited by 2
  30. 2022Anonymous Bandits for Multi-User Systemscited by 1
  31. 2022Benefits of Monotonicity in Safe Exploration with Gaussian Processescited by 1
  32. 2026Nearly-Optimal Algorithm for Adversarial Kernelized Banditscited by 1
  33. 2026Improved Regret Analysis for Parallel Gaussian Process Bandit Optimizationcited by 1
  34. 2023From Random Search to Bandit Learning in Metric Measure Spacescited by 0
  35. 2024Order-Optimal Regret in Distributed Kernel Bandits using Uniform Sampling with Shared Randomnesscited by 0
  36. 2024The Traveling Bandit: A Framework for Bayesian Optimization with Movement Costscited by 0
  37. 2025Representative Action Selection for Large Action Space Bandit Familiescited by 0
  38. 2025Direct Regret Optimization in Bayesian Optimizationcited by 0

50 most cited of 57 All 57 (JSON)