Lenient Regret and Good-Action Identification in Gaussian Process Bandits

2021/02/11 by Xu Cai, Cai, Xu, Selwyn Gomes +3 · 3 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Advanced Multi-Objective Optimization Algorithms #FOS: Computer and information sciences #FOS: Mathematics #Gaussian Processes and Bayesian Inference #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2102.05793

openalex publication_date 2021/02/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• Finite-Time Analysis of Kernelised Contextual Bandits
• Predictive Entropy Search for Efficient Global Optimization of Black-box\n Functions
• Taking the Human Out of the Loop: A Review of Bayesian Optimization
• Truncated Variance Reduction: A Unified Approach to Bayesian\n Optimization and Level-Set Estimation
• Max-value Entropy Search for Efficient Bayesian Optimization
• On Kernelized Multi-armed Bandits
• Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization
• Lenient Regret for Multi-Armed Bandits

Cited by

• Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization
• Robust Satisficing Gaussian Process Bandits Under Adversarial Attacks
• High-dimensional Nonparametric Contextual Bandit Problem

Related

• Regret Bounds for Deterministic Gaussian Process Bandits
• Exponential Regret Bounds for Gaussian Process Bandits with Deterministic Observations
• Regret Bounds for Safe Gaussian Process Bandit Optimization
• Optimal Order Simple Regret for Gaussian Process Bandits
• Regret and Belief Complexity Trade-off in Gaussian Process Bandits via Information Thresholding