Bandits with Knapsacks beyond the Worst Case
Year: 2021

Abstract:
Bandits with Knapsacks (BwK) is a general model for multi-armed bandits under supply/budget constraints. While worst-case regret bounds for BwK are wellunderstood, we present three results that go beyond the worst-case perspective. First, we provide upper and lower bounds which amount to a full characterization for logarithmic, instance-dependent regret rates. Second, we consider “simple regret" in BwK, which tracks algorithm’s performance in a given round, and prove that it is small in all but a few rounds. Third, we provide a general “reduction" from BwK to bandits which takes advantage of some known helpful structure, and apply this reduction to combinatorial semi-bandits, linear contextual bandits, and multinomial-logit bandits. Our results build on the BwK algorithm from Agrawal and Devanur [3], providing new analyses thereof.

heading: 1 Introduction
text: We study multi-armed bandit problems with supply or budget constraints. Multi-armed bandits is a simple model for exploration-exploitation tradeoff, i.e., the tension between acquiring new information and making optimal decisions. It is an active research area, spanning computer science, operations research, and economics. Supply/budget constraints arise in many realistic applications, e.g., a seller who dynamically adjusts the prices or product assortment may have a limited inventory, and an algorithm that optimizes ad placement is constrained by the advertisers’ budgets. Other motivating examples concern repeated auctions, crowdsourcing markets, and network routing.
We consider a general model called Bandits with Knapsacks (BwK), which subsumes the examples mentioned above. There are d 2 resources that are consumed over time, one of which is time itself. Each resource i starts out with budget Bi. In each round t, the algorithm chooses an action (arm) a = at from a fixed set of K actions. The outcome is a vector in [0, 1]d+1: it consists of a reward and consumption of each resource. This vector is drawn independently from some distribution over [0, 1]d+1, which depends on the chosen arm but not on the round, and is not known to the algorithm. The algorithm observes bandit feedback, i.e., only the outcome of the chosen arm. The algorithm stops at a known time horizon T , or when the total consumption of some resource exceeds its budget. The goal is to maximize the total reward, denoted REW.
The presence of supply/budget constraints makes the problem much more challenging. First, algorithm’s choices constrain what it can do in the future. Second, the algorithm is no longer looking for arms with maximal expected per-round reward (because such arms may consume too much resources). Third, the best fixed distribution over arms can be much better than the best fixed arm. Accordingly, we compete with the best fixed distribution benchmark: the total expected reward of the best distribution, denoted OPTFD. All this complexity is already present even when d = 2, i.e., when there is only one resource other than time, and the minimal budget is B = mini Bi = ⌦(T ).
BwK were introduced in [14, 16] and extensively studied since then. The optimal worst-case regret rate is well-understood. In particular, it is Õ( p KT ) when B = ⌦(T ).
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
We present several results that go beyond the worst-case perspective:
1. We provide a full characterization for instance-dependent regret rates. In stochastic bandits, one obtains regret O K log T , where is the the reward-gap: the gap in expected reward between the best and the second-best arm. We work out whether, when and how such results extend to BwK.
2. We show that simple regret, which tracks algorithm’s performance in a given round, can be small in all but a few rounds. Like in stochastic bandits, simple regret can be at least ✏ in at most Õ(K/✏2) rounds, and this is achieved for all ✏ > 0 simultaneously.
3. We improve all results mentioned above for a large number of arms, assuming some helpful structure. In fact, we provide a general “reduction" from BwK to stochastic bandits, and apply this reduction to three well-studied scenarios from stochastic bandits.
Our algorithmic results focus on UcbBwK, a BwK algorithm from [3] which implements the “optimism under uncertainty" paradigm and attains the optimal worst-case regret bound. We provide new analyses of this algorithm along the above-mentioned themes.
Related work. Background on multi-armed bandits can be found in books [23, 54, 42]. Stochastic bandits (i.e., BwK without resources) is a basic, well-understood version. The dependence on and ✏ are optimal as stated above [41, 10, 11], and is achieved simultaneously with the optimal worst-case regret eO(KT ), e.g., in [10]. Various refinements are known for O(log T ) regret [10, 8, 34, 32, 45]. Most relevant to this paper is O ( P a log(T )/ (a) ) regret, where (a) is the gap in expected reward between arm a and the best arm [10]. Improving regret for large / infinite number of arms via a helpful structure is a unifying theme for several prominent lines of work, e.g., linear bandits, convex bandits, Lipschitz bandits, and combinatorial (semi-)bandits.
Bandits with Knapsacks were introduced in [14, 16], and optimally solved in the worst case. Subsequent work extended BwK to a more general notion of rewards/consumptions [3], combinatorial semibandits [49], and contextual bandits [15, 6, 4]. Several special cases with budget/supply constraints were studied separately (and inspired a generalization to BwK): dynamic pricing [19, 12, 20, 59], dynamic procurement [13, 52], and dynamic ad allocation [53, 28]. The adversarial version of BwK was studied by [35, 36]. All this work considers worst-case regret bounds.
Several papers achieve O(log T ) regret in BwK, but with substantial caveats that we avoid. [61] assume deterministic consumption, whereas all motivating examples of BwK require stochastic consumption correlated with rewards (e.g., dynamic pricing consumes supply only if a sale happens). They posit d = 2 and no other assumptions, whereas we show that “best-arm optimality" is necessary with stochastic consumption. [31] assume “best-arm-optimality" as we do (it is implicit in their version of reward-gap). However, their algorithm inputs an instance-dependent parameter which is “hidden" in BwK. Moreover, their O(log T ) regret bound scales with cmin, minimal expected consumption among arms (as c 4min). Their worst-case regret bound is suboptimal, since it also scales with cmin (as c 2 min), and only applies for d = 2. [58] study a contextual version of BwK with two arms, one of which does nothing; this is meaningless when specialized to BwK. [44], subsequent to our initial draft on arxiv.org, use extra parameters (other than a version of reward-gap), which yield p T regret whenever our lower bounds apply;1 it is unclear when all their parameters are small. No worst-case regret bounds are provided; their algorithm does not appear to achieve even o(T ) regret in the worst case. Finally, [33, 56, 57, 30, 47] posit one constrained resource and T = 1. This is an easier problem, e.g., the best arm is the best distribution over arms.
2 Preliminaries: the problem, linear relaxation and UcbBwK algorithm
The bandits with knapsacks (BwK) problem is as follows. There are K arms, d resources, and T rounds. Initially, each resource j 2 [d] is endowed with budget Bj . In each round t = 1 , . . . , T , an algorithm chooses an arm at, and observes an outcome vector ot = (rt; c1,t , . . . , cd,t) 2 [0, 1]d+1, where rt is the reward, and cj,t is the consumption of each resource j. The algorithm stops when the consumption of some resource j exceeds its budget Bj , or after T rounds, whichever is sooner. We maximize the total reward, REW = P⌧ t=1 rt, where ⌧ is the stopping time. We focus on the stochastic version: for each arm a, there is a distribution Da over [0, 1]d+1 such that each outcome vector ot is 1Conceptually, our assumption of “best-arm-optimality" is replaced with another assumption: a lower bound on the positive entries of the optimal distribution x⇤ (parameter in Section 3.3 of [44]).
an independent draw from distribution Dat (which depends only on the chosen arm at). A problem instance consists of parameters (K, d, T ; B1 , . . . , Bd) and distributions (Da : arms a). Given a problem instance, the best dynamic policy benchmark OPTDP maximizes the total expected reward over all algorithms; it is used in all worst-case regret bounds. The best fixed distribution benchmark OPTFD, used in some of our results, maximizes the total expected reward over all algorithms that always sample an arm from the same distribution. The worst-case optimal regret rate is [16]:
OPTDP E[REW] = Õ( p K OPTDP + OPTDP p K/B ), B = minj2[d] Bj . (2.1)
Simplifications and notation. Following prior work, we make three assumptions without losing generality. First, all budgets are the same: B1 = . . . = Bd = B. This is w.l.o.g. because one can divide the consumption of each resource j by Bj/mini Bi; dependence on the budgets is driven by the smallest Bj . Second, resource d corresponds to time: each arm deterministically consumes B/T units of this resource in each round. It is called the time resource and denoted time. Third, there is a null arm, denoted null, whose reward and consumption of all resources except time is always 0.2
Like most prior work on BwK, we use O(·) notation rather than track explicit constants in regret bounds. This improves clarity and emphasizes the more essential aspects of analyses and results.
For n 2 N, let [n] = {1 , . . . , n} and n = {all distributions on [n]}. Let [K] and [d] be, resp., the set of all arms and the set of all resources. For each arm a, let r(a) and cj(a) be, resp., the mean reward and mean resource-j consumption, i.e., (r(a); c1(a) , . . . , cd(a)) := Eo⇠Da [o]. We sometimes write r = (r(a) : a 2 [K]) and cj = (cj(a) : a 2 [K]) as vectors over arms. Given a function f : [K] ! R, we extend it to distributions X over arms as f(X) := Ea⇠X [f(a)].
Linear Relaxation. Following prior work, we consider a linear relaxation:
maximize X · r such that X 2 [0, 1]K , X · 1 = 1
8j 2 [d] X · cj  B/T. (2.2)
Here X is a distributions over arms, the algorithm does not run out of resources in expectation, and the objective is the expected per-round reward. Let OPTLP be the value of this linear program. Then OPTLP OPTDP/T OPTFD/T [16]. The Lagrange function L : K ⇥ Rd+ ! R defined as follows:
L(X, ) := r(X) + P
j2[d] j [ 1 T/B cj(X), ]. (2.3)
where corresponds to the dual variables. Then (e.g., by Theorem D.2.2 in [17]):
min 0 max X2 K L(X, ) = max X2 K min 0 L(X, ) = OPTLP. (2.4)
The min and max in (2.4) are attained, so that (X⇤, ⇤) is maximin pair if and only if it is minimax pair; such pair is called a saddle point. We’ll use L( · , ⇤) to generalize reward-gap to BwK.
Algorithm UcbBwK. We analyze an algorithm from [3], defined as follows. In the LP (2.2), rescale the last constraint, for each resource j 6= time, as (B/T)(1 ⌘LP), where
⌘LP := 3 · ( p K/B log(KdT ) + K/B (log(KdT ))2 ). (2.5)
We call it the rescaled LP (see (C.1)). Its value is (1 ⌘LP) OPTLP. At each round t, the algorithm forms an “optimistic" version of this LP, upper-bounding rewards and lower-bounding consumption:
maximize P
a2[K] X(a) r + t (a) such that
X 2 [0, 1]K , P
a2[K] X(a) = 1
8j 2 [d] P
a2[K] X(a) c j,t(a)  B(1 ⌘LP)/T.
(2.6)
UcbBwK solves (2.6), obtains distribution Xt, and samples an arm at independently from Xt. The algorithm achieves the worst-case optimal regret bound in (2.1). The upper/lower confidence bounds r+t (a), c j,t(a) 2 [0, 1] are computed in a particular way specified in Appendix B. What matters to this paper is that they satisfy a high-probability event
0  r+t (a) r(a)  Radt(a) and 0  cj(a) c j,t(a)  Radt(a), (2.7) 2Choosing the null arm is equivalent to skipping a round. One can take an algorithm ALG that uses null, and
turn it into an algorithm that doesn’t: when ALG chooses null, just call it again until it doesn’t.
for some confidence radius Radt(a) specified below. This event holds, simultaneously for all arms a, resources j and rounds t, with probability (say) at least 1 log(KdT )T 4 . For a 6= null, we can take
Radt(a) = min( 1, p Crad/Nt(a) + Crad/Nt(a) ), (2.8)
where Crad = 3 · log(KdT ) and Nt(a) is the number of rounds before t in which arm a has been chosen. There is no uncertainty on the time resource and the null arm, so we define c
time, t(·) = B/T and Radt(null) = r+t (null) = c j,t(null) = 0 for all resources j 6= time.

