Bandits with Knapsacks beyond the Worst Case
Authors: Karthik Abinav Sankararaman
Aleksandrs Slivkins
Venue: NeurIPS 2021 Poster (2021)
Keywords: multi-armed bandits
theory of computation
online learning

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 well-understood, 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 prior work, providing new analyses thereof.


Bandits with Knapsacks beyond the Worst Case
Karthik Abinav Sankararaman Facebook AI, Menlo Park kabb
Aleksandrs Slivkins Microsoft Research, New York City slivkinssmicrosoott.. com
Abstract
Bandits with Knapsacks (BwK) is a general model for multi-armed bandits un- der supply/budget constraints. While worst-case regret bounds for BwK are well- understood, we present three results that go beyond the worst-case perspective. First, we provide upper and lower bounds which amount to a fuul characterization for logarithmic, mnstance-dependee regret" in BwK, which tracks algorithm's performance in given round, and prove that it is small in all but few rounds. Third, we provide general "reduction" " from BuK to bandits which takes advantage of some known helpful structure, and apply this reduction to combinatorial multinomial-logit bandits. Our results build on the BuK algorithm from Agrawal and Devanur [3], providing new analyses thereof.
regret rates. Second, we consider "simple
aani-bandits, linear contextual bandits, and
Introduction
We study multi-armed bandit problems with supply or budget constraints. Multi-armed bandits is simple model for exploration-eplooiatii 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, egg. 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 Each resource starts out with budget B;. In each round f, the algorithm chooses an action (arm) 0₂ from fixed set of K actions. The outcome 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 The algorithm observes bandit feedback, i.e., only the outcome of the chosen arm. The algorithm stops at known time horizon T,, when the total consumption of some resource exceeds its budget. The goal is to maximize the total reward, denoted REW.
resources that are consumed over time, one of which time itself.
vector in [0, 1]d+1; consists of a reward
known to the algorithm.
The presence of supply/budget constraints makes the problem much more challenging. First, algo- rithm's '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 the best distribution, denoted OPTpp- 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 min, B, = ((T).
BuK were introduced in [14, 16] and extensively studied since then. The optimal worst-case regret rate is well-understood. In particular, it is Ō(VKT) when B = 2(T).
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

We present several results that go beyond the worst-case perspective:
1. We provide full characterization for instance-dependent regret rates. In stochastic bandits, one obtains regret O K best and the second-best arm. We work out whether, when and how such results extend to BwK.
A log 7',, where A is the the reward-gaps the gap in expected reward between the
2. We show that simple regret, which tracks algorithm's 's performance in a given round, can be small all but a few rounds. Like stochastic bandits, simple regret can be at least in at most (K//e)) rounds, and this is achieved for all e > O 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 three well-studied scenarios from stochastic bandits.
Our algorithmic results focus on UcbBwK, a BuK 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 optimal as stated above [41, 10, 111, and is achieved simultaneously with the optimal worst-case regret (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 E... log (T)) / (a)) ) regret, where Aaa) 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, egg., linear bandits, convex bandits, Lipschitz bandits, and combinatorial (banii)aandit..
Bandits with Knapsacks were introduced in [14, 16], and optimally solved in the worst case. Subse- quent work extended BwK to more general notion of rewards/consumption [3], combinatorial semi- bandits [49], and contextual bandits [15, 6, 4]. Several special cases with budget/supply constraints were studied separately (and inspired generalization 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 (log T) regret 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 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-optimalllee reward-gap). However, their algorithm inputs instance-dependent parameter which is "hidden" in BuK. Moreover, their Olog T) regret bound scales with Cuinn minimal expected consumption among arms (as m. ). Their worst-case regret bound is suboptimal, since it also seales with Cmin (as mmjn), and only applies for d = 2. [58] study contextual version of BwK with two arms, 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 2 VT regret whenever our lower bounds apply: it is unclear when all their parameters small. No worst-case regret bounds are provided; their algorithm does not appear to achieve even ((T) regret in the worst case. Finally, [33, 56, 57, 30, 47] posit one constrained resource and T co. This is an easier problem, e.g., the best arm is the best distribution over arms.
as we do (it is implicit in their version of
of which
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 E [d] is endowed with budget By. In each round ( - 11, ... an algorithm chooses an arm de and observes an outcome vector o, = (rr; C1 where r; is the reward, and Cj.t is the consumption of each resource j. The algorithm stops when the consumption of some resource exceeds its budget By, or after T rounds, whichever is sooner. We maximize the total reward, REW Ei= Tı, where is the stopping time. We focus on the stochastic version: for each arm a. there is a distribution D, over [0. 1]d+1 such that each outcome vector o, is
Ca,,) E [0, 1]
'Conceptually, our assumption of "best- "resst-rmm--e arm optimalltllty"" is replaced with another assumption: a lower bound on the positive entries of the optimal distribution x² (parameter x in Section 3.3 of [44]).

---

an independent draw from distribution Da, (which depends only on the chosen arm at). A problem instance consists of parameters (K, ...... Ba) and distributions (Da arms a).
Given a problem instance, the best dynamic policy benchmark OPTpp maximizes the total expected reward over all algorithms; it is used in all worst-case regret bounds. The best fixed distribution benchmark OPT used in some of our results, maximizes the total expected reward over all algorithmss that always sample an arm from the same distribution. The worst-case optimal regret rate is [16]:
DPTpp [REW]] = Ō v K OPTop + OPTop ( ) B minjeid] By.
(2.1)
Simplifications and notation. Following prior work, we make three assumptions without losing generality. First, all budgets are the same: B1 ... Bg B. This is w.l.o.g. because can divide the consumption of each resource j by mi,; B;; dependence on the budgets is driven by the smallest B, Second, resource d corresponds 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
time: each arm deterministically consumes B B/T
Like most prior work on BuK, 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.
.n) and A, = fall 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 (a) be, resp., the mean reward and mean resource-j consumption, i.e., (r(a); ea (a).
For n E N, let [n] = {1,
, ca((a) == EowD, We [K]) as vectors over arms. Given
sometimes write function f [K] + R. we extend it to distributions X over arms as f(X) == Ea~x[[(a))
(r(a) E [K]) and cj = (c)(a)
Linear Relaxation. Following prior work, we consider a linear relaxation:
maximize
X.r X [o11k x-1=1 X e
such that
(2.2)
Vj E [d]
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
LF 2 pp 2 OPT / [16]. The Lagrange function L Ax x IR. -> R defined as follows:
((X, A) := rxx) + ΣjEW Ay[ - T/B ey (X), ].
(2.3)
where À corresponds the dual variables. Then (e.g., by Theorem D.2.2 in [17]):
min max C(X, A) = max min L(X, A) = OPT
(2.4)
X XEAR
XEAK X20
The min and max in (2.4) attained, that (X","² is maximin pair if and only if it is minimax
pair; such pair is called a saddle point. We'll use L( C(,,A*) ) to generalize reward-gap to BuK.
Algorithm UcbBwK. We analyze an algorithm from [3], defined as follows. In the LP (2.2), rescale the last constraint, for each resource & time, as (B/2) (1 - -)r)), where
Trr = 3- (K/BB log(K + K/B (log(KdT))²))
(2.5)
We call it the rescaled LP (see (C.1)). Its value is - (1-m))) OPT At each round 6, the algorithm forms an "optimistic" version of this LP, upper-bounding rewards and lower-bounding consumption:
maximize
Emelay X(a) (a)
such that
X E 11 Eee[K] X(a) =1
(2.6)
Vj [d]
EjelK] X(a) (a)()) S B(1 TTT
UcbBwK solves (2.6), obtains distribution X and samples an arm a, independently from X,, The algorithm achieves the worst-case optimal regret bound in (2. The upper/lower confidence bounds r. (a), G,((a) e [0, 1] are computed in a particular way specified in Appendix B. What matters to this paper is that they satisfy a high-pnu seahbbbrbbbbbitty event
0 < r r(a) (ad and 0 S cj(a) F,,(0 & (a),
(2.7)
CChossing 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 tt when ALG chooses null, just call again until it doesn't.
3

---

for some confidence radius (a) specified below. This event holds, simultaneously for all arms resources j and rounds t, with probability (say) least 1
log( K&T) For a o null, can take T
(a) min( 1, /raaa/ (2(a) + Craa/N((a))
(2.8)
where Crad 3 log (KdT) and (a) is the number of rounds before t in which arm has been chosen. There is uncertainty the time resource and the null arm, we define Grine, B/T and Rad, (null) r (null) Sza (mull) for all resources j * time.
Logarithmic instance-dependent regret bounds
We provide upper and lower bounds which amount to full characterization of logarithmic, instance- dependent regret rates in BuK. We achieve (loog 7') regret under two assumptions: there only one resource other than time (i.e., d = 2), and the best distribution over arms reduces to the best fixed arm prest-arm-ottimalttyy We prove that both assumptions are essentially necessary for any algorithm, deriving complementary Q2 (2vT) lower bounds if either assumption fails. Both lower bounds hold in 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 (OPTpp).
We achieve (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):
Ga)((a) == OPT1> L(a,
(Lagrangian gap of arm a).
(3.1)
where A is a minimizer in Eq. (2.4). It is non-obvious generalization of the reward- gap from multi-armed bandits, ((a) max,' r(a') r(a). The Lagrangian gap of problem instance is
GLaG == minag (a- mull] (a))
(3.2)
Our regret bound scales as OKG assumption, and as D(KG log T) otherwise.
LAG log 7), which is optimal in GLAGI under a mild additional
3.1 Olog 7) regret analysis for UcbBuK
We analyze version of UcbBwK which "prunes out" the null arm, call it PrunedUcbBuK. (This modification can only improve regret, so it retains the worst-case regret 1) of UcbBuX.) We provide new analysis of this algorithm for d = 2 and best-arm-oppimmaltty 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 few rounds. The key is connect each arm's confidence term with its Lagrangian gap. This gives us O(KG log I') regret rate. To improve it to O(K log T), counting argument which accounts for rewards and consumption of non-optimal arms.
a careful
Algorithm PrunedUcbBuK is formally defined as follows: in each round f, call UcbBwK as an oracle, repeat until chooses a non-null arm a, and set a; a. (In one "oracle call", UcbBwK outputs an arm and inputs outcome vector for this arm.) The total number of oracle calls is capped at Nnax = og T log T. with sufficiently large absolute constant ai 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 cest-arm-opiiee ann-optimal with best arm a" E [K] if the following conditions hold: (i) OPT,p = $ rr(a)) maxje[d] ca(",, (ii) the linear program (2.2) has a unique optimal solution X" supported on null), and (iii) X (*())> 3/B (oglog(aa)
Part (ii) here essentially w.l.o.g.." part (iii) states that the optimal value should not be tiny.
*Part (ii) holds almost surely given part (i) if one adds a tiny noise, e.g., e-variance, mean-O Gaussian for < > 0, independently to each coefficient in the LP (2.2), as per Prop. 3.1 in [46]. To implement this, an algorithm precompute the noise terms and add them consistently to observed rewards and consumptions.

---

We assume d = 2 and best-arm- -otaammllllttttttyyyy 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² * 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 best-arm optimal problem instance with only one resource other than time (i.e., d 2). Consider Algorithm PrunedUcb BuK with parameter The S in (2.5). Then
(i) OPT - E[REW I O
OPTe1 B
V where v ;= Eo swts) Grdd(a) log(KdT)).
(ii) Moreover. if lc(a") B/r) V (T), then
rP IE| REW S O Engla" mwil) (m11) Gzie(a) log(K )
(3.3)
Eq. (3.3) optimally depends on GLad()): 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 > 1/4 and lc(a*) - R/rl > ((2-)/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.
3.1.1 Basic analysis: proof of Theorem 3.2(i)
We analyze UcbBwK relaxed version of BwK, where an algorithm runs for exactly Nuax 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 E [Nmax] call it the "clean event". Recall that its probability is at least 1 Ollog( (Mlog(Kar)) (TT))
T
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- -.--ssiitiivit).. Consider execution of UcbBwK in Relaxed BwK. Under the "clean event", (a) 2 1/2 GLao(a) for each round t and each arm E supp(X,) X,) 1) {a", null].
Proof Sketch We use a standard result about -e-seiiitiiityy 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
GLaa (a)
T EjEt {īes(a) - r(a)),
(3.4)
B
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 + null can only be chosen in at most O (0-2 log K KdT)) ) rounds t. with Rade(a) 2 0.
Corollary 3.5. Consider an execution of UcbBuK in Relaxed BwK. Under the clean event, each arm É (a", null) is chosen in at most No(a) = O (Gzll(a log( (dT)) rounds.
This follows from Lemma 3.3 and Claim 3.4. Next, the null is not chosen often:
Claim 3.6. Consider an execution of Ucb in Relaxed BwK. With probability at least 1 - () the following happens: the null arm cannot be chosen in any oo T log(T') consecutive rounds, for large enough absolute constant Org. Consequently, a non-null arm is chosen in at least T rounds.
Proof Sketch Fix round 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 X, stays the same, too. Thus,
have N consecutive independent draws from X that return null. It follows that r(X, < 1/r with high probability, egg., by (B.2). On the other hand, assume the clean event. Then r r(x,) ,) > (1 'hpp)) OPTLe by definition of the optimistic LP, and consequently r r(X,) 2 (1 The) OPTpe T. We obtain a contradiction.
Corollary 3.5 and Claim 3.6 imply strong statement about the pruned algorithm.
5

---

Claim 3.7. Consider an execution of PrunedUcbBul in the (original) Buk problem. With probability at least )). each arm a & {a², nult) is chosen in at most Na(a) rounds, and arm is chosen in T No remaining rounds, No = Lag(ar mull) No(a).
We take a very pessimistic approach to obtain Theorem 3.2(): 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 given arm a, let (E)(a) be the total reward collected by Bo, To) be the total reward of an algorithm that always plays arm a if the budget and the time horizon changed to Bo < B and To T, respectively. Note that
in PrunedUcbBuK. Let REW(a
LP(a Bo, To) == (a Bo. To)] r(a) minn To: a(a) )
Bg
(3.5)
is the value of always playing arm a in linear relaxation with the same constraints. By best-arm- optimality, we have E BiREW(a" B, T)
OPT We observe that
E REW a=
Bu, Tu)l 2
min(TT..B] OPT
(3.6)
B
By Claim 3.7 there are at least Bo = B - No units of budget and at least To = T - NN, rounds left for a" with high probability. Consequently,
E REW] 2 [[]EE[a")] 2 B|REEW(" Bo, To)] Ö(/r).
(3.7)
We obtain Theorem 3.2(i) by plugging these Bu, To into Eq. (3.6), and then using (3.7).
3.1.2 Tighter computation: proof of Theorem 3.2(ii)
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 (a), T(a) denote, resp., the budget and time consumed by PrunedUcbBwK when playing given arm a. We use expectations of ((a) and T(a), rather than lower bounds:
E [R)] r(a) E[T(a)] = r(a) B[B(a]]
c(a)
(a E(
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 B, S B, S T
LP(a" Bo, To)) 2 OPT
Bo / /maxx
B. c(a)))) max To
c(caaa) c(aa))))
(3.9)
Third, we lower-bound GLaG (a) in way that removes Lagrange multipliers X":
if c(a") B/T, GLac(a) OPT c(a)/B r(a) if d(a) > B/T.
OPPmm/T--(0
(3.10)
We derive this from Eq. (3.4) and complementary slackness, see Appendix D.4.
Fourth, let Bu E[B(a*), and To Ea]) denote, resp., the expected budget and time consumed by arm a² Let (aa = (a) be the expected number of pulls for each arm a & {a", mul1). In this notation, Eq. (3.8) implies that
E [EEW] = Eag(a m01)) ((a) r(a) + LP(a") Bo, To)-
(3.11)
Now we are ready for the main computation . We consider four cases, depending on how c(a*) compares with B/T and Bo/To. 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 between. The "in-between" cases 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/r, Bo/1a). Plugging in Eq. (3.9) into Eq. (3.11) and simplifying,
REW 2 Eng(ar molll) N(a) r(a) + DPT To/T.
(3.12)

---

Re-arranging, plugging in To =T -oofa- N(a) and simplifying, we obtain
OPTpp E REW
- E aafla aull) [aa) ( ( - -r(a))
(3.13)
$ E (a mull) ((a) GLac(a)
(by Eq. (3.10))
1 0 Eas(a' m011] (a) log(KdT))
(by Claim 3.7).
Case 2: c(aa) max(B/1 Bo) Plugging in Eq. (3.9) into Eq. (3.11) and simplifying.
E [[EE 2 Eag(a' mmll) (N(a) r(a) OPT,p Bo/B.
(3.14)
Re-arranging, plugging in Bu B Enpor N(a) c(a), and simplifying, obtain
OPTиD E.[REW]
- Eag(ar mull]) ((a) (= c(a) r((a)
$ Sa mu11) (a) GLaG(a) (a)
(by Eq. (3.10)),
and we done by Claim 3.7, like in Case 1. Case 3: Bo/To I ddaa)= - B/r. Let write out Bo and To:
c(a") Bu
B- --Eagfe- amll) ((aa c(a)
B
( 1- BB" Eagfar mill) M(a)
1
To T Eugla" mmll) Maa)
T
2 B/T O ((T)), where as in Theorem 3.2
(by Claim 3.7).
Since c(a") _ B/T, we have s 8/T c(a") I OVV/T) which contradicts the premise.
Case 4: B/T S c(a") I Bo/To. The argument is similar to Case 3. Writing out Bo To, we have
Bu
B - Englar m011) (a)c((a)
c(a") <
T(I T(1- - Eagga mlll N(a)) By Claim 3.7, c(a") < B/T (1 O(V Therefore, 0 S c(a") - BBTT S 1 /T), contradiction.
To T La aml N(a)
3.2 Lower Bounds (for arbitrary algorithms)
We provide two lower bounds to complement Theorem 3.2: we argue that regret ((VTT) is essentially inevitable if problem instance is far from best-arm-optimal if there are d > 2 resources.
We consider problem instances with three arms (Ai, A2, mull], Bernoulli rewards, and 2 resources, one of which is time; call them 3 x d instances. Each lower bound constructs two similar problem instances I, I' such that any algorithm incurs high regret on at least one of them. 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 e; we call them e-perturbation of each other.
We start with an "original" problem instance To and construct problem instances I, I' that are small perturbations of To. This a fairly general result: unlike many bandit lower bounds that focus on specific pair I. I', we allow a wide range for Iy. as per the assumption below.
Assumption 3.8. There exists an absolute constant CLB (0, 1/3) such that:
r r(A,), (A,, E [CLB. 1- 1-cral C.a) for each arm E {1,2] and each resource j.
r(A2) - -T(Ai) cLs and c2(A2) eg (Ai) 2 CLa frr every resource j E [d].
3. B < CLB T T OPT
Lagrangian gap is not extremely small: GLaG caa/VT.
For a concrete example, let us construct family of x problem instances that satisfy these assumptions. Fix some absolute constants e, CLa E (0, 1/s) and time horizon T. The problem instance is defined follows: budget B
T. mean rewards r( r(Ar) 1-qa and r((A) = 1
mean consumptions c(A,) = CLs e and c(A2) = 201s- Parts (1-4) of Assumption 3.8 hold trivially. One can work out that GLAG = c, so part (4) holds as long as e 2 CL./VT.
regret in multi-armed bandits is to construct multiple problem instances, A notable exception is the celebrated Q(log 7') lower bound in Lai and Robbins [41], which considers (arbitrary) problem instance, but makes additional assumptions the algorithm.
A standard approach for Nower-bounding
7

---

Theorem 3.9. Posit an arbitrary time horizon T. budget B, and d resources (including time). Fix any d problem instance In which satisfies Assumption 3.8. In part (a), assume that d = 2 and To is far from being best-arm- best-arm-oplimal, in the sense that
There exists an optimal solution X" such that X(A)) > /VT and ((2) 2 CLB
(3.15)
In part (b), assume that d > 2. For both parts, there exist problem instances I, I', which are O 1TV pperturbations of To, such that
Any algorithm incurs regret 0PT,0 E R|REV| 2 2 G. VT on I or I'
(3.16)
For part (a), instance I has the same expected outcomes as Io (but possibly different outeome distributions); we call such problem instances mean-twins. For part (b), one can take To to be best- arm-optimal. For both parts, the problem instances I, 'I' require randomized resource consumption.
Both parts follow from a more generic lower bound which focuses on linear independence of per-resource consumption vectors Cj == (cş(Ai), cy(A2), (g(nll)) E [o, 1js, resources j [d].
Theorem 3.10. Posit arbitrary time horizon T, budget B, and d 2 2 resources (including time). Fix any 3 x d problem instance To that satisfies Assumption 3.8 and Eq. (3.15). Assume that the consumption vectors Cj, j E [d] are linearly independent. Then there are instances I,I I' which are c-perturbations To, with 2c2./ VT, which satisfy (3.16). fact, a mean-twin of Io-
Proof Sketch (see Appendix E for full proof). Lea)(a) and c(a) E [0, 11 be, resp., the mean reward and the mean resource consumption vector for each arm a for instance Zo. Let = CLB/VI
Problem instances I, I'' are constructed as follows. For both instances, the rewards of each non- null arm a E (A1, A2} are deterministic and equal to r(a). Resource consumption vector for arm A1 is deterministic and equals c(Ar). Resource consumption vector of arm Ag in each round t, denoted C(e) (A2), is a carefully constructed random vector whose expectation is c(Az) for instance I. and slightly less for instance T'. Specifically, C(t) (A2) c(A2) W1/(1 CLB). where W, is an independent Bernoulli random variable which correlates the consumption of all resources. We posit E[W,]= CLa for instance I, and [[[;] =1- Cъв for instance I'.
Because of the small differences between I, 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 's choices result in large regret.
The corollarie are obtained as follows. For Theorem 3.9()), problem instance To trivially satisfies all preconditions Theorem 301 Indeed, letting time be resource 1, the per-resource vectors are C1 = (0, 0, 1) and C₂ (.. 0), hence they are linearly independent. For Theorem 3.9(b), we use some tricks from the literature to transform the original problem instance Io to another instance To 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 ( as OPTp:/T-r(X where X, is the distribution over arms chosen by the algorithm. The benchmark OPT /T generalizes the best-arm benchmark from stochastic bandits. If each round corresponds to user and the reward is this user's 's utility, then OPT /T is the "fair share" of the total reward. We prove that with UcbBwK, all but 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 2 I(T)) and Tur S 1. With probability 2 1 O)
for each 0, there are at most N. O ( log KTd) rounds t such that OPTpp/ /T - r rXx,)
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/r) r(X)/ (max,e(4) C (X))
(4.1)
Here, V(X) is the value of X in the LP (2.2) after rescaling, so that OPT2, = supx V(X). Note that X does not need to be feasible for (2.2). It suffices study the LP-gap because r r(X,) 2
8

---

(1 - [ for each round t with high probability. This holds under the "clean event" in (2.7), because X, being the solution to the optimistic LP implies max, Cy (X,, 2 B/r (hp)
Thus, we upper-bound the number of rounds t in which GLe( Xx) is large. We do this in two steps, focusing on the confidence radius Rad, (X,) defined in (2.8). First, we upper-hound the number of rounds t with large Rad, (X²). A crucial argument concerns confidence sums:
Eies (ado(ar) and ELes (Xd,(X.).
(4.2)
the sums of confidence radii over given subset of rounds S C [TT, for, resp., actions as and distributions X₂ chosen by the algorithm. Second, we upper-bound (1)(X,) in terms of Rad;(X,) The details are spelled out in Appendix G.
5 Reduction from BuK to stochastic bandits
We improve all regret bounds for UcbBuK algorithm, from worst-case regret to logarithmic regret to simple regret, when the problem instance has some helpful structure. In fact, we provide general reduction which translates insights from stochastic bandits into results on BuK. This reduction works follows: if prior work a particular scenario in stochastic bandits provides improved upper bound on the confidence sums (4.2), this improvement propagates throughout the analyses of UcbBwK. Specifically, suppose Enes (ad)(a,) < v B [S] for all algorithms, all subsets of rounds S C [T], and some instance-dependent parameter B < K, then UcbBwK satisfies
worst-case regret OP E|REW] < ((V + DPTpr [3. Theorem 3.2 holds with V = 3 G and regret O G/G in part (ii).
iiii Theorem 4.1 holds with N. = O (B
Conceptually, this works because confidence sum arguments depend only 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 3 = K, the number of arms. The confidence sum bound with 3 = 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 semi- bandits (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.² The details are spelled out in Appendix H.
Another reduction from BuK bandits, found in [35], is very different from ours. requires a much stronger premise (a regret bound against an adaptive adversary), and only yields worst-case regret bounds. Moreover, reuses a bandit algorithm as subroutine, whereas ours reuses lemma.
Discussion: significance and novelty
Characterizing Jlogrithhi 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 UcbBuK and without sacrificing the worst-case performance.
The Ollog T) regret result is well-motivated on own, even though it requires d = and best-arm- optimality and reasonably small K = #arms. Indeed, problems with d = 2 and small K arise in many motivating upplications of BwK (see Appendix A), and capture the three challenges of BwK discussed in the Introduction. Moreover, best-arm-optimality is typical, non-degenerate case.
'However, we do not provide generic computationally efficient implementation. 'To make this point formal, we focus 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, egg., from the definition of primal degeneracy in Section 2 of [46], combined with Proposition 2.7.2 in [55].
2 and observe that best-am optiimalllly arises with probability

---

For lower bounds in terms of Lagrangian gap GLAG- we rely on the Ω(// log T') regret bound for bandits [41], where G is the reward-gap (since GLaC generalizes reward-gap). In particular, 1/GLaC scaling is optimal. No other instance-dependenn lower bounds are known for BuK. However, Theorem 3.9 implies (TVT) regret for some "proper" instances of Bwk (i.e., ones with resource consumption) that have small GLag.
Simple regret is standard performance measure in stochastic bandits, previously not studied for BwK. While our result requires B > (2(T)) >>>>> K, this the main "parameter regime" " of interest in most/all prior work on BuK, 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 mathematical structure which drives these extensions (namely, bound on confidence sums). In way, we formalize the intuition that analyses of "optimism under uncertainty" are likely 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, LP- sensitivity arguments appear new in bandit analyses. Both new notions of "gap" satisfy the natural desiderata: they generalize reward-gapp 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."
"This should not be surprising per se, as reward-gay gap does not capture all "nice" bandit instances either. E.g., problem instances with small reward-gap gap admit O(log I') regret if they have likewise small best reward.
10

---

References
[1] Yasin Abbasi-Yauen Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in Neural Information Processing Systems (NIPS), 24:2312 2320, 2011.
[2] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. 25th Advances Neural Information Processing Systems (NIPS), pages 2312-2320, 2011.
[3] Shipra Agrawal and Nikhil R. Devanur. Bandits with concave rewards and convex knapsacks. In 15th ACM Conf. on Economics and Computation (ACM-EC), 2014.
[4] Shipra Agrawal and Nikhil R. Devanur. Linear contextual bandits with knapsacks. In 29th Advances in Neural Information Processing Systems (NIPS), 2016.
[5] Shipra Agrawal and Nikhil R Devanur, Linear contextual bandits with knapsacks. Advances in Neural Information Processing Systems, 2016.
[6] Shipra Agrawal, Nikhil R. Devanur, and Lihong Li. An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives. In 29th Conf. Learning Theory (COLT), 2016.
[7] Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. Mnl-bandit: A dynamic learning approach to assortment selection. Operations Research, 6755):1433-1485 2019. Prelinimary version in ACM EC 2016.
[8] J.-Y. Audibert, R. Munos, and Cs. Szepesvári. Exploration-exploitationn trade-off using variance estimates in multi-armed bandits. Theoretical Computer Science, 410:1876-1902 2009.
[9] Peter Auer. Using confidence bounds for exploitation-exxloraiion trade-offs. J. of Machine Learning Research (JMLR), 3:397 422, 2002. Preliminary version 4/st IEEE FOCS, 2000.
[10] Peter Auer, Nicolò Cesa-Bianchi and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2-3):235-2555 2002.
[11] Peter Auer, Nicolò multiarmed bandit problem. SIAM J. Comput., 32(1):48-77, 2002. Preliminary version in 36th IEEE FOCS, 1995.
Yoav Freund, and Robert E. Schapire. The nonstochastic
[12] Moshe Babaioff, Shaddin Dughmi, Robert D. Kleinberg, and Aleksandrs Slivkins. Dynamic pricing with limited supply. ACM Trans. on Economics and Computation, 3(1):4, 2015. Special issue for 13th ACM EC, 2012.
[13] Ashwinkumar Badanidiyura, Robert Kleinberg, and Yaron Singer. Learning budget: posted price mechanisms for online procurement. In 1 13th ACM Conf. on Electronic Commerce (ACM-EC), pages 145, 2012.
[14] Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knap- sacks. In 54th IEFE Symp. on Foundations of Computer Science (FOCS), 2013.
[15] Ashwinkumar Badanidiyura, John Langford, and Aleksandrs Slivkins. Resourceful contextual bandits. In 27th Conf. on Learning Theory (COLT), 2014.
[16] Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knap- sacks. J. of the ACM, 63:3):13:1 2018. Preliminary version in FOCS 2013.
[17] Ahron Ben-Tal and Arkadi Nemirovski. Lectures on modern convex optimization: analysis, algorithms,, and engineering applications, volume 2. Siam, 2001.
[18] Dimitris Bertsimas and John N Tsitsiklis. Introduction linear optimization, volume 6. 1997.
[19] Omar Besbes and Assaf Zeevi. Dynamic pricing without knowing the demand function: Risk bounds and near-optimal algorithms. Operations Research, 1706:1407-1 2009.
11

---

[20] Omar Besbes and Assaf J. Zeevi. Blind network revenue management. Operations Research, 60(6):1537-1550, 2012.
[21] Jean Bourgain, Van H Vu, and Philip Matchett Wood. On the singularity probability of discrete random matrices. Journal of Functional Analysis, 258(2):559-66) 2010.
[22] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[23] Sébastien Bubeck and Nicolo Cesa-Bianche Regret Analysis of Stochastic and Nonstochas- tic Multi-armed Bandit Problems. Foundations and Trends Machine Learning. 5(1): 1-122, 2012. Published with Now Publishers (Boston, MA. USA). Also available at https://arrn www../orggabb//////// /00b///224..04 5721.
[24] Felipe Caro and Jérémie Gallien. Dynamic assortment with demand learning for seasonal consumer goods. Management Science, 53(2):276 292, 2007.
[25] Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit: General framework and applications. In 20th Intl. Conf. on Machine Learning (ICML), pages 151-159,, 2013.
[26] Wang Chi Cheung and David Simchi-Levi. known multinomial logit choice models, 2017.
Assortment optimization under Technical report, available at
http://arxis org brg/abs//en /tbb//704.000 1010000088.....
00108.
[27] Wei Chu, Lihong Li, Lev Reyzin, and Robert E. Schapire. Contextual Bandits with Linear Payoff Functions. In 14th Intl. Conf. on Artificial Intelligence and Statistics (AISTATS), 2011.
[28] 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.
[29] Varsha Dani, Thomas P. Hayes, and Sham Kakade. Stochastic Linear Optimization under Bandit Feedback. In 21th Conf. on Learning Theory (COLT), pages 355-366, 2008
[30] Wenkui Ding, Tao Qin, Xu-Dong Zhang, and Tie- Yan Liu. Multi-armed bandit with budget constraint and variable costs. In 27th AAAI Conference on Artificial Intelligence (AAAI), 2013.
[31] Arthur Flajolet and Patrick Jaillet. Logarithmic regret bounds for bandits with knapsacks. arXiv preprint arXiv:1510.01800 2015.
[32] Aurélien Garivier and Olivier Cappé. The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond. In 24th Conf. on Learning Theory (COLT), 2011.
[33] András György, Levente Koesis, Ivett Szabó, and Csaba Szepesvári. Continuous time associative bandit problems. 20th Intl. Joint Conf. on Artificial Intelligence (IJCAI), pages 830-835, 2007.
[34] Junya Honda and Akimichi Takemura. An asymptotically optimal bandit algorithm for bounded support models. 23rd Conf. on Learning Theory (COLT), 2010.
[35] Nicole Immorlica, Karthik Abinav Sankararaman, Robert Schapire, and Aleksandrs Slivkins. Adversarial bandits with knapsacks. J. of the ACM, 2021. To appear. Preliminary version in 60th IEEE FOCS, 2019.
[36] Thomas Kesselheim and Sahil Singla. Online learning with vector costs and bandits with knapsacks. In 33rd Conf. on Learning Theory (COLT), pages 2286-2305, 2020.
[37] Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Multi-armed bandits in metric spaces. In 40th ACM Symp. on Theory of Computing (STOC), pages 681-690, 2008
[38] Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Bandits and experts in metric spaces. J. of the ACM, (0(4):30:1-30:77) May 2019. Merged and revised version of conference papers ACM STOC 2008 and ACM-SIAM SODA 2010. Also available at
12

---

[39] Branislav Kveton, Zheng Wen, Azin Ashkan, Hoda Eydgahi, and Brian Eriksson. Matroid bandits: Fast combinatorial optimization with learning. In 13th Conf. on Uncertainty in Artificial Intelligence (UAI), pages 420-429, 2014.
[40] Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvári. Tight regret bounds for stochastic combinatorial semi-bandits. In 18th Inil. Conf. on Artificial Intelligence and Statistics (AISTATS), 2015.
[41] Tze Leung Lai and Herbert Robbins. Asymptotically efficient Adaptive Allocation Rules. Advances in Applied Mathematics, 6:4-22, 1985.
[42] Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, Cam- bridge, UK, 2020. Versions available at https: //////nnnnaaa.......///.. com/ since 2018.
[43] Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. A contextual- bandii approach to personalized news article recommendation. 19th Int. World Wide Web Conf. (WWW), 2010.
[44] Xiaocheng Li, Chunlin Sun, and Yinyu Ye. The symmetry between arms and knapsacks: A primal-dual approach for bandits with knapsacks. In 38th Intl. Conf. on Machine Learning (ICML), 2021.
[45] Odalric-Ambrym Maillard, Rémi Munos, and Gilles Stoltz. A finite-time analysis of multi- armed bandits problems with kullback-leibler divergences. In 24th Conf. on Learning Theory (COLT), 2011.
[46] Nimrod Megiddo and R Chandrasekaran. On the-perturbation method for avoiding degeneracy. In Tech. Report, IBM Almaden Research Center, San Jose, CA, 1988.
[47] Anshuka Rangi, Massimo Franceschetti, and Long Tran-Thanh. Unifying the stochastic and the adversarial bandits with knapsack. In 28th Intl. Joint Conf. on Artificial Intelligence (IJCAI), pages 3311-3317, 2019.
[48] Paat Rusmevichientong, Zuo-Jun Max Shen, and David B Shmoys. Dynamic assortment optimization with a multinomial logit choice model and capacity constraint. Operations research, 586)) 2010.
[49] Karthik Abinav Sankararaman and Aleksandrs Slivkins. Combinatorial semi-bandits with knapsacks. In Intl. Conf. Artificial Intelligence and Statistics (AISTATS), pages 1760-1770, 2018.
[50] Denis Sauré and Assaf Zeevi. Optimal dynamic assortment planning with demand learning. Manufacturing & Service Operations Management, 15(3):387-40) 2013.
[51] Denis Sauré and Assaf Zeevi. Optimal dynamic assortment planning with demand learning. Manufacturing & Service Operations Management, 15(3):387-404 2013.
[52] Adish Singla and Andreas Krause. Truthful incentives in crowdsourcing tasks using regret minimization mechanisms. In 22nd Inil. World Wide Web Conf. (WWW), pages 1167-1178, 2013.
[53] Aleksandrs Slivkins. Dynamic ad allocation: Bandits with budgets. A technical report on hwt.://rrg/abs///aa/a aws.aa//...0 0155, June 2013.
arxiv. orxiv.org/aae
[54] Aleksandrs Slivkins. Introduction to multi aamdd bandits. Foundations and Trends in Machine Learning, 12(1-2):1-286, November 2019. Published with Now Publishers (Boston, MA, USA). Also available at
abs9044 1904. 07272. Latest online revision: June 2021.
[55] Terence Tao. Topics in random matrix theory, volume 132. American Mathematical Soc., 2012.
[56] Long Tran-Thanh, Archie Chapman, Enrique Munoz de Cote, Alex Rogers, and Nicholas R. Jennings. 6-first policies for budget-limited multi-armed bandits. In 24th AAAI Conference on Artificial Intelligence (AAAI), pages 1211-1216, 2010.
13

---

[57] Long Tran- Thanh. Archie Chapman, Alex Rogers, and Nicholas R. Jennings, Knapsack based optimal policies for budget-limited multi-armes bandits. 26th AAAI Conference on Artificial Intelligence (AAAI), pages 1134-1140, 2012.
[58] Alberto Vera, Siddhartha Banerjee, and Itai Gurvich. Online allocation and pricing: Constant regret via bellman inequalities. Operations Research, 2020.
[59] Zizhuo Wang, Shiming Deng, and Yinyu Ye. Close the gaps: A leaniig--while-diing algorithm for single-product revenue management problems. Operations Research, 62(2):318 -3111, 2014.
[60] Zheng Wen, Branislav Kveton, and Azin Ashkan. Efficient learning large-scale combinatorial semi-bandits. In International Conference on Machine Learning, pages 1113-1122 122, 2015.
[61] Huasen Wu, R. Srikant, Xin Liu, and Chong Jiang, Algorithms with logarithmic or sublinear regret for constrained contextual bandits. In 28th Advances in Neural Information Processing Systems (NIPS), 2015.
14


Reviews:
[{"review_id": "gaUZ8MRr4Cy", "reviewer": "Reviewer_3DAX", "summary": "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.\n\nPros:\n(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.\n(ii) Better bound. From certain \"best-arm-optimal\" instances, their regret bound is better than the existing work. \n(iii) One-round performance. It shows that the rewards collected by UcbBwK are approximately optimal for all but a few rounds.  \n(iv) Reduction from BwK to stochastic bandits.\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Given the merits summarized above, I have the following concerns:\n\nThe recent work [44] studies the BwK problem under a more general setting without the best-arm-optimal condition. It would be helpful to present a comparison of the bound in this paper and the bound therein (when reduced to a best-arm-optimal instance). \n\nThere might be some issues with the lower bound proof:\n(i) The second line on the inequalities at the bottom of page 22 might not hold. First, intuitively, for an algorithm that only plays non-null arms at the last few rounds, $V({Y})$ can be larger than $V({X}^*)$ in those rounds since during those rounds, the resources average budget is more than the initial average budget and scaled average budget. Second, theoretically, in the proof of E.4, it seems that authors assume that the policy ${Y}$ at each round must be a feasible solution to the LP corresponding to ${X}^*$ (thus the performance of ${Y}$ can not be better than $V(X^*)$ in that step). However, the average budget in a step can be larger than the initial average budget. Thus, even if ${Y}$ and ${X}^*$ are different, $V({Y})$ can still be larger than $V({X}^*)$ in this case.\n\n(ii) The first paragraph of Appendix F might require more clarifications. First, it seems unclear why the perturbation on $r$ and ${C}$ is equivalent to perturbing the vector ${b}$ in general. More importantly, Proposition 3.1 in [46] only provides a sufficient condition that small perturbation can help a degenerate LP to become non-degenerate. Authors might need more explanation on how the perturbation can render an LP from non-degenerate to degenerate (reversely from [46]). ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no negative societal impact that I can see. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Rnt4-wrbIyK", "reviewer": "Reviewer_Ueua", "summary": "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.\nWhile 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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- The paper is nicely written and contains extensive discussion on the related literature.\n- Strong theoretical guarantees are provided for the BwK problem.\n- Unfortunately, no numerical experiments are provided to illustrate some mathematical claims. For instance, it would be interesting to verify empirically the relation between the parameter \" beta \" (line 326), the number of arms K, and the regret. In practice, how large can beta be?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": " ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "FxmZf5Vkkj", "reviewer": "Reviewer_9Bz5", "summary": "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. \n\nIn 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.\n\nThe authors also studied the simple regret of BwK and showed that their algorithm can achieve $O(\\log{T})$ simple regret. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The logarithmic regret of BwK has been a difficult problem, and there are only a very few works that have focused on this topic. To the best of my knowledge, this work is the first to obtain a logarithmic regret with i) more than one type of resource and ii) random or non-deterministic regrets. When one of i) or ii) does not hold, then previous works have shown logarithmic regrets, but when both of them are true, then this work is the first. However, I do not find a lot of novelty in the algorithm design and this specific case may be limited in practice. \n\nThis paper is not quire well written as there are too many notations. Perhaps the authors can try simplifying or hiding some of the notations in the next version. \n\nIn my opinion, the logarithmic lower bound of BwK is also difficult, but it would be better if the authors can provide some results on the lower bound. It is not clear whether $G_{\\mbox{LAG}$ is a good or tight enough gap for deriving the regret. \n\nThus, I will vote a 6 for this submission. This work has significant contribution to a specific case, the contribution is limited in practice and lacks the justification that this result is good enough. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See the comments in the box Main Review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper investigates the bandits with knapsack (BwK) problem. It extends the state of the art by looking beyond the worst case regret analysis and provides logarithmic regret upper and lower bounds, first of their kinds. The second contribution of the paper is the analysis of BwK from the simple regret's perspective. Here the authors have proved that for any $\epsilon > 0$, apart from $O(K/\epsilon^2)\log(KTd))$ time steps, this simple regret is typically smaller than $\epsilon$. The final main contribution of the paper is the new proving concept that helps converting proof techniques from the classical bandit to the BwK setting, making the regret analysis in the BwK domain more seamless. Apart from this, the paper also introduces a number of new gap concepts and proof techniques.

As someone quite familiar with the BwK literature, I find this paper to be fascinating. If any weaknesses I need to mention then perhaps the denseness of the paper. It was a bit difficult to follow all the new concepts and terms. However, overall I find the amount of novelty and new ideas compensate this weakness.

From the reviewers' comments I can conclude that they also (more or less) share my judgement that this is a good paper. It is quite unfortunate that the reviewers were not involved in the discussion with the authors in a more active way to further elaborate on the strengths and weaknesses of the paper. Nevertheless, none of the reviewers did mention any reasons for rejecting this paper. Therefore, I recommend it to be accepted as a poster. 

Decision: Accept (Poster)