Combinatorial Bandits with Linear Constraints: Beyond Knapsacks and Fairness
Authors: Qingsong Liu
Weihang Xu
Siwei Wang
Zhixuan Fang
Venue: NeurIPS 2022 Accept (2022)

Abstract: This paper proposes and studies for the first time the problem of combinatorial multi-armed bandits with linear long-term constraints. Our model generalizes and unifies several prominent lines of work, including bandits with fairness constraints, bandits with knapsacks (BwK), etc.  We propose an upper-confidence bound LP-style algorithm for this problem, called UCB-LP, and prove that it achieves a logarithmic problem-dependent regret bound and zero constraint violations in expectation. In the special case of fairness constraints, we further provide a sharper constant regret bound for UCB-LP. Our regret bounds outperform the existing literature on BwK and bandits with fairness constraints simultaneously. We also develop another low-complexity version of UCB-LP and show that it yields $\tilde{O}(\sqrt{T})$ problem-independent regret and zero constraint violations with high-probability. Finally, we conduct numerical experiments to validate our theoretical results.

Combinatorial Bandits with Linear Constraints:
Beyond Knapsacks and Fairness
Qingsong Liu'*, Weihang Xu Siwei Wang?, Zhixuan Fang
IIIS, Tsinghua University Microsoft Research Shanghai Qi Zhi Institute {liu-qs19, kxww11))0mail tanasiii siweiwangemi crosoft. com
tsinghua. edu.
zf zfang@mail tsinghua. edu. cn
Abstract
This paper proposes and studies for the first time the problem of combinatorial multi-armed bandits with linear long-term constraints. Our model generalizes and unifies several prominent lines of work, including bandits with fairesss constraints, bandits with knapsacks (BwK), etc. We propose an upper-confidence bound LP- style algorithm for this problem, called UCB-LP, and prove that it achieves a logarithmic
regret bound and zero constraint violations expectation. In the special case of fairness constraints, we further provide a sharper constant regret bound for UCB-LP. Our regret bounds outperform the existing literature on BwK and bandits with fairness constraints simultaneously. We also develop another low-complexity version of UCB-LP and show that it yields Õ(VT) problem-independe regret and zero constraint violations with high-probability. Finally, we conduct numerical experiments validate our theoretical results.
Introduction
In this paper, we study the problem of combinatorial bandits with long-term linear constraints. Our model captures important application scenarios like ad placement in online advertising systems [41), real-time traffic scheduling in wireless networks, and task assignment crowdsourcing platforms [29], etc. Although being studied for the first time, model subsumes several well-know problems in the Constrained Multi-Armed Bandit (CMAB) literature, including bandits with knapsacks, bandits with fairness constraints, etc. Details about these problems and how they fit into framework are
provided in Section L.I
Specifically, we consider an agent's online decision problem faced with fixed finite set of N arms labelled 1, 1,2, ..., N, within the time horizon T. At each round (1 S S T), every arm E [N] is associated with random reward fi(t) [o, sampled from time-invariant distribution P. The reward ft(t) and its distribution P. are unknown to the agent a priori. The mean reward of distribution P. is denoted
μa [0. We denote define μ² = maxie[N] μr as the maximum mean reward value of all arms. At the beginning of each round the agent is allowed to pull multiple, but more than arms. At round i, the action taken by the agent is represented by an action vector a(I) = (I)...... (n) E 1) if and only if arm is pulled. The set of all feasible action vectors is defined as = {ala E {0, 1 ||a]], S m). After taking action att), the agent can observe reward from each pulled arm. Summing up the reward from the pulled arms, round the agent receives total reward of R2 = f(t)a,
(Wi,.., ... pN) T E [0, 1 the mean reward vector, and "oN,..,,,))
where (t)
"These authors contribute equally this work. Corresponding author: Zhixuan Fang (zfang @ mail. .si.ggu..ed...cn)
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Beyond the standard combinatorial bandit setting above, we consider that the agent is subject to some constraints g() every round defined as ((((t)) :=
gr (xnggg((((aa (a(())] where gr. 02.9...... .9 R R are linear functions. The goal of the agent is to maximize the accumulated expected reward up the time horizon T, while satisfying the constraints in the long term, i.e.,
T
HHXXX Σ Rr. S.L. Eg(a(() S.
(1)
[-1
(The comparison operator & is coordinate-wise Define OPT(T) as the expected accumulated reward in T rounds of the optimal policy satisfying the long term constraints. The agent's performance is measured in terms of regret and constraint violations defined respectively as
Regret, OPT(Z) B Hi], Vio(T)
Σ g(a(t)))
where the expectation taken w.r.t. the randomness of the reward and algorithm's internal randomness. Consider the following linear programming problem (LP)):
OP = max
a
S.L. g(x) - O, S S 1, |=||| S m.
BERV
T OPTLp. We denote the set of optimal solutions to LP X", and define x' E X as one of these optimal solutions. Following a common approach, we use the optimal randomized policy x' the benchmark in the regret:
4 showed that OPT(T) <
Regrety $ -TOOPT
E Re)= T(,,, x0), E
Re]
(3)
1.1 Representative problems and related works
In this section, we outline several motivating and representative problems which fit into our general formulation and review the literature closely related to them (listed in Table D). Problem-dependent parameters Amin and will be formally defined Scction 2.1
Table I: The comparison between our results and prior closely-related works. In this table, Tmin min; rs. "Single-arm" means m = "I.P" means the algorithm should solve a linear program. "Complexity" refers to the computational-complee
of the algorithm at each round.
ALGORITUM
SETTING
ASSUMPTIONS
REGRET
VIOLATION
COMPLEXITY
KNAPSACKS
[M (RL)
LP
SINGLE-ARN, KNAPSACKS
=1 ONE RESOURCE IK 2) BEST UPTMALLTYY I. PROOR KNOWLEGE ONE RESOUTCE (K
Oiiii K) kg
0
LP
SINOLF-ARM KNAPSACKS
Of log 700
0
L.P
365GLE-MK ENTPSICSS
T
D
"L"""
15
COMPINATORIAL KNAPSACKS
0flig
0
L.P
COMBINATOLIAL FAIRNISS
Tl
o(T)
(1K)
COMBINATOLIAL, FAIRNESS
Oly Oly TogT)
ofT)
COMMINATORIAT, FAIRNESS
Olyy (ilog))
Oly TogT;
SINGLE-ARM, FAIRNESS
mo KINN
O[NA(1 1//4 (ra))))))
60)
((K)
SINGLE ARMM, FAIRNESS
logT))
NIA
0.2)
(THiS WORK) UCR-LPP
COMRINATORIAL,
O(snN log (A/m)))))
(THIS WORK) UCB-LP
COMBINATORIAL, COMBINATORIAL,
Oil]
0:33
(THIS WORK) UCB PLLP
DHIGH (808)
0.3)
Bandits with knapsacks. The BwK (Bandits with Knapsacks) problem with deterministic costs
studied in 18 42 40) assumes that there are K resources consumed over time, each with budgets Bi, BB ... Bx respectively. Every resource E [K] is associated with fixed consumption vector A: = (),,,, Ai.,,.... N,,N) Ry- The agent maximizes the accumulated reward subject to the budget constraints Exem A, a(t) < B,, vi E [K]. One can see that, this problem is equivalent with the special case of our setting where the linear constraint functions have the form g(a(1)) Bx/T)
(AT att) -
The existing BwK literature 0 17 has derived algorithms that achieve the problem-independent regret bounds of the similar order Ö(VKNT). Such order of the regret bound is also obtained

---

for combinatorial setting. However, the problem- dependent regret of BwK with deterministic costs is less explored. [8] achieved one regret bound of O (min(N, K} (N log
with unsatisfying exponential dependence on K and N. They also provide another regret bound of ((minn(N, K})* log 2 with polynomial dependence N, K but require additional assumption by 41 42 28
amm
of the optimal solution of LP being unique. Later [40] improves this regret to O Jox also under the assumption that LP has an unique optimal solution. But their algorithm requires the knowledge of some parameters of the problem instance a priori (characterized by Amin and μ²), which is unpractical. With the "best-armmoppimalltt" assumption, i.e., there is an optimal policy that only pulls one arm, [2] achieved the regret of O(N ..VV.oo log (G(m)) (GLaG is their defined Lagrangian gap) when there is only one resource (K 2), whose practicability is also restricted. Very recently, [15] derives a regret bound of (log"T) for combinatorial setting and one resource constraint, which is the best so far in the area of combinatorial BwK but still sub-optimal in terms Tf
7 obtained logarithmic regrets under different restrictive assumptions, e.g., non-degeneracy of K = 2 (single source) or "best-arm- optimality". [T8 42 showed that it impossible to achieve any woblem-dependentt regret bound of
For BwK problems with stochastic costs, 18
30
o( o(VT) without additional assumptions in general.
studied the problem of bandits with fairness constraints. Under their setting, the agent maximizes the cumulative expected reward, and needs to ensure that each arm E [N] is pulled for at least E (0, 1) fraction of times at the end of rounds. In our model, such fairness constraints are equivalent with the following special kind of linear long-term constraints: g(a(t)) = a(f) where r (ri, (2.,22...,,7
Bandits with fairness constraints. Recently, 22 48
229 first studied the combinatorial (sleeping) bandits with faimess constraints. Their algorithm LFG combines virtual queue technique and UCB learning. LFG yields ((VT) regret and sublinear (o(T)) constraint violations. 20) replaced the UCB learning with Thompson Sampling in LFG and obtained performance guarantees with the same order. Later [48) improved the constraint violations bound to O(VT) with the same regret order by using online convex optimization techniques and RRS rounding. A big advancement is made by recent works [12 39 that they achieve Ollog T') and oflog I') regret bounds, respectively, for MAB (m 1) with fairness constraints based on the modified UCBI algorithm. And [66 achieved a "penalized" regret bound of Ollog T') in the single-arm setting.
Bandits with group fairness. In scenarios like ad-display optimization, the agent is subject the group fairnsss constraint, e.g.. arms belonging to one group should be pulled more frequently than arms belonging to another group (36,, the arm with higher average reward should be pulled more times than the arm with lower average reward [23]. etc. This problem also fits into our formulation of linear constraints. Only problem-dependent regrets of Õ(VT) obtained in related works.
Other related literature. A large body of literature (e.g.. (TO] 45) derived O(log T) regret bounds for unconstrained combinatorial bandits. [22] 24 studied the BwK problem under the adversarial setting. 22 38 3 35| studied constrained linear bandits. Our framework is also related to online
convex optimization with long-term constraints (e.g.. 133 [ 51 50)) where the agent faces several convex constraints and these constraints need to be satisfied in the long term. We remark that, in this setting, the full reward function at each round would be revealed after the decision making, which is in contrast to our setting that we do not have such observation due to the bani-bandit feedback.
1.2 Discussion: significance of linear constraints
In this section, we discuss the significance of generalization to linear constraints. Previous literature on constrained bandits only studies constraints with specific forms, namely, the fairness constraint and the knapsacks constraint, etc. As only require g(.) to be linear, our model not only subsumes both of them as its special cases, but also solves a larger group of constraints, enabling broader applications. For example: 1. Our model for the first time addresses scenarios where both fairness and knapsack constraints exists simultaneously. 2. Our model solves the case of weighted fairesss constraints, i.e., weighted sums of pulls of each arm required to be larger than a threshold: ΣN (T) 2 ryT, where æsy is the j weight of the 2hh arm. In contrast, traditional fairness constraints treat each arm as unweighted and could be seen special case of weight fairness constraints.
In fact, there are many applications where combinatorial bandits with various complicated linear constraints are required. We show some concrete examples as follows. (a) In crowdsourcing, where
3

---

group of workers are assigned with tasks to achieve high accuracy, a set of complex linear constraints occurs: each tasks should have enough workers, while each worker should have fair workload. (b) In network routing where multiple paths (each path consists of series of links) needs to be selected to send the traffic within the time budget and the bandwidth constraints. (c) Case of Internet of Things where set of sensors need to be selected at each round to guarantee the QoS requirement [21] (e.g.. throughout, mean-delay) under budget constraint on data collection cost (e.g., energy consumption).
1.3 Our contributions
Our main contributions summarized below.
(a) We define a general formulation termed combinatorial bandits with linear long-ter constraints. In contrast to previously outlined pieces of work, we consider the problem in its full generality and do not assume or require any prior knowledge the problem instance. We design an upper-confidence bound LP-style algorithm named UCB-LP, and develop novel analytical technique to build relationship between LP solution (distribution support over arms) and "reward allocation", with which we show that UCB-LP guarantees problem-dependen regret of O(mN jox and constraint violation in expectation. To the best of our knowledge, this is the first logarithmic regret bound for bandits with long term linear constraints under the combinatorial setting.
(b) For the special case of fairness constraints, we show that UCB-LP achieves O(1) regret and guarantees zero expected constraint violation at the same time. To the best of our knowledge, both the regret and the constraint violations outperform all existing works on combinatorial bandits with fairness constraints. We also show that UCB-LP has low rumning time of Ó(N) this special case.
(c) To overcome the potentially time-conuuiing LP in UCB-LP, we further develop a low-complexity version of UCB-LP, called UCB-PLLP, since builds the Lagrangian (L.) of UCB-LP and pes- simistically (P) tracks the constraint violations. We show that it yields ((vT) problem-independent regret and guarantees zero constraint violations for any with high-probability. The computa- tional complexity of UCB-PLLP is Ö(N).
2
Main results
In this section, we present our algorithm and corresponding performance analysis for our general formulation. All the proofs of listed lemmas, propositions and corollaries are deferred to the supplementary material. Our experimental results are given in the suppmetary material.
2.1 Preliminary: notations and existing techniques
Notations. For every arm i, define ht,1)) := = (;( as the number of pulls of it at the beginning of round f, and (=(() := P.( Σ (:(T) as its empirical reward estimate at round t. Denote the
feasible region of (2) as = {æ>a [0, 11 ||=l|| S m, g(x) S 03. this paper, for any vector v, we use i to denote its 2th coordinate, For any event E, we use E to denote its negation.
Extreme points and general sub-optimality measure. Note that the feasible region D to LP 2 is convex polytope, and we let B be the set of its extreme points. An extreme point of D is a point in D which does not lie in any open line segment joining two points of D. It is well-known in the theory of LP that extreme points and basic feasible solutions are equivalent, and any LP attains its optimal value an extreme point (6) Recall that x' is an optimal solution to LP (2). and define the sub-optimality gap for any æ E B as A. == (M,, x") (1,, æ). Define Amin = millgEBI,.* Az. Since is finite, Amin well-defined and strictly positive. The same definition of the sub-optimality gap also used in [18.. We note that Amin can be seen as a generalization of the minimum sub-optimality gap in standard MAB problem defined as == minipp 11= pil- Specifically, under the standard MAB setting, m 1, B (ala e (0. 1) [|all, S 1), Amin coincides with A. In this paper, we will state our problem-dependent regret bounds terms of Amin.
2.2 The general algorithm UCB-LP and its performance analysis
Now we introduce our algorithm UCB-LP for combinatorial bandits with long-term linear constraints. UCB-LP is generalization of SemiBwK algorithm [4] to the general linear constraints setting which

---

chooses arms through randomized policy. In our setting, one main challenge is that no super-arm is optimal across all rounds, but there exists an optimal sampling distribution over arms and the intuition behind UCB-LP is to identify such distribution and sampling arms based on it. At each round, UCB-LP consists of two stages. In the first stage, we first compute the truncated UCB estimate
2lne vector (t) e R defined as (f) = min (ts(() (.
} vi E [N]. Then we solve the following
LP and get an optimal solution s<(() E B:
(4) (Note that LP 22 and LP (4) have the same feasible region D, hence the same set of extreme points
max OE
(p((). ar) S.L. g( = 0 S 11 |||||| S m..
B.) Here we require the solved optimal solution sx1) to be an extreme point of LP 4 i.e., æ(t)= e B. In fact, this is naturally satisfied by many LP algorithms, e.g., Simplex Method. Even if the optimal solution of LP not an extreme point, it can be efficiently converted one by tightening some slack 19].
constraints in
The second stage is to construct a distribution sT(-) over with expectation xxt), i.e., Enca Tr(a) a = stt), and sample super-arm a(t) ~ Te. Since xt) E D C Conv(A), such Te exists and can be generated via convex decomposition of (t)). Although there are many random- ized rounding methods with O(N²) running time to achieve this, we show in the supplementary material that computing Ti and sampling a(t) can be finished in O(N log N) time. The idea of sampling arms maintaining the marginal distribution are also used in 13 52). Finally, we pull the arms according to at),, observe the reward value of pulled arms, and update the statistics.
Although motivated by SemiBwK algorithm 41 UCB-LP deals with general linear constraint funetion without any assumptions and our goal is to derive problem-dependent regret bound. Therefore, new techniques have to be developed for the analysis of UCB-LP.
The following theorem provides the generic bounds of regret and constraint violations for UCB-LP.
Theorem UCB-LP satisfies
Regrety = ( mmN log T
(5)
Amin
E[Vio[T)] - O.
(6)
Proof sketch of Theorem 1: Note that (6) is straightforward from LP 4 and the fact that g(-)
is linear. Now we present the main idea of proving (5). To obtain the regret bound, we cannot
directly apply the traditional analysis from bandit community here as we cannot bound h; (t) and the
algorithm might favor sub-optimal arms even if they have already been pulled for M(og T) times due to the structural property of the LP. Instead, we bound the number of times UCB-LE LP fails to yield the optimal policy, i..., xx) & X The most natural idea to achieve this is to bound the number of times xx) उ for every sub-optimal policy τ E B \ X However, such an idea fails in the sense that the resulting bound would scale with [28. which is exponentially large. Addressing this technical challenge is nontrivial and previous works circumvented this problem by assuming special structures (e.g., 18) and [40] assumed X = 1, 42 assumed only one resource and ||=1||, = 1, etc) or using parameters [40] In our proof, we overcome this difficulty directly by handling the case axt) & X with the idea of "regret allocation".
the prior knowledge of some moobemm-dependee
Define w(t) (V (ln
R.()) kn Since the regret only occurs when æ $ X", we claim that x²) S (p((),, att)), (p((), (t)) 2 (p((), xtt) + Agci) and (w, xt)) 2 Amcn/2 /2 all hold with high probability in such case since (ū(t), (t)) 2 (LP (fo x)) 2 (high-prob){j4. x") 2 (()) + Au(1) = (a(()- u()) 2 (high-prob) + (2w, ax()) 2 (high-prob)Aacu = (w, x(1) 2 (high-prob)
With these properties, when x & X", we could allocate the in- curred regret R²- (M, x²) - (H, x(t)]] = Am(1) to every base arm in the following way, and we will argue that this allocation is correct since:
R: =( (4, x())] = Am()) = B((((t) - μ. x(1)) - Ei x,,x") - x(1))
< (high-prob) (()(()))))))))))))))) μt, az a0)) < (high-prob) (2w, x (()) 2E
Σ 21(()) (lnt/h/)))
[E[N]
Thus each arm contributes 2z, (t)
2 Ay(e
to the regret Az())- Next we claim that the sum above
regret allocation all arms is dominated by the arms in the set V = {i: h,(t)
32m 2 Int
}, i.e.
A?
Eie[N (z:(t)
2 ( < Eievc (t.(t)
2ln k,00
which is derived by:
5

---

EEENNIV zi(0
21n1 ()
EiENN/VOO (1(
Smin EIE(NY 22(1) Amin
Amin
Aa(t)
and
EIENN zi(t)y
2imt Ae(
= (w(t), x (t))
Amis)
Therefore, the following total regret decomposition holds with high-probability:
Regretr S 2B
m(0/2h11//:((11aa) & x
[=
(7)
S 1ED
Σ
2100)2ht/hh(00)aaaa x 1E
(h(t)/2tt/hh())))
(eV(
ieV())
Define G(1) (t:iE V(t),, and T; arg c0(() т. Continuing from
we obtain
Regretr S 1E
Σ
(lt)//nt/hh() = 1E
Σ
lnt (1)
S
T
(eV())
iEN tEG(()
IE
The remaining problem is to bound 4 Σ 1z (1) lemma.
which is solved by the following
Lemma 1 (tTT)//(//////) S 33/nnt El +1)
Applying Lemma
yields 4F|DIeN E (t)
2lnt (,
S 12 V 2 (h, +1 s
12 12 / 22 T: in + 1) (Since T. V(T.)) - 12 12Σ EiE(N
In T/ min + 1)
0 mN In T). Putting all things together completes the proof of Theorem
Amin
Proof of Lemma 1: Our proof idea is using the facts (a): 1/v5 S 3(v=+1 VT), * 2 1;
(b): Fly (T,((++1 F1) = F(a.(T)//A(T)) + F-11 + FT((1 (()r)) where F,
(a(()) Then E (n
S VintE (fa 11/b(()))
3v Bor
( Ely (-)) S 3/ (1+ [)]A[] S VintEi
3vintE ET (T 3 +1).
Comparison with previous results. Several previous works (e.g., 18
42
40
39 studying bandits
with long term constraints have also achieved O(log 7') regret bounds. Our regret bound has four major improvements over theirs: (a) Our regret bound has better dependence on Amin and N. (b) Previous regret bounds only apply to the single-armed setting, while ours applies to the combinatorial setting. (c) Our regret bound valid for all linear constraints, while theirs is only valid for specific kind of constraints, either BwK with detereministic costs, or fairness constraints (which are the special cases of linear constraints). (d) Almost all of them require additional assumptions or knowledge of some parameters of the problem instance prior. For example, [18] explicitly admitted that their Jlgarthloaiii regret and the corresponding analysis only valid under the assumption of | = 1. (See Appendix A. and Assumption 9 in their arxiv version.) However, | = 1 does not always hold. When consider BwK problem with only one resource, if there exist arms p. q such that Az Hi, where A; is the amount of resource consumed by arm i if it gets pulled, then LP (2) Ap has non-unique optimal solution, i.e., |x*| * Even consider problem of bandits with fairness constraints, if there exist two arms with the same required probability of being pulled, the optimal solution to LP (2) also may not be unique. Beyond assuming | = 1, the algorithms in 40 still require some prior knowledge of the problem instance (characterized by μ² and Amin). Substantial assumptions including only one resource and -rotiaomotptt are also required (42. On the contrary, we do not require any assumptions and prior knowledge of the problem instance.
Reduction to unconstrained (combinatorial) bandits setting. When there no constraints, i.e., (t) = 0, UCB-LP reduces to the standard (Comb) UCBI algorithm [25] and we could also recover the results of 25 in such case. This further justifies the tightness of our regret bound.
2.3 Achieving constant regret for fairness constraints
In this section, we consider the special case of fairness constraints. Following the same setting in the literature, c.g., (29 48 39], each arm [N] is required to be pulled at least ri E (0,

---

fraction of times, and ZLE[N] Ta < m. Namely, the agent has to satisfy (x) 2 r:T, Va E [N] Define P.1.,2......11 7x)" T, then the equivalent linear long term constraint function g(+) under our setting is g(a(t)) = (t) + r. In the fairness constraints setting, the main challenge is that the time horizon T is unknown to the algorithm beforehand, and thus the "forced exploration" trick cannot be directly applied here. A lot of work (See Table 1) has sprung up recently to tackle this difficulty, but the best previous result is only ((VT) under the combinatorial setting. The following theorem shows that UCB-LP could guarantee constant regret.
Theorem Define Tmmn
min ri. In the case of faimnes constraints, UCB-LP guarantees that RE[N] Regrety S minn Aiio In2
32mN2
32N2
mNN#
min A2 min
To derive constant regret, one natural idea is to show that the quantity E[h,(T)) -r:-)Trr--T is bounded for every sub-optimal arm i (whose mean reward is not Top-m). However, this is not the case in classic bandit analysis (e.g.. for UCB-based algorithms) and thus cannot directly apply here. Our main proof idea is to show that UCB-LP only chooses a sub-optimal distribution over arms (i.e., axt) & X²) limited number of times for fairess constraints. To achieve this, we first transform the event of (1) X to the events associated with arm's UCB estimate error, i.c., we use the following lemma to characterize the case of at)) & X by the sensitivity analysis of LP (4).
Basic analysis of Theorem 2.
Lemma If\ (t)) - 14l12 < Amin, then (t) E X
In other words, when xxt) $ X' we have l| - H4l, > Amin. And then we just have to prove that [lă(()) الll > Amin = max;e [N] [t) pu| Amm/N only happens finite number of times. This is a little counterintuitive for UCB-style algorithms, but it holds for UCB-LP in the faimess setting as UCB-LP guarantees that every arm has positive probability of being pulled at each round which leads to the diminishing confidence width of all arms and the bonus of concentration inequality. In particular, by martingale analysis and extending the concentration bound to random process that evolves over time, we prove that there exists constant
0 (e.g.,
32N22 In? 32N2
min A
such that h, (t) 2 sN² Int holds with high-probability for each arm when / >> G, which gives that [A:(t) ((st) S Amin/N
/N holds with high-probability when t > It is worth noting that such properties do not hold for classic bandit algorithms (e.g., algorithms based on the UCBI framework). And to the best of our knowledge there is no such results in the literature. Finally, to fit into our Lemma 2, we handle the regret as Regrety S m Σ Pr Pr(a(() & x²1 S mc + m Σieei Pr(x(t) & x=) S mc + m Eimpp (r]ll((()= 11,, 2 Amin]. Put all things together then we complete the proof.
Breaking the (log T) lower bound. The constant regret bound given by Theorem 2 might seem counter-intuitive at first glance, since the lower bound of regret under classical MAB setting is A(log 7) 126.. However, note that the fairness level r; is required to be strictly positive, and the benchmark policy in the regret also needs to satisfy the long term constraints. This distinguishes our setting from the classical MAB setting. Thus, the traditional 2(log T) lower bound no longer applies.
The reason why UCB-LP achieves a constant regret is: UCB-LP guarantees that every arm has a positive probability of being pulled at each round. This leads more accurate reward estimates of arms and diminishing gap between ju(t) and μ, which makes UCB-LP output the sub-optimal action distribution only a finite number of times. That said, still requires non-trivial techniques to establish a constant regret bound. In fact, even Olog T) regret bound has not yet been achieved for combinatorial setting in prior works.
Note that our regret bound has quadratic dependence on 1/rmin, which goes to infinity as r + 0. In fact, when r 0, i.e., there are fairness constraints, our problem degenerates to classical MAB setting where achieving constant regret bound is impossible. This indicates that such dependence on extra parameters is inevitable for any constant regret bound. Of course, the general Olog I') regret bound developed in Theorem still applies when + O, since it does not depend on 1/Tmin.
Ö(N) running time. The structural property of the faimess constraints allows us to obtain a closed form solution to LP as shown in the following proposition.
Proposition 1 For each round rearrange the coordinates of UCB estimate vector ((()) in descend- ing order such that Pay (t) 2 Pag (t) 2 ... 2 Payy (t), where o' is permutation 1...,, Then one of the optimal extreme points LP (denoted as xet)) has the following form:
7

---

(ot(1) 1, Vi ku; Not :ot vi > kas Fot (f) m++1+1111 ku Σ
Toj
where h, = mi E Z+ E (To) 2 m E ri).
Proposition immediately implies that UCB-LP computationally efficient when dealing with fairness constraints. To solve LP 4 one can simply sort all coordinates of (t() in O(N log N time, then compute k, and (t) according to the closed form expression in proposition| I (note that x(() in Proposition I also
also lies in B). Since the running time of computing distribution and sampling a(t) is
also O(N log N), we conclude that the time average complexity of UCB-LP is O(N log logN)= Ö(N).
Another constant regret bound. Proposition further provides two important implications:
(a) Since LP 2 has the same form with LP 44, the optimal solution x" to LP 2 can also be written in closed form in the same manner to Proposition [ Specifically, rearrange the coordinates of in descending order as Hoi 2 Moz 2
payy and define k = min(q Z+ |E -ra.) 2 m DN rz). Then x² has the following form:
Fr. = 1, Vi < k; xe, = Tos vi k; = - - E ror.
(b) The optimal solution (1) to LP 4 only depends on the relative order, not the absolute value of (t)...... ........... (t). This motivates to characterize the sensitivity of LP (4) from new perspective. Intuitively, if fi and μ are close enough such that the relative order between the coordinates is (at least partially) preserved, then the optimal solutions of LP and LP 2 will coincide.
The above two implications motivate us to define a new parameter e == millyettor I Mox and
propose the following corollary to characterize the sensitivity of LP 4
Corollary If (()((()) p0l1oo S. then (=))= E X
Proof sketch of Corollary 1. Proposition | shows that when is fixed, for vi + of, the value of (t) only depends on whether (t((t) < Ast, (t) or not. Similarly, for Vi & ax, the value of x; only
depends on whether (4 < Msy or not. This implies that, if k2 = kt of. = ax and (t((t) Paj, (f) have
the same sign with μ4 Hey, then (1) zz. In other words, if μr > Hog = (() > Pa. (1) and
I < Hog = (t) < fir (t) holds for Vi E [N], then x+t) = x²" When [| p |l100 < 5. by the
definition of for Vi we have p4 Me, + 14 2 Ma,
(t) 14 _ May $ > Dzg (t) and
[A < Pay * 14s S Poa e (t) < #4 + S Mo, 5 < Mrr (t). Then sxt) = x².
With Corollary we derive another constant regret bound of UCB-LP in the following theorem.
Theorem UCB-LP also guarantees the following regret bound for fairness constraints,
64m Regrety S 2 e
64
+ mN#
In
min
In the supplementary material, we show that Amin = c= both reasonable generalizations of A.
A when our formulation reduces to the
classical MAB setting, which suggests that Amin and Although c and Amin are generally incomparable, we believe that the regret bound given by Theorem is tighter than Theorem 2 To provide evidences for this, in supplementary material, we investigate the closed form expression of Ami- We show that e = A 2 Amin = A(1 Σ, r,) in the special case of 1. Intuitively, characterizes the structural properties of faimess constraints, while Amin is more general and applies to all linear constraints.
Remark 1 LP-sensitivity arguments are not new in bandit analyses and was firstly shown in (42) which used a technique based on LP-sensitivity analyze the UcbBwK algorithm (I] for BwK problem in the single-arm setting. Here we would like to point out that the technique based on LP- sensitiivity we used is completely different from theirs. Specifically, their analysis relies on the assumptions of single resource and that the best distribution over arms reduces to the best fixed arm, while we do not require any ussumptions. Moreover, our technique also non-standun as our sensitivity anulysis (Lemma) 2, Corollary 1) takes full advaniage of the fairness structure (e.g.. closed-fore solution of LPP.. Thus, our result is sharper than standard results about I.P sensitivity and leads to the O(1) regret bound.
8

---

Algorithm I UCB-PLLP
1: Initialization: A { x E {0, 1 ||ح||| $ m)
2: for round t = 1....T do
3: Compute UCBs: (t) = [7, (t) +
2lnt
1}, Vi.
he(0):
4: Update the primal iterate: a(t) = arg max (fa(t) - ar Ei= acA
5: Play arm i and receive (1(t) if (t) 1.
6: Update the virtual queues: Q(t 1) = (Q(1) (00)++(e (((())(a(())aaa)) +
7: Update the statistics: h.(t + +1, Ft,tt + 1), Vi.
8: end for
Except [42] studies the BwK problem based on the LP methodology, (5) also develops an algorithm based I.P methodology to track the (contextual) blocking bandit problem wherein once an arm is pulled it cannot be played again for a fixed number of consecutive rounds. Here we argue that their L.P-sensitiiiyybaaeee proof techniques cannot obtain our regret bounds. Specifically, (5) utilizes techniques in 110J and [44], where [10] proposes the general CMAB framework and [44] improves upon its regret bounds. The core of their techniques is maintain set of counters for every arm i and allocate the regret to arms according to these counters. However, this regret allocation leads to the arms in the support of LP solution associated with the same term while their probubility of being triggered by the LP-solution is different. This coarseness makes the final regret bound to scale with the size of the support, transforming the regret bound from our result of O(mN Iu'T Amin)) to ( TI A.in). In contrast, our analysis is more fine-graing since we do not maintain a counter for every arm i and allocate the regret according to the counter value, but allocate the regret to arm i according to the number of times it is pulled directly. More specifically, we only allocate the regret to arms in V(L)= == {i: ht(()) I 32m ) i.e., the "dominant arms" whose pulls is no more than O(m² In ainn) ) times. Thus, each arm is bounded according to its probability of being triggered, and one no longer needs to distinguish arms in the support and other arms.
Remark 2 When the long-ten tnng-termnae constraints only need to be satisfied in expectation, someone may adopt the well-established linear bandit algorithuss like LinUCB (14) to track and identify the optimal sampling distribution over arms (optimal extreme point). We pointed out that applying LinUCB to our model involves solving an NP-hard optimization problem and fails to achieve logarithmic regret bound of O(mN log T) as our algorithm UCP.-IP does. In contrast, UCB-LPP has much lower computational complexity than the reduced LinUCB algorithm since it is polynomial-tine computable. Furthermore, UCB-LP can guarantee a bounded regret for fairness setting. The reason why LinUCB produces sub-optimal results is that LinUCB ignores the structural properties of the constraints (e.g., concentration property bonus caused by the fairness constraints) and observations about each individual pulled arm.
2.4 O(N) running time version of UCB-LP and its theoretical performance
As mentioned earlier, UCB-LP might be computationally inefficient when constraint function g(.) is complicated. In this section, we present the low pppputaioonalcompeliiiiii
version of UCB-LP, the UCB-PLLP algorithm, for problems of combinatorial bandits with linear long-term constraint. Note that the main computational bottleneck of UCB-LP B-PPiP is caused by the constraint g(x) < 0. To be computationally efficient, we optimize the (partial) Lagrangian of LP (4) at each round t:
max RER BERN
(x, Xx) = (f(().
g()) s.t. 0 < x < 1, || m.
(8)
In (8) Ar is the Lagrange multiplier associated with the constraints at round t. The main challenge is how to design A, to make a good balance between reward maximization and long-term constraints satisfaction. To address this challenge, we construct a virtual queue Qtt) to keep track of the "debt" of constraint violations up to round 6, i.e., Q(1) = [Q( 1) + g(a(t 1)){+, and let A, = Q(). where a, could be vareing However, this Lagrange multiplier deign may lead to large constraint violations as g(.) becomes a "soft" constraint in LP (8) while in LP 44) it is a "hard" constraint.
To yield lower constraint violations, we incorporate the virtual queue update with "pessimistic" mechanism 35 so that the virtual queues overestimate the constraint violations, which is novelty of our PLLP, Although the idea of using a "pessimistic" mechanism has been exploited in linear

---

(contextual) bandits with safety constraints (e.g., 2 38), etc), the pessimism in our algorithm achieved via adding a time-varying tightness constant virtual queue update, i.e. Q(1)
[Q 1) g(a(t 1)) + f which is completely different from the pessimism in previous works. Since g(-) is linear, the optimization problem (8) has an integral closed-form solution and equivalent to the following optimization problem:
(p((t)
Vg - 1))Qx(t).
s.f. x T [0,1),
||]|| m.
KE[K]
(9)
max (1(1) az
Σ
- (o)(a(t-1))Qxt).o0) s.t. a a {0,1) ||||| S m
kE[K]
1 Note that if we set at = 1) and = 0, the N for fairness constraints setting. Apparently, the computationallcooplexii of UCB-PLLP is essentially the same as choosing
We illustrate this algorithmic approach in Algorithm
algorithm LBF in [29] our special case as Vg.( -ek and
the top arms with maximum positive compound value, which is Ö(N).
Theoretical performance of UCB-PLLP. Here we present the regret bound and constraint violations for UCB-PLLP. Our result relies on mild assumption of Slater condition (Interior condition), i.c., there exists > and @ E D> such that g(Ø) < -ô1. Note that Slater condition automatically holds for fairness constraints as < 1, Vi, and Σie(N] < m. It is also default assumption in BwK literature (They all assume the null arm denoted by 0 exists, i.e, X = 0, vi E [K]).
Theorem 4 Set 6, = 044)) and az O(2)), then UCB-PLLP achieves
Regret,- S (mmT)), (r) > 0J S O Va E [K], T S.
We give the proof of Theorem in supplementary material. Our proof technique is based on the drapu analysis for queueing systems. The bounds in Theorem 4 are sharp in the perspective that the regret bound matches the problem-independen regret of UCBI algorithm in standard MAB setting, and the probability of constraints not being violated converges to 1, i.e, holds asymptotically almost surely.
Intuition behind Theorem 4. Here we explain the intuition why UCB-PLLP has such performance guarantees. Since a = O(1/vt), the reward term dominates the whole term in ( when (t = of vt). If Qu(t)= w( (t), the term containing virtual queues dominates the reward term, and UCB-PLLP tends to reduce the virtual queues Q+ Slater's 's condition implies that there exists a policy that can reduce (!) by constant (related to 5) in each round. Therefore, the algorithm takes at most (vV)) rounds to reduce (1) to of VT), which may lead to OVVT) increase of the regret. Thus, we could derive that (+) = O(vi). Recall that (t + 1) 2 E g (a(t)) +f= F = Viox(T) = ΣT 9 (a(t)) s Qu(T'+ - >i=1 cx, we can obtain zero constraint violation via choosing proper e,. Then, the high probability constraint violation guarantee is established by bounding the exponential moment of the virtual queues since Pr(Vio: 2 0) < Pr(Qu(T + > Ei 4.) < 1/
Remark 3 Although the virtual queue techniques have been used for various constrained online learning problems in the literature (e.g.. M& 2 29 20 49 27
32 37 344), our virtual queue update rule differs from theirs in the pessimistic mechanism via adding a time-varying tightness constant. Beyond the update rule of virtual queue, we also employ some new techniques in our Lyapunov analysis. For example, we establish bound on the exponential moment of the virtual queue length (Lemma 6), which is the central focus of our high--roobbbiiity guarantee on zero constraint violations. We also establish an upper bound on the qi-tight term (incurred by our pessimistic mechanism) via comparing the optimal solution to the original LP problem and that to its -tightened version based on LP-sensitivity (lemmas? and 4). These analysis techniques are not present in these works.
35
focus
2.5 Experiments
The results of our numerical experiments are given in the supplementary material.
Acknowledgments and Disclosure of Funding
The work of Siwei Wang is supported part by the National Natural Science Foundation of China Grant 122.
10

---

References
[1] Shipra Agrawal and Nikhil R Devanur. Bandits with concave rewards and convex knapsacks. In Proceedings of the fifteenth ACM conference Economics and computation, pages 989-1006, 2014.
[2] Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. Linear stochastic bandits under safety constraints. Advances Neural Information Processing Systems, 32:9256-9266, 2019.
[3] Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. Generalized linear bandits with safety constraints. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3562-3566. IEEE, 2020.
[4] Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knap- sacks. Journal of the ACM (JACM), 65(3):1-55, 2018.
[5] Soumya Basu, Orestis Papadigenopoulos, Constantine Caramanis, and Sanjay Shakkottai. Contextual blocking bandits. In International Conference on Artificial Intelligence and Statistics, pages 271 271-279. PMLR, 2021.
[6] Dimitris Bertsimas and John N Tsitsiklis. Introduction to linear optimization, volume 6. Athena Scientific Belmont, MA, 1997.
[7] Semih Cayci, Atilla Eryilmaz, and Rayadurgam Srikant. Budget-constraine bandits over general cost and reward distributions. In International Conference on Artificial Intelligence and Statistics, pages 4388-4398. PMLR, 2020.
[8] Semih Cayci, Swati Gupta, and Atilla Eryilmaz. Group-fair online allocation in continuous time. Advances in Neural Information Processing Systems, 13500-111677,, 2020.
[9] Semih Cayci, Yilin Zheng, and Atilla Eryilmaz. lyapunov-based methodology for constrained optimization with bandit feedback. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 3716-3723, 2022.
[10] Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit: General framework and applications. In International conference on machine learning, pages 151-159. PMLR, 2013.
[11] Yuchao Chen, Jintao Wang, Qining Zhang, Feifci Gao, and Jian Song. Online utility optimization in multi-user interference networks under a long-term budget constraint. IEEE Transactions on Vehicular Technology, 2022.
[12] Houston Claure, Yifang Chen, Jignesh Modi, Malte Jung, and Stefanos Nikolaidis. Multi-armed bandits with fairness constraints for distributing resources human teammates. In Proceedings of the 2020 ACM/IEEE International Conference on Hoaman-RRbor Interaction, pages 299-308, 2020.
[13] Richard Combes, Chong Jiang, and Rayadurgam Srikant. Bandits with budgets: Regret lower bounds and optimal algorithms. ACM SIGMETRICS Performance Evaluation Review, 43(1):245-257, 2015.
[14] Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. 2008.
[15] Debojit Das, Shweta Jain, and Sujit Gujar. Budgeted combinatorial multi-armed bandits. arXiv preprint arXiv:2202.053: 037044 2022.
[16] Guanhua Fang, Ping Li, and Gennady Samorodnitsky. A new look at fairness in stochastic multi-armed bandit problems. 2021.
[17] Kris Johnson Ferreira, David Simchi-Levi Levi, and He Wang. Online network revenue management using thompson sampling. Operations research, 1566):158611 2018.

---

[18] Arthur Flajolet and Patrick Jaillet. Logarithmic regret bounds for bandits with knapsacks. arXiv preprint arXiv:1510.01800 2015.
[19] Dongdong Ge, Chengwenjian Wang, Zikai Xiong, and Yinyu Ye. From an interior point to corner point: Smart crossover. arXiv preprint arXiv:2102.09422 2021.
[20] Zhiming Huang, Yifan Xu, Bingshan Hu, Qipeng Wang, and Jianping Pan. Thompson sampling for combinatorial semi- bandis with sleeping arms and long-tet long-termian fairesss constraints. arXiv preprint arXiv:2005.06725, 2020.
[21] Ziyao Huang, Weiwei Wu, Chenchen Fu, Vincent Chau, Xiang Liu, Jianping Wang, and Junzhou Luo. Aoi-constrained bandit: Information gathering over unreliable channels with age guarantees. arXiv preprint arXiv: (..Ki::212.027000 12.02786, 2021.
[22] Nicole Immorlica, Karthik Abinav Sankararaman, Robert Schapire, and Aleksandrs Slivkins. Adversarial bandits with knapsacks. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 202-219. IEEE, 2019.
[23] Matthew Joseph, Michael Kearns, Jamie Morgenstern, and Aaron Roth. Fairness in learning: Classic and contextual bandits. arXiv preprini arXiv: 2016.
[24] Thomas Kesselheim and Sahil Singla. Online learning with vector costs and bandits with knapsacks. In Conference on Learning Theory, pages 2286-2305. PMLR, 2020.
[25] Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. Tight regret bounds for stochastic combinatorial semi-bandits. In Artificial Intelligence and Statistics, pages 535-543.
PMLR, 2015.
[26] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020,
[27] Bin Li. Efficient learning-based scheduling for information freshness in wireless networks. In IEEE INFOCOM 2021-IEEE Conference on Computer Communications, pages 1-10. IEEE, 2021.
[28] Feng Li, Jichao Zhao, Dongxiao Yu, Xiuzhen Cheng, and Weifeng Lv. Harnessing context for pudget-limited crowdsensing with massive uncertain workers. arXiv preprint arXiv:2107.01385. 2021.
[29] Fengjiao Li, Jia Liu, and Bo Ji. Combinatorial sleeping bandits with fairness constraints. IEEE Transactions on Network Science and Engineering, 17)::179--1813, 2019.
[30] Xiaocheng Li. Chunlin Sun, and Yinyu Ye. The symmetry between arms and knapsacks: A primal-dual approach for bandits with knapsacks. arXiv preprint arXiv:2102.06388 2021.
[31] Qingsong Liu and Zhixuan Fang. Learning to schedule tasks with deadline and throughput constraints. In IEEE INFOCOM 2023-IEFE Conference on Computer Communications, pages 1-10. IEEE, 2023.
[32] Qingsong Liu, Zhuoran Li, and Zhixuan Fang. Online convex optimization with switching costs: Algorithms and performance. 2022 20th International Symposium on Modeling and Optimization in Mobile, Ad hoc, and Wireless Networks (WiOpt), pages 1-8. IEFE, 2022.
[33] Qingsong Liu, Wenfei Wu, Longbo Huang, and Zhixuan Fang. Simultaneously achieving sublinear regret and constraint violations for online convex optimization with time-varying constraints. Performance Evaluation, 152:102240, 2021.
[34] Qingsong Liu and Yaoyu Zhang. Learning to caching under the partial partial-feedback regime. In 2022 18th International Conference on Network and Service Management (CNSM), pages 162. IEEE, 2022.
[35] Xin Liu, Bin Li, Pengyi Shi, and Lei Ying. An efficient pessimistic-optinste algorithm for stochastic linear bandits with general constraints. Advances Neural Information Processing Systems, 34, 2021.
12

---

[36] Will Ma, Pan Xu, and Yifan Xu. Group-level fairness maximization in online bipartite matching. arXiv preprint arXiv:2011.133005 2020.
[37] Nimrod Megiddo. On finding primal-and dual-optimal bases. ORSA Journal on Computing, 3(1):63-65, 1991.
[38] Aldo Pacchiano, Mohammad Ghavamzadeh, Peter Bartlett, and Heinrich Jiang. Stochastic bandits with linear constraints. In International Conference on Artificial Intelligence and Statistics, pages 2827-2835, PMLR, 2021.
[39] Vishakha Patil, Ganesh Ghalme, Vineet Nair, and Y Narahari. Achieving fairness in the stochastic multi-armed bandit problem. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5379-5386, 2020.
[40] Wenbo Ren, Jia Liu, and Ness Shroff. On logarithmic regret for bandits with knapsacks. In 2021 55th Annual Conference on Information Sciences and Systems (CISS), pages 1-6. IEEE, 2021.
[41] Karthik Abinav Sankararaman and Aleksandrs Slivkins. Combinatorial cami-bandits with knapsacks. In International Conference on Artificial Intelligence and Statistics, pages 1760- 1770. PMLR, 2018.
[42] Karthik Abinav Sankararaman and Aleksandrs Slivkins. Bandits with knapsacks beyond the worst case. In Thirty-Fiif Conference on Neural Information Processing Systems, 2021.
[43] Juaren Steiger, Bin Li, and Ning Lu. Learning from delayed semi-bandi feedback under strong fairness guarantees. In IEEE INFOCOM 2022-IEEE Conference on Computer Communications, pages 1379- 1388. IEEE, 2022.
[44] Qinshi Wang and Wei Chen. Tighter regret bounds for influence maximization and other combinatorial semi-bandits with probabilistically triggered arms. CoRR, abs/1703.016/) 2017.
[45] Siwei Wang and Wei Chen. Thompson sampling for combinatorial emmi-bandits. In International Conference on Machine Learning, pages 51 14-52222. PMLR, 2018.
[46] Yingce Xia, Wenkui Ding, Xu-Dong Zhang, Nenghai Yu, and Tao Qin. Budgeted bandit problems with continuous random costs. In Asian conference on machine learning, pages 317-332. PMLR, 2016.
[47] Yingee Xia, Haifang Li, Tao Qin, Nenghai Yu, and Tie- Yan Liu. Thompson sampling for budgeted multi-armes bandits. In Twenty-Fore Fourth International Joint Conference on Artificial Intelligence, 2015.
[48] Huanle Xu, Yang Liu, Wing Cheong Lau, and Rui Li. Combinatorial multi-armed bandits with concave rewards and faimnsss constraints. In IJCAI, pages 2564,, 2020.
[49] Jingjing Yao and Nirwan Ansari. Task allocation in fog-aided mobile iot by Iyapunov on- line reinforcement learning. IEEE Transactions Green Communications and Networking, 4(2):556-565, 2019.
[50] Xinlei Yi, Xiuxian Li, Tao Yang. Lihua Xie, Tianyou Chai, and Karl Johansson. Regret and cumulative constraint violation analysis for online convex optimization with long term constraints. In International Conference on Machine Learning, pages 11998-189 12008. PMLR, 2021.
[51] Hao Yu and Michael J Neely. A low complexity algorithm with o(vT) regret and o11) constraint violations for online convex optimization with long term constraints. Journal of Machine Learning Research, 21(1):1-24, 2020.
[52] Julian Zimmert, Haipeng Luo, and Chen- Yu Wei. Beating stochastic and adversarial semi- bandits optimally and simultaneously. In International Conference on Machine Learning, pages 7683-7692. PMLR, 2019.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [No]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "cHlzzcbAT7F", "reviewer": "Reviewer_7wPF", "summary": "This paper proposes the general bandit problem that subsumes Bandits with Knapsacks and Bandits with fairness constraints. UCB-LP, inspired by  SemiBwK algorithm [30], is proposed and its regret bound archives $O(mN \\log T/\\Delta_{\\min})$. They also study the special class for fairness constraints and show that UCB-LP guarantees a constant regret. Finally, UCB-PLLP algorithm is proposed as a computational efficient algorithm and its regret bound archives $\\tilde{O}(m \\sqrt{T})$. \n", "questions": "Any new difficulties that arise from changing from a single-armed setting to a combinatorial (size constraint) setting?\n\nAre there any lower bounds for fairness setting with respect to the $r_{\\min}$?\n\n===Post Rebuttal===\n\nThank you for the author feedback. I have read other reviews and discussion. \n\nEspecially, comparison with [Cayci et al., 2021]  and discussion on how this paper uses virtual queue techniques is clearer.\nI hope the authors will incorporate them and position this paper in the literature.\n\nSo I will keep my score.", "limitations": "The paper is missing the section for conclusion and does not discuss any limitation or future direction. More discussion is appreciated.\n", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. Though UCB-LP is designed based on SemiBwK algorithm [30], generalization to linear constraints and regret analysis is done in a novel way. Naive analysis will suffer from the bound with size of extreme points of a feasible region of LP, i.e.,  $|\\mathcal{B}|$ which is exponentially large. \\\n\n\n2. UCB-LP does not need prior knowledge while existing work [12, 29, 31] requires some knowledge of the problem instance, and UCB-LP reduces to the standard UCB-1 algorithm for the special case. \n\n\n\nWeakness:\n\nThe whole procedure (pseudocode) for UCB-LP is missing in the main paper and supplemental material. \n \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "SP5nCYqnNz", "reviewer": "Reviewer_Rm7C", "summary": "\nThe paper studies a combinatorial multi-armed bandits with linear long-term constraints, where the combinatorial constraints are cardinality constraints and the linear constraints are deterministic and known. The paper proposes an upper-confidence bound LP-style algorithm for this problem that provides a logarithmic instance-dependent regret and no constraint violations in expectation. Then, the authors develop a second algorithm with better running time, a $\\tilde O(\\sqrt{T})$ regret, and no constraints violation in high probability.", "questions": "Let me know if I’m missing something about the relation between classical bandit problems and your framework.\nFor instance, are there some previous works in which neither condition 1) nor condition 2) is satisfied?\n\n\n", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work", "rating": 7, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I have a huge concern about the meaningfulness of the problem studied in the paper.\nI think that the study of BwK is meaningful when at least one of the following condition is satisfied:\n1) the costs are unknown,\n2) the costs are not in expectation, i.e., if the regret minimizer chooses a vector x the actual suffered cost is not g(x) but g(a) where a is sampled from x. Then, if the budget ends the game is over.\n\nIf none of the conditions is satisfied, the problem reduces to a classical Linear bandit.\nIn particular, any no-regret algorithm for linear bandits with action space defined by the constraints in Problem (4) does satisfies the constraints in expectation and provides no-regret.\nNotice that your algorithm in Theorem 1 follows this approach: it satisfies the constraints at each round (in expectation).\n\n\nMinor comments:\n\nThe abstract does not specify all the assumptions in the framework. For instance, I suggest to specify in the abstract that the constraints are deterministic and time invariant, while the combinatorial constraints are cardinality constraints.\n\nAt line 42. I don’t see a clear relation with the result in [4]. In [4] the constraints are not deterministic and it could happen that the algorithm have to stop before round T since it ended the budget. For this reason $OPT(T)$ could be strictly smaller than $T\\ OPT_{LP}$. \nI’m quite sure that $OPT(T)=T \\ OPT_{LP}$ with deterministic constraints that need to be satisfied in expectation, since the algorithm never stop.\n\n\nPost rebuttal update: I'm completely convinced by the authors' answers.\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6woQb7RwVNI", "reviewer": "Reviewer_rd83", "summary": "The authors study the Combinatorial bandits problem with linear constraints. This problem captures multiple existing problems including fairness constraints, and Knapsack constraints. The authors show that using UCB estimates for the mean reward of each arm in a constrained LP, and playing the arms according to the optimal solution of that LP ensures in expectation 0 constraint violation and logarithmic regret. As a special case, fairness constraints incurs constant regret when each arm is forced to choose a constant fraction of time. They augment this result with a Lagrangian based computationally efficient algorithm with $O(\\sqrt{T})$ problem independent regret, and 0 constraint violation with high probability.   ", "questions": "Please compare the current work with the prior works mentioned in the weakness section.", "limitations": "Any negative societal impact for this work is hard to foresee.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The proposed UCB-LP algorithm solves multiple well studied problems, such as semi-bandits with knapscak, and bandits with fairness constraints.\n- The constant regret in fairness constraint is an interesting result (though not very surprising).\n- The Lagrangian based optimization process (UCB-PLLP) is computationally efficient, and shows optimal minimax regret with no constraint violation with high probability. \n\nWeakness\nThe paper is not well placed in the literature, in my opinion. \n- The paper \"The Combinatorial multi-armed bandit: General framework and applications.\" by Wei Chen et al.  already addresses the main challenge discussed in the paper, i.e. tackling exponential extreme points in the LP.  Similar ideas are used in a slightly different context in \"Contextual Blocking Bandits\" by Basu et al. \n- The virtual queue based approach used in the UCB-PLLP is used in a series of work by H Yu and MJ Neely. E.g. \"A Low Complexity Algorithm with $O(\\sqrt{T})$ Regret and $O(1)$ Constraint Violations for Online Convex Optimization with Long Term Constraints\" H Yu and MJ Neely. \n\nPost Rebuttal: Upon discussing with the authors, I came to the conclusion that the current work indeed improves upon the technique used in  [Basu et al. 2021] for regret bounds in constrained LP with blocking, which was based on  [Chen et al., 2013] and [Wang and Chen, 2017]. The novelty in the virtual queue based technique was also made clear from discussions. The authors are requested to include these works and brief summary of discussions in the paper.  ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "31Pi_JLY4Jj", "reviewer": "Reviewer_SVeo", "summary": "The paper studies a general formulation of combinatorial bandits with linear constraints, which contains bandits with fairness and knapsacks as special cases. The authors propose and analyze an algorithm that combines UCB-based estimation with a linear program solution to yield logarithmic regret and zero constraint violation performance. Authors also propose a low-complexity variant of the algorithm that utilizes virtual queues to iteratively solve the LP component of the original design. ", "questions": "The examples in the discussion are limited. Please expand on them to clarify how the formulation fits into the generic form. \n\n", "limitations": "I have not seen a discussion on limitations of this work. The emphasis has been on its contributions, which is understandable. It would be good to note any limitations that the authors recognize. ", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The work provides a solid contribution to the literature on constrained MABs by encapsulating knapsack and fairness constraints within a unified formulation. The design and analysis are valuable contributions to this literature. \n\nThe novelty of the design is limited as it relies largely on well-known principles. However, the analysis yielding the logarithmic regret bound in this setting is important.\n\nWhile the literature review is extensive, there are several other works that are worth including, such as: \n\nA Lyapunov-Based Methodology for Constrained Optimization with Bandit Feedback\nSemih Cayci, Yilin Zheng and Atilla Eryilmaz\nThirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022\n\nBudget-Constrained Bandits over General Cost and Reward Distributions\nSemih Cayci, Atilla Eryilmaz, R. Srikant\nInternational Conference on Artificial Intelligence and Statistics (AISTATS), PMLR 108, 2020.\n\nThe first of these works in particular also uses the lyapunov drift minimization techniques for constrained MABs, which is utilized in the PLLP algorithm design. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept