Bayesian Optimization with Switching Cost: Regret Analysis and Lookahead Variants

1 Introduction

Suppose we want to locate a global maximum f ∗ = f(x∗ ) from a continuous, compact, and bounded region X ⊂ Rp . The unknown objective function f : X → R is a black-box function that lacks closed-form expression and gradient information, making it difficult to optimize. In addition, evaluations of the function are often subject to a budget, thus necessitating a quick search of the global maximum in as few steps as possible. To obtain x∗ = argmaxx∈X f (x), a sampleefficient global optimization approach called Bayesian optimization is often adopted. A typical BO approach uses a surrogate model to approximate the unknown objective function f(x) and an acquisition function to guide the search. The surrogate model, using Gaussian processes in most practical applications, provides the most probable posterior estimates of functional values and uncertainties across the full search domain. The acquisition function is then used to maximize the expected marginal gain in the utility of the collected dataset to proceed with the sequential decision-making under uncertainty.

In this sequential optimization process, each new data point in {(xi, yi)}Ni=1 is revealed online, possibly perturbed by random noise. Given a limited sampling budget, the BO policy must consciously reason about exploring new regions with potentially high values and exploiting a known promising region with high confidence. In real-life applications such as crack detection in a wall or survivor search in the wild, a physical drone is often used to perform the search guided by a specific algorithm, which also needs to account for the total air time when moving the drone between locations and taking pictures. A total budget, such as the available battery power, must be considered in this case. The search policy needs to consider possible future paths and associated switching costs to make an optimal decision at the current step, a typical Dynamic Programming (DP) problem. However, exactly solving this intractable DP is NP-hard, especially in a continuous search space with infinite decision variables. Deciding on the continual search requires justifying a higher gain in the expected utility over the potential traveling cost.

In this paper, motivated by the aforementioned real-life applications, we consider the problem of sample-efficient optimization inclusive of a second criterion for success, which involves the cumulative distance traveled between subsequent tests. We formulate the problem as a constrained MDP and propose an efficient rollout algorithm based on a distanceadjusted Upper Confidence Bound (distUCB) heuristic to obtain the approximate DP solution. The proposed non-myopic BO policy effectively weighs the transition cost and gains over several future steps to determine the optimal sampling location at the current step. Our formulation highlights an automatic stopping criterion: the search terminates when the cumulative switching cost at a future candidate location exceeds the remaining budget, thus making it a finite-horizon MDP. In addition, we provide a theoretical analysis on the convergence guarantee of the cost-aware base policy using an information gain approach, as motivated by the sub-linear regret analysis in [Srinivas et al., 2009].

1.1 Literature Review

Bayesian optimization was first proposed by [Mockus and others, 1978] to optimize expensive, black-box functions using expected improvement (EI) as the acquisition function. Representative candidates in this increasingly crowded space of novel acquisition functions include upper confidence bound (UCB) [Srinivas et al., 2009], predictive entropy search (PES) [Hern´andez-Lobato et al., 2014], and knowledge gradient (KG) [Scott et al., 2011], among others.

The rising interest in non-myopic BO acquisition functions started from [Lam and Willcox, 2017], which considered the constrained BO problem and proposed a lookahead approach to maximize the long-term gain using a particular approximate DP algorithm called rollout. The rollout algorithm is a suboptimal control method used in the BO context to determine the following sampling location by maximizing an approximate long-term reward over a rolling horizon. It dates back to [Bertsekas et al., 1997] in the deterministic optimization case and was later extended to stochastic dynamic programs by [Goodson et al., 2016]. Recent work by [Yue and Kontar, 2020] characterizes the rollout improving nature in non-myopic policy under properly selected heuristics. It guides the stagewise rolling horizon based on the negative effect from a misspecified surrogate model. Since a typical rollout algorithm suffers from exponential growth in computational time as the rolling horizon increases, [Jiang et al., 2020] further accelerated the computation by jointly optimizing all decision variables in a multi-step tree. Besides, [Lee et al., 2021] proposed a cost-constrained BO framework using a non-myopic acquisition function and rollout approximation with EI per unit cost as the base policy.

