Quantum Bayesian Optimization
Authors: Zhongxiang Dai
Gregory Kang Ruey Lau
Arun Verma
Yao Shu
Bryan Kian Hsiang Low
Patrick Jaillet
Venue: NeurIPS 2023 poster (2023)
Keywords: quantum bandits
kernelized bandits
TL;DR: We introduce the first algorithm for quantum Bayesian optimization, which achieves a regret upper bound of O(polylog T) with the aid of quantum computing.

Abstract: 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 $\mathcal{O}(\text{poly}\log 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.

16 19 32). has been Quantum Bayesian Optimization
Zhongxiang Dai*!, Gregory Kang Ruey Lau*1.2, " Arun Verma', Yao Shu', Bryan Kian Hsiang Low', Patrick Jaillet 'Department of Computer Science, National University of Singapore CCNS @ CREATE, 1 Create Way, #08-01 Create Tower, Singapore 138602 *Department of Electrical Engineering and Computer Science, MIT dzx@nus edu. sg, greglau@come shuyao950u. nus edu, lowkh@comp mus mus.edu..em edu.sg, jaillet@mit. edu edu
edu.sg, arun@comp.
edu. sg,
Abstract
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 cunulative regret which are sub-linear in the number 7 of iterations, and regret lower bound of Q VT) 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-line non-linear reward functions. To this end, introduce the quantum- Gausssann ppocess-uppee confidence bound (Q-GP-UCB) algorithm. To the best of our knowledge, our Q-GP-UCB is the first BO algorithm able to achieve regret upper bound of Oppoly log T), which is significantly smaller than its regret lower bound of ((vT)) in the classical setting. Moreover, thanks to our novel analysis of the confidence ellipsoid, our Q-GP-UCB with the linear kernel achieves 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.
Introduction
Kernelized bandits 9 also named Bayesian optimization (BO) 110
immensely popular method for various applications involving the optimization of complicated black- box reward functions. For example, BO has been extensively used optimize the hyperparameters of 14 22], the parameters of computationally expensive simulators [5). etc. In every iteration 1, 1.... T, BO chooses an arm/input 2; and then queries the reward function ff for noisy observation yr = f(z)) + Se where Ç. is a Sab-Gaussian noise. In addition to its impressive practical performance, BO also equipped with solid theoretical guarantees. number of commonly adopted BO algorithms have been theoretically shown to enjoy sub-linear upper bounds on their cumulative regret
machine learning (ML) models 12
33 which ensures that they are guaranteed to able to find the global optimum of the reward function T (i.e., the total number of function queries) increases. On the other hand, a lower bound of Ω R(VT) (ignoring additional log factors) on the cumulative regret of BO has been shown [31, which represents the fundamental limit of any BO algorithm (in the classical setting). In other words, no classical BO algorithm can achieve cumulative regret smaller than Ω( ((VT). This naturally begs the question:
leverage more advanced technology to go beyond
Equal contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the classical setting and hence break this fundamental limit of Q ((VT)? In this work, we give an affirmative answer by showing that this can be achieved with the aid of quantum computing 34
Quantum bandits, which incorporates quantum computing into bandit algorithms, has been studied by number of recent works [8 3 40 41. Notably, the recent work of (38 has introduced quantum variants of classical algorithms for multi-armed bandits (MAB) and stochastic linear bandits (SLB). the arm Ie (in the classical setting) is replaced by a chance to access a quantum oracle, which encodes the reward distribution for the arm 24. For every selected arm Ttt, [38] has proposed to adopt the quantum Monte Carlo (QMC) algorithm [4] [28] as subroutine to obtain an accurate estimation of fxze in an efficient way, i.e., using a small number of queries to the quantum oracle (Lemma D. As a result, [38] has shown that the regrets of the quantum algorithms for both MAB and SLB are significantly improved compared with their classical counterparts and are smaller than their classical lower bounds. However, both MAB and SLB fall short when optimizing complex real-world functions (e.g., optimizing the hyperparameters of MI. models). This is because MAB unable to exploit the correlations among the arms to model the reward function, and the assumption of linear reward function adopted by SLB is usually too restrictive in practice. Therefore, designing a quantum bandit algorithm capable of optimizing sophisticated non-linear reward functions, which is a critical step towards practically useful quantum bandit algorithms, is still an open problem. In this work, we resolve this open problem by proposing the first algorithm for quantum BO.
In the setting of quantum bandits adopted by [38), every query to the reward function
Similar to (38, in our quantum BO problem setting, queries to the reward function in the classical setting are replaced by access to quantum oracle encoding the reward distribution. As discussed in [8 39 a quantum oracle available when the learning environment is implemented by a quantum algorithm, which makes the setting of our quantum BO fairly general. For example, our quantum BO algorithm may be used to optimize the hyperparameters of quantum ML algorithms 3. such as quantum support vector machines (SVMs) [29], quantum neural networks (NNs) I among others. It may also be used to optimize the parameters of simulators implemented on a quantum computer, or for applications involving quantum systems where the data produced is inherently quantum. Moreover, our quantum BO algorithm could also be applied to classical data and algorithms, because discussed in (39), any classical computer program be converted to quantum circuit, allowing it to serve as a quantum oracle in our quantum BO algorithm.
In this work, we introduce the first quantum BO algorithm: guustunn process-upper confidence bound (Q-GP-UCB). For every selected arm F.., our Q-GP-UCB algorithm (Algo. I adopts the QMC subroutine (Lemma I] to efficiently estimate the corresponding reward function value f' fxx to satisfy a target estimation error c.. Every arm Wg is selected based on our weighted GP posterior distribution, in which every previously selected arm v, is given weight of 1/e² which is inversely related to its estimation error. The theoretical analysis of our Q-GP-UCB is faced with non-trivial technical challenges, and our contributions can be summarized as follows:
We analyze the growth rate of the weighted information gain (Sec. 5.I)) which arises due the use of our weighted GP regression (Sec. 4.1). and show its connection with the standard maximum information gain commonly used in the analysis of BO/kernelized bandits 9 33 Our analysis here may be of broader independent interest for future works adopting weighted GP regression.
We derive a tight confidence ellipsoid which gives guarantee on the concentration of the reward function around the weighted GP posterior mean (Sec. (5.3), and discuss the intuition behind our proof which corresponds to an interesting interpretation about our Q-GP-UCB algorithm. A particularly crucial and novel step in our analysis relies on the recognition to apply the concentration inequality for u-sub-Gaussian noise (Sec. 5.3)
We prove that our Q-GP-UCB achieves a regret upper bound of O(poly log I') for the commonly used squared exponential (SE) kernel (Secs. and which considerably smaller than the classical regret lower bound of 9( B(VT) (1) and hence represents a significant quantum speedup.
By using similar proof technique to the one adopted for our tight confidence ellipsoid (Sec. 5.3
we improve the confidence ellipsoid for the quantum linear UCB (Q-LinUCB) algorithm 38] This improved analysis leads tighter regret upper bound for Q-LinUCB, which matches the regret of our Q-GP-UCB with the linear kernel (Sec.5.6))
We use simulations implemented based on the Qiskit package to verify the empirical improvement of our Q-GP-UCB over the classical GP- UCB and over Q-LinUCB, through synthetic experiment and an experiment on automated machine learning (AutoML) (Sec. 6). Notably, we have also

---

performed an experiment using real quantiam computer, in which our Q-GP-UCB still achieves a consistent performance advantage (Fig. 4 App. !
2 Related Work
A number of recent works have studied bandit algorithms in the quantum setting, The works of g
and (40) have focused on the problem of pure exploration in quantum bandits. [25) has studied a different problem setting where the learner aims to maximize some property of an unknown quantum state (i.e., the rewards) by sequentially selecting the observables (i.e., actions). The recent work of [38] has introduced algorithms for quantum multi-armed bandits (MAB) and stochastic linear bandits (SLB), and has shown that by incorporating the QMC subroutine into MAB and SLB, tight regret upper bounds can be achieved which are better than the classical lower bounds. More recently, the works of [3 and [41 have followed similar approaches to introduce quantum bandit algorithms for, respectively, stochastic convex bandits and bandits with heavy-tailed reward distributions. In addition to quantum bandits, some recent works have introduced quantum reinforcement learning (RL) algorithms. [39] has assumed access to a generative model of the environment and proved that their quantum RL algorithm achieves significantly better sample complexity over their classical counterparts. More recently, [17 43 have removed the requirement for a generative model in quantum RL and achieved quantum speedup in terms of the regret. More comprehensive reviews of the related works quantum RL can be found in recent surveys (c.g., (27]). ). The problem setting of our quantum BO (Sec. 3.2) is the same as many of these monoemmet previous works on However, to the best of our knowledge, none of the existing works on quantum bandits (and quantum RL) is able to handle non-lineat lineir reward functions, which resolve in this work. Over the years, extensive efforts 7 24 330 36) have been made to design BO/kernelized bandit algorithms whose regret upper bounds are small enough to (nearly) match the classical regret lower bound of ((VT) (ignoring additional log factors). Our work provides an alternative route by proving that with the aid of quantum computing, it is possible to achieve tight regret upper bound which is significantly smaller than the classical regret lower bound.
quantum bandits 38 41
and quantum RL 117
39 43
3 Problem Setting and Background
3.1 Classical Kernelized Bandits
A BO/kernelized bandit algorithm aims to maximize a reward function f X' - R where X' C Rd i.e., it aims to find x" E arg max (x) Consistent with the previous works on BO/kernelized bandits [9 (37) we assume that f lies in the reproducing kernel Hilbert space (RKHS) associated with kernel k: f E (X). That is, we assume that [] H. S for B > 0, in which|/-Il H. denotes the RKHS norm induced by the kernel k. Note that unlike previous works on linear bandits [2] our assumption here allows f to be non-linear w.r.t. the input x. In this work, we mainly focus on the widely used squared exponential (SE) kernel: k(z, x²) ف exp(-1l 2 x 1 (2())) in which / is the length scale. We also extend our results to the Matérn kernel in Sec. 5.7 Without loss of generality,
assume that k((,)) -) 1. In the following, we use [t] to denote {1, ......... t) for simplicity.
In every iteration t E [T] of BO, an input 2, is selected, after which a corresponding noisy observation V = =xx,) + Ç, is collected where Ç, is a nub-Gaussian noise (e.g.. bounded noise or Gaussian noise). The inputs x, ' are sequentially selected by maximizing an acquisition function, which calculated based on the Gaussian process (GP) posterior distribution. Specifically, after / iterations, we use the
current history D, A {(11, ((11,1))- 91).... (Xt, vt)) to calculate the GP posterior predictive distribution at I X:: ((, of())) where
(e(x) A E. ( AI) (x(x) A k, + AT) -
(I)
in which (x) A [k(ar, x) and Y, A [ue., IT are column vectors, K, _ [k(x,, arr )r.rre is the t x t covariance matrix, and >= > 1 is a regularization parameter. Based ①.. commonly used acquisition function is GP-UCB 333, which selects the next query by: .2+1 = arg max Ph (x) + (1) where E is parameter carefully chosen to balance exploration and exploitation. The performance of a BO/kernelized bandit algorithm is usually theoretically analyzed by deriving an upper bound on its cumulative regret: Rr Ii=I(("*) [f(x*) - (xx)], and a tighter regret upper bound
an indicator of better theoretical convergence.
3

---

3.2 Quantum Bandits/BO
quantum state (z)) in Hilbert space C" can be expressed as a superposition of n basis states (c.g. qubits) via vector Ø [21.-.... , Fn]", with |x:|? representing the probability of being in the ith basis state. Given two quantum states (2) E C and [y) CTT, use (z)ly) [2131.... ,.......,,........... Fn to denote their tensor product. A quantum algorithm typically works by applying unitary operators to quantum states, and may have access to input data encoded in unitary operators called quantum oracles (examples have been discussed in Sec. D. We defer a more detailed introduction to quantum computing related works dedicated to these topics (e.g.. (66).
Our quantum BO setting follows that of the quantum bandits works in of quantum BO, after an input is selected, instead of observing noisy reward as in classical BO/bandits (.1c. we get a chance to access a quantum unitary oracle O2 and its inverse that encode the noisy reward distribution. Specifically, let Pa denote the reward distribution, Ω2 denote the finite sample space of Pæ. and yy= 22 - R denote the random reward associated with input x. Then, Og is formally defined as:
In every iteration
O+: 10) - EwER, Vp2 ())))(W))
(2)
Quantum mean estimation, which aims to estimate the mean of an unknown distribution with better sample efficiency than classical algorithms, has been a widely studied problem [4].]. Consistent with the works of [38,41], we will make use of the following quantum Monte Carlo (QMC) algorithm:
Lemma (Quantum Monte Carlo (QMC) (28) Let yu 22 - R denote a random variable, Ug is equipped with probability measure Pz, and the quantum unitary oracle O₂ encodes P. and ya-
Bounded Noise: If the noisy output observation satisfies yz E [0, 1}, then there exists a constant
C1 > 1 and QMC algorithm QMC(O,,. 6,8) which returns an estimate Úz of Elya)) such that P(L0- - Eyyz] > c) S 6, using at most C₁ 1og(1/5) queries to O₂ and its inverse.
Noise with Bounded Variance: If the variance of yu < o², then for e < 4a, there exists constant C2 > 1 and a QMC algorithm QMC(O2,, e, which returns an estimate de s.t. P(Lez 3/2
Elyz]1 > c) S 8, using at most Caa
(+e) logg logg(log2 ) log Y/2 queries to O2 and its inverse. logg
The quantum query complexity of quantum algorithm is usually measured by the number of queries to the quantum oracle [3] [88. So, the sample complexities from Lemma| [ can be compared with that of classical Monte Carlo (MC) estimation. In the classical setting. it can be easily shown using concentration inequalities that MC estimation requires O(1ee² samples reach a target mean estimation error of e. Therefore, the QMC algorithm (Lemma 1. which only needs ((1/c) samples, achieves quadratic reduction in the required number of samples. This dramatic improvement is crucial for the quantum speedup in terms of regrets achieved by our algorithm (Sec. 5.4).
During our Q-GP-UCB algorithm, after every input x, is selected, we will apply the QMC algorithm from Lemma with the quantum oracle Oz, to obtain an estimation ys of its reward f(x,) (line 6 of Algo. Of note, the mentroned equivalence between query to the quantum oracle and a sample for classical MC mean estimation implies that a query to the quantum oracle O, in quantum BO/bandits is equivalent to the pulling of an arm x: in classical BO/bandits. Therefore, the cumulative regret Rr of our Q- D-GP-UCB algorithm is defined as the regret incurred after T queries to the quantum oracle, which makes it amenable to comparisons with the regrets of classical algorithms.
4 Quantum Bayesian Optimization
In this section, we first introduce weighted GP regression (Sec. 4.1 which will be used by our Q-GP-UCB algorithm to calculate the acquisition function for input selection, and then describe our Q-GP-UCB algorithm (Sec. 4.2p in detail.
4.1 Weighted GP Posterior Distribution
In contrast to standard GP-UCB 33 which uses the standard GP posterior distribution ( to calculate the acquisition function, our Q-GP-UCB makes use weighted GP posterior distribution. That is, we assign weight to every previous observation. Specifically, after stage of our Q-GP-UCB (i.c.. given D, e {(zr, Vr )+))rrr))))))))))))))))))) )e())), we define the weight matrix W, e diag( 1/e2). W, is

