Abstract
Standard Bayesian Optimization (BO) typically aims to find the exact global maximum of an objective function, a task that theoretically results in cumulative regret bounds scaling with $\sqrt{T}$. However, many practical applications only require finding a "good enough" solution. This paper formalizes this intuition by introducing the concepts of lenient regret and good-action identification in Gaussian Process (GP) bandits. We demonstrate that seeking "good enough" actions allows for significantly improved theoretical bounds—potentially reaching constant regret—and faster practical convergence compared to traditional optimization approaches.
Introduction
In real-world optimization tasks such as hyperparameter tuning or robotics, the goal is often to find a solution that meets a specific performance threshold rather than the absolute global optimum. Standard BO theory, which focuses on finding the exact maximum $f(x^*)$, suffers from the "needle-in-a-haystack" problem, where infinite precision is required to distinguish between near-optimal points. This paper addresses the gap between standard theory and practical "satisficing" requirements by asking: can we achieve better regret bounds if we stop penalizing algorithms once they find a "good enough" point?
Theoretical Framework: Lenient Regret
To formalize the concept of "good enough," we define lenient regret, where actions within a distance $\Delta$ of the optimum incur zero penalty. We consider three primary variations of the penalty function $\Phi(r)$ based on simple regret $r$:
- Indicator: A binary penalty that counts the number of "bad" actions.
- Large Gap: Sums the simple regret only for actions that fall outside the $\Delta$-neighborhood.
- Hinge: Sums the distance from the "good enough" threshold for sub-optimal actions.
These definitions allow us to analyze the performance of popular algorithms like GP-UCB and Confidence-based Elimination under a more relaxed, practical lens.
Good-Action Identification
Beyond cumulative regret, we consider the task of identifying a single point exceeding a known threshold $\eta$. We introduce three acquisition functions designed for this purpose:
- Probability of Being Good (PG): Selects the point with the highest probability of exceeding $\eta$.
- Expected Improvement Over Good (EG): A variant of Expected Improvement (EI) that measures improvement relative to $\eta$ instead of the current observed maximum.
- Good-Action Search (GS): A non-myopic approach using Gumbel distribution approximations to look one step ahead.
Key Insights and Results
Breaking the $\sqrt{T}$ Barrier
A major theoretical finding is that lenient regret can be significantly smaller than standard regret. While standard regret is $O(\sqrt{T})$, lenient regret for the Squared Exponential (SE) kernel can be as low as $O(poly(\log T))$ or even $O(1)$ (constant) for elimination algorithms.
Elimination vs. UCB
In the context of lenient regret, elimination algorithms prove theoretically superior to GP-UCB. While GP-UCB's exploration parameter grows over time, eventually forcing it to revisit "bad" regions, elimination algorithms can prune these regions permanently once they are confirmed to be outside the $\Delta$-neighborhood.
Empirical Performance
Experiments on synthetic functions and real-world benchmarks (e.g., Robot Pushing 4D, XGBoost tuning) show that threshold-aware algorithms like PG and EG find "good" actions much faster than standard baselines like EI or Thompson Sampling. These methods are also robust; if the threshold $\eta$ is set higher than the actual maximum, they revert to finding the best possible point with performance comparable to standard BO.
Conclusion
By shifting the focus from exact optimization to "good-enough" identification, we can derive tighter theoretical bounds and more efficient algorithms for GP bandits. Future work includes refining bounds for Matérn kernels and developing methods to estimate the threshold $\eta$ dynamically when it is unknown.
Summary updated