On another front, the path-dependent switching cost in the sequential decision-making process was first explicitly considered in [Marchant and Ramos, 2012], where the distance traveled by a moving robot is incorporated as an additive penalty in the UCB acquisition function, resulting in the so-called distance-based upper confidence bound (DUCB). However, the two weighting parameters introduced by the variance and distance terms are challenging to be tuned simultaneously. The original convergence guarantee for UCB in [Srinivas et al., 2009] no longer exists in the presence of an additional distance term. To our knowledge, none of the existing work has considered explicitly incorporating switching costs in the non-myopic BO framework. To obtain substantial acceleration, we also employ an efficient rollout algorithm with quasi-Monte Carlo, sample average approximation (SAA) initially used in [Balandat et al., 2019], and the one-shot optimization scheme in [Jiang et al., 2020].

1.2 Summary of Contributions

We summarize our main contributions as follows:

• We provide the first analysis on BO with path-dependent switching cost formulated as a constrained MDP and develop an efficient rollout approximation algorithm that involves long-term cost-benefit analysis.
• Our framework offers an optimal policy (based on Bellman's principle of optimality) that automatically considers the termination condition if the cost of the ad-
• ditional search is uniformly higher than the remaining budget across the whole domain, which further results in an episodic simulation over future steps and saves the need to set the size of the rolling horizon.
• We perform a theoretical analysis of the convergence rate of the proposed algorithm and conduct both synthetic and real-data experiments to show the potential benefits of our proposed methodology compared with other baseline approaches.

2 Background

2.1 Bayesian Optimization

In a maximization setting, the objective is to find the global maximizer x∗ = argmaxx∈X f(x). Suppose we have now collected a set of n observations Dn = {(xi, yi)})ni=1 , where the sampled location xi ∈ Rp is a p-dimensional vector in a compact set X ⊂ Rp , and yi ∈ R is a noiseperturbed scalar observation with yi = f(xi) + ϵi. We assume a Gaussian noise ϵi ∼ N(0, σ2 ) with a homogenous variance σ2 across the whole domain. Under the GP framework, any finite set of random variables within the domain follows a multivariate Gaussian distribution, resulting in y1:n ∼ N(0,Kn), where we assume a constant zero mean function µ = 0 and Kn = Kn(x1:n, x1:n) denotes the covariance matrix, noting K(x1:n, x1:n)i,j = k(xi, xj). Specifically, for a new sampling location x∗ ∈ X, its corresponding observation y∗ again follows a normal distribution, i.e., p(y∗; x∗,Dn) = N(y∗|µ∗, σ2 ∗ ), where µ∗ = k(x∗, x1:n)T (Kn + σ2 I)-1 y1:n and σ2 ∗ = k(x∗, x∗) - k(x∗, x1:n)T (Kn + σ2 I)-1k(x∗, x1:n), and k(x∗, x1:n) = [k(x∗, x1), ..., k(x∗, xn)]T . We refer the readers to [Rasmussen and Williams, 2006] for a more comprehensive review of Gaussian processes.

In each BO iteration, the GP posterior is updated by refreshing its governing hyperparameters based on the available training set Dn, then choosing the next sampling location where the specified auxiliary acquisition function obtains its maximum. Locating the maximum of the acquisition function is also called the inner optimization, which happens per iteration in contrast to the outer optimization that seeks the global optimum of the unknown objective function. The newly acquired location and its observation are then appended to form Dn+1 = {Dn ∪ (xn+1, yn+1)}, completing one round of iteration and proceeding until the sampling budget exhausts.

2.2 Distance-Constrained Bayesian Optimization

