On Kernelized Multi-Armed Bandits with Constraints
Authors: Xingyu Zhou
Bo Ji
Venue: NeurIPS 2022 Accept (2022)
Keywords: kernelized bandits
Gaussian process bandits
regret bounds
constraint violation

Abstract: We study a stochastic bandit problem with a general unknown reward function and a general unknown constraint function. Both functions can be non-linear (even non-convex) and are assumed to lie in a reproducing kernel Hilbert space (RKHS) with a bounded norm. This kernelized bandit setup strictly generalizes standard multi-armed bandits and linear bandits. In contrast to safety-type hard constraints studied in prior works, we consider soft constraints that may be violated in any round as long as the cumulative violations are small, which is motivated by various practical applications. Our ultimate goal is to study how to utilize the nature of soft constraints to attain a finer complexity-regret-constraint trade-off in the kernelized bandit setting. To this end, leveraging primal-dual optimization, we propose a general framework for both algorithm design and performance analysis. This framework builds upon a novel sufficient condition, which not only is satisfied under general exploration strategies, including \emph{upper confidence bound} (UCB), \emph{Thompson sampling} (TS), and new ones based on \emph{random exploration}, but also enables a unified analysis for showing both sublinear regret and sublinear or even zero constraint violation. We demonstrate the superior performance of our proposed algorithms via numerical experiments based on both synthetic and real-world datasets. Along the way, we also make the first detailed comparison between two popular methods for analyzing constrained bandits and Markov decision processes (MDPs) by discussing the key difference and some subtleties in the analysis, which could be of independent interest to the communities.

On Kernelized Multi-Armed Bandits with Constraints
Xingyu Zhou
Bo Ji Computer Science Virginia Tech Blacksburg, VA, USA boji@vt.edu
Electrical and Computer Engineering
Wayne State University Detroit, MI, USA
xingyu. wtw.:y/w..oouwwwyee.coo edu
Abstract
We study stochastic bandit problem with a general unknown reward function and general unknown constraint function. Both functions can be non-linear (even non-convex) and are assumed to lie in a reproducing kernel Hilbert space (RKHS) with bounded norm. In contrast to safety-type hard constraints studied in prior works, we consider soft constraints that may be violated in any round as long as the cumulative violations nature of soft constraints to attain a finer complexity-regred -egeerotrggrtttnnntaaaann trade-off in the kernelized bandit setting. To this end, leveraging primal-dual optimization, we propose a general framework for both algorithm design and performance analysis. This framework builds upon a novel sufficient condition, which only satisfied under general exploration strategies, including upper confidence bound (UCB), Thompson sampling (TS), and new ones based on random exploration, but also enables a unified analysis for showing both sublinear regret and sublinear or even zero constraint violation. We demonstrate the superior performance our proposed algorithms via numerical experiments based on both synthetic and real-world datasets. Along the way, we also make the first detailed comparison between two popular methods for analyzing constrained bandits and Markov decision processes (MDPs) by discussing the key difference and some subtleties the analysis, which could be of independent interest to the communities.
small. Our ultimate goal is to study how to utilize the
Introduction
Stochastic bandit optimization of an unknown function has recently gained increasing popularity due to its widespread real-life applications such as recommendations [1], cloud resource configurations [2]. and wireless power control [3]. each time f, an action v; is selected and then (noisy) bandit reward feedback is observed. The goal is to maximize the cumulative reward, or equivalently minimize the total regret due to choosing the optimal action in hindsight. To capture a generic function, researchers have turned to nonparametric models of f via Gaussian process or reproducing kernel Hilbert space (RKHS), which are able to uniformly approximate an arbitrary continuous function over compact set [4]. In this paper, as in [5, 6]. we consider the agnostic setting (i.e., frequentist-type), where assumed to fixed function an RKHS with a bounded norm (i.e., measure of smoothness). We call this setting frequentist type kernelized bandits (KB).
In addition generic non-linear or even non-convex function f. another common feature in practical applications is that there often exist additional constraints in the decision-making process such hard-constraint like safety or soft-constraint like cost. To this end, there have been exciting recent advances in the theoretical analysis of constrained kernelized bandits. In particular, [7-9] propose algorithms with convergence guarantees, while [10], the best our knowledge, the first
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

