Regret Bounds for Safe Gaussian Process Bandit Optimization

2020·arXiv

Abstract

1 Introduction

Stochastic bandit optimization has received significant attention in applications where a learner must repeatedly deal with an unknown random environment and observations are costly to obtain. At each round, the learner chooses an action x and observes a noise-perturbed version of an otherwise unknown reward function f(x). The goal is to minimize the so-called cumulative pseudo-regret, i.e., the difference between the expected T -period reward generated by the algorithm and the optimal expected reward if f was known to the learner. The most well-studied case is when the unknown function f comes from a finite dimensional linear model, with regret bounds provided by [Dani et al., 2008, Abbasi-Yadkori et al., 2011, Rusmevichientong and Tsitsiklis, 2010] for Upper Confidence Bound (UCB) based algorithms. In a more general setting, the expected reward is a sample from a Gaussian Process (GP), with regret bounds first provided by [Srinivas et al., 2010]. GPs are a popular choice for modelling reward function in Bayesian optimization methods as well as experimental design with applications in medical trials and robotics, e.g., [Berkenkamp et al., 2016b, Akametalu et al., 2014, Ostafew et al., 2016, Berkenkamp et al., 2016a]. In a closely related line of work, [Srinivas et al., 2010, Valko et al., 2013, Chowdhury and Gopalan, 2017] proposed kernelized UCB algorithms for settings where the reward is an unknown arbitrary function in a reproducing kernel Hilbert space (RKHS), and provided regret bounds through a frequentist analysis. A variant of this problem considers an environment that is also subject to a number of unknown safety constraints. The application of stochastic bandit optimization in safety-critical systems requires the learner to select actions that satisfy these safety constraints at each round, in spite of uncertainty regarding the safety requirements.

In this paper, we consider a stochastic bandit optimization problem where both the reward function f and the constraint function g are samples from Gaussian Processes. We require that the learner’s chosen actions respect safety constraints at every round in spite of uncertainty about safe actions. This setting was first studied in [Sui et al., 2015] in the specific case of a single safety constraint of the form and later in [Sui et al., 2018], in the more general case of as adopted in our paper. In this case, the learner hopes to overcome the two-fold challenge of keeping the cumulative regret as small as possible while ensuring that selected actions respect the safety constraints at each round of the algorithm. We present SGP-UCB, which is a safety-constrained variant of GP-UCB proposed by [Srinivas et al., 2010]. To ensure constraint satisfaction, SGP-UCB restricts the learner to choose actions from a conservative inner-approximation of the safe decision set that is known to satisfy safety constraints with high probability given the algorithm’s history. The cumulative regret bound of our proposed algorithm (given in Section 3 as our main theoretical result) implies that SGP-UCB is a no-regret algorithm. This is the main difference of our results compared to the algorithms studied in [Sui et al., 2015, Sui et al., 2018] that only come with convergence-but, no regret- guarantees. Throughout the paper, we discuss in detail the differentiating features of our algorithm from existing ones.

Notation. We use lower-case letters for scalars, lower-case bold letters for vectors, and upper-case bold letters for matrices. The Euclidean norm of a vector x is denoted by . We denote the transpose of any column vector x by . Let A be a positive definite matrix and . The weighted 2-norm of v with respect to A is defined by . We denote the minimum and maximum eigenvalue of A by and . The maximum of two numbers is denoted . For a positive integer n, [n] denotes the set {1, 2, . . ., n}.

1.1 Problem Statement

The learner is given a finite decision set . At each round t, she chooses an action and observes a noise-perturbed value of an unknown reward function , i.e. . At every round, the learner must ensure that the chosen action satisfies the following safety constraint:

where is an unknown function and h is a known constant.1 We define the safe set from which the learner is allowed to take action as:

Since g is unknown, the learner cannot identify . As such, the best she can do is to choose actions that are in with high probability. We assume that at every round, the learner also receives noise-perturbed feedback on the safety constraint, i.e. .

Goal. Since our knowledge of g comes from noisy observations, we are not able to fully identify the true safe set and infer g(x) exactly, but only up to some statistical confidence for some . Hence, we consider the optimal action through an -reachable safe set for some :

as our benchmark. A natural performance metric in this context is cumulative pseudo-regret [Audibert et al., 2009] over the course of T rounds, which is defined by where is the optimal safe action that maximizes the reward in expectation over the , i.e., For the rest of this paper, we simply use regret to refer to the pseudo-regret and drop the subscript from .

A desirable asymptotic property of a learning algorithm is that as fast as possible as T grows, especially when actions are costly. Algorithms with this property are called no-regret. Thus, the goal of the learner is to follow a no-regret algorithm while ensuring all actions she chooses are safe with high probability.

Regularity Assumptions. The above specified goal cannot be achieved unless certain assumptions are made on f and g. In what follows, we assume that these functions have a certain degree of smoothness. This assumption allows us to model the reward function f and the constraint function g as a sample from a Gaussian Process (GP) [Williams and Rasmussen, 2006]. We now present necessary standard terminology and notations on GPs. A is a probability distribution across a class of smooth functions, which is parameterized by a kernel function that characterizes the smoothness of the function. The Bayesian algorithm we analyze uses and as prior distributions over f and g, respectively, where and are positive semi-definite kernel functions. Moreover, we assume bounded variance and . For a noisy sample , with i.i.d Gaussian noise the posterior over f is also a GP with the mean and variance :

where and is the positive definite kernel matrix . Associated with g, the mean and variance are defined similarly.

