Non-monotonic Resource Utilization in the Bandits with Knapsacks Problem
Authors: Raunak Kumar
Robert Kleinberg
Venue: NeurIPS 2022 Accept (2022)
Keywords: multi-armed bandits
regret
knapsack constraints

Abstract: Bandits with knapsacks (BwK) is an influential model of sequential decision-making under uncertainty that incorporates resource consumption constraints. In each round, the decision-maker observes an outcome consisting of a reward and a vector of nonnegative resource consumptions, and the budget of each resource is decremented by its consumption. In this paper we introduce a natural generalization of the stochastic BwK problem that allows non-monotonic resource utilization. In each round, the decision-maker observes an outcome consisting of a reward and a vector of resource drifts that can be positive, negative or zero, and the budget of each resource is incremented by its drift. Our main result is a Markov decision process (MDP) policy that has constant regret against a linear programming (LP) relaxation when the decision-maker knows the true outcome distributions. We build upon this to develop a learning algorithm that has logarithmic regret against the same LP relaxation when the decision-maker does not know the true outcome distributions. We also present 
a reduction from BwK to our model that shows our regret bound matches existing results.

Non-monotonic Resource Utilization in the Bandits with Knapsacks Problem
Raunak Kumar
Robert D. Kleinberg
Department of Computer Science
Department of Computer Science
Cornell University Ithaca, NY 14853 Saunkk@ss.cornee edu
Coreell University Ithaca, NY 14853
rdkêcs. cornell. edu
Abstract
Bandits with knapsacks (BwK) [6] is influential model of sequential decision- making under uncertainty that incorporates resource consumption constraints. each round, the decision-maker observes outcome consisting of reward and a vector of nonnegative resource consumptions, and the budget of each resource is decremented by its consumption. this paper introduce natural generalization of the stochastic BwK problem that allows non monooono resource utilization. In each round, the decision-maker observes an outcome consisting of reward and a vector of resource drifts that can be positive, negative or zero, and the budget of each resource is incremented by its drift. Our main result is Markov decision process (MDP) policy that has constant regret against a linear programming (LP) relaxation when the decision-mall maker knows the true outcome distributions. We build upon this to develop a learning algorithm that has logarithmic regret against the same LP relaxation when the decision-maker does not know the true outcome distributions. We also present reduction from BwK to our model that shows our regret bound matches existing results [14].
Introduction
Multi-armed bandits are the quintessential model of sequential decision-making under uncertainty in which the decision-maker must trade-off between exploration and exploitation. They have been studied extensively and have numerous applications, such as clinical trials, ad placements, and dynamic pricing name a few. We refer the reader to Bubeck and Cesa-Bianchi [7], Slivkins [17], Lattimore and Szepesvári [13] for an introduction to bandits. An important shortcoming the basic stochastic bandits model is that it does not take into account resource consumption constraints that are present in many of the motivating applications. For example, in a dynamic pricing application the seller may be constrained by limited inventory of items that can out well before the end of the time horizon. The bandits with knapsacks (BwK) model [18, 19, 5, 6] remedies this by endowing the Decision-maker with some initial budget for each of resources. In each round, the outcome a reward and a vector of nonnegative resource consumptions, and the budget of each resource is decremented by its consumption. The process ends when the budget of any resouree becomes nonpositive. However, even this formulation fails to model that in many applications resources can get replenished renewed time. For example, in dynamic pricing application seller may receive shipments that increase their inventory level.
Contributions In this paper we introduce natural generalization of BwK by allowing non- monotonic resource utilization. The decision-maker starts with some initial budget for each of m resources. In each round, the outcome is reward and vector of resource drifts that can be positive, negative or zero, and the budget of each resource is incremented by its drift. negative drift has
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the effect of decreasing the budget akin to consumption in BwK and positive drift has the effect of increasing the budget. We consider two settings: (i) when the decision-main
knows the true outcome distributions and must design a Markov decision process (MDP) policy; and (ii) when the decision-maker does not know the true outcome distributions and must design a learning algorithm.
Our main contribution is an MDP policy, ControlBudget that has constant regret against a linear programming (LP) relaxation. Such a result was not known even for BwK. We build upon this to develop a learning algorithm, www.loreTeenCCoooooBBBee
Not known
ween for Bak
Tocal exsested reward
FTCH
cn
DPT
IP
(ETCB), that has logarithmic regret against the same LP relaxation. We also present a reduction from BwK to our model and show that our regret bound matches existing results.
o(logT)
Instead of merely sampling from the optimal probability distribution over arms, our policy samples from a perturbed distribution to ensure that the budget of each resource stays close to a decreasing sequence of thresholds. The sequence is chosen such that the expected leftover budget a constant and proving this is a key step in the regret analysis. Our work combines aspects of related work on logarithmic regret for BwK [9. 14].
Related Work Multi-armed bandits have rich history and logarithmic instance-dependee regret bounds have been known for a long time [12, 3]. Since then, there have been numerous papers extending the stochastic bandits model in a variety of ways [4, 16, 11, 6, 10, 2, 1].
To the best of our knowledge, there are three papers on logarithmic regret bounds for BwK. Flajolet and Jaillet [9] showed the first logarithmic regret bound for BwK. In each round, their algorithm finds the optimal basis for optimistic version of the LP relaxation, and chooses arms from the resulting basis to ensure that the average resource consumption stays close to pre-specified level. Even though their regret bound is logarithmic in T' and inverse linear in the suboptimality gap, is exponential in the number of resources, Li et al. [14] showed an improved logarithmic regret bound that is polynomial in the number of resources, but scales inverse quadratically with the suboptimality gap and their definition of the gap is different from the one in Flajolet and Jaillet [9]. The main idea behind improving the dependence on the number of resources to proceed in two phases: (i) identify the set of arms and binding resources in the optimal solution; (ii) in each round, solve an adaptive, optimistic version of the LP relaxation and sample an arm from the resulting probability distribution. Finally, Sankararaman and Slivkins [15] show a logarithmic regret bound for BwK against a fixed-distribution benchmark. However, the regret of this benchmark itself with the optimal MDP policy can be as large as O(VT) [9, 14].
Preliminaries
2.1 Model
Let T' denote a finite time horizon, x= (l...., k} set of k arms, J = =1, (1,...,,,, denote a set of m resources, and Bo, = B denote the initial budget of resource j. In each round E [T], if the budget of any resource is less than 1, then X; = {1}. Otherwise, X; = X. The algorithm chooses an arm x, X₂ and observes an outcome o = (r,, di, dr,m) [0, x 1| The algorithm earns reward and the budget of resource j E J is incremented by drift dr,5 as B = B,- + de.j.
Each arm x E X' has an outcome distribution over [0, [-1, and is drawn from the outcome distribution of the arm T4. We use /22 = (/% / "..."....... ...... (...m) to denote the expected outcome vector of arm I consisting of the expected reward and the expected drifts for each the m resources.' We also use d (nd
X)) to denote the vector of expected drifts for resource j. We assume that arm σ0 1 E is a null arm with three important properties: drift for each resource is nonnegative a.s.; and (iii) the expected drift for each resource is positive.
(i) its reward is zero a.s.; (ii) the
'In fact, our proofs remain valid even if outcome distribution depends on the past history provided the conditional expectation is independent of the past history and fixed for each arm. In this case μ denotes the conditional expectation of o, when arm x is pulled in round t. Since our proofs rely on the Azuma- Hoeffiding inequality, we need this assumption on the conditional expectation to hold.

---

The second and third properties of the null arm plus the model's 's requirement that = if 3j s.t. B,- ensure that the budgets are nonnegative a.s. and can be safely increased from O.
Our model is intended to capture applications featuring resource renewal, such as the following. In each round, each resource gets replenished by some random amount and the chosen consumes some random amount of each resource. If the consumption is less than replenishment, the resource gets renewed. The random variable di,j then models the net replenishment minus consumption. The full model presented above is more general because it allows both the consumption and replenishment depend on the arm pulled.
We consider two settings in this paper.
MDP setting The decision-maker knows the true outcome distributions. In this setting the model implicitly defines an MDP, where the state is the budget vector, the actions are arms, and the transition probabilities are defined by the outcome distributions of the arms.
Learning setting The decision-maker does not know the outcome distributions.
The goal is to design to an MDP policy for the first setting and a learning algorithm for the second, and bound their regret against an I.P relaxation as defined in the next subsection.
2.2 Linear Programming Relaxation
Similar to Badanidiyuru et al. [6, Lemma 3.1], we consider the following LP relaxation that provides an upper bound on the total expected reward of any algorithm:
OPT p = max
Σ ZEX
PaPl
EpOlE BBT,jE 2. DEX
-
20VEEX.. (1)
ZEX
Lemma 2.1. The total expected reward of any algorithu is at most T OPTLP
The proof of this lemma, similar to those in existing works [2, 6). follows from the observations that (i) the variables p {p= E X} can be interpreted as the probability of choosing and (ii) we set Pa equal to the expected number of times x is chosen by an algorithm divided by T, then it is a feasible solution for the LP.
in round;
Definition 2.1 (Regret). The regret of an algorithm A is defined as (r = - LP REW(AA). where REW(AA) denotes the total expected reward of A.
2.3 Assumptions
We assume that the initial budget of every resource is B T. This assumption is without loss of generality because otherwise we can scale the drifts by dividing them by the smallest budget. This results in smaller support set for the drift distribution that is still contained in [-1,
Our assumptions about the null arm o are major difference between our model and BwK. In BwK the budgets can only decrease and the process ends when the budget of any resource reaches O. However, in our model the budgets can increase or decrease, and the process ends the end of the time horizon. Our assumptions about the null arm allow to increase the budget from 0 without making it negative.
side-effect this is that in our model we can even assume that B is a small constant because we can always increase the budget by pulling the null arm, in contrast to existing literature on BwK that assume the initial budgets are large and often scale with the time horizon.
A standard assumption for achieving logarithmic regret in stochastic bandits is that the gap between the total expected reward of an optimal arm and that of second-best arm is positive. There are few different ways in which one could translate this to our model where the optimal solution is a mixture over arms. We make the following choice. We assume that there exists unique set of arms X* that form the support set of the LP solution and unique set of resources J that correspond to binding
In model where, each round, each resource gets replenished by some random amount and the chosen arm consumes some random amount of each resource, the null arm represents the option to remain idle and do nothing while waiting for resource replenishment. See Appendix A for more discussion on the assumptions about the null arm.
3

---

constraints in the LP solution [14]. We define the gap of the problem instance in Definition 4.1 and our uniqueness assumption" implies that the gap strictly positive.
We make a few separation assumptions parameterized by four positive constants that can be arbitrarily small. First, the smallest magnitude of the drifts, oann min [u2-11 E X J), satisfies darift > O. Second, the smallest singular value of the LP constraint matrix, denoted by minn satisfies Third, the LP solution p" satisfies Pz: Osupport > 0 for all x X*. Fourth, Exex- p 2 Ostack > 0 for all resources j & J The first assumption is necessary for logarithmic regret bounds because otherwise one can show that the regret of the optimal algorithm for the case of one resoure and one zero-drift arm is ( (Appendix B). The second and third assumptions are essentially the same as in existing literature on logarithmic regret bounds for BwK [9. 14]. The fourth assumption allows us to design algorithms that can increase the budgets of the non-binding resources away from O, thereby reducing the number of times the algorithm has to pull the null arm. Otherwise, if they have zero drift, then, as stated above, the regret of the optimal algorithm for the case of one resource and one zero-drift arm is @(vT) (Appendix B).
Omin Omin
3 MDP Policy with Constant Regret
In this section we design an MDP policy, ControlBudget (Algorithm 2), with constant regret in terms of T for the setting when the learner knows the true outcome distributions and our model implicitly defines an MDP (Section 2.1). At a high level, CondrolBudget, which shares similarities with Flajolet and Jaillet [9, Algorithm UCB-Simplex| plays arms to keep the budgets close to decreasing sequence of thresholds. The choice of this sequence allows us to show that the expected leftover budgets and the expected number of null arm pulls are constants. This is a key step in proving the final regret bound. We start by considering the special case one resource in Section 3.1 because it provides intuition for the general case of multiple resources in Section 3.2.
3.1 Special Case: One Resource
Since there is only one resource we drop the superscript in this section. We say that an arm æ is a positive (resp. negative) drift arm if p > 0 (resp. nd < 0). The following lemma characterizes the possible solutions of the LP (Eq. (1)).
The solution of the LP relaxation (Eq. (1)) is supported on at most arms. Fur- thermore, T 2 B/bsa, then the solution belongs to one of three categories: (i) supported on single positive drift arm; (ūi) supported on the null arm and negative drift arm; (iii) supported on positive drift arm and a negative drift arm.
Lemma 3.1.
The proof of this lemma follows from properties of LPs and case analysis of which constraints tight. Our MDP policy, ControlButt BBudget (Algorithm 1), deals with the three cases separately and satisfies the following regret bound.*
Theorem 3.1. Ifc 8 the MDP policy Control (Algorithm 1) satisfies
6
(r(ControlBudget) S Õ
where č (5 In (1--exp) exp
(-
+ S (1 e1-exp (82 (82n))) ) is constant.
We defer all proofs in this section to Appendix C, but we include a proof sketch of most results in the main paper following the statement. The proof of Theorem 3.1 follows from the following sequence of lemmas.
Lemma 3.2. If the LP solution is supported on a positive drift arm x", then
Ry (Contro (eattrr S Č,
"This assumption is essentially without loss of generality hecause the set of problem instances with multiple optimal solutions is set of measure zero.
'In this theorem and the rest of the paper, we use Ò to denote constant that depends on problem parameters, including k m. and the various separation constants mentioned in Section 2.3, but does not depend on T. We this notation because the main focus of this work how the regret scales a function of T.

---

Algorithm 1: ControlBudget (for m = 1)
Input: time horizon T, initial budget B, set of arms X, of resources J, constant 0.
Set Bo = =B.
LP solution is supported on positive drift arm x? then
for t = 1,2,..., T do
Bt-1 1, pull x". Otherwise, pull xP. end
else if I.P solution is supported on null arm x and negative drift arm x² then for t = 1, ................................ do
Define threshold T, clog(T If B.-1 ma Tr), pull xº. Otherwise, pull x". end
10
11
else L.P solution is supported on positive drift arm x and negative drift arm x" then
for 1,2.....2 do
13
Define threshold 7, clog(T - -t).
14
B < 1, pull x. If 1 < B < To, pull x?. Otherwise, pull xt
end 15
drgs In ((1-cxp) exp (- 82
))
))")
where Č ==
Jnn
is constant.
We can write the regret in terms of the norm of (Eu=), where Eur is the expected difference between the number of times x" is played by the LP and by ControlBudget. This is equal to the expected number of times the policy plays the null arm and, in turn, is equal the expected number of rounds which the budget is below 1. Since both x and x have positive drift, this is a transient random walk that drifts away from O. It is known that such walk spends constant number of rounds in any state in expectation.
Lemma 3.3. If the I.P solution supported on the null amm x and a negative drift arm x", then
Br(ControlBuuger) S Ō CE[BB].
where Č 0(6mg) is a constant.
We can write the regret terms of the norm of < (Ego, Ern), where & is the expected difference between the number of times is played by the LP and by ControlBudget. Since both constraints (resource and sum-to-one) are tight, the lemma follows by writing D and taking norms, where D is the LP constraint matrix and b (-E[Br],0).
Lemma 3.4. If the LP solution is supported on a positive drift amm xº and a negative drift arm x", then
Ri( Contro s Ō max (ax) E[N,o]
(5)
where , denotes the expected number null arm pulls and Č (5 is constant.
This lemma follows similarly to the previous one by writing regret in terms of the norm of g (Ex,, and writing { = D-11, for b [[ E[Noo))
Therefore, proving that (Control ) is a constant in T' requires proving that both the expected leftover budget and expected number of null arm pulls are constants. Intuitively, ensure E Br] is small by playing the negative drift arm whenever the budget is at least 1. However, there is constant probability of the budget decreasing below 1 and the expected number of null arm pulls becomes (T)) ControlBudgee choosing decreasing sequence of thresholds т, The threshold is initially far from to ensure low probability of pre-mature resource depletion, but decreases to 0 over time to ensure small expected leftover budget and decreases rate that ensures the expected number of null pulls is constant.
could
solves the tension between the two objectives by carefully
Lemma 3.5. If the LP solution is supported on positive drift arm x and a negative drift arm x", and e _ then
[[Noo] Õ
(6)
5

---

((1-aa)) cxp (-& driji
))) a constant.
where č==
8 In
If the budget is below the threshold, i.e., B;-1 < for some then Contro Budget pulls xP until B, 2 Te+1 for some s 2 t. Since x" has positive drift, the event that repeated pulls decrease the budget towards is low probability event. Using this, choice of clog(T' t) for appropriate constant e, and summing over all rounds shows that the expected number of rounds in which the budget is less than 1 is constant in T.
Lemma 3.6. If the LP solution is supported on two arms, and c 2 82
then
E[ S SC
where C. = ((1 ((1- exp (damg))
& is constant.
If Bt-1 2 Tr, then ControlBudget pulls negative drift arm r". We can upper bound the expected leftover budget by conditioning on 9, the number consecutive pulls of x" at the end of the timeline. The main idea in completing the proof is that (i) if q is large, then it corresponds to low probability event; and (ii) if q is small, then the budget round sequence in and there are few rounds left so the budget cannot increase by too much.
was smaller than Tg. which is decreasing
3.2 General Case: Multiple Resources
Now we use the ideas from Section 3.1 to tackle the case of m > resources that much more challenging. Generalizing Lemma 3.1, the solution of the LP relaxation (Eq. (1)) is supported on at most min k, m arms. Informally, our MDP policy, controlBudger (Algorithm 2), samples an arm from probability distribution that ensures drifts bounded away from in the "correct directions": (i) a binding resource has drift at least 7/ Bt-15 < Tr and drift at most -7t Bt- 2 Tri and (ii) a non-binding resource ý has drift at least 5 B, тτ. This allows us to show that expected leftover budget for each binding resource and the expected number of null arm pulls are constants in terms of
Algorithm 2: ControlBudget (for general m)
Input: time horizon T. initial budget B, set of arms X, of resources J, constant >> 0.
Set Bo,, B for all j E J.
Define threshold Tt log(T -t). t).
3 for / = 1, 2..,...777 T do
if 3j I such that B then
Pull the null arm _.".
else
Define s, (=1)1X*1-1 0 as follows. Let denote the resource corresponding row
i [| in the matri D and vector b. Then, the ith entry of s is +1 if
Bi-1, < Tj and -1 otherwise.
Define Tt to be the solution to the following constrained optimization problem:
max { 0
D
0, p VjE if < <t) (8)
Sample an arm from the probability distribution p: = D= (()))))
10 end
end
Theorem 3.2. Ifc x the regret of Controla Luddee (Algorithm 2) satisfies
Rr (r(CottoolBudge)) S
(9)
where 7"' (defined in Lemma 3.9) and are constants with Ò O (mo_il (m(7"))311) ((11 - exp (- -) + exp(rx2))- )))

---

We defer all proofs in this section to Appendix D, but we include a proof sketch of most results in the main paper following the statement. The proof of Theorem 3.2 follows from the following sequence of lemmas. The next two lemmas are generalizations of Lemmas 3.3 and 3.4 with essentially the same proofs. Recall J denotes the unique set of resources that correspond binding constraints in the IP solution (Section 2.3).
Lemma 3.7. If the LP solution includes the null arm x in its support, then
RT( Rrr(ControlBudge S SO.
Σ
(10)
JEJ
where C= 0( is constant.
Lemma 3.8. If the LP solution does not include the null arm x. in its support, then
Ri (ControlBudget) Sc-
Σ
E[Br,]l B[Na.)]
(11)
JEJ
where [0] denotes the expected number of null arm pulls and Č ((mmin)) is a constant.
Lemmas 3.10 and 3.11 are generalizations of Lemmas 3.5 and 3.6 with similar proof' after taking union bound over resources. But we first need Lemma 3.9 that lets conclude there is drift of magnitude at least y > 0 in the "correct directions" as stated earlier.
Lemma 3.9. [9, Lemma 14] each round I, "tt 2 2
Emin min 6aspprrr Sctack
4m
The proof of this lemma is identical to Flajolet and Jaillet [9, Lemma 14] but we provide proof in appendix for completeness.
Lemma 3.10. If the LP solution does not include the null arm in its support, then
E[Nao] S C
(12)
where = (m((')) (((7)-311 ((a- (-²))
constant.
Lemma 3.11. the L.P solution is supported more than one arm, then for all J
B[Brsl
(13)
== Ō= ( -2 (17)-2 is constant.
where č
exp(?>2))
A subtle but important point is that the regret analysis does not require ControlBudget to know the true expected drifts order to find the probability vector Pt- simply requires the algo- rithm to know _'* and find any probability vector Pt that ensures drifts bounded away from 0 in the "correct directions" as stated earlier. We use this property in our learning algorithm, Explore@hhenControlBBee
(Algorithm 3), in the next section.
4 Learning Algorithm with Logarithmic Regret
(Algorithm 3), with logarithmic regret in terms of I' for the setting when the learning does not know the true distributions. Our algorithm, which can be viewed as combining aspects of Li et al. [14, Algorithm I] and Flajolet and Jaillet [9, Algorithm UCB-Simples [14, Algorithm 1] to identify the set of optimal arms X* and the set of binding constraints J" by playing arms round-robin fashion, and using confidence intervals and properties of LPs. This is reminiscent of successive elimination [8], except that the algorithm tries to identify the optimal arms instead eliminating suboptimal ones. the second phase the algorithm continues playing the arms in X in round-robin fashion to shrink the confidence radius further. In the third phase the algorithm plays a variant of the MDP policy ControlBudget (Algorithm 2) with slighly different optimization problem for % because it only has empirical esitmates of the drifts.
In this section we design a learning algorithm, EepploreeThenContro.BB.
proceeds in three phases. It uses phase one of Li al.
7

---

4.1 Additional Notation and Preliminaries
For all arms E X' and rounds / 2 k. define the upper confidence bound (UCB) of the expected
outcome vector 24 as UCB,(z) (z(x) rad)(r), where rade (x) /n, T denotes the confidence radius, nz(2)) denotes the number of times æ has been played before and or(x) =
(x) E, (x, z=| denotes the empirical mean outcome vector of z. The lower confidence bound (LCB) defined similarly as (cB,(z) = oz (z) rad) (z))
For all arms 2 E X, let OPT denote the value of the LP relaxation (Eq. (I)) with the additional constraint Px: 0, and for resources j E J. OPT denote the value when the objective has an extra - Ex Pu + #/T term [14]. Intuitively, these represent how important
play arm or make the resource constraint for j binding constraint. Define the UCB of OPT zz to be the value of the LP when the expected outcome is replaced by its UCB, and denote this by UCB,(OPT_:) The LCB for OPT -a.- and UCB and LCB for OPT and OPT are defined similarly.
Definition 4.1 (Gap [14]). The gap the problem instance is defined
A = min
min m
{OPT - OPT min {OPTLP OPT-1]
(14)
Learning Algorithm and Regret Analysis
Algorithm ExplooreThennonttrolBuggge
Input: time horizon T, initial budget B, set of arms X, set of resources J, constant e > 0.
Set Bo, B for all j E J.
Initialize t = X = J = 0.
3 while < 7 & and [X* + +|]| <
Play each arm in X {x²) ) in round-robin fashion. Play x if Ej such that Bt- 1. For each x E X, UCB, -a) < LOPT then add x to X For each j E J, if UCPT -) LPPT). then add J'.
end
8
Set J = J'.
while f. < T | and nz(2) < 32 for all X", where 7 is defined in Lemma 3.9 do
10
Play each arm in X in a round-robin fashion.
11 end
12
while
L < do
13
3j E I such that B then
Pull the null arm _
15
else
16
Define s, in Algorithm 2.
17
Choose (7e, Pt) max such that there exists probability vector satisfying
LCB, (1 (6 2
g Vj E
Jf < T6:
(15)
(C (pFPdd) 2 Vje J" Bf <
(16)
(p" (d))) Jf
(17)
18
Sample an arm from the probability distribution pt.
end
end
Theorem 4.1. Ifc 2 6,
3, the regret of PappooreTheeCCossrolBB.ue (Algrassrrooouuuuggegogggooooroo (Algorithm 3) satisfies
BrgBBppooorTTheenCommrroLLLssgg Ć log
(18)

---

where y (defined in Lemma 3.9), C and Ć are constants with C¹ denoting the constant in Theo- rem 3.2 and
km2 I 142 -k(x-)-2+ Ō² )
Ö Ō= m Sagg
(19)
We defer all proofs in this section to Appendix E, but we include a proof sketch of most results in the main paper following the statement. We refer to the three while loops of ExploreehhenCatrolBBBgg
(Algorithm 3) the three phases. The lemmas and corollaries following the theorem below show that the first phase consists of at most logarithmic number of rounds. It is easy to see that the second phase consists of at most logarithmic number of rounds. The third phase plays a variant of the MDP policy ControlBudget (Algorithm 2). There exists feasible solution to the optimization problem in Line 17 that ensures drifts bounded away from in the "correct directions" (Appendix E.3). Combining the analysis of the first two phases with Theorem 3.2 lets conclude that harplorrTThenContoolBBoeo
has logarithmic regret.
Definition 4.2 (Clean Event), The clean event is the event such that for all E X and all t 2 k. (i) 1 E (LCB,(x) (x),, (x)); and (ii) after the first n pulls of the null arm the sum of the drifts for each 2u
resource is at least where 4096km² log T and 6m
Lemma 4.1. The clean event occurs with probability at least 5m7
The lemma follows from the contributes Om to the regret, it suffices to bound the regret conditioned on the clean event.
inequality. Since the complement of the clean event
Lemma 4.2. If the clean event occurs, then UCB, (OPTLL) LCB,( S statement is true for OPT and -pT-jfor all x E and j E J.
omin rad,. similar
The proof follows from perturbation analysis of the LP and uses the confidence radius to bound the perturbations the rewards and drifts.
Corollary 4.1. If the clean event occurs and n²(x)
2048m' log for all X, then a A
UCP. < LCB,(OPTLP) and (CB,()PT_)) < LCB.(OPTLp)
(20)
for all x E X jnd j E \
This follows from substituting the bound (x(x) into the definition of rad,(x)) and apply- ing Lemma 4.2. In the worst case, each pull of an arm can cause the budget to drop below 1, but the clean event implies that the first pulls of d0 have enough total drift allow n²(x) pulls of each non-null arm in phase 1. This allows us to upper bound the duration of phase I as follows.
Corollary 4.2. If the clean event occurs, then phase 1 of Eap ExploreTTenCCntte Budgee has at most
Ö log T
(21)
rounds, where Ö 0
km
is a constant.
iin Age o2 min
A
4.3 Reduction from BwK
Theorem 4.2. Suppose 1 2 Sarig- Consider BwK instance such that for each arm and resource, the expected consumption of that resource differs from by least 8arg: and (ii) all the other assumptions required by Theorem 4.1 (Section 2.3) are also satisfied. Then, there is an algorithm for BwK whose regret satisfies the same bound as in Theorem 4.1 with the same constant C.
Due to space constraints, we present the reduction in Appendix E.4.
Conclusion
In this paper we introduced natural generalization of BwK that allows non-monotonic resource utilization. We first considered the setting when the decision-maker knows the true distributions and presented an MDP policy with constant regret against LP relaxation. Then considered

---

the setting when the decision maker does not know the true distributions and presented a learning algorithm with logarithmic regret against the same LP relaxation. Finally, we also presented reduction from BwK to our model and showed a regret bound that matches existing results [14].
An important direction for future research is to obtain optimal regret bounds. The regret bound for our algorithm scales as O(poly(A (k) poly (ooly(m) A 3), where k is the number of arms, m is the number of resources and A is the suboptimality parameter. A modification to our algorithm along the lines of Flajolet and Jaillet [9, algorithm UCB-Simplex] that considers each support set of the LP solution explicitly leads to a regret bound that scales as ((poly(k)) A 1²)). It is an open question, even for BwK, to obtain a regret bound that scales as ((poly(k) (polyyy)))) A-') or show that the trade-off between the dependence on the number of resources and the suboptimality parameter is unavoidable.
Another natural follow-up to our work is to develop further extensions, such as considering an infinte set of arms [11], studying adversarial observations [4, 10], or incorporating contextual information [16, 1] as has been the case elsewhere throughout the literature on bandits.
Acknowledgments and Disclosure of Funding
We thank Kate Donahue, Sloan Nietert, Ayush Sekhari, and Alex Slivkins for helpful discussions. This research was partially supported by the NSERC Postgraduate Soooaarships-Doctore Fellowship 545847-2020.
References
[1] Shipra Agrawal and Nikhil Devanur. Linear contextual bandits with knapsacks. Advances in Neural Information Processing Systems, 29, 2016.
[2] Shipra Agrawal and Nikhil R Devanur. Bandits with concave rewards and convex knapsacks. In Proceedings of the fifteenth ACM conference on Economics and computation, pages 989-1006, 2014.
[3] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-256, 2002.
[4] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-77, 2002.
[5] Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knap- sacks. In 2013 IEEE 54th Annual Symposium Foundations of Computer Science, pages 207-216. IEBE, 2013.
[6] Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knap- sacks. Journal of the ACM (JACM), 65(3):1-55, 2018.
[7] Sébastien Bubeck and Nicolò Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Found. Trends Mach. Learn., 5(1):1-122, 2012.
[8] Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Pac bounds for multi-armed bandit and markov decision processes. In International Conference on Computational Learning Theory, pages 255-270. Springer, 2002.
[9] Arthur Flajolet and Patrick Jaillet. Logarithmic regret bounds for bandits with knapsacks, arXiv preprint 1510.00 018000,0000440 2015.
[10] Nicole Immorlica, Karthik Abinav Sankararaman, Robert Schapire, and Aleksandrs Slivkins. Adversarial bandits with knapsacks. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 202-219. IEEE, 2019.
[11] Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Bandits and experts in metric spaces. Journal of the ACM (JACM), 66(4):1-77, 2019.
[12] Tze Leung Lai, Herbert Robbins, et al. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
10

---

[13] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[14] Xiaocheng Li, Chunlin Sun, and Yinyu Ye. The symmetry between arms and knapsacks: A primal-dual approach for bandits with knapsacks. In International Conference on Machine Learning, pages 6483-6492. PMLR, 2021.
[15] Karthik Abinav Sankararaman and Aleksandrs Slivkins. Bandits with knapsacks beyond the worst case. Advances in Neural Information Processing Systems, 34, 2021.
[16] Aleksandrs Slivkins. Contextual bandits with similarity information. In Proceedings of the 24th annual Conference On Learning Theory, pages 679-702, JMLR Workshop and Conference Proceedings, 2011.
[17] Aleksandrs Slivkins. Introduction to multi-armed bandits. Found. Trends Mach. Learn., 12 11-2):1-286, 2019.
[18] Long Tran-Thanh, Archie Chapman, Enrique Munoz De Cote, Alex Rogers, and Nicholas R Jennings. Epsilon- policies for Conference on Artificial Intelligence, 2010.
multi-armes bandits. In Twenty-Fourth AAAI
[19] Long Tran-Thanh, Archie Chapman, Alex Rogers, and Nicholas Jennings. Knapsack based optimal policies for budget-limited multi-armed bandits. In Proceedings of the AAAI Conference on Artificial Intelligene, volume 26, pages I 1134-1140 2012.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We discuss potential improve- ments in Section 5.
(c) Did you discuss any potential negative societal impacts of your work? [No] Our paper studies a theoretical model and we do not believe there are any negative societal impacts
of this paper.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set assumptions of all theoretical results? [Yes] We state our assumptions in Section 2.3.
(b) Did you include complete proofs of all theoretical results? [Yes] We include complete proofs in the appendix. But we include a proof sketch of most lemmas in the main paper following the lemma statement.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
11

---

(d) Did you discuss whether and how consent was obtained from people whose data you' re using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "Yi5RT38f37G", "reviewer": "Reviewer_S3ZC", "summary": "Authors introduce a generalization of the Bandits with Knapsack problem in which resources can be stochastically replenished over time. They introduce an algorithm which achieves constant regret with respect to an upper bound of the optimal reward both for the single-resource case and the multi-resource case, which involves non-trivial analysis. They then introduce a learning algorithm that they prove has log(T) regret. They finish by showing that BwK can be reduced to their generalization and as such, the same bounds can apply, matching the state of the art.", "questions": "\n- Can the authors please provide more motivation for why this generalization of BwK is significant?\n- Can the authors please provide either minimal empirical results or a commentary on the practical usefulness of their theoretical results, especially as related to the assumptions made in section 2.3?\n- Can the authors comment on how their algorithm and results adapt to the case of deterministic costs, e.g., Case 2 of Flajolet and Jaillet, which also has many real-world applications?\n\n", "limitations": "The authors acknowledge that their work does not achieve the optimal regret bound. They do not discuss the social implications of their work, which is ok for this mostly theoretical submission.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nStrengths:\n - Theoretical analysis is thorough, including some relatively non-intuitive results, e.g., Lemma 3.5 which shows that the proper choice of budget threshold can eliminate the regret's dependency on the horizon T. Main results are:\n   - Constant regret achieved in the case where reward and cost distributions are known. They achieve mainly by making assumptions necessary to ensure that the optimal solution can reduce to cases amenable to analysis, i.e., there is a subset of arms+resources manipulated in the upper bound solution, and that each arm is \"positive\" or \"negative\" drift with respect to a given resource -- these allow analysis of small number of individual cases where the challenge is to compute in expectation how often the authors' proposed policy plays arms that deviate from the upper bound solution.\n   - Log(T) regret achieved in the online learning case, via building off of pieces of a previously used multi-stage learning approach which identifies and improves confidence about the \"best arms\" in the first stages in log(T) time, then runs the optimal algorithm in the final stage.\n   - The reduction from BwK is helpful in grounding their results in current literature\n - The paper is relatively clearly written for what is a very math-dense submission. Authors do a nice job providing intuitive explanations within their proof sketches of how they arrived at certain key results, e.g., lines 183-190.\n - This seems to be a novel bandits problem.\n\nWeaknesses:\n - In my view, the authors do not do enough to motivate the problem they introduce. The example they give is \"in a dynamic pricing application a seller may receive shipments that increase their inventory level,\" but it is not clear that the author's model is the proper one even for this example. I.e., is it reasonable to assume that shipments would arrive stochastically and without respect to current supply? More examples should be given, or citations suggesting that this generalization will have impact on the theory community would be helpful. Without a stronger motivation for the problem, it is challenging to evaluate the significance/potential impact of the work. \n - In my view, it is a weakness not to provide any empirical results. These would help readers understand the current practical usefulness of the theoretical results.\n - Authors also do not provide much commentary on how restrictive their assumptions in section 2.3 are, which also limits understanding the practical usefulness.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "P1tmQpVExui", "reviewer": "Reviewer_5cwS", "summary": "The paper introduced a generalization of BwK model which admits increasing in budget. The authors then proposed an offline MDP-based algorithm named \"CB\", follows by a learning algorithm that combines the offline version with Li et.al's algorithms. The regret analysis of proposed algorithms is provided and it is tight. Interestingly, the offline algorithm achieves constant regret against OPT_LP, implying the gaps between the expected total reward of \"CB\", OPT and OPT_LP are not larger than a constant. Besides, the regret of the learning algorithm matches the result in [14] when applying to the classic BwK model. ", "questions": "I have 3 following questions:\n\nQ1: While the problem is well motivated as the resources can be renewed, the proposed model is rather unnatural. Particularly, the assumption that both consumption and replenishment depend on arm pulled and are represented by only one variable does not sound reasonable to me. Moreover, I understand that the notion of the null arm is technical and only serves for the analysis. Is there any practical motivation to introduce this arm into the model? \n\nQ2: I found the proof of lemma 3.1 and its generalization (line 209) are not clear. Which properties of LPs and case analysis are used? Perhaps it is based on the assumption that |X*| =|J*| as in [14]? I do think the authors should be more specific to avoid confusion here.\n\nC3: What is the advantage of the offline MDP-based algorithm (Algorithm 2) over solving the LP (1), as the algorithm also requires solving linear programming within its procedure?\n\n ", "limitations": "No", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros: \nThe introduced model is new and can serve as a generalisation of BwK model. Accordingly, the two proposed algorithm is new and the  regret is tight.\n\nThe offline method and its analysis is new and insightful. \n\nCons:\nThe paper sometimes lacks clarity and I found the its organisation is not easy to follow.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "14HgqpHXN0l", "reviewer": "Reviewer_RYqt", "summary": "This paper introduced a generalization of the stochastic bandit with knapsacks (BwK), where in each round, the decision maker observes an outcome consisting of a reward and a vector of resource drifts that can be positive, or negative, or zero. The authors considered two problems depending on whether the knowledge of true outcome distributions is available. If the knowledge is available, the authors developed a Markov decision process (MDP) policy that has constant regret against a linear program (LP) relaxation. Based on this result, the authors developed a learning algorithm that has logarithmic regret against the same LP relaxation when the distribution knowledge is not available. The authors also showed that their regret bound matches a reduction from BwK to their model.", "questions": "- The key difference in this paper is that there exists a null arm $x_0$ such that, if played, the expected drift for each resource is positive. This seems to suggest that the resource will increase linearly on average due to the expected positive drift when the null arm is played. To some extent, the resource replenishment rate is quite fast and hence this modeling assumption is quite strong. With this modeling assumption, one can use this null arm to quickly increase the resource budget to sustain the bandit learning. As a result, the strong constant and logarithmic regret under this modeling assumption is not very surprising. Can this assumption be weakened? \n\n- In the ExploreThenControlBudget learning algorithm, the first while-loop is quite similar to the literature and the associated regret analysis appears to be standard and not surprising. It's unclear what is the major difference, challenges, novelty, and new contributions in this part. It would be great if the authors could clarify the challenges and their contributions in this part.\n\n- Although I understand this paper is of theoretical nature, it's still worth providing some numerical experiments to verify the performance of the proposed learning algorithms, particularly given the fact some of the constants in the theoretical results are likely not optimal (e.g., 4096 in Definition 4 and 2048 in Corollary 4.1). Could the authors provide some experimental results?", "limitations": "This paper is theoretical and not relevant to negative societal imapcts.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n+ The authors proposed a generalized BwK model with non-monotonic resource utilization that has several interesting applications.\n+ This paper proposed two policies that achieve constant and logarithmic regrets for cases with or without true outcome distributions, respectively.\n\nWeaknesses:\n\n- The rationale of the null arm modeling assumption appears to be somewhat strong and unclear.\n- The UCB/LCB-type learning and regret analysis techniques appear to be standnard.\n- Lack of experiments to verify the proposed algorithms.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept