Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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.
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.

Strengths of the paper:
- The paper is very well-written 
- The paper to me seems technically sound and theoretical assumptions are formally proved 
- The algorithm is evaluated on synthetic and real data

Weaknesses of the paper:
- 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)

To 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].

Minor things:
- 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? 
- 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)
- Line 335: missing “.” after ‘constraints‘

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.
- 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…

limitations: Yes.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: 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.

strengths_and_weaknesses: **Strengths**

- The overall problem is interesting and very general, suggesting many potential applications. I only briefly checked the main theoretical result, but it seems sound. 

**Weaknesses**

- 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?

**References**

Sui et al., Safe exploration for optimization with gaussian processes.

Sui et al., Stagewise safe bayesian optimization with gaussian processes.

Wang et al., Best arm identification with safety constraints

questions: - In the active learning experiments, what is the FDR constraint right-hand-side? What is the level of constraint satisfaction? 
- 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.)
- 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?

**References**

Munjal et al., Towards Robust and Reproducible Active Learning using Neural Networks, CVPR’22


limitations: The paper clearly describes societal impact and potential limitations of their framework.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.


First 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.

Then 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$.


Then 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.

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.

Quality: 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.

Clarity: 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.

Significance: 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.

questions: Line 66: should be -\epsilon in eq(1)

Due 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.

What is a practical example of a safety constraint ? Apologies if this is already given in the paper but I might have missed it. 

limitations: None.
review_title: null

Meta-review: metareview: 3 reviewers evaluated the submitted paper, 2 recommending rejection (1x reject, 1x borderline reject), 1 borderline acceptance. There was some interaction between authors and reviewers and the reviewers considered the authors' responses. Unfortunately, the reviewers' expertise was more on the active learning side and less on the bandit side -- in that regard, the paper title is rather uninformative about what to expect from the paper. Therefore, I decided to read the paper closely myself.

-- 

Based on my own reading, I would argue that the paper makes some valuable contributions to the problem of solving safety-constrained bandits. The considered problem setting in which constraint violations are possible during exploration is relevant as motivated by the authors by several convincing examples.

The theoretical and algorithmic contributions (assuming the correctness of the proofs which I didn't check in large detail) are interesting, providing some first solid insights into a novel problem setting, and providing the first algorithm to solve the considered problem setting with guarantees.

The coverage of related work is mainly fine but, as also noted by the authors, is missing the very related paper by Lindner et al. (ICML'22) which investigates a similar but simpler problem setting.

The empirical evaluation is not very exhaustive but is in line with typical bandit papers. My only real criticism in that regard is that the chosen baseline is unnecessarily weak in that it estimates all safety gaps up to some desired precision while it would be sufficient to estimate those only until one can be sufficiently certain that an arm is not feasible. One can also think of other sensible baselines, e.g., a greedy policy that focuses on the most promising-looking arms until they are shown to be unsafe, if they are (of course one can then construct examples, where such a strategy will fail but for not constructed examples such a strategy might work reasonably well).

The write-up is mainly clear and easy to follow if one is familiar with general bandit literature. Nevertheless, the title of the paper is rather uninformative and might trigger incorrect expectations. 

Overall, as already said above, I think the paper would be a valuable addition to the existing literature.

--

Taking into account my own reading of the paper, as well as the 3 submitted reviews, and the author's feedback, I am recommending acceptance of the paper. The main concerns of the critical reviews were regarding the relevance of the problem setting, violation of constraints during exploration, and the evaluation, in particular the considered baselines. While the raised concerns are valid, I think the authors sufficiently justify their problem setting and the empirical evaluation is also sufficient (although it could clearly be extended; see some suggestions in my review and also below). I see the paper's main contributions on the theoretical side - and in that regard, there are some novel valuable insights.

When preparing the camera-ready version of the paper, please consider the following suggestions for improving the paper:

* Adjust the discussion of related work: in particular, include Lindner et al. in the revised paper
* Consider the addition of further baselines to provide a better sense of the proposed algorithm's performance
* There are some minor issues with notation, e.g., line 55/56 should be an argmax. So please carefully revise your paper in that regard.
* Consider adjusting the title of your paper to better match it to the content
* Carefully consider all reviews, in particular also those recommending rejection, when preparing the camera-ready version and adjust your paper accordingly; For instance, I suggest implementing some of the authors' responses that came up in the discussion to emphasize the importance and practical relevance of the studied problem better.
confidence: Less certain
Decision: Accept