1.2 Related work

As mentioned in the introduction, the most closely related works to this paper are [Sui et al., 2015, Sui et al., 2018]. With the objective function denoted by f(x), [Sui et al., 2015] adopts a single constraint of the form , whereas [Sui et al., 2018, Berkenkamp et al., 2016a] consider the more general constraint set . As is the case in our paper, the objective and constraint are modeled by Gaussian Processes. For algorithmic design purposes, [Sui et al., 2015, Sui et al., 2018] further assume Lipschitzness on reward and constraint functions. These assumptions are not required in our framework. Moreover, both of the aforementioned papers seek to identify a safe decision with the highest possible reward given a limited number of trials; i.e., their goal is to provide best-arm identification with convergence guarantees. Instead, our paper focuses on a long-term performance characterized through cumulative regret bounds. A more detailed comparison to algorithms and guarantees of [Sui et al., 2015, Sui et al., 2018] is given in Section 4.

There exist other contexts where safety constraints have been applied to stochastic bandit optimization frameworks. To name a few, the recent work of [Usmanova et al., 2019] studies a safe variant of the Frank-Wolfe algorithm to solve a smooth optimization problem with unknown convex objective and unknown linear constraints that are accessed by the learner via stochastic zeroth-order feedback. The analysis aims at providing sample complexity results and convergence guarantees, whereas we aim to provide regret bounds. In contrast to our setting, the paper [Usmanova et al., 2019] requires multiple measurements of the constraint at each round of the algorithm. Other closely related works of [Amani et al., 2019, Amani et al., 2020] study the problem of safe linear and generalized linear stochastic bandit where the constraint and loss functions depend linearly (directly or via a link function) on an unknown parameter. In fact, our algorithm can be seen as an extension of Safe-LUCB proposed by [Amani et al., 2019] to safe GPs. Specifically, in Section 3.1, we show that our algorithm and guarantees are similar to those in [Amani et al., 2019] for linear kernels. While [Amani et al., 2019] studies a frequentist setting, our results hold for a rich class of kernels beyond linear kernel.

In a broader sense, the problem of safe learning has received significant attention in reinforcement learning and controls. For example, [Berkenkamp et al., 2017] combines classical reinforcement learning with stability requirements by applying a Gaussian process prior to learn about system dynamics and shows improvement in both control performance and safe region expansion. Another notable work is [Schreiter et al., 2015], which presents an active learning framework that uses Gaussian Processes to learn the safe decision set. In [Turchetta et al., 2016], the authors address the problem of safely exploring finite Markov decision processes (MDP), where state-action pairs are associated with safety features that are modeled by Gaussian processes and must lie above a threshold. Also in the MDP setting, [Moldovan and Abbeel, 2012] proposes an algorithm that allows safe exploration in order to avoid fatal absorbing states that must never be visited during the exploration process. By considering constrained MDPs that are augmented with a set of auxiliary cost functions and replacing them with surrogates that are easy to estimate, [Achiam et al., 2017] proposes a policy search algorithm for constrained reinforcement learning with guarantees for near constraint satisfaction at each iteration. Furthermore, [Wachi et al., 2018] presents a reinforcement learning approach to explore and optimize a safety-constrained MDP where the safety values of states are modeled by GPs. From a control theoretic point of view, the recent work [Liu et al., 2019] studies an algorithmic framework for safe exploration in model-based control which comes with convergence guarantees, but no regret bound. Other notable work in this area include [Gillulay and Tomlin, 2011] that combines reachability analysis and machine learning for autonomously learning the dynamics of a target vehicle and [Aswani et al., 2013] that designs a learning-based MPC scheme that provides deterministic guarantees on robustness when the underlying system model is linear and has a known level of uncertainty.

2 A Safe GP-UCB Algorithm

We start with a description of SGP-UCB, which is summarized in Algorithm 1. Similar to a number of previous works (e.g., [Sui et al., 2018, Amani et al., 2019]), SGP-UCB proceeds in two phases to balance the goal of expanding the safe set and controlling the regret. Prior to designing the decision rule, the algorithm requires a proper expansion of . Hence, in the first phase, it takes actions at random from a given safe seed set until the safe set has sufficiently expanded (discussion on other suitable sampling strategies in the first phase is provided in Appendix G). In the second phase, the algorithm exploits GP properties to make predictions of f from past noisy observations . It then follows the Upper Confidence Bound (UCB) machinery to select the action. In the absence of constraint (1), UCB-based algorithms select action such that is a high probability upper bound on . Specifically, SGPUCB constructs appropriate confidence intervals of f for (see (6)). However, the safety constraint (1) requires the algorithm to have a more delicate sampling rule as follows.

The algorithm exploits the noisy constraint observations to similarly establish confidence intervals for the unknown constraint function such that for . These confidence intervals allow us to design an inner approximation of the safe set (see (9)). The chosen actions belong to which guarantees that the safety constraint (1) is met with high probability. In sections 2.1 and 2.2, we explain the first and second phases of the algorithm in detail.

2.1 First Phase: Exploration phase

The exploration phase aims to reach a sufficiently expanded safe subset of . The stopping criterion for this phase is to reach an approximate safe set within which lies with high probability. The algorithm starts exploring by choosing actions from at random (see Appendix G for discussion on alternative suitable sampling rules in the first phase). After rounds of exploration, where is passed as an input to the algorithm, SGP-UCB exploits the collected observations to obtain a reasonable estimate of the unknown function g and consequently to establish an expanded safe set which contains with high probability.

2.2 Second Phase: Exploration-Exploitation phase

In the second phase, the algorithm follows an approach similar to GP-UCB [Srinivas et al., 2010] in order to balance exploration and exploitation and guarantee the no-regret property. At rounds , SGP-UCB uses previous observations to estimate and predict f. It creates the following confidence interval for f(x):

where,

Confidence intervals corresponding to g(x) are defined in a similar way. We choose according to Theorem 1 to guarantee and for all and t > 0 with high probability. Theorem 1 (Confidence Intervals, [Srinivas et al., 2010]). Pick and set , then:

with probability at least .

Using the above defined confidence intervals and , the algorithm is able to act conservatively to ensure that safety constraint (1) is satisfied. Specifically, at the beginning of each round , SGP-UCB forms the following so-called safe decision sets based on the mentioned confidence bounds:

Recall that for all t > 0 with high probability. Therefore, is guaranteed to be a set of safe actions with the same probability. After creating safe decision sets in the second phase, the algorithm follows a similar decision rule as in GP-UCB algorithm in [Srinivas et al., 2010]. Specifically, is chosen such that:

3 Regret Analysis of SGP-UCB

Consider the following decomposition on the cumulative regret:

where is the instantaneous regret at round t.

Bounding Term II. The main challenge in the analysis of SGP-UCB compared to the classical GP-UCB is that may not lie within the estimated safe set at all rounds of the algorithm’s second phase if is not properly chosen.

In the following sections, we show how is appropriately chosen such that with high probability for all . Having said that, we bound the second term of (11) using the standard regret analysis which appears in [Srinivas et al., 2010]. Specifically, the bound depends on the so-called information gain which quantifies how fast f can be learned in an information theoretic sense. Concretely, , is the maximal mutual information that can be obtained about the GP prior from t samples. Information gain is a problem dependent quantity: its value depends on the given decision set and kernel function . For any finite , it holds [Srinivas et al., 2010]:

While is generally bounded by , it has a sublinear dependence on for commonly used kernels (e.g. Gaussian kernel).

Bounding Term I. Since for the first rounds actions are selected at random, the bound on Term I is linear in . In other words, the upper bound on the first term is of the form , where diamfor some C > 0 if is an RBF kernel with parameter , otherwise such that (see Lemma 6 in Appendix D for details):

Next, we need to find the value of such that with high probability for all . The following lemma, proved in Appendix A, establishes a sufficient condition for which is more convenient to work with.

From Lemma 1, it suffices to establish an appropriate upper bound on the RHS of (14) to determine the duration of the first phase, i.e., .

A positive semi-definite kernel function is associated with a feature map that maps the vectors in the primary space to a reproducing kernel Hilbert space (RKHS). In terms of the mapping , the kernel function is defined by:

Let denote the dimension of (potentially infinite) and define the matrices at each round t. Using this notation, we can rewrite as (see Appendix E for details):

In the following two subsections, we discuss how this expression helps us control for . Depending on the type of kernel functions and their corresponding , we derive different expressions for in Theorems 2 and 3.

3.1 Constraint with finite-dimensional RKHS

In this section we consider g with finite dimensional RKHS. Linear and polynomial kernels are special cases of these types of functions. For a linear kernel and a polynomial kernel , the corresponding is d and, respectively [Pham and Pagh, 2013].

Let Unifbe a d-dimensional random vector uniformly distributed in . At rounds , SGPUCB chooses safe iid actions . We denote the covariance matrix of by . A key quantity in our analysis is the minimum eigenvalue of denoted by:

Regarding the definition of in (16), we show that if can be controlled for all by appropriately lower bounding the minimum eigenvalue of the Gram matrix , which is possible due to the randomness of chosen actions in the first phase.

Lemma 2. Assume , and . Then, for any , provided , the following holds with probability at least ,

Consequently, for all .

We present the proof in Appendix B.

Combining Lemmas 1 and 2 gives the desired value of that guarantees for all with high probability. Putting these together, we conclude the following regret bound for constraint with corresponding finite-dimensional RKHS.

Theorem 2 (Regret bound for g with finite dimensional RKHS). Let the same assumptions as in Lemma 2 hold. Let and define . Then for sufficiently large T and any , with probability at least :

See Appendix D for proof details.

Linear Kernels. We highlight the setting where f and g are associated with linear kernels as a special case. In this setting the primal space and the corresponding RKHS are the same. Let k be a linear kernel with mapping , and y be the corresponding observation vector. Therefore, we have where . We drive the following from (16):

where . Thus, we observe the close relation in these notations with that in Linear stochas- tic bandits settings, (e.g. see [Dani et al., 2008, Abbasi-Yadkori et al., 2011]). As such, our setting is an extension to [Amani et al., 2019], where linear loss and constraint functions have been studied (albeit in a frequentist setting).

3.2 Constraint with infinite-dimensional RKHS

Now we provide regret guarantees for a more general case where the underlying RKHS corresponding to g can be infinite-dimensional.

In the infinite-dimensional RKHS setting, controlling for can be challenging. To address this issue, we focus on stationary kernels, i.e., , and apply a finite basis approximation in our analysis. Particularly, we consider which maps the input to a lower-dimensional Euclidean inner product space with dimension such that:

Definition 1 (-uniform approximation). Let be a stationary kernel, then the inner product in -uniformly approximates if and only if:

