Active Learning with Safety Constraints
Authors: Romain Camilleri
Andrew Wagenmaker
Jamie Heather Morgenstern
Lalit K Jain
Kevin Jamieson
Venue: NeurIPS 2022 Accept (2022)
Keywords: bandits
linear bandits
active classification
active learning

Abstract: Active learning methods have shown great promise in reducing the number of samples necessary for learning. As automated learning systems are adopted into real-time, real-world decision-making pipelines, it is increasingly important that such algorithms are designed with safety in mind. In this work we investigate the complexity of learning the best safe decision in interactive environments. We reduce this problem to a safe linear bandits problem, where our goal is to find the best arm satisfying certain (unknown) safety constraints. We propose an adaptive experimental design-based algorithm, which we show efficiently trades off between the difficulty of showing an arm is unsafe vs suboptimal. To our knowledge, our results are the first on best-arm identification in linear bandits with safety constraints. In  practice, we demonstrate that this approach performs well on synthetic and real world datasets.

Active Learning with Safety Constraints
Romain Camilleri, Andrew Wagenmaker, Jamie Morgenstern, Lalit Jain, Kevin Jamieson University of Washington, Seattle, WA
(tamilr,ajwagen jami jamieson Momieson)@cs, washington. edu, lalitj @uw @dw.edu
Abstract
Active learning methods have shown great promise in reducing the number of samples necessary for learning. As automated learning systems are adopted into real-time, real-world decision-make makiing pipelines, it increasingly important that such algorithms are designed with safery in mind. In this work we investigate the complexity learning the best safe decision in interactive environments. We reduce this problem to constrained linear bandits problem, where our goal is to find the best arm satisfying certain (unknown) safety constraints. We propose an adaptive experimental design-based algorithm, which we show efficiently trades off between the difficulty of showing an arm is unsafe vs suboptimal. To our knowledge, results are the first on best-arm identification in linear bandits with safety constraints. In practice, we demonstrate that this approach performs well on synthetic and real world datasets.
Introduction
In many problems online decision-making, the goal the learner is to take measurements such way as to learn a near-optimal policy. Oftentimes, though the space of policies may be large, the set of feasible, or safe policies could be much smaller, effectively constraining the search space of the learner. Furthermore, these constraints may themselves depend on unknown problem parameters.
For example, consider the problem of bidding sequentially in series of auctions where the bidder bids a price Wt, the value of winning an item f is denoted Vt, and the utility of winning that item and paying price Pt is 04- pt. The goal of the bidder is to choose an optimal strategy amongst bidding strategies E S. R - IR. When a bidder is deciding how to choose these strategies, they often face constraints: they may have a budget B they must abide to; they may wish have those auctions they win be well-distributed across time (e.g. in the case of advertising campaigns); they may want to ensure the set of items they win satisfy some other property (e.g. for advertisements, they might want to ensure they are not over-targeting any demographic group).
As another example, inventory management systems may face similar issues of deciding amongst strategies, where there is some objective function (such as revenue) and variety of constraints at play in this choice (e.g. capacity of set of warchouses, employee scheduling constraints, or limits on the duration of delivery lag). They also operate in markets with changing demand and other uncertainties, leading to uncertainty about which strategies are feasible or safe (satisfy constraints) and uncertainty about the revenue they generate.
Both of these scenarios motivate understanding the sample complexity of selecting an action or strategy which approximately maximizes an objective while also satisfying some constraints, where samples are needed to both learn the objective value of actions and whether not they satisfy said constraints. In this work, we study the active sample complexity of this task-if the learner can choose which examples compared to the number needed in a passive setting? We pose this as best-arm identification problem in the setting of linear bandits with safety constraints, where the goal is to estimate the best arm, subject to it meeting certain (initially unknown) safety constraints. We propose experiment design-based algorithm which efficiently learns the best safe decision, and show the efficacy of this
observe and have labeled, how many fewer samples might they need
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

