# Lenient Regret and Good-Action Identification in Gaussian Process Bandits

arXiv: https://arxiv.org/abs/2102.05793 · HTML: https://mlsanity.com/paper/2102.05793/

## Key facts

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

## Builds on (most cited first, 22 of 22)

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Max-value Entropy Search for Efficient Bayesian Optimization](https://mlsanity.com/paper/1703.01968/) (2017)
- [Predictive Entropy Search for Efficient Global Optimization of Black-box Functions](https://mlsanity.com/paper/1406.2541/) (2014)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1706.00090/) (2017)
- [Parallel Gaussian Process Optimization with Upper Confidence Bound and Pure Exploration](https://mlsanity.com/paper/1304.5350/) (2013)
- [Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimation](https://mlsanity.com/paper/1610.07379/) (2016)
- [Bandit optimisation of functions in the Mat'ern kernel RKHS](https://mlsanity.com/paper/2001.10396/) (2020)
- [Satisficing in Time-Sensitive Bandit Learning](https://mlsanity.com/paper/1803.02855/) (2018)
- [The True Sample Complexity of Identifying Good Arms](https://mlsanity.com/paper/1906.06594/) (2019)
- [Corruption-Tolerant Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2003.01971/) (2020)
- [On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2008.08757/) (2020)
- [Good Arm Identification via Bandit Feedback](https://mlsanity.com/paper/1710.06360/) (2017)
- [Gaussian Process bandits with adaptive discretization](https://mlsanity.com/paper/1712.01447/) (2017)
- [Tight Regret Bounds for Bayesian Optimization in One Dimension](https://mlsanity.com/paper/1805.11792/) (2018)
- [Knowing The What But Not The Where in Bayesian Optimization](https://mlsanity.com/paper/1905.02685/) (2019)
- [Multi-Scale Zero-Order Optimization of Smooth Functions in an RKHS](https://mlsanity.com/paper/2005.04832/) (2020)
- [Multiscale Gaussian Process Level Set Estimation](https://mlsanity.com/paper/1902.09682/) (2019)
- [Lenient Regret for Multi-Armed Bandits](https://mlsanity.com/paper/2008.03959/) (2020)

## Built on by (most cited first, 12 of 12)

- [Gaussian Process Bandit Optimization with Few Batches](https://mlsanity.com/paper/2110.07788/) (2021)
- [Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization](https://mlsanity.com/paper/2506.01393/) (2025)
- [Stopping Bayesian Optimization with Probabilistic Regret Bounds](https://mlsanity.com/paper/2402.16811/) (2024)
- [Collaborative Learning in Kernel-based Bandits for Distributed Users](https://mlsanity.com/paper/2207.07948/) (2022)
- [Adversarial Attacks on Gaussian Process Bandits](https://mlsanity.com/paper/2110.08449/) (2021)
- [Robust Bayesian Satisficing](https://mlsanity.com/paper/2308.08291/) (2023)
- [On Regret Bounds of Thompson Sampling for Bayesian Optimization](https://mlsanity.com/paper/2603.09276/) (2026)
- [Batched Kernelized Bandits: Refinements and Extensions](https://mlsanity.com/paper/2603.12627/) (2026)
- [Provably Efficient Bayesian Optimization with Unknown Gaussian Process Hyperparameter Estimation](https://mlsanity.com/paper/2306.06844/) (2023)
- [High-dimensional Nonparametric Contextual Bandit Problem](https://mlsanity.com/paper/2505.14102/) (2025)
- [Robust Satisficing Gaussian Process Bandits Under Adversarial Attacks](https://mlsanity.com/paper/2506.01625/) (2025)
- [Nearly-Optimal Algorithm for Adversarial Kernelized Bandits](https://mlsanity.com/paper/2605.10299/) (2026)

## 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.