Bandits with Replenishable Knapsacks: the Best of both Worlds
Authors: Martino Bernasconi
Matteo Castiglioni
Andrea Celli
Federico Fusco
Venue: ICLR 2024 poster (2024)
Keywords: online learning
bandits with knapsack
best-of-both-worlds
Primary area: reinforcement learning

Abstract: The bandits with knapsacks (BwK) framework models online decision-making problems in which an agent makes a sequence of decisions subject to resource consumption constraints. The traditional model assumes that each action consumes a non-negative amount of resources and the process ends when the initial budgets are fully depleted. We study a natural generalization of the BwK framework which allows non-monotonic resource utilization, i.e., resources can be replenished by a positive amount. We propose a best-of-both-worlds primal-dual template that can handle any online learning problem with replenishment for which a suitable primal regret minimizer exists. In particular, we provide the first positive results for the case of adversarial inputs by showing that our framework guarantees a constant competitive ratio $\alpha$ when $B=\Omega(T)$ or when the possible per-round replenishment is a positive constant. Moreover, under a stochastic input model, our algorithm yields an instance-independent $\tilde{\mathcal{O}}(T^{1/2})$ regret bound which complements existing instance-dependent bounds for the same setting. Finally, we provide applications of our framework to some economic problems of practical relevance.