heading: 3 Logarithmic instance-dependent regret bounds
text: We provide upper and lower bounds which amount to full characterization of logarithmic, instancedependent regret rates in BwK. We achieve O(log T ) regret under two assumptions: there is only one resource other than time (i.e., d = 2), and the best distribution over arms reduces to the best fixed arm (best-arm-optimality). We prove that both assumptions are essentially necessary for any algorithm, deriving complementary ⌦( p T ) lower bounds if either assumption fails. Both lower bounds hold in a wide range of problem instances; arguably, they represent typical scenarios rather than exceptions. All upper and lower bounds are against the best fixed distribution benchmark (OPTFD).
We achieve O(log T ) regret with UcbBwK algorithm [3], which implies two very desirable properties: the algorithm does not know in advance whether best-arm-optimality holds, and attains the optimal worst-case regret bound for all instances, best-arm-optimal or not. The positive result would have been weaker without either property, although still non-trivial.
We identify a suitable instance-dependent parameter, defined via Lagrangians from Eq. (2.3):
GLAG(a) := OPTLP L(a, ⇤) (Lagrangian gap of arm a), (3.1)
where ⇤ is a minimizer in Eq. (2.4). It is a non-obvious generalization of the reward-gap from multi-armed bandits, (a) = maxa0 r(a0) r(a). The Lagrangian gap of a problem instance is
GLAG := mina 62{a⇤,null} GLAG(a). (3.2)
Our regret bound scales as O(KG 1 LAG log T ), which is optimal in GLAG, under a mild additional assumption, and as O(KG 2
LAG log T ) otherwise.
3.1 O(log T ) regret analysis for UcbBwK
We analyze a version of UcbBwK which “prunes out" the null arm, call it PrunedUcbBwK. (This modification can only improve regret, so it retains the worst-case regret (2.1) of UcbBwK.) We provide a new analysis of this algorithm for d = 2 and best-arm-optimality. We analyze the sensitivity of the “optimistic" linear relaxation to small perturbations in the coefficients, and prove that the best arm is chosen in all but a few rounds. The key is to connect each arm’s confidence term with its Lagrangian gap. This gives us O(KG 2
LAG log T ) regret rate. To improve it to O(KG 1 LAG log T ), we use a careful
counting argument which accounts for rewards and consumption of non-optimal arms.
Algorithm PrunedUcbBwK is formally defined as follows: in each round t, call UcbBwK as an oracle, repeat until it chooses a non-null arm a, and set at = a. (In one “oracle call", UcbBwK outputs an arm and inputs an outcome vector for this arm.) The total number of oracle calls is capped at Nmax = ↵0 · T 2 log T , with a sufficiently large absolute constant ↵0 which we specify later in Claim 3.6. Formally, after this many oracle calls the algorithm can only choose the null arm. Definition 3.1. An instance of BwK is called best-arm-optimal with best arm a⇤ 2 [K] if the following conditions hold: (i) OPTLP = BT · r(a ⇤)/maxj2[d] cj(a ⇤), (ii) the linear program (2.2) has a unique optimal solution X⇤ supported on {a⇤, null}, and (iii) X⇤(a⇤) > 3 p B log(KdT )
T .
Part (ii) here is essentially w.l.o.g.;3 part (iii) states that the optimal value should not be tiny.
3Part (ii) holds almost surely given part (i) if one adds a tiny noise, e.g., ✏-variance, mean-0 Gaussian for any ✏ > 0, independently to each coefficient in the LP (2.2), as per Prop. 3.1 in [46]. To implement this, an algorithm can precompute the noise terms and add them consistently to observed rewards and consumptions.
We assume d = 2 and best-arm-optimality throughout this section without further mention. In particular, the linear program (2.2) has a unique optimal solution X⇤, and its support has only one arm a⇤ 6= null. We use c(a) to denote the mean consumption of the non-time resource on arm a. We distinguish two cases, depending on whether c(a⇤) is very close to B/T . Theorem 3.2. Fix a best-arm optimal problem instance with only one resource other than time (i.e., d = 2). Consider Algorithm PrunedUcbBwK with parameter ⌘LP  12 in (2.5). Then
(i) OPTFD E[REW]  O OPTFD B · , where := P a 62{a⇤,null} G 2 LAG (a) · log(KdT ).
(ii) Moreover, if |c(a⇤) B/T | > ⌦( /T ), then OPTFD E[REW]  O( P a 62{a⇤,null} G 1 LAG (a) log(KdT ) ). (3.3)
Eq. (3.3) optimally depends on GLAG(·): indeed, it does in the unconstrained case when Lagrangian gap specializes to the reward gap, as per the lower bound in [41]. In particular, Eq. (3.3) holds if GLAG > T 1/4 and |c(a⇤) B/T | > O(T 1/2). The constant in O(·) is 48 in both parts of the theorem; the analysis only suppresses constants from concentration bounds and from Lemma 3.3.

heading: 3.1.1 Basic analysis: proof of Theorem 3.2(i)
text: We analyze UcbBwK in a relaxed version of BwK, where an algorithm runs for exactly Nmax rounds, regardless of the time horizon and the resource consumption; call it Relaxed BwK. The algorithms are still parameterized by the original B, T , and observe the resource consumption.
We sometimes condition on the high-probability event that (2.7) holds for all rounds t 2 [Nmax], call it the “clean event". Recall that its probability is at least 1 O(log(KdT ))T 2 . We prove that the best arm a⇤ chosen in all but a few rounds. The crux is an argument about sensitivity of linear programs to perturbations. More specifically, we argue about sensitivity of the support of the optimal solution for the linear relaxation (2.2). Lemma 3.3 (LP-sensitivity). Consider an execution of UcbBwK in Relaxed BwK. Under the “clean event", Radt(a) 14 GLAG(a) for each round t and each arm a 2 supp(Xt) \ {a ⇤, null}.
Proof Sketch We use a standard result about LP-sensitivity, the details are spelled out in Appendix C. We apply this result via the following considerations. We treat the optimistic LP (2.6) a perturbation of (the rescaled version of) the original LP (2.2). We rely on perturbations being “optimistic" (i.e., upper-bounding rewards and lower-bounding resource consumption). We use the clean event to upper-bound the perturbation size by the confidence radius. Finally, we prove that
GLAG(a) = T B P j2[d] ⇤ jcj(a) r(a), (3.4)
and use this characterization to connect Lagrangian gap to the allowed perturbation size. ⌅ We rely on the following fact which easily follows from the definition of the confidence radius: Claim 3.4. Consider an execution of some algorithm in Relaxed BwK. Fix a threshold ✓ > 0. Then each arm a 6= null can only be chosen in at most O ✓ 2 log(KdT ) rounds t with Radt(a) ✓.
Corollary 3.5. Consider an execution of UcbBwK in Relaxed BwK. Under the clean event, each arm a 62 {a⇤, null} is chosen in at most N0(a) := O G 2 LAG (a) log(KdT ) rounds.
This follows from Lemma 3.3 and Claim 3.4. Next, the null arm is not chosen too often: Claim 3.6. Consider an execution of UcbBwK in Relaxed BwK. With probability at least 1 O(T 3), the following happens: the null arm cannot be chosen in any ↵0 T log(T ) consecutive rounds, for a large enough absolute constant ↵0. Consequently, a non-null arm is chosen in at least T rounds.
Proof Sketch Fix round t, and suppose UcbBwK chooses the null arm in N consecutive rounds, starting from t. No new data is added, so the optimistic LP stays the same throughout. Consequently, the solution Xt stays the same, too. Thus, we have N consecutive independent draws from Xt that return null. It follows that r(Xt) < 1/T with high probability, e.g., by (B.2). On the other hand, assume the clean event. Then r(Xt) (1 ⌘LP) OPTLP by definition of the optimistic LP, and consequently r(Xt) (1 ⌘LP) OPTDP/T . We obtain a contradiction. ⌅ Corollary 3.5 and Claim 3.6 imply a strong statement about the pruned algorithm.
Claim 3.7. Consider an execution of PrunedUcbBwK in the (original) BwK problem. With probability at least 1 O(T 2), each arm a 62 {a⇤, null} is chosen in at most N0(a) rounds, and arm a⇤ is chosen in T N0 remaining rounds, N0 := P a 62{a⇤,null} N0(a).
We take a very pessimistic approach to obtain Theorem 3.2(i): we only rely on rewards collected by arm a⇤, and we treat suboptimal arms as if they bring no reward and consume the maximal possible amount of resource. We formalize this idea as follows (see Appendix D for details).
For a given arm a, let REW(a) be the total reward collected by arm a in PrunedUcbBwK. Let REW(a | B0, T0) be the total reward of an algorithm that always plays arm a if the budget and the time horizon are changed to B0  B and T0  T , respectively. Note that
LP(a | B0, T0) := E[REW(a | B0, T0)] = r(a) ·min( T0, B0c(a) ). (3.5)
is the value of always playing arm a in a linear relaxation with the same constraints. By best-armoptimality, we have E[REW(a⇤ | B, T )] = OPTFD. We observe that
E[REW(a⇤ | B0, T0)] min{T0,B0}B · OPTFD. (3.6)
By Claim 3.7 there are at least B0 = B N0 units of budget and at least T0 = T N0 rounds left for arm a⇤ with high probability. Consequently,
E[REW] E[REW(a⇤)] E[REW(a⇤ | B0, T0)] Õ(1/T). (3.7) We obtain Theorem 3.2(i) by plugging these B0, T0 into Eq. (3.6), and then using (3.7).

heading: 3.1.2 Tighter computation: proof of Theorem 3.2(ii)
text: We re-use the basic analysis via Claim 3.7, but perform the final computation more carefully so as to account for the rewards and resource consumption of the suboptimal arms.
Let’s do some prep-work. First, we characterize REW(a⇤) in a more efficient way compared to Eq. (3.7). Let B(a), T (a) denote, resp., the budget and time consumed by PrunedUcbBwK when playing a given arm a. We use expectations of B(a) and T (a), rather than lower bounds:
E[REW(a)] = r(a) E[T (a)] = r(a) E[B(a)]c(a) = LP ( a | E[B(a)],E[T (a)] ) for each arm a. (3.8)
We prove Eq. (3.8) via martingale techniques, see Appendix D.5.
Second, we use a tighter version of Eq. (3.6) (see Appendix D.3): for any B0  B, T0  T
LP(a⇤ | B0, T0)] OPTFD · B0B / ⇣ max B T , c(a ⇤) ·max n B0 T0 , c(a⇤) o⌘ . (3.9)
Third, we lower-bound GLAG(a) in a way that removes Lagrange multipliers ⇤:
GLAG(a) ⇢ OPTFD/T r(a) if c(a⇤) < B/T , OPTFD · c(a)/B r(a) if c(a⇤) > B/T .
(3.10)
We derive this from Eq. (3.4) and complementary slackness, see Appendix D.4.
Fourth, let B0 = E[B(a⇤)] and T0 = E[T (a⇤)] denote, resp., the expected budget and time consumed by arm a⇤. Let N(a) = E[T (a)] be the expected number of pulls for each arm a 62 {a⇤, null}. In this notation, Eq. (3.8) implies that
E[REW] = P
a 62{a⇤,null} N(a) r(a) + LP(a ⇤ | B0, T0). (3.11)
Now we are ready for the main computation . We consider four cases, depending on how c(a⇤) compares with B/T and B0/T0. We prove the desired regret bound when c(a⇤) is either larger than both or smaller than both, and we prove that it cannot lie in between. The “in-between" cases is the only place in the analysis where we use the assumption that c(a⇤) is close to B/T .
Case 1: c(a⇤) < min(B/T ,B0/T0). Plugging in Eq. (3.9) into Eq. (3.11) and simplifying,
E[REW] P
a 62{a⇤,null} N(a) r(a) + OPTFD · T0/T . (3.12)
Re-arranging, plugging in T0 = T P a 6=a⇤ N(a) and simplifying, we obtain
OPTFD E[REW]  P a 62{a⇤,null} N(a) OPTFD T r(a)
(3.13)
 P
