Near-Optimal Regret Bounds for UCB-Style Gaussian Process Bandits via Data Thinning
Abstract
Gaussian process upper confidence bound (GP-UCB) has been widely studied, though its known regret upper bound is suboptimal. To obtain near-optimal regret upper bounds, existing studies mainly focus on non-adaptive methods, such as uncertainty sampling, whose practical effectiveness is often limited. This paper shows that, under a Gaussian noise assumption, UCB-style algorithms can achieve near-optimal regret upper bounds via data thinning, a statistical technique for creating independent datasets from a single dataset. First, we show that data thinning can yield tighter confidence intervals in the bandit setting, and that a direct extension of GP-UCB achieves a near-optimal simple regret upper bound. Furthermore, by leveraging the tighter confidence intervals and combining GP-UCB with a phased elimination algorithm, we show a near-optimal cumulative regret upper bound. Finally, we demonstrate the effectiveness of UCB-style algorithms incorporating data thinning via numerical experiments.
Related
- Exact Bayes Regret and Asymptotic Optimality in High-Dimensional Gaussian Bandits
- Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary
- Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity
- Near-Optimal First-Order Regret for Bandits with Feedback Graphs
- Nearly Minimax Optimal Regret for Adversarial Linear Bandits with Strong Corruptions
BibTeX
@misc{takeno2026nearoptimal,
title = {{Near-Optimal Regret Bounds for UCB-Style Gaussian Process Bandits via Data Thinning}},
author = {Shion Takeno and Shogo Iwazaki and Ichiro Takeuchi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.28136},
eprint = {2610.28136},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.28136},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Near-Optimal Regret Bounds for UCB-Style Gaussian Process Bandits via Data Thinning
AU - Shion Takeno
AU - Shogo Iwazaki
AU - Ichiro Takeuchi
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2610.28136
UR - https://arxiv.org/abs/2610.28136
AB - Gaussian process upper confidence bound (GP-UCB) has been widely studied, though its known regret upper bound is suboptimal. To obtain near-optimal regret upper bounds, existing studies mainly focus on non-adaptive methods, such as uncertainty sampling, whose practical effectiveness is often limited. This paper shows that, under a Gaussian noise assumption, UCB-style algorithms can achieve near-optimal regret upper bounds via data thinning, a statistical technique for creating independent datasets from a single dataset. First, we show that data thinning can yield tighter confidence intervals in the bandit setting, and that a direct extension of GP-UCB achieves a near-optimal simple regret upper bound. Furthermore, by leveraging the tighter confidence intervals and combining GP-UCB with a phased elimination algorithm, we show a near-optimal cumulative regret upper bound. Finally, we demonstrate the effectiveness of UCB-style algorithms incorporating data thinning via numerical experiments.
ER -