Published as a conference paper at ICLR 2024
BANDITS WITH REPLENISHABLE KNAPSACKS: THE BEST OF BOTH WORLDS
Martino Bernasconi
Matteo Castiglioni
Bocconi University
Politeenico di Milano
ma martino. beernasconi@uriboccoon i
@un
matteo. cast i goniiiiniiiiio 8po1 imi itt
Andrea Celli
Federico Fusco
Bocconi University
Sapienza University
andrea. celli2eun
federico. fuscoluniromal
ABSTRACT
The bandits with knapsacks (BwK) framework models online decision-making problems in which agent makes a sequence of decisions subject resource consumption constraints. The traditional model assumes that each action consumes non-negative amount of resources and the process ends when the initial budgets are fully depleted. We study natural generalization of the BwK framework which allows non-monotonic resource utilization, i.e., resources can be replenished by a positive amount. We propose best-of-both-wortee primal-dual template that can handle any online learning problem with replenishment for which suitable primal regret minimizer exists. In particular, case of adversarial inputs by showing that our framework guarantees a constant competitive ratio when B S2(T") when the possible per-round replenishment is a positive constant. Moreover, under stochastic input model, our algorithm yields an iestance-indeeedeer 1TT)/2 regret bound which complements existing instance-dependent bounds for the same setting. Finally, we provide applications of our framework to some economic problems of practical relevance.
provide the first positive results for the
INTRODUCTION
We study online learning problems in which decision maker tries to maximize their cumulative reward over a time horizon T,, subject to set of m resource-comsumptio constraints. At each t, the decision maker plays an action 2; E X', and subsequently observes a realized reward (x with f + [0, 1], and an m-dimensional vector of resource consumption (2z).
Our framework extends the well-known Bandits with Knapsacks (BwK) framework of Badanidiyuru et al. (2018). In the BwK model, the resource consumption is monotonic (i.e. cx(-) )) E [0. 1 for all I E [T]. This framework has numerous motivating applications ranging from dynamic pricing to online ad allocation (see, e.g., Besbes and Zeevi (2009); [Babaioff et al. (2012); Waag et al. (2014); Badanidiyuru et al. (2012); Combes et al. (2015)) ). and has been extended in numerous directions
such modeling adversarial inputs (Immorlica et al. 2022) and other non-stationary input models Celli et al. (023): Fikioris and Tardos (2023), more general notions of resources and constraints Agrawal and Devanur (2019), contextual and combinatorial bandits (Badanidiyuru al. (2014);
Agrawal et al. (0166) Sankararaman and Slivkins 2018).
Kumar and Kleinberg (2022) recently proposed natural generalization of the BwK model in which
resource consumption can be non-monotonic. i.e., resources can be replenished over time so
costs are (x,) E [-1, 11m We call such model Bandits with Replenishable Knapsacks (BwRK).
Kumar and Kleinberg (2022) focus on the stochastic setting, while we are interested in providing best-of-both- worlds algorithms that provide guarantees under both stochastic and adversarial inputs.
Contributions. We propose a general primal -ualll-dull template that can handle online learning problems in which the decision maker has guarantee some long-term resource-consumption constraints and

---

Published as a conference paper at ICLR 2024
resources can be renewed over time. We show that our framework provides guarantees in the spirit of Balseiro et al. (002)): it guarantees a regret bound of ((T)/2) in the case in which (fr, Cq) are i.idd samples from a fixed but unknown distribution, and it guarantees a constant-facte factor competitive ratio in the case in which budgets grow at least linearly in T, or when the possible per-round replenishment is a positive constant. We remark that known
frameworks like the one by Balseiro et al. (2022) cannot be applied this setting as they assume monotonic resource consumption. In that case, we show that our framework recovers the state-of- the-art rate of p/p by Castiglioni al. (2022a). where p is the per-iteration budget. Our primal-dual template is applicable to any online problem for which a suitable primal regret minimizer is available. Therefore, we first provide general guarantees for the framework without making any assumption on the primal and dual regret minimizers being employed (Section 4). Then, we show how such regret minimizers should be chosen depending on the information available to the learner about the intensity of the budget replenishment (Section 5}. Moreover, we provide explicit bounds that only depend on the guarantees of the primal regret minimizer. In particular, we show how the primal and dual minimizers should be instantiated in the case in which the amount of resources that can be replenished at each time is known, and in the more challenging case in which it is unknown a-prioni to the decision maker. Finally, we demonstrate the flexibility of our framework by instantiating it in some relevant settings (Section 6). First, we instantiate the framework in the BwRK model by Kumar and Kleinberg (2022), thereby providing the first positive results for BwRK under adversarial inputs, and the first instance-independer regret bound for the stochastic setting. The latter complements the instance-dependent analysis sis by Kumar and Kleinberg (2022). Then, we apply the framework to a simple inventory management problem, and to revenue maximization in bilateral trade.
constraints popularized by the work of Immorlica et al. (2022) cannot be applied in our setting. Such primal-dua approaches (see also Castiglioni al. (2022a); Balseiro et al. (2022); Balseiro and Gur (2019) usually require as an input the Slater's ' parameter of the problem (i.e., in their setting, the per-round budget). This is not the case in our setting since the amount by which each constraints is replenished is a priori unknown. This issue has been effectively addressed in stochastic settings where sublinear constraints violations are allowed, such as online optimization under stochastic inputs (see, e.g., . Yu et al. (2017); Wei et al. (2020), and stochastic online learning problems with long-term constraints Castiglioni et al. (2022b); Slivkins et al. (2023). However, in BwK problems constraints are required to be satisfied strictly at all rounds. Addressing this issue in the adversarial setting is considerably more challenging and this direction remains largely unexplored. A notable exception is the recent work by DyyCatigliioi ett al. (2023). Such works focuses which Slater's parameter is known, and one "soft" courr-on-investmentt (ROI) constraints (i.e. ROI constraints can be violated up to sublinear amount). Being allowed to violated the ROI constrain renders the problem significantly simpler than ours, where budget constraints must be strictly satisfied each time L. Moreover, our framework can handle an arbitrary number of constraints, while Castiglioni et al. (2033) can only manage one unknown feasibilty parameter. Finally, we mention that in the case of stochastic inputs other approaches for budget-managemen problems are known, most (Agrawal and Devanur 20199 Badanidiyuru et al. 2018).
Related works. Primal-dual approaches for bandit problems with eesource-consumppe
setting with only one monotone budget constraint, for
notably optimism ppriinis--uder--uee
2 PRELIMINARIES
Vectors are denoted by bold fonts. Given vector x. let [x be its i-th component. The set (1,...,m}, with n E Nyo, is denoted as [n]. Finally, given a discrete set S, we denote by A the |S]-ssimllxx
2.1
BASIC SET-UP
There are T rounds and resources. The decision maker has an arbitrary non-empty set of available strategies X. In each round t E [T), the decision maker chooses F, E X', and subsequently observes reward function St : X + [0, 1]. and function e; X' + [-1, 1]mh specifying the consumption or replenishment of each of the m resources. Each resource E [m]] is endowed with an initial budget of B to be spent over the 7 steps [ We denote by p the per-iteration budget, which is such that B = Tp.
For ease of notation consider uniform intial buget, but the case of different initial budgets easily follows from our results.
2

---

Published as a conference paper at ICLR 2024
and we let p == p1 R2y. where 1 I is the vector of all ones. For i E [m] and z X, if (z) < 0 we say that at time action x restores a positive amount to the budget available for the time depletes some of the available budget.
i-th resource. If (z,)(z) > O, we say that action
Let 7/- == (fe, 6+) be the input pair at time t, and "Yr = (71 12..... ?r) be the sequence of inputs up to time T. The repeated decision making process stops at the end of the time horizon T. The
goal of the decision maker is to maximize the cumulative reward Σ f((2)) while satisfying the resource constraints Ei=1 (x,( < T -p for each i E [m]] Given two functions f X + IR and c: c: + R"", we denote by f.e. : X' R + R the Lagrangian function defined as Liola, X) f(x + (X, p c(x)) for all X, À E 20
Given X. the set of strategy mixtures E\t is the set of probability measures on the Borel sets of X.
2.2 BASELINE ADVERSARIAL SETTING
Given a sequence of inputs "r selected by an oblivious adversary, the baseline for the adversarial setting is OPT, == 2u Σ/= ft (z), which is the total expected reward of the bestfixed uncon- strained strategy in hindsight belonging to X. Moreover, for any sequence of inputs Yr, and E [T], let ft :X + [0, 1] and é X - [-1, tM be such that:
f((=) = f and (x) ( (z))
E
(2.1)
Then, for E [T). we define J.T = suPrex Je(x)) and the baseline for the adversarial setting can be rewritten as O T O In the setting with monotonic resource utilization and adversarial inputs, previous work usually employs weaker baselines (see, e.g., [Immorlica et al. al.] [2022] Castiglioni et al. (2022a b)). For example, Castiglioni et al. (2022a) considers the reward attained by the best fixed strategy mixture until budget depletion, after which the void action is played. We show that, despite the stronger baseline, we match the state-of oftte-of-the-art 1/p competitive-ratio by Castiglioni et al. (2022a) when constraints are monotonic. We will work under the following standard assumption. Assumption 2.1. There exists void action 2 E X and a constant 3 2 0 such that (2) S -B, for all resources i [m] and & [T].
Notice that when = we recover the standard assumption of BwK (see, e.g., Badanidiyuru et al. (2018)). We will often parametrize regret bounds using == B + p. This parameter measures how much budget is available at each iteration, and how fast the available budget can be replenished.
2.3 BASELINE STOCHASTIC SETTING
In the stochastic version of the problem, each input 7/- (Je, c,) is drawn i.i.d. from some fixed but unknown distribution over a set of possible input pairs. Let f X + [0, 1] be the expected reward function, and X + [-1, 1| be the expected resource-consumption function (where both
expectations are taken with respect to P).
Given two arbitrary measurable functions f X - [0, 1]. c: X + [-1, define the following linear program, which chooses the strategy mixture & that maximizes the reward f, while keeping the expected consumption of every resource [m] given e below a target p:
sup [f
OPT f.c = EEE
(2.2)
s.t. Ex<e(c(x)] p
In the stochastic setting, baseline is OPT it well-known that T OP T. is an upper bound on the expected reward of any algorithm (see, e.g., (Badanidiyuru et al. 2018 Lemma 3.1) and (Kumar and Kleinberg 2022 Lemma 2.))). Lemma 2.2 (Lemma 2.1 Kumar and Kleinberg 2022 ) In the stochastic setting, the total expected reward of any algorithm is at most T. OPT J,e'
In the stochastic setting we make the same "positive drift" assumption of Kumar and Kleinberg (2022). which is weaker than our Assumption 2.1 in the adversarial case.
Assumption 2.3. There exists of a void action Ø X such that, for all resources i [m], it holds that E(c,(e) < BB and IPcc, (2) < 0] = 1, where 2 and the expectation is with respect to the draw of the e from P.
3

---

Published as a conference paper at ICLR 2024
Algorithm 1 Primal-Duu template
1: Input: parameters B,T; T': regret minimizers A' and A
2: Initialization: B1, <- B, Vi E [m]] initialize A A²; To [0}, To {0}.
3: for 11.2.... -''dd do
4:
3f [m] Bt, then
5:
Ta < TTo {t)
6:
Primal action: 24z
7:
Observe costs: Observe (2()) and update available resources: B(+1 t B, - c((
8:
else
9:
T: T TcU
Dual decision: X < AP_ NEXTELEMENTO
11:
Primal decision: I2 < ....TTEELEEENTT
12:
Observe cost: Observe e₁ (Ix) and update available resources: B4t f- B; - cx(xi)
13:
Primal update:
uf (x:) f1(x)) (A,, (x))))
AA". (:OOSERVUUULLTT((((.:..)
14:
Dual update:
of RR 3 A (A. (1))) -
AA ...OBSERVEUTILITYU))
2.4 REGRET MINIMIZATION
We will consider regret minimizers for a set W as generic algorithms that implements two func- tions: (i) the function NEXTELEMENT() returns an element wy W, and (ii) the function OBSERVEUTILITY
which takes some feedback and updates the internal state the regret mini- mizer. In the full-feedback model the regret minimizer observes feedback function u4 X - R, while in the bandit-feddbac model it observes only the realized un (ww)). The standard objective of regret minimizer is to control the cumulative regret with respect to a RT())) == supwey E (M+(w) de (w:)).. the following, we will also exploit more general notion of regret, in which the regret minimizer suffers regret only in specific rounds. In particular, uu (wx)). Then, we can recover common notions of regret such as standard (external) regret for which
S W defined as
given a subset of rounds T C [T] we define (R(()) ;= supwey Eie (ue(w)
[T]. and
weukly-alaptive regret for which Ri (J)) = supz=(th.eo[[1 (R)))) Hazan and Seshadhri (007).
We remove the dependency from y when y = W (e.g.. we write Ry in place of Rr(W)).
PRIMAL-DUAL TEMPLATE
We assume to have access to two regret minimizers with the following characteristic. A bandit- feedback primal regret minimizer Ae which outputs a strategy de X each I, and subsequently receives as feedhack the realized utility function of (xz) = fe(xz) ) + (Ae, P - G (,, and full- feedback dual regret minimizer A that receives as input the utility function: u² X (A. cx
p). note that the dual regret minimizer always has full feedback by construction
Algorithm D summarizes the structure of our primal-dual template. For each if the available budget B1, is less than for some resource the algorithm plays the void action Ø and updates the budget accordingly. This ensures that the budget will never fall below O. Otherwise, the regret minimizer plays action 2y at time I, which is determined by invoking NEXTÉLEMENTÚO Then, (xx,) and uf are observed, and the budget consumption updated according to the realized costs c. If the budget was least 1, the internal state of the two regret minimizers is updated via DOSERVEUTILLES on the basis of the feedback specified by the primal loss ui (Ir). and the dual loss function uf. The algorithm terminates when the time horizon T' is reached.
We partition the set of rounds in two disjoint sets Ta C [T] and To S [T]. The set To = (t E [T]: vi [m], B 1} includes all the rounds in which all the resources were least 1, and hence
We focus the more challenging landit-fcedbace setting. Our results easily extend full-feedback.
4

---

Published as a conference paper at ICLR 2024
the regret minimizers A" and A were actually invoked. On the other hand, To f [T] Ei [m]. B < 1 is the set of rounds in which at least one resource is smaller than 1. Clearly, we have To Te [r]. Then, let
To be the last time in which the budget was strictly less then 1 for at least one resource, i.e., T = max Te. We partition To in two sets Te.Sr and Te,3r which are the rounds in To before and after T, respectively. Formally, Te,sr = [r] Te. and To,>7 == (T) (+).
We denote by Ry (resp.. )2 the cumulative regret incurred by AA" (resp., AP). Following the notation introduced in Section 2.4 we will write R5 to denote the regret accumulated by the primal regret minizer over time steps in Tg. Let D == {A E R4 ||||| I 1/v). We consider the regret of the dual in the set of rounds To and Te. with respect to the action set D. Formally, RT (D) = supxeD LieT,er up (A) up (Ae). The term Rt is defined analogously. Finally, let M == max; Della be the largest value of the fnoorm of dual multipliers over the time horizon.
4 GENERAL GUARANTEES OF THE PRIMAL-DUAL TEMPLATE
In this section, we provide no-regret guarantees of the general template described in Algorithm |
4.1 ADVERSARIAL SETTING
We start by describing the guarantees of Algorithm in in the adversarial setting. The idea is that, since corresponds to the last time in which at least resource had B < 1, it must be the case that the primal "spent a lot" during the time intervals before T in which it played (i.e., To,sr). ). Ideally, the dual regret minimizer should adapt to this behavior and play a large À in Te.<r thereby attaining large cumulative utility in Ts We show that the Lagrange multipliers in 'D are enough for this purpose. Then, as soon we reach t T, the dual should adapt and start play small X. Indeed, during these rounds the primal regret minimizer gains resources and therefore the optimal dual strategy would be setting À= = 0. The effectiveness of the dual regret minimizer in understanding in which phase it is playing, and in adapting to it by setting high/small penalties, is measured by the size of the regret terms R..... (D) and R (D). In particular. R (D) (resp.. Re (D)) low if the dual regret minimizer behaves as expected before т (resp., after r). Intuitively, if A guarantees that those terms are small, then the dual regret minimizer is able to react quickly to the change in the behavior of the primal player before and after r. As a byproduct of this, we show that the part of the primal's cumulative utility due to the Lagrangian penalties is sufficiently small. At the same time, we know that the primal regret minimizer has regret at most RS with respect to strategy
mixture that plays the optimal fixed unconstrained strategy with probability v/(1+ B), and the void action otherwise. This strategy mixture guarantees // + 3) fraction of the optimal utility without violating the constraints at any rounds. Formally, we can show the following
Theorem 4.1. Let a == v/(1 + B). In the adversarial setting, Algorithm outputs a sequence of actions (xx) (T=) such that
Σ f(()) ( a- OPI, (2 + RR To (D) + RD To (D) + Re. 1E
Notice that, in the case of 3 = we recover the standard guarantees of adversarial bandits with knapsacks for the case in which B = ?(T) Castiglioni et al. (2022a), where the competitive ratio exactly P. The possibility of replenishing resources yields an improved competitive ratio.
Remark. In order for Theorem 4.1 to provide a meaningful bound, we need the three regret terms on the right-hand side to be suitably upperbounded by some term sublinear in T (see Section 5). Since the time steps in To are the only rounds in which A² is invoked, any standard regret minimizer can be used to bound Re. However, the same does not holds for AP. Indeed, we need a regret minimizer which can provide suitable regret upper bounds to RDp Perr
(D) and R. (D), at the same time. One cannot simply bound Re_ (D) + Re. Ta (D) by Re (D), since the best action in the sets Te.cr and Te may differ. Standard regret minimizers usually do not provide this guarantee, so we need special care in choosing Ar. In particular, we need weakly adaptive dual regret minimizer.
'lll omitted proofs can he found in the appendix.
5

---

Published as a conference paper at ICLR 2024
4.2 STOCHASTIC SETTING
In this setting, we can exploit stochasticity of the environment to show that the expected utility of the primal under the sequence of realized inputs 7 (Sz, ct)E=1 is close to the primal expected utility (J,C), and to provide a suitable upperbound to the amount by which each resource is replenished during Te. Given 8 E (0, 1), let E,, = /8T log (4mT/6).
Lemma 4.2. For any { E and 6 E (0, 1], with probability at least 1 - 6, it holds that:
EXETa (,((0) - T + M&T, Vi [mm], and
(4.1)
Eang EeeT f((x) + P cx(x))]]
E x~6
EETT, f(x) + (2c, (c,p-c((s)]] ME
(4.2)
Then, we can prove the following regret bound.
Theorem 4.3. Let the inputs (fr, c.) be i.i.d. samples from a fixed but unknown distribution P. For 5 E (0, 1], we have that with probability at least 1 5, it holds
Σ f((z)) 2 T. OPTOP (2
1 e Ra (D) + R Na (D) + My.
The proof follows similar approach to the one of Theorem with two main differences. First, we can now exploit standard concentration inequalities relate realizations of random variables with their mean. Second, we exploit the fact that the primal has regret at most R7, against an optimal solution to OPTY T.e. which is feasible in expectation and has an expected utility that matches the value of our baseline. This allows to obtain competitive-ratio equal to in the stochastic setting.
5 CHOOSING APPROPRIATE REGRET MINIMIZERS
In order to have meaningful guarantees both the adversarial and stochastic setting, we need to choose the regret minimizers A² and A that RT.- RR. (D) and RZ (D) all grow sublinearly in T. In the following section we will discuss two different scenarios, which differ in the amount of information which the decision maker is required to have. In Section [ we are going to assume that the decision maker knows the per-round replenishment factor 3. Then, in Section 5.2] we will show that this assumption can be removed by employing primal regret minimizer A with slightly stronger regret guarantees. In both cases, the dual regret minimizer A has be weakly adaptive, since both terms Re.. (D) and RD Ta,, (D) need to be sublinear in T. On the other hand, we will make minimal assumptions on the primal regret minimizer A². Its choice largely depends the application considered, as we show in Section [6] In general, the primal regret minimizer must meet the minimal requirement of guaranteeing sublinear regret upper bound Eir with probability least
1 6, when the adversarial rewards are in [0, 1].
5.1 IMPLEMENTING ALGORITHM| 1 WITH KNOWN REPLENISHMENT FACTOR
We start by assuming that the decision maker knows 3 or, more generally, a lower bound 3 on it. Therefore, the algorithm can compute v, or its lower bound. When 3 is known, we can instantiate the regret minimizer A to play on the set D = {A IR. ||A|| < 1/5} 2 D. where i = 3 + S v.
As discussed above, the dual regret minimizer on the set of Lagrange multipliers D must be weakly adaptive. This can be achieved via variations of the fixed share algorithm proposed by Herbster and Warmuth (1998). We will employ the generalized share algorithm of Bousquet and Warmuth (2002) and the analysis of
et al. (2012). as AP has full feedback by construction.
The set D can be written as D = co (0, 1/61, with i [m]]] where 1, is the i-th standard basis vector, and denotes the convex hull. Since D D, achieving weakly-adaptin regret with respect to D implies the same result for D. Thus, instantiating the fixed-shan algorithm on the (m + 1)-simplex, and since the losses of AP are linear we can prove that:
Lemma 5.1. (Cesa-Bianchi et al. 2012 Corollary 2) For any 0 3 S B, there exists an algorithm that guarantees max R2 RR. (D),
RD Ray, (D)
< 3 Tlog (2mT).

---

Published as a conference paper at ICLR 2024
Since the dual regret minimizer AP can play any Lagrange multiplier A D, have that the
rewards observed by the primal regret minimizer AA" are in the range [0,1+ + 2/ because it holds
{16(2z) ||ll lle ax))l - + 2 4 ZEX,EE]]
sup =EX
(x))
sup
With probability at least 6, the primal regret minimizer A guarantees a regret e7. against rewards in [o, 1]. Then, by re-scaling the realized rewards before giving them in input to the regret minimizer, get regret bound of y ECG against rewards uf (+) that in [0, 1/s.. This simple construction is applicable because the range of the rewards is known. By combining these observations we can easily recover the following corollary of Theorem 4.1]and Theorem 4.3
Corollary 5.2. Assume that the dual regret minimizer is generalized fixed share on DD and that the primal regret minimizer has regret at most ET.,8 against losses in [0, 1] with probability at least 1 8, for â E (0, 1). In the adversarial setting, for any S B, with probability at least 1 - Algorithm guarantees that
E f(r)) aOPT, (2+1) TTTTlo (2mI) + ETT
4
V
tE[T]
where a = 1/1+0. In the stochastic setting, with probability at least 26, Algorithm guarantees
Σ 1
f(xx)) 2 T OPTYA - + D
VT (2mT) + TT. ET. 1 1et +
5.2 IMPLEMENTING ALGORITIMM 1 WITH UNKNOWN REPLENISHIMENT FACTOR
In this section we will show how to implement Algorithm T when no information about the per-round replenishment factor 3 is available. This impacts both the primal and the dual regret minimizer. Differently from the previous section, we cannot instantiate the regret minimizer A directly D (or a larger set D) since do not know such set. Therefore, we need dual regret minimizer that plays on R but has sublinear weakly-adaptive regret with respect to Lagrange multipliers D. To achieve this, we can
the Online Gradient Descent (OGD) algorithm, instantiated on RT with starting point Ag = 0. Indeed, is well known that OGD guarantees that the regret on any interval of rounds [t t2l S [T] is upper bounded by the & distance between the point played
and the comparator. In our setting this is equivalent to the following lemma (Hazan et al. 2016 Chapter 10).
Lemma 5.3. For any To C [T] and any 1,, 12 E T if the dual regret minimizer is OGD with learning rate we have that the regret with respect to X is upper bounded by
|
Re Tanke 12) ((A))
2 m.
2n
In this setting, we also need additional assumptions on the primal regret minimizer A². Formally we need an algorithm that satisfies the following condition.
Condition 5.4. We assume that, for any T [4,, 12) S [T], the weakdy-adaptive regret of facing adversarial losses with unknown range L. upper bounded by T. with probability least 1 8. where & is independent from the range of payoffs.
In order to provide the final regret bound for this setting, we need to show that the size of Lagrange multipliers remains bounded by a suitable term.
Lemma 5.5. Assume that the dual regret minimizer OGD on RT with 17 = Eki 8 + kgm
2my/T T -1, where ki, 2iz are absolute constants, and the primal regret minimizer A satisfies Condi- tion 5.4 Then, both in the adversarial and stochastic setting, the Lagrange multipliers de played by the dual regret minimizer A are such that M := suptett]
|>ell < 8m/v.
This result extends the similar result of Castiglioni et al. (2023 Theorem 6.2) to the case of multiple constraints. Lemma allows bound the regret Ri, the primal, and the regret terms R2.er (D) and R2 (D) of the dual regret minimizer. In particular, for what concerns the dual regret minimizer
7

---

Published as a conference paper at ICLR 2024
A², we bound the maximum distance between Lagrange multipliers which played by AP. Then, we can bound the regret terms <x (D) and R
bound the regret of the primal through Condition 5.4 br (D) via Lemma [33) Similarly, we
Using this observations, together with
Theorem 4.1 and Theorem 4.3 we can extend Corollary 5.2 to the case of unknown, ,3
Corollary 5.6. Assume that the dual regret minimizer is OGD on RT with rj E kymEr +
2m T -1, where ki, 222 are absolute constants, and the primal regret minimizer A satisfies Condi- Then, in the adversarial setting, Algorithm guarantees with probability 8 that
tion 5.4
Σ f((e)) 2 OPTy [E[T]
K3
m 122 (ET + ET,)
where ki an absolute constant and = v/148. In the stochastic setting, there is an absolute constant 1n such that Algoritiu guarantees that, with probability at least 1 28,
7(x))21 OPT k4 m²
Σ LE|2
v2 (E 5 +c,,))
APPLICATIONS
This section demonstrates the flexibility of our framework by studying three well motivated models: BwRK, inventory management, and revenue maximization in bilateral trade.
6.1 BANDITS WITH REPLENISHABLE KNAPSACKS (BwRK)
Consider the standard BwK problem: at each time step f, the learner selects an action is out of K
actions (thus X' ( suffers loss (ia) E [0. 1] and incurs cost vector ca (ft) [-1, 1] that specifies the consumption of each one its m resources. We focus on the most challenging scenario, in which the parameter 33 is known. We instantiate the primal-dual framework (Algorithm []] using EXP3-SIX Neu (2015) as the primal regret minimizer, while online gradient descent is employed as the dual regret minimizer. Castiglioni et al. (2023 show that EXP3-SIX achieve weakly-adaptoe regret (=((VK)) where L is the range of the observed losses.
First, let's consider the adversarial case, where losses and cost functions are generated by an oblivious adversary. Assumption 2. verified when there exists null action Ø that always yields non-negative resource replenishment (i.e., there exists B 2 0 s.t. (Ø) S - for each resource j and time t).
Theorem 6.1. Consider the BwRK problem in the adversarial setting. There exists an algorithm satisfying the following bound on the regret:
m
1 )
a OPT.
Σ ((())) S
KT log
122
1E[T)
with probability at least 1 8, where = +
This is the first positive result for the BwRK problem in the adversarial setting.
Second, we consider a stochastic version, in which losses and cost vectors are drawn i.i.d. from an unknown distribution. this setting, the void action assumption (Assumption 2.3) requires the existence of a distribution Ø E AK over the actions such that, in expectation over the draws of the cost function, verifies [Ø)) S -3 for all resources { The analysis of our primal-dual framework allows us show that the same learning algorithm presented for the adversarial setting yields the following instance-independent results the stochastic setting.
Theorem 6.2. Consider the BwRK in the stochastic setting. There exists algorithm satisfying, with probability at least 26, the following bound on the regret:
T T-OPTYe E((t))
m
KT log
1 1))
22
'Note, the role of 99 is played in Kumar and Kleinherg 22022 by the parameter &tack- Furthermore, there the authors make additional assumptions the structure of the optimal I.P and its solution.
8

---

Published as a conference paper at ICLR 2024
Theorem 6.2 provides the first iistance-independeee regret bound under i..d. inputs, and it comple-
ments the instance-dependee setting, they provide logarithmic instance- deseadee-dependent bound the regret of order O ((mm²/ [[Km//a" /2" log T),, where A is a notion of suboptimality gap (already present in Li et al. (02T)). which in principle may be arbitrarily small. Although our work does not offer instance destance-dependett logarithmic bounds on the regret, we advance the study of the BwRK problem along three main directions: i) we design an algorithm which handles the same time both stochastic and adversarial inputs (while Twhile/Kumar and Kleinberg (2022) only deal with the stochastic input model), ii) our primal-dual approach is arguably simpler, and iii) we provide the first worst-case dependence on the time horizon T.
analysis by Kumarr and Kleinberg (202). In particular, in the stochastic
6.2 ECONOMIC APPLICATIONS AND DISCUSSION
In the following, describe two additional economic applications where our framework can be applied in the stochastic setting.
Inventory management. As simple application of our techniques, consider the following inventory management problem. Each day t, a shopkeeper is confronted with a decision: either open for business and attempt to sell the goods it has in the store, or travel to its supplier in order to restore its inventory. This simplified model captures many real world application that contemplates the trade-off between exploiting the available inventory, and "skipping turn" to replenish it. For the sake of clarity we restrict ourselves to the case of a single resource and supplier, however this could be easily extended more general instances. Formally, the goods in stock day are B, 2 O, and the shopkeeper has a set two actions X' {o, s). Action corresponds to opening for business with reward (o) E [o, 1] and inventory consumption or (o) [0, 1]. while action s corresponds to going to the supplier, with (s) E [-] and negative resource consumption (a E [-1, which both depend on the supplier's availability and current price. Clearly, it is possible to select action only
B, 2 1, while action s plays the role of the void action Ø. We focus of the stochastic case in which Blex(s) S B, where 3 is the expected amount of good available from the supplier. By employing
EXP-SIX as in Section 6.1 this immediately yields a (VVT) regret bound via Corollary 5.6
Bilateral trade. We consider the well known bilateral trade model (Vickrey 1961| Myerson and Satterthwaite/ 1983] Cess-Biiancii et al., 202T]: each day, the merchant posts two prices, a price P: E 2 and a price 4t E R4 to a seller and a buyer of a good, respectively. The seller (resp., the buyer) has private valuation of 6, E [0, 1] (resp., b, E [0, I].. If the valuation 8, is smaller than Pt- then the merchant buys one unit of good from the seller, while if the valuation by is larger than the price qe (and there is some inventory left) then the merchant sells a unit of the good to the buyer. The merchant can only sell good if B, > 1, i.e., the inventory has least one unit of it. Moreover, we assume that the merchant has no initial budget, i.e., B₁ = 0. The merchant's revenue at time t rev qt) := (g. pc) < b,]1[s, < pr]. Similarly, for any t [T'], the stock consumption is updated as follows: B++1 = B, - 1 (4: < br] + 1[s S pr]. Therefore, the strategy of choosing Pe and q: > 1 surely increases the budget by one unit, and it has revenue rev qt) = -1 This strategy plays the role of the void action Ø, with rou-dound replenishment 3 = 1. Similarly to the example above, in the stochastic setting is enough to translate and re-scale the revenue to satisfy all the assumptions of our algorithm. This immediately yields the ((VT) regret guarantees. The adversarial case was addressed in recent paper by Bernasconi et al.) (2024) using techniques similar to the ones developed in this paper. When considering the same baseline of our paper, they achieve a constant competitive ratio of 2 through an ad hoc analysis.
Challenges of the adversarial setting. In the case in which rewards are allowed to be negative and inputs are adversarial, the simple trick of re-scaling and translating the utilities is not applicable. This is due to the fact that our algorithm guarantees multiplicative approximation of the benchmark and this multiplicative factor is not invariant with respect to translations. We leave as an open problem the question of how to handle application scenarios in which rewards may be negative in the adversarial setting. We observe that the results for the adversarial setting would be preserved if we could provide a void action Ø that has non-negative reward and negative cost, but this is not usually the case in practical applications. Finally, it would be interesting to extend the simplified inventory unventory-managemmet model which we discussed to more complex models which have been proposed in the operations research literature (see, e.g., Chen et al. 20022; Chen and Simchi-Levi (2004))

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
MB, MC, AC, FF are partially supported by the FAIR (Future Artificial Intelligence Research) project PE0000013, funded by the NexIGenerationEUU program within the PNRR-PED PE-AI scheme (M4C2, investment 1.3, line on Artificial Intelligence). FF is also partially supported by ERC Advanced Grant 788893 AMDROMA "Algorithmic and Mechanism Design Research in Online Markets", and PNRR M-N0001-SSBiDDaae
MC is also partially supported by the EU Horizon project ELIAS (European Lighthouse AI for Sustainability, No. 101 120237). AC is partially supported by MUR PRIN 2022 project 2022R45NBB funded by the NexIGenerationEU program.
MUR project
REFERENCES
Shipra Agrawal and Nikhil Devanur. Bandits with global convex constraints and objective.
Operations Research, 67(5):1486-1555 2019.
Shipra Agrawal, Nikhil R Devanur, and Lihong Li. An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives. In 29th Annual Conference on Learning Theory (COLT), 2016.
Moshe Babaioff, Shaddin Dughmi, Robert Kleinberg, and Aleksandrs Slivkins. Dynamic pricing with limited supply. In Proceedings of the 13th ACM Conference on Electronic Commerce, pages 74-91, 2012.
Ashwinkumar Badanidiyuru, Robert Kleinberg, and Yaron Singer. Learning on budget: posted price mechanisms for online procurement. Proceedings of the 13th ACM conference on electronic commerce, pages 125-145, 2012.
Ashwinkumar Badanidiyuru, John Langford, and Aleksandrs Slivkins. Resourceful contextual bandits. In Conference Learning Theory, pages 1109-1134. PMLR, 2014.
Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knapsacks. J. ACM, 65(3), 2018.
Santiago R Balseiro and Yonatan Gur. Learning in repeated auctions with budgets: Regret minimiza- tion and equilibrium. Management Science, 65(9))3952-3968 2019.
Santiago R Balseiro, Haihao Lu, and Vahab Mirrokni. The best of many worlds: Dual mirror descent for online allocation problems. Operations Research, 2022.
Martino Bernasconi, Matteo Castiglioni, Andrea Celli, and Federico Fusco. No-regret learning in bilateral trade via global budget balance. Proceedings of the 56th Anmual ACM Symposium on Theory of Computing, 2024.
Omar Besbes and Assaf Zeevi. Dynamic pricing without knowing the demand function: Risk bounds and npar-optimal algorithms. Operations Research, 5766):407--1200, 2009.
Olivier Bousquet and Manfred K Warmuth. Tracking a small set of experts by mixing past posteriors. Journal of Machine Learning Research, 3630v):363-396, 2002.
Matteo Castiglioni, Andrea Celli, and Christian Kroer. Online learning with knapsacks: the best of both worlds. In International Conference on Machine Learning, pages 2767-2783. PMLR, 2022a.
Matteo Castiglioni, Andrea Celli, Alberto Marchesi, Giulia Romano, and Nicola Gatti. A unifying framework for online optimization with long-term constraints. In Advances Neural Information Processing Systems, volume 35, pages 23589-33602 2022b.
Matteo Castiglioni, Andrea Celli, and Christian Kroer. Online bidding in repeated non-truthful auctions under budget and roi constraints. arXiv preprint arXiv:2302.01203, 2023.
Andrea Celli, Matteo Castiglioni, and Christian Kroer. Best of many worlds guarantees for online learning with knapsacks. arXiv preprint arXiv:2202.137/11 2023.
10

