mlsanityData to 7 Oct 2026

Lenient Regret and Good-Action Identification in Gaussian Process Bandits

arXiv 2102.05793 ↗First posted 11 Feb 2021stat.ML cs.IT cs.LGcited by 12

Not on the map. Why?

Abstract (arXiv)

In this paper, we study the problem of Gaussian process (GP) bandits under relaxed optimization criteria stating that any function value above a certain threshold is "good enough". On the theoretical side, we study various em lenient regret notions in which all near-optimal actions incur zero penalty, and provide upper bounds on the lenient regret for GP-UCB and an elimination algorithm, circumventing the usual O(√T) term (with time horizon T) resulting from zooming extremely close towards the function maximum. In addition, we complement these upper bounds with algorithm-independent lower bounds. On the practical side, we consider the problem of finding a single "good action" according to a known pre-specified threshold, and introduce several good-action identification algorithms that exploit knowledge of the threshold. We experimentally find that such algorithms can often find a good action faster than standard optimization-based approaches.

Key facts. Cited by 12 papers in the map (data through 7 Oct 2026). Builds on 22 of its 38 references that are in the map. First posted on arXiv 11 Feb 2021.

Builds on

22 of 38 references.

References · 22

  1. 2016XGBoost: A Scalable Tree Boosting Systemcited by 5,120
  2. 2017A Tutorial on Thompson Samplingcited by 420
  3. 2017On Kernelized Multi-armed Banditscited by 348
  4. 2017Max-value Entropy Search for Efficient Bayesian Optimizationcited by 202
  5. 2014Predictive Entropy Search for Efficient Global Optimization of Black-box Functionscited by 201
  6. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  7. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 156
  8. 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 77
  9. 2013Parallel Gaussian Process Optimization with Upper Confidence Bound and Pure Explorationcited by 50
  10. 2016Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimationcited by 40
  11. 2020Bandit optimisation of functions in the Mat'ern kernel RKHScited by 40
  12. 2018Satisficing in Time-Sensitive Bandit Learningcited by 38
10 more
  1. 2019The True Sample Complexity of Identifying Good Armscited by 37
  2. 2020Corruption-Tolerant Gaussian Process Bandit Optimizationcited by 34
  3. 2017Good Arm Identification via Bandit Feedbackcited by 29
  4. 2020On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimizationcited by 29
  5. 2017Gaussian Process bandits with adaptive discretizationcited by 20
  6. 2018Tight Regret Bounds for Bayesian Optimization in One Dimensioncited by 20
  7. 2019Knowing The What But Not The Where in Bayesian Optimizationcited by 20
  8. 2020Multi-Scale Zero-Order Optimization of Smooth Functions in an RKHScited by 16
  9. 2019Multiscale Gaussian Process Level Set Estimationcited by 10
  10. 2020Lenient Regret for Multi-Armed Banditscited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 1; 2023: 2; 2024: 1; 2025: 3; 2026: 3.

12 papers.

  1. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
  2. 2025Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimizationcited by 13
  3. 2024Stopping Bayesian Optimization with Probabilistic Regret Boundscited by 11
  4. 2022Collaborative Learning in Kernel-based Bandits for Distributed Userscited by 6
  5. 2021Adversarial Attacks on Gaussian Process Banditscited by 5
  6. 2023Robust Bayesian Satisficingcited by 3
  7. 2023Provably Efficient Bayesian Optimization with Unknown Gaussian Process Hyperparameter Estimationcited by 2
  8. 2026On Regret Bounds of Thompson Sampling for Bayesian Optimizationcited by 2
  9. 2026Batched Kernelized Bandits: Refinements and Extensionscited by 2
  10. 2025High-dimensional Nonparametric Contextual Bandit Problemcited by 1
  11. 2025Robust Satisficing Gaussian Process Bandits Under Adversarial Attackscited by 1
  12. 2026Nearly-Optimal Algorithm for Adversarial Kernelized Banditscited by 1