Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 


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: 

1. 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. 
2. 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. 
3. (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)?
4. 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 .  

questions: Please see above. 
limitations: Same as above.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.

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

strengths_and_weaknesses: Strength:

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

To construct a unified algorithm and regret analysis, they identify a novel sufficient condition.

The paper is well written and clear.    
questions: none
limitations: yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 
strengths_and_weaknesses: Strengths:
- The CKB framework can employ multiple exploration strategies.
- Under the sufficient condition, CKB can attain sublinear cumulative regret and sublinear cumulative constraint violations.

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

Comments:
- 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".
questions: - What are the definitions of $c_f(T)$ and $c_g(T)$ mentioned in Assumption 3?
- 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$ ?
- 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.
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: 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. 
strengths_and_weaknesses: Strengths:

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

Weaknesses: 

Please see the next section for questions.
questions: 1. Line 154-155: Better bounds on $\gamma_t$ are known in the literature [1]. Please update the citations accordingly.

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

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

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


[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

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

[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.
review_title: null

Meta-review: metareview: The paper provides new techniques (algorithmic as well as analytical) to solve black box optimization of smooth functions with constraints. The reviewers are largely in favor of the paper's contributions, and the author responses have helped to clarify several aspects of the presentation and connections to existing work. Therefore, I recommend that the paper be accepted.  
confidence: Certain
Decision: Accept