work that establishes regret bounds for their developed algorithm, although under the Bayesian-type setting. These algorithms mainly focus on KB with a hard constraint such as safety, i.e., the selected action in each round needs to satisfy the constraint with a high probability. Hence, compared to the unconstrained case, additional computation is required to construct safe action set in each round, which not only incurs additional complexity burdens, but often leads to conservative performance.
Motivations. In practice, there are also many applications that involve soft constraints that may be violated in any round. The goal is to maximize the total reward while minimizing the total constraint violations. For example, in wireless networking system, the reward could be the throughput while the constraint is that the average energy consumption is below threshold. In this case, the constraint can be violated at any time, and moreover. using less energy at one time instant allows one to use more in the next time instant, i.e., "compensation" across time (see a formal definition in (I) Furthermore, existing provably efficient algorithms [7-10] largely build on upper confidence bound (UCB) exploration, which often has inferior empirical performance compared to Thompson sampling (TS) exploration. Hence, another key question is whether one can design provably efficient CKB algorithms with general explorations. In summary, the following fundamental theoretical question remains open:
Can a finer complesitt-regret-connnn
trade-off be attained in CKB under general explorations?
Contributions. this paper, we take a systematic approach to affirmatively answer the above funda- mental question. In particular, we tackle the complexity- wei.itt--rrret-oooe constritnnt trade-off by formulating KB under soft constraints as a stochastic bandit problem where the objective is to maximize the cumulative reward while minimizing the cumulative constraint violations and maintaining the same computation complexity as in the unconstrained case. Our detailed contributions are as follows.
We develop a unified framework for CKB based on primal-dual optimization, which can guarantee both sublinear reward regret and sublinear total constraint violation under a class of general exploration strategies, including UCB, TS, and new effective ones (e.g.. random exploration) under the same complexity as the unconstrained case. We also show that by introducing slackness in the dual update, one can trade regret to achieve bounded or even zero constraint violation. This framework builds upon a novel sufficient condition, which not only facilitates the design of new CKB algorithms but provides a unified view in the performance analysis.
We demonstrate the superior performance of our proposed algorithms via numerical experi- ments based on both synthetic and real-world data. In addition, we discuss the benefits of our algorithms in terms of various practical considerations such as low complexity, scalability, robustness, and flexibility.
We also provide the first detailed comparison between two popular methods for analyzing constrained bandits in general. Specifically, the first one based on convex optimization tool as in [11, 12], which is also the inspiration for our paper. The other one is based on Lyapunov-driff argument as in [13-15]. We discuss the key difference in terms of regret and constraint violation analysis in these two methods and highlight the subtlety in applying standard queueing technique (i.c., Hajek lemma [16]) to bound the constraint violation in the second method. We believe this provides a clear picture the methodology, which is of independent interest to the communities.
1.1 Related Work
In the special cases of KB, including multi-armed bandits (MAB) and linear bandits (e.g., KB with a linear kernel), there is a large body of work on bandits with different types of constraints, including knapsack bandits [17-19], conservative bandits [20-22], bandits with fairness constraints [23, 24], bandits with hard safety constraints [25-27], and bandits with cumulative soft constraints [28, 13]. Among them, the bandit setting with cumulative soft constraints is the closest to ours. In particular, [13] considers linear bandits under UCB exploration and zero constraint violation is attained via the Lyapunov-drift method. However, it unclear how to generalize it to handle general exploration strategies such as TS; a further discussion in Section 4.
In the Bayesian-type KB, f is assumed to be a sample from a Gaussian process and the observation noise is Gaussian. In contrast, in our considered frequentist- type KB. f is a fixed function in an RKHS and the noise can be any sub- Gaussian. A better regret bound often be achieved in the easier Bayesian-type KB setting [6].

---

Broadly speaking, our work is also related to reinforcement learning (RL) with soft constraints, i.e., constrained MDPs. In particular, our analysis is inspired by those on constrained MDPs [11, 12] (which is another popular method to handle constrained bandits and MDPs via convex optimization tools), but has significant differences. First, in those works, the constraint violation is Õ(vT). In contrast, ours can attain bounded and even zero constraint violations by introducing the slackness in the dual update. Second, they only consider UCB-typs exploration, but algorithms can be equipped with various exploration strategies (including UCB), thanks to our general sufficient condition. Third, they focus on either tabular or linear function approximation settings. In contrast, both objective and constraint functions we consider can be nonlinear. There are also recent works on constrained MDPs that claim to achieve bounded or zero constraint violation [14, 15] based on the Lyapunov-drift method. However, as in the bandit case, it is unclear how to generalize it to handle general explorations beyond UCB. Finally, the theoretical understanding of unconstrained KB (a. Gaussian process bandit) is well-established, including regret upper bounds under UCB and TS [5, 29, 6] and lower bounds [30, 31]. We remark that our work is mainly theory-guider study. In more practical area of KB, i.e., Bayesian optimization (BO), there have been many BO algorithms developed for the constrained setting; see [32-34] and the references therein. Although these algorithms enjoy good performance in various practical settings, their theoretical performance guarantees are still unclear.
2 Problem Formulation and Preliminaries
We consider stochastic bandit optimization problem with soft constraints. In particular, in each round E {1.2.... T)+ a learning agent chooses an action X; E and receives a bandit reward feedback Fi- = fzz) + Mh. where de is a zero-mean noise. The learning agent also observes a bandit constraint feedback e = (x+4) + &c, where & a zero-mean noise. By soft constraints, the goal here is to maximize the cumulative reward while minimizing the cumulative total violation.
Learning Problem. Define cumulative regret and constraint violation follows:
T R(T) = == Σ f(x). V(T) = Σ 9
f(x and [++ == maxf:, The goal of the learning agent to achieve both sublinear regret and sublinear constraint violation. In fact, we will establish bounds on the following stronger version of regret. Specifically, let n be probability distribution the of actions X' (i.e., stochastic policy), and let E [f(r]]] == JEEx f(z)=(()) da and E, [g[x]]] == Seex ((x) (x)) dx. We compare our achieved reward with the following baseline optimization problem: max, {E, [f : Ex [g(x)] S 0} where both f and are known, and π is its optimal solution. Now, our stronger regret is defined as
where x² :=
(T) (=) TE. [s(z)) Σ (x.)) 1=1
Clearly, we have R(T)= S (7) Throughout the paper, we assume the following commonly used condition in constrained optimization literature; see also [13, 35, 11].
Assumption 1 (Slater's condition). There is constant 8 > such that there exists a probability distribution To that satisfies Exx [g(x)] < -ô. Without loss of generality, we assume < 1.
This is a quite mild assumption since it only requires that one can find a stochastic policy under which the expected cost is less than a strictly negative value. This is in sharp constraint to existing KB algorithms for hard constraints that typically require the existence of an initial safe action [9, 10].
In this paper, we consider the frequentist-type regularity assumption that is typically used in uncon- trained KB works (e.g., [5, 6)). Specifically, we assume that f is a fixed function in an RKHS with bounded norm. In particular, the RKHS for f is denoted by H4. which is completely determined by the corresponding kernel function à: : X' x X R. Any function h E Hr satisfies the reproducing property: hxx)) = (h, k(. x)) Ha. where (., HH is the inner product defined on Ha- Similarly, for the unknown constraint function g. we assume that g is a fixed function in the RKHS defined by
"This stronger regret also allows us to use convex optimization tool since E,, [f() = Seex (x))(()) de is convex function with respect which will be important for our analysis.
3

---

kernel function k. and the RKHS for is denoted by Hz. We assume that the following boundedness property holds throughout the paper.
Assumption 2 (Boundedness), We assume that ll S B and k(z, x) S 1 for any x E X and that the noise Tu is i..d
Similarty, we assume that l19ll I G and k( S for
any z E X and that the noise & ii.d.
Gaussian Process Surrogate Model. We use a Gaussian process (GP), denoted by GP k(: +)), as a prior for the unknown function f. and a Gaussian likelihood model for the noise variables Tr, which are drawn from (0, A) and are independent across t. Note that this GP surrogate model is used for algorithm design only; it does not change the fact that f is a fixed function in Hi and that the noise Ne can be sub-Gaus Gaussinn (i.e., an agnostic setting [6]). Let [t] == {1,2, . f). Conditioned on set of observations He = (Zs,)r)) E [t]] by the properties of GP [36], the posterior distribution for where
is
pe(x) == kx(=)) (Kg + AT)
(3)
(K₁ Re (( == k(x, x²) - ke (K) +
AI)- (z²),
(4)
=²"" K, = [k (e) and R2 is the (noisy) reward vector [11, rel"". In particular, we also define (x) == k, Let KA == [k( x') 22)]x, E for A S X. We define the maximum information gain as Ye X) == maxAcxx14/=1 _ In 14 + X KAl where 1, is the / x identity matrix. The maximum information gain plays a key role in the regret bounds of GP-based algorithms. While (k,k, X') depends on the kernel k and domain X. we simply use "/ whenever the context is clear. For instance, if X' is compact and convex with dimension d, then we have 7/- O(In 1) for squared exponential kemeel kige, 7t- = Oddnn t) for linear kernel [6] and 7t- = ( (where v is a hyperparameter) for Matérn kernel AMatém [37]. Similarly, the learning agent also uses a GP surrogate model for g, i.e., GP prior GP(O, k(::)) and a Gaussian noise (0, X). Conditioned on a set of observations H, = {xx, c,), s E [t]]. the posterior distribution for is GP(Pe()), ()), where ii and hy are computed in the same way.
in which kx(x)= :
3 A Unified Framework for Constrained Kernelized Bandits
In this section, leveraging primal-dual optimization, we develop unified framework for both algorithm design and performance analysis in constrained kernelized bandits. In particular, we first propose "master" algorithm called CKB (constrained KB), which can be equipped with very general exploration strategies. Then, we develop a novel sufficient condition, which not only provides a unified analysis of regret and constraint violation, but also facilitates the design of new exploration strategies (and hence new CKB algorithms) with rigorous performance guarantees.
Algorithm. We first explain our "master" algorithm CKB in Algorithm 1, which is based on primal- dual optimization. Let the Lagrangian of the baseline problem max, [[=[[( : E. [g(x)) I 0}
be [(T, 6) := Ex, [f()]] - oE,, [9(x)] and the associated dual problem is defined as D(Ø) == max, [(T,, Φ) with the optimal dual variable being o* := argmin..0 D( Note that since both f and g are unknown, the agent has to first generate estimates of them (i.c., fr and gt, respectively) based on exploration strategies As and Ag. which capture the tradeoff between exploration and exploitation (line 3). Then, both estimates will be truncated according to the range of and g. respectively (lines 4-5) (where Proj is the projection operator). The truncation is necessary for our analysis, but it does not impact the regret bound since it will not lead to loss of useful information. Then, lines 6-7 correspond to the primal optimization step that approximates D(oe) (i.e., approximate f. by L with ʃ and q replaced by ft and gt). The reason behind line 7 is that one of the optimal solutions for max, L(T,, (+)) is simply argmax, that minimizes D():) with respect to Φ by taking projected gradient step with 1/V being the step size. The parameter p is chosen to be larger than the optimal dual variable o², and hence the projected interval [0, p] includes the optimal dual variable. This can be achieved since the optimal dual variable is bounded under Slater's s condition, and in particular, we have Ø² < (E,, [f(x)] - Ero [f (x)))/ by [38, Theorem 8. 8.42]. Finally, line 8 is the posterior update via standard GP regression for both f and g as computed in (3) and (4) with of (z) = (z, x) and G. (z) = 2x)
deee (z)). Then, line 8 is the dual update
Remark (Computational complexity). CKB enjoys the same computational complexity as the standard unconstrained case (e.g., [5]) since the additional dual update is simple projection and

---

Algorithm CKB Algorithm
1: Parameters: V, P. 01 = 0. vo(x)) = [=(x)) = 0. (x) = 5o (2)) 1, Vx, exploration strategies
Ay and Ag
2: for batch I. 1 do
3: Based on posterior models, generate ft and 9s using A, and Ag. respectively
4: Truncate ft as (x) (r
5: Truncate as Dr (z) = Proj cro
6: Pseudo-acquisitiin function: &o, (x) ft(x)) (rār(a)
7: Choose primal action 2a - argmax 2q. (z); observe ra and ct
8: Update dual variable: Φx+1 = Projjo,ol 0 + (z+))
9: Posterior model: update (Ne, σr) and (1t, σx) via GP regression using new data (It, Tt, Ct)
end for
the primal optimization keeps the same flavol as the unconstrained case, i.e. without constructing a specific safe set in existing constrained KB algorithms designed for hard constraints.
We call CKB "master" algorithm acquisition functions) (i.e., A and Ag). Therefore, one fundamental question is: How to design efficient exploration strategies such that favorable performance can be guaranteed? In the following. we first use UCB-type exploration as an example to gain useful insights, which in turn will facilitate the development of a novel sufficient condition. This condition not only is satisfied under very general exploration strategies, but also enables a unified analytical framework for showing both sublinear regret and sublinear constraint violation in constrained kernelized bandits.
allows to employ different exploration strategies (or called
We first introduce standard UCB and TS explorations under GP as in [5].
Definition (GP-UCB and GP-TS Explorations). Suppose the posterior distribution for black-box function h in round is given by GP(P)-1()) and Be is an increasing sequence.
(i) The estimate of h in round under GP-UCB exploration is ha(-) Th--1(-)+ B:0r-1()), where (x) == k (x, x) for all x E X.
(ii) The estimate h in round under GP-TS exploration is h₂(+) (
3.1 Warm Up: CKB with GP-UCB Exploration
In this section, instantiate CKB with GP-UCB exploration called CKB-UCB, warm-up. In partieular, CKB-UCB, A, a GP-UCB exploration (see Definition 1) with a positive B, sequence
(i.e., optimistic with respect to reward), and Ag is GP-UCB exploration with negative Bg sequence (i.e., optimistic with respect to cost). This instantiation enjoys the following performance guarantee.
Theorem Suppose p 2 4B/8. = GVT/p, A a GP-UCB exploration with 3, = 3, B + R 2 +1+ ln(2/))), and Ag is GP-UCB exploration with 3r = - == -G
R 26/ + 1 (nnn/a/))) Under Slater's condition in Assumption I and regularity assumptions in Assumption 2, CKB-UCB achieves the following bounds simultaneously with probability at least
1 a for any E (0, 1):
RT) 0 (B (B/TTT + VT + In(2/a))
+ pGVT).
V(T)- -0 (u+ ( VT +21n(2/a)) + GVT).
where C' = max B, G) and frx := max TT).
Remark 2. The (reward) regret here the stronger version, i.e., (T).). Compared to the uncon- strained case, the regret bound has an additional term pGvT, which roughly captures the impact of the constraint. As in the unconstrained case, one can plug in different "rr and 5rr to see that both regret and constraint violation are sublinear for commonly used kernels. For example, for an SE kernel, both vrr and Fyr are the order of (In T)d+1, Finally, the standard "doubling trick" can be used to design an anytime algorithm (i.e., without the knowledge of with regret and constraint violation bounds of the same order.
5

