An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints
Year: 2022

Abstract:
is the number of constraints, d is the dimension of the reward feature space, and δ is a Slater’s constant; and zero constraint violation in any round τ ą τ 1, where τ 1 is 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.

text: ´´
K0.75 δ ` d ¯? τ ¯
(pseudo) regret in round τ ď T, where K is the number of constraints, d is the dimension of the reward feature space, and δ is a Slater’s constant; and zero constraint violation in any round τ ą τ 1, where τ 1 is 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.

heading: 1 Introduction
text: Stochastic linear bandits have a broad range of applications in practice, including online recommendations, job assignments in crowdsourcing, and clinical trials in healthcare. Most existing studies on stochastic linear bandits formulated them as unconstrained online optimization problems, limiting their application to problems with operational constraints such as safety, fairness, and budget constraints. In this paper, we consider a stochastic linear bandit with general constraints. As in a standard stochastic linear bandit, at the beginning of each round t P rT s, the learner is given a context cptq that is randomly sampled from the context set C (a countable set), and takes an action Aptq P rJs. The learner then receives a reward Rpcptq, Aptqq “ rpcptq, Aptqq ` ηptq, where rpc, jq “ xθ˚, φpc, jqy, φpc, jq P Rd is a d-dimensional feature vector for (context, action) pair pc, jq, θ˚ P Rd is an unknown underlying vector to be learned, and ηptq is a zero-mean random variable. For constrained stochastic linear bandits, we further assume when action Aptq is taken on context cptq, it incurs K different types of costs, denoted by W pkqpcptq, Aptqq. We assume W pkqpc, jq is a random variable with mean wpkqpc, jq that is unknown to the learner. This paper considers general cost functions and does not require wpkqpc, jq to have a linear form like rpc, jq. Denote the action taken by policy π in round t by Aπptq. The learner’s objective is to learn a policy π that maximizes the cumulative rewards over horizon T subject to anytime cumulative constraints:
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
max π
E
«
T ÿ t“1 Rpcptq, Aπptqq
ff
(1) E
«
τ ÿ t“1 W pkq pcptq, Aπptqq
ff
ď 0,@ τ P rT s, k P rKs. (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 is a cumulative constraint over horizon T, including knapsack bandits [10, 9, 3, 4, 5, 17, 11] where the process terminates when the total budget has been consumed; fair bandits where the number of times an action can be taken must exceed a threshold at the end of the horizon [12]; and contextual bandits with a cumulative budget constraint [40, 14]. In these settings, the feasible action set in 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 a threshold [6, 29] or the expected cost of the policy in each round is lower than a threshold [32]. We call them anytime action constraints and anytime policy constraints, respectively.
Our constraint in the form of (2) is an anytime cumulative constraint, i.e., it imposes a cumulative constraint in every round. This anytime cumulative constraint is most similar to the anytime policy constraint in [32] because the average cost of a 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 a cumulative constraint on actions over many rounds (like ours). Furthermore, when our anytime cumulative constraint (2) is satisfied, it is guaranteed that the time-average cost is below a threshold in every round.
In summary, our anytime cumulative constraint is stricter than a cumulative constraint over fixed horizon T but is less restrictive than anytime action constraint in [6, 29]. Figure 1 provides a conceptual description of the relationship between these different forms of constraints.
Main Contributions
This paper presents a pessimistic-optimistic algorithm based on the primal-dual approach in optimization for the problem defined in (1)-(2). The algorithm is efficient in two aspects. First, the algorithm yields Õ ´´ K0.75 δ ` d ¯? τ ¯
regret in round τ ď T and achieves zero constraint violation in any round τ ą τ 1 for a constant τ 1 independent of horizon T . Second, the algorithm is computationally efficient.
For computational efficiency, the design of our algorithm is based on the primal-dual approach in optimization. The computation of the primary component is similar to unconstrained stochastic linear bandits [15, 33, 25, 1, 13]. The dual component includes a set of Lagrangian multipliers that are updated in a 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.
For constraint violation, our algorithm guarantees that for any τ ą τ 1, the constraint holds with probability one. In other words, after a constant number of rounds, the constraint is always satisfied. This is in contrast to prior works [32, 6], where anytime constraints are proven to hold over horizon T with probability 1´ χ for a constant χ. In other words, the anytime constraints may be violated with probability χ, and it is not clear how often they are violated when it happens. Furthermore,
beyond mean cost constraints considered in (2) and in [32, 6], we prove that a sample-path version of constraint (2) holds with probability 1´O ´ e´ δ ? τ 50K2.5 ¯ in round τ under our algorithm.
To summarize, our algorithm is computationally efficient and provides strong guarantees on both regret and constraint violations. Additionally, our cost function is in a 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 [2, 8] are a special class of contextual bandits [39, 23], which generalize multi-armed bandits [22]. Besides [32], [12] considered an adversarial contextual bandit with anytime policy constraint representing fairness. The proposed algorithm has Õp a
|C|JT q regret when the context distribution is known to the learner; otherwise it has Õp a |C|JT q regret and Õp a
|C|T q 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 Õp ? T q regret and Õp ? T q constraint violation. Recent work studied unconstrained structured bandits and proposed primal-dual approach based on asymptotically lower bound problem in bandits [21, 35, 16]. However, our algorithm is different from them in three aspects. Our primal component is a greedy algorithm instead of a (sub-)gradient algorithm (as in [35]). Our dual component does not solve a best response problem, which is a constrained optimization problem as in [21, 16]. Our analysis is based on the Lyapunov-drift analysis for queueing systems, e.g., we establish a bound on the exponential moment of the dual variable, which is not present in [21, 35, 16]. It is also worth mentioning that [20, 19, 30] studied “conservative” bandits which require that the reward or the cumulative reward exceeds a threshold at each step. Another line of related work is online convex optimization with constraints, studied in [28, 27, 41, 42, 38, 36], where online primal-dual with proximal regularized algorithms have been proposed to achieve Op ? T q regret and Op1q violation for static constraints in [41] and Op ? T q violation for stochastic constraints in [42] .
Notation. fpnq “ Õpgpnqq denotes fpnq “ Opgpnqlogknq with k ą 0; rN s denotes the set t1, 2, ¨ ¨ ¨ , Nu; x¨, ¨y denotes the inner product; p¨q: denotes the transpose of a vector or a matrix; || ¨ || “ || ¨ ||2, and ||x||Σ “ ? x:Σx.

heading: 2 A Pessimistic-Optimistic Algorithm
text: We consider a stochastic linear bandit over horizon T 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 (1)-(2). To address the challenges on the unknown reward and cost in constraint, as well as the anytime cumulative constraints, we develop a pessimistic-optimistic algorithm based on the primal-dual approach for constrained optimization. We first give out the intuition of the 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:
max x
ÿ
cPC,jPrJs pcrpc, jqxc,j (3)
s.t. ÿ
jPrJs xc,j “ 1, xc,j ě 0,@c P C, (4)
ÿ
cPC,jPrJs pcw
pkqpc, jqxc,j ` ď 0, @k P rKs, (5)
where xc,j can be viewed as the probability of taking action j on context c, and pc is the probability that context c is selected in each round. We will discuss in further details the importance of the tightness constant in Section 4. The Lagrangian of the problem above is
max x: ř
j xc,j“1,xc,jě0
ÿ
c,j
pcrpc, jqxc,j ´ ÿ
k
λpkq
¨
˝
ÿ
cPC,jPrJs pcw
pkqpc, jqxc,j `
˛
‚, (6)
where λpkq is the Lagrange multiplier associated with the kth constraint in (5). Fixing the values of the Lagrange multipliers, solving the optimization problem is equivalent to solving |C| separate subproblems (7), one for each context c, because the optimization variables x are coupled through j only:
max x: ř j xc,j“1,xc,jě0 pc
˜
ÿ
j
rpc, jqxc,j ´ ÿ
k
λpkq
˜
ÿ
j
wpkqpc, jqxc,j
¸¸
. (7)
Since the problem above is a linear programming, one of the optimal solutions is xc,j “ 1 for j “ j˚ and xc,j “ 0 otherwise, where
j˚ P arg max j rpc, jq ´
ÿ
k
λpkqwpkqpc, jq (8)
and a tie can be broken arbitrarily. If we call rpc, jq ´ ř k λ pkqwpkqpc, jq the action-value of context c, then the solution for fixed values of Lagrange multipliers is to choose an 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 a solution according to (8) include: (i) both rpc, jq and wpkqpc, jq are unknown, and (ii) the optimal Lagrange multipliers λpkq are also unknown. To overcome these challenges, we develop a pessimistic-optimistic algorithm that
• Uses LinUCB to estimate rpc, jq based on its linear structure. • Uses observed W pkqpcptq, jq to replace wpkqpcptq, jq at each round t. • Uses the following function to dynamically approximate the Lagrange multipliers (Xjptq “ 1 if Aptq “ j; otherwise Xjptq “ 0):
Qpkqpt` 1q “
»
–Qpkqptq ` ÿ jPrJs W pkqpcptq, jqXjptq ` t
fi
fl
`
,@k.
In other words, we increase its value when the current cost exceeds the current “budget,” and decrease it otherwise. Therefore, Qpkqptq keeps track of the cumulative constraint violation by round t.
• We further add a scaling parameter 1{Vt to Qpkqptq, i.e. Qpkqptq{Vt, to approximate λpkq. With a carefully designed Vt, 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 our algorithm. This algorithm takes the following information as input at the beginning of each round t: (i) historical observations
Ft´1 “ tcpsq, Apsq, Rpcpsq, Apsqq,W pkqpcpsq, ApsqqusPrt´1s,kPrKs,
(ii) current observations cpsq and tW pkqpcpsq, jqukPrKs,jPrJs, and (iii) system parameters: the feature map tφpc, jqucPC,jPrJs, time horizon T, and a pre-set constant δ. In the analysis of our algorithm, we will reveal the connection of this constant δ with Slater’s condition. The algorithm outputs the action in each round, observes reward Rpcptq, Aptqq, makes updates, and then moves to the next round t` 1.

heading: A Pessimistic-Optimistic Algorithm
text: Initialization: Qpkqp1q “ 0, B1 “ tθ|||θ||Σ0 ď ? β1u,Σ0 “ I and ? β1 “ m` ? 2 log T .
For t “ 1, ¨ ¨ ¨ , T,
• Set: Vt “ δK0.25 b 2t 3 and t “ K 0.75 b 6 t .
• LinUCB (Optimistic): Use LinUCB to estimate rpcptq, jq for all j : r̂pcptq, jq “ mint1, r̃pcptq, jqu with r̃pcptq, jq “ max
θPBt xθ, φpcptq, jqy.
• MaxValue: Compute pseudo-action-value of context cptq for all action j, and take the action Aptq “ j˚ with the highest pseudo-action-value, breaking a tie arbitrarily
j˚ P arg max j r̂pcptq, jq ´ 1
Vt
ÿ
k W pkqpcptq, jqQpkqptq loooooooooooooooooooooooomoooooooooooooooooooooooon
pseudo action value of pcptq, jq
.
• Dual Update (Pessimistic): Update the estimates of dual variables Qpkqptq as follows:
Qpkqpt` 1q “ « Qpkqptq ` ÿ
j
W pkqpcptq, jqXjptq ` t
ff`
,@k. (9)
• Confidence Set Update: Update Σt, θ̂t, βt`1 and Bt`1 by the received reward Rpcptq, j˚q :
Σt “ Σt´1 ` φpcptq, j˚qφ:pcptq, j˚q, θ̂t “ Σ´1t t ÿ
s“1 φpcpsq, ApsqqRpcpsq, Apsqq,
a
βt`1 “ m`
d
2 log T ` d log ˆ d` t d ˙ , Bt`1 “ tθ | ||θ ´ θ̂t||Σt ď a βt`1u.
The complexity of our algorithm is similar to LinUCB. The additional complexity is proportional to the number of constraints (for updating Qpkq), and it is much lower than OPLB in [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 wpkqpc, jq, hence, we do not need to make any specific assumption on wpkqpc, jq.

heading: 3 Main Results: Regret and Constraint Violation Bounds
text: To understand the performance of a 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.

heading: 3.1 Baselines and Assumptions
text: Regret baseline: We consider the following optimization problem:
max x
ÿ
cPC,jPrJs pcrpc, jqxc,j (10)
s.t. ÿ
jPrJs xc,j “ 1, xc,j ě 0,@c P C, (11)
ÿ
cPC,jPrJs pcw
pkqpc, jqxc,j ď 0, @k P rKs. (12)
Constraint violation baseline: We choose zero (no violation) as our baseline.
It worth noting the baseline we use in the regret analysis is derived from relaxed cumulative constraints instead of anytime cumulative constraints in 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, our regret analysis is with respect to the best (the most relaxed) baseline.
We make the following assumptions for all the results present in this paper.
Assumption 1 The context cptq are i.i.d. across rounds. The mean reward rpc, jq “ xθ˚, φpc, jqy P r0, 1s with ||φpc, jq|| ď 1, ||θ˚|| ď m for any c P C, j P rJs. ηptq is zero-mean 1-subGaussian conditioned on tFt´1, Aptqu.
Assumption 2 The costs in the constraints satisfy |W pkqpc, jq| ď 1. Furthermore, we assume tW pkqpc, jquTt“1 are i.i.d. samples for given c and j.
Assumption 3 (Slater’s condition) There exists δ ą 0 such that there exists a feasible solution x to optimization problem (10)-(12) that guarantees ř
cPC,jPrJs pcw pkqpc, jqxc,j ď ´δ,@k P rKs. We
assume δ ď 1 because if the condition holds for δ ą 1, it also holds for δ “ 1.
We call δ Slater’s constant because it comes from Slater’s condition in optimization – this is the constant used as an input of our algorithm. This constant plays a similar role as the cost of a safe action in [6, 32]. In fact, a safe action guarantees the existence of a Slater’s constant, and we can estimate the constant by running the safe action for a period of time. However, the existence of a Slater’s constant does not require the existence of a 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 a feasible solution that is not necessarily optimal.
The next lemma shows that the optimal value of (10)-(12) is an upper bound on that of (1)-(2). The proof of this lemma can be found in [26].
Lemma 1 Assume tcptqu are i.i.d. across rounds, and tRpc, jqu and tW pkqpc, jqu are i.i.d. samples given action j and context c. Let π˚ be the optimal policy to problem (1)-(2) and x˚ be the solution to (10)-(12) with entries tx˚c,jucPC,jPrJs. We have
E
»
–
T ÿ
t“1
ÿ
jPrJs Rpcptq, jqXπ
˚
j ptq
fi
fl ď T ÿ cPC,jPrJs pcrpc, jqx˚c,j .
The baseline problem (10)-(12) is the same as the one presented in Section 2 except that the tightness constant “ 0 here. Any feasible solution for the tightened problem in Section 2 is a feasible solution to the baseline problem. Under Slater’s condition, when ă δ, the tightened problem also has feasible solutions.

heading: 3.2 Regret and Constraint Violation Bounds
text: Given the baselines above, we now define regret and constraint violation.
Regret: Given policy π, we define the (pseudo)-regret of the policy to be
Rpτq “τ ÿ cPC,jPrJs pcrpc, jqx˚c,j ´ E
»
–
τ ÿ
t“1
ÿ
jPrJs Rpcptq, jqXπj ptq
fi
fl . (13)
Constraint violation: The constraint violation in round τ is defined to be
Vpτq “ ÿ
kPrKs
¨
˝E
»
–
τ ÿ
t“1
ÿ
jPrJs W pkqpcptq, jqXπj ptq
fi
fl
˛
‚
`
. (14)
Note that the operator p¨q` “ maxp¨, 0q is imposed so that different types of constraint violations will not be canceled out.
Theorem 1 Under Assumptions 1-3, the pessimistic-optimistic algorithm achieves the following regret and constraint violations bounds for any τ P rT s :
Rpτq ď60K 3 δ3 ` 4
? 6K0.75 ? τ
δ ` 2`
d
8dτβτ pT´1q log ˆ d` τ d ˙ ,
Vpτq ďK1.5 ˆ 48K2
δ log
ˆ
16
δ
˙
` 24K 1.5 δ2 ` 30K 1.5 δ ` 8K ´ ? τ
˙`
.
where a βτ pT´1q “ m` a 2 log T ` d log p1` τ{dq.
We make a few important observations from our theoretical results. First, for the reward regret, we observe
Rpτq “ Õ ˆˆ K0.75
δ ` d
˙? τ ˙ .
So the regret is independent of the number of contexts, action space rJs and the dimension of cost functions W pkqp¨, ¨q. 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 δ.
Second, for the constraint violation, we observe
Vpτq “ # Õ ´ K3.5 δ ` K3 δ2 ¯ τ ď τ 1 “ Õ ´ K4 δ2 ` K3 δ4 ¯
0 otherwise . (15)
That is, the constraint violation is independent of horizon T and becomes zero when τ ą τ 1. The constraint violation, however, has a strong dependence onK and δ when τ ď τ 1. 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 on Slater’s constant. Both the regret and constraint violation increase in δ. To see the intuition, note that δ determines the size of the feasible set for the optimization problem. A larger δ implies a larger feasible set, so it is easier to find a 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 in Theorem 1 are sharp because the regret boundRpT q matches the instance-independent regret Ωp ? T q in multi-armed bandit problems without constraints [7, 18] up to logarithmic factors. Furthermore, zero constraint violation is the best possible. Therefore, the bounds are sharp up to logarithmic factors in terms of horizon T . It is not clear whether these bounds are sharp in terms of K, d, and δ, which are interesting open questions.

heading: 3.3 A High Probability Bound on Constraint Violation
text: 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 a sample-path version of the constraints to be satisfied. It turns out that our algorithm provides a high probability guarantee on that as well. The proof can be found in [26].
Corollary 1 The pessimistic-optimistic algorithm guarantees that for any τ ě κK 5
δ2
` log ` K δ ˘˘2 ,
where κ is a positive constant independent of τ, K, δ and d,
P
¨
˝
τ ÿ
t“1
ÿ
jPrJs W pkqpcptq, jqXjptq ą 0
˛
‚“ O ´ e´ δ ? τ 50K2 ¯ .

heading: 4 Proof of Theorem 1
text: We first explain the intuition behind the main result. Recall that the algorithm selects action j˚ such that
j˚ P arg max j
˜
r̂pcpτq, jq ´ 1 Vτ ÿ
k
W pkqpcpτq, jqQpkqpτq ¸ ,
and Vτ “ Op ? τq. Therefore, when Qpkqpτq “ op ? τq, the reward term dominates the cost term, and our algorithm uses LinUCB to maximize the reward. When Qpkqpτq “ ωp ? τq, the cost term dominates the reward term and our algorithm focuses on reducing Qpkq. Slater’s condition implies that there exists a policy that can reduce Qpkq by a constant (related to δ) in each round. Therefore, the algorithm takes Õp ? τq rounds to reduce Qpkq to op ? τq, which may add Õp ? τq to the regret
during this period. The argument above also implies that Qpkqpτq “ Op ? τq. Then, because
E
»
–
τ ÿ
t“1
ÿ
jPrJs W pkqpcptq, jqXjptq
fi
fl ď E ” Qpkqpτ ` 1q ı ´ τ ÿ
t“1 t.
we can further bound the constraint violation at time τ to be a constant or even zero via the bound on ErQpkqpτ ` 1qs and a proper choice of t.

heading: 4.1 Regret Bound
text: Now consider the regret defined in (13) and define x t,˚ to be the optimal solution to the tightened problem (3)-(5) with “ t. We obtain the following decomposition by adding and subtracting corresponding terms:
Rpτq paq“ τ ÿ
c,j
pcrpc, jqx˚c,j ´ E « τ ÿ
t“1
ÿ
j
rpcptq, jqXjptq ff
“ τ ÿ
t“1
ÿ
c,j
pcrpc, jq ` x˚c,j ´ x t,˚ c,j ˘
looooooooooooooooomooooooooooooooooon
t-tight
`E « τ ÿ
t“1
ÿ
j
prpcptq, jq ´ r̂pcptq, jqqx t,˚cptq,j
ff
looooooooooooooooooooooooomooooooooooooooooooooooooon
reward mismatch
` E « τ ÿ
t“1
ÿ
j
´ r̂pcptq, jqx t,˚cptq,j ´ r̂pcptq, jqXjptq ¯
ff
´ τ ÿ
t“1
Kp1` 2t q Vt
loooooooooooooooooooooooooooooooooooooooooomoooooooooooooooooooooooooooooooooooooooooon
Lyapunov drift
(16)
` τ ÿ
t“1
Kp1` 2t q Vt looooooomooooooon
accumulated tightness
`E « τ ÿ
t“1
ÿ
j
pr̂pcptq, jq ´ rpcptq, jqqXjptq ff
looooooooooooooooooooooooomooooooooooooooooooooooooon
reward mismatch
, (17)
where paq holds because the random reward is revealed after action Aptq is taken so the noise is independent of the action. We next present a sequence of 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-drift analysis [31, 34]. We consider a Lyapunov function Lptq “ ř
kQ pkqptq and show that maximizing the pseudo action value in our
algorithm (MaxValue step) is equivalent to maximizing the following “reward minus Lyapunov drift”
Vt ÿ
jPrJs r̂pcptq, jqXjptq ´ pLpt` 1q ´ Lptqq.
Therefore, our algorithm outperforms a static policy x tcptq,j and results in the following lower bound
VtE
»
–
ÿ
jPrJs r̂pcptq, jqXjptq
fi
fl´ ErLpt` 1q ´ Lptqs ě Vt ÿ
jPrJs r̂pcptq, jqx tcptq,j ´Kp1` 2 t q. (18)
Apply the telescoping sum on (18) provides an upper bound on (16) in Lemma 2.
Lemma 2 Under the Pessimistic-Optimistic Algorithm, we have
E
»
–
τ ÿ
t“1
ÿ
jPrJs r̂pcptq, jq
´ x tcptq,j ´Xjptq ¯ ˇ ˇ ˇ Hptq “ h
fi fl´ τ ÿ
t“1
Kp1` 2t q Vt ď τ ÿ
t“1
Ktp t ` 2t qIp t ą δq Vt .
Next, we present Lemma 3 which establishes an upper bound on the t-tight term by comparing the optimal solution to the original baseline problem and that to its t´tightened version. It is based on the intuition that adding t-tightness to the feasible region only incurs Op tq loss in the reward.
Lemma 3 Under Assumptions 1-3, we can bound the difference between the baseline optimization problem and its tightened version:
τ ÿ
t“1
ÿ
c,j
pcrpc, jq ` x˚c,j ´ x t,˚ c,j ˘
ď τ ÿ
t“1
t δ .
Finally, we present Lemma 4 that provides an upper bound on the reward mismatch terms. The proof is based on “self-normalized bound for vector-valued martingales” in [1] and shows that r̂pc, jq over-estimates rpc, jq and converges to rpc, jq.
Lemma 4 Under the Pessimistic-Optimistic Algorithm, LinUCB guarantees that
E
«
τ ÿ
t“1
ÿ
j
pr̂pcptq, jq ´ rpcptq, jqqXjptq ff ď1`
d
8dτβτ pT´1q log ˆ d` τ d ˙ ,
E
«
τ ÿ
t“1
ÿ
j
prpcptq, jq ´ r̂pcptq, jqqx t,˚cptq,j
ff
ď1.
Based on Lemmas 2, 3, and 4, we conclude that
Rpτq ď τ ÿ
t“1
Ktp t ` 2t qIp t ą δq Vt ` τ ÿ
t“1
t δ `
τ ÿ
t“1
Kp1` 2t q Vt ` 2`
d
8dτβτ pT´1q log ˆ d` τ d ˙ .
By choosing t “ K0.75 b 6 t and Vt “ δK 0.25 b 2t 3 , we have
τ ÿ t“1 t ď 2K0.75 ? 6τ , τ ÿ t“1 1{Vt ď
? 6τ
K0.25 , and
τ ÿ
t“1
Ktp t ` 2t qIp t ą δq Vt ď 60K 3 δ3 ,
which yields the regret bound
Rpτq ď60K 3 δ3 ` 4
? 6K0.75 ? τ
δ ` 2`
d
8dτβτ pT´1q log ˆ d` τ d ˙ .

heading: 4.2 Constraint Violation Bound
text: According to the dynamic defined in (9), we have
Qpkqpτ ` 1q ě τ ÿ
t“1
ÿ
j
W pkqpcptq, jqXjptq ` τ ÿ
t“1 t,
where we used the fact Qpkqp0q “ 0. This implies the constraint violation can be bounded as follows:
Vpτq ď ÿ
k
˜
ErQpkqpτ ` 1qs ´ τ ÿ
t“1 t
¸`
. (19)
Next, we introduce a lemma on the upper bound ofQkpτq.Define τ 1 the first time such that τ 1 ď δ{2, that is, τ ą δ{2,@1 ď τ ă τ 1.
Lemma 5 For any time τ P rT s such that τ ě τ 1, i.e., τ ď δ{2, we have
E ” Qpkqpτq ı ď ? K
˜
48K2
δ log
ˆ
16K
δ
˙
` 2K ` 4pVτ `Kp1` 2 τ qq
δ ` τ 1 `
? K
τ 1 ÿ
t“1 t
¸
.
Based on our choices of t “ K0.75 b 6 t and Vt “ δK 0.25 b 2t 3 , we obtain
τ 1 “ 24K 1.5
δ2 and
τ ÿ
t“1
t? K ´ 4Vτ`1 δ ě ? τ ´ 6K.
Note Vpτq ď Kτ 1 for any τ ď τ 1. Combine Lemma 5 into (19), we conclude
Vpτq ďK1.5 ˆ 48K2
δ log
ˆ
16
δ
˙
` 24K 1.5 δ2 ` 30K 1.5 δ ` 8K ´ ? τ
˙`
.

heading: 5 Numerical Evaluations
text: In this section, we present numerical evaluations of the proposed algorithm, including 1) the constrained multi-armed bandit (MAB) example studied in [32]; 2) a constrained linear bandit example based on a healthcare dataset. We briefly report the setting and results due to the page limit. More details can be found in [26].
The Constrained MAB Example in [32]: To compare with OPA in [32], we studied the MAB example in [32] with K “ 4-arms where the reward and cost distributions are Bernoulli with means r̄ “ p0.1, 0.2, 0.4, 0.7q and c̄ “ p0, 0.4, 0.5, 0.2q 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 significant lower regret than that under OPA while the cost constraint is satisfied under both algorithms.
Constrained linear bandits for inpatient flow routing: We also evaluated our algorithm with a real-world dataset on 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, fairness, and resource. We chose different learning horizons. The regrets and constraint violations at the end of the horizon are summarized in Table 1, which shows that our algorithm achieves a low regret and zero violation. This experiment also confirms that our algorithm guarantees the anytime cumulative constraints.

heading: 6 Conclusions and Extensions
text: In this paper, we study stochastic linear bandits with general anytime cumulative constraints. We develop a pessimistic-optimistic 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 pkqpcptq, Aptqq are revealed after action Aptq is taken. However, we assume the costs can be linearly parameterized as in [32], i.e. W pcptq, Aptqq “ xµ˚, ψpc, jqy ` ξptq, where ψpc, jq P Rd is a feature vector, µ˚ P Rd is an unknown underlying vector, and ξptq is a zero-mean random variable. In this case, we also obtain an estimate W̌ pcptq, jq of W pcptq, jq with LinUCB and replace W pcptq, jq with W̌ pcptq, jq in the steps of MaxValue and Dual Update in the Pessimisitic-Optimistic Algorithm. This variation of Pessimisitic-Optimistic Algorithm has a similar regret and constraint violation guarantees in Theorem 2 (the details are in [26]).
Theorem 2 (Informal) With linear costs as in [32], a variation of our algorithm achievesRpτq “ Õ ´
d δ
? τ ` d 4
δ3
¯ for any τ P rT s and Vpτq “ 0 for τ ě τ2 “ O ´ d2
δ4 log 2 T
¯
.
Acknowledgment: This work has been supported in part by NSF CNS-2001687, CNS-2002608 and CNS-2152657.

Review summaries:
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).

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.