Due to the infinite dimensionality of , there is no notion for minimum eigenvalue of . Hence, we adopt an -unifrom approximation to bound for all by lower bounding the minimum eigenvalue of the approximated matrix instead. The argument follows the same procedure as in Lemma 2, other than an error bound on caused by the -unifromly approximation is required.

We consider to be an ()-uniform approximation and denote the covariance matrix of by with minimum eigenvalue:

Lemma 3. Assume that is a stationary kernel, and defined in (22) is positive. Fix . Then, it holds with probability at least for all ,

provided that .

Technical details on how analytically helps us obtain this upper bound on for all by lower bounding the minimum eigenvalue of are deferred to Appendix C. Putting these together, we obtain the regret bound for constraint with corresponding infinite-dimensional RKHS in the following theorem.

Figure 1: Illustration of SGP-UCB: (a) The blue and red solid lines denote the unknown reward function f and constraint function g, respectively. The dashed green line represents the threshold , the gray bar shows the safe seed set , and the red star is the optimum value of f through . (b,c) The dashed purple and orange lines are the estimated GP mean functions corresponding to f and g, respectively at rounds 50 and 200.

Theorem 3 (Regret bound for g with infinite dimensional RKHS). Assume there exists an -uniform approximation of stationary kernel with for which defined in (22) is positive. Let and

and define . Then, for sufficiently large T and any , with probability at least :

Complete proof is given in Appendix D.

Depending on the feature map approximation , the dimension can be appropriately chosen as a function of the algorithm’s inputs and d to control the accuracy of the approximation. We emphasize that our analysis is not restricted to specific approximations (see Appendix F for details). We focus on the Quadrature Fourier features (QFF) studied by [Mutny and Krause, 2018] who show that for any stationary kernel k on whose inverse Fourier transform decomposes product-wise, i.e., , we can use Gauss-Hermite quadrature [Hildebrand, 1987] to approximate it. The results in [Mutny and Krause, 2018] imply that the QFF uniform approximation error decreases exponentially with . More concretely, in this case, features are required to obtain an -accurate approximation of the SE kernel .

4 Comparison to existing algorithms

A few remarks regarding the differences between our algorithm and existing work on safe-GP optimization are in order. We first remark on the assumptions placed on the safe seed set in our work, which might appear restrictive when compared to those in the closely related works of [Sui et al., 2015, Sui et al., 2018]. Specifically, our theoretical guarantees require the safe seed set to satisfy assumptions put forth in Theorems 2 and 3, which would ensure that and . For instances with dimension discussed in Section 3.1, a sufficient condition that guarantees is that contains at least actions, such that their maps into each corresponding RKHS form linearly independent vectors. For example, for linear constraints the size of the seed set needs only to be linear in the dimension d. Hence, our analysis suggests that Safe GP learning is easy when the safety constraint is simple (e.g. linear/polynomial kernels). However, for instances with dimension discussed in Section 3.2, the assumption holds if at least actions with linear independent corresponding exist in . As a corollary, employing QFF for SE kernels in the analysis requires to contain at least

actions.

Figure 2: Regret comparison

In comparison, the safe-GP algorithms proposed by [Sui et al., 2015, Sui et al., 2018, Berkenkamp et al., 2016a] can start from a safe seed set of arbitrary size; However, this comes at a costs: 1) There is no guarantee that they are able to explore the entire space to reach a sufficiently expanded safe set that includes ; 2) They require the functions f and g to be Lipschitz continuous with known constants. More specifically, in all the above mentioned work a onestep reachablity operator for a single constraint function g is defined as follows: , where L is the Lipschitz constant corresponding to the constraint function g. Then they define an -reachable safe set by , where

n-step reachability operator starting from the safe seed set [Sui et al., 2015]. The above stated -reachable safe set clearly depends on . The optimization benchmark in [Sui et al., 2015, Berkenkamp et al., 2016a] is , which varies on a case by case basis depending on .

Instead, our benchmark is which satisfies since for any choice of . Similarly, the optimization goal of StageOpt [Sui et al., 2018] is approaching for an arbitrary safe seed set , where is the round at which the first phase of StageOpt, ends under the condition , where is the set of potential expander points that is created at each round t and is the width of confidence interval of constraint function g(x) at round t (see [Sui et al., 2018]). Hence, as pointed out in [Sui et al., 2018], given an arbitrary seed set, it is not guaranteed that they will be able to discover the globally optimal decision , e.g. if the safe region around is topologically separate from that of . On the other hand, given its stronger assumptions on the safe seed set, our algorithm does not suffer from this issue.

Our second remark is concerning the fundamentally different goals of our algorithm versus that of [Sui et al., 2015, Sui et al., 2018, Berkenkamp et al., 2016a]. Unlike SGP-UCB, the proposed algorithms in the latter works are not focused on regret minimization; rather, their focus is on best arm identification through safe exploration, i.e., providing convergence guarantees to the reachable optimal solution defined in the previous remark. We refer the reader to Appendix G for more clarifications on the algorithmic design differences of SGP-UCB and the algorithm studied by [Sui et al., 2015] and their implications on cumulative regret analysis.

5 Experiments

In this section, we analyze SGP-UCB through numerical evaluations on synthetic data. We first give an illustration of how our algorithm performs by depicting the estimated f and g and the expanded safe sets at certain rounds. The second experiment seeks to compare SGP-UCB’s performance against a number of other existing algorithms.