---

Proof Sketch of Theorem 1. The key step is to establish a sublinear bound on the term R+(T)) + Then, with convex optimization tools, one can establish regret and constraint violation bound. To this end, By the dual update of CKB, we can first show that (T) + I g(re)
Et= g(2)) for any & E [0. p).
S 71 +
T2
+ V 0² + 27 TG' where
2
T := E [f(x)] - p. [g(x)])
(5)
T2 : Σ ((a))))((())))) + E((ox) - gx(r))).
(6)
Thus, the analysis for each choice of exploration strategy only differ in how to bound T1 + T2- Under GP-UCB exploration, the term Ti - 0 by the optimism while To can be upper bounded
by To S 2, Σi= d (x+) + 2 Σt= 0 (x+) = O(8r V + / i.e., standard
predication error bound. Building on the bound on Ti + T2, one can then show the required results. D
3.2 A Sufficient Condition for Provably Efficient Explorations
The above analysis reveals that the key step in obtaining sublinear performance guarantees of Algorithm 1 is to find a sublinear bound on Ti + Tz. which depends on the choice of exploration strategies. To go beyond GP-UCB exploration, we will establish sufficient condition on general exploration strategies (i.e., and Ag), which guarantees a sublinear bound on Ti + To and hence sublinear regret and sublinear constraint violation.
We first present the intuition hehind the key components of our sufficient condition. Inspired by [39], it suffices to focus on the following three nice events as to bound Ti + T2 in (5)-(6):
gest = -L0gst (I, t) (x, f); V(r, t)}, Dione = LD (x) O Lg. (z); Vx Egnti
Eonti n
Fggt in which
Ej"h (x, () = -1(x)) - 14- (4-1 s ffr 01 (x), Egat (a, 1) = 1s(x) - T ( (x) S 0..00-1 (0.00-(17) (z),
(1)
f. E (x) == (f((z) - - S 67.4 O/ 0-
( (I), Egg (z) == (9)(x) - t (x)) S cg. 9g
(2) 0z))
E E.. [f-()) 22 10o- (z)) Egn := E,. [9 - Fo 1 (x)) - B.. lō.-
To see the intuition. first suppose that events gast and Ex hold with high probability. Then, it is easy to see that the estimates are close to the true functions, and hence, one can derive a bound on To in (6). Now, suppose that events Eest and Eanti hold with some positive probability. Then, one can see that the estimates are optimistic with respect to the true functions when evaluated at the optimal points. This probabilistic optimism is the key to bounding Ti in (5). Note that GP-UCB exploration is optimistic with probability one by definition (see Definition I), and hence, Ti S 0 always holds.
To formally state our result, let us define the filtration Fg as all the history up to the end of round t. Let E. [ := E [-FF and P, (.) := P [-]FF-1). Then, we have the following sufficient condition. Assumption 3 (Sufficient Condition). The sufficient condition includes two parts:
(I) (Probability condition) P (Eest) 2 1 pı, Pr (Egone) 2 P2,t, and P. (Eanti) 2 pB > 0fr some time-dependent sequences (1) (1) (2)
G..1 G.r and (2)
(2) (Boundedness condition) (i) There exists positive probability p4 such that + 2
S 1/p1
(ps-
for all t; (ii) There exist some functions of T: (T) such that (1)
Cj + ftt I (T) and
(2)
(1) (2) < (T) for all t; (iii) Σt P2. S C" for some constant C².
9.1 9.
Remark 3. The above sufficient condition generalizes existing similar results [39-41] in several aspects. First, existing works mainly focus on the MAB or linear bandit settings. which are special cases of our KB setting (e.g., choosing a linear kernel leads to linear bandit). Second, while existing works only establish bounds on the expected regret, we aim to establish a high-probability bound. As a resull, we need the additional boundedness condition, which, however, is simply for technical reasons. Third, in contrast to existing works that consider the unconstrained case only, we consider the constrained case, which is more challenging. Specifically, requires that Eonts holds under policy nt (i.e., the expectation over x²) rather than under single optimal action x".
6

---

With the above sufficient condition, we have the following general performance bounds for CKB.
Theorem 2. Suppose p 2 4B/6 and V = GvT/p. == B
pG. Assume that CKB is equipped with exploration strategies that satisfy the sufficient condition in Assumption 3. Then, under Slater's 's condition in Assumption 1 and regularity assumptions in Assumption 2, CKB achieves the following bounds on regret and constraint violation with probability at least 1 a fi.for any a E (0,1): 1):
2 Cc((TTTT
+ (C, + pGvT ej (g) (Tg(T)
R4 R+(T)= =0
2T (T(1a(//))
P4
P4
p4
V(T) 0 (
c, Thr+
GVT cf (T) + pCg
v (2T
pp1
P1
PP1
In the following, we will show that Theorem 2 provides a unified view of the regret and constraint violation performance for various CKB algorithms, thanks to our sufficient condition. In particular, we first show that existing exploration strategies, such as GP-UCB and GP-TS, satisfy our sufficient condition, given by the following corollary.
Corollary 1. Let Br 3--R22(1 + + In(1/af)) and B, = B+BB++R BBBBB//------
ln(1/ag));
(i). GP-UCB with Br = Be and B. -B for A, and Ag, respectively, satisfies the sufficient condition.
(ii). GP-TS with 3, = 3g and B, -B, for A, and Ag. respectively, satisfies the sufficient condition when x² is a deterministic policy.
The sufficient condition also enables to design CKB algorithms with new exploration strategies. In the following, inspired by [40], we propose a new GP-based exploration strategy, which aims to strike balance between GP-UCB and GP-TS explorations.
Definition 2 (RandGP-UCB Exploration). Suppose that the posterior distribution for a black-box function h in round is given by GP((h-1(), kr ():)( Then, the estimate of h in round under
RandGP-U -UB exploration strategy is h₂(-) (-- Zz0r-1()), where Ze D for some
distribation D and (x) = (x,,) for all x E X.
In contrast to GP-UCB, RandGP-UCB replaces the deterministic confidence bound by randomized one. Compared to GP-TS, RandGP-UCB uses "coupled"" noise in the sense that all the actions share the same noise Zg rather than "decoupled" and correlated noise in GP-TS. This subtle difference will not only help to eliminate the additional factor, /In((x1) in GP-TS due to the use of union bound, but also allow to deal with general stochastic n²"
Corollary 2. Let Bi, Br be the same as in Corollary 1. RandGP-UCR with D = (O, B8 and D = -N, Bt) for Aÿ and Ag. respectively, satisfies the sufficient condition.
Thus, one can instantiate CKB with RandGP-UCA exploration to obtain new algorithm called CKB-Rand with performance guarantees given by Theorem 2. Note that RandGP-UCB with other distributions D can also satisfy the sufficient condition (as discussed in Appendix C).
4 Discussions
In this section, we discuss several possible questions one may have at this moment about our CKB algorithm. The first natural question to ask is whether one can further improve the constraint violation bound. It turns out that with minor modification of CKB algorithm, one can achieve bounded and even zero constraint violation by trading the regret slightly (but still the same order as before). The modification to introduce a slackness given by e the dual update in Algorithm 1, i.e., Φ++1 = Projjo.e) [db. + & (xx)) + E)] with S 5/2. Intuitively speaking, this can be viewed as if one is working on a new pessimistic constraint function. After obtaining the constraint violation under this new hypothetic constraint, one can subtract ET to find the true constraint violation under the true function g. The catch here is that one needs also change the baseline problem to the following one: max, [[x))
Ex, [g(x)] + e < 0} so that it matches the new pessimistic constraint function. Let nh be the optimal solution to this new problem and the obtained regret is only with respect to ग. rather than the original n². Thus, we need to further bound the following difference
TE,,- [f()] TE;; [z)] to obtain the true regret bound, which is given in Appendix E.
7

---

220
Seorget Cumpu Condroim Woaator
F00
CHBTTS
CHBB-T5 .... Sangera
CHIDOC CHIBTT
180
Cumuaate Regee:
180
Danunatee Regget
140
120
120
0.
2030
Daration
Iaraaion
Iaration
(a) Regret synthetic data
(h) Regret real-world data
(c) Constraint real-world data
Figure I: Experimental results on constrained kerneiized bandits with light-tailed data
Another question one may ask is why we are able to go beyond UCB-type exploration compared to existing works (e.g., [13-15]) that only establish performance guarantees under UCB. The answer is that they resort to another popular method for constrained optimization based on the so-called Lyapunov-drift argument. However, this method relies heavily on optimism under UCB to derive both regret and constraint violation bounds. Thus, it is difficult to generalize it for other exploration strategies even for simpler linear bandit problems. In contrast, our analysis relies only on the bound for Ti + T2, which allows us to consider more general exploration strategies. In Appendix F, we also discuss how to apply the Lyapunov-drift based method to analyze UCB exploration in our setting, through which we highlight more differences and some subtleties in Lyapunov-drit method.
5 Simulation Results
Although our work is mainly theoretical study, we conduct simulations to compare the performance of our algorithms (i.e., CKB-UCB, CKB-TS, and TS, and RandGP-UCB explorations, respectively) with existing safe KB algorithms based on both synthetic and real-world datasets. In particular, consider the two most recent safe KB algorithmss: StageOpt [28] (which has a superior performance compared to SafeOpt [27]) and SGP -CCB [3]. Our goal is to show that proposed CKB algorithms trade slight performance in constraint violation (i.e., soft constraint) for improvement the reward regret, computation complexity and flexible implementations, i.e., better complexity-regree-comm regret-constraint trade-off.
that is, CKB with GP-UCB, GP-
5.1 Synthetic Data and Light-Tailed Real-World Data
Synthetic Data. The domain X' generated by discretizing [0, uniformly into 100 points. The objective function f(-) Σe= | a,k((,, .I,) is generated by uniformly sampling E 1-11, and support points T; X' with p 100. With the same manner, we generate the constraint function g. The kernel is kse with parameter = 0.2. Other parameters include B, R and are set similar as in the unconstrained case (e.g.. [5]).
Light-Tailed Real-World Data. We use the light sensor data collected in the CMU Intelligent Workplace in Nov 2005, which available online as Matlab structure? and contains locations of 41 sensors, 601 train samples and 192 test samples. We use it in the context of finding the maximum average reading of the sensors. In particular, is set as empirical average of the samples, with B set as its maximum, and & is set as the empirical covariance of the normalized train samples. The constraint given by g()) = -f-)- + with h B/2. 2. We perform 50 trials (each with T = 10, 000) and plot the mean of the cumulative regret along with the error bars, as shown in Fig. 1.
Regret. Our three CKB algorithms achieve better (or similar) regret performance compared to the existing safe BO algorithms (see Figures ((a) and 1(b)). Among the three CKB algorithms, CKB-Rand appears have reasonably good performance all times.
Constraint violation. Since we have V(T) = under the algorithms, we study the total number of rounds where the constraint is violated, denoted by N. In the synthetic data setting, our proposed CKB algorithms have N < over 7 10, 000 rounds; in the real-world data setting, CKB-UCB enjoys N 0 and Ran-Rand has average N 38 over horizon T 1, 000. Furthermore, plot the stronger cumulative constraint violations given by Di [xx]]+
shown in Figure 1(c),
Phttp:// emu. http://p...../.t.ttt.a/a//aaaaaa

---

-16
160
Seorggt Clrru stun Condraan 50 aloe
1220
CHIB-T ... SSCP LAdB
CHI-ES
1000
240-75
Camuratin Regget
100
600
8
400
8
200
0000
3020
Ianaton
Baratoo
(a) Regret finance data (b) Avg. regret finance data
(c) Constraint finance data
Figure 2: Experimental results constrained kerneiized bandits under heavy-tailed finance data.
that all CKB algorithms achieve sublinear performance with respect to this stronger metric, i.e., violation cancellation across rounds is not allowed.
from which we
Practical considerations. Our proposed CKB algorithms have the same computational complexity as the unconstrained case. particular, they scale linearly with the number of actions in the discrete- domain case*. On the other hand, St ag scales quadratically due to the construction of the safe set, and SGP-UCT requires the additional random initialization stage, which leads to linear regret at the beginning of the learning process. Moreover, standard methods for improving the scalability of unconstrained KB can naturally applied to our CKB algorithms [42]. Finally, both St ategeOpt and SGP-UC3 require the knowledge of safe action (i.e., that satisfies the constraint) in advance, and moreover, StageOpt requires f to be Lipschitz and needs to estimate the Lipschitz constant, which impacts the robustness. In contrast, CKB algorithms for soft constraints only require mild Slater's condition as in Assumption 1, which does not require the existence of a safe action.
5.2 Heavy-Tailed Real-World Data
We further compare different constrained KB algorithms in a new real-world dataset, which demon- strates heavy-tailed noise. Note that Gau-saas noise required in all the existing theoretical works (including our work). We use this dataset to test the robustness of various constrained KB algorithms. The experimental results tend to show that our three CKB algorithms are more robust in terms of heavy-tailed noise, which is common in practical applications. The detail of this real-world dataset deferred to Appendix D.
Regret. We plot both cumulative regret and time-average regret in this setting (see Figures 2 (a) and (b)). We can observe that the presence of heavy-tailed noise, our three CKB algorithms have significant performance gain over existing safe KB algorithms.
Constraint violation. We focus the strong metric, i.e., the number of rounds where the constraint violated, denoted by N. We have that CXB-Rand enjoys an average = 21 and CKB-UCB has an average N = 47 within the horizon of T 10, 000. We also plot stronger cumulative constraint violations given by Σ [g(x))]+ as shown in Figure 2(c), from which we can that all CKB algorithms achieve sublinear performance even with respect to this stronger metric.
6 Conclusion
We presented general framework for constrained KB with soft constraints via primal-dual opti- mization. Armed with our developed sufficient condition, this framework not only allows us to design provably efficient (i.e., sublinear reward regret and sublinear total constraint violation) CKB algorithms with both UCB and TS explorations, but presents a unified method to design new effective ones. By introducing slackness, our algorithm can also attain a bounded or even zero constraint violation while still achieving sublinear regret. We further perform simulations on both synthetic data and real-world data that corroborate our theoretical results. Along the way, we also present the first detailed discussion on two existing methods for analyzing constrained bandits and MDPs by highlighting interesting insights. For future work, one interesting direction is build upon recent advances in unconstrained KB that attain improved regret (e.g., [43-46]) to study the corresponding constrained case in the hope to maintain the same improvement.
'For continuous domain, as in the unconstrained case, of random sampling (cheap) and the "I-BFGS-B"" optimization method.). In fact, attain the order of regret bound, solution to the acquisition maximization problem need not he exact. Instead, only needs to maximize the acquisition function within C/vL accuracy for constant C' each step.
resort to heuristic solvers (e.g.. combination

---

Acknowledgement
We would like thank the anonymous reviewers for their helpful comments. XZ partially supported by NSF grant CNS-2153220. BJ is partially supported by NSF grant CNS-211
References
[1] Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual- approach to personalized news article recommendation. Proceedings of the 19th international conference on World wide web, pages 661-670 2010.
[2] Brijen Thananjeyan, Kirthevasan Kandasamy, Ion Stoica, Michael I Jordan, Ken Goldberg. and Joseph E Gonzalez. Pac best arm identification under deadline. arXiv preprint 2Xxv::2006.03211, 2021.
[3] Mung Chiang, Prashanth Hande, and Tian Lan. Power control in wireless cellular networks. Now Publishers Inc, 2008.
[4] Charles A Micchelli, Yuesheng Xu, and Haizhang Zhang. Universal kernels. Journal of Machine Learning Research, 7(12), 2006.
[5] Sayak Ray Chowdhury and Aditya Gopalan, On kernelized multi-armed bandits. arXiv preprint 1eXiv:170.0004// 2017.
[6] Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian pro- cess optimization in the bandit setting: No regret and experimental design. arXiv preprint 1rXiv:0912.3995, 2009.
[7] Yanan Sui, Alkis Gotovos, Joel Burdick, and Andreas Krause. Safe exploration for optimization with gaussian processes. In International Conference on Machine Learning, pages 997-1005. PMLR, 2015.
[8] Felix Berkenkamp, Andreas Krause, and Angela P Schoellig. Bayesian optimization with safety constraints: safe and automatic parameter tuning robotics. arXiv preprint 16Xiv:1602.00 040000 2016.
[9] Yanan Sui, Joel Burdick, Yisong Yue, et al. Stagewise safe bayesian optimization with gaussian processes. In International Conference on Machine Learning, pages 4781-4789. PMLR, 2018.
[10] Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. Regret bound for safe gaussian process bandit optimization. In Learning for Dynamics and Control, pages 158-159, PMLR. 2020.
[11] Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-expllotttion in constrained mdps. arXiv preprint arXiv:2003.02//8) 2020.
[12] Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo Jovanovic. Provably efficient safe exploration via primal-dual policy optimization. International Conference on Artificial Intelligence and Statistics, pages 3304-3312. PMLR, 2021.
[13] Xin Liu, Bin Li, Pengyi Shi, and Lei Ying. An efficient pessimistic algorithm for stochastic linear bandits with general constraints. arXiv preprint arXi::2102.05295, 2021.
[14] Honghao Wei, Xin Liu, and Lei Ying. A provably-efficient model-free algorithm for constrained markov decision processes. arXiv preprint arXiv:2106.01577, 2021.
[15] Tao Liu, Ruida Zhou, Dileep Kalathil, PR Kumar, and Chao Tian. Learning policies with zero or bounded constraint violation for constrained mdps. arXiv preprint arXiv:2106.0266 2021.
[16] Bruce Hajek. Hitting-time and occupation-time bounds implied by drift analysis with applica- tions. Advances in Applied probability, pages 502-525, 1982.
[17] Shipra Agrawal and Nikhil Devanur. Linear contextual bandits with knapsacks. Advances in Neural Information Processing Systems, 29:3450-3458, 2016.
10

---

[18] Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knap- sacks. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 207-216. IEEE, 2013.
[19] Huasen Wu, Rayadurgam Srikant, Xin Liu, and Chong Jiang. Algorithms with logarithmic or sublinear regret for constrained contextual bandits. arXiv preprint (rXiv:1504.0693: 2015.
[20] Yifan Wu, Roshan Shariff, Tor Lattimore, and Csaba Szepesvári. Conservative bandits. In International Conference on Machine Learning, pages 1254-1262. PMLR, 2016.
[21] Abbas Kazerouni, Mohammad Ghavamzadeh, Yasin Abbasi-Yadkori, and Benjamin Van Roy. Conservative contextual linear bandits. arXiv preprint arXivv1611.06420 2016.
[22] Evrard Garcelon, Mohammad Ghavamzadeh, Alessandro Lazaric, and Matteo Pirotta. Improved algorithms for conservative exploration in bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 3962-3969, 2020.
[23] Yifang Chen, Alex Cuellar, Haipeng Luo, Jignesh Modi, Heramb Nemlekar, and Stefanos Nikolaidis. Fair contextual Uncertainty in Artificial Intelligence, pages 181-190. PMLR, 2020.
bandits: Theory and experiments. In Conference on
[24] Fengjiao Li, Jia Liu, and Bo Ji. Combinatorial sleeping bandits with faimesss constraints. IEEE Transactions on Network Science and Engineering, 7(3):1999-1813, 2019.
[25] Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. Linear stochastic bandits under safety constraints. arXiv preprint arXiv:1908.0558 2019.
[26] Aldo Pacchiano, Mohammad Ghavamzadeh, Peter Bartlett, and Heinrich Jiang. Stochastic bandits with linear constraints. In International Conference on Artificial Intelligence and Statistics, pages 1827-2835.. PMLR, 2021.
[27] Ahmadreza Moradipari, Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. Safe linear thompson sampling with side information. arXiv preprint arXiv: 2019.
[28] Xin Liu, Bin Li, Pengyi Shi, and Lei Ying. Pond: Pessimistic-optimsstic online dispatch. arXiv preprint arXiv:2010.0999 099999 2020.
[29] Michal Valko, Nathaniel Korda, Rémi Munos, Ilias Flaounas, and Nelo Cristianini. Finite-time analysis of kernelised contextual bandits. arXiv preprint arXiv:1309 6869, 2013.
[30] Jonathan Scarlett, Iliaa Bogunovic, and Volkan Cevher. Lower bounds on regret for noisy gaussian process bandit optimization. In Conference Learning Theory, pages 1723-1742. PMLR, 2017.
[31] Xu Cai and Jonathan Scarlett. On lower bounds for standard and robust gaussian process bandit optimization. International Conference on Machine Learning, pages 1216-1226. PMLR, 2021.
[32] David Eriksson and Matthias Poloezek. Scalable constrained bayesian optimization. Interna- tional Conference on Artificial Intelligence and Statistics, pages 730-738. PMLR, 2021.
[33] Michael A Gelbart, Jasper Snock, and Ryan Adams. Bayesian optimization with unknown constraints. arXiv preprint 143.v51403.6607 2014.
[34] José Miguel Hernández-LLohato. Michael A Gelbart, Ryan P Adams, Matthew W Hoffman, and Zoubin Ghahramani. A general framework for constrained bayesian optimization using information-based search. MIT Press, 2016.
[35] Hao Yu, Michael J Necly, and Xiaohan Wei. Online convex optimization with stochastic constraints. arXiv preprint arXiv:
[36] Carl Edward Rasmussen. Gaussian processes in machine learning. In Summer School on Machine Learning, pages 63-71. Springer, 2003.

---

[37] Sattar Vakili, Kia Khezeli, and Victor Picheny. On information gain and regret bounds in gaussian process bandits. International Conference on Artificial Intelligence and Statistics, pages 82-90. PMIR, 2021.
[38] Amir Beck. First-order methods in oplimization. SIAM, 2017.
[39] Branislav Kveton, Csaba Szepesvari, Mohammad Ghavamzadeh, and Craig Boutilier. Perturbed-
history exploration in stochastic linear bandits. arXiv preprint arXiv:1903.091:: 2019.
[40] Sharan Vaswani, Abbas Mehrabian, Audrey Durand, and Branislav Kveton. Old dog learns new tricks: Randomized ucb for bandit problems. arXiv preprint UrXiv:1910.0492. 2019.
[41] Baekjin Kim and Ambuj Tewari. Randomized exploration for stationary stochastic linear bandits. In Conference on Uncertainty in Artificial Intelligence, pages 71-80. PMLR, 2020.
[42] Daniele Calandriello, Luigi Carratino, Alessandro Lazaric. Michal Valko, and Lorenzo Rosasco. Gaussian process optimization with adaptive sketching: Scalable and no regret. Conference on Learning Theory, pages 533-557. PMLR, 2019.
[43] Zihan Li and Jonathan Scarlett. Gaussian process bandit optimization with few batches. In International Conference on Artificial Intelligence and Statistics, pages 92-107. PMLR, 2022.
[44] Sudeep Salgia, Sattar Vakili, and Qing Zhao. A domain-shrinking based bayesian optimization algorithm with order-optimal regret performance. Advances in Neural Information Processing Systems, 34:28836-28847, 2021.
[45] Romain Camilleri, Kevin Jamieson, and Julian Katz-Samuels. High-dimensional experimental design and kernel bandits. International Conference on Machine Learning, pages 1227-1237. PMLR, 2021.
[46] Sattar Vakili, Jonathan Scarlett, Da-shan Shiu, and Alberto Bernacchia. Improved con- vergence rates for sparse approximation methods in kernel-based learning. arXiv preprint urXiv:2202.04005. 2022.
[47] Sayak Ray Chowdhury and Aditya Gopalan. Bayesian optimization under heavy-tailed payoffs. In Advances in Neural Information Processing Systems, pages 13790-13801, 2019.
[48] Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances neural information processing systems, 24:2312-2320, 2011.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This is rather theoretical work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] In the appendix
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A] Experiments were rather run personal computer.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "qTCffVuY41o", "reviewer": "Reviewer_Q2Vc", "summary": "This paper provides a unified framework CKB for kernelized bandits optimization with unknown kernelized constraints based on primal-dual optimization. This framework can employ general exploration strategies (GP-UCB and GP-TS), and achieve sublinear cumulative regret with sublinear cumulative constraint violation. A new exploration strategy RandGP-UCB is also provided. Experiments on synthetic and real-world data are conducted. The paper is generally well-written with detailed proofs provided in the appendices. ", "questions": "- What are the definitions of $c_f(T)$ and $c_g(T)$ mentioned in Assumption 3?\n- Can CKB use the expected improvement or the max variance strategy $x_t=\\argmax_x \\sigma_{t-1}(x)$? What are the corresponding $h_t$ ?\n- What kind of strategies are likely to satisfy the sufficient condition? Can the sufficient condition prevent CKB from employing some exploration strategies?", "limitations": "Comparisons between convex optimization methods and Lyapunov-drift methods have been discussed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The CKB framework can employ multiple exploration strategies.\n- Under the sufficient condition, CKB can attain sublinear cumulative regret and sublinear cumulative constraint violations.\n\nWeaknesses:\n- It is frequently mentioned that CKB can use general exploration strategies. Based on my understanding, this algorithm requires a function estimator $f_t$  rather than an acquisition function. Some exploration strategies like maximum variance do not involve an estimator of the unknown function.\n\nComments:\n- For line 154, a better upper bound on maximum information gain for the Matern kernel has been provided in \"On information gain and regret bounds in Gaussian process bandits\".", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "puTlJ9-nZkw", "reviewer": "Reviewer_HvKs", "summary": "The paper considers the problem of black box optimization under soft constraints where the objective of the learner is to maximize a function f subject to $g \\leq 0$, where both $f$ and $g$ are elements in (possibly different) RKHS. The objective is to attain a sublinear regret and a sublinear violation of the constraint. The authors propose a general algorithmic framework for such scenarios that works for a class of exploration strategies satisfying certain conditions. It is shown that GP-UCB and GP-TS satisfy these conditions and the regret and violation bounds are derived for these two policies. Supporting numerical evidence has also been provided. ", "questions": "1. Line 154-155: Better bounds on $\\gamma_t$ are known in the literature [1]. Please update the citations accordingly.\n\n2. Why does the definition of $\\mathcal{V}(T)$ have a max operation on the entire sum instead of the summands? From what I understand, each summand should have a max operation on it, just like in the case of so called \"stronger cumulative constraint violations\" considered in the simulations. In simple words, the \"soft\" constraint implies that one is allowed to violate the constraint every now and then as long as it is not too often. If the max operation is taken as a whole, then being within the constraints \"compensates\" for the violations, which should not be the case, or at least is not what is being described in the problem setting. Such a setting is more akin to a reward cost system, where the company is using a resources and the overall cost should not exceed a limit in which using less resources at one time instant allows one to use more in the next time instant. Thus, I am a little concerned by the definition of $\\mathcal{V}(T)$ and hence whether the algorithm does solve the \"soft\" constraint problem. It is promising to see good results in the simulations. However, given the authors present this is a theory-guided study, it is important to have a complete theoretical understanding of the situation.\n\n3. It is claimed that the regret is sublinear and so is violation of constraint. However, this is only true for particular values of $\\gamma_T$, or equivalently a subset of kernels. This is a drawback associated with UCB type approaches. There are non-adaptive approaches established in the literature that achieve the optimal regret guarantees for all kernels (See [2], [3]). It would make the results stronger if the authors could use those techniques to strengthen the results. Since one just needs to check if the sufficient conditions mentioned in Assumption 3 are being met, I believe it would actually be rather straightforward to incorporate the changes especially given the authors have already developed a unified framework.\n\n4. In theorem 1, the constraint violation has a term of $\\hat{\\gamma_T} = \\max\\{ \\gamma_T, \\tilde{\\gamma}_T\\}$. It implies that if one of the kernel is very smooth and the other is quite non-smooth, the constraint violation is always governed by the non-smooth one. Can the authors please explain why that is the case? For example, if the kernel corresponding to $g$ is non-smooth, I can see why one might end up violating the constraint often and hence incur a large constraint violation. However, if the kernel is the corresponding to $g$ is the smoother one, then I would expect the constraint violation to be small and not governed the kernel corresponding to $f$.\n\n\n[1]  Sattar Vakili, Kia Khezeli, Victor Picheny, \"On Information Gain and Regret Bounds in Gaussian Process Bandits\", Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:82-90, 2021\n\n[2] Zihan Li, Jonathan Scarlett, \"Gaussian Process Bandit Optimization with Few Batches\", Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:92-107, 2022.\n\n[3] Sudeep Salgia, Sattar Vakili, Qing Zhao, \"A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance\", Advances in Neural Information Processing Systems, 2021", "limitations": "N/A.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nI think the analysis techniques used in the work are interesting. Even though the ideas are borrowed from existing work, the work draws interesting parallels and extends the analysis from GP-UCB to GP-TS. I liked the discussion on convex-opt and Lyupanov-opt techniques in the Appendix.\n\nWeaknesses: \n\nPlease see the next section for questions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "UcebwpvHCf", "reviewer": "Reviewer_JSLq", "summary": "This paper examines kernelized online optimization problems and propose to tackle the problem by some generalization of primal-dual techniques. The techniques developed in this paper looks plausible but I am not an expert in this area so feel a bit unsure about the depth of the techniques and wish the authors can elaborate a bit more on some conceptual questions. \n\n", "questions": "Please see above. ", "limitations": "Same as above. ", "rating": 6, "confidence": 2, "soundness": 1, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper aims to optimize a function in RKHS, subject to a certain soft-constraint (it can be violated in a sublinear manner). Then it argues that by carefully combining Gaussian processes, UBC, and primal-dual algorithms, a non-trivial algorithm can be designed. I feel the way different techniques are integrated is quite reasonable, and this overall sounds like a nice result. Nevertheless I have a few questions: \n\n1. Is there a nice way to interpret the soft constraint formulation. The formulation smells like a \"made-up\" constraint because of certain limitation of the new techniques developed. \n2. How does this work compare to Srinivas, Krause, Kakade, and Seeger 12? Is that the only difference is that a soft constraint is added (and maybe that's the reason some primal dual is needed)? Also, some submodular techniques seemed to be needed to deal with those \"information gain\" things. It appears that this kind of techniques are not needed in this paper.  Did the author manage to circumvent the submodular property in a different way, or indirectly used this property somewhere. \n3. (likely to be my ignorant): does sublinear regret implies that there exists an offline algorithm that can optimize any function in strongly polynomial time (with error parameter $\\epsilon$)? That sounds too good to be true (or maybe standard grid-search also can achieve so)?\n4. Related to 2 and 3: does the algorithm have a multi-dimensional generalization? I imagine the result would be exponential in the dimension like SKKS12. So my question at the end is that if exponential regret is allowed, how is this better than standard grid search? Comments on both the practical and theoretical aspects would be helpful .  \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OYBKIna1Rqj", "reviewer": "Reviewer_x6gL", "summary": "The authors study a stochastic bandit problem when the reward function and constraint function lie in a reproducing kernel Hilbert space (RKHS) with a bounded norm. The paper considers soft constraints that may be violated in any round as long as the cumulative violations are small. They solve the restricted maximization problem using  primal-dual optimization and propose a flexible algorithm for various types of exploration including UCB and TS.  They  also provide a unified analysis with sublinear regret and sublinear constraint violation.\n\nTheir main contribution seems to suggest a unified solution for constrained kernelized bandits.  The paper succeds in providing a unified regret analysis that accommodates various exploration tools such as UCB and TS by circumventing previous approaches relying on Lyapunov-drift arguement. \n", "questions": "none", "limitations": "yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\nThe authors develop a unified framework for kernel bandits with soft constraints using primal-dual optimization and show sublinear reward regret and sublinear total constraint violation when UCB or TS type of exploration is utilized.\n\nTo construct a unified algorithm and regret analysis, they identify a novel sufficient condition.\n\nThe paper is well written and clear.    ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept