# On the Suboptimality of GP-UCB under Polynomial Effective Optimism

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 16 references that are in the map.
- First posted on arXiv 3 Dec 2023.

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

- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [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)
- [Bandit optimisation of functions in the Mat'ern kernel RKHS](https://mlsanity.com/paper/2001.10396/) (2020)
- [On the Sublinear Regret of GP-UCB](https://mlsanity.com/paper/2307.07539/) (2023)
- [Bayesian Optimization for Policy Search via Online-Offline Experimentation](https://mlsanity.com/paper/1904.01049/) (2019)
- [Open Problem: Tight Online Confidence Intervals for RKHS Elements](https://mlsanity.com/paper/2110.15458/) (2021)
- [Bayesian Optimization Allowing for Common Random Numbers](https://mlsanity.com/paper/1910.09259/) (2019)

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

- [BARK: A Fully Bayesian Tree Kernel for Black-box Optimization](https://mlsanity.com/paper/2503.05574/) (2025)
- [TextBO: Bayesian Optimization in Language Space for Eval-Efficient Self-Improving AI](https://mlsanity.com/paper/2511.12063/) (2025)
- [On Improved Regret Bounds In Bayesian Optimization with Gaussian Noise](https://mlsanity.com/paper/2412.18789/) (2024)
- [Bellman-sufficient Information Complexity](https://mlsanity.com/paper/2606.11171/) (2026)

## Abstract (arXiv)

Gaussian process upper confidence bound (GP-UCB) is widely used for sequential optimization of expensive black-box functions. Although many upper bounds on its cumulative regret have been established in the literature, whether GP-UCB is minimax optimal remains open. We study this question through the effective optimism level, defined as the product of the exploration coefficient and the regularization parameter in kernel ridge regression. Under a uniform confidence assumption, we prove a new regret lower bound for GP-UCB with Mat'ern kernels. The bound shows that polynomial growth of the effective optimism level, up to logarithmic factors, rules out the minimax-optimal regret rate. Since this is the regime covered by most existing analyses, our result identifies a concrete obstacle to proving minimax optimality for standard GP-UCB. More broadly, it suggests that the gap between current upper bounds and minimax lower bounds may reflect a real limitation of the algorithm, not only of the analysis.