The distance can be considered an additional cost constraint imposed on the optimizer. For example, a specific location may not be reachable due to the limited battery of a robot. In such cases, the optimizer should display a tradeoff between the utility of a sampling location and the cost it will incur if it decides to sample in that particular location, preferably considering future evolution should the learning proceeds.

There are different approaches to modeling the distance penalty by embedding it into the acquisition function to discount the utility of a candidate sampling location. Examples include subtracting from UCB the distance traveled from the current location to the candidate location. Specifically, in the DUCB formulation used in [Marchant and Ramos, 2012], the acquisition function for the next candidate location xn+1 with yn+1 ∼ N(µn, σ2n ) takes the following form:

where d(xn+1, xn) = √∑pi=1 (xin+1 -xin )2 denotes the general Euclidean distance between the current location xn of the optimizer and the next candidate location xn+1, βn+1 is a stage-wise weighting factor to set the level of confidence in the face of uncertainty, and ρn+1 is another weighting factor for the distance-induced penalty. Although being an intuitive formulation, this data-driven approach requires tuning two hyper-parameters simultaneously, which is both stage and domain-dependent and lacks the theoretical justification for setting the optimal hyper-parameters, as compared to the case of choosing βn = 2log(n2 2π2 /(3δ)) + 2plog(n2 pbr√log(4pa/δ)) in [Srinivas et al., 2009], where we use p to denote the dimensionality of the feature space.

Other heuristics include multiplying the original acquisition function with an indicator function that specifies the feasible region of the optimizer at the current step, as originally proposed in [Gardner et al., 2014]. However, explicitly confining the optimizer within the feasible region is not conducive to the cost-performance tradeoff in the early stages; the optimizer displays no foresight on budget consumption when the feasible region covers the whole domain. In addition to the myopic nature of the acquisition function, the multiplying indicator function also makes it inconvenient for theoretical analysis.

More recent work by [Lee et al., 2021] divides the acquisition function (using EI) by the corresponding cost to get the EI per unit cost (EIpu) in a multi-step lookahead setting, which is most similar to our work. Although [Lee et al., 2021] uses the rollout algorithm to obtain an approximate DP solution with a theoretical guarantee on its sequential improving nature, no analysis on the convergence rate of the base policy is given. In our experiment section later, we also show the superior performance of our proposed distUCB policy over EIpu and other alternatives.

2.3 Regret Analysis Using Information Gain

To better characterize the performance of the online optimizer in BO setting, we denote ri = f(x∗ ) - f(xi) as the instantaneous regret (or simple regret) of the online optimizer at step i due to not knowing the global optimum f ∗ in advance. The cumulative regret RN after N steps is derived by summing all instantaneous regrets: RN = ∑Ni=1 ri.

In order to bound the cumulative regret RN, we follow a similar approach in [Srinivas et al., 2009], using the maximum information gain γN = maxI(y1:N ; f1:N ) after N steps to provide an explicit sub-linear convergence rate. Here, I(y1:N; f1:N) = H(y1:N) - H(y1:N|f1:N) denotes the reduction in the uncertainty of f after obtaining N noisy measurements y1:N, where H(y1:N) = 12 log|2πe(KN + σ2 I)| is the marginal entropy and H(y1:N|f1:N) = 1 2 log|2πe(σ2 I)| is the conditional entropy under a multivariate Gaussian distribution with Gaussian noise. Plugging in, we have I(y1:N ; f1:N ) = 12 log|σ-1KN + I|.

Being a submodular function, the information gain I(y1:N; f1:N) reveals a property of diminishing return as N increases, which plays an important role in bounding γN as shown in [Srinivas et al., 2009].

2.4 Multi-Step Lookahead Acquisition Function

The sequential process in Bayesian optimization can be modeled as a Markov Decision Process (MDP), where the learning environment is characterized by a state space S, an action space A, a transition probability between different states P, and the reward R. In the context of BO, the state space S is the observed set of data Dn until the current time step n, and the action space A is the whole continuous domain X . A policy π = {π1, . . . , πN} specifies the sampling decisions for a total of N steps. Specifically, πn at any step n is a function that maps the current state Dn to the next sampling location xn+1, i.e., πn(Dn) = xn+1. The only transition probability is the probability of sampling yn+1 from its posterior:

An optimal policy can be derived by maximizing the sum of the current reward R(Dn, xn+1,Dn+1) and the longterm return that accounts for all possible randomness in both the locations and the functional evaluations, i.e., π∗ = argmaxπ∈Π ∑τ-1 i=0 R(Dn+i, πn+i(Dn+i),Dn+i+1). Following Bellman's principle of optimality, the optimal policy not only selects the current action (i.e., sampling location) that maximizes the reward but also assumes all future actions are made optimally.

Specifically, denote u(Dn) as the utility of the current training set Dn. Typically, u(Dn) = max{y1:n} in an improvement-based heuristic. The expected utility after acquiring an additional putative pair (§n+1, yn+1) can then be expressed as

where the expectation is taken over the random variable yn+1 at the candidate location xn+1. The optimal sampling location at time step n + 1 is:

where,

denotes the one-step expected marginal gain in utility, with the subscript indicating the number of lookahead steps into the future.

Now, assume a total lookahead horizon of τ steps into the future, forming a putative dataset Dn+τ = Dn ∪

{(xn+1, yn+1)} ∪ · · · ∪ {(xn+τ , yn+τ)}. The multi-step lookahead policy then chooses the next sampling location via:

where ατ (§n+1; Dn) = E(u(Dn+τ )|xn+1, Dn) - u(Dn) is the τ-step lookahead expected marginal gain in utility, with the expectation taken over all possible values of yn+1 as well as following pairs {(xn+i, yn+i)}τi=2 .

The τ -step nonmyopic acquisition function can also be decomposed into the sum of an immediate expected one-step lookahead gain in utility as well as the expected marginal gain for the remaining τ -1 steps. Adding and subtracting the onestep utility function gives the following recursive form:

Selecting the best sampling location with α∗ τ (xn+1;Dn) = maxxn+1∈Xατ(xn+1;Dn) amounts to directly maximizing the average-case long-term utility and follows the Bellman's principle of optimality: a sequence of optimal decisions starts with making the first optimal decision, followed by a series of optimal decisions conditioned on the previous outcome. The optimal multi-step lookahead acquisition function could be written as a DP formulation that consists of a series of nested maximization and expectation operations:

Choosing the next sampling action by maximizing the multistep lookahead acquisition function gives the optimal policy π∗ . However, solving this intractable DP problem is computationally challenging when the lookahead horizon becomes large. In most lookahead problems in the BO setting, the rollout algorithm has become a popular approximate DP solution that provides a good-quality solution in a reasonable computational time.

The rollout algorithm breaks the forward-backward pass in solving an intractable DP problem and instead completes a single forward pass. It starts by simulating a set of future values over the future τ horizon and uses a base policy with averaged results to approximate the value of the multi-step acquisition function. In this paper, we use a new distancebased UCB as the one-step base policy in the rollout algorithm to perform a multi-step lookahead selection of sampling locations. As it turns out, such a lookahead policy delivers a natural sense of impact: as the policy treks from point to point in the search space, a constant tradeoff between seeking the maximum function value and minimizing the switching cost exists. Considering such a tradeoff, even for 1 or 2 steps ahead, makes a difference in the overall search performance.

3 Methodology

Given a total traveling budget B, the goal of our moving robot is to seek the global maximum before its power drains. When the remaining budget is insufficient to support an additional sampling at the suggested location, the optimizer terminates and returns a recommendation based on the previously sampled locations. Mathematically, for a total of N steps, we have

where d(xi+1, xi) = ||xi+1 - xi||2 for i = 2, ...,N. We propose a new distance-adjusted UCB (distUCB) base policy to quantify the utility of a candidate location xn+1 across the whole domain:

where distUCB intuitively scales down the utility of the uncertain long-distance regions. Such formulation avoids another tuning parameter and permits theoretical analysis of its convergence rate. To facilitate the analysis of the regret bound, we absorb the distance-based scaling factor into βn+1 and denote it as βn+1,d to highlight its dependence on both the current step n and the switching cost. Thus,

which is also the reward function R in the constrained MDP (CMDP) setting. Next, we define the expected total return and cost of a policy π. For any policy π with a lookahead horizon of τ, the expected total return and cost are respectively defined as:

Here, V π τ (xn+1;Dn) is the action value at location xn+1, defined as the expected sum of current and future rewards till horizon τ , given training set Dn and following the policy π. C π τ (xn+1;Dn) denotes the associated expected total cost. The problem can thus be modeled as seeking the optimal policy π∗ (which maximizes αdistUCB(xn+i+1;Dn+i) in each lookahead stage) in the context of CMDP as follows:

where Π is the space of all admissible policies. When simulating future trajectories using rollout, only feasible trajectories are allowed if the remaining budget permits. Denote a base policy ˜π = {˜π1, . . . , ˜πN} used to approximate the optimal policy. When given a dataset Dn and simulating at a future stage i ∈ {0, . . . , τ - 1}, the corresponding decision rule ˜πn+i follows the base heuristic of maximizing the stagewise acquisition function αdistUCB(xn+i+1; Dn+i):

Algorithm 1: distUCB: distance-adjusted UCB

Data: GP prior µ0 and σ0, search domain X

Result: Estimated location of global maximum x∗ while ∑ni=1 di ≤B do Select next sampling location xn+1 = argmaxx∈χµn + βn,dσn; Query the corresponding observation yn+1 = f (xn+1) + ϵn+1; Update the training set Dn+1 = Dn ∪ (xn+1, yn+1); Update GP posterior to obtain µn+1 and σ2n+1 ; Output: x∗ = argmaxx∈Dn y(x)

Rolling out this heuristic policy till budget exhaustion gives the rollout policy, where the horizon τ differs for each feature path. When calculating the value function of the rollout policy, we use Monte-Carlo integration to approximate the expectation operator, giving:

To accelerate and stabilize the simulations, we use quasiMonte-Carlo based on the Sobol sequence and common random variables when using gradient-based updates based on the re-parameterization trick.

Since budget B is a limited scalar, we note that the nonmyopic acquisition function using rollout essentially solves a constrained finite-horizon dynamic program. The overall procedure is given in Algorithm 1.

4 Theoretical Analysis

To facilitate theoretical analysis, we make the following assumptions.

Assumption 1. Given constants a, b, and L, we assume that the kernel function k(x, x′ ) satisfies the following Lipschitz continuity for the confidence bound of the derivatives of GP sample paths f:

For example, the popular squared exponential kernel k(x, x′ ) = σ2 exp(- (x-x′ )2 2l2 ) with the length-scale parameter l and noise variance σ2 satisfies this assumption.

Of note, the assumption on Lipschitz continuity is standard as in the regret analysis of BO [Srinivas et al., 2009], which also includes the popular Mat´ern kernel. We introduce the main theorem on the cumulative regret bound of the singlestage distUCB algorithm.

4.1 Regret Bound Analysis (The Main Theorem)

Theorem 1. Let X ⊂ [0, r]p be compact and convex, p ∈ N, r > 0. Under Assumption 1, for any arbitrarily small δ ∈ (0, 1), choose βn,d = 2 d2 log 4πn δ + 2p d2 log(n2 brp√log( 4pa δ )), where ∑n≥1 π-1 n = 1, πn > 0. As n → ∞, we obtain a regret bound of O∗ (√pNγN). Specifically, with C1 = 8 log(1+σ-2 ) , we have:

We put the sketch proof for the main theorem in the appendix.

5 Experiments

We compare distUCB with EI, EIpu, and UCB rollout via both synthetic and real-world experiments. Among these benchmark methods, EI was first proposed in [Mockus and others, 1978], EIpu was proposed in [Lee et al., 2021] using non-myopic acquisition function and rollout approximation with EI per unit cost as the base policy, and UCB rollout was constructed by us in order to compare the effectiveness of considering the switching cost, which was obtained by combining UCB [Srinivas et al., 2009] method and rollout algorithm. Note that we did not consider DUCB due to its myopic nature and dependence on multiple hyperparameters involved; instead, our main benchmark under a similar setting is the EIpu acquisition function.

Our constrained Bayesian optimization problem essentially highlights a tradeoff between the search quality and distance traveled. An aggressive policy may achieve a higher function value (lower regret) but incur a significant switching cost, while a more cost-constrained policy will likely end up with a lower cost but at the expense of a higher regret. To this end, we study how the switching cost affects the test performance in multiple experiments, involving both synthetic and real data, and use the Euclidean distance to measure the distance between two points in the search space.

5.1 Synthetic Experiments

To make the comparison fair, we follow the setting of EIpu, using a Mat´ern 5/2 kernel for the GP with its hyperparameters learned via maximum likelihood estimation. These hyper-parameters are re-estimated by maximizing the evidence after each iteration, a common practice used in [Srinivas et al., 2009] and [Lee et al., 2021] .

We compare the distUCB algorithm with other baseline policies over classical functions used for global optimization: Ackley-2, Branin-2, and Hartmann-6, detailed in Table 1. We also repeat each experiment 30 times, reporting the mean and standard deviation across all repetitions. The total iteration budget N for each experiment is set to N = n0 +100, where n0 denotes the number of initial design points and is set as 20, 40, and 60 for the three synthetic functions, respectively. All experiments are evaluated on a Latin hypercube after normalization.

In addition, we add a homogeneous noise with a standard normal distribution with a standard deviation of 0.1, and set up 32 simulations in each Monte Carlo approximation to keep the same setting as EIpu. For a fair comparison, each method's number of lookahead steps is set to 3, although the horizon could be determined automatically based on the remaining budget.

In general, we observed that distUCB displays a better cost awareness in the tradeoff between cumulative regret and switching costs, as shown by the lowest cumulative switching cost together with a competing cumulative regret. As shown in Figure 1, distUCB performs nearly identically to UCB rollout on cumulative regret after 100 iterations, which is only marginally larger than EI and EIpu. However, distUCB incurs a much smaller cumulative switching cost among all the policies. This suggests that our method achieves competitive results in cumulative regret compared to baseline methods while consuming a much smaller budget. See the appendix for the experimental results of the other two synthetic functions for a similar observation.

The experiment results also suggest that our method works better on relatively high-dimensional problems, which is possibly due to the fast convergence in low-dimensional test functions. The switching cost is thus potentially a more costinducing factor in high-dimensional space. We choose two relatively high-dimensional real cases in the next section to validate our hypothesis.

5.2 Real Data Experiments

Many real-world experiments prefer a small jump (i.e., a lower switching cost) between test configurations. For example, search over a domain with a prior preference region identified by domain expertise or previous experience. The cost consideration in distUCB naturally fits such scenarios. Also, to make the tradeoff more explicit, we show the empirical dynamics between cumulative switching cost and simple regret, which is a better metric to measure the quality of the current proposal. Such comparison allows us to assess how the limited traversal distance impacts the quality of the optimization in a multi-objective sense.

Using a neural network model, we empirically evaluate distUCB on two hyperparameter tuning tasks for training a two-layer feed-forward neural network on two popular UCI datasets: breast cancer and spam, both commonly used in hyperparameter tuning experiments (see [Hu et al., 2022]). The breast cancer Wisconsin dataset has 569 data and 32 columns, where most features are continuous and nucleus-related. The label of each sample is the result of the diagnosis, including 357 benign cases and 212 malignant cases. The spam database contains 4601 samples (1813 of which are spam) and 58 attributes. For both data sets, we allocate 70% to training and 30% to the test set.

