๐Ÿ“–
Near-Optimal Regret Bounds for UCB-Style Gaussian Process Bandits via Data Thinning
Shion Takeno, Shogo Iwazaki, Ichiro Takeuchi

Near-Optimal Regret Bounds for UCB-Style Gaussian Process Bandits via Data Thinning

Science & Mathematics Published 2026 Verification Pending

Overview & Synopsis

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.

Indexed from repository: arXiv (arxiv.org)
Loading document from verified source...
Keyboard Shortcuts: ← / → for pages • + / - for zoom • 0 to fit width Powered by Mozilla PDF.js v3.11

Document Information

Document Title Near-Optimal Regret Bounds for UCB-Style Gaussian Process Bandits via Data Thinning
Author / Organization Shion Takeno, Shogo Iwazaki, Ichiro Takeuchi
Subject & Discipline stat.ML
Categories Science & Mathematics
Publication Year 2026
License / Rights arXiv Open Access / Creative Commons
Resource Verification Listed PDF (Verification Pending)
Original Host Website arXiv (arxiv.org)
File Format application/pdf (Portable Document Format)
Language EN
Catalog ID DOC-269976
Original Source Link Visit Source Page on arxiv.org »