Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper considers stochastic linear bandits with (possibly nonlinear) cumulative constraints that need to be satisfied on expectation. For this problem they propose a pessimistic-optimistic algorithm with the following properties: (i) it has O(\sqrt(\tau)) regret at each round \tau; (ii) it has zero constraint violations at any round \tau>\tau' for a constant number of rounds \tau'.
main_review: The paper has potentially some interesting ideas. However, I am afraid that I am leaning towards recommending rejection in its current form for the following main reasons: 

(i) Insufficient reference to related works.
First, in my opinion it is not good practice to defer the entire section on related works to the appendix. Second, the authors have missed citing a series of recent related works on safe bandits; for example (and several more...) 
* Khezeli, K. and Bitar, E. (2019). Safe linear stochastic bandits. arXiv preprint arXiv:1911.09501
* Kazerouni, A., Ghavamzadeh, M., Abbasi, Y., and Van Roy, B. (2017). Conservative contextual
linear bandits. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S.,
and Garnett, R., editors, Advances in Neural Information Processing Systems 30, pages 3910–3919.
Curran Associates, Inc.
* Moradipari, Ahmadreza, Christos Thrampoulidis, and Mahnoosh Alizadeh. "Stage-wise Conservative Linear Bandits." Advances in Neural Information Processing Systems 33 (2020).
* HasanzadeZonuzy, Aria, Dileep M. Kalathil, and Srinivas Shakkottai. "Learning with safety constraints: Sample complexity of reinforcement learning for constrained mdps." arXiv preprint arXiv:2008.00311 (2020)
* Moradipari, Ahmadreza, et al. "Safe linear thompson sampling." arXiv preprint arXiv:1911.02156 (2019).

(ii) Comparison to related works. 
The authors claim that their setting is more relaxed than that of [32]. But, they do not seem to discuss what their result implies specifically for the setting of [32] and how exactly it compares to their result.
Lines 81-82: Constraints in [6] hold with high-probability, but they are *not* on expectation as in this paper's setting. Thus, the claim does not appear correct. 

(iii) Motivation.
What is the motivation behind the formulation in (2)? Can you provide concrete examples elaborating on the potential applications on "safety, fairness, and budget constraints"? 

In addition to the points above:
(iv) Simulation results might help the reader better understand the algorithm's operation
(v) How is \delta estimated to be used in the algorithm? How does the mismatch in estimating this quantity affects the regret and constraint violations?
(vi) Intuitively knowledge that the constraints have specific structure (eg linear) should affect performance. How is this reflected in the bounds? 


===============
Increase score to 5 after rebuttal. See discussion.
limitations_and_societal_impact: Limitations of the model/setting/algorithm/analysis are not clearly discussed
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies stochastic linear bandits with anytime cumulative constraints on (non)linear costs. It proves a sublinear regret bound for the reward, and beyond round $\tau'$, it shows that the proposed primal-dual algorithm has zero constraint violation. 
main_review: *Main Comments*
- The analysis and proof structure is well-written and easily understandable. I have verified the details and am satisfied with the correctness of the proof. 
- The observation model in line 128 for the constraints is the full-information setting,  i.e. the learner observes the costs $W^k(c(t),  j)$ for each $j$, and not just the cost of the played arm. Please justify this feedback model. This also needs to be made explicit in the introduction. This is different compared to [32] which observes the cost only of the played arm, and perhaps the comparison to [32] is not fair. 
- In Section 5, the paper also considers linear cost functions and obtains similar regret guarantees (by replacing the empirical estimates with the UCB estimates). Again, this needs to be explicitly explained in the introduction. Since this setting is now the same as [32], please compare the technical novelty in the analysis and the bounds to those obtained in [32]. 

*Details*
- It would be helpful to give examples that require anytime cumulative constraints, and which are not covered by cumulative constraints (not anytime) or anytime policy constraints. The setting studied by the paper needs to be better motivated. 
- How does the algorithm set the Slater constant $\delta$? Is the safe action known to the algorithm in advance?
- It would be helpful to do some synthetic experiments to verify the correctness of the algorithm and the regret bound. Of particular interest would be to empirically verify that there is no constraint violation after $\tau^\prime$ rounds. 
limitations_and_societal_impact: NA
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers stochastic linear bandits with general nonlinear constraints. They propose a pessimistic-optimistic algorithm for this problem, which obtains a sublinear of time and is computationally efficient. 
main_review: The paper is well written and easy to follow. I think that the main contribution of this paper is to extend linear bandits with linear constraints in [6], [32] to the ones with general nonlinear constraints.  However, there are several main limitations that make me lean towards rejection. 
(1)	The authors said that their results in a “much more efficient calculation” comparing to OPLB proposed in [32]. However, OPLB is designed for contextual bandit which is more general than the problem this paper is considering. More importantly, [32] also proposed an algorithm for linear bandits, called OPB, which can be “implemented extremely efficiently” as [32] mentioned. Thus, it would be fair if the authors compare their algorithm to OPB. 
(2)	Because the authors propose a new algorithm, experimental results are needed to demonstrate the performance compared to existing algorithms such as OPB in [32], SLUCB in [6].   
(3)	The idea of using a pessimistic-optimistic mechanism has been exploited in [32].  The primal-dual approach in optimization may be different from [32], however, this novelty is not enough so that it is a theoretical paper.  

limitations_and_societal_impact: No, the authors have not addressed the limitations. Please see my comments in the main review.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes an efficient pessimistic-optimistic algorithm for stochastic linear bandits with general nonlinear constraints. The authors give a later-constant-dependent regret that, compared to the unconstrained case, achieves a similar complexity order in terms of T but higher-order dependence on d. This algorithm also achieves zero-constraints violation after a certain time \tau, where $\tau$ is independent.  Besides the main results, the author also gives several side results including a high probability bound on sample-path version of the constraints and abound for linear cost when the cost is revealed after the learning taking actions (so it's also bandits).
main_review: --Originality:
While the analysis on the optimism part is standard LinUCB, the techniques the author uses to adaptively estimate the Lagrange multipliers via tracking its violations and choosing proper scaling parameters are novel. Also, this work makes an interesting connection between Slater’s constant and regret/violation updates.

--Quality:
This submission is technically sound, all the claims are supported.

--Clarity: 
This paper is well-written with clear intuition explanation and rigorous proof.

--Significance:
The results are meaningful and some analysis techniques including dual updates and the connection to Slater's constant are inspiring. 

--Question: 
I wonder if this algorithm could be directly extended to getting instance-dependent bound? In particular, I know linUCB is unable to achieve the optimal instance-dependent bound, but how about the bound depends on, for example, $\min_{c}  \min_{x’} \max_x <\theta, \phi(c,x) - \phi(c,x’)> $ ? Because I notice that, there are many parts in analysis that greedily use the term \sqrt{\tau} (scaling parameter V, budget $\epsilon_t$ ). It seems that aiming at $\sqrt{T}$ makes the whole problem less challenging.


limitations_and_societal_impact: The authors didn't address the limitation of their work. From a theoretical perspective, I think there are no big limitations. One concern I am thinking about is whether such an algorithm can achieve some instance-dependent regret as I raised in the main review.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a learning algorithm for a stochastic linear bandits with constraints. At each decision step, the decision maker can choose between J actions. Each action A_t then provides a context-dependent reward $r(C_t, A_t)$ and contributes a $W_k(C_t, A_t)$ to the "constraint k". The goal of the learner is to maximize the reward provided that the K constraint $\sum_{t=0}^\tau W_k(C_t, A_t) \le 0$ are respected.

The authors present an algorithm that guarantees a sublinear regret in $O(\sqrt{T})$ while respecting constraints for all time-steps except at most O(1) time-steps.

After presenting the algorithm, most of the paper is devoted to a careful analysis of the theoretical properties of the algorithm. No application nor experimental results are presented.

main_review: I think that the problem studied in the paper is very relevant. Most of the learning algorithms are either presented in a unconstraint setting or in very restrictive setting (like anytime action constraint). The type of constraints chosen in this paper are both quite expressive (they can represent fairness, budget,...) and also quite flexible to allow for efficient algorithms.

The algorithm presented in the paper is convincing. The algorithm is based on a primal-dual approach and uses virtual queues to estimate the Lagrange multipliers. I did not check all details but the proof methodology looks sound: The analysis is based on an optimistic algorithm (LinUCB) plus a Lyapunov-drift method.

The performance guarantee of the algorithm seem very good as the algorithm can provide a O(T) regret with a O(1) constraint violation.

From a methodological point of view, the paper is very close to the recent paper "POND: Pessimistic-Optimistic oNline Dispatching" by Liu et al.  Apart from the struct of the reward, the two settings are very close.

To me, the main limitation of the paper is that it is purely focussed on theory and does not provide any experimental algorithm. One may wonder if this is to keep the paper more consistant or because:
- formulating a real problem in this setting is difficult? 
- the hidden constants in the O(.) are too large to make the algorith practical?

Also, the reward setting with finite action space and linear payoff is quite specific and closely related to bandits. Would the approach be generalizable to more general contextual bandit settings?

limitations_and_societal_impact: There is no direct societal impact foreseen.

The theoretical part of the paper is strong but there is not empirical evaluation of the algorithm. This could be further discussed in the paper (the only discussion for now is to say that "it can be implemented easily").
review_title: null

Meta-review: This paper looks at linear stochastic bandits with unknown, non-linear constraints.

We had a discussion about the novelty of this paper, compared to the existing ones (with linear constraints). Even if the global idea is roughly the same, we believed that this paper still has new interesting methodology and that the non-linearity of constraints is actually quite challenging.

At the end, we believe this paper should pass the acceptance bar. 
Decision: Accept (Poster)