We consider tuning four hyperparameters: batch size, initial learning rate, learning rate schedule, and the number of hidden dimensions. For each of the four hyperparameters to be adjusted, the adjustment range is given: [32, 128], [1e - 6, 1.0], [1e - 6, 1.0], [0.5, 4]. We specify these four hyperparameters in each iteration before training a Multi-layer Perceptron (MLP) prediction model on the training set. The trained model is then scored over the test set, where the test set classification error is registered for the current iteration. Each iteration repeats 5 times.

The results of the four methods on two hyperparameter tuning experiments are shown in Figure 2. After 100 iterations, all four policies deliver a similar simple regret, showing a decreasing impact of the cost constraint for the distance-aware policy. However, distUCB algorithm consistently incurs a lower cumulative switching cost than the other three methods. All results reflect the central theme of a continuous tradeoff between simple regret, as a measure of optimization quality, and the cumulative switching cost, as an indication of total distance traveled. We further observe that such a tradeoff is more pronounced only in the early stage of the search; as iteration proceeds, all policies report a smaller optimality gap, yet only the cost-aware policy (in this case, distUCB) demonstrates the long-term benefit of a consistently lower cumulative switch cost.

6 Conclusion

In this paper, we proposed a cost-aware multi-step acquisition function to perform sequential sampling under uncertainty. Our proposed algorithm (distUCB) can deliver similar or better overall performance in the cumulative regret and switching cost. We provide a theoretically no-regret analysis of the base policy and show its superior empirical performance in a rollout policy compared with standard benchmark methods. Using synthetic and real-data experiments, we highlight the explicit tradeoff between global maximization (searching anywhere within the domain) and cost minimization (penalizing long-distance moves). Our work thus paves the way for further studies in cost-aware BO with non-myopic policies.

A Sketch Proof of The Main Theorem

Our proof relies on the confidence bound on the selected decision xn at stage n for an adequately selected hyperparameter βn,d, as well as a stage-wise discretization Xn ⊂ X used to obtain a bound of f(x∗ ). We use O∗ , a variant of the O notation to suppress the log factors.

Proof. Following a similar argument in [Srinivas et al., 2009], we have r2n ≤ 4d2βn,dσ2n-1 (xn) with probability ≥ 1 - δ as n → ∞. Since βn,d = 2 d2 log 4πn δ + 2p d2 log(n2 brp√log( 4pa δ )) and is non-decreasing in n, we can upper bound it by the final stage βN,d:

where we rely on the fact that k(xn, xn) = 1 for the SE kernel, thus σ2n-1 (xn) ≤ k(xn, xn) = 1. Note that (1 + σ-2 )σ2n-1 (xn) is a concave function for a given σ2n-1 (xn) ∈ [0, 1] with different values of σ-2 > 0. Using the first-order Taylor approximation to bound the concave function, giving σ2n-1 (xn)log(1 + σ-2 ) ≤ log(1 + σ-2σ2n-1 (xn)). Setting C2 = σ-2 log(1+σ-2 ) , we have:

Using Cauchy-Schwarz inequality, we have:

where C1 = 8σ2C2 and γN = maxI(y1:N; f1:N) is the maximum information gain after N steps of sampling. Thus,

Note that the form of our main theorem is quite similar with [Srinivas et al., 2009], although our stage-wise constant βn,d is different and includes a distance term.

Experiment Details

The experiment results on the Branin and Ackley functions are shown in Figure 3 and Figure 4. We observe a similar tradeoff in distUCB compared with other policies.

Ethical Statement

There are no ethical issues.

Acknowledgments

We thank Professor Chung-Piaw Teo for his constructive suggestions while preparing this manuscript.