In Figure 1, we give an illustration of SGP-UCB’s performance. For the sake of visualization, we implement the algorithm in a 1-dimensional space and connect the data points since we find it instructive to also depict estimates of f and g as well as the growth of the safe sets. The algorithm starts the first phase by sampling actions at random from a given safe seed set. After 50 rounds, in Figure 1b, the safe set has sufficiently expanded such that the optimal action lies within the . Figure 1c shows the expansion of the safe set after 200 rounds, which still includes .

Figure 2 compares the average per-step regret of SGP-UCB against a number of closely related algorithms over 30 realizations (we include the error bars in figures presented in Appendix H). In particular, we compare against 1) StageOpt [Sui et al., 2018]; 2) SafeOpt-MC [Berkenkamp et al., 2016a] that generalizes SafeOpt [Sui et al., 2015] to settings with multiple constraints possibly different than the objective function f; 3) A heuristic variant of GP-UCB, which proceeds the same as SGP-UCB except that there is no exploration phase, i.e., ; 4) The standard GP-UCB with oracle access to the safe set.

We evaluated regret on synthetic settings with reward and constraint functions corresponding to SE kernels with hyperparameters 1 and 0.1, respectively. Parameters and have been chosen in all settings. The decision sets are time-independent sets of 100 actions sampled uniformly from the unit ball in . We implemented all algorithms by starting from the same seed set, i.e., . Figure 2 highlights the key role of the seed set’s size that is discussed in detail in Section 4. Figure 2c shows that once the safe seed set contains enough actions, SGP-UCB outperforms SafeOpt-MP and StageOpt whose -reachable set (i.e., in SafeOpt-MP and in StageOpt) do not include the true globally optimal considered in this paper. We also implemented SGP-UCB for settings where has relatively small number of safe actions. The results given in Figure 2a show the poor performance of SGP-UCB which is expected since is not large enough to explore the whole space for the purpose of safe set expansion. In Figure 2b, the regret curves are plotted for instances where is not large enough to reach the sufficiently expanded safe set including , but it is also not too small to get the expansion process stuck. In these instances, StageOpt performs well compared to SGP-UCB on average. What is common in all figures is the poor performance of Naive SGP-UCB (almost linear regret) compared to the others since it is never able to expand the safe set properly. When implementing SafeOpt-MC, we took the results of Theorem 1 in [Berkenkamp et al., 2016a] into account. We found numerically and modified the sampling rule after as follows: .

Another issue worth highlighting regrading implementation of SafeOpt-MC and StageOpt is construction of the safe sets . In our experiments, we relied on the exact definition of suggested in [Berkenkamp et al., 2016a, Sui et al., 2018], which depends on the Lipschitz constant of g. While we numerically calculate the Lipschitz constant to have a fair comparison, [Berkenkamp et al., 2016a, Sui et al., 2018] use only the GP model to ensure safety in their numerical experiments. As such, they construct in the same way as we form in (9). However, since the provided guarantees in these works are obtained with respect to the optimal action through an -reachable set, i.e., , which clearly depends on , this modification disregards the role of in the provided theoretical results.

As is the case in our proposed algorithm, StageOpt also proceeds in two distinct phases and the duration of the first phase is an input to the algorithm which needs to be specified. An interesting observation is that there are similarities between the first phase duration suggested for StageOpt and that introduced in our paper. These similarities mostly come from their dependence on parameters such as and . In our experiments, we did not rely on the value of that the theoretical results suggest. For both implementations, we stopped the first phase when the safe region plateaued for at least 20 iterations, and also hard capped at 100 iterations (a similar approach was adopted by [Sui et al., 2018]).

6 Discussion and future work

We studied a safe stochastic bandit optimization problem where the unknown payoff and constraint functions are sampled from GPs. We proposed SGP-UCB which is comprised of two phases: (i) a pure-exploration phase that speeds up learning of the safe set; (ii) a safe exploration-exploitation phase that focuses on regret minimization. We balanced the two-fold challenge of minimizing regret and expanding the safe set by properly choosing the duration of the first phase . Our analysis suggests that the type of kernels associated with the constraint functions plays a critical role in tuning and consequently affects the regret bounds. We used QFF [Mutny and Krause, 2018] as a tool to facilitate our analysis in settings with constraint function with infinite-dimensional RKHS. Beyond analysis, it is interesting to employ such approximations or other approaches like variational inference introduced by [Huggins et al., 2019] to further overcome computational associated with solving (10).

Several issues remain to be studied. While our algorithm is the first providing regret guarantees for safe GP optimization, it is not clear whether it is the best to apply. The answer could depend on the application. Hence, numerical comparisons on real application-specific data is worth investigating. More importantly, the other issue that needs to be addressed is that the existing guarantees (either in terms of cumulative regret, simple regret or optimization gap) for all safe-GP optimization algorithms, suffer from loose constants that make such comparisons hard. Indeed evaluating the performances of all these four algorithms in numerical experiments requires us to resort to empirical tuning of parameters like , which is an important challenge to overcome.

7 Acknowledgement

This research is supported by UCOP grant LFR-18-548175 and NSF grant 1847096.

References

[Abbasi-Yadkori et al., 2011] Abbasi-Yadkori, Y., Pál, D., and Szepesvári, C. (2011). Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pages 2312–2320.

[Achiam et al., 2017] Achiam, J., Held, D., Tamar, A., and Abbeel, P. (2017). Constrained policy optimization. In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pages 22–31. JMLR. org.

[Akametalu et al., 2014] Akametalu, A. K., Fisac, J. F., Gillula, J. H., Kaynama, S., Zeilinger, M. N., and Tomlin, C. J. (2014). Reachability-based safe learning with gaussian processes. In 53rd IEEE Conference on Decision and Control, pages 1424–1431. IEEE.