---

Published as a conference paper at ICLR 2024
Nicolò Resa-Bianchi, Pierre Gaillard, Gábor Lugosi, and Gilles Stoltz. Mirror descent meets fixed share (and feels no regret). In Proceedings of the 25th International Conference on Neural Information Processing Systems Volume I, page 980-988, 2012.
Nicolò Dasa-Bianchi, Tommaso R Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. A regret analysis of bilateral trade. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 289-309, 2021.
Boxiao Chen, David Simchi-Levi, Yining Wang, and Yuan Zhou. Dynamic pricing and inventory control with fixed ordering cost and incomplete demand information. Management Science, 68(8): 5684-5703, 2022.
Xin Chen and David Simchi-Levi. Coordinating inventory control and pricing strategies with random demand and fixed ordering cost: The finite horizon case. Operations research, 52(6))887-896, 2004.
Richard Combes, Chong Jiang, and Rayadurgam Srikant. Bandits with budgets: Regret lower bounds and optimal algorithms. ACM SIGMETRICS Performance Evaluation Review, 43(1):245-22) 2015.
Giannis Fikioris and Éva Tardos. Approximately stationary bandits with knapsacks. In The Thirty Sixth Annual Conference on Learning Theory, pages 3758-3782. PMLR, 2023.
Elad Hazan and Comandur Seshadhri. Adaptive algorithms for online decision problems. In Electronic colloquium on computational complexity (ECCC), volume 14, 2007.
Elad Hazan et al. Introduction to online convex optimization, volume 2. Now Publishers, Inc., 2016.
Mark Herbster and Manfred K Warmuth. Tracking the best expert. Machine learning. 32(2):151-178, 1998.
Nicole Immorlica, Karthik Sankararaman, Robert Schapire, and Aleksandrs Slivkins. Adversarial bandits with knapsacks. ACM, 69(6). 2022. ISSN 0004-5411.
Raunak Kumar and Robert Kleinberg. Non-monotonic resource utilization in the bandits with knapsacks problem. In Advances Neural Information Processing Systems (NeurIPS), 2022.
Xiaocheng Li, Chunlin Sun, and Yinyu Ye. The symmetry between arms and knapsacks: A primal- dual approach for bandits with knapsacks. In /CML, volume 139 of Proceedings of Machine Learning Research, pages 6483-6492. PMLR, 2021.
Roger B Myerson and Mark A Satterthwaite. Efficient mechanisms for bilateral trading. Journal of economic theory, 29(2): 1983.
Gergely Neu. Explore more: Improved high-probability regret bounds for non-stochastic bandits. Advances in Neural Information Processing Systems, 28, 2015.
Karthik Abinav Sankararaman and Aleksandrs Slivkins. Combinatorial semi-bandits with knapsacks. In International Conference on Artificial Intelligence and Statistics, pages 1760-1770. PMLR, 2018.
Aleksandrs Slivkins, Karthik Abinav Sankararaman, and Dylan J Foster. Contextual bandits with packing and covering constraints: A modular lagrangian approach via regression. The Thirty Sixth Annual Conference on Learning Theory, pages 4633-4656. PMLR, 2023.
William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance, 16(1):8-37, 1961.
Zizhuo Wang, Shiming Deng, and Yinyu Ye. Close the gaps: A learning-whille-diing algorithm for single-product revenue management problems. Operations Research, 62(3)318-331, 2014.
Xiaohan Wei, Hao Yu, and Michael I Neely. Online primal-dual mirror descent under stochastic constraints. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 4(2): 1-36, 2020.
Hao Yu, Michael Necly, and Xiaohan Wei. Online convex optimization with stochastic constraints. Advances in Neural Information Processing Systems, 30, 2017.
11

---

Published as a conference paper at ICLR 2024
A PROOFS OMITTED FROM SECTION 4.1
Theorem 4.1. Let a == v/(1 + B). In the adversarial setting, Algorithm 1 outputs a sequence of actions (zz)(=1 such that
Σ f a. OPTy (2 + Ry Rt... (D) + R4 Re... (D) + + TE
Proof. We divided the proof in two steps. First, we show that over the rounds Ta in which the regret minimizers play the "lagrangified" cumulative costs is controlled. Then, in the second step, show that over the same set of rounds Te the "lagrangified" utility is large. In order to simplify the notation, will write R (resp., To.,) ) place of R (D) (resp., Re R (D)).
Part 1. First, show that in Ta the budget spent by the decision maker is sufficiently high. Let 1" be the resource that had the lowest budget in round T E Te.
Summing the budget equation B Bi,i- Ct,+ (24) over tert- fl,..... 1}, gives us
B Bi =- Σ
Ci (2t).
1ST-1
Since by definition B and B1 B we get that:
(A.1)
AST-1
Moreover, in rounds / E Te, since the budget was strictly less we have by construction that dy = Ø, and thus Cr (zt) S -3. This readily implies that:
Σ BE
Cr -B
(A.2)
By combining Equation A.I and Equation
(.2)
we obtain that:
Ca.- (x1)
Cta- (are)
Σ (x:)
TETe,
EE|T
BET
B - 2 Tel
Since the budget spent in rounds To,<- is large, it must be the case that the dual regret minimizer . collects large cumulative utility in those rounds. Formally, the regret RD
To,er of A4"h on rounds Te,er
with respect to À 11,-- reads follows
Σ (x p) tETaeer
(ct,)(())) -p--) - -RP TeT
Σ
BB 2 Taa - To,crlpt-) Re RRa.e
(prT 2 B|Tz| (To<r(pp.) - RR
(pr (pT, + +Tal + (Te,>r)) - 2 TT - (Ta.erlps)) - RR
Ta,c-
(v|Tol + +p.
|o, +
- 2) - RR To
> (y| -2) RR RRP..
2 RD Ta.er'
Txl
(A.3)
Then, by considering A 0 and the definition of the regret on Ta.5r get that the utility of dual is bounded by:
Σ
(21)) p) 2 - R2 Te
(A.4)
TET
12

---

Published as a conference paper at ICLR 2024
Thus, by combining the inequalities of Equation ) and Equation
A.44 conclude that:
(d,, p) (Tll Ta,er
R Tapp
(A.5)
LET
Part 2. Now, let x² be the best unconstrained strategy, i.e., x² E arg maxxeX EiE(T] ft(z) and thus
Eist fi(x*) OPT 0 Consider the mixed strategy 8* E E that randomizes between x² and Ø, p+8 and 1+3 respetively. Then En-e- (AE --c(x)))))) 2 0. This can be with probability 1+33 easily proved via the following chain of inequalities:
E
E (ee pc(x))
B 3
(7e, P- c((x)) + 1- P
Σ
(Ae. p c((0))
1+B
1 1+ 8 TET
To
A1, p)
P+
Σ
(ec, c((x))
1- Σ (10))
1 1
1 1+
1o
1ET
1E
2 0
|
P B
Σ
| +
1- P 3 Σ ||
1+8 LET.
1+ B
1ET:
LET.
p + 8
8 1-
Σ
PAlli
1+ B
1+
IET.
0.
(A.6)
Then, use the defintion of the regret of the primal regret minimizer to find that:
E g
Σ f((z) + (A., P-.p-c((1)) -((o)))
((i(o,) - (Ai, p- - s R
TE
and by rearranging and using the inequality of Equation
A.6
we have that:
Σ f((z)) + p - cx(x))
Σ f((x)) - RRy:
E
TE
LIET
By building upon this inequality we obtain the following:
Σ f(( + (A..P- (xx)))) 2 E
Σ fzx
-Re
1ETa
zmge
LIETo
Σ f(())
Σ f((x)
RT/
z~
1ST
1ETx
Σ f((
-Tel -Ro
2~
1ST
p+
+ 1-p Σ f(()) - (Tal - -Re
f((x))
1+ 3
1+ 3 1T
IST
P+3 Σ - -TTal - Rt.
1+3 IST
p OPT, Te Rr.
(A.7)
1 B
Forr simplicity we replaced the supremum with the maximum. Results would continue to hold with sup with minor modifications.
13

---

Published as a conference paper at ICLR 2024
Concluding, Using the inequality of Equation A.4) and the inequality of Equation A.7
we have
E Σ
f((1z)
15T
1E
( - -p) P
2 Σ
OPT, - [T -R 1+
1T
2
- R Ta + p 3 OPT
2 [T
Ie -Ry
Ta,er
1+ B
p + B
RD
RT Tuxer
RR
Rr.
+ 8
V
which concludes the proof.
B PROOFS OMITTED FROM SECTION 4.2
Lemma 4.2. For any & and 5 E (0, 1], with probability at least - 6, it holds that:
EIETo (,) S -B|Ta| M&g,s Vi [mn], and
(4.1)
Eowg [ETET, + (Ar, c+(x))
2 E EIET, f(x) + P p - M Mr,6. ane
(4.2)
Proof. We start by proving that the incquality of Equation 4 holds with probability 1 - 8/2. Let K [Tz). Then, we can easily see that, for i [m], with probability 1 -/(2m())
[4mT
[AmT
Σ (cx, - (,0) < 2K log KE(A]
2T log
where the first inequality holds by Hoeffding's bound. By taking union bound over all possible lengths of To (which are T') and E [mm]. we obtain that for all possible sets To holds:
4mT
Σ (c) < EE
2Tg log
with probability at least - 6/2. Then the proof of the inequality of Equation concluded by observing that:
Σ
a(0)
and that /2T log (4mT/a) S ME Equation 4.2) can be proved similar way. Indeed, for any fixed To of size K = (Ta), and for any strategy mixture ç, by Hoeffding we have that with probability at least 1 - 6/2T the following holds
K
4T 8
Σ f((z) (2. P- c(()) LIET
E x~
Σ f(x) + (A,,p-
- -(1 -(1+2M)
log
2
LET
T
47
E
f(x) + 2x,p-E(1))
- -1++2M)
log
2~5
2
LIT
E
Σ
f())+
ME
LET
By taking a union bound over all possible T lengths of Tes we obtain that for all possible sets Te. the equation above holds with probability 1 - 5/2.
The Lemma follows by union bound on the two equations above, which hold separately with probability 1 - 5/2.
14

---

Published as a conference paper at ICLR 2024
Theorem 4.3. Let the inputs (fi, ca) be i.i.d. samples from a fixed but unknown distribution P. For E (0, 1}, we have that with probability at least holds
T
OPT (
1 e +
Σ f((z)
R Ro (D) + + (D) + Rt,
Proof. The proof follows similar approach to Theorem 4.1 with extra details regarding concentration inequalities to exploit stochasticity of the environment. We sketch here the proof for the sake of clarity. In order simplify the notation of the proof, we will write F.... (resp., Ra in place of R7 Te.cr (D) (resp., R7 (D)).
Part 1. In the same fashion as the proof of Theorem 4.1 we can define be the index of the resource that had budget less then round т, and show that
Σ
cu. (x)) B-1,
(B.1)
which is exactly Equation A.1 from Theorem Moreover, in rounds t E Te C [7] we have that It Ø, and by Equation obtain
Σ IET
(a) - + &
(B.2)
which follows Equation AA.1 from Theorem 4.1 with the addition the εr,, term (see definition
in Section 4.2) due to the concentration inequality. Then, since [T] = To U Toker by combining Equation B.1 and Equation (B.2) we can conclude that:
Σ
Cr. (x+4)
Σ Cr.5 (x+)) 15
Σ
C..- (xx) 2 B 2 T εT,8
TETs,cr
TETs
Then, through a chain of inequalities similar to the one of Equation
A.3
we can conclude that
Σ
(A,,)(( p)
Taa
1 Er, R2
To.er"
T
The same arguments used for Equation A.4 readily imply that
1 (e,, - p) 2 To Er, - R2
Σ RET
Rr To
(B.3)
Part 2. Define 5* to be the optimal stochastic policy that achieves OPT f.c = suPtez (xxe(((x) and Ez (nrr)]c(])]]--)- p. By the definition of regret of AP on the rounds Ta with respect 8" the following holds
Σ fx( + (Ae,p- cx(x))) 2 Exng" 1ET
Σ fe(x) + PA,, cc(x))
- RR
LITT
> Eznng
Σ f(x) + (2t,p- c(x))
Rr Er,6
LET
2 T CPT j,e
[Tel - RRc E7,,6-
(B.4)
where we used Equation 4.1 in the first inequality, and [T] TT= To in the third one.
Concluding, By combining Equation B.3 and Equation B.4 we can conclude that:
1 ET, R2,., RD Ri..s
(
OPT Rt.
v
1ST
which concludes the proof.
15

---

Published as a conference paper at ICLR 2024
C PROOFS OMITTED FROM SECTION 5
Lemma 5.5. Assume that the dual regret minimizer is OGD on RT with 1= (k1 E,, + k2mE
2my ( where K1, k2 are absolute constants, and the primal regret minimizer A" satisfies Condi- tion 5.4 Then, both in the adversarial and stochastic setting, the Lagrange multipliers X played by the dual regret minimizer A are such that M := suPre(T]] | 1 S 8m/v.
Proof. We will address the stochastic and adversarial case separately. First, we focus on the stochastic case. The adversarial case will follow via minor modifications.
Stochastic setting. We prove the theorem by contradiction. Suppose that there exists round t2 such that ||all 2 Sm/v, and let E E [t2] be the the first round such that || || 2 1/v. Notice that the dual regret minimizer A (i.e. OGD) guarantees that:
2
8m
9m
Ar 111 S V
+ my S
and Meall S
+ my S
since the dual losses are in [-1, 1]m, and by assumption || S 1/v and || 11-11h 111 I 8m 8m/v. Hence, the range of payoff's of the primal regret minimizer [u]] in the interval T = (l,,..,,t b2) can be bounded as follows
sup
1u ( sup
{IA((E) + ||Alll lppll----p - cx()))l s 1 2 S v
9m
19m
IEX Therefore, by assumption, the regret of the primal regret minimizer is at most:
SEXTET
19m
ET.8-
Similarly to the proof of Lemma 4.2 by applying Hoeffding's 's bound to all the intervals and a union bound, we get that, with probability least 1 8, holds
Σ ET
Ce,, (0)) < [()e
(Ac. c(0)) + 9m
ET.
9m
S - 3
| +
ET,s-
(C.1)
1'
RE
Then, by the no-regret property of the primal regret minimizer we have
(fi(zt) (z))) p)) > E(i(()) - (Ae, pp))
p))- - ((10)))) Er,s
19m
IET
IET
99
11m
Σ
f(0)) + 3
|eell + E(de, (Ne,
ET,
ET
1
AET
EET
RET
9m
19m
Exi
EET
9m
19m
2 (12 41)
ε
&T,5.
(C.2)
where in the second inequality we use Equation C.I for E T.
and in the last one we use that | 2 1/v
For each resource i E [m]. we consider two cases: i) the dual regret minimizer never has to perform projection operation during T, and ii) i, E T is the last time in which At, = 0. In both cases, we show that
Σ cx(x))) S 1ET
Σ
A Ata
+ 2
5m
(C.3)
mp
EE mm]
16

---

Published as a conference paper at ICLR 2024
In the first case, since using OGD as the dual regret minimizer and, by assumption, it never has to perform projections during T, holds that for all resources E [m]]
Ata. Σ (xx) - p) + Aea. RET
Now consider the Lagrange multiplier A such that, for each [m],
1/v if EiET(CL,(E1) p)
X
0
otherwise
By exploiting Lemma 5.3 for single component E [m/] we have that:
Σ (x - (e,,st))))s -p) -p) (1; ))
7/1
(C.4)
2n
ET
which yields the following
M cc,(()) + (A5- )e,
1
Σ IET
Nes (0 (p- (u-c()))
S
Σ 1ET
2 ///
27
De Aezie
(15
)e,,))
2n
Then, since 1 < 1/v by construction, it holds de, S 1/v. Hence, since the dual regret minimizer is OGI and its utilities are in [-1,1]m,
m it holds
1
X n-
(C.5)
Then, we have
(2; r)
(max(>). x2)
1
2
+
2m
2n
2m
V
is easy to verify that for all v. T, and 17 S 2
6
5
+
+ 7
1/l'
S
2n
1211
which implies that
Σ
1 - -
Dent Aezit
5
+
71
221j"
EET
In the second case define &, as the last time step & [ti, t2] in which X, =. 0. Thus, the following holds:
A 77 Σ (x,, - p).
(C.6)
(E(T..0)
Now, consider the Lagrange multipliers A = 0 and X4,2 J. By Lemma 5.3 we have that the
regret of the dual regret minimizer with respect to 0 over [41, is bounded by:
Σ
(21,1 - X;,1 2
7/ < ( + m)
1 TTT
(C.7)
2n
2n
where in the last inequality we use Equation
Similarly, on the interval [ + 1, t2] we have that the regret of the dual regret minimizer with respect to 1/v bounded by
2
(Xi2 -Ain.
Σ (A12- - Xe,)) (ces(x)) - p) p) s
+ <
1
TT
v2 + 1
2 nT,
2m
2
2m
te
'Notiee that the definition of 17 satisfies 1) 2/7
17

---

Published as a conference paper at ICLR 2024
which can be rearranged into
Σ
Ae, (p - c,,(x+)) S v
Σ (p - (-(((()))) +
2n v2 + nT
RE/R.tal
sElt,,aa
Azzáe
1
1
2n u2
Ata.i
27 D2 + 1/2"
(C.8)
T
2
where the equality follows from Equation x, y 2 O.
C.6
and the last inequality from S min(y x, 0) for
Then by summing Equation C.7 and Equation C.8
we obtain
Σ
Aes (p c,)()))) <
A Aea
+
( + n)
+
21Tu2 + 1/T
2n
If we take 17 S 2V7. then the following inequality holds for all v and T
3 +))
5
+ 1/I S
2n
2np²
D2n
This concludes the second case and concludes the proof of Equation Now we can sum over all resources E [m]] and conclude that:
C.3
Σ P- ca(x)) s
A Aesid
5m
+
nuu
1ET
*E[m]
| |1
1eealla
5m
+
1jv
nua
6m
5m
v2 r
1T/2
m
22
Finally, the cumulative utility of the primal regret minimizer over is bounded by
Σ
(Fll)) (Ne, (xx)))) - (12 +1) van
(C.9)
By putting Equation C.2 and Equation
C.9
together we have that
(12 (1)
m
> (t2
t1)
9m 1/
ET,s
19m
2
E
222
1
Hence,
m
9m
Ey,
+
19m
2
Eg.38
(C.10)
12
V
which holds by the assumption that there exists time lo such that || 11l 2 8mz
Thus, we set
= 18E + 361mE + 2mvT)
NNotiee that the definition of 17 satisfies 17 S 2/7
18

---

Published as a conference paper at ICLR 2024
reach contradiction with Equation (C.10) by observing that
2
m (8E 361mET, + mVVT)
m De
9m
E +
19m
E7,6
This concludes proof for the stochastic setting.
Adversarial setting. In the adversarial setting all the passages above still apply by setting &,, = 0. This because, using Assumption 2.1 we can refrain from using the concentration inequality originating the term &T,5*
This concludes the proof.
Corollary 5.6. Assume that the dual regret minimizer is OGD on RT with (k1 k2m&
2mv T -1 where ki, 22 are absolute constants, and the primal regret minimizer A satisfies Condi-
tion 5.4
Then, in the adversarial setting, Algorithm Srrritmm@gurattesss with probability 8 that
m 222 (Er, Er,))
f(()) 2 a OPTY ks LELT
where ki is an absolute constant and v/140. In the stochastic setting, there is absolute constant K4 such that Algorithm Zaamm guarantees that, with probability at least 1 - 26,
Σ f(la,) 2 T OPTY,E EE[T]
k4 m
(E + Er.s)
V2
Proof. Lemma allows us bound the -noom of the Lagrange multipliers which are played by ||elli 8m/u V. This fact, by using Lemma 5.3 readily gives a bound on the terms RD Ra (D) and
RD To>, (D) by observing that
64m y2
sup X.X
a
X
|A MII.IIIISS S 8m
This, together with the definition of = (K1 + hamE + 2mvT) yields the bound
max( R7, S
32m
(KI + K2mE + 2mvT) + m
T
v2
2 &,, + kom& + 2mvT
ki 32m
32m
32m
VT + LVT
&7S + li2
E7,5 +
u2
kg m²
+ E7 VT).
<
2 w²
Then, by Condition 5.4 and Lemma
5.5 the regret of the primal regret minimizer AP is bounded by:
16m
R < 1
&
m
K4
Eg.
22
This concludes the proof by leveraging Theorem 4.1 and Theorem 4.3
19


Reviews:
[{"review_id": "UjCdloEsKT", "reviewer": "Reviewer_fu8A", "summary": "This paper studies the problem of bandits with knapsacks (BwK). In a BwK problem, there are m (m > 1) different types of cost for each action, and the agents needs to maximize the cumulative rewards (i.e., minimize the cumulative regret) before any resource runs out. In classic bandit setting, there is only one cost which is time, so the standard MAB problem is a special case of BwK.\n\nIn this paper, the cost of each action can be negative, whereas the previous BwK works only study the cases where the costs are non-negative. This new setting simulates the real-world applications (eg inventory management and Bilateral trade given in the paper) where the resources can be recovered with time. \n\nThis paper gives a general primal-dual algorithms for this new setup. In both of adversarial and stochastic bandit settings, this paper achieves nearly optimal results (linear gaps for adversarial and logarithm gaps for stochastic). To be specific, in the adversarial case, no algorithm can achieve sub-linear regrets, and the proposed algorithm only has constant gap to the lower bound. In the stochastic case, the algorithm achieves \\tilde{O}(\\sqrt{T \\log{mT}}) regret upper bound (note that the trivial lower bound is \\Omega(\\sqrt{T})).", "questions": "It is not well discussed or stated how the negative cost could affect the problem. Is this new setup invalidate the existing algorithms, or it creates major challenges where we cannot simply use the existing algorithms or the regret analysis techniques?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This paper proposes and studies a novel and interesting problem. It is pretty smart to consider the case where the cost of an arm could be negative. \n\n2. The results are rich and good. It studies multiple cases, and provides good results for them. The results look good enough from my understanding and knowledge.", "weaknesses": "This paper has one major weakness, and one minor weakness about presenting.\n\n1. It is not well discussed or stated how the negative cost could affect the problem. Is this new setup invalidate the existing algorithms, or it creates major challenges where we cannot simply use the existing algorithms or the regret analysis techniques? The algorithm looks pretty similar to the existing works, so as the regret bounds. From the current writing, I am not able to tell how hard the new setting is.\n\n2. This paper's writing and presenting need improvement. It is not clearly presented. For me, there are two major challenges. \ni) There are too many notations and many of them can be avoided. For instance, in Theorem 4.1, it defines \\alpha = \\nu/(1+\\beta), which is not necessary at this point but makes this paper less easier to perceive. \nii) I do not find the clear definition of NextElement(), which makes Algorithm seem incomplete. I did a search of \"next\" but did not find any definition. Probably it is hidden in some sentences, but it is better to have a clear statement of it.", "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": "", "extra_scores": {}}, {"review_id": "IaMfiMfENB", "reviewer": "Reviewer_GRFy", "summary": "This paper studies an extension of Bandits with Knapsacks, called Bandits with Replenishable Knapsacks (BwRK). It proposes a primal-dual algorithm addressing both the adversarial and stochastic cases, with competitive ratio and regret upper bound analysis. The paper also discusses application examples of BwRK and its results.", "questions": "- From my aspect, \"the best of both worlds\" means that the proposed algorithm can achieve optimal theoretical guarantees in two different settings. Could the authors point out how their theoretical upper bounds match the lower bounds in these two settings? As BwRK is a new model, do we have such lower bounds?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- Well-motived model formulation. BwRK is an interesting extension of BwK, and the authors provide application examples as well (Sec. 6). \n- Algorithmic framework. The authors propose a primal-dual template (Alg. 1) that can be applied with various minimizers under different scenarios.", "weaknesses": "- The theoretical results are not clearly discussed. For example, how tight are the theoretical results compared to lower bounds? \n- Lack of experiments. It would be interesting to know the empirical performance of the proposed algorithm. Especially compare the actual performance of this paper's algorithm with known ones in BwK when $\\beta=0$. Are they exactly the same algorithms?", "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": "", "extra_scores": {}}, {"review_id": "4LtVOHsNI5", "reviewer": "Reviewer_divY", "summary": "This paper studies the problem of BwK under replenishable knapsack assumption, where the budget consumption in each round could be negative. The authors propose and analyze a primal-dual framework, achieving best-of-both world performance.", "questions": "1. Any lower bound results?\n2. Connection and comparison with soft constraint satisfaction? It seems to me that allowing negative budget consumption is somewhat related to constraint violation in such round, so the results should be comparable.\n3. Optimizing the coefficients in the regret bound? In bandits these are hidden in the big O term most of the times, but it could be pretty large in many cases, especially when T is not very large. Alternatively, without theoretical justification, some experiments showing that the bounds are empirically tight would be very helpful.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem setup is clearly motivated and introduced. The algorithm and analysis are thoroughly explained and neatly presented. Regret bounds improves on existing results.", "weaknesses": "I believe there are some related work that could be beneficial to be added to the comparison. The line of work I would like to mention is the bandits with (soft) constraints. The authors argue that $\\textit{in BwK problems constraints are required to be satisfied strictly at all rounds}$. However, when allowing negative $c_t$s, it is essentially allowing constraint violation in those rounds.", "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": "", "extra_scores": {}}, {"review_id": "UWZTga3qs3", "reviewer": "Reviewer_fWPt", "summary": "This paper focuses on the bandits with replenishable knapsacks (BwRK), building upon a framework introduced in Kumar and Kleinberg (2022). This paper presents a \"best-of-both-worlds\" algorithm to address such a learning problem. Furthermore, it conducts theoretical analyses of the algorithm under two distinct scenarios: adversarial inputs and stochastic inputs. Finally, this paper presents an exploration of potential economic applications.", "questions": "See weakness.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "(1) This paper presents, for the first time, a best-of-both-worlds algorithmic design for bandits with replenishable knapsacks, accompanied by the corresponding theoretical analysis.\n(2) This paper provides the first instance-independent regret bound under i.i.d. inputs. This complements the earlier work of Kumar and Kleinberg (2022), which primarily focused on instance-dependent analysis in the initial BwRK paper.", "weaknesses": "(1) There are some implicit assumptions that are not well justified. Firstly, the authors say that B=\\omega (T) which seems not practical as it is not evident in which real-world situations a direct linear relationship exists between the budget and the total number of rounds T. A constant budget will result in a non-sublinear final upper regret bound. Secondly, the range of the replenishable resource \\beta is [-1,0] which indicates that such amount of source is close to the consumption cost of other action. This, in turn, suggests that the policy will frequently favor the empty action once the budget B is depleted. It would be beneficial to offer motivating real-world scenarios that illustrate the relevance and feasibility of such a resource range. Finally, in the example of the inventory management in Section 6.2, the reward action s is r_t(s)\\in [-1,0] which is not consistent with the setting in Section 2. Please give a clear justification for this variation.\n(2) The Meta-Algorithm proposed in this paper appears to be a trivial extension of the one presented in \"Online Learning with Knapsacks: the Best of Both Worlds\" (2022). The main difference is that the policy does the empty action when the budget is smaller than one. Furthermore, in terms of theoretical analysis, although the concept of a replenishable resource is introduced, the proofs for Theorem 4.1 and Theorem 4.3 do not exhibit significant advancement when compared to the proofs for Theorem 6.1 and Theorem 7.1 of the 2022’s work. Please clarify the primary contribution compared with previous literature.\n(3) The paper would benefit from the design of experiments to provide stronger empirical support for the theoretical findings.\n \nMinor Comments:\nPage 4: note --> Note\nPage 9: simple simple --> simple", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)