---

an s x diagonal matrix, in which the 7thh diagonal element represents the weight 1/e, given to the 7thh observation (Ir, vr). We will set e, = = - (Sec. 4.2). i... e, is calculated using the weighted GP posterior standard deviation
(conditioned on the first T observations) at Zy.
Define K. [k (T),, which is the s-dimensional covariance matrix given the first observations, and define K, - w K2 K.W: which is the weighted covariance matrix. Similarly, define k; (a) _ [k<2, xx and kg (x) _ (.')k,(xr). Denote the collection of output observa- tions by Y, A [wr]reje) and define Y. _ w With these definitions, given D., our weighted GP posterior distribution an input X' is Gaussian distribution: (x), 03 (x)). in which (x) _ F. (K), + A (x) - k(x, - k._ (x) + (x)).
(3) Note that the GP posterior mean j. above equivalently the solution to the following weighted kernel ridge regression problem: 34, = arg m HH) Σ;= 2 (vz - f(x))) Allfll H2 We give more detailed analysis of the weighted GP posterior (3) in App. A Weighted GP regression has also been adopted by previous works on BO such as [5]. However, our choice of the weights,
algorithmic design and theoretical analyses all require significantly novel treatments.
4.2 Q-GP-UCB Algorithm
Algorithm 1 Q-GP-UCB
1: for stage s = 1,2, do
2: F, arg magmmaxxee0 MM- (z) + 3,
3: Eg = (z.)
4:
(a) No,- C1 log( 2 (for bounded noise), or
2m 5 5: If Ei= No. > T, terminate the algorithm.
(b) No,
log2
3/2 (ee 2 8e log
(for noise with variance bounded by o?).
6: Run the QMC(O,,, e,, )2(m)) algorithm to query the quantum oracle of v, for the next Ne, rounds, and obtain ys as an estimate of f(z.).
7: Update the weighted GP posterior 3 using (Is, Wx).
Our Q-GP-UCB algorithm is presented in Algo. I Q-GP-UCB proceeds in stages. In stage s, we first select the next input x, to query by maximizing the GC-UCB acquisition function calculated using the weighted GP posterior distribution (3) (line 2 of Algo. D Here 3, e B B+ 22(5,-1 + (2g(2
(more details in Sec. 5.3), in which 5 E (0, 2/e] and 7--1 - log(dde(II+ ( + ()) is the weighted
information gain (more details in Sec. 5.1 p. Next, we calculate e, = - (x.)// (line 3) and Ne, (line 4), in which Ne, depends on the type of noise and the value of c.. Here m is an upper bound on the total number m of stages which we will analyze in Sec. [5.2] Subsequently, unless the algorithm is terminated (line 5), we run the QMC algorithm (Lemma to estimate f(x.) by querying the quantum oracle of x, for Ne. rounds (line 6). The QMC procedure returns an estimate y. of the reward function value f(z,), for which the estimation error is guaranteed to be bounded: ly. f(xx)) S 6x with probability of least 1- 6/(2m). Lastly, we update the weighted GP posterior using the newly collected input-output pair (I.,, Us), as well as its weight 1/2; (line 7).
Of note, the value of c, is used for both (a) calculating the number Ne, of queries to the quantum oracle for T.. and (b) computing the weight 1/e² assigned to (I., ys) in the weighted GP regression (3) in the subsequent iterations. Regarding (a), our designs of e, and Ne, = Õ(1/e.) have an interesting interpretation in terms of the exploration-cxploiaaae weighted GP posterior standard deviation (x-1(x)) and hence e, are usually large, which leads to small number Ne, of queries for every x, and hence allows our Q-GP-UCB to favor the exploration of more unique inputs; in later stages, & 0--1 (x,) and e, usually become smaller, which results in a small number of unique inputs. Regarding (b), assigning larger weight 1/e2 to an input I, with a smaller e, is reasonable, because a smaller e, indicates a smaller estimation error for y. as we explained above, which makes the observation y, more accurate and reliable for calculating the weighted GP regression (3).
trade-off: In the initial stages, the
large N,, 's and hence causes our Q-GP-UCB to prefer the exploitation
Note that we have modified the original GP-UCB by querying every selected input vs multiple times, in order to make it amenable to the integration of the subroutine The recent work of (6) has also
5

---

adapted BO to evaluate small number of unique inputs while querying each of them multiple times. has been shown [ that the resulting BO algorithm preserves both the theoretical guarantee (i.e.. the regret upper bound) and empirical performance of the original BO, while significantly reducing the computational cost. So, the findings from [6] can serve as justifications for our modification to GP-UCB. Also note that despite this similarity, [6] still focuses on the traditional setting (i.e., their regret upper bound is Rt OCT and their regret analyses are entirely different from ours.
5 Theoretical Analysis
Throughout our analysis, we condition on the event that [f(x))) -vs S Ea, Vs 1,...,.7 m. This
event holds with probability of at least 1 1 8/22, because we set the error probability in QMC (Lemma
D to 6/(z)) in which 2 m (see Theorem 2 for details). For simplicity, we mainly focus on the scenario of bounded noise (i.e., the observations are bounded within [0, 1]. the first case of Lemma I
because the theoretical analyses and insights about the other scenario of noise with bounded variance (i.e., the second case of Lemma] D are almost identical (more details in Sec. (..5)
5.1 Weighted Information Gain
To begin with, the following lemma (proof in App. BD gives an upper bound on the sum of the weights in all m stages, which will be useful for upper-bounding the weighted information gain 7m-
Lemma 2. Choose å E 20,2/e), then we have that Σ== 1/e, < T
Denote by TT the maximum information gain from any set of T inputs: "T (x.., & log det + KK), which is commonly used in the analysis of BO/kernllized bandit algorithms (9] 33). Denote by Ym the weighted information gain from all m selected inputs in all stages: 7m - log det(T+ 1 Km). Note that in the definition of 7im. we do not take the maximum over all sets of inputs, 7m still depends on the selected inputs Xmm _ {x1...., F' ). Also note that {ei...., } } are known constants conditioned on Xm. This is because the weighted GP posterior standard deviation - (3) does not depend on the output observations, so every C, = 1 (x,)) VA only depends on { J. The next theorem gives an upper bound on 7m..
Theorem 1. (a) Given Xmm A (xi,..., Fmh (b) 7. 5 7r2..
the growth rate of 7 is the same as that r 1/22
We give the complete statement of result (a) in Theorem 8 (App. Cl. which presents the concrete growth rate. As stated by result (a), to obtain an upper bound on 7m. we simply need to firstly use the upper bound on Yr from previous works [35, and then replace the T in this upper bound by
8= m 1/e2. Based on this, the result (b) has further upper--oundee Σ 1/22 by T22 through Lemma
2 Note that because e, v.- (z_1(2,)/V3 < 1, we have that 1/e² e=1
and hence Σm 1/e, > m. Therefore, our weighted information gain 7/m. has a looser upper bound than Yin- This intuitively
implies that our weighted covariance matrix Km is expected to contain more information than the original Km. whose implication will be discussed again in Sec. 5.2 The proof of Theorem (App. has followed the analysis of the information gain from [35]. Specifically, we have leveraged a finite- dimensional projection of the ciinitt-dimeniional RKHS feature space, and hence upper-bounder the information gain in terms of the tail mass of the eigenvalues of the kernel k. The proof requires carefully tracking the impact of the weights 1/2, throughout the analysis. Importantly, our Theorem aand its analysis may be of wider independent interest for future works which also adopt weighted GP regression (Sec. [4....
The growth rate of yr has been characterized for commonly used kernels 35 Based on these, the next corollary provides the growth rates of 7m for the linear and squared exponential (SE) kernels.
Corollary 1. For the linear and squared exponential (SE) kernels, we have that linear kernel,
Fm Od E
1/2) = log 7m Ollg d+1 ETh 1/() = (Olg T)d+1)
SE kernel.
5.2 Upper Bound on The Total Number m of Stages
The next theorem gives an upper bound on the total number of stages of our Q-GP-UCB algorithm.

---

Theorem 2. For the linear kerne,, our Q-GP-UCB algorithm has at most m Od T) stages. For the SE kernel, our Q-GP-UCB algorithm has most m O(log T) )) stages.
Note that for the linear kernel, our upper bound on m matches that of the Q-LinUCB algorithm from [38] (see Lemma 2 from (38). The proof of Theorem 2 is given in App. D and here we give a brief sketch of the proof. For stage define V, _ X/ + which ((-) is the (potentially
in RKHS feature mapping: k(x,z') d(x) o(x). Intuitively, log det V, represents the amount of information contained in the first selected inputs {Z1:- }. As the first step in our proof, we prove that thanks to our choice of 6, (line 3 of Algo. and our design of the weights 1/e2. the amount of information log det V, is doubled after every stage: det V++1= 2 det V,, VT 0, ....., 1. This allows to show that m log 2 = where V/- AZ. Next, we show that this term is also related to our weighted information gain: log(det (V,det((,,,) (Vm)) d/l)/(e)))))))))))))))))))))))))
(w.)
25m.. which allows us to upper-bound m in terms of I'm and hence in terms >x=1 1/e3 (see Corollary []. This eventually allows us to derive an upper bound on by using the fact that the total number of iterations (i.e., queries to the quantum oracles) is no larger than T. Therefore, the key intuition of the proof here is that as long as we gather a sufficient amount of information in every stage, we do not need large total number of stages.
5.3 Confidence Ellipsoid
The next theorem proves the concentration of ʃ around the weighted GP posterior mean 3
Theorem 3. Let 17 _ 2/T, X ê 1 ++1 17, and Bg a + 22(7--1 + 1+ log(2/8)). We have with probability of at least 1 5/2 that
[f(x) - (x)) S (,))
Va E [m], X
The proof of Theorem 3 is presented in App. and here we give brief proof sketch. Denote by F--1 the o-algebra J, = {ai,.... Uaa Cl...rs 6a-13 where CA = 4/ - (xrx) ) is the noise. 1/c,) (Sec. 4.1), and define S1:a - [S))ke(s)- In the first part of
Recall that W-!²² _ (iag(1/<(.-
the proof, we use the RKHS feature space view of the weighted GP posterior (see App. (A) to upper-bound [f(x) - - (z)] in terms of (z) and ||W!! (I:ell(((.+n)))
1+) 1- Next, the most crucial step in the proof is upper- -huurd ||W (1==ll(,,+ -1)))-1))))) in terms of if by applying the eelf-normalized concentration inequality from Theorem of [9] I-sub- Gaussian noise. This feasible because (a) every 6, 00-1(z.)/ -- --esuurra....... and (b) conditioned on Fs,1+
-
the scaled noise term Se/Cz (in w (1:)) (!')' is L-sub-Gaussinn only depends on { } as we have discussed in 5.c. The statement (b) follows since our QMC subroutine ensures that every noise term S& is bounded within [-<R, fa.] (Sec. 4.2) because lyk= - ff(x)) & 6 (with high probability). This suggests that conditioned on Fs-1 (which makes 6, a known constant as discussed above), Ça/e, is bounded within [-1, 1] and is hence I-sub-Gaussian.
The statement (a) follows because e,
This critical step in the proof is in fact also consistent with an interesting interpretation about our algorithm. That is, after v, is selected in stage s, we adaptively decide the number Ne, of queries to the quantum oracle in order reach the target accuracy e, (line 4 of Algo. D This ensures that 13.- - fxx)) $ c (with high probability), which guarantees that the noise S. ye - f(x.) is (conditionally) E,-sub-Gaussian. Moreover, note that the vector of observations Y, used in the calculation of the weighted GP posterior mean 33) is Y, = W So, from the perspective of the weighted GP posterior (3), every noisy observation Ve- and hence every noise Cer is multiplied by 1/c,- So, the effective noise of the observations Y, used in the weighted GP posterior (i.e., (s/c,) is ca/c, = 1-sul-Gauussiee Gaussian. This shows the underlying intuition as to why our proof of the concentration of the reward function f using the weighted GP regression can make use of Suub-Gaussian noise (e.g.. in contrast to the o-sub-Gaussian noise used in the proof of classical GP-UCB 1
Our tight confidence ellipsoid around ff from Theorem 3 is crucial for deriving tight regret upper bound for our Q-GP-UCB (Sec. [54]. Moreover, as we will discuss in more detail in Sec. 5.6 our proof technique for Theorem 3 interestingly, can be adopted to obtain a tighter confidence ellipsoid for the Q-LinUCB algorithm from [38] and hence improve its regret upper bound.
5.4 Regret Upper Bound
Here derive upper bound on the cumulative regret of our Q-GP-UCB algorithm.
7

---

Theorem 4. With probability of at least 1 6, we have that"
Rr = O (2 (log // 2 log log 7)) RT = O ( (log T) 3(d+1)/2 log (log T))+1))
linear kernel,
SE kernel.
The proof of Theorem is presented in App. F The proof starts by following the standard technique
in the proof of UCB-type algorithms to show that r, = f(x²) f(x)) I 2,3,5,-1 . (x,). Next, importantly, our design of 6s = J.- (x,1( (xxss/vv allows us to show that rs S 23 After that, the total regrets incurred in a stage s can be upper-bounded by N., x 2,3cc, Vx = OC,, log(m/6) x (,6,) = Og3, log (mg))))) Lastly. the regret upper bound follows by summing the regrets from all m stages. Of note, for the commonly used SE kernel, our regret upper bound of the order (poly log T"), which is significantly smaller than the regret lower bound of (2( in the classical setting shown by [3I] This improvement over the classical fundamental limit is mostly attributed to the use of the QMC (Lemma D. i.e. line 6 of Algo. I If the QMC procedure is replaced by classical MC estimation, then in contrast to the Ne, = (1, queries by QMC, every stage would require Nr = ((1=2.) queries. As a result, this would introduce an additional factor of 1/c, the total regrets in stage (as discussed above), which would render the derivation of our regret upper bound (Theorem q invalid. This verifies that our tight regret upper bound Theorem 4 is only achievable with the aid of quantum computing. Our Theorem is a demonstration of the immense potential of quantum computing to dramatically improve the theoretical guarantees over the classical setting.
Importantly, when the linear kernel is used, the regret upper bound of our Q-GP-UCB is in fact better than that of the Q-LinUCB algorithm from 38 This improvement arises from our tight confidence ellipsoid in Theorem 3] In Sec. S.c.5.66 we will give more detailed discussion of this improvement and adopt our proof technique for TheoremB3] to improve the confidence ellipsoid for Q-LinUCB, after which their improved regret upper bound matches that of our Q-GP-UCB with the linear kernel.
5.5 Regret Upper Bound for Noise with Bounded Variance
Here we analyze the regret of our Q-GP-UCB when the variance of the noise is bounded by o², which encompasses common scenarios including o-sub-Gaussian Gaussian noises and Gaussian noises with a variance of o². Consistent with the analysis of Q-LinUCB [38]. in order to apply the theoretical guarantee provided by QMC (Lemmal) IT for noise with bounded variance, here we need to assume that the noise variance is not too small, i.e., we assume that a > 1/4. In this case of noise with bounded variance, the following theorem gives an upper bound on the regret of our Q-GP-UCB.
Theorem 5. With probability of at least 8, we have that
Ry = 0 (odd (T) 8/2 log T) (log2 oT) 3/2 log, (log2 oT))
linear kernel,
R1 (a (()(0)))))((+1)//212 log (log T) d (log, s/ log, (log, oT)) SE kernel.
The proof of Theorem 5 is given in App. G Note that same as Theorem 4 the regret for the SE kernel in Theorem 5 is also of the order (pooly log which is also significantly smaller than the classical regret lower bound of 52( / T) [31) Moreover, Theorem 5 shows that for both the linear kernel and SE kernel, the regret of our Q-GP-UCB is reduced when the noise variance o2 becomes smaller.
5.6 Improvement Quantum Linear UCB (Q-LinUCB)
As we have mentioned in Sec. 5.4 the regret upper bound of our Q-GP-UCB with the linear kernel is RT = (Io Ty log which is better than the corresponding Rt = (log 3/2 log(d d log T)) for Q-LinUCB 38 by a factor of ((vd). This improvement can be attributed to our tight confidence ellipsoid from Theorem 3 Here, following the general idea of the proof of our Theorem 3 we prove a tighter confidence ellipsoid for the Q-LinUCB algorithm, i.e., we improve Lemma 3 from the work of (38) Here we follow the notations from 38, and defer the detailed notations, as well as the proof of Theorem 6 below, to App. H due to space limitation.
'We have omitted the dependency on log(1/5) /6) for simplicity. Refer to App. for the full expression.
This is the high-probability regret (rather than expected regret) from 38). which we focus on in this work.
8

---

Theorem 6 (Improved Confidence Ellipsoid for (8))
With probability of at least 1 6,
8" Ec, = R² - s
s( 2dlog (1 (V2dlog
L2
Σ km
+ VAS), As E [m].
A
2
Note that the size of the confidence ellipsoid from our Theorem is of the order O( D(vdlog(Ziz) 1 (V (we have used Lemma 2 here), which improves
the (sv = dm = Of / To = Oody from Lemma 3 of [38] by a factor of vd. Plugging in our tighter confidence ellipsoid (Theorem into the regret analysis Q-LinUCB,
log log T)) (more details at the end of App. H). This improved regret upper bound exactly matches that of our Q-GP- UCB with the linear kernl (Theorem 4). Similar to Theorem the most crucial step in the proof of Theorem i to apply the self-normalizee concentration inequality from Theorem of [2] to I Gaub-Gaussinn noise. Again this is feasible because 6, = (x.) V Fs- -easurable, and conditioned on F, the scaled noise Ca/C, is
the regret upper bound for Q-LinUCB is improved to Rt (d8/22
log Odd
5.7 Regret Upper Bound for the Matérn Kernel
So far we have mainly focused on the linear and SE kernels in our analysis. Here we derive regret upper bound for our Q-GP-UCB algorithm for the Matérn kemnel with smoothness parameter v. Theorem (Matérn Kemel, Bounded Noise).
With probability of at least 1 - 8, we have that
RT ((r3d/1204d))
The proof is in App. I Note that the state-of-the-ar regret upper bound for the Matérn kernel
in the classical setting is Fr O(vTTr) = Ö(T(v-))((2vtd)) 7 24 the corresponding classical regret lower bound (up to logarithmic factors in T) 355 Therefore,
30
36
which matches
the regret upper bound of our Q-GP-UCB for the Matérn kernel (Theorem 7 improves over the
corresponding classical regret lower bound when > 2d, i.e., when the reward function sufficiently smooth. Also note that similar to the classical GP-UCB [33] (with regret Rt = O(TvVT) ((T(043d/2)/22444 )) which requires the reward function to be sufficienlly smooth (i.e., v > 4/2) to attain sub-linear regrets for the Matérn kernel, our Q-GP-UCB, as the first quantum BO algorithm. also requires the reward function to be smooth enough (i.c., >> d) in order to achieve a sub-linead regret upper bound for the Matérn kernel. We leave it to future works further improve our regret upper bound and hence relax this requirement for smooth functions.
6 Experiments
We use the Qiskit python package to implement the QMC algorithm (Lemma d following the recent work of (20). Some experimental details are deferred A space limitation.
Synthetic Experiment. Here we use a grid of X = 20 equally spaced points within [o. 1 as the 1-dimensional input domain X' (d 1), and sample function f from a GP prior with the SE kernel. The sampled function ff is scaled so that its output bounded within [0, 1]. and then used as the reward function in the synthetic experiments. We consider two types of noises: (a) bounded noise (within [o, 1)) and (b) Gaussian noise, which correspond to the two types of noises in Lemma [ respectively. For (a) bounded noise, we follow the practice of 38 such that when an input selected, we treat the function value f(x) as the probability for a Bernoulli distribution, i.e., we observe an output of with probability of (z) and otherwise. For (b) Gaussian noise, we simply add zero-mean Gaussian noise with variance o² to fzx) The results for (a) bounded noise and (b) Gaussian noise are shown in Figs. D (a) and (b), respectively. The figures show that for both types of noises, our Q-GP-UCB significantly outperforms the classical baseline of GP-UCB Specifically, although our Q-GP-UCB incurs larger regrets in the initial stage, observations provided by the QMC subroutine to rapidly find the global optimum. These results show that the quantum speedup of our Q-GP-UCB in terms the tighter regret upper bounds (Theorems and 5) may also be relevant in practice. We have additionally compared with linear UCB (LinUCI) ( and Q-LinUCB [38], which are, respectively, the most representative classical and quantum linear bandit algorithms. The results in Fig. 2 (App. show that in these experiments where the reward
able to leverage the accurate

---

ochize
30
Comulnitte 40
300
Cumulille
200
20
3100
66
10000
4000
4000
3030
100K
1000
2050
3000
4050
S00:
2000 3000 4000 5000
Rerations
Reratoins
Ronxions
Iteratons
(a) synthetic (Bernoulli) (b) synthetic (Gaussian)
(c) AutoMI
(d) AutoMI
Figure 1: Cumulative regret for synthetic experiments with (a) bounded noise and (b) Gaussian noise.
(c) Cumulative regret for the AutoML experiment: (d) additionally includes results for linear bandits.
function is non-linear, algorithms based on linear bandits severely underperform compared with BO/kernelized bandit algorithms in both the classical and quantum settings.
AutoML Experiment. In our experiments on automated machine learning (AutoML). we use our Q-GP-UCB algorithm to tune the hyperparameters of an SVM for classification task. Here consider a Gaussian noise with a variance of o² since it is more practical and more commonly used in real-world experiments. The results in Fig. (c) show that our Q-GP-UCB again significantly outperforms the classical GP-UCB. Fig. (d) additionally shows the comparisons with LinUCB and Q-LinUCB. The results again corroborate that BO/kernelized bandit algorithms are considerably superior in real-world applications with highly non-linear reward functions in both the classical and quantum settings. These results here further demonstrate the potential of our Q-GP-UCB lead to quantum speedup in practical applications.
More Realistic Experiments. We have additionally tested the performance of our Q-GP-UCB algo- rithm after accounting for the effect of quantum noise, by incorporating into our Qiskit simulations noise model based on the actual performance of real IBM quantum computers. The results (Fig in App. J show that although the addition of quantum noise slightly deteriorates the performance of our EGP-UCB, it is still able significantly outperform classical GP-UCB. Notably, we have additionally performed an experiment using a real quantum computer (details in App. [J. in which the performance of our Q-GP-UCB, although further worsened compared to the experiment using simulated noise, is still considerably better than classical GP-UCB (Fig. 4 App.J). Also note that the work of (38 has not shown that Q-LinUCB outperforms LinUCB in the presence of simulated quantum noise. Therefore, the consistently superior performances of our Q-GP-UCB over GP-UCB with both simulated quantum noise and real quantum computer serve as important new support for the potential practical ad advantages of quantum bandit algorithms.
Discussion. In our experimental results (e.g., Fig. D. our Q-GP-UCB usually has relatively larger regrets in the initial stages but quickly achieves zero regret thereafter (i.e., the curve plateaus), which has also been observed in 38 for the Q-LinUCB algorithm. This is because in the initial stages, our Q-GP-UCB explores a smaller number of unique arms than GP-UCB. However, after the initial exploration, our Q-GP-UCB quickly starts to perform reliable exploitation, because the accurate reward observations achieved thanks to our QMC subroutines allow us to rapidly learn the reward function and hence find the optimal arm.
7 Conclusion
We have introduced the first quantum BO algorithm, named Q-GP-UCB. Our Q-GP-UCB achieves regret upper bound of O (poly log T), which is significantly smaller than the classical regret lower bound of ((VT). A limitation of our work is that the regret upper bound of our Q-GP-UCB: ((lg 7))((++))2 (ignoring polylog factors) has a worse dependency on the input dimension than the regret of the classical GP-UCB: O(log Ty vT). A similar limitation is shared by Q-LinUCB, since its regret has a dependency of O (22/2) in contrast to the (dd) of LinUCB. It is an interesting future work to explore potential approaches remove this extra dependency on d. Another limitation of our work is that for the Matérn kernel, we require the reward function to be smooth enough in order achieve sub-linear regret upper bound (Sec. (.7). So, another important future work is to further tighten the regret upper bound of our Q-GP-UCU for the Matérn kernel when the reward function less smooth, as well as for other kernels encompassing non-smooth functions such as the neural tangent kernel which has been adopted by recent works on neural bandits [13 42 44). Moreover, another interesting future work is to derive regret lower bounds in our setting of quantum kernelized bandits, which can help evaluate the tightness of our regret upper bounds.
10

---

Acknowledgements and Disclosure of Funding
This research/project is supported by the National Research Foundation, Singapore under its AI Singapore Programme (AISG Award No: AJSG-PhD/2023301-0339) DesCartes: this research is supported by the National Research Foundation, Prime Minister's Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme.
References
[1] A. Abbas, D. Sutter, C. Zoufal, A. Lucchi, A. Figalli, and S. Woerner. The power of quantum neural networks. Nature Computational Science, 1(6):403-44) 4093 2021.
[2] Y. Abbasi-Yadkond D. Pál, and Szepesvári. Improved algorithms for linear stochastic bandits.
In Proc. NeurlPS, volume 24, 2011.
[3] J. Biamonte, Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd. Quantum machine learning. Nature, (99(7771):115-222
202, 2017.
[4] G. Brassard, P. Hoyer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation.
Contemporary Mathematics, 305:53-74 2002.
[5] S. Cakmak, R. Astudillo Marban, P. Frazier, and E. Zhou. Bayesian optimization of risk measures. In Proc. NeurIPS, volume 33, pages 20130-20141, 2020.
[6] D. Calandriello, L. Carratino, A. Lazaric, M. Valko, and L. Rosasco. Scaling Gaussian process optimization by evaluating a few unique candidates multiple times. In Proc. ICML, pages 2523-2541. PMLR, 2022.
[7] R. Camilleri, K. Jamicson, and J. Katz-Samuels. High-dimensional experimental design and kernel bandits. In Proc. ICML, pages 1227-1237. PMLR, 2021.
[8] B. Casalé, G. Di Molfetta, H. Kadri, and L. Ralaivola. Quantum bandits. Quantum Machine Intelligence, 2:1-7, 2020.
[9] R. Chowdhury and A. Gopalan. On kernelized multi-armed bandits. Proc. ICML., pages 844-853, 2017.
[10] Z. Dai, B. K. H. Low, and P. Jaillet. Federated Bayesian optimization via Thompson sampling. In Proc. NeurlPS, 2020.
[11] Z. Dai, B. K. H. Low, and P. Jaillet. Differentially private federated Bayesian optimization with distributed exploration. In Proc. NeurIPS, volume 34, 2021.
[12] Z. Dai, Y. Shu, B. K. H. Low, and P. Jaillet. Sample-then-optinin batch neural Thompson sampling. In Proc. NeurIPS, 2022.
[13] Z. Dai, Shu, A. Verma, X. Fan, K. H. Low, and Jaillet. Federated neural bandits. In Proc. ICLR, 2023.
[14] Z. Dai, H. Yu, B. K. H. Low, and P. Jaillet. Bayesian optimization meets Bayesian optimal stopping. In Proc. ICML., pages 1496-1506, 2019.
[15] Y. Deng, X. Zhou, B. Kim, A. Tewari, A. Gupta, and N. Shroff. Weighted Gaussian process bandits for non-stationary environments. In Proc. AISTATS, pages 6909-6932. PMLR, 2022.
2018. [17] B. Ganguly, Y. WU, D. Wang, and V. Aggarwal. Quantum computing provides exponential regret improvement in episodic reinforcement learning. arXiv:2302.088: 006617...81,.... 2023.
[16] P. Frazier. A tutorial on Bayesian optimization. arXiv preprint
[18] S. Garg and G. Ramakrishnan. Advances in quantum deep learning: An overview. arXiv preprint arXiv:2005.0433 2020.
[19] R. Garnett. Bayesian Optimization. Cambridge Univ. Press, 2022.
[20] D. Grinko, J. Gacon, C. Zoufal, and S. Woerner. Iterative quantum amplitude estimation. npj
Quantum Information, 7(1):52, 2021.
[21] I.. K. Grover. A framework for fast quantum mechanical algorithms. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 53-62, 1998.
[22] Hutter, L.. Kotthoff, and Vanschoren. Automated machine learning: methods, systems, challenges. Springer Nature, 2019.

---

[23] T. Li and R. Zhang. Quantum speedups of optimizing approximately convex functions with applications to logarithmic regret stochastic convex bandits. In Proc. NeurIPS, 2022.
[24] Z. Li and J. Scarlett. Gaussian process bandit optimization with few batches. In Proc. AISTATS, pages 92-107. PMLR, 2022.
[25] J. Lumbreras, E. Haapasalo, and M. Tomamichel. Multi- aumti-armed quantum bandits: Exploration
versus exploitation when learning properties of quantum states. Quantum, 6:749, 2022.
[26] A. Messiah. Quantum mechanics. Courier Corporation, 2014.
[27] N. Meyer, C. Ufrecht, M. Periyasamy, D. D. Scherer, A. Plinge, and C. Mutschler. A survey on quantum reinforcement learning. arXiv:2211 1. .03464, 2022.
[28] A. Montanaro. Quantum speedup of Monte Carlo methods. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 47 471(2181)2015533011 2015.
[29] Rebentrost, M. Mohseni, and S. Lloyd. Quantum support vector machine for big data classification. Physical review letters, 113(13):130503, 2014.
[30] S. Salgia, S. Vakili, and Q Zhao. A domain-shrinking based Bayesian optimization algorithm with order-optimal regret performance. In Proc. NeurIPS, volume 34, pages 28836-28847, 2021.
[31] Scarlett, I. Bogunovic, and V. Cevher. Lower bounds on regret for noisy Gaussian process bandit optimization. In Proc. COLT, pages 1723-1742. PMLR, 2017.
[32] B. Shahriari, K. Swersky, Z. Wang, R. P. Adams, and N. de Freitas. Taking the human out of the loop: A review of Bayesian optimization. Proceedings of the IEEE, 104(1):148-I1) 2016.
[33] N. Srinivas, A. Krause, S. M. Kakade, and M. Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proc. ICML, pages 1015-1022, 2010.
[34] A. Steane. Quantum computing. Reports on Progress in Physics, 61)) 1998.
[35] S. Vakili, K. Khezeli, and V. Picheny. On information gain and regret bounds in Gaussian process bandits. In Proc. AISTATS, pages 82-90. PMLR, 2021.
[36] M. Valko, N. Korda, R. Munos, I. Flaounas, and N. Cristianini. Finite-time analysis of kernelised contextual bandits. In Proc. UAI, 2013.
[37] A. Verma, Z. Dai, and B. K. H. Low. Bayesian optimization under stochastic delayed feedback. PMLR, 2022.
In Proc. ICML, pages
[38] Z. Wan, Z. Zhang, T. Li, J. Zhang, and X. Sun. Quantum multi-arme -rrmed bandits and stochastic linear bandits enjoy logarithmic regrets. In Proc. AAAI.
[39] D. Wang, A. Sundaram, R. Kothari, A. Kapoor, and M. Roetteler. Quantum algorithms for reinforcement learning with a generative model. In Proc. ICML, pages 10916-10926. PMLR, 2021.
[40] D. Wang, X. You, T. Li, and A. M. Childs. Quantum exploration algorithms for multi-armed bandits. In Proc. AAAI, volume 35, pages 10102-100 101 10, 2021.
[41] Y. Wu, C. Guan, V. Aggarwal, and D. Wang. Quantum heavy-tailed bandits. arXiv:2301.0968) 2023.
[42] W. Zhang, D. Zhou, L. Li, and Q Gu. Neural Thompson sampling. In Proc. ICLR, 2021.
[43] H. Zhong, J. Hu, Y. Xue, T. Li, and L. Wang. Provably efficient exploration in quantum reinforcement learning with logarithmic worst-case regret. UrXiv:2302.10796 2023.
[44] D. Zhou, L. Li, and Q Gu. Neural contextual bandits with UCB-based exploration. In Proc.
ICML, pages 1 11492 150.. PMLR, 2020.
12

---

A Analysis of the Weighted GP Posterior (3)
Here we show an alternative view of the weighted GP posterior distribution (3) in the RKHS feature space. The notations in this section will be extensively used in the theoretical analyses in the subsequent sections.
We denote the kernel k by k(x,,') dimensional feature mapping of x the RKHS of k. Define + - [o(x)),.... ,(x))] which is an 8 x do matrix. Recall that we have defined W _ diag( c) ................................ 1) which is an 8 x s diagonal matrix. Define V, A A + ((x))) = AI + o W.D, which is an o0 x co matrix, and let Vi A AI. With these notations, it can be easily verified that K, 2,0, = [k(z,, Z " and K, W $. W! w./ K2 W! Moreover, we can also easily show that (x) = (()() = [k(z, z, 1I........ (x) = 1y = w:! and Y. w!/
(<x)) in which ((x) is the potentially infinite-
We start by deriving an alternative expression for the weighted GP posterior mean 76, (2)). To begin with, we have that
4 ( + +1) = 2-_
W + +))
- w//2 \Φ w/!/
W., W21/2
= V.
Now multiply both sides by V. on the left and by (K, + A1) on the right, which leads to
V. T _ W3/2 W.! / + AT)-
Now we can show that
(x(x)= o V 4. W,W,Y o(x) $ w (K2 X1) w/!-y =k + -
Next, we derive an alternative expression for the weighted GP posterior variance (2). To begin with, have that
W + D. 2
W-
1 w. 1
W,
(5)
w!!? 1 W1/20 $. T
W3/2
= sw!!/ (Y1 (Nt + (u.K)) w//²
This allows to show that
xz( {σ(x) V, 6(x)
= {x(x) (A + 4-_ W.b.) W,bb)-1o(a))
(a) ^d(x) T (+1- 1 (WW,
(W, + 2
-T )
-10
1
d(x)
=(x) [(())=)))))))))()))) 6(x) :. (W,1
1
T)
-1 o ((x)
1
)
① o(x) T (xx) M(x) T. W!/
(AT+ K.)
(X)
= k(x x) k (k) + -
in which have used the matrix inversion lemma in step (a), and used equation 5 in step (b). To summarize, we have derived the following alternative expressions for the weighted GP posterior distribution
(x) 6(x) ".T........ = (z) + - (2(xx) = TV ((x) = k(x,x) FJ (z) + A1) -R,
(6)
13

---

B Proof of Lemma 2
To begin with, we can lower-bound the total number of iterations (i.e., the total number of queries to the quantum oracles) in m stages by
Ci
2m
log(
Ex
2
The first inequality follows since C > 1 (Lemmal and log( (x)) 2 log(
2 because we have
chosen 5 E (0, 2/e]. Suppose that Ex= 2े > T2, then we have that > 2x=1 is a contradiction. Therefore, we have that
C. log
2m
>
which
5
m
T
(8)
C Proof of Theorem
Here we prove the growth rate of 7m i.e., the weighted information gain. Recall that Wm and 7m = 2 log det [ K-m Rm) Our proof here follows closely the proof of Theorem 3 from the work of [35]. We will omit the subscript as long the context is clear.
diag cf .g...... em
Denote by Km 2m = [k(2,, Zzy =k).kj.i...... the m x m covariance matrix, and define w w w Following Theorem 1 from 35 our kernel can be Ex= (r)) in which {
K = W f Fm $ m denoted as k( x²) respectively, the eigenvalues and eigenfunctions of the kernel k. We will make use of the projection onto D-dimensional RKHS (D < s0), which consists of the first D features corresponding to the D largest eigenvalues of the kernel k. Specifically, define kp as the D-dimensional projection in the RKHS of k; and ko corresponds to the orthogonal element such that k(:,)) kp(,-) -) ko )). That is, following Section 3.2 from the work of [35], define
and [ represent,
D kp(2,x))= = Σ (z)
(9)
We define Kp A [kr(a;, (r)lg,,,, and Ko A ( Jy)).......... Similarly, define Kr w KpW!l/² 1/2 and Ko w 1/2 Ko This implies that Km Kp + Ko and that Km.
Kp Ko.
Here to be consistent with 355, we use Im to denote the m x m-dimensional identity matrix. Denote by T(ym; f) the information gain about the function f from the observations ym = [y1,..., ym)
We have that
1
I(ymi f) = log det
Im +
2 Km
(Kp + Ko))
=
2 log det
Im
+ x
2 log det
1 [ (R))
Im + 1
1
Im + tkp)
-1
Ko
(10)
=
1 Kp
1
Im 1 ( Im
-1
Ko )o).
log det
Im
+
+
log det
Kp
2
X
The last line follows because det (AB) det (A) det (B). In the following, we will separately upper-bound the two terms in (10).
14

---

We start by upper- upper-boundee bounding the first term in equation (TO). Denote by 2 ))(()) the D-dimensional feature vector corresponding
the first D principle features of the kemel (i.e., the features corresponding to the largest D eigenvalues). Define WD - (() & (f()m) which an m x D matrix. Denote by AD = ... ÅD) D x D-diagonal matrix whose diagonal entries consist of the largest D eigenvalues of the kernel k in descending order. With this definition, we have that Kp = V// mm DA D and
Kp w 4 m. DD V W W
Kp=Wh//2
(11)
Also define the gram matrix:
T. =A v n. Wm, v Am 1/2
(12)
Based on these definitions, we have that
1 II +
1 x (kp) 2 am det Im +
det
(13)
which follows from the Weinstein-Aronszaji identity: det (ID + AAT) det (Im + A A) for a D x m matrix A, and we have plugged in A = 7x 1/2 A/ m.
1/2 In addition, the following
inequality will also be useful in the subsequent proof:
Ab [ = Σ (x))())) = ()( S k(x, S 1,
(14)
in which we have made use of the definition of kp from 9 and our assumption (w.l.o.g.) that ='x,,') S 1, Vr, (Sec. 3.I.. In the following, we will denote the trace of matrix A by Tr(A).
Next, we have that
Tr In
+
- G
= D +
- Tr (Gm
1
X
X
D Tr
1
(Al²"T
WT F W V DA!²)
(0) D+
Tr
A
1/2
m
A!2
D + - TT
1
m 1
D
1/2
4/ D (T.
14b (b.))
DD
Tr A
1/2 2
(15)
( D+
(D( 1/2 {12
D+
Σ
v
T
F. A
1/2
D
A 1/2
3 (Ix) ?
(4)
2 D+
Σ
in which (a) follows because v T cyclic property of the trace operator, and (c) follows from [4 above.
m, W', Mn = Emh 1 (x.) (b)
has made use of the
15

---

Also note that for positive definite matrix P E R we have that
(r(P)
log (egdel()) S n log
(16)
Therefore, we have that
log dot (Im
1 IIm
X kr)
logdet
1 (ID -
[D
X
1 + x
- 2
1 m
(17)
D log
log
1
XD
2
The first equality follows from
(3). and the inequality results from [6 and (15).
Now we upper-bound the second term equation (TO). To begin with, we have that
Tr (4m + 1 Kr
(Kr)
Ko
S Tr (Ro).
(18)
which is because the matrix (Im + 1 {Kp)
positive semi-definite (PSD) whose largest eigenvalue is upper-hounded by 1, and Tr( Tr(P; P2) >r; Tr(P2) where Pi and P3 are PSD matrices and Xp, is D dr where (o+ S 1,, Var, T. Then immediately have that (o x²) DT=D+1 d o (x)) s dD. Vx, x'. Therefore, we have that
the largest eigenvalue of Pt. Next, define 8D
m
Tr (o)) = Σ ko (Is vx)) S 6n
(19)
As result, we have that
(1mm Im
Tr mm
+
+
Kp
Ko
S m +
8D
(20)
in which the inequality follows from
18) and
Next, again making use of equation we have that
16 and incorporating the upper bound on the trace from
20
log det
4m + x
((1 Im
+ 1 x
kPp
Ko
I m log
m + AOD E 2
8p 1
< m log
mX
(21)
8D
m
m
m
2
m
8D
X
in which the second last step is because log(1 + 2) < 2, Vz E. Finally, combining the upper bounds from 17 and
equation
TOP
can be upper-bounded by
i(ymi < 2
D log
1==1 T 1+
+ 2
m
ip
(22)
DA
2
X
Therefore, we have that
Σm +
5m I(ymi f) =
2 log det
1
Im +
1 km
<
D log(1 +
+
Σ
1
(23)
DA
x=1
16

---

Also recall that for the standard unweighted maximum information gain Yr, we have that 35
log(1 [T ( k +xtr S Dog
T DX
YT 2 log det
(24)
Therefore, the upper bound on the weighted information gain 7m obtained by replacing the T from the upper bound on standard maximum information gain "r by 2 following Theorem.
L. This is formalized by the 2
Theorem 8. [More formal statement of Theorem [a)] Given Xm A fa1,,... Fm then we have that
En
Im S Dogg(1
1 log(1
dp
+
DA
?
1 Dogg(1 DE 1/e7 2
D
1
6D X
+
DA
2
2
Lastly, note that it has been shown that "T = Od T' for the linear kernel and "i ( T) for the SE kernel, Therefore, plugging in Lemma which allows us to upper-hound Exe 1/e, by 12, leads to Corollary !
D Proof of Theorem 2
Our proof here follows the outline the proof of Lemma from the work [38]. To begin with, show that 1et(V++1) = 2det(V+), = O...., 1, i.e., the amount of collected information is doubled after every stage.
++1 1 Al +
det(V = det
Σ
((1))((1))
j=1
= det
Al
+
2 {ozz))(z,)
+ ((
j=1
1
det
Vr
+
( -0
2
c++
det
V112
I+
1/2
((44)))))(()1 V
V212
2+1
(25)
det (V+) det
1+
1
1/-1/ VV-
2t11
det (V+)
p(xx+11)
V,- VV,
1/2,, ((
c++1
det (V+)
+
| |
2+1
1 (e( J3(z++1//A
det (V+)
= 2det (V+)-
Step (a) has made use of the matrix determinant lemma: det(T + abT) = det(T aa Tb), and (b)
follows from the expression of the weighted GP posterior variance 6 and our choice of e,+1
17

---

3. (z(x++1)/ V (line of Algo. 1. An immediate consequence of 25 is that (et(Vm)) = 2 det det( Recall we have defined earlier that Vo XI (App.
Recall that following the notations of App. A we have that Vm = X 4 m also show that
Wm Pm Next, we can
det(V det
det(AT + TT Wm pm
log
log
det(AI)
= log det
1+
( To w
( pm))
A
m
(a) log det
w1/2 W m T///
(26)
1+
A
= log det
I+ A
Km
mm
in which step (a) has again made use of the Weinstein-Aronszzij identity (similar to (33 and the last two equalities have simply plugged in the expressions for K, w:2/2 4, 4 w!/2 (App. A and
5m Y log de -
K m) (Sec. 5.1)
According to Corollary such that 7. I Cdlog
I for the linear kernel, we have that there exists an absolute constant
s=1 Combining equations 25 and (26), we can show that
det(V 2m S 2Cdlog det(Vi) (io)
1
m log log
Σ
(27)
2
This allows us to show that
m
(2m)1/(20d)
(28)
Note that in every stage s, we query the quantum oracle for Ci log( 2m times, in which C₁ > 1, 8 E (0, 2/e] and m is an upper bound on the total number of stages. An immediate consequence is that log( 2m
8 > log(3) (3) 2 1. Therefore, the total number of iterations can be analyzed as
C1
2m log(
(22)1/(201))
(29)
Eo
Now derive upper bound by contradiction. Suppose m implies that
2Cd log
log T. this immediately
(22))/(2Cd)) > T.
(30)
This equation, combined with (2).. implies that Exe Ci log Therefore, we have that
2m o
> T, which a contradiction.
m S
Cd Od T).
T).
(31)
log2
That is, for the linear kernel, our algorithm runs for at most Od T) stages, which matches the upper bound on the total number of stages for the quantum linear UCB (Q-LinUCB) algorithm, as proved by Lemma from the work of [38).
Next, for the SE kernel, Corollary I shows that there exists an absolute constant C > 0 such that 2=
5m < C log d+1
(> 4 Again combining equations 25 and (26). we can show that
det(Vm))
m
m log 2 = log
det(Vo) 2:m & 2C log d+1
Σ
(32)
2
18

---

This allows us to show that
m
(mile)
(mlog? 2
1/(d+1]
exp
(33)
2C
Now again we derive an upper bound by contradiction. Suppose this implies that
2C log
log T) T then
m log
1/(d+1)
exp
> T.
(34)
2C
This, combined with
29
implies that Σ ==1
Ci
log( 2 5
> T which is a contradiction. Therefore
<
2C
(2
d+1 O ((1og))4tt) T7
(35)
log 2
for the SE kernel. This completes the proof.
E Proof of Theorem 3
Our proof here follows closely the proof of Theorem from [9. Denote by So the observation noise for the observation in stage s: ys = fx,) + Se. Define Ç1:a - (G......C.. Ca] which is an s x 1 vector. { (.......: Nf+1..- -1.-.., Ss). With this definition,
Denote by Fs the o-algebra: F,
have that I, is F----measurrble and Ç, is meassuraalle. Note that we have used ((-) to denote the RKHS feature map the kernel A: k(æ, x') = d(x) T d(x'), and here we ((x) = k(z,)). Then using the reproducing property. we have that f(x) (6(x), fix = o(x) f. in which the inner product denotes the inner product induced by the RKHS of k.
To begin with, have that
Φ T 1/2 (wWl//(WW///,0,0 W 1/2 + AI) = - W. + -1 1. 1/1/2
(36)
which follows from noting that (Ø, W $ A T. w/ WW
12 1T T w + AT),
and then multiplying by (0_ W. + 17)-1 on the left and by (W! $. $ W2/2 AT) 1 on the right.
Now let fo & [f(Ex))E=I..... = f.f which is an s x 1-dimensional vector, and F. & w fo =
w 1 fff. Next, we can prove that
(xxx) F A 1f(x) ((x) T.W. (W. $ TW!/2 + 27) -1 J/ Ta
(0. W.
11111 +
(37)
llfll, / [OO==) - W W.4, + -1)-1
< 11f1l, (A0l=) -V W.W. W,,W, + -1)o)(())
11/ ( + -
2 BT.(
19

---

in which step (a) has made use of (36), and step (b) follows from our assumption that fl S B
(Sec. 3.I and the expression for the weighted GP posterior variance (6). Next, we have that
[ (x) -
10(x) W W D
w1/2
/ w!/2 =1)
W Si
10(z) W, + [o W/ W//
(W.
+ + V Wohi
< (0. + +,)
(6) W.D. AT) W.,,WGGi..
W.
= (()) ( (0 W Wo ( W. + -11- - Wel
(38)
(.(()V W.P, W W!
C1: Gl.
VA
( 1
W...W...WW:" (W: D. + AI) - - S11o
VÁ
1
$. 2. 2
ΦD T. W + - C1:
VÁ
( TT. W. + X1) 11) W 61:31
in which (a) and (b) follow from (6) Since W. (x) = kg (z)( "Ý, and Y, = / then the two equations above combine to tell us that
f(x) (=(())
s (x))
B
1
V CTs WT/2 K2 (K, AT) -W!/ C1:s
VX
(39)
<..())
B / CT. /2 R.(K. + \/) C1:30
in which the second inequality follows since À 1++1 r 1. Again following D we apply few more steps of transformations. Note that for an invertible K, we have that K(K + 7)-1
((K + ()K-))- -(I+ ([+K-1)-+ Substituting K K, + ./,, we have that
(K, + nl) + (n+ 1)))) (I + (K, + n1)-1
Next, we have that
GT. W..KKKK,(KK KK, + A1) - /r S ST..W! / + (n))(K + (1 (1+ - // -1 W!!?(
W!!o
-||w3// ((K,-
This allows us to further re-write (39 as
ff(x) - [a(( S (x)
+ W2/2 S11s
G1is ((R.tn)) -111))1-11--11
(40)
27 tq ................................ ) therefore, W Si: Isk 1 Ik=i..... Of note, since we have that (xxx) ) - yal S 6,, Vs = 1..... m (with high probability, refer to the beginning of Sec. 5), so, the noise C. y, f(x.) is bounded: IS.1 S Vs = 1,...,m. m. In other words, Ç, is Gu-sub-Gaussian.
Recall that W, diag 1
To begin with, note that eg is F -eassurall. This can be seen recursively: conditioned on {x1 }. (oooo(1//VV is deterministic constant (i.e., predietable); conditioned on {z1, 22) T1(-) is predictable because it depends on ii and e (via the weight } and hence e2 ō. (122) X is pre-
dictable conditioned on (2), By induction, conditioned on {a1,..., [K), , 6 = ã (Ix) (VA) is predictable. Therefore, EY is FR-1 measurable, because Fx-1 {21, Ik, .i...., (--1)
20

---

Next, note that since S& is FP meaauuaable, we have that Si. is Fa-meauurall.. Moreover, conditioned et on F (i.e., Eg is predictable), S is Suub-Gaussian, because Ç& is s-ssub-Gaussian as discussed above. To summarize, we have that every element Se of this noise vector W S1:s is (a) F&- measurable and (b) I-sub-Gaussian conditionally on Fk-1- Therefore, we can apply Theorem I of to I-sub-Gaussian noise, to show that
V det((1 + + + K.)
W S1: Si:s ((R.+11)-++))) $
2
(41)
8
with probability of at least 1 - 8. When applying Theorem of [9], we have also replaced the original unweighted covariance matrix K, by the corresponding weighted covariance matrix K₂ K, K,W.? This is possible because every eg is F More concretely, in the proof of Theorem 1 of [9], when defining the super-martingale {Me) which is conditioned on Fo.. we only need to replace the covariance matrix K, (for the multivariate Gaussian distribution of h(zz),..., h(z;)) by K = w. K,W, because both the original K₁ and our K₁ only require conditioning on {-1....... 21).
Combining the two equations above allows us to show that
V det((1 (1 + 17) Ks)
(42)
- -f())-;<<<)) S0, B+
2log
with probability of 5. 8.
Next, we can further upper-bound the log determinant term:
log det (11+ 7)1 K.)
(a) 3 log(1 77 + log det [
1
Kr
1+
(6)
1 [k, + s7
log det
I+
(43)
[c] 27 +
(d)
I 27, + 2,
in which (a) follows since (ct(AB) = det( A) det B) and dct(cA) S c dct(A) for a scalar e and an s s-matrix A. (b) has made use of log(1 + S (c) has made use of the definition of 7a and (d) follows because = 2/T and 8 < T. This eventually allows us to show that
det((1 + 7) + Ks)
((x)-ūū(z))) s (x)
B 2
(44)
< (x)
B v 2(7 1+ log log(1/)))
Of note, although the work [15] has also adopted weighted GP regression similar way to our (3). our proof technique here cannot be applied in their analysis. This is because the work of [I5] chosen the weight to w, = 1 for 17 E (0, 1) and hence W, diag w1, ..... w.]. Therefore, every element of the scaled noise vector 1-1/2 (1:s (i.e., (k//wg)) is not guaranteed to be sub- Gaussian. As result, this makes infeasible for them to apply the self-normalizing concentration inequality from Theorem of [9. i.e., our (41) above does not hold in their case. The work of [15] has come up with other novel proof techniques suited to their setting. Therefore, our proof here only works in our problem setting of quantum BO.
21

---

F Proof of Theorem 4
To begin with, we can show that
(a)
r3 = (x*) - f(xx) S U1 -1-1((²)) + 8,0.-1(²²)) f(xe)
(6)
x 7 + 1 (2x) f(x,))
(45)
22,,0- ( 28,e,vA,
in which (a) and (c) follow from Theorem (b) results from policy for selecting x, (line 2 of Algo. _ and (d) follows from design of e, x V (line 3 of Algo. 1 As result, the
total regret in stage can be upper bounded by:
C1 2m
2m 23,c, VA 2C18, VAlog
log E
(46)
8
Then an upper bound on the total cumulative regret can be obtained by summing up the regrets from all m stages:
2m < m2011mm v log RT S 2C1B.VAlog
2m
m
8 = =
mmm log
(47)
8
8
8=1
For the linear kernel, recall from Theorem 3 and Corollary I that 3m O Om + log (1/8))
dlgo T log(1/ log(1/8)). Also recall that Theorem 2 tells us that S O(dlog T). Therefore, for the linear kernel,
3/2 Ry =-= = O [ dlo + log((10)) log d dol T = O (o0/210g
3/2 T log log (og
(48)
in which we have ignored the dependency on log(1/6) in the second step to get a cleaner expression.
For the SE kernel, recall from Theorem and Corollary that (3m. = O(vim-1 + log (1/8) =
(VV(lg (Tdd4 + log(1/8)). Also recall that Theorem tells us that m S ग. O(log 1) Therefore, for the linear kernel,
Rr o
0 (log Tyd+1 V (log T + log(1/5) log
(log T)
(49)
0 (log 37) log((((gggg TTd-1)
in which we have again ignored the dependency log(1/8) obtain a cleaner expression.
The probability of 5 results from (a) conditioning the event that [((r,) yel S 6, Vs l.... m which holds with probability of at least 1 - 8/2, and (b) Theorem which also holds with probability of at least 1- 0/2.
G Proof of Theorem
Consistent with the analysis of Q-LinUCB [8 in order to apply the theoretical guarantee provided by QMC (Lemma[] for noise with bounded variance, here we need to assume that the noise variance is not too small: We assume that > 1/3. We have chosen the value of 1/3 just for convenience, in fact, any a larger than 1/4 can be used our analysis here because these different values will only alter the constants in our regret upper bound which are absorbed by the O.
Note that e, = ( VĀ < 1, which follows because )²-((x.) < 1 (which can be easily seen from (3) and our assumption that k(x, x') S 1) and À > 1. As result of the assumption of
> 1/3, we have that > 1/3 > 2/2 /8. This, combined with e, S 1, allows us to show that logg
8a 23/4 and that log, (log, -,- 1/2.
22

---

Next, we derive an upper bound on Σx=1 2 which is analogous to 8 Note that in the case of noise with bounded variance, the number of queries the quantum oracle in stage is given by logg(log, 8a
Ne, = Se log2 5,
3/2 Sa
c, log 2m with C2 > 1. As result, we have the following 8
inequality which is in a similar spirit to
C
3/2 log2
88
logg
(log2
log
2m
m 1
23/12
Σ
(50)
8
3
3 x 21/4
==1
Now suppose that Ex=1 Therefore, we have that
>
9v272 then we have that Ex=1 No, > T which a contradiction.
27
m
< 2
(51)
Next, note that Theorem is unaffected since its proof does not depend the noise. Moreover, Corollary also stays the same because it has only made use of (8) which gives an upper bound on
Ex=1 1/e ee and compared to (8), its counterpart (5T) in the analysis here only introduces extra constant factor which is absorbed by the bit O notation. Similarly, Theorem 2 is also unaltered for a similar reason, i.c., only an extra constant factor x 21/4 will be introduced to the right hand side of 30 and (4). which is absorbed by the big O notation.
Theorem B also unaltered since its proof does not depend on the type of noise. In particular, the key underlying reason why it is unaffected is because for both types of noise, given particular cs, we choose the corresponding number N., of queries (to the quantum oracle) depending on the type of noise so that the error guarantee of [y- fxxx)] S c, is satisfied. This allows us to make use of the neff-normalizing bound from [9] for nuu-Gaassiian noise.
Lastly, we need to modify the proof of Theorem now be bounded
To begin with, the total regret from stage can
C2
log2
80
log, (log2
8ø log
2m 5
x
23,c, V = 1o log?
3/2 2/
log, (logz
m log Bz).
8
(52)
Note that every 1/c, is upper-bounded by 1/c, s 3 x 21/4T= which can be easily inferred using (1). So, the total regret can be upper- bounded
Rr = 0
logz
3/2 logg (log2
( 0 E
m Be log E
(53)
m 0 mmm log
o log 3/2 (oTT)) loga (logz (o7))
g
As result, for the linear kernel for which 1m + 1og(1/8) O(Vdlog log(1/8) (Theorem and Comolary
Old 7) (Theorem and Bm
Rr o ( T 108(1 log loo T
a log (oT) log, (lgg((0g
(54)
o (od3/2 3/2 log T) log 3/2 (aT) log, (logg
in which we have ignored all (1g(1 factors for cleaner expression.
For the SE kernel for which m S गा (log d+1 T) (Theorem and 3m = / + log(1/8) =
O log d+1
11 T log(1/8)) (Theorem 3 and Corollary 1b
log d+1 T
Rr 0
log 4+1
TV
log 4+1 T log(1/5) log Volo
log
3/2 (oT) loga (lo22
5
(55)
0 (allog 3)d(411//2 log((log d) log 3/2
2/2
(oT) loga (log, oT)).
in which we have again ignored all log(1/o) factors for cleaner expression.
23

---

H Proof of Theorem
Our proof here follows closely the proof of Theorem 2 from the work of 2 For consisteney, in our proof here, we follow the notations from 38 and [2].
Since we focus on linear bandits here, assume that the reward function is linear with groundtruth d-dimensional parameter vector 8": f(x) = xx 8", Vx. Again following [2] and [8] as well as many other works linear bandits, assume that||0"||2 denote X, [T which an s X d matrix, and denote Y, .y....., ya]' which is an 1-dimensional vector of observations. We use Ç1:. _ [c....., C.] denote the x 1-dimensional vector of noise. These notations allow us to write Y, = + We denote V, - x, W,W.X W AT. Following 38 we use 0. to denote the MLE estimate of the parameter 0* given the observations after the first stages: 0₂_ = V N.W.X. W.Y,, Given these notations, we firstly have that
ll2 S S, and ||2||| - L, Va. We use X, to
0. (X, W,X, + XX W.(X,0* + (1:))
(X, W,X, + - Woh1s + +X, W,X, (X, W,X, AL)0
(56)
-XX W,X, -00
(x, W,X, + 11, Wolni + +0" - -XXx W.X, + 11)
Therefore.
TTO, x0 = x0===xxXx' (x, W,X, + A1) X Wi Ax
Ax (X, W.X, + AI) 10"
(57)
= Xx, W. WoLI=) V, - A(x, 8*) v"vv--
This allows to use the Cauchy-
Cauchy-Schwarz Schwarz inequality show that
(|xT] WoSi v. + +11001lv;-1
lx 0- TT $ |
(58)
< $|<z|||,-1
[ X__Wisis
V,- + VV
The last inequality follows because | 1001 122-
S Jmaia [VJ 11011/ 1110-12.
Note that X_ WoCt=
=
Ei 2t CLT
Next, we make use of the self-normalized concentration inequality from Theorem of 2] Specifically, we will use { ( j as to replace the stochastic process { (i.e., representing the noise, { according to the notations from (2), and use (2 x. to replace the vector-valuee stochastic process { (i.e., representing the sequence of inputs). Now explain why this is feasible.
Similar to the proof of Theorem we again denote the observation noise as Ç5i ys f(xx)) + C.. and define F, as the o-algebra F. (I1, T2, I: 11 G........... G.). Similarly, an immediate consequence is that vs is F-------aaaee measurable, and ç. is F.-measurable. Following similar analysis to that used in the proof of Theorem alllos us to show that is Fx -eeasurable (i.e., can be predicted based on Fx) Therefore, we have that ex Zz is 1 measurable (i.c., el I can be predicted based on Fx-1) and that & is mmeesuurablee Moreover, conditioned on FR-1. e is 1-sub- Gaussian. This is because the QMC subroutine guarantees that 1y: f(xx) S Eg, Vk 1,...,m m
(with high probability), which means that the absolute value of the noise Ç2 = yk (xx) is
upper-bounded by εx: |G& cy. Therefore, conditioned on Fx-1. Ca is --sub-Gaussian
Ex
Given that these conditions are satisfied, we can apply the self-normalized concentration inequality 1:00 and { 1_x J with (following the notations from Theorem 1 of from Theorem 1 of 2 to Su [00
V, = V
+
I'k
=
Al
+
J A=1
x
2
1=1
(59)
5
Gk
S,
Ek
2
k=1
24

---

in which we have used V = AI. This allows us to show that
dot((V)) det (AI) A/2-
|| = X W WoSr:s
V. -
2 2og
(60)
which holds with probability of at least - 8. Next, again making use of the trace-determinant inequality from (T6) and using the aforementioned assumption that || S L, we show that
dV,(V,) & (A 1 Σk= ) Also note that det(AT) = Xa. As result, we can further upper-
bound the equation above by:
L2 DE (A+
1 3d -== c
x__ WaSt:s Iv--
2log
1 8
2
11
(61)
2 2
1
1 13
1 2
k==
V
2dlog
in which have used d > in the last step get cleaner expression. Therefore, we can re-write (58) as
1 x E
x 0. x T0 < |=l|v_11 v-
1
2d
VaS
Vx,
(62)
8
in which we have also used the above-mentioned assumption of 0f|10*1| 1l2 - S. Now again following 2 we plug V., 0²). which gives
1
12 X Ei
|0, -011 s V.1.00 03)11--
12dlog
VAS
(63)
1+
= -1 - 0011v
12 22dlog
X
k=
VAS
8
Therefore, we have that
12 1+ DE X
0. 8.
V 2d
+ VXS
(64)
This completes the proof of Theorem 6
Now we briefly show how the improved confidence ellipsoid from our Theoremb]leade to an improved regret upper bound for Q-LinUCB. Here we follow the proof of Theorem 3 from (38), and hence defer the detailed explanations of some of the steps to the proof there. To begin with, we have that
f(x*) f(x.) = (x* - xx)Tel
S 6a (10ā, - - -0--1/
V.-1 -100-11-00 - 0- (1)r--)
< 2es x (V22100s
1+ 12922/X + Vās)
(65)
=0 (vVVologT)
25

---

Here for simplicity, we have upper-bounded (1/E() by T (Lemma in the second inequality. and have omitted the dependency on log(1/6).
Then the total regrets in stage 8 can be upper-bounded by
C1
2m log x O
(eo (cVVdlogT) =o
=ooologg T m
(66)
Plugging in our tighter confidence ellipsoid (Theorem into the regret analysis of QLinUCB, we have that the regret upper bound of QLinUCB can be analyzed as
m 5 Rr = 0 dlog log(
Omm log T logg {))
(67)
= O(dlog T dlog log
o (d 8)5/2 log(d
which gives the tighter regret upper bound for Q-LinUCB that we have discussed in the main text (Sec. 5.6
I Regret Upper Bound for the Matérn Kernel (Proof of Theorem 7
In this section, we modify our analysis to derive a regret upper bound for the Matérn kernel. We focus on bounded noise here (i.e., the first scenario in Lemma IT, since the analysis for noise with bounded variance (i.e., the second scenario in Lemma D is similar and follows from the analysis of App. G In our analysis here, for simplicity, we ignore the logarithmic factors.
To begin with, note that Theorem iis is not kernel-specific and hence still holds in analysis here. It has been shown that for the Matérn kernel, the upper bound on the standard maximum information
gain is "T (T (о [35]. Therefore, similar our Corollary for the Matérn kernel, we use [ show that
7m = H
S Tarid
(68)
Next, we modify the proof of our Theorem 2 to derive the corresponding upper bound on the total number of stages for the Matérn kernel, i.e., discuss here how we modify the proof of TTheoem
in App. D To begin with, 68 suggests that there exists C' such that 7. C [E
Different from our analysis for the linear and SE kernels App. D
(i.e., (7 and (32 the absolute
constant C' here also contains logarithmic factors. Similar to 27
we can show that
m log 2 log det(V.m) 25m 2C
m
(69)
det(
2
This naturally leads
m
log 2
2=
Σ
(70)
2C
which is analogous to
28 Next, similar to the total number iterations can be analyzed as
29
2m
log 2
log
m
(71)
20
#=1
1=1
26

---

Now suppose m T log
2C
then this implies that
2044
log 2
m
> T.
(72)
2C
This equation, combined with (7)). suggests that Σx=1 Therefore, we have that
C. log
2
T, which is a contradiction.
m S T
24 20
2C
T
24 2044
(73)
log 2
Next, note that our confidence ellipsoid in Theorem does not depend on the choice of the kernel and hence also holds for the Matérn kernel.
Lastly, we can modify the proof of Theorem (App. F. Specifically, we can adopt the result from
RT S O mm log m 8. Øl (m))m-1) Ø(V for the Matérn kernel,
For the Matérn kernel, Theorem 3 and (68) allow us to show that
8
Ö(TTt))) ). Combining this with 73 allows us to show that 2e
RT Ö T 20=a T Tiiks) ) O 2044
(74)
This completes the proof of Theorem 7
More Experimental Details, and Experiment on Real Quantum Computer
In experiments, when implementing both the classical GP-UCB and our Q-GP-UCB algo- rithms, we use random Fourier features (RFF) approximation to approximate the kernel: k(r, x²) z ((x) "(x"). As result, we can implement the weighted GP posterior following (6) as discussed in App. A in which the M-dimensional (M < oo) random features ((-) are used replace the infinite-dimessione RKHS features ())). We have used M = 100 random features in the synthetic experiment and M 200 in the AutoMI. experiment. As have mentioned in the main paper (Sec. 6). we have implemented the QMC algorithm from the recent work of [20] using the Qiskit python package. We have used 6 qubits for the Gaussian noise and qubits for the Bernoulli noise. For each experiment, we perform multiple independent trials (10 trials for the synthetic experi- ment and trials for the AutoML experiment) and have plotted the resulting mean and standard error as the solid lines and error bars in each figure, respectively. For our Q-GP-UCB, we choose 3. = 1+ log s, Vs 2 1 following the order given by the theoretical value of B, (Theorem 3). For classical GP-UCB, we tried different approaches to setting 3g: 3, + log s, 3, v2 and B. all of which are commonly adopted practices in BO; we found that B, = v2 and B, = 1 have led to the best performances for GP-UCB in, respectively, the synthetic and AutoML experiments.
For the synthetic experiment, some important experimental details have been discussed in Sec. 6 The reward function f used in the synthetic experiment is sampled from a GP with the SE kernel with length scale of 0. In the AutoML experiment, an SVM is used for diabetes diagnosis. That is, we adopt the diabetes diagnosis dataset which can be found at httht::://wwwt pima-indi ans www.dddeeeeettaatleeee
kaggle. com/ucim1/ which is under the CCO license. The task involves using 8 features to predict whether the patient had diabetes or not, which constitutes a two-class classification problem. We use 70% of the dataset as the training set and the remaining dataset as the validation set. We aim to tune two hyperparameters of the SVM: the penalty parameter and the RBF kernel parameter, both within the range of [10- -4 1]. For simplicity, for each of the two hyperparameters, we discretize its domain into 5 points with equal spacing. This results in a domain with | = 25.
Here we adopt the SE kernel: k(2,, x²) & o exp(-lIz 2²112 (2(2)) with of 0.5. Since we have implemented our algorithms (both classical GP-UCB and our Q-GP-UCB using RFF approximation as discussed above, we performed grid search for the length scale within {0.1, 0.2........1 for both GP-UCB and Q-GP-UCB when generating the random features. We found that / = 1.0 leads to the best performance for GP-UCB and / 0.2 works the best for Q-GP-UCB. This likely because for our Q-GP-UCB, the effective noise is much smaller (thanks to the accurate estimation by the QMC algorithm), which allows us to use a smaller length scale (which can model more complicated functions) to accurately model the reward function.
27

---

10000
10000
Cumulative Regret
Q-GPAICB
Cumulative Regret
o-gncca (:m0.3)
8000
LinKEB
8000
og (c
Q UnUCB
Uidcs lom 044)
Qunlca
6000
6000
4000
4000
2000
2000
2000
4000 6000 Iterations
8000
10000
2000
4000
6000
8000
10000
Iterations
(a) synthetic, Bernoulli noise
(b) synthetic, Gaussian noise
Figure 2: Cumulative regret for the synthetic experiment with (a) Bernoulli noise and (b) Gaussian noise, with the additional comparisons with LinUCB and Q-LinUCB.
60
40
60
Regret.
Cumulativv Regret
30
40
40
Cumulaative
Spuck 1- 880
20
20
07-028
D0NLO 1am0
10
quenue Jthl Bang
COALER feetut qaraa aood
10000
10000
1000
5000
(a) synthetic, Bernoulli noise
(a) synthetic, Gaussian noise
(c) AutoML
Figure 3: Cumulative regret for (a) the synthetic experiment with Bernoulli noise, (b) the synthetic experiment with Gaussian noise, and (c) the AutoML experiment, with the additional comparisons with our Q-GP-UCB algorithm after considering quantum noise.
All experiments 64 CPUs. No GPUs are needed.
computer with Intel(R) Xeon(R) Gold 6326 CPU @ 2.90GHz, with
More Experimental Results. Fig. additionally shows the cumulative regret for the LinUCB and Q-LinUCB algorithms in the synthetic experiment. Consistent with the results in Fig. (d) in the main paper (Sec. 6)) which has included the results for LinUCB and Q-LinUCB in the AutoML experiment, here LinUCB and QLinUCB again underperform significantly in Fig. 2 for both types of noises. These results further verify that in realistic experiments with non-linear reward functions, algorithms based on linear bandits are significantly outperformed by those based on BO/kernelized bandits. Fig. additionally shows the results of our Q-LinUCB after considering quantum noise. As we have discussed in the main paper (Sec. 6 the results show that the quantum noise leads to slightly worse performances for our Q-GP-UCB, yet they are still able significantly outperform classical GP-UCB.
Results Using A Real Quantum Computer. Here additionally perform an experiment using real quantum computer. Specifically, we ran our QMC subroutine on a real IBM quantum computer based superconducting qubit technology qubit, Falcon r5.1 1H processor) through the IBM Quantum cloud service. We ran our synthetic experiment with Gaussian noise on the system for only 1 trial (instead of 10 in other simulations) due to time and resouree constraints. The results in Fig. 4 show that although the performance of our Q-GP-UCB on real quantum computers is worse than those obtained without quantum noise and with simulated quantum noise, our Q-GP-UCB run on real quantum computers is still able to significantly outperform classical GP-UCB. This experiment provides further demonstration for the potential of our Q-GP-UCB algorithm lead to quantum speedup real BO applications.
28

---

60
Cumulative Regret
40
20
GP-UCB (d-m0.4)
Q-GP-UCB (a= 0.4)
Q-GP-UCB simulated quantum nalse)
0
Q-GP-UCB (a= 0.4, real quantum computer)
2000
4000 6000
8000 10000
Iterations
Figure 4: Results using a real IBM quantum computer. Cumulative regret for the synthetic experiment with Gaussian noise with = 0.4.
29


Reviews:
[{"review_id": "GyEgMExNgQ", "reviewer": "Reviewer_Hp2A", "summary": "This paper studies Bayesian optimization with quantum reward oracles where the reward function $f$ lies in an RKHS space with the squared exponential kernel, and at every iteration after input is selected, we can access a quantum unitary oracle and its inverse that encode the noisy reward distribution. In such a setting, the authors introduce the quantum-Gaussian process-upper confidence bound (Q-GP-UCB) which achieves a regret upper bound of $\\mathcal O(\\text{poly log} T)$. To do it, they introduce a weighted GP regression and then analyze the growth rate of the weighted information gain. Next, they derive a tight confidence ellipsoid which gives a guarantee of the concentration of the reward function and the weighted GP posterior mean. They also show that their bound on the confidence ellipsoid improves that of the quantum linear UCB (Q-LinUCB) algorithm [32] over a factor $\\sqrt{d}$, where $d$ is the input dimension. Finally, they show the performance of their proposed algorithm over the classical GP-UCB and Q-LinUCB, through a synthetic experiment and an experiment on automated machine learning ", "questions": "- The authors seem not to consider the case of the Materm kernel. Is there any improvement in the regret bound with the aid of quantum computing in this case?\n-  It would be interesting if the authors can provide a discussion on the lower bound of the regret bound of BO in the setting of quantum computing.    ", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well-organized and easy to read. The arguments, and comparisons with related works are clear and well-supported.\n- The paper is the first to introduce the first quantum Bayesian optimization algorithm which enjoys a regret upper bound of $\\mathcal O(\\text{poly log} T)$.   ", "weaknesses": "However, I am concerned about the novelty of the used techniques in this paper. They seem to be an unsophisticated combination of common techniques from classical Bayesian optimization (e.g., see [9], [28], [30]), the classical bandits [9], and quantum bandits [32]. It follows that the regret upper bound of $\\mathcal O(\\text{poly log} T)$ for their proposed BO algorithm has the same order as that of [32] which is designed for linear bandits.  \n\nThe authors claim that the recent quantum works on multi-armed or linear bandits are not able to solve sophisticated real-world problems with non-linear reward functions like their setting. However, from the technical point of view, Bayesian optimization under the setting that the reward function $f$ lies in an RKHS space is in fact a kind of linear bandit problem except that the input space is continuous. \n\nHence, I think that this paper is OK but not good enough from a technical point of view.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe'd like to thank the reviewer for your insightful comments.\n\n---\n\n> However, I am concerned about the novelty of the used techniques in this paper... the regret upper bound of $\\mathcal{O}(\\text{poly}\\log T)$ for their proposed BO algorithm has the same order as that of [32] which is designed for linear bandits.\n\nWe have clarified and highlighted our technical novelty and contributions (especially compared with [32]) in our global response above (point 1). Here we give a brief summary:\n- The analysis of our weighted information gain (Theorem 1) is non-trivial, and is a novel contribution especially compared to quantum linear bandits [32] whose analysis didn't involve information gain. It may also be **of broader independent interest**.\n- The proof of our confidence ellipsoid (Theorem 3) also requires non-trivial techniques and insights, such as the recognition to apply the concentration inequality for 1-sub-Gaussian noise. It is also **novel because it is closely tied to our algorithmic design**.\n- We have used the techniques and insights from the proof of our Theorem 3 to **improve the confidence ellipsoid and hence the regret of quantum linear bandits [32]**, which is another important contribution of ours.\n- We've also made important empirical contributions by conducting a more realistic AutoML experiment and **an experiment using a real quantum computer**, both of which were not done by previous works on quantum bandits [32]. We also achieved significantly better performances than quantum linear bandits [32] and classical GP-UCB [28].\n\nIn addition to the individual novel contributions listed above, another major aspect of our novelty and technical difficulty lies in **identifying the different required techniques** (e.g., weighted information gain, concentration for 1-sub-Gaussian noise) and **integrating them into a coherent analytical framework**, which we think is highly non-trivial. \n\nTherefore, we think that despite achieving the same regret order of $\\mathcal{O}(\\text{poly}\\log T)$ as quantum linear bandits [32], our work has overcome non-trivial additional challenges and made important novel technical contributions, which go beyond unsophisticated combination of common techniques. Please refer to our global response above (point 1) for more details.\n\n---\n\n> The authors claim that the recent quantum works on multi-armed or linear bandits are not able to solve sophisticated real-world problems with non-linear reward functions like their setting. However, from the technical point of view, Bayesian optimization under the setting that the reward function $f$ lies in an RKHS space is in fact a kind of linear bandit problem except that the input space is continuous.\n\n\nWe'd like to clarify that when the reward function $f$ lies in an RKHS space, it is a linear function w.r.t. the RKHS feature mapping $\\phi(x)$, but **not a linear function w.r.t. the original input $x$**. In contrast, the quantum linear bandits [32] does assume that $f$ is a linear function w.r.t. the original input $x$. Therefore, our algorithm is able to model non-linear reward functions, which the quantum linear bandit algorithm [32] is incapable of. Thanks for pointing this out, we'll revise the paper to make this point clearer.\n\n---\n\n> The authors seem not to consider the case of the Materm kernel. Is there any improvement in the regret bound with the aid of quantum computing in this case?\n\nAs you suggested, we have additionally analyzed our algorithm for the Matern kernel (with smoothness parameter $\\nu$), and included a detailed discussion in our global response above (point 2). Briefly, for the Matern kernel, our regret bound $\\widetilde{\\mathcal{O}}(T^{(3d)/(2\\nu+d)})$ also improves over the state-of-the-art regret in the classical setting $\\widetilde{\\mathcal{O}}(T^{(\\nu+d)/(2\\nu+d)})$ when the reward function $f$ is sufficiently smooth (i.e., when $\\nu > 2d$). We think that this smoothness condition is reasonable for our work (as the first work on quantum BO) because it is analogous to the classical GP-UCB [28]: GP-UCB also requires the function $f$ to be sufficiently smooth (i.e., $\\nu>d/2$) in order to achieve a sub-linear regret bound. This requirement of GP-UCB for smooth functions (for the Matern kernel) was only removed by later works (e.g., [19,25,31]) which improved the regret bound of GP-UCB through sophisticated algorithmic designs and analyses; similarly, we also leave it to future works to further improve the regret bound of our quantum BO for the Matern kernel.\n\nThank you for pointing this out. We'll add the results and discussions about the Matern kernel (more details in the global response above, point 2) to the paper after revision. We think that these additional results, given our already significantly improved regret for the SE kernel, will further improve the significance of our contributions.\n\n---\n\n> It would be interesting if the authors can provide a discussion on the lower bound of the regret bound of BO in the setting of quantum computing.\n\nTo the best of our knowledge, deriving a regret lower bound for quantum multi-armed bandits and quantum linear bandits is also still an open problem [32]. We agree that obtaining a regret lower bound in the quantum bandit setting is an interesting and important research problem, and we aim to explore this in future works.\n\n---\n\nThank you again for your feedback. We hope our additional clarifications could improve your opinion of our paper.\n\n"}, {"review_id": "JNK7M3RqAL", "reviewer": "Reviewer_pGF9", "summary": "This paper considers kernelized bandits also known as Bayesian optimization under a particular feedback model inspired by quantum computing. Under this model repeating sampling from the same point for N times reduces the noise to the level on $1/N$. That is significantly tighter than the classic setting where sampling the same point for N times reduces the noise to the level on $1/\\sqrt{N}$. The paper introduces a UCB based algorithm, that is very similar to mini-META proposed in [6]. The proposed algorithm is referred to as Q-GP-UCB, and, in the case of SE kernel, obtains a polylogarithmic regret bound in the time horizon $T$ that is a significant improvement compared to $\\sqrt{T}$ regret bound in the classic setting. ", "questions": "- Considering the example above about Matern kenrel, could the authors comment on the tightness of the bounds? The results seem to be an improvement only in the case of SE kernel. Why they do not necessarily improve the regret bounds in the case of other kernels. \n\n- If the standard mean and variance are used rather than the weighted ones, which step in the proof would fail? The number of unique points or the regret on each unique point? ", "limitations": "Although the formulation seems interesting, the results do not seem tight. To some extent they follow the case of linear bandits. When it comes to more general kernels the regret bounds seem to even fail to be sublinear in some cases. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The problem is inspired by quantum computing and may be of broader interest. Overall this is an interesting formulation of kernel bandits. \n\n", "weaknesses": "The formulation and analytical techniques are similar to those of [32] in the case of linear bandits. That to some extent limits the novelty and contributions. \n\nIn terms of complexity, the regret bounds seem to scale as $\\tilde{\\gamma}_m^{1.5}$, where the number of unique points is bounded by $\\tilde{\\gamma}_m$ and an additional $\\tilde{\\gamma}_m^{0.5}$ is contributed by the regret on each unique point, due to confidence ellipsoid. Theorem 1 bounds this quantity by \\gamma_{T^2}. For example, in the case of Matern kernels, that leads to a regret bound of $T^{(3d)/(4\\nu+2d)}$ where $\\nu$ is the smoothness of the kernel. This regret bound may be worse than the classic results of $T^{(\\nu+d)/(2\\nu+d)}$ when $d$ is large. I think this is an indication that the regret bounds presented in this work are sub-optimal and can be further improved. Given that there is no lower bound under this setting, that raises some doubts about the tightness of the analysis. The results should be seen as some initial attempt on the problem.  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe'd like to thank the reviewer for your constructive feedback.\n\n---\n\n> The formulation and analytical techniques are similar to those of [32] in the case of linear bandits. That to some extent limits the novelty and contributions.\n\nWe have clarified our technical novelty and contributions (especially compared with [32]) in our global response above (point 1). Here we give a brief summary:\n- The analysis of our weighted information gain (Theorem 1) is non-trivial, and is a novel contribution especially compared to quantum linear bandits [32] whose analysis didn't involve information gain. It may also be **of broader independent interest**.\n- The proof of our confidence ellipsoid (Theorem 3) also requires non-trivial techniques and insights, such as the recognition to apply the concentration inequality for 1-sub-Gaussian noise. It is also **novel because it is closely tied to our algorithmic design**.\n- We have used the techniques and insights from the proof of our Theorem 3 to **improve the confidence ellipsoid and hence the regret of quantum linear bandits [32]**, which is another important contribution of ours.\n- We've also made important empirical contributions by conducting a more realistic AutoML experiment and **an experiment using a real quantum computer**, both of which were not done by previous works on quantum bandits [32]. We also achieved significantly better performances than quantum linear bandits [32] and classical GP-UCB [28].\n\nIn addition to the individual novel contributions listed above, another major aspect of our novelty and technical difficulty lies in **identifying the different required techniques** (e.g., weighted information gain, concentration for 1-sub-Gaussian noise) and **integrating them into a coherent analytical framework**, which we think is highly non-trivial. \n\nTherefore, we think our work has made important contributions especially compared with quantum linear bandits [32]. Please refer to our global response above (point 1) for more details.\n\n---\n\n> ... For example, in the case of Matern kernels, that leads to a regret bound of $T^{(3d)/(4\\nu+2d)}$ where $\\nu$ is the smoothness of the kernel. This regret bound may be worse than the classic results of $T^{(\\nu+d)/(2\\nu+d)}$ when $d$ is large. I think this is an indication that the regret bounds presented in this work are sub-optimal and can be further improved. Given that there is no lower bound under this setting, that raises some doubts about the tightness of the analysis. The results should be seen as some initial attempt on the problem.\n\n> ...could the authors comment on the tightness of the bounds? The results seem to be an improvement only in the case of SE kernel. Why they do not necessarily improve the regret bounds in the case of other kernels.\n\nAs you suggested, we've added a discussion of our regret bound for the Matern kernel in our global response above (point 2). Below we also give a (self-contained) discussion, with additional discussions on the tightness and improvement (over the classical setting) of our regret bound.\n\nFor the Matern kernel, our regret bound of $\\widetilde{\\mathcal{O}}(T^{(3d)/(2\\nu+d)})$ also improves over the state-of-the-art regret in the classical setting $\\widetilde{\\mathcal{O}}(T^{(\\nu+d)/(2\\nu+d)})$ **when the reward function $f$ is sufficiently smooth** (i.e., when $\\nu > 2d$). So, even when $d$ is large, we still achieve an improvement if $\\nu$ is large enough. We think this smoothness condition for the Matern kernel is reasonable, which can be justified by drawing analogy between our work (as the first work on quantum BO) and the classical GP-UCB [28]: For the Matern kernel, **the classical GP-UCB** [28] (with a regret bound of $\\mathcal{O}(\\gamma_T\\sqrt{T})=\\widetilde{\\mathcal{O}}(T^{(\\nu+3d/2)/(2\\nu+d)})$) **also requires the function $f$ to be sufficiently smooth** (i.e., $\\nu>d/2$) to achieve a sub-linear regret. This requirement for smooth functions was only removed in later works (e.g., [19,25,31]), which used sophisticated algorithmic designs and analyses to improve the regret of classical GP-UCB to $\\mathcal{O}(\\sqrt{\\gamma_T T})=\\widetilde{\\mathcal{O}}(T^{(\\nu+d)/(2\\nu+d)})$. Therefore, we agree that for the Matern kernel, our regret bound may not be tight. However, given our discussions here, our regret bound for the Matern kernel is still a reasonable and important contribution (analogous to the regret of GP-UCB for the Matern kernel which also requires smooth functions), and we hope our work could also inspire future works to further improve the regret of quantum BO for the Matern kernel (similar to how the regret of GP-UCB was improved by later works).\n\nLastly, we briefly summarize the contributions and **improvements** of our regret bound for different kernels: For the *SE kernel*, our regret bound significantly improve over the classical regret; for the *Matern kernel*, our regret bound improves over the classical regret when the reward function $f$ is sufficiently smooth; for the *linear kernel*, our regret bound improves over that of the quantum linear bandits [32].\n\n---\n\n> If the standard mean and variance are used rather than the weighted ones, which step in the proof would fail? The number of unique points or the regret on each unique point?\n\nIf the standard GP posterior mean and variance are used instead of the weighted ones, the proof of the number of unique points (i.e., the total number of stages, Sec. 5.2) would not be valid. Specifically, the proof of Equation (25) in Appendix D wouldn't go through, and hence we could no longer derive the upper bound on the total number of stages given in Theorem 2.\nTherefore, the weighted GP posterior regression (Sec. 4.1) is indispensable for deriving our theoretical results.\n\n---\n\nThank you again for your comments. We hope our additional clarifications could improve your evaluation of our paper.\n"}, {"review_id": "L8b0S42NOY", "reviewer": "Reviewer_n5g2", "summary": "The paper studies the regret attainable for multi-armed bandits with non-linear reward functions when having access to a quantum oracle. For this setting they introduce the Quantum Gaussian Process Upper Confidence Bound (Q-GP-UCB) that with probability at least $\\delta$ achieves regret:\n- $\\mathcal{O}((d\\log{T})^{3/2}\\log{d\\log{T}})$ using the linear kernel,\n-  $\\mathcal{O}((\\log{T})^{3/2\\cdot(d+1)}\\cdot (d+1) \\cdot \\log{\\log{T}})$ using the squared exponential (SE) kernel,\n\nwhen the noise is bounded and $d$ is the dimensionality of the input space. Similar rates are derived for noise with bounded variance.\n\nThis notable improvement over the classical fundamental limit is mostly attributed to the use of the Quantum Monte Carlo (QMC), and the improvement over the work of Wan et. al. 2022 (when instantiated with the linear kernel) is due to the paper's novel and tighter analysis of the confidence ellipsoid. They actually modify the proof of this prior work to attain the same rate as well.\n\nFinally, they run experiments using the Qiskit package that demonstrate their algorithm's superiority over the classical variant, as well as the benefits of using the SE kernel in the more practical setting of AutoML.\n\n", "questions": "- Could you expand more on the empirical behavior of Q-GP-UCB in the initial stage? It is a bit hard to see given the large setting of total time-steps. For example, could you comment on when this may be an issue and when not? \n- Do you have intuition for what would happen with other kernels being used?\n", "limitations": "- As per above, maybe more limitations regarding trade-offs of initial phase (and others) could be discussed in experimental section?", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Intuitive and well explained use of staging to manage the growing number of samples fed to the QMC subroutine.\n- Their weighing technique is very intuitive and by making the noise 1-sub-Gaussian allow them to use a self-normalized concentration inequality that improves the confidence ellipsoid and allows for better rates (also has nice intuitive meaning as enabling a measuring of weighted information gain).\n- I particularly like that they use plug their improved analysis into the work of Wan et. al. to make their original algorithm match the rate the authors attain with the linear kernel. This is a nice way to both showcase the strengthened analysis, as well as to clarify to the community which things are key algorithmic behavior versus analysis artifacts.\n\n", "weaknesses": "- No core majorly novel algorithmic design / concept definition, i.e. results are due to elegant combinations of techniques and careful analyses rather than groundbreaking new concepts/approaches introduced.\n- Minor typo: \"encode\" -> \"encodes\" (line 144).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe'd like to thank the reviewer for your valuable comments.\n\n---\n\n> Could you expand more on the empirical behavior of Q-GP-UCB in the initial stage? It is a bit hard to see given the large setting of total time-steps. For example, could you comment on when this may be an issue and when not?\n\nThe empirical behavior of our Q-GP-UCB in the initial stage (i.e., its regrets in the initial stage are relatively larger compared with the classical GP-UCB) is reasonable because our Q-GP-UCB explores a smaller number of unique arms than the classical GP-UCB initially (because we query every selected arm for multiple rounds). However, after the initial exploration, our Q-GP-UCB can quickly start performing reliable exploitation, because the accurate reward observations achieved thanks to our QMC subroutine allow us to quickly learn the reward function and hence find the optimal arm. Of note, the same behavior (i.e., relatively larger regrets in the initial stage) is also observed in [32] regarding the quantum linear bandit algorithm, which is similar to our algorithm using the linear kernel. So, we think that this behavior is not kernel-specific.\n\nRegarding your second question, we think this may be an issue when the problem is easy, i.e., when the reward function is easy to optimize (e.g., when the noise is too small or when the required number of iterations to find the optimal arm is too small). Specifically, when the problem is easy, classical BO algorithms such as GP-UCB may also be able to quickly find the optimal arm, which makes it difficult for the advantage of our Q-GP-UCB algorithm to manifest. On the other hand, this is unlikely to be an issue when the problem is relatively difficult, in which case we expect our Q-GP-UCB algorithm to consistently perform better, as we have demonstrated in our experiments.\n\nWe'll follow you suggestion and add our discussions here to the experimental section.\n\n> Do you have intuition for what would happen with other kernels being used?\n\nAs you suggested, we have additionally analyzed the regret of our algorithm for the Matern kernel, and included a detailed discussion in our global response above (point 2). Intuitively, for the Matern kernel, our regret bound also improves over the state-of-the-art regret in the classical setting when the reward function $f$ is sufficiently smooth. \nThis in fact brings about an analogy between our work (as the first work on quantum BO) and classical GP-UCB [28]: GP-UCB also requires the function $f$ to be sufficiently smooth in order to achieve a sub-linear regret bound. Also similar to how GP-UCB was extended by later works, We leave it to future works to further improve our regret bound for the Matern kernel. \nWe'll add the results and discussions about the Matern kernel (more details in the global response above, point 2) to the paper after revision, which we think will further improve the significance of our contributions.\n\n---\n\nThank you again for your feedback. We'll also follow your suggestion to correct the typo, and do a thorough check for other potential typos.\n"}, {"review_id": "lIgQbx3O6T", "reviewer": "Reviewer_5kMD", "summary": "The paper studies quantum kernelized bandits or Bayesian optimization (BO). Classically, in every iteration t=1,2,\\ldots,T, a BO algorithm chooses an arm x_t and then queries the reward function f for a noisy observation y_t=f(x_t)+\\zeta_t, where f can be non-linear and \\zeta_t is a sub-Gaussian noise. The goal is to minimize the cumulative regret R_T=\\sum_{t=1}^{T}[f(x^*)-f(x_t)]. In the quantum setting, every query to the reward function f at the arm x_t is replaced by a chance to access a quantum oracle or its inverse, which encodes the reward distribution for the arm x_t. Besides, a bounded noise or a noise with bounded variance are considered. The paper introduces the Q-GP-UCB algorithm which is the first BO algorithm able to achieve a regret bound of  O(poly log T), which is significantly smaller than the classical lower bound of \\Omega(\\sqrt{T}).", "questions": "1. Please explain more about the technical difficulties in analyzing the Q-GP-UCB algorithm.\n\n2. I notice that the authors of [32] showed their Q-LinUCB algorithm has a regret of O(log^{5/2} T) for bounded noise, but this paper said the regret is O(log^{3/2} T) (see line 350) when citing [32]. Is this because the analysis of [32] is not tight? Please confirm it since one of the contributions of this paper is an improvement over Q-LinUCB. If you indeed improve the regret from O(log^{5/2} T) to O(log^{3/2} T), this would increase the contributions of the paper.", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper provides the first quantum BO algorithm, which achieves a polylog(T) regret, beats the classical lower bound of \\Omega(\\sqrt{T}), and offers more evidence of quantum advantages over classical computers.\n\n2. The result generalizes the previous quantum speedup for multi-armed bandits (MAB) and stochastic linear bandits (SLB) [32]. Besides, the paper improves the regret bound of SLB in [32] by improving the analysis of the confidence ellipsoid.\n\n2. The paper is overall structured very well. The ingredients of the analysis for the Q-GP-UCB algorithm are listed in a readable way so I can quickly get the ideas behind it. I enjoy reading this paper very much.", "weaknesses": "1. I'm a bit doubtful about the technical contributions of this paper. Apparently, the basic framework of Q-GP-UCB follows from the weighted least squared estimator and the doubling trick in [32]. The key difference from [32] is the design of the weighted GP posterior distribution (see Eq. (3)), which looks very similar to the classical one (see Eq. (1)). Such a combination, of course, can be regarded as the main technical novelty, but the question is, I have no idea whether it raises inherent difficulties in the analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe'd like to thank the reviewer for your insightful comments.\n\n---\n\n> 1. I'm a bit doubtful about the technical contributions of this paper... Such a combination, of course, can be regarded as the main technical novelty, but the question is, I have no idea whether it raises inherent difficulties in the analysis.\n\n> 1. Please explain more about the technical difficulties in analyzing the Q-GP-UCB algorithm.\n\nThe analyses of our algorithm indeed posed non-trivial difficulties. We have clarified and highlighted our technical novelty (including the difficulties) and contributions in our global response above (point 1). Here we give a brief summary:\n- The analysis of our weighted information gain (Theorem 1) is non-trivial, and is a novel contribution especially compared to quantum linear bandits [32] whose analysis didn't involve information gain. It may also be **of broader independent interest**.\n- The proof of our confidence ellipsoid (Theorem 3) also requires non-trivial techniques and insights, such as the recognition to apply the concentration inequality for 1-sub-Gaussian noise. It is also **novel because it is closely tied to our algorithmic design**.\n- We have used the techniques and insights from the proof of our Theorem 3 to **improve the confidence ellipsoid and hence the regret of quantum linear bandits [32]**, which is another important contribution of ours.\n- We've also made important empirical contributions by conducting a more realistic AutoML experiment and **an experiment using a real quantum computer**, both of which were not done by previous works on quantum bandits [32]. We also achieved significantly better performances than quantum linear bandits [32] and classical GP-UCB [28].\n\nIn addition to the individual novel contributions listed above, another major aspect of our novelty and technical difficulty lies in **identifying the different required techniques** (e.g., weighted information gain, concentration for 1-sub-Gaussian noise) and **integrating them into a coherent analytical framework**, which we think is highly non-trivial. \n\nTherefore, we think that our work has made important novel technical contributions, which required overcoming non-trivial technical difficulties. Please refer to our global response above (point 1) for more details.\n\n---\n\n> 2. I notice that the authors of [32] showed their Q-LinUCB algorithm has a regret of $\\mathcal{O}(\\log^{5/2}T)$ for bounded noise, but this paper said the regret is $\\mathcal{O}(\\log^{3/2}T)$ (see line 350) when citing [32]. Is this because the analysis of [32] is not tight? Please confirm it since one of the contributions of this paper is an improvement over Q-LinUCB. If you indeed improve the regret from $\\mathcal{O}(\\log^{5/2}T)$ to $\\mathcal{O}(\\log^{3/2}T)$, this would increase the contributions of the paper.\n\nIf we understand correctly, you are referring to the upper bound on the **expected regret** of Q-LinUCB [32] (reported in Table 1 of [32]), which is indeed of the order $\\mathcal{O}(\\log^{5/2}T)$. To clarify, in our paper, we have only focused on **high-probability regret** (instead of expected regret), and the high-probability regret of Q-LinUCB [32] is of the order $\\mathcal{O}(\\log^{3/2}T)$ (Theorem 3 of [32], equation 37) which is consistent with what we have reported in our paper (line 350). The additional factor of $\\mathcal{O}(\\log T)$ in the expected regret results from the term $\\log(\\frac{m}{\\delta})$ in the high-probability regret, because [32] has set $\\delta=\\frac{m}{T}$ to convert the high-probability regret to expected regret.\nIn fact, the expected regret of our Q-GP-UCB with the linear kernel can also be easily derived, and it is also of the order $\\mathcal{O}(\\log^{5/2}T)$ which matches the expected regret of Q-LinUCB [32]. \n\nMore importantly, **for both high-probability regret and expected regret**, **our Q-GP-UCB (with the linear kernel) indeed improves over Q-LinUCB [32]** by a factor of $\\mathcal{O}(\\sqrt{d})$ (lines 348-350).\n\n---\n\nThank you again for your comments. We hope our additional clarifications could improve your opinion of our paper.\n"}]

Author rebuttal:

We'd like to sincerely thank all reviewers for your constructive feedback and for appreciating our contributions.
For example, Reviewer Hp2A and Reviewer 5kMD have acknowledged that our paper "introduces the first quantum BO algorithm", Reviewer pGF9 has commented that our work "may be of broader interest", Reviewer n5g2 "particularly likes" the way we "showcase our **strengthened analysis**" and acknowledges our "**elegant combinations of techniques and careful analyses**", Reviewer 5kMD has commented that our work "offers more evidence of quantum advantages over classical computers" and "**enjoys reading this paper very much**". We are deeply encouraged by these comments.

We have provided individual responses to your questions below, and have also highlighted two points here.

---

# 1. Technical novelty and contributions.

Here we clarify and highlight some of our major technical novelty and contributions:

- Weighted information gain (Theorem 1): Our proof of Theorem 1, despite following the analysis of [30], is non-trivial since it requires carefully tracking the impact of the weights $1/\epsilon_s^2$ throughout the analysis (lines 257-258). Our proof of weighted information gain, as well as its adoption in the analysis of quantum bandits, is also novel to the best of our knowledge, especially when compared with the analysis of quantum linear bandits [32] which did not involve information gain at all. More importantly, our Theorem 1 may be **of broader independent interest** for future works using weighted kernel ridge regression (Sec. 4.1).
- Confidence ellipsoid (Theorem 3): Despite following the analysis of [9], our proof of Theorem 3 also requires non-trivial analyses and insights, such as **the recognition to apply the concentration inequality for 1-sub-Gaussian noise**. To the best of our knowledge, our technical proof and insights here are **novel since they is closely tied to our algorithmic design** (specifically, our QMC subroutine which is required to guarantee 1-sub-Gaussian noise, lines 297-307), and they are the core reasons why we can improve over the regret bound of quantum linear bandits [32] (see below).
- Improvement over quantum linear bandits [32]: Our regret upper bound (when using the linear kernel) is tighter than the regret of quantum linear bandits [32] (Sec. 5.6). Additionally, by adopting our proof techniques and insights for our Theorem 3, we have **improved the confidence ellipsoid and hence the regret bound of quantum linear bandits [32]** (Theorem 6) to match our result. This is another important contribution of ours.
- Empirical contributions: Our empirical experiments also represent important contributions, as they may be significant steps towards assessing the real-world potential of quantum bandit algorithms. Specifically, to the best of our knowledge, our paper is the first work on quantum bandits to include a non-synthetic experiment (AutoML experiment, Fig. 1 c-d) and **an experiment using a real quantum computer** (Fig. 4 on page 27). Moreover, in our experiments, we've shown that our quantum BO significantly outperforms quantum linear bandits [32] and classical GP-UCB [28].


In addition to the individual novel contributions listed above, another major aspect of our novelty and technical difficulty lies in **identifying the different required techniques** (e.g., weighted information gain, concentration for 1-sub-Gaussian noise) and **integrating them into a coherent analytical framework**, which we think is highly non-trivial. 

So, we think that our work has made important novel technical contributions compared with the previous works. We'll also revise our paper to further clarify our technical novelty and contributions.

---

# 2. Other kernels such as the Matern kernel.

In this work, we've focused on the commonly used squared exponential (SE) kernel, and significantly improved the regret bound over the classical setting. We've also analyzed the regret of our algorithm with the linear kernel, and shown that it achieves a better regret bound than quantum linear bandits [32].

For the Matern kernel with smoothness parameter $\nu$, we can in fact also derive a regret bound of the order $\widetilde{\mathcal{O}}(T^{(3d)/(2\nu+d)})$ (ignoring log factors, we'll add more details on this after revision). This **improves over the state-of-the-art classical regret upper bound of $\widetilde{\mathcal{O}}(T^{(\nu+d)/(2\nu+d)})$ when the reward function $f$ is sufficiently smooth** (when $\nu > 2d$). We think this smoothness condition for the Matern kernel is reasonable, which can be justified by drawing analogy between our work (as the first work on quantum BO) and the classical GP-UCB [28]: For the Matern kernel, **the classical GP-UCB** [28] (with a regret bound of $\mathcal{O}(\gamma_T\sqrt{T})=\widetilde{\mathcal{O}}(T^{(\nu+3d/2)/(2\nu+d)})$) **also requires the function $f$ to be sufficiently smooth** (i.e., $\nu>d/2$) to achieve a sub-linear regret. This requirement for smooth functions was only removed in later works (e.g., [19,25,31]), which used sophisticated algorithmic designs and analyses to improve the regret of classical GP-UCB to $\mathcal{O}(\sqrt{\gamma_T T})=\widetilde{\mathcal{O}}(T^{(\nu+d)/(2\nu+d)})$. Similarly, because our Q-GP-UCB is the first BO algorithm in the quantum setting (analogous to GP-UCB [28] in the classical setting), we think it's expected and reasonable that our Q-GP-UCB **also** requires the function $f$ to be smooth for the Matern kernel (in order to improve over the regret in the classical setting), and we **also** leave it to future works to further improve the regret bound of our Q-GP-UCB for the Matern kernel.

We'll add the discussions here (as well as the associated technical details) about the Matern kernel to the paper after revision. We think that these additional results, given our already significantly improved regret for the SE kernel, will further improve the significance of our contributions.

Meta-review: The paper investigates a new version of (kernelized) multi-armed bandits with non-linear reward functions where the decision maker has access to a quantum oracle. With this setting the authors prove that we can go below the well-known \Theta(\sqrt(T)) regret lower bound. I particular, they introduce a new bandit algorithm called Quantum Gaussian Process Upper Confidence Bound (Q-GP-UCB) that with high probability can achieve O(polylog T) regret. This is an exciting result and definitely advances the state of the art of bandit theory and Bayesian optimization. It also opens new research questions (e.g., to what extent quantum oracles can enhance the bandit algorithms, etc).

The rebuttal phase was quite productive and the authors have clarified all the concerns of the reviewers. Given this, I strongly recommend accepting this paper.
Decision: Accept (poster)