[Amani et al., 2019] Amani, S., Alizadeh, M., and Thrampoulidis, C. (2019). Linear stochastic bandits under safety constraints. In Advances in Neural Information Processing Systems, pages 9252–9262.

[Amani et al., 2020] Amani, S., Alizadeh, M., and Thrampoulidis, C. (2020). Generalized linear bandits with safety constraints. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3562–3566. IEEE.

[Aswani et al., 2013] Aswani, A., Gonzalez, H., Sastry, S. S., and Tomlin, C. (2013). Provably safe and robust learning-based model predictive control. Automatica, 49(5):1216–1226.

[Audibert et al., 2009] Audibert, J.-Y., Munos, R., and Szepesvári, C. (2009). Exploration–exploitation tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science, 410(19):1876–1902.

[Berkenkamp et al., 2016a] Berkenkamp, F., Krause, A., and Schoellig, A. P. (2016a). Bayesian optimization with safety constraints: safe and automatic parameter tuning in robotics. arXiv preprint arXiv:1602.04450.

[Berkenkamp et al., 2016b] Berkenkamp, F., Schoellig, A. P., and Krause, A. (2016b). Safe controller optimization for quadrotors with gaussian processes. In 2016 IEEE International Conference on Robotics and Automation (ICRA), pages 491–496. IEEE.

[Berkenkamp et al., 2017] Berkenkamp, F., Turchetta, M., Schoellig, A., and Krause, A. (2017). Safe model-based reinforcement learning with stability guarantees. In Advances in neural information processing systems, pages 908–918.

[Chowdhury and Gopalan, 2017] Chowdhury, S. R. and Gopalan, A. (2017). On kernelized multi-armed bandits. In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pages 844–853. JMLR. org.

[Contal et al., 2013] Contal, E., Buffoni, D., Robicquet, A., and Vayatis, N. (2013). Parallel gaussian process opti- mization with upper confidence bound and pure exploration. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 225–240. Springer.

[Dani et al., 2008] Dani, V., Hayes, T. P., and Kakade, S. M. (2008). Stochastic linear optimization under bandit feedback.

[Gillulay and Tomlin, 2011] Gillulay, J. H. and Tomlin, C. J. (2011). Guaranteed safe online learning of a bounded system. In 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 2979–2984. IEEE.

[Hildebrand, 1987] Hildebrand, F. B. (1987). Introduction to numerical analysis. Courier Corporation.

[Huggins et al., 2019] Huggins, J., Campbell, T., Kasprzak, M., and Broderick, T. (2019). Scalable gaussian pro- cess inference with finite-data mean and variance guarantees. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 796–805.

[Liu et al., 2019] Liu, A., Shi, G., Chung, S.-J., Anandkumar, A., and Yue, Y. (2019). Robust regression for safe exploration in control. arXiv preprint arXiv:1906.05819.

[Moldovan and Abbeel, 2012] Moldovan, T. M. and Abbeel, P. (2012). Safe exploration in markov decision processes. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pages 1451– 1458. Omnipress.

[Mutny and Krause, 2018] Mutny, M. and Krause, A. (2018). Efficient high dimensional bayesian optimization with additivity and quadrature fourier features. In Advances in Neural Information Processing Systems, pages 9005– 9016.

[Ostafew et al., 2016] Ostafew, C. J., Schoellig, A. P., and Barfoot, T. D. (2016). Robust constrained learning-based nmpc enabling reliable mobile robot path tracking. The International Journal of Robotics Research, 35(13):1547– 1563.

[Pham and Pagh, 2013] Pham, N. and Pagh, R. (2013). Fast and scalable polynomial kernels via explicit feature maps. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 239–247. ACM.

[Rahimi and Recht, 2008] Rahimi, A. and Recht, B. (2008). Random features for large-scale kernel machines. In Advances in neural information processing systems, pages 1177–1184.

[Rigollet, 2015] Rigollet, P. (2015). 18. s997: High dimensional statistics. Lecture Notes), Cambridge, MA, USA: MIT Open-CourseWare.

[Rusmevichientong and Tsitsiklis, 2010] Rusmevichientong, P. and Tsitsiklis, J. N. (2010). Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395–411.

[Schreiter et al., 2015] Schreiter, J., Nguyen-Tuong, D., Eberts, M., Bischoff, B., Markert, H., and Toussaint, M. (2015). Safe exploration for active learning with gaussian processes. In Joint European conference on machine learning and knowledge discovery in databases, pages 133–149. Springer.

[Srinivas et al., 2010] Srinivas, N., Krause, A., Kakade, S., and Seeger, M. (2010). Gaussian process optimization in the bandit setting: no regret and experimental design. In Proceedings of the 27th International Conference on International Conference on Machine Learning, pages 1015–1022. Omnipress.

[Sui et al., 2018] Sui, Y., Burdick, J., Yue, Y., et al. (2018). Stagewise safe bayesian optimization with gaussian processes. In International Conference on Machine Learning, pages 4788–4796.

[Sui et al., 2015] Sui, Y., Gotovos, A., Burdick, J. W., and Krause, A. (2015). Safe exploration for optimization with gaussian processes. In Proceedings of the 32Nd International Conference on International Conference on Machine Learning - Volume 37, ICML’15, pages 997–1005. JMLR.org.

[Tropp et al., 2015] Tropp, J. A. et al. (2015). An introduction to matrix concentration inequalities. Foundations and Trends Rin Machine Learning, 8(1-2):1–230.

[Turchetta et al., 2016] Turchetta, M., Berkenkamp, F., and Krause, A. (2016). Safe exploration in finite markov decision processes with gaussian processes. In Advances in Neural Information Processing Systems, pages 4312– 4320.

[Usmanova et al., 2019] Usmanova, I., Krause, A., and Kamgarpour, M. (2019). Safe convex learning under uncertain constraints. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2106–2114.

[Valko et al., 2013] Valko, M., Korda, N., Munos, R., Flaounas, I., and Cristianini, N. (2013). Finite-time analysis of kernelised contextual bandits. In Uncertainty in Artificial Intelligence.

[Vershynin, 2018] Vershynin, R. (2018). High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge University Press.

[Wachi et al., 2018] Wachi, A., Sui, Y., Yue, Y., and Ono, M. (2018). Safe exploration and optimization of constrained mdps using gaussian processes. In Thirty-Second AAAI Conference on Artificial Intelligence.

[Williams and Rasmussen, 2006] Williams, C. K. and Rasmussen, C. E. (2006). Gaussian processes for machine learning, volume 2. MIT press Cambridge, MA.

A Proof of Lemma 1

In this section we prove the Lemma 1, which states the condition under which it is guaranteed that with probability at least it holds that .

If we lower-bound the LHS of (25) using the definition of confidence interval , we obtain:

Since each confidence interval is built to contain the g(x) with high probability, it is clear that (25) is satisfied whenever (27) is true.

B Proof of Lemma 2

In order to bound the minimum eigenvalue of the Gram matrices , we use the Matrix Chernoff Inequality [Tropp et al., 2015].

Theorem 4 (Matrix Chernoff Inequality, [Tropp et al., 2015]). Consider a finite sequence of independent, random, symmetric matrices in . Assume that and for each index k. Introduce the random matrix . Let denote the minimum eigenvalue of the expectation E[Y],

Then, for any , it holds,

Proof of Lemma 2. Let for , such that each is a symmetric matrix with 0 and . In this notation, We compute:

Thus, Theorem 4 implies the following for any :

To complete the proof of the lemma, simply choose and in (28). This gives

Using this high probability lower bound on and the fact that

for all , we can easily obtain the desired bound on for all as follows:

C Proof of Lemma 3

In this section, we present the proof of Lemma 3.

First, we bound the ([Mutny and Krause, 2018]), where is the approximated posterior vari- ance.

Lemma 4 (Approximation of posterior variance, [Mutny and Krause, 2018]). Let the -uniformly approximates the kernel . Then,

Completing the proof of Lemma 3.

Proof. In order to complete the proof of Lemma 3, we employ a similar technique as in the proof of Lemma 2. In this direction, we bound using Theorem 4 such that with probability at least :

Note that for a QFF and RFF map .

Now we combine (31) and (33) to conclude that for and all with probability at least :

as desired.

D Proof of Theorems 2 and 3

First, we decompose the cumulative regret as follows:

The bound on the second term is standard in the literature (see for example [Srinivas et al., 2010]), but we provide the necessary details for completeness.

Lemma 5. Let be defined as in Theorem 1 and for . Then, for any with probability at least :

Proof. The proof is mostly adapted from [Srinivas et al., 2010]. We start with analysis of . If for , the following holds for all with probability at least :

where the second inequality follows from the definition of decision rule in (10) and the fact that for . For the last inequality we used the definition of the confidence interval in (6).

It follows from (37) that with probability at least :

where in (38) we used for any when and (39) follows from the definition of the mutual information between function values and the observations .

Lemma 6. With probability at least :

where diamfor some positive universal constant C > 0 if the function f is associated with an RBF kernel with parameter , otherwise .

Proof. By the GP assumption, f(x) is a random gaussian vector with mean 0 and covariance matrix K = . First, we assume is an RBF kernel. For an RBF kernel with parameter , [Vershynin, 2018] implies that for some universal constant :

Let be the gaussian width [Vershynin, 2018] of . Then for some universal constant C > 0:

The first inequality follows from the Markov inequality. The second inequality is an application of [Vershynin, 2018] combined with (42). Finally, the last inequality holds due to the fact that diam. Therefore, (43) implies that:

For a general setting, where is not an RBF kernel, we have:

For the second inequality see [Rigollet, 2015] and the last inequality holds because for all .

Hence, we deduce that:

We finalize the proof as follows:

provided that diamif is RBF kernel with parameter and .

Next, we show that when the Theorems 2 and 3 choices of are combined with Lemmas 2 and 3, respectively, (14) holds with probability at least for all .

Completing the proof of Theorem 2. Let T be sufficiently large such that . For all , Lemma 2 implies:

where the last inequality follows from the the definition of and the fact that . Hence, as stated in Lemma 1, (48) is equivalent to for all with probability at least .

We are now ready to complete the proof of Theorem 2. Let T sufficiently large such that:

We combine Lemmas 2, 5 and 6 to conclude that with probability at least :

Completing the proof of Theorem 3. Let T be sufficiently large such that . Employing Lemma 3, for we have:

where, in the first inequality we used . Note that assumptions and combined with (50) guarantees (14). Hence with probability at least for all . This fact allows us to bound Term II in (11) using Lemma 5.

Hence, we combine Lemmas 2, 5 and 6 to conclude that with probability at least :

E Posterior variance

F Uniform approximations

Definition 2 (QFF approximation). For SE kernel the Fourier transform is

the SE kernel is approximated as follows. Choose and , and construct the -dimensional feature map:

Lemma 7. [Mutny and Krause, 2018] Let be the SE kernel and . Then, for an -uniform QFF approximation in it holds that:

Lemma 7 implies that if , the uniform approximation error decreases exponentially with .

Our analysis and results are not limited to only stationary kernels whose Fourier transform decomposes product-wise, i.e., . There exists other uniform approximations adapted for a broader range of kernels. Specifically, for any stationary kernel, we can adapt the so-called Random Fourier Features (RFF) mapping introduced by [Rahimi and Recht, 2008].

Definition 3 (RFF approximation). For any stationary kernel if , the -dimensional feature map is constructed by:

where are i.i.d random variables in .

In the following theorem, we see how is chosen for an -uniform RFF approximation. Theorem 5. [Rahimi and Recht, 2008] Let be an stationary kernel . Then, for Random Fourier Features mapping and any it holds with probability at least :

provided that ,

While the uniform approximation error of QFF decreases exponentially with the size of the linear basis, applying the standard RFF [Rahimi and Recht, 2008] for any stationary kernels implies number of features are required for an -uniform RFF approximation; in other words, the uniform approximation error of RFF decreases with the inverse square root of the basis dimension. See Appendix F for details on QFF and RFF.

In comparison, QFF scales unfavorably with the dimensionality of the model. Hence, on one hand, QFF is unsuitable for an arbitrary high dimensional kernel approximation. The strengths of QFF manifest on problems with a low dimension or a low effective dimension. On the other hand, adapting RFF results in drastically large when a very small is required to control the accuracy of the approximation.

Figure 3: Average regret of SGP-UCB and SafeOpt with linear kernel.

G Comparison to existing algorithms

In this section we address the design of safe-GP optimization algorithms for the purpose of best arm identification (studied in [Sui et al., 2015, Sui et al., 2018]) versus that of regret minimization (studied in this paper) and highlight why regret guarantees are not the focus of the former.

A popular sampling criteria for best arm identification, which is also adopted for the safe-GP optimization setting by [Sui et al., 2015], relies on a purely exploratory approach referred to as the uncertainty sampling (a.k.a. maximum variance) rule. Here, the decision maker would select actions from a safe subset of true safe set, , with the highest variance of the GP estimate:

where and are the set of potential expanders and maximizers, respectively, and is the expanded safe set at round t that is constructed based on the knowledge of Lipschitz constant of f (see [Sui et al., 2015] for more details).

A general observation about the uncertainty sampling rule adopted in (60) is that while it is a provably good way to explore a function, it is not well suited to control regret, i.e., identifying points x where f(x) is large in order to concentrate sampling there without unnecessarily exploration. A relevant paper that has also highlighted this aspect is [Contal et al., 2013], which has applied the maximum variance rule (60) as a pure exploration approach for GP optimization (in the unconstrained setting), and yet proves theoretical upper bounds on the regret with batches of size K. To do so, they introduce the Gaussian Process Upper Confidence Bound and Pure Exploration algorithm (GP-UCB-PE) which combines the UCB strategy and Pure Exploration. GP-UCB-PE combines the benefits of the UCB policy with pure exploration queries which is based on uncertainty sampling rule in the same batch of K evaluations of f. While only relying on the maximum variance as the sampling criterion results in a greedy pure exploratory algorithm, the UCB strategy has been used in parallel with the pure explorative rule to obtain regret bound.

For the purpose of further clarification, we would also like to numerically highlight the unsuitability of the uncertainty sampling rule (60) for regret minimization. Consider the following example. In a relaxed version of Safe GP, let the objective function f be associated with linear kernels, the true safe set be known to the algorithm and contain all the standard basis vectors, , whose only non-zero element is the i-th element which is 1. At each round t, uncertainty sampling (60) maximizes the estimated variance, which is according to (20), over the given safe set. It can be shown that at each round t, it equivalently selects an eigenvector of corresponding to its minimum eigenvalue. Hence, the standard basis vectors, , are repeatedly selected, resulting in a linear regret. In order to illustrate this issue, we implemented SafeOpt on 20 instances where the kernels are linear and the true safe sets are as explained above (and of course unknown to the algorithm). We also evaluated SafeOpt when the cumulative regret is obtained with respect to the benchmark considered in [Sui et al., 2015], i.e., . Figure 3 compares the average regret curves of SGP-UCB and SafeOpt, with respect to both and true benchmark and . Please note that in this experiment, we estimated by . Figure 3 highlights the poor performance of SafeOpt compared to that of SGP-UCB when the regret is obtained with respect to true . Let us however reiterate that SafeOpt was not designed for regret minimization to begin with.

Figure 4: Average regret of SGP-UCB: uniform and uncertainty sampling in the first phase.

Figure 5:

A final remark is concerning a potential modification to SGP-UCB that can improve performance of the first phase but it is unclear how one can analyze this theoretically. Due to pure-explorative behaviour of uncertainty sampling, it might be an appropriate alternative for sampling actions form the safe seed set in the first phase to explore the function g. In Figure 4, we depict the average regret curves of SGP-UCB over 20 instances where f and g are sampled from GPs with SE kernels with hyper parameters 1 and 0.1, respectively. The curves highlight the performance of SGP-UCB when two different exploration approaches, uniform and uncertainty sampling, are applied in the first phase.

Figure 6:

Figure 7:

H Numerical study with error bars

Designed for Accessibility and to further Open Science