Unverified

Regret Bounds for Noise-Free Kernel-Based Bandits

For the noise-free kernel-based bandit problem above, determine the lowest achievable growth rate of $R(N)$ with the number $N$ of observations, uniformly over all $f\in\mathcal H_k$ with $\|f\|_k\leq C_k$ .

In particular, when $k$ is a Mat{'e}rn kernel with smoothness parameter $\nu>0$ and

R(N)=\widetilde O(N^\alpha),

what is the smallest exponent $\alpha$ achievable by a learning algorithm? Is the following conjectured rate attainable under mild regularity assumptions on $\mathcal X$ ?

R(N)= \begin{cases} O(N^{(d-\nu)/d}),&d>\nu,\\ O(\log N),&d=\nu,\\ O(1),&d<\nu. \end{cases}

Download

Abstract

We consider sequential optimization of an unknown function belonging to a bounded ball of a reproducing kernel Hilbert space, with exact noise-free observations. While cumulative-regret rates are well developed in the noisy setting, directly setting the noise to zero gives loose bounds, and near-optimal simple-regret algorithms may incur linear cumulative regret. The open problem is to determine the lowest possible growth rate of cumulative regret, particularly for Mat{'e}rn kernels of smoothness $\nu$ .

Background and progress

Let $\mathcal X\subseteq\mathbb R^d$ be compact, let $k\colon\mathcal X\times\mathcal X\to\mathbb R$ be positive definite, and let $\mathcal H_k$ be its reproducing kernel Hilbert space. The objective $f$ satisfies $\|f\|_k\leq C_k$ . An algorithm chooses $x_i\in\mathcal X$ , observes $f(x_i)$ exactly, and incurs cumulative regret

R(N)=\sum_{i=1}^N(f(x^*)-f(x_i)), \qquad x^*\in\operatorname*{argmax}_{x\in\mathcal X}f(x).

For noise-free GP-UCB, the known cumulative-regret bound specializes to $\widetilde O(N^{(\nu+d)/(2\nu+d)})$ for a Mat{'e}rn kernel and is always worse than $\sqrt N$ [Lyu et al., 2019]. Simple-regret results for expected improvement imply $O(N^{(d-1)/d})$ cumulative regret when $\nu\geq1$ , while mixing with pure exploration attains optimal simple regret but linear cumulative regret [Bull, 2011]. A simple explore-then-commit construction gives $\widetilde O(N^{d/(\nu+d)})$ . These gaps indicate that noisy-setting analyses are not suited to the noise-free problem.

The source conjectures cumulative regret $O(N^{(d-\nu)/d})$ when $d>\nu$ , $O(\log N)$ when $d=\nu$ , and $O(1)$ when $d<\nu$ , under mild regularity of the domain. The open problem is posed directly in [Vakili, 2022].

Reference papers

Open Problem: Regret Bounds for Noise-Free Kernel-Based BanditsSattar VakiliProceedings of Thirty Fifth Conference on Learning Theory · 2022 ↗
Convergence Rates of Efficient Global Optimization AlgorithmsAdam D. BullJournal of Machine Learning Research · 2011
Efficient Batch Black-Box Optimization with Deterministic Regret BoundsYueming Lyu, Yuan Yuan, Ivor W. TsangarXiv preprint arXiv:1905.10041 · 2019

Regret Bounds for Noise-Free Kernel-Based Bandits

Coming soon

Organizer