approach in practice through several experimental examples. To the best of our knowledge, ours is the first approach to handle best-arm identification linear bandits with safety constraints.
1.1 Linear Bandits with Safety Constraints
Let 8 (0, 1) be confidence parameter, X, 2 Rd be finite known sets of vectors, and assume there exists 0- RR Me E iR unknown to the learner. For simplicity, we assume that ||0. ll2 S 1, and ||ا,,ع|| S 1 E [ra] and || S 1, ||= < 1, Va E X, E Z. The learner plays according to the following protocol: at each time step / the learner chooses some action E X, observes (re. [st,)==1 where T2 = 0,1 Ie + wy and St,; = __, 24 + w., for all i E [m], where wft w are ii.d. mean zero I-subGaussian noise. The choice of action 2t is measurable with respect to the history F; = Tz {8 ) ) The learner stops at a stopping time which is measurable with respect to the filtration generated by FisT, and returns 2, E Z. In general, when referring to any expectation E or probability P. the underlying measure will be with respect to the actions, observed rewards, and internal randomness of the algorithm.
We are interested in the safe transductive best-arm identification problem (STBAT), where the goal of the learner is to identify
2x arg max ZE2
6, s.t. 2 Pa,s E [m]
for some (known) threshold y. In words, goal is to identify the best safe arm in 2, 2., where say an arm & is safe it satisfies every linear constraint: z H4.i S 7, Vi E [m]] We are interested in obtaining learners that take the fewest number of samples possible to accomplish this. In practice, will consider a slightly easier objective. Fix some tolerance é > 0 and let
Z, = {= 2
=T 0. 24.240 2. e, 2 U4, S Vi [m]].
Then our goal is obtain an (c, P)-C learner defined as follows:
Definition ((e, 6PC Learner). A learner is (e, 6PCC for any instance it returns ū, such that P(Z, E 2.] 2 1 8.
We define the optimality gap for any 2 Z as A(2) = 0_ (2. - 2), and the safery gap for constraint i as (=)
11, 2. Note that either A(2) or ( can be negative. If A(=) < O, it
follows that z has larger value-= 0, 0.-than the best safe z., which implies it must be unsafe. If A safe (2) < O for some i, then arm 2 is unsafe. We also define the e-safe optimality gap as:
(=) = max(=' - =)T S.L. min A A 2
(I)
A (1) is then the gap in value between
and the best arm with minimum safety gap at least
Mathematical Notation. Let || = T Ar and p(x) = maxfæ; 0}. Ö(-) hides factors that are logarithmic in the arguments. S denotes inequality up constants. We denote the simplex as 4x == (A
T |X 20
Ex
Safe Best-Arm Identification in Linear Bandits
2.1
Algorithm Definition
The main challenge in algorithm design for the safe best-arm identification problem is ensuring that we are efficiently balaneing our exploration between refining our estimates of both the safety gaps, as well as the optimality gaps. Our approach is given in Algorithm [
BESIDE.
BESIDE relies on round-based adaptive experimental design approach. In each round BESIDE consists of three phases. In the first phase, it solves an experimental design over A E Ax. with the goal of refining our estimates of the safety gaps. It then takes тę samples from Aç. In the second phase these samples are used to estimate the safety constraints, f. and the safety gaps of each safe (z). Finally, in Phase 3, an additional experimental design is solved which now aims to refine our estimates of the optimality gaps, and the estimates of the optimality gaps & for each 2 are then computed. We encapsulate Phase 3 in subroutine, RAGE" which we outline in the following. We now carefully describe each phase-wa we begin with Phase 2 to explain how our estimator works.
arm, A i.f.

---

Algorithm Best Safe Arm Identification (BESIDE)
I: input: tolerance e, confidence 8
2: 4r <- [log( 20)
A (=) 0, (2) < 0 for all E 2
3: for { 1, 1,2.,.....4 do
4: 6f <- 20-2 2-
// Phase 1: Solve design to reduce uncertainty in safety constraints
5: Define
ce(2) y
min - + maxp maxp -i6-1 sale (2)) + p(A
6: Let be the minimal value of E R_ which is greater than 4 log 4m 2|1 such that the objective to the following no greater than Et/ 100, and de the corresponding optimal distribution
inf max XEΛx ZE
(ce(z) + + + V= 1| (A)) -log(
4ml
100
7: Sample ~ λy, collect тı observations {(Te, It, St,1,..,, ,
// Phase Estimate safety constraints
8:
(D'') li=l RIPS((()), st,1) 2, 2mm
9: Tue (2) 7 - TT + ||elll Te log 4m|21e"
// Phase 3: Refine estimates of optimality gaps
10: (=)))) + RAGE" 2, Et, Tez (m) + max, p(-Appp0p safe (z) =))))))))
- ie
Perform final round exploration to ensure we find e-good arm 11: Vend f (= E ce(z) I safe (z)
12: A (x)nd))) (z)) + RAGE (Vend: Vend, C, (Aeato + max, p(- p safe (EE2)
return arg min Lend
Phase 2: In Phase 2 the algorithm would like to use the samples drawn from the design X to estimate the constraints for each 2 E Z: z Hr., for each E [m]. Past works using adaptive experimental design in the linear bandits literature have utilized the least-squares estimator along with complicated rounding schemes [133] which may require an additional poly(d) samples each round (this poly(d) factor could be prohibitively large-for example, in active classification problems, d the total number data points). We instead utilize the RIPS estimator of [ which gives us a guarantee of the form: with probability greater than 5, for all Z,
TTtt pa,:)l ||=|| VT Te log( 4m 2
We describe the RIPS estimator in more detail in Appendix B
Phase 1: By our definition of the experimental design on Line 6 our safety gap estimation error bound in 2 satisfies, for each 2 E Z:
1 "T - p, S ||=1|A(0011
log( 4m 2/e2
S cz(2) +
(3)
Note that design chooses allocation that minimizes the variance in estimate of each safety constraint (up to some tolerance), which scales as || This can be thought of as a form of X'V-design-a design of the form infxe^x maxyey reduce our uncertainty estimating the safety value for each z E 2. We refer to such a design objective henceforth as X' Assume that at round f - 1, we can guarantee
-where here y +- Z is chosen
cx(2) = -in A j. (2)1 + max p( ----------- A safe (z)) ) + (z)) +
(
safe
S min A (=) + max p( AJ safe (=)) +
(=)) + +
(4)
Then combining the above inequalities, we see that the experiment design on Line alaim minimize the uncertainty in estimate of 2 Me,i up to a tolerance that scales as the maximum of the four

---

terms in (4) It follows that if any of these terms is large, we will only allocate small number of samples to refining our estimate of arm 2. Each one of these terms can be intuitively motivated by thinking through what is needed to prove that an arm + 2.
z has small safety gap min, to (z)|: | if this term is large, it implies that minimum safety gap for is large. To show an is safe or unsafe, it suffices to learn each safety gap up tolerance a constant factor from its vagua-regulariziin by this term ensures we do just that.
z fails some safety constraint max, p( ante sate (z)): if this term is large, it implics that arm is very unsafe for some constraint. In this case, not need to reduce our uncertainty in the safety gap any more.
easily determine is unsafe, and therefore do
is sub- sub-optimal p( A ( (=)): if this term is large, it implies that is very suboptimal compared to some safe arm with safety gap at least 6g-1- In this case, we do not need to estimate z's safety gap, as we will have already eliminated it.
remains to ensure that 4 holds. As we show in Appendix Dtthoogh careful inductive argument, combining ( with our guarantee on the estimates the optimality gaps obtained Phase 3, A (2). is sufficient guarantee (4) holds. In particular, if any gap is greater than it is estimated up to constant factor, and otherwise it is estimated up to (Ee). This ensures that our gaps are estimated at the correct rate while guaranteeing we do not collect too many samples in each round.
Phase 3: In this phase we estimate the suboptimality gaps using RAGE RAGE' is inspired by
the RAGE algorithm of [13] for best-arm identification. In the interest of space, defer the full definition of RAGE to Appendix Erpeenix/CJbuu provide some intuition here. After Phase 2, by 3 the set of
arms }/+ :- (= E 2 : c, (=) S 7 (=)(),) Vi E [m]] for 8 < t are precisely the ones that we can certify are safe (note that we do not need to ever explicitly construct such a set-we can instead maintain an implicit definition through the constraints). RAGE uses an adaptive experimental design procedure to sample such way as to optimally estimate the gaps (= 77) 0,, Vz E 2 and some ū E Ve up to some (sufficient) tolerance. In particular, it also solves an deedssig,, but now on the set Y (z y E Z}. Thus, rather than minimizing ||=||2(a)- we minimize I|= T1 This design reduces uncertainty on the differences between arms, which allows us to refine our estimates of their optimality gaps. Henceforth
refer such design Xa We describe the importance of the choice of design in more detail in Section 2.4 Ultimately, if an arm 2 has value within a factor of e of the best safe arm in V/, and if we have not yet shown its optimality gap up to constant factor of eg. If we were maintaining arm sets explicitly (similar to the original RAGE algorithm of [3] we would eliminate arms this point.
is unsafe, then will estimate
Remark 1 (Computational Complexity). The main computational challenge in BESIDE and RAGE is the calculation of the experimental designs (i.e. Linelaand the corresponding design in RAGE" ). In general, the presence of the square rool implies that the resulting oplimization problem may not be convex in X. To handle this issue we note that 2 2 = mina70 OCE thus we can replace the ex-
isting design with infxe/x maxzez mina>0
Too (ce(=) (a)
log(
4m 12162 ) 5
By appropriately discretizing the space we search over for T and a we can then apply the Frank- Frank-Wolfe algorithm to minimize over x. While computationally efficient in theory, this procedure is quite complicated and impractical for large problems. In the experiments section we provide a practical heuristic that is motivated by the above algorithm and is computationally efficient for larger problems.
2.2 Main Result
BESIDE achieves the following complexity.
Theorem 1. BESIDE is (e, 8)-PAC In other words, with probability at least 1 8, BESIDE returns an arm 2 E such that
2 0,
2TO0
min A (2) i [m]
and terminates after collecting at most
| 2 log( ml22
-us inf max Eee X #E2 (min, / (=)l + max, p( p(-A (=)r)(=))) + (=))(=)) +ā)²
(safety)

---

|| 2. 2.llA(A)= log( (24
+ sup inf max E2e dEAx =E2
+ Co
(optimality)
(maxy p( p(- (z)) + p (=) + +2)
samples for some C poly log( and Co poly log( : [2]) log
The complexity bound given in Theorem may, at first glance, appear rather opaque, yet it in fact yields a very intuitive interpretation. The first term in the complexity, the safety term, is the complexity needed to show each arm is safe or unsafe, if they have not otherwise been eliminated. As described the previous section, if (( (z) large, this implies we have found an arm better than so learning its safety value is irrelevant.
The second term in the complexity, the optimality term, corresponds to the difficulty of showing an arm is worse than the best arm we can guarantee is safe. Note that we can only guarantee an arm is suboptimal if
find safe arm with higher value. Recall the definition of A (=) given in [ and the best arm with safety gap least can show additional arms are safe, which increases A (z). While this makes it easier to show 2 is suboptimal, it comes at a cost- extra samples necessary to decrease safety tolerance, given by the first term in the complexity. BESIDE trades off between optimizing for each of these terms goradualll decreasing its tolerance on both the safety and optimality terms to more easily eliminate suboptimal arms, while not allocating too many samples guarantee safety.
Intuitively, A (=) denotes the gap in value between
E. As we make é smaller,
To help illustrate this complexity, we consider simple example with orthogonal arms, i.e. multi-armed bandit example.
Example (BESIDE on Multi-Armed Bandits), In the multi-armed bandit setting, we have X = 2 fei...., Cd). Let
1, d 3, and consider the settings of 0, and p.a given in Figure] [ Here we see that arm E₁ is safe and has value much higher than any other arm, so 2. = e1, and can be shown to be safe relatively easily; arm e2 has near-optimal value but is very unsafe; and arm eg is unsafe with very small safety gap, but has the smallest value.
0.50
0.50
Safety Value
Value
0.25
0.00
0.00
[0.]1
0-/2
[0-]a
[p=]]
[4,12
Figure 1:
Bandit Instance
Showing 22 is Suboptimal. As e2 has near-optimal value, A(e2) is very small and it is very difficuls to show e2 is suboptimal. However, -Deate = O(1), so it is very easy to show is unsafe. It follows that p( (sate( for = BESIDE does not attempt to show is suboptinal, but instead shows it is unsafe, and therefore does not pay for the small optimality gap of ((e2) in the complexity.
(11) so both denominators in our complexity will always be O(1)
Showing is Suboptimal. Recall the definition of (²(2) max ( 0 (2' 2). In this case, for c (1), will have (eate(e1) 2 which implies that A (es) 0, (E1 (z) = ~(ea)= or suboptimal (which is very easy). Observing the sample complexity of Theorem 7 we see that the denominator of both terms will always be O(1) for ea since A (e2)) = (11-BBSIDD never pays for the small safety gap of e3, it instead takes advantage of the fact that ez can easily be shown to be suboptimal, and uses this to eliminate it.
To show ea is suboptimal, we could either show it is unsafe (which is very difficult)
In both of these cases see that BESIDE does the "right" thing, always using the easier of the two criteria either showing an arm is unsafe or suboptimal- show that + 2.. Combining the above observations, for e zs min ((ez), Asate(ez) Deate (e1)), it follows that on this example the total
5

---

sample complexity of BESIDE given by Theorem scales as:
1 δ ((Daidlen)) + (e2e + (leg)2)
log 1 5)
where the Saae (c1) arises because must also show 61 is safe.
2.3 Optimality of BESIDE
Optimality in Best-Arm Identification. Consider applying BESIDE to a problem instance where m I, 14,1 O, and 7 In this case, every arm is safe, and the safety constraints essentially "acuous-evee arm can easily be shown safe. We can therefore think of this as simply an instance of the best-arm identification problem. In this setting, we obtain the following corollary.
Corollary 1. Consider ranning BESIDE on problem instance where m 1, 14,1 and y #s. 0__ (z, 2). Then with probability at least 1 6, BESIDE returns 2, and has
and set c 1 + sample complexity bounded by:
ō inf max ΛE 2E
||2 - 2. (111)(())
A(A)
log
[Z] 5
+ inf max [|=1 log
2 6
A(2)²
AEAx ZEZ
Up lower-order terms, this exactly matches the lower bound on best-arm identification given in 13. Thus, in settings where the safety constraint is vacuous, BESIDE hits the optimal rate.
Worst-Case Performance BESIDE. We next consider the worst-case performance of BESIDE in settings when X' = Z. We have the following result.
Corollary 2. Assume that X = Z. Then for any 0_ and (1=,,) ym the sample complexity of BESIDE necessary return e-good and e-safe arm is bounded as O (4- (log(m]
log }))
Theorem 2 of 38 shows a worst-case lower bound of Q(d2 (c2) on the sample complexity of identifying e-optimal arm the standard linear bandit setting. Safe best-arm identification problems in which the safety constraint is vacuous are at least as hard as the standard best-arm identification problem, since minimum we need find the best arm out of every safe arm. Thus, (dff/e2) ) is also worst-case lower bound for the safe best-arm identification problem. The hard instance of (38) has | = (22)) so it follows that on this instance, BESIDE achieves a complexity of ( (d + log 1 )), and therefore BESIDE has optimal dimensionality dependence. In addition, this also implies that safe best-arm identification, in the worst-case, is no harder than standard best-arm identification problem-it is no harder to find the best safe arm, regardless of the number of safety constraints, than to find the best arm, ignoring safety constraints.
2.4 The Role of Experiment Design
We can think of the safe best-arm identification problem, in some sense, as an interpolation of the standard best-arm identification problem, as well as the level-set estimation problem, where the goal is to identify z E satisfying μ.. S 7 [29]. In the former problem, [I3] shows that the instance-optimal rate can be attained by running round-based algorithm and at every round solving an instance the X'aai experiment design, as defined Section 2.T. the latter problem, [29] also show that a round-based algorithm can hit the instance-optimal rate, but instead solving the Xaasate problem at each round. It is natural to ask whether either of these strategies could be applied to the safe best-arm identification problem directly, or if it is necessary alternate between them. The following results show that, on their own, each of these designs is unable to hit the optimal rate.
Fix some small enough E > 0. Then there exist instances of the safe best-arm identification problem, I, = (0,,,', X* 22'), i 1,2, with d = |x*| | 2, = 1, such that:
Proposition 2.
On Il, any (c,8)-PAC algorithm which plays only allocations minimizing XYaæ must have Eira] 2 Ω ( loo })) while BESIDE identifies an c-optimal arm after Ō log 1 1/5) samples. On I2, any (e, P)C algorithm which plays only allocations minimizing XYisato must have B[78] 2 Ω ( log )), while BESIDE identifies an e-optimal arm after O log 1/8) samples.

---

Proposition ieriitooniimoe iimplies that, to solve the safe best-arm identification problem optimally, more care must be taken exploring than either standard experiment design induces we must trade off between X'at and safe as BESIDE does. We remark briefly on the instance I On this instance we have X [61,62) and 2- {21, 22] with 21 = [1/4, 1/2] and 22 [3/4, 1/2 + ox.. We set 01 = [1, 0), n1 = [0, 1], and 7 = 1/2 + a/2. Here =2 is unsafe while 21 is safe, so it follows that E, 21. As 22 0: 21 0,. to show 22 * 2z, we must show it is unsafe. However, if we solve the design VY we see that it places nearly all of the mass on the first coordinate. While this would be optimal both 21 and were safe and we simply wished to determine which has a higher value, to show 22 is unsafe, the optimal strategy places (roughly) the same mass on each coordinate, since each coordinate could contribute to the safety value. This is precisely the allocation BESIDE will play, so it is able to show that 22 unsafe much more efficiently than a naive Vis approach.
3 Experiments for Safe Best Arm Identification in Linear Bandits
We next present experimental results BESIDE demonstrate the advantage of experimental combining XQ and X'stt designs. As there are no existing algorithms that consider safe best-arm identification, as benchmark we consider the naive adaptive approach BASELINE that first solves the problem of finding the safe arms up to a desired tolerance, and then solves the problem of finding the best (safe) arm among the arms that were found to be safe. We first describe instances on which we test BESIDE. Our experimental details and precise implementation of BESIDE using elimination are described in Section
Multi-Armed Bandit. We consider a best-arm identification problem in which every arm is safe, but the arm with highest value is very difficult to identify as safe, while the second-best arm can easily be shown safe. We vary the total number of arms and run BESIDE and BASELINE with 0.5 and 8 = 0.1. From Figure 2 about two times for 100 arms) than the sample complexity of its baseline.
we observe that the sample complexity of BESIDE is smaller (up to
Linear Response Model. Random Instance: We also consider the more general setup where X, Z C Rd. 0 Rd and μ Rd are randomly generated from independent Gaussian random variables with mean 0 and variance 1. We set X = 50 and vary the size of Z|. In Figure we see again that BESIDE significantly outperforms the bascline.
Hard Instance: We last consider the instance of Proposition and benchmark against the strategy playing only allocations minimizing Xaait. In Figure 4 we see again that BESIDE significantly outperforms this baseline, corroborating the theoretical result of Proposition
sample complexity
MAB hard instance
complexity
safe linear bandits
sample complexity
LB hard Instance
Baseline BESIDE
Baseline BESIDE
105
6000
xy design
BESIDE
10000
10
4000
2000
10a
50 number of arms
100
10
20
30
40
2 epsilon
size of Z
Figure 2: Total arm pulls to ter- mination vs. number of arms
Figure 3: Total arm pulls to termination vs. |
Figure Total arm pulls termination vs.
3.1 Practical Algorithms for Active Classification Under Constraints
Next, we provide an application of the above ideas to bose- active classification with constraints namely, adaptive sampling learn the highest accuracy classifier with a constraint the false discovery rate (FDR). We first explain how this problem maps to the linear bandit setting. Precisely, let X' be the example space and y {0, the label space. Fix hypothesis class H such that each h
H is classifier h X + y. We represent each h with associated indicator vector Nn E (0, 1] 1. Similarly, let 1) E [0, 1 represent the label distribution, i.e. y(x)) = IP(Y = 1|X = x). Then the risk of a classifier R(h) == Re Ber(n))))))))))) [[[h(r)) # YIl 2/ (2n - 1) and the FDR is defined as FDR(h) := (1 n) 2/1 2. In the case when
where 2n (x) = 1 < h(x))
7 E (0. FDD(h) is the proportion of examples that h incorrectly labels as 1 out of all
7

---

examples h labels as 1. Our goal is to solve the following constrained best arm identification problem:
h = min R(h) s.t. FDR(h) S q KER
+
min hCH
s.t. ((1-n) - ) -1
S 0. (5)
The main challenge in running BESIDE on this problem directly is potentially high computational cost from computing a design over an extremely large hypothesis class H. (e.g. neural networks of a bounded width). In this section we provide an alternative approach motivated by BESIDE. Algorithm follows a similar design as BESIDE and relies on an oracle, CERM, that can solve (5) i.e. given a dataset it returns the highest accuracy classifier under an FDR constraint. Such oracles are available in, for example II ICC In each round of Algorithm we perform randomized exploration by perturbing the labels our existing dataset with mean zero Gaussian noise, and then training k classifiers h2, E [k], on the resulting datasets. Implicitly, we making the assumption that the loss function in the training of ERM can handle continuous labels, such as the MLE of logistic regression. As described in [25). randomized exploration emulates sampling from posterior distribution on possible set of classifiers. We then use the labels generated from these classifiers to compute safe classifiers ha, i [k:.. Finally, mimicking the strategy of BESIDE, we compute safo and X' designs on these & safe classifiers and repeat (note that the designs computed on Line 5 are equivalent X.V and aYa in the classification setting).
Algorithm 2 Active constrained classification with randomized exploration
(0) (0) Require: Batch size n, initial (labeled) data si 1..., In number of rounds I,, number of classifiers per round k perturbation variance
1: for L = 1,.... do
2: for 1,...,k do
h. ERM(((=) (1) (1) +.2 where Jisign itd. N((, 21 h; = CERM (2x, (1(()))
3:
4:
5: Compute designs:
Asale
arg minxe maxisigk Exex (h)
((,(())
Anr
d
arg minxe maxisipjsk Ezex
A=
6: Sample (e) .....,.......................... In from uniform mixture of Asate, Adiff
(2)
7: Observe corresponding labels y1 ( ........h""
return CERM( (zx) (f) )ssesmosses)
To validate Algorithm 2 we experiment against passive baseline that selects points uniformly at randoms from the pool of examples X, retrains the model using the same Constrained Empirical Risk Minimization oracle (CERM) as Algorithm 2 on its current samples, and report the accuracy and FDR. We evaluate on two real world datasets and on one synthetic dataset next and provide an additional details on the experiments in Section
Adult dataset. We evaluate on the adult income data set [27] (48,842 examples) where the goal is predict whether someone's ' income above $50k per year. We the constraint be FDR < 0.15 and report in Fig- ure the accuracy and the FDR obtained when varying the number of labels given each method (batch size is set to 25 and initial number of queried labels is 50). We observe that for any desired accuracy Algorithm alloos us to provide a classifier with lower FDR. Also, for any chosen number of total labels- as 500, 750, 2000 reported in Figure 5 the Algorithm 2 gives classifier with higher accuracy and lower FDR. In general we found that the active method needed half the number of sam- ples as the passive sampling to achieve a given FDR. This demonstrates the effectiveness of Algorithm 2 to learn si- multaneously the objective (risk) and the constraint (FDR),
Adult dalaset
0.40
5E0
0.35
0.30
300
0.25
500
passive
n 750
0.20
active
0.15
0.79
0.80
0.81
accuracy
Figure 5: FDR accuracy for active (Al-
gorithm P and passive sampling, ticks report number of samples. FDR and accuracy are averaged over 5 trials
in similar favorable way as characterized by our theoretical findings.
8

---

German Credit dataset. We consider the German Credit Dataset originally from the Staflog Project Databases [24]. The goal is to predict whether someone's s credit is 'bad' or 'good'. We report in Figure the recall (TPR) and the precision (1 FDR) obtained when varying the number of labels given to each method. We observe that for any desired precision Algorithm alloows us pro- vide a classifier with higher recall. Also, for any chosen number of total labels Subells-uuh-ae as 170, 270, 330, 450, 600 as reported in Figure 6 the Algorithm 2 gives a classifier with higher precision and higher recall. As for the Adult dataset we found that the active method needed half the number of samples as the passive sampling achieve given precision.
German Credit dataset
8 172
310
0.86
0.84
m- 400
0.82
passive
active
0.80
0.78
0.80
0.82
0.84
precision
Figure 6: TPR vs FDR for active active
(Algorithm 2 and passive sampling, ticks report number of samples. Precision is FDR, recall TPR. Precision and recall are averaged over 25 trials
Half circle dataset. We consider a -wo-dimensional half circle dataset, visualized on Figure 10 We report in Figures 11 12n the precision and (respectively) the recall obtained when varying the number of labels given to each method. The confidence intervals are obtained over 25 repetitions. We observe that Algorithm 2 allows to provide classifier satisfying a given recall precision in far fewer queries. This is in line with the results of [16] on One Dimensional Thresholds, where the sample complexity of the active strategy is (Iog(n)) while the sample complexity of the passive strategy is at least of order n.
Half circle dataset
Half circle
Half circle
1.0000
1.000
feature
label
precision
0.9975
recall
0.995
0
0.9950
active
active
label
0.990
0.9925
passive
passive
0.985
-1
0.0
0.5
1.0
250 500
750
250
500
750
x feature
number of labels
number of labels
Figure 7: Half circle dataset.
Figure 8: Precision
Figure Recall
Related works
Constrained Bandits. growing body of work seeks address the question of safe learning in interactive environments. In particular, the majority of such works have considered the problem of regret minimization in linear bandits with linear safety constraints. Here, the goal is to maximize online reward, xx 0., by choosing actions 2, E X C Rd, while ensuring a safety constraint of the form I.7 < y is met at all times (either in expectation or with high probability). A variety of algorithms have been proposed, including UCB-style 23 32), and Thompson Sampling [30, 3T
While these works show that VT regret attainable, they only provide worst-case bounds (while we obtain instance sestance-ddeedden bounds) and do not study the pure-explore pure-exploration best-arm identification problem. To our knowledge, the only work to offer mnstance-depende focus exclusively on the regret setting, and offer relatively coarse notion of instance-dependence analogous to Old poly log T/Amin Amin) bounds in the unconstrained linear bandits setting in contrast to the more fine-grained notion of instance-dependdece we provide.
guarantees is [9], yet they
To our knowledge, only several existing works consider the question of best-arm identification with safety constraints [36] (37 39 22). The most related to ours is (28) which focuses on the easier problem of safe best arm identification with known rewards and unknown constraints. Since the reward is known, the main challenge in the setting of (28) is to learn constraints via G-optimal designs. The key and novel challenge of our framework is carefully balance between G and X') designs: naively spending enough budget to either learn the reward model (via X' design) or to learn the safety constraints (via a design) will fail catastrophically (see Example 2. I and Proposition 1). (36] 37) consider a general constrained optimization setting where the goal of the learner is to minimize some function (xx over domain E DD while only having access to noisy samples of f(x), f(x) + wi, and guaranteeing that safety constraint g(xx)) > f is met for every query point zt-

---

While they do provide a sample complexity upper bound, they give no lower bound, and, as shown in [39]. their approach can be very suboptimal. [9] considers the setting of best-arm identification in multi-armed bandits. In their setting, at every step / they query a value at E A for particular coordinate it, and their goal to identify the coordinate i" such that a f-- 2 max; a where af is the largest value respecting the safety constraint: o = arg aE al, s.t. ap4, S y. Similar to [36, 37]. they require that the safety constraint aejts, S 7 must be met while learning. Though they do show matching upper and lower bounds, and in addition consider slightly more general setting that allows for nonlinear (but monotonic) response functions, they treat every coordinate as independent, and do not allow for information information-sharing between coordinates the key generalization the linear bandit setting targets. We remark as well that in our setting, unlike these works, we allow the learner to query unsafe points during exploration, and only require that they output safe decision at termination.
Best-Arm Identification in Linear Bandits. The best-arm identification problem in multi-armed bandits (without safety constraints) is a classical and well-studied problem [3
12 5 and near-
optimal algorithms exist [18] 22]. More recently, there has been a growing interest in understanding
the sample complexity of best-arm identification in linear bandits 35
19
40
13
20
We
highlight in particular the work of [3] which proposes an experiment-design based algorithm, RAGE, that our approach takes inspiration from. While much progress has been made in understanding best-arm identification linear bandits, to our knowledge, no existing works consider the setting of best-arm identification in linear bandits with safety constraints, the setting of this work.
Active Classification under FDR constraints We finally mention one other related body of work- the problem of actively sampling find classifier with high accuracy or recall under precision constraints. Motivated by the experimental design approach of our main algorithm, BESIDE, we provide heuristic algorithm for this problem with good empirical performance in Section 3.1 There is an extensive body of work on active learning (see the survey (14) but only recently have works made the connection between best-arm identification for linear bandits and classification [21 16 7
Precision constraints has been less studied in the adaptive context, we only know of [[6
5 Conclusion
In this work we have shown that it is possible to efficiently find the best safe arm in linear bandits with a carefully designed adaptive experiment design-based approach. Our results open up several interesting directions for future work.
Instance Optimality. While BESIDE is worst-case optimal, in Appendix A we show an instance- dependent lower bound which BESIDE does not, in general, seem to hit. We conjecture that this lower bound may be moose-addressing this discrepancy and showing matching instance-dependent upper and lower bounds is an exciting direction for future work.
Safety During Exploration. Though there are many interesting applications where we may not require safety during exploration (i.e. only querying safe arms), in other cases we may need to ensure safety is met during exploration. Extending our work to this setting is an interesting open problem.
Potential Impacts. As with any algorithm making stochastic assumptions, if assumptions are not met can not guarantee the performance. In this case, one limitation is that if the underlying environment is changing (i.e. the constraints vary over time) the algorithm could have unexpected behavior with unintended consequences. Such a situation could lead harmful results in examples such as the online ad advertising bidding example from the introduction. To mitigate this limitation of our setting, practitioners are encouraged to monitor many metrics, both short and long-term.
Acknowledgements
The work of AW was supported by an NSF GFRP Fellowship DGE-1762114, The work of JM was supported by an NSF Career award, and NSF Al institute (IFML) and the Simons collaborative grant on the foundations of fairness. The work of KJ was funded in part by the AFRL and NSF TRIPODS 2023166.
10

---

References
[1] Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna Wallach. A reductions approach to fair classification, 2018.
[2] Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. Linear stochastic bandits under safety constraints. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché Buc, Edward A. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pages 9252-9262, 2019. URL http:h/pappprrr nips. hwtp:cccppppp/p.e 99144- 11124-1inear" stochastic-
cetastic-bandiige bwndits- under snteerssafftyye contraico
[3] Robert Bechhofer. A sequential multiple-decision procedure for selecting the best one of several normal populations with a common unknown variance, and its use with various experimental designs. Biometrics, (433):48-422) 1958.
[4] Paul N Bennett, David M Chickering, Christopher Meek, and Xiaojin Zhu. Algorithms for active classifier selection: Maximizing recall with precision constraints. In Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, pages 711-719, 2017.
[5] Sébastien Bubeck, Rémi Munos, and Gilles Stoltz. Pure exploration in multi-armed bandits problems. In International conference on Algorithmic learning theory, pages 23-37. Springer, 2009.
[6] Romain Camilleri, Julian Katz-Samuels, and Kevin Jamieson. High-dimensional experimental design and kernel bandits, 2021.
[7] Romain Camilleri, Zhihan Xiong, Maryam Fazel, Lalit Jain, and Kevin Jamieson. Selective sampling for online best-arm identification, 2021.
[8] Olivier Catoni. Challenging the empirical mean and empirical variance: deviation study. In Annales de I'IHP Probabilités et statistiques, volume 48, pages 1148-118,,, 2012.
[9] Tianrui Chen, Aditya Gangrade, and Venkatesh Saligrama. A doubly optimistic strategy for safe linear bandits, 2022. URL https:: //axxiv. www.oogg///////eo.///...o.eeee/e abs//209/ 13694.
[10] Andrew Cotter, Maya Gupta, Heinrich Jiang, Nathan Srebro, Karthik Sridharan, Serena Wang, Blake Woodworth, and Seungil You. Training well-generalizing classifiers for faimess metrics and other data-dependent constraints, 2018. URL httpt::ttt//aat:t wttp://w.rrg/ab//18...000
[11] Rémy Degenne, Pierre Ménard, Xuedong Shang, and Michal Valko. Gamification of pure exploration for linear bandits. In International Conference on Machine Learning, pages 2432- 2442. PMLR, 2020.
[12] Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Pac bounds for multi-armed bandit and markov decision processes. In International Conference on Computational Learning Theory, pages 255-270. Springer, 2002.
[13] Tanner Fiez, Lalit Jain, Kevin Jamieson, and Lillian Ratliff. Sequential experimental design for transductive linear bandits, 2019.
[14] Steve Hanneke. Theory of active learning. Foundations and Trends in Machine Learning, (2-3), 2014.
[15] Elad Hazan and Satyen Kale. Projection-free online learning, arXiv preprint vrXiv:1206.4657. 2012.
[16] Lalit Jain and Kevin Jamieson. A new perspective on pool-based active classification and false-discovery control, 2020.
[17] Kevin Jamieson and Lalit Jain. Interactive machine learning. 2022.
[18] Kevin Jamieson, Matthew Malloy, Robert Nowak, and Sébastien Bubeck. lil' dil'ucb: An optimal exploration algorithm for multi-armed bandits. Conference on Learning Theory, pages 423-439. PMLR, 2014.

---

[19] Zohar S Karnin. Verification based solution for structured mab problems. Advances in Neural Information Processing Systems, 29, 2016.
[20] Julian Katz-Samuels, Lalit Jain, Kevin G Jamieson, et al. An empirical process approach the union bound: Practical algorithms for combinatorial and linear bandits. Advances in Neural Information Processing Systems, 33:
2020.
[21] Julian Katz-Samuels, Jifan Zhang, Lalit Jain, and Kevin Jamieson. Improved algorithms for agnostic pool-based active classification, 2021. URL httpt:t//axaai...ooo abs/ 06499.
[22] Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best arm identification in multi-armed bandit models, 2016.
[23] Abbas Kazerouni, Mohammad Ghavamzadeh, Yasin Abbasi Yadkori, and Benjamin Van Roy. Conservative contextual linear bandits. Advances in Neural Information Processing Systems, 30, 2017.
[24] E. Keogh, C.; Blake, and C. Merz. Uci repository of machine learning databases,, 1998. URL nttp://archive. ics. uci. edu/ml
[25] Branislav Kveton, Manzil Zaheer, Csaba Szepesvari, Lihong Li, Mohammad Ghavamzadeh, and Craig Boutilier. Randomized exploration in generalized linear bandits, 2019. URL https
//ar larxiv.org// orgooggggggoo wwwrg/abs/199... 08947
[26] Tor Lattimore and Csaha Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[27]
M Lichman. Uci machine learning repository, 2013. URL http::/archive. ics. uci edu/
m
[28) David Lindner, Sebastian Tschiatschek,, Katja Hofmann, and Andreas Krause. Interactively
learning preference constraints in linear bandits, 2022. URL httL:/ttps://axxivorrr/bbb 05255.
[29]
Blake Mason, Romain Camilleri, Subhojyoti Mukherjee, Kevin Jamieson, Robert Nowak, and Lalit Jain. Nearly optimal algorithms for level set estimation. arXiv preprint 1..0722 2021.
[30] Ahmadreza Moradipari, Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis, Safe linear thompson sampling with side information, 2019. URL
0211622156
[31] Ahmadreza Moradipari, Christos Thrampoulidis. and Mahnoosh Alizadeh. Stage-wise conser- vative linear bandits. 2020. doi: 1044550ARXXW.200000001. URL WRt/httss///axxiv.
abs/2010. /bss/2010000011
[32] Aldo Pacchiano, Mohammad Ghavamzadeh, Peter Bartlett, and Heinrich Jiang. Stochastic bandits with linear constraints, 2020. /tt//tttp////rrr..orrg wttp://///aaaa////////////// 10185
[33] Edward Paulson. sequential procedure for selecting the population with the largest mean from k normal populations. The Annals of Mathematical Statistics, pages 174-180, 1964.
[34] Max Simchowitz, Kevin Jamieson, and Benjamin Recht. The simulator: Understanding adaptive sampling in the moderate--onfideen regime. In Conference on Learning Theory, pages 1794- 1834. PMLR, 2017.
[35] Marta Soare, Alessandro Lazaric, and Rémi Munos. Best-arm identification in linear bandits. Advances in Neural Information Processing Systems, 27:828-836, 2014.
[36] 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.
[37] 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.
12

---

[38] Andrew Wagenmaker, Yifang Chen, Max Simchowitz, Simon S Du, and Kevin Jamieson. Reward-free no harder than reward-aware rl in linear markov decision processes. arXiv preprini arXiv:2201. / 2022.
[39] Zhenlin Wang, Andrew Wagenmaker, and Kevin Jamieson. Best arm identification with safety constraints. In International Conference on Artificial Intelligence and Statistics. PMLR, 2022.
[40] Liyun Xu, Junya Honda, and Masashi Sugiyama. A fully adaptive algorithm for pure explo- ration in linear bandits. In International Conference Artificial Intelligence and Statistics, pages 843-851. PMLR, 2018.
13

---

Checklist
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] See Conclusion.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Conclusion.
(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 of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Refer to Appendix.
If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material or URL.? [Yes] Refer to Appendix.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Refer to Appendix.
(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, cloud provider)? [Yes] See Appendix.
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? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new 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'ne 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 or 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]
14


Reviews:
[{"review_id": "nnHWGwxXh89", "reviewer": "Reviewer_QfJJ", "summary": "The paper proposes a study for the best arm identification problem and an algorithm that constructs an adaptive experimental design to efficiently balance exploration between the refinement of estimates and optimality gaps. The paper studies the problem from the perspective of a linear bandits setup. The algorithm is evaluated on a synthetic and a publicly available real-world dataset.", "questions": "- I wonder how realistic the problem setting actually is. The paper studies the problem of estimating both the value and safety of actions. However, in practice, in my opinion the safety of actions can oftentimes be defined a priori.\n- A second question I have is about safety violations during learning. In practical applications – when learning on the job – safety violations are not permitted and can also cause harm. This essentially renders the approach useless in such settings, right? In such cases [32, 33] seem to be better suited…\n", "limitations": "Yes.", "rating": 4, "confidence": 1, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Unfortunately, for me the paper was not easily accessible as I am not familiar with studies of active learning from a linear bandits perspective.\n\nStrengths of the paper:\n- The paper is very well-written \n- The paper to me seems technically sound and theoretical assumptions are formally proved \n- The algorithm is evaluated on synthetic and real data\n\nWeaknesses of the paper:\n- To me the paper was not easily accessible and could at points additionally resort to intuitive explanations (it is not within my field of expertise though)\n\nTo me the additional contribution over [35] could be outlines more clearly. In lines 316 to 321 the paper describes one big difference: safety constraints must be satisfied during training – which to me seems more reasonable. The rest of the paragraph only considers [32, 33] but does not further differentiate from [35].\n\nMinor things:\n- I was a bit confused by some terminology. In lines 19-21 the paper uses s_t for the price and strategies s \\in S for bidding strategies. But those are not compatible right? \n- In line 45, when introduction \\mu, please immediately explain that these are the set of constraints (although mathematically clear, this is only mentioned at some remote point)\n- Line 335: missing “.” after ‘constraints‘\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": "HON1mEIqEo5", "reviewer": "Reviewer_rbwS", "summary": "This paper explores a constrained linear bandit problem, i.e., a learner that can maximize a linear objective subject to linear constraints when given access only to noisy observations of the objective and of constraint satisfaction for an input action. The proposed algorithm is proved to be $(\\delta, \\epsilon)$-PAC, in that it generates a solution that is at most $\\epsilon$-suboptimal/infeasible with probability $1-\\delta$; in addition, has a lower bounded number of samples. This methodology can be applied to active learning with custom constraints on model performance and the paper demonstrates its performance over naive random data collection policies.\n", "questions": "- In the active learning experiments, what is the FDR constraint right-hand-side? What is the level of constraint satisfaction? \n- What is the batch size? And initial number of rounds? It is understood that active learning algorithms are often heavily sensitive to initial settings and rounds (Munjal et al.)\n- My interpretation was that the passive sampler baseline always satisfies the constraints, due to the CERM. Is this interpretation correct? If so, any active learning sampler + CERM should be able to ensure the constraints are satisfied, then, how would other well-known active learning strategies perform, e.g., coreset?\n\n**References**\n\nMunjal et al., Towards Robust and Reproducible Active Learning using Neural Networks, CVPR’22\n\n", "limitations": "The paper clearly describes societal impact and potential limitations of their framework.", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n- The overall problem is interesting and very general, suggesting many potential applications. I only briefly checked the main theoretical result, but it seems sound. \n\n**Weaknesses**\n\n- There is very limited experimental analysis, especially compared to baselines. Pool-based active learning is a well-studied problem and although the constrained active learning problem is new, the paper only considers a passive random sampler baseline. It would be useful to see more meaningful baselines to justify the methodology. In related works, the authors mention several other papers in this space (Sui et al., Sui et al., Wang et al.). Can these be considered as baselines?\n\n**References**\n\nSui et al., Safe exploration for optimization with gaussian processes.\n\nSui et al., Stagewise safe bayesian optimization with gaussian processes.\n\nWang et al., Best arm identification with safety constraints\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": "3GIJGcoJIA", "reviewer": "Reviewer_4PUH", "summary": "In this paper, the authors attempt to learn the (near) optimal decision in the linear bandit setting with the additional imposition of safety (linear) constraints. They supplement their results with experiments on real-world data sets.\n\n\nFirst they define the STBAI problem which aims to find an arm whose utility is maximum but also satisfies a safety requirement i.e its expected risk is below a threshold \\gamma.\n\nThen they define an $\\epsilon$ approximation to the STBAI problem the goal is to have the expected utility of our chosen arm within $\\epsilon$ of that of the best arm and we violate the safety constraint inequality by at most $\\epsilon$.\n\n\nThen they give an algorithm to identify such an arm and explore the sample complexity (and computational complexity) of such a routine. They show that when safety constraints are moot, this complexity is essentially matched by the lower bounds for best-arm identification. Similar results can be shown for the standard linear bandits setting.\n", "questions": "Line 66: should be -\\epsilon in eq(1)\n\nDue to paucity of time, i did not verify the correctness of the technical results. But I was wondering if the techniques used in the paper are completely new or have been extended/motivated from techniques used in prior work. As such in the main paper, i did not see any references to related techniques.\n\nWhat is a practical example of a safety constraint ? Apologies if this is already given in the paper but I might have missed it. \n", "limitations": "None.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: I am not familiar with this area, but I find this work quite original to the best of my limited knowledge.\n\nQuality: The quality of writing is above average. I like how the setting is explained; how different scenarios correspond to previously known settings and the comparison. The algorithm is complicated but they do try to give an intuitive explanation.\n\nClarity: The non-technical part of the paper is clear to understand. As for the technical part, my domain is not in this area, but the theorem statements and the corresponding corollaries make sense to me.\n\nSignificance: Since this is not my field of expertise, i can not make a solid judgment on the significance, but to me, the significance as compared to prior work seems not path breaking but not too minor either.\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": {}}]

Author rebuttal:

Decision: Accept