aiqbench analysis
This research advances parallel Gaussian process bandit optimization by eliminating the multiplicative regret penalty associated with batch size, removing the need for an often ineffective initial uncertainty sampling phase. The findings demonstrate superior performance in noiseless settings compared to noisy ones, offering a more efficient theoretical framework for sequential decision-making algorithms.
Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization
arXiv:2608.16492v1 Announce Type: cross Abstract: This paper studies the regret analysis for parallel Gaussian process (GP) bandit optimization. The known regret upper bounds for the widely used GP batched upper confidence bound and GP batched Thompson sampling (GP-BTS) suffer from a multiplicative factor with respect to the batch size $Q$. To avoid this degradation, existing analyses require a polynomial number of uncertainty sampling (US) for $Q$ at the beginning of optimization. However, this initial US phase is often ineffective in practice. This paper shows that the regret upper bound without the multiplicative factor on $Q$ can be achieved without the initial US phase, using GP-BTS as an example. Furthermore, we show much better regret upper bounds in the noiseless setting than in the noisy setting, as in the sequential GP bandit setting.
Abstract:This paper studies the regret analysis for parallel Gaussian process (GP) bandit optimization. The known regret upper bounds for the widely used GP batched upper confidence bound and GP batched Thompson sampling (GP-BTS) suffer from a multiplicative factor with respect to the batch size $Q$. To avoid this degradation, existing analyses require a polynomial number of uncertainty sampling (US) for $Q$ at the beginning of optimization. However, this initial US phase is often ineffective in practice. This paper shows that the regret upper bound without the multiplicative factor on $Q$ can be achieved without the initial US phase, using GP-BTS as an example. Furthermore, we show much better regret upper bounds in the noiseless setting than in the noisy setting, as in the sequential GP bandit setting.
Machine Learning (stat.ML); Machine Learning (cs.LG)
arXiv:2608.16492 [stat.ML]
(or arXiv:2608.16492v1 [stat.ML] for this version)
https://doi.org/10.48550/arXiv.2608.16492 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 224 words
Related coverage
ALMAB-DC: Active Learning, Multi-Armed Bandits, and Distributed Computing for Sequential Experimental Design and Black-Box Optimization
arXiv · Jun 5, 2026
Productionizing TurboQuant on AMD GPUs for KV-Cache-Bound LLM Inference
AMD · Jun 11, 2026
[AINews] not much happened today
Latent Space · Sep 18, 2026
Regret Analysis of Retry-Based Bandits
arXiv · Oct 1, 2026