a 62{a⇤,null} N(a)GLAG(a) (by Eq. (3.10))
 O( P
a 62{a⇤,null} G 1 LAG (a) log(KdT ) ) (by Claim 3.7).
Case 2: c(a⇤) > max(B/T ,B0/T0). Plugging in Eq. (3.9) into Eq. (3.11) and simplifying, E[REW] P a 62{a⇤,null} N(a) r(a) + OPTFD · B0/B. (3.14) Re-arranging, plugging in B0 = B P a 6=a⇤ N(a) c(a), and simplifying, we obtain
OPTFD E[REW]  P a 62{a⇤,null} N(a) OPTFD B · c(a) r(a)
 P
a 62{a⇤,null} N(a)GLAG(a) (by Eq. (3.10)),
and we are done by Claim 3.7, just like in Case 1.
Case 3: B0/T0  c(a⇤)  B/T . Let us write out B0 and T0:
c(a⇤) B0 T0 = B
P a 62{a⇤,null} N(a) c(a)
T P a 62{a⇤,null} N(a) B T
✓ 1 1
B · P a 62{a⇤,null} N(a)
◆
B/T O( /T ), where is as in Theorem 3.2 (by Claim 3.7). Since c(a⇤)  B/T , we have 0  B/T c(a⇤)  O( /T ) which contradicts the premise.
Case 4: B/T  c(a⇤)  B0/T0. The argument is similar to Case 3. Writing out B0, T0, we have
c(a⇤)  B0 T0 = B
P a 62{a⇤,null} N(a)c(a)
T P a 62{a⇤,null} N(a)  B T (1 1T · P a 62{a⇤,null} N(a)) .
By Claim 3.7, c(a⇤)  B/T (1 +O( /T )). Therefore, 0  c(a⇤) B/T  O( /T ), contradiction.

heading: 3.2 Lower Bounds (for arbitrary algorithms)
text: We provide two lower bounds to complement Theorem 3.2: we argue that regret ⌦( p T ) is essentially inevitable if a problem instance is far from best-arm-optimal or if there are d > 2 resources.
We consider problem instances with three arms {A1, A2, null}, Bernoulli rewards, and d 2 resources, one of which is time; call them 3⇥ d instances. Each lower bound constructs two similar problem instances I, I 0 such that any algorithm incurs high regret on at least one of them.4 The two instances have the same parameters T,K, d,B, and the mean reward and the mean consumption for each arm and each resource differ by at most ✏; we call them ✏-perturbation of each other.
We start with an “original" problem instance I0 and construct problem instances I, I 0 that are small perturbations of I0. This is a fairly general result: unlike many bandit lower bounds that focus on a specific pair I, I 0, we allow a wide range for I0, as per the assumption below. Assumption 3.8. There exists an absolute constant cLB 2 (0, 1/3) such that:
1. r(Ai), cj(Ai) 2 [cLB, 1 cLB] for each arm i 2 {1, 2} and each resource j. 2. r(A2) r(A1) cLB and cj(A2) cj(A1) cLB +GLAG for every resource j 2 [d]. 3. B  cLB · T  OPTFD. 4. Lagrangian gap is not extremely small: GLAG cLB/ p T .
For a concrete example, let us construct a family of 3 ⇥ d problem instances that satisfy these assumptions. Fix some absolute constants ✏, cLB 2 (0, 1/3) and time horizon T . The problem instance is defined as follows: budget B = cLB T , mean rewards r(A1) = 1 cLB2 and r(A2) = 1 cLB ✏, mean consumptions c(A1) = cLB ✏ and c(A2) = 2cLB. Parts (1-4) of Assumption 3.8 hold trivially. One can work out that GLAG = ✏, so part (4) holds as long as ✏ cLB/ p T .
4A standard approach for lower-bounding regret in multi-armed bandits is to construct multiple problem instances. A notable exception is the celebrated ⌦(log T ) lower bound in Lai and Robbins [41], which considers one (arbitrary) problem instance, but makes additional assumptions on the algorithm.
Theorem 3.9. Posit an arbitrary time horizon T , budget B, and d resources (including time). Fix any 3⇥ d problem instance I0 which satisfies Assumption 3.8. In part (a), assume that d = 2 and I0 is far from being best-arm-optimal, in the sense that
There exists an optimal solution X⇤ such that X(A1) > 2c4LB/ p T and X(A2) cLB. (3.15)
In part (b), assume that d > 2. For both parts, there exist problem instances I, I 0, which are O ( 1/pT )-perturbations of I0, such that
Any algorithm incurs regret OPTFD E[REW] ⌦( c4LB p T ) on I or I 0 (3.16)
For part (a), instance I has the same expected outcomes as I0 (but possibly different outcome distributions); we call such problem instances mean-twins. For part (b), one can take I0 to be bestarm-optimal. For both parts, the problem instances I, I 0 require randomized resource consumption. Both parts follow from a more generic lower bound which focuses on linear independence of per-resource consumption vectors cj := ( cj(A1), cj(A2), cj(null) ) 2 [0, 1]3, resources j 2 [d]. Theorem 3.10. Posit an arbitrary time horizon T , budget B, and d 2 resources (including time). Fix any 3 ⇥ d problem instance I0 that satisfies Assumption 3.8 and Eq. (3.15). Assume that the consumption vectors cj , j 2 [d] are linearly independent. Then there are instances I, I 0 which are ✏-perturbations of I0, with ✏ = 2 c2LB/ p T , which satisfy (3.16). In fact, I is a mean-twin of I0.
Proof Sketch (see Appendix E for full proof). Let r(a) and c(a) 2 [0, 1]d be, resp., the mean reward and the mean resource consumption vector for each arm a for instance I0. Let ✏ = cLB/ p T .
Problem instances I, I 0 are constructed as follows. For both instances, the rewards of each nonnull arm a 2 {A1, A2} are deterministic and equal to r(a). Resource consumption vector for arm A1 is deterministic and equals c(A1). Resource consumption vector of arm A2 in each round t, denoted c(t)(A2), is a carefully constructed random vector whose expectation is c(A2) for instance I, and slightly less for instance I 0. Specifically, c(t)(A2) = c(A2) ·Wt/(1 cLB), where Wt is an independent Bernoulli random variable which correlates the consumption of all resources. We posit E[Wt] = 1 cLB for instance I, and E[Wt] = 1 cLB ✏ for instance I 0. Because of the small differences between I, I 0, any algorithm will choose a sufficiently “wrong" distribution over arms sufficiently often. The assumption in Eq. (3.15) and the linear independence condition are needed to ensure that “wrong" algorithm’s choices result in large regret. ⌅ The corollaries are obtained as follows. For Theorem 3.9(a), problem instance I0 trivially satisfies all preconditions in Theorem 3.10. Indeed, letting time be resource 1, the per-resource vectors are c1 = (0, 0, 1) and c2 = ( · , · , 0), hence they are linearly independent. For Theorem 3.9(b), we use some tricks from the literature to transform the original problem instance I0 to another instance eI0 which satisfies Eq. (3.15) and the linear independence condition. The full proof is in Section F.
4 Simple regret of UcbBwK algorithm
We define simple regret in a given round t as OPTDP/T r(Xt), where Xt is the distribution over arms chosen by the algorithm. The benchmark OPTDP/T generalizes the best-arm benchmark from stochastic bandits. If each round corresponds to a user and the reward is this user’s utility, then OPTDP/T is the “fair share" of the total reward. We prove that with UcbBwK, all but a few users receive close to their fair share. This holds if B > ⌦(T ) K, without any other assumptions. Theorem 4.1. Consider UcbBwK. Assume B ⌦(T ) and ⌘LP  12 . With probability 1 O(T
3), for each ✏ > 0, there are at most N✏ = O K ✏2 logKTd rounds t such that OPTDP/T r(Xt) ✏.
To prove Theorem 4.1, we consider another generalization of the “reward-gap", which measures the difference in LP-value compared to OPTLP. For distribution X over arms, the LP-gap of X is
GLP(X) := OPTLP V (X), where V (X) := (B/T) · r(X)/ maxj2[d] cj(X) . (4.1)
Here, V (X) is the value of X in the LP (2.2) after rescaling, so that OPTLP = supX V (X). Note that X does not need to be feasible for (2.2). It suffices to study the LP-gap because r(Xt)
V (Xt)(1 ⌘LP) for each round t with high probability. This holds under the “clean event" in (2.7), because Xt being the solution to the optimistic LP implies maxj cj(Xt) B/T (1 ⌘LP). Thus, we upper-bound the number of rounds t in which GLP(Xt) is large. We do this in two steps, focusing on the confidence radius Radt(Xt) as defined in (2.8). First, we upper-bound the number of rounds t with large Radt(Xt). A crucial argument concerns confidence sums:
P t2S Radt(at) and P t2S Radt(Xt), (4.2)
the sums of confidence radii over a given subset of rounds S ⇢ [T ], for, resp., actions at and distributions Xt chosen by the algorithm. Second, we upper-bound GLP(Xt) in terms of Radt(Xt). The details are spelled out in Appendix G.
5 Reduction from BwK to stochastic bandits
We improve all regret bounds for UcbBwK algorithm, from worst-case regret to logarithmic regret to simple regret, when the problem instance has some helpful structure. In fact, we provide a general reduction which translates insights from stochastic bandits into results on BwK. This reduction works as follows: if prior work on a particular scenario in stochastic bandits provides an improved upper bound on the confidence sums (4.2), this improvement propagates throughout the analyses of UcbBwK. Specifically, suppose P t2S Radt(at)  p |S| for all algorithms, all subsets of rounds S ⇢ [T ], and some instance-dependent parameter ⌧ K, then UcbBwK satisfies (i) worst-case regret OPTDP E[REW]  O( p T )(1 + OPTDP/B).
(ii) Theorem 3.2 holds with = G 2 LAG and regret O G 1 LAG in part (ii).
(iii) Theorem 4.1 holds with N✏ = O ✏ 2 .
Conceptually, this works because confidence sum arguments depend only on the confidence radii, rather than the algorithm that chooses arms, and are about stochastic bandits rather than BwK. The analyses of UcbBwK in [3] and the previous sections use = K, the number of arms. The confidence sum bound with = K and results (i, ii, iii) for stochastic bandits follow from the analysis in [10].
We apply this reduction to three well-studied scenarios in stochastic bandits: combinatorial semibandits [e.g., 25, 40, 39], linear contextual bandits [e.g., 9, 29, 43, 27, 2], and multinomial-logit (MNL) bandits [e.g., 7, 48, 51, 24]. The confidence-sum bounds are implicit in prior work on stochastic bandits, and we immediately obtain the corresponding extensions for BwK. To put this in perspective, each scenario has lead to a separate paper on BwK [resp., 49, 5, 26], for the worst-case regret bounds alone. We essentially match the worst-case regret bounds from prior work, and obtain new bounds on logarithmic regret and simple regret.5 The details are spelled out in Appendix H.
Another reduction from BwK to bandits, found in [35], is very different from ours. It requires a much stronger premise (a regret bound against an adaptive adversary), and only yields worst-case regret bounds. Moreover, it reuses a bandit algorithm as a subroutine, whereas ours reuses a lemma.

heading: 6 Discussion: significance and novelty
text: Characterizing (poly-)logarithmic regret rates is a very natural question, and we give a complete answer. The answer consists of positive and negative parts: the positive part requires substantial assumptions, and these assumptions are necessary. The positive result comes “for free" despite the assumptions: it is achieved via UcbBwK and without sacrificing the worst-case performance.
The O(log T ) regret result is well-motivated on its own, even though it requires d = 2 and best-armoptimality and a reasonably small K = #arms. Indeed, problems with d = 2 and small K arise in many motivating applications of BwK (see Appendix A), and capture the three challenges of BwK discussed in the Introduction. Moreover, best-arm-optimality is a typical, non-degenerate case. 6
5However, we do not provide a generic computationally efficient implementation. 6To make this point formal, we focus on d = 2 and observe that best-arm-optimality arises with probability at least p, for some absolute constant p > 0, if expected rewards and expected resource consumptions are drawn independently and uniformly at random. This is a generic fact about LPs, which follows, e.g., from the definition of primal degeneracy in Section 2 of [46], combined with Proposition 2.7.2 in [55].
For lower bounds in terms of Lagrangian gap GLAG, we rely on the ⌦(1/G · log T ) regret bound for bandits [41], where G is the reward-gap (since GLAG generalizes reward-gap). In particular, 1/GLAG scaling is optimal. No other instance-dependent lower bounds are known for BwK. However, Theorem 3.9 implies ⌦( p T ) regret for some “proper" instances of BwK (i.e., ones with resource consumption) that have small GLAG.
Simple regret is a standard performance measure in stochastic bandits, previously not studied for BwK. While our result requires B > ⌦(T ) K, this is the main “parameter regime" of interest in most/all prior work on BwK, and a necessity in an important subset of this work [19, 20, 59, 35]. In contrast with stochastic bandits, Theorem 4.1 does not imply logarithmic regret, as per our lower bounds.
The “reduction" result is conceptual rather than technical. We make the point that regret bounds for many extensions of BwK can be derived seamlessly, and identify a mathematical structure which drives these extensions (namely, a bound on confidence sums). In a way, we formalize the intuition that analyses of “optimism under uncertainty" are likely to carry over from stochastic bandits to BwK.
We introduce several new concepts and techniques: Lagrangian gap (3.1) for logarithmic regret, LP-gap (E.2) for analyzing simple regret, and the abstraction of confidence sums (4.2). Also, LPsensitivity arguments appear new in bandit analyses. Both new notions of “gap" satisfy the natural desiderata: they generalize reward-gap, separate the dependence on the problem instance from that on the time horizon T (formally: do not depend on T , fixing the B/T ratio), and are “productive", leading to improved results. However, neither notion captures all BwK instances with low regret.7
7This should not be surprising per se, as reward-gap does not capture all “nice" bandit instances either. E.g., problem instances with small reward-gap admit O(log T ) regret if they have a likewise small best reward.

Review summaries:
This paper tackles the Bandits with Knapsacks (BwK) problems, where the learner is not just looking for the arm with per-round maximal expected reward, but has to take into account the consumption of ressources that can end prematurely the whole process. While existing work on BwK have already characterized the worst-case regret scaling in sqrt(T), this paper provides additional theoretical guarantees: problem depend upper bounds in log(T) for a UCB-like algorithm called UcbBwK, lower bounds matching the worst-case rate, as well as guarantees on the simple regret. Finally, when the problem instance presents some specific structure (e.g. in combinatorial semi-bandit, linear contextual bandits, multinomial-logit bandits), all these bounds for UcbBwK are improved.

This paper studies the problem of bandits with knapsacks (BwK). In a BwK instance, there are $K$ arms and multiple types of resources with limited budgets, while in standard bandits there is only one resource time. Each pull of an arm returns a random reward and consumes a random amount of each resource. The pulling ends as soon as one of the resources runs out, and the goal is to maximize the cumulative reward before a resource runs out.   In particular, this paper focuses on the case (denoted as $C$) where there are only two types of resources and the optimal policy is always pulling some arm $a^*$. In this specific case, the authors showed a regret upper bound in the form of $O(\frac{K}{\Delta^2}\log{T})$ or $O(\frac{K}{\Delta}\log{T})$ under some conditions. The authors also showed that if $C$ does not hold, then no algorithm can do better than $\Omega(\sqrt{T})$ and thus, no logarithmic regret can be obtained.  The authors also studied the simple regret of BwK and showed that their algorithm can achieve $O(\log{T})$ simple regret. 

The paper introduces a new algorithm for the BwK Problem achieving $O(\log T)$ regret for a "best-arm-optimal" instance. The algorithm is based on a variant of UcbBwK. Moreover, they show $\Omega(\sqrt{T})$ lower bound and they provide a general reduction from BwK to stochastic bandits.  Pros: (i) Characterizing the problem-dependent lower bound by a new quantity, Lagrangian gap. In the language of linear programming (LP), this is related to minimal non-zero reduced cost for the underlying LP that does not include the null arm. (ii) Better bound. From certain "best-arm-optimal" instances, their regret bound is better than the existing work.  (iii) One-round performance. It shows that the rewards collected by UcbBwK are approximately optimal for all but a few rounds.   (iv) Reduction from BwK to stochastic bandits.