Gaussian process upper confidence bound (GP-UCB) is a standard method for optimizing black-box functions, but its theoretical regret guarantees have historically been suboptimal. Near-optimal bounds have mostly come from non-adaptive techniques like uncertainty sampling, which often underperform in practice. The authors propose using data thinning, a statistical method that splits a single dataset into several independent-looking pieces, to give UCB-style algorithms both strong theory and practical utility.
Under a Gaussian noise assumption, they show that data thinning produces tighter confidence intervals in the bandit setting. This allows a direct extension of GP-UCB to achieve a near-optimal simple regret upper bound. When GP-UCB is combined with a phased elimination algorithm, the same tighter intervals lead to a near-optimal cumulative regret upper bound.
The paper also reports numerical experiments demonstrating that UCB-style algorithms with data thinning are effective, not just theoretically attractive. The result suggests that adaptive methods can be competitive with the best non-adaptive regret guarantees, addressing a long-standing gap in the Gaussian process bandit literature.