An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints
Authors: Xin Liu
Bin Li
Pengyi Shi
Lei Ying
Venue: NeurIPS 2021 Poster (2021)
Keywords: stochastic linear bandits
general constraints
pessimistic-optimistic algorithm

Abstract: This paper considers stochastic linear bandits with general nonlinear constraints. The objective is to maximize the expected cumulative reward over horizon $T$ subject to a set of constraints in each round $\tau\leq T$. We propose a pessimistic-optimistic algorithm for this problem, which is efficient in two aspects. First, the algorithm yields $\tilde{\cal O}\left(\left(\frac{K^{0.75}}{\delta}+d\right)\sqrt{\tau}\right)$ (pseudo) regret in round $\tau\leq T,$ where $K$ is the number of constraints, $d$ is the dimension of the reward feature space, and $\delta$ is a Slater's constant; and  {\em zero}  constraint violation in any round $\tau>\tau',$ where $\tau'$ is  {\em independent} of horizon $T.$ Second, the algorithm is computationally efficient. Our algorithm is based on the primal-dual approach in optimization and includes two components. The primal component is similar to unconstrained stochastic linear bandits (our algorithm uses the linear upper confidence bound algorithm (LinUCB)). The computational complexity of the dual component depends on the number of constraints, but is independent of the sizes of the contextual space, the action space, and the feature space. Thus, the computational complexity of our algorithm is similar to LinUCB for unconstrained stochastic linear bandits.


An Efficient Pessimstic-Optimistii Algorithm for Stochastic Linear Bandits with General Constraints
Xin Liu University of Michigan, Ann Arbor xinliuee@umi ch. edu
Bin Li
Pennsylvania State University binli@psu.
Pengyi Shi Purdue University shi178@purdue.cm edu
Lei Ying
University of Michigan, Ann Arbor leiying@umich..o cettsfumicche...
Abstract
This paper considers stochastic linear bandits with general nonlinear constraints.
The objective is to maximize the expected cumulative reward over horizon T subject set of constraints in each round т T. We propose a pessimistic- optimistic algorithm for this problem, which is efficient in two aspects. First, the algorithm yields δ
((Ki (Ka. + dd)
vF) (F) (pseudo) regret in round r & T, where
is the number of constraints, d is the dimension of the reward feature space, and 6 is a Slater's 's constant; and zero constraint violation in any round 7 > r', where I' independent of horizon T. Second, the algorithm computationally efficient. Our algorithm is based on the primal-dual approach in optimization and includes two components. The primal component similar to unconstrained stochastic linear bandits (our algorithm uses the linear upper confidence bound algorithm (LinUCB)). The computational complexity of the dual component depends on the number of constraints, but is independent of the sizes of the contextual space, the action space, and the feature space. Thus, the computational complexity of our algorithm is similar to LinUCB for unconstrained stochastic linear bandits.
Introduction
Stochastic linear bandits have broad range of applications in practice, including online recommen- dations, job assignments in crowdsourcing, and clinical trials in healthcare. Most existing studies on stochastic linear bandits formulated them unconstrained online optimization problems, limiting their application to problems with operational constraints such as safety, fairness, and budget con- straints. In this paper, consider stochastic linear bandit with general constraints. As in standard stochastic linear bandit, at the beginning of each round t e [T]. the learner is given a context c(t) that randomly sampled from the context set (a countable set), and takes an action A(t) [J]. The learner then receives a reward R(c(t), A(t)) = r(c(t), A())) + 77(), where r(c,,) = (0., o(c, o(c,j) E Rd is a d-dimensional feature vector for (context, action) pair (c,j), 0g E Rd is an unknown underlying vector to be learned, and nt{t) is a zeto-men meaa random variable. For constrained stochastic linear bandits, we further assume when action A(t) is taken on context c(t), it incurs K different types of costs, denoted by (())), that is unknown to the learner. This paper considers general cost functions and does not require (c, to have a linear form like r(c,j).
We assume (c)) j) is a random variable with mean
Denote the action taken by policy in round by (f). The learner's objective is to learn policy a that maximizes cumulative rewards over horizon subject to anytime cumulative constrainis:
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

max E
R(c(0, (0))
()
E
Σ w (c(), (7)) & v r [T], [K]. (2)
The constraint 2 above may represent different operational constraints including safety, fairness, and budget constraints.
Anytime cumulative constraints
In the literature, constraints in stochastic bandits have been formulated differently. There are two popular formulations. The first one a cunulative constraint over horizon T, including knapsack bandits [10 9 3 S
17 [[] where the process terminates when the total budget has been consumed; fair bandits where the number of times an action can taken must exceed a threshold the end of the horizon [12]; and contextual bandits with cumulative budget constraint [40] [4]. In these settings, the feasible action set each round depends on the history. In general, the learner has more flexibility in the earlier rounds, close to that in the unconstrained setting. Another formulation is anytime constraints, which either require the expected cost of the action taken in each round to be lower than threshold 66 [29] or the expected cost of the policy in each round is lower than threshold 32]. We call them anytime action constraints and anytime policy constraints, respectively.
Our constraint in the form of is anytime cumula- live constraint, i.e., it imposes cumulative constraint every round. This anytime cumulative constraint is most similar to the anytime policy constraint in [32 because the average cost of policy is close to its mean after the policy has been applied for many rounds and the process converges, so it can be viewed as cumulative constraint on actions over many rounds (like ours). Furthermore, when anytime cumulative constraint 2 is satisfied, is guaranteed that the time-average cost is below a threshold in every round.
cumulative constraints
anytihe policy constrainis
anytime chmulative comstraints
any anytime constraints
Figure 1: A conceptual description of feasi- ble policy sets under different constraint for- mulations.
In summary, our anytime cumulative constraint is stricter than a cumulative constraint over fixed horizon 7 but less restrictive than anytime action constraint in [6 29 Figure provides conceptual description of the relationship between these different forms of constraints.
Main Contributions
This paper presents pessimistic-optimistiic algorithm based on the primal-dual approach in optimiza- tion for the problem defined in (1--2) The algorithm is efficient in two aspects. First, the algorithm VT) regret in round < T and achieves zero constraint violation in any round 7 T' for a constant 7' independent of horizon T. Second, the algorithm computationally efficient.
yields
Ko076
For computational efficiency, the design our algorithm based on the primal-dual approach in optimization. The computation of the primary component is similar to unconstrained stochastic linear I [3 The dual component includes set of Lagrangian multipliers that are updated in simple manner to keep track of the levels of constraint violations so far in each round; the update depends on the number of constraints, but it is independent of the sizes of the contextual space, the action space, and the feature space. Thus, the overall computational complexity of our algorithm is similar to that of LinUCB in the unconstrained setting. This results in a much more efficient calculation comparing to OPLB proposed in [32]. OPLB needs to construct a safe policy set in each round, hence, its computational complexity is prohibitively high as the authors acknowledged.
bandits [15 33 25
For constraint violation, our algorithm guarantees that for any т > r', the constraint holds with probability one. In other words, after constant number rounds, the constraint is always satisfied. This is in contrast to prior works 32 6 where anytime constraints are proven to hold over horizon with probability
X for a constant X. other words, the anytime constraints may violated with probability X, and it is not clear how often they are violated when it happens. Furthermore.

---

beyond mean cost constraints considered in (2) and in [3 61. we prove that a
version of in round 7 under our algorithm.
A.f bOK
constraint 2 holds with probability -
To summarize, our algorithm is computationally efficient and provides strong guarantees on both regret and constraint violations. Additionally, our cost function is in general form and does not need to be linear as those in 32 6
We discuss more related work in the following.
Related Work
Stochastic linear bandits are a special class of contextual bandits [3 23), which generalize multi-armed bandits [22). Besides (32. considered an adversarial contextual bandit with anytime policy constraint representing fairmess. The proposed algorithm has Ö JC((T) regret when the context distribution is known the learner; otherwise it has O DlV/CIJT regret and O( /C(T) constraint violation. 24 studied a combinatorial sleeping bandits problem under cumulative fairness constraints and proposed an algorithm based on UCB which they conjectured to have Ō (T) regret
and ((VT) (T) constraint violation. Recent work studied unconstrained structured bandits and proposed primal-dual approach based asymptotically lower bound problem in bandits [2] 35 [6]. However,
our algorithm is different from them in three aspects, Our primal component is greedy algorithm instead of (sub-)gradient algorithm (as in (35)). Our dual component does not solve a best response problem, which is a constrained optimization problem as in [2 16]. Our analysis is based on the
Lyapunov-drift analysis for queueing systems. e.g.. we establish bound on the exponential moment of the dual variable, which is not present in [21 35 [6]. It is also worth mentioning that [20] 19 30 studied "conservative" bandits which require that the reward or the cumulative reward exceeds threshold at each step. Another line of related work is online convex optimization with constraints, studied in 22
36. where online primal-dual with proximal regularized algorithms have been proposed achieve O(vT) regret and O(1) violation for static constraints in [1 and (VVT) violation for stochastic constraints 42)
Notation. f(n) Ö(g(n)) denotes f(n) (gg(n)log"n) with >
[N] denotes the set (1,2, N); (:,-) denotes the inner product; (-)t denotes the transpose of vector matrix;
|| || ll,, and ||x||x VxlEx.
2 A Pessimistic-Optiie Optimistic Algorithm
We consider a stochastic linear bandit over horizon as described in the introduction. The learner's objective is to maximize the cumulative reward over time horizon T subject to K anytime cumulative constraints as defined in ID- To address the challenges on the unknown reward and cost in con- straint, well as the anytime cumulative constraints, develop pessimistic-optimle approach for constrained optimization. We first give out the intuition the
algorithm
based on the primal-dee algorithm and then provide the formal statement of the algorithm.
To start, we consider a baseline, deterministic problem that replaces all the random variables with their expectations. Different from the conventional setup, we introduce a "tightness" constant > 0:
Σ
(er j)
(3)
CEC,jE[]]
Σ Tejj
Faj 2 0, V.
(4)
Σ
(c, + + Ak [K],
(5)
GEC.jE[J]
where Fe.j can viewed as the probability taking action j on context e, and pa is the probability that context is selected in each round. We will discuss in further details the importance of the tightness constant e in Scction 4 The Lagrangian of the problem above is
max
Σ Eper(e,))ass cj
Ex x
Σ CEC.jE[J]
(kw (c, +e).
(6)
E, Leg -l
3

---

where ( is the Lagrange multiplier associated with the kth constraint in 5 Fixing the values of the Lagrange multipliers, solving the optimization problem is equivalent solving [C] separate subproblems (7), one for each context e, because the optimization variables x are coupled through only:
(
))
Er(e,)aass - Σx(s) (c.
max E, #oyy 5
Pe
&
Since the problem above is a linear programming, one of the optimal solutions is Zej = 1 for j = and že.j 0 otherwise, where
j E arg maxrax)(c..)) - E1 (0)
(k)
(1) (c,
(8)
and tie can be broken arbitrarily. If we call r(c. Eg (10) the action-value of context e, then the solution for fixed values of Lagrange multipliers is to choose action with the highest action-value. We may view the action value here plays a similar role as the Q-value (also called action-value function) in Q-learning [37].
Now the challenges to find solution according to 8 include: (i) both r(c, and w. (c, j) are unknown, and (ii) the optimal Lagrange multipliers (k) are also unknown. To overcome these challenges, we develop a pessimistic-oppimistie algorithm that
Uses LinUCB to estimate r(c,)) j) based on its linear structure.
Uses observed (c())c(t) to replace (* (c(t). at each round t.
Uses the following function to dynamically approximate the Lagrange multipliers (Xy(t) = if A(t) = j; otherwise (t()) 0):
( + 1)
Q (1)+
Σ (c() + vk. jE[J]
In other words, we increase its value when the current cost exceeds the current "budget," and decrease it otherwise. Therefore, (+) keeps track of the cumulative constraint violation by round t.
We further add scaling parameter 1/V, to (+)((t), i.. (t) approximate (R), With carefully designed Ve, we can control the tradeoff between maximizing reward and minimizing constraint violation in the policy and achieve the regret and constraint violation bounds to be presented in the main theorem.
Next, we formally state algorithm. This algorithm takes the following information as input the beginning each round t: (i) historical observations
F (c(s), A(s). R(c(s), A(s)), (CG))
(ii) current observations c(s) and (K) (ee and (iii) system parameters: the feature map (o(e, (o(e,)))eEc,ee (E time horizon T, and pre-set constant 8. the analysis of our algorithm, we will reveal the connection of this constant 8 with Slater's condition. The algorithm outputs the action in each round, observes reward R(c(t), A(t),, makes updates, and then moves to the next round + 1.
A Pessimisti--Opimmsstic Algorithm
Initialization: (1) = 0, B, = (8111111s & VBr. = and v = m + 22
For t = 1,...
Set: V- = 0.25 and 6 = 0.75
LinUCB (Optimistic): Use LinUCB to estimate r(c(t)..) for all j
F(c(t).)) = ((n())(((()). with f(c(t), = max(O ((c(t),
BeB,

---

Max Value:
Compute pseudo- pseudo-action-vee action- value of context c(t) for all action j. and take the action A(t) j with the highest pseudo-action aetooo-aattiiovvllllia value, breaking a tie arbitrarily
j E arg max maxf(((((t)))) V. Σ (d()))))))))))
pscudo action value of (c(t).
Dual Update (Pessimistic): Update the estimates of dual variables ((A)(t) as follows:
Q (1+ (1) Σ (d0.)) 1x vkk
Confidence Set Update: Update Me, dc Bt+1 and Bu+1 by the received reward j(c(t)."*)
n, Ex-1 +(c(t) (c(t,
0; Σ o(((s), ((s))
dd(b d
BB++ m 2log doo
Bet 10) 110 0.112, & BB+1).
The complexity of our algorithm is similar to LinUCB. The additional complexity is proportional to the number of constraints (for updating ((1)), and it is much lower than OPLB [32), where the construction of a safe policy set in each round is a major computational hurdle. Our algorithm is computationally efficient. Additionally, our algorithm does not estimate (c,),, need to make any specific assumption on we()) (c,
(c, hence, we do not
Main Results: Regret and Constraint Violation Bounds
To understand the performance of given policy æ,, we will analyze both the regret and the constraint violation. For that, we first define the baselines and state the assumptions made for the performance analysis. Then, we present our main results on the regret bound and constraint violations for the latter, we present both results on expected violation and an additional high probability bound for pathwise constraint violation.
3.1 Baselines and Assumptions
Regret baseline: We consider the following optimization problem:
max
Σ per(c,jaan jaes
(10)
[cC.E[[]
s.t.
Σ
Des = 1, Des 30 V.. C,
(11)
Σ
Paw (x) (c,j)zes 0, [k]
(12)
[EC.JE[]]
Constraint violation baseline: We choose zero (no violation) as our baseline.
worth noting the baseline we use in the regret analysis is derived from relaxed cumulative constraints instead of anytime cumulative constraints the original problem. Since the cumulative constraint is the least restrictive constraint, a learner obtains the highest cumulative rewards in such a setting. In other words, regret analysis is with respect the best (the most relaxed) baseline.
make the following assumptions for all the results present this paper.
Assumption The context c(t) are i.i.d. across rounds. The mean reward r(c,j) (O., (C,, [o. 1] with [| & 1, ||04| & m for any e C, j E [J]. 1((1) is zero-mean 1-subGoussian conditioned on A(t).
5

---

Assumption The costs in the constraints satisfy (c,)) & 1. Purthermore, we assume (c.)) are ii.d samples for given and
Assumption (Slater's condition) There exists > such that there exists feasible solution
to optimization problem (10)4T2) that guarantees _e (c. $ -6, 44 e [K]. We assume E because if the condition holds for > 1, it also holds for å 1.
We call 6 Slater's constant because it comes from Slater's condition in optimization - this is the input of our algorithm. This constant plays similar role as the cost of safe action in 16 (2). In fact, safe action guarantees the existence of Slater's constant, and we can estimate the constant by running the safe action for period of time. However, the existence of Slater's constant does not require the existence of safe action. It is also a more relaxed quantity than the safety gap in [6]. which is defined under the optimal policy. Slater's constant can be from feasible solution that is not necessarily optimal.
constant used
The next lemma shows that the optimal value of 10 is upper bound that of The proof this lemma can be found 26
Lemma Assume {c(t)} are ii.d. across rounds, and (R(c, and (c, are i.id. samples gäven action and context Let n² be the optimal policy problem - and x be the solution to (10 with entries
We have
T
E
Σ M(c(),5)xT (1) [=1 JE
Σ
ET Σ pelle OEC
The baseline problem (T0 is the same as the one presented in Section 2 except that the tightness constant 0 here. Any feasible solution for the tightened problem Section is feasible solution to the baseline problem. Under Slater's 's condition, when e < 6, the tightened problem also has feasible solutions.
3.2 Regret and Constraint Violation Bounds
Given the baselines above, we now define regret and constraint violation. Regret: Given policy n, define the (pseudo)-regret of the policy be
R(T)
Σ
Par(c,)==E - EE Σ Σ R(c()))37())
(13)
CEC,JE[M]
JE[
Constraint violation: The constraint violation in round 7 is defined to be
V(T)
Σ kE[K]
E
(
(c(.))))
(14)
je[J]
Note that operator (-)+ = max(., (.00) 0) imposed so that different types constraint violations
will not be canceled out.
Theorem Under Assumptions the pessimisiic-optimisii algorithm achieves the following regret and constraint violations bounds for any 7 E [T]
60
4.6K00.5
VF
dd+
R(T) & 83
+
2
/
5
d
48K²
16
1s
30K15
((T) 1K5
log
8K
VT
82
where (B-(T
2 2og T d log T/d).

---

We make a few important observations from our theoretical results. First, for the reward regret, we observe
R(r) = ( (K0.13
((Kk + + VT) VT).
So the regret is independent of the number of contexts, action space [J] and the dimension of cost functions W (:--). It grows sub-linearly in and the number of constraints K, and linearly in the dimension of reward feature d and the inverse of Slater's constant 6.
Second, for the constraint violation, observe
V(T) = 1
(0(4))
K 8
T TET
Kt
Kd 5z
(15)
otherwise
That is, the constraint violation independent of horizon T' and becomes zero when 7'. The constraint violation, however, has strong dependence on K and ō when & r'. This is not surprising because K defines the number of constraints, and represents the tightness of the constraints (or size of the feasible set).
Dependence Slater's constant. Both the regret and constraint violation increase in 6. To the intuition, note that 6 determines the size of the feasible set for the optimization problem. larger implies larger feasible set, it is easier find feasible solution, vice versa. Therefore, both regret and constraint violation increase as ô decreases because the problem becomes harder and requires more accurate learning.
Sharpness of the bound. In terms of horizon T, the bounds Theorem T are sharp because the regret bound R(T) matches the ietaace-indeeeendett regret (VTT) in multi-armed bandit problems without constraints [8] up logarithmic factors. Furthermore, zero constraint violation is the best possible. Therefore. the bounds are sharp up to logarithmic factors terms of horizon T.. is not clear whether these bounds are sharp in terms of K, d, and ò, which interesting open questions.
3.3
A High Probability Bound on Constraint Violation
The constraint (2) defined in the original problem and the constraint violation measure defined in (14) are both in terms of expectation. An interesting, related question is what the probability is for sample-path version of the constraints be satisfied. turns out that our algorithm provides a high probability guarantee on that as well. The proof can be found in [26].
Corollary The pessimistic-optiminae algorithm guarantees that for any T 3 where k is positive constant independent of T, K, 8 and d,
"k 8
(log ))
( (t)) > = =0 [e[J]
EVF
50x
4 Proof of Theorem
We first explain the intuition behind the main result. Recall that the algorithm selects action j* such that
j arg max f(c(T), V, [ (1(
and V, = O(VT). Therefore, when (7) o(VT), the reward term dominates the cost term, and algorithm uses LinUCB to maximize the reward. When (²)) (r) w(V7), the cost term dominates the reward term and our algorithm focuses reducing (4k), Slater's condition implies
that there exists policy that can reduce ((k) by constant (related to 5) in each round. Therefore, the algorithm takes Ö(VT) rounds to reduce ((k) to vT),,, which may add ((VT) to the regret
7

---

during this period. The argument above also implies that (T)((T) O(vF). Then, because
Σ w (c(t)))) JE(J]
< Q
1)
Σ c
we can further bound the constraint violation at time be a constant or even zero via the bound on (T + 1)] and proper choice of Ex.
4.1
Regret Bound
Now consider the regret defined in 113 and define x to be the optimal solution to the tightened problem (3 with e = Eg. We obtain the following decomposition by adding and subtracting corresponding terms:
R(7) (a) Σ (pr(ee)) - (c(0),))x((1)
Σ c
par(e,) (2 - 255 +E
FL. (rld0.))-((00...))) c(().)
x
fi-tight
reward mismatch
f
Σ K(1 + E?) 1-1
E
(16)
Vi
Lyspunov drift
K(1 4 V/
(F(c().)) - r((d)))))
(17)
sccumulated tightness
reward mismatch
where (a) holds because the random reward is revealed after action A(t) is taken the noise is independent the action. We next present a sequence lemmas that bounds the terms above. The proofs of these lemmas are presented in (26].
First, we establish an upper bound on (16) by using the Lyapunov-din drift analysis
We consider Lyapunov function L(l) Σn Q (l) and show that maximizing the pseudo action value in algorithm (MaxValue step) is equivalent to maximizing the following "reward minus Lyapunov drift"
V E ((((0,))x(()) - (L(t + - I(())-
Therefore, our algorithm outperforms a statie policy (((,,) and results the following lower bound
VIE
((c()).))xx()) jEl
Σ
E] L(0) > V Σ F((()))))000 - K(1 + (18)
jElo
Apply the telescoping sum on (18 provides an upper bound on 16 in Lemma
Lemma 2 Under the Pessimistic-Oppimmste Algorithm, we have
(100))))(0))))) xx(1) H(() h K(1 2 V
Kt(e + 2) > 6)
E
Σ F((()))) ( [EE
V1
Next, we present Lemma which establishes an upper bound on the tighttht term by comparing the optimal solution the original baseline problem and that its e, e tighteend version. is based on the intuition that adding ti-tightness to the feasible region only incurs O(Ez) loss in the reward.

---

Under Assumptions 3 problem and its tightened version:
Lemma? 3
we can bound the difference between the baseline optimization
Σ per(e (1
6
Finally, we present Lemma that provides an upper bound on the reward mismatch terms. The proof is based on "self normaliedd bound for vector-valued martingales" in [ and shows that f(c. over-estimates r(c, j) and converges to r(c,j).
Lemma 4 Under the Pessmistti-OOpiimiss Algoritlm, LinUCB guarantees that
d+ d
E
Σ
- (((()))))-(((())))))))))))
<1 +
( log
E
(r(c(()..) F(c(t). o(t).
<1.
Based on Lemmas
2
and
we conclude that
Kt(e + T 8)
K(1 g)
dd+
((T))
+ 2
( log
(dd
Vi
V
By choosing & = K0775
and V, 0.25
we have
3
vor
Kiler + +et)
6)
60K3
c 2k V
1/V
&
and
$
K0.25
V2
83
which yields the regret bound
60K33
4V6Ku.73
V
d
R(T)
+ 2 V (
log
53
d
4.2 Constraint Violation Bound
According to the dynamic defined in we have
(T (
where we used the fact (0)) O. This implies the constraint violation can be bounded as follows:
((T)
(T 1)]
(19)
Next, we introduce a lemma on the upper bound of (T) Define r' the first time such that 6,' & 6/2, that is, 6 6/2, V1 T'.
Lemma For any time T [T]
such that 2 7', ie., er & 6/2, we have
E (T) VKK
48K² log
16K
+ 2K 4(V, K(1 +2)) +
KK Σ c
8
Based on our choices of e, 0.77
and V, 0.25
V
3
obtain
24 1.5
and
6
4V 4V
F
6K.
82
KK
Note V(T) & K for any & T' Combine Lemma
5 into
19
conclude
4
16
24K
30K
V(() 1.1
log
+
+ 8K
vT)
82
8

---

Numerical Evaluations
In this section, present numerical evaluations of the proposed algorithm, including 1) the con- strained multi-armed bandit (MAB) example studied in [32]; 2) constrained linear bandit example based on healthcare dataset. We briefly report the setting and results due the page limit. More details can be found in [26].
The Constrained MAB Example in 132 To compare with OPA in 32 studied the MAB example in [32] with = 4-arms where the reward and cost distributions are Bernoulli with means A= (0.1, 0.2, 0.4, 0.7) and (0, 0.4, 0.5, 0.2) and the total cost in each round should not exceed 0.5. The results are presented in Figure 2 where we can see that our algorithm has sigmificant lower regret than that under OPA while the cost constraint is satisfied under both algorithms.
240
64-
330
133
61-
Ocdmal Threshols
Optimal
03:
(a) Regret
(b) Reward
(c) Cost
Figure 2: Our Algorithm versus OPA 32
Constrained linear bandits for inpatient flow routing: We also evaluated our algorithm with a real-world dataset inpatient flow routing, where incoming patients have different features (context) such as age, gender, medical history, etc, and incur different amounts of "rewards" when being assigned to different wards (actions). We considered three types of constraints: capacity, fairesss, and resource. We chose different learning horizons. The regrets and constraint violations at the end of the horizon are summarized in Table which shows that our algorithm achieves low regret and zero violation. This experiment also confirms that our algorithm guarantees the anytime cumulative constraints.
2,500
10,000
22,500
40,000
62,500
Regret
24.38
51.89
74.38
90.39
106.82
Largest constraint violation of the three types
0
0
0
0
Table I: Regret and Constraint Violations under Our Algorithm for Inpatient Flow Routing
6 Conclusions and Extensions
In this paper, study stochastic linear bandits with general anytime cumulative constraints. We develop a pessimisticoopimmisiic algorithm that is computationally efficient and has strong guarantees on both regret and constraint violations. We conclude this paper by mentioning an extension on the case where the cost signals W(()) A(t)) are revealed after action A(t) is taken. However, assume the costs can be linearly parameterized as in (32), i.e. (c(t)), A(t)) (Mo, (c,,)) + E(t), where vi(c c, 1) Rd is a feature vector, μl E Rd is an unknown underlying vector, and g(t) is a zero-mean random variable. In this case, we also obtain an estimate W (c((),.) of (c(tt). with LinUCB and replace W (c(()..j) with (c(t), in the steps Max Value and Dual Update in the Pessimisitic-Opiiiis Algorithm. This variation of
Algorithm has a similar regret and constraint violation guarantees in Theorem 2 (the details are 26)).
Theorem 2 (Informal) With linear costs as in 132,, variation of our algorithm achieves R(T) δ (d d') for any T [T] and ((r)= = 0 for 2 r"
64 log" T
Acknowledgment: This work has been supported in part by NSF 687, CNS-2002608 and CN5-2152657.
10

---

References
[1] Yasin Abbasi-yadkori, Dávid Pál. and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems 24, 2011.
[2] Naoki Abe and Philip M. Long. Associative reinforcement learning using linear probabilistic concepts. In Int. Conf. Machine Learning (ICML), 1999.
[3] Shipra Agrawal and Nikhil Devanur. Linear contextual bandits with knapsacks. Advances Neural Information Processing Systems (NeurIPS), 2016.
[4] Shipra Agrawal and Nikhil R. Devanur. Bandits with concave rewards and convex knapsacks. In Proceedings of the Fifteenth ACM Conference on Economics and Computation. Association for Computing Machinery, 2014.
[5] Shipra Agrawal, Nikhil R. Devanur, and Lihong Li. An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives. In Proc. Conf. Learning Theory (COLT), 2016.
[6] Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. Linear stochastic bandits under safety constraints. In Advances Neural Information Processing Systems (NeurIPS), pages 9256-9266, 2019.
[7] P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. Gambling in a rigged casino: The adversarial multi-armed bandit problem. In Proceedings of IEEE 36th Annual Foundations of Computer Science, 1995.
[8] Peter Auer. Using confidence bounds for exploitation-exploaaiio trade-offs. Jraueolffs.Joumal of Machine Learning Research, 3:397-422, March 2003.
[9] Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knap- sacks. J. ACM, 2018.
[10] Ashwinkumar Badanidiyuru, John Langford, and Aleksandrs Slivkins. Resourceful contextual bandits. In Proc. Conf. Learning Theory (COLT), 2014.
[11] Semih Cayci, Atilla Eryilmaz, and R Srikant. Budget-constrained bandits over general cost and reward distributions. In Proceedings of Machine Learning Research, volume 108, pages 4388-4398, 26-28 Aug 2020.
[12] Yifang Chen, Alex Cuellar, Haipeng Luo, Jignesh Modi, Heramb Nemlekar, and Stefanos Nikolaidis. Fair contextual multi-armed bandits: Theory and experiments. In Proceedings of Machine Learning Research, 2020.
[13] Wei Chu, Lihong Li. Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, 2011.
[14] Richard Combes, Chong Jiang, and Rayadurgam Srikant. Bandits with budgets: Regret lower bounds and optimal algorithms. Proc. Ann. ACM SIGMETRICS Conf., 43(1):245-22) 257, 2015.
[15] Varsha Dani, Thomas Hayes, and Sham Kakade. Stochastic linear optimization under bandit feedback. In Proc. Conf. Learning Theory (COLT), 2008.
[16] Rémy Degenne, Han Shao, and Wouter Koolen. Structure adaptive algorithms for stochastic bandits. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 1443-2455 PMLR, 13-18 Jul 2020.
[17] Kris Johnson Ferreira, David Simchi-Levi, and He Wang. Online network revenue management using Thompson sampling. Operations Research, 6666))1586-1602 1602, 2018
[18] Sébastien Gerchinovitz and Tor Lattimore. Refined lower bounds for adversarial bandits. In Advances Neural Information Processing Systems (NeurIPS), 2016.
[19] Abbas Kazerouni, Mohammad Ghavamzadeh, Yasin Abbasi Yadkori, and Benjamin Van Roy. Conservative contextual linear bandits. In I. Guyon, U. V. Luxburg, Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30, 2017.
[20] Kia Khezeli and Eilyan Bitar. Safe linear stochastic bandits. Proceedings of the AAAI Conference on Artificial Intelligence, 14:10202-10209 04 2020.
11

---

[21] Johannes Kirschner, Tor Lattimore, Claire Vernade, and Csaba Szepesvári. Asymptotically optimal information-directte sampling. Arxiv preprint arX14:2011.05944, 2021.
[22] T.L. Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 1985.
[23] John Langford and Tong Zhang. The epoch-greedy algorithm for multi-armed bandits with side information. In Advances Neural Information Processing Systems (NeurIPSS, 2008.
[24] Li, Liu, and B. Ji. Combinatorial sleeping bandits with faimess constraints. In Proc. IEEE Int. Conf. Computer Communications (INFOCOM), pages 1702-1710, 2019.
[25] Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. A contextual -andextual-bandit approach to personalized news article recommendation. Proc. Int. Conf. World Wide Web (WWW), page 661-670, 2010.
[26] Xin Liu, Bin Li, Pengyi Shi, and Lei Ying. An efficient pessimistic-opimmisiic algorithm for stochastic linear bandits with general constraints. arXiv preprint arXiv:2102.05295, 2021.
[27] Mehrdad Mahdavi, Rong Jin, and Tianbao Yang. Trading regret for efficiency: Online convex optimization with long term constraints. Journal of Machine Learning Research, 13(81): (:203) 2528, 2012.
[28] Shie Mannor, John N. Tsitsiklis, and Jia Yuan Yu. Online learning with sample path constraints.
J. Mach. Learn. Res., 10:569-594 June 2009.
[29] Ahmadreza Moradipari, Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. Safe linear thompson sampling. arXiv preprint arXiv:/911.00 1.02156, 2019.
[30] Ahmadreza Moradipari, Christos Thrampoulidis, and Mahnoosh Alizadeh. Stage-wise con- servative linear bandits. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 11191-11201. Curran Associates, Inc., 2020.
[31] Michael J. Neely. Stochastic network optimization with application to communication and queueing systems. Synthesis Lectures on Communication Networks, 3(1):1-211, 2010.
[32] Aldo Pacchiano, Mohammad Ghavamzadeh, Peter Bartlett, and Heinrich Jiang. Stochastic bandits with linear constraints. arXiv preprint arXiv:2006. 10185, 2020.
[33] Paat Rusmevichientong and John N. Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395 2010.
[34] R. Srikant and Lei Ying. Communication Networks: An Optimization, Control and Stochastic Networks Perspective. Cambridge University Press, 2014.
[35] Andrea Tirinzoni, Matteo Pirotta, Marcello Restelli, and Alessandro Lazaric. An asymptotically optimal primal-dual incremental algorithm for contextual linear bandits. In nips, volume 33, pages 1417-1427, 2020.
[36] Ilnura Usmanova, Andreas Krause, and Maryam Kamgarpour. Safe convex learning under uncertain constraints. Proceedings of Machine Learning Research. PMLR, 2019.
[37] Christopher J. C. H. Watkins and Peter Dayan. Q-learning. In Machine Learning, pages 279-292, 1992.
[38] Xiaohan Wei, Hao Yu, and Michael J. Neely. Online primal-dual mirror descent under stochastic constraints. Proc. Ann. ACM SIGMETRICS Conf., 4(2), June 2020.
[39] Michael Woodroofe. A one-armed bandit problem with a concomitant variable. Journal of the American Statistical Association, 74(368):79--806 1979.
[40] Huasen Wu, R. Srikant, Xin Liu, and Chong Jiang. Algorithms with logarithmic sublinear regret for constrained contextual bandits. In Advances Neural Information Processing Systems (NeurIPS), 2015.
[41] Hao Yu and Michael J. Neely. A low complexity algorithm with of (T) regret and o(1) constraint violations for online convex optimization with long term constraints. Journal of Machine Learning Research, 21(1):1-24, 2020.
[42] Hao Yu, Michael Neely, and Xiaohan Wei. Online convex optimization with stochastic constraints. In Advances Neural Information Processing Systems (NeurIPS), page 1427-1437, 2017.
12


Reviews:
[{"review_id": "zRbAP9Pr4Cj", "reviewer": "Reviewer_1DcG", "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "*Main Comments*\n- 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. \n- 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. \n- 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]. \n\n*Details*\n- 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. \n- How does the algorithm set the Slater constant $\\delta$? Is the safe action known to the algorithm in advance?\n- 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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "ZMaFt8K93k", "reviewer": "Reviewer_1dmt", "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).", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "--Originality:\nWhile 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.\n\n--Quality:\nThis submission is technically sound, all the claims are supported.\n\n--Clarity: \nThis paper is well-written with clear intuition explanation and rigorous proof.\n\n--Significance:\nThe results are meaningful and some analysis techniques including dual updates and the connection to Slater's constant are inspiring. \n\n--Question: \nI 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.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "Uj4908Cxx_V", "reviewer": "Reviewer_nU53", "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'.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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: \n\n(i) Insufficient reference to related works.\nFirst, 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...) \n* Khezeli, K. and Bitar, E. (2019). Safe linear stochastic bandits. arXiv preprint arXiv:1911.09501\n* Kazerouni, A., Ghavamzadeh, M., Abbasi, Y., and Van Roy, B. (2017). Conservative contextual\nlinear bandits. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S.,\nand Garnett, R., editors, Advances in Neural Information Processing Systems 30, pages 3910–3919.\nCurran Associates, Inc.\n* Moradipari, Ahmadreza, Christos Thrampoulidis, and Mahnoosh Alizadeh. \"Stage-wise Conservative Linear Bandits.\" Advances in Neural Information Processing Systems 33 (2020).\n* 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)\n* Moradipari, Ahmadreza, et al. \"Safe linear thompson sampling.\" arXiv preprint arXiv:1911.02156 (2019).\n\n(ii) Comparison to related works. \nThe 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.\nLines 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. \n\n(iii) Motivation.\nWhat is the motivation behind the formulation in (2)? Can you provide concrete examples elaborating on the potential applications on \"safety, fairness, and budget constraints\"? \n\nIn addition to the points above:\n(iv) Simulation results might help the reader better understand the algorithm's operation\n(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?\n(vi) Intuitively knowledge that the constraints have specific structure (eg linear) should affect performance. How is this reflected in the bounds? \n\n\n===============\nIncrease score to 5 after rebuttal. See discussion.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations of the model/setting/algorithm/analysis are not clearly discussed", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Jbijy6OsYKA", "reviewer": "Reviewer_DVmW", "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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. \n(1)\tThe 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. \n(2)\tBecause 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].   \n(3)\tThe 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.  \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No, the authors have not addressed the limitations. Please see my comments in the main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "2Uq8LWSTDxN", "reviewer": "Reviewer_WupD", "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.\n\nThe 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.\n\nAfter 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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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.\n\nThe 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.\n\nThe performance guarantee of the algorithm seem very good as the algorithm can provide a O(T) regret with a O(1) constraint violation.\n\nFrom 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.\n\nTo 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:\n- formulating a real problem in this setting is difficult? \n- the hidden constants in the O(.) are too large to make the algorith practical?\n\nAlso, 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?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no direct societal impact foreseen.\n\nThe 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\").\n", "review_text": "", "extra_scores": {"ethical_concerns": "NA. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

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)