Kernelized bandits, also known as Bayesian optimization (BO), has been a
prevalent method for optimizing complicated black-box reward functions. Various
BO algorithms have been theoretically shown to enjoy upper bounds on their
cumulative regret which are sub-linear in the number T of iterations, and a
regret lower bound of Omega(sqrt(T)) has been derived which represents the
unavoidable regrets for any classical BO algorithm. Recent works on quantum
bandits have shown that with the aid of quantum computing, it is possible to
achieve tighter regret upper bounds better than their corresponding classical
lower bounds. However, these works are restricted to either multi-armed or
linear bandits, and are hence not able to solve sophisticated real-world
problems with non-linear reward functions. To this end, we introduce the
quantum-Gaussian process-upper confidence bound (Q-GP-UCB) algorithm. To the
best of our knowledge, our Q-GP-UCB is the first BO algorithm able to achieve a
regret upper bound of O(polylog T), which is significantly smaller than its
regret lower bound of Omega(sqrt(T)) in the classical setting. Moreover, thanks
to our novel analysis of the confidence ellipsoid, our Q-GP-UCB with the linear
kernel achieves a smaller regret than the quantum linear UCB algorithm from the
previous work. We use simulations, as well as an experiment using a real
quantum computer, to verify that the theoretical quantum speedup achieved by
our Q-GP-UCB is also potentially relevant in practice.

通过引入量子高斯过程 - 置信上界（Q-GP-UCB）算法，我们得到了第一个 BO 算法，可以在经典设置中将遗憾上界压缩为 O（对数多项式级别的 T），明显小于其遗憾下界 Omega（sqrt（T））。

量子贝叶斯优化

Quantum Bayesian Optimization

In recent years methods from optimal linear experimental design have been
leveraged to obtain state of the art results for linear bandits. A design
returned from an objective such as $G$-optimal design is actually a probability
distribution over a pool of potential measurement vectors. Consequently, one
nuisance of the approach is the task of converting this continuous probability
distribution into a discrete assignment of $N$ measurements. While
sophisticated rounding techniques have been proposed, in $d$ dimensions they
require $N$ to be at least $d$, $d \log(\log(d))$, or $d^2$ based on the
sub-optimality of the solution. In this paper we are interested in settings
where $N$ may be much less than $d$, such as in experimental design in an RKHS
where $d$ may be effectively infinite. In this work, we propose a rounding
procedure that frees $N$ of any dependence on the dimension $d$, while
achieving nearly the same performance guarantees of existing rounding
procedures. We evaluate the procedure against a baseline that projects the
problem to a lower dimensional space and performs rounding which requires $N$
to just be at least a notion of the effective dimension. We also leverage our
new approach in a new algorithm for kernelized bandits to obtain state of the
art results for regret minimization and pure exploration. An advantage of our
approach over existing UCB-like approaches is that our kernel bandit algorithms
are also robust to model misspecification.

本研究提出了一种避免连续概率分布到离散分配转化中需要基于维度的限制的舍入过程，以实现线性实验设计和内核化赌博机方面的最优解的研究。