Piecewise-Stationary Bandits with Knapsacks
Authors: Xilin Zhang
Wang Chi Cheung
Venue: NeurIPS 2024 poster (2024)
Keywords: non-stationary bandits
bandits with knapsacks
competitive ratio
Primary area: bandits
TL;DR: We propose novel inventory-reserve algorithms for a piecewise-stationary BwK problem, achieving provably near-optimal competitive ratios adapting to available information against the dynamic benchmark without requiring bounded global variation.

Abstract: We study Bandits with Knapsacks (Bwk) in a piecewise-stationary environment. We propose a novel inventory reserving algorithm which draws new insights into the problem. Suppose parameters $\eta_{\min}, \eta_{\max} \in (0,1]$ respectively lower and upper bound the reward earned and the resources consumed in a time round. Our algorithm achieves a provably near-optimal competitive ratio of $O(\log(\eta_{\max}/\eta_{\min}))$, with a matching lower bound provided. Our performance guarantee is based on a dynamic benchmark, distinguishing our work from existing works on adversarial Bwk who compare with the static benchmark. Furthermore, different from existing non-stationary Bwk work, we do not require a bounded global variation.

Piecevise-Stationary Bandits with Knapsacks
Xilin Zhang Department of ISEM National University of Singapore Singapore, 117578 zhangxilin@u. mus edu
Cheung Wang Chi Department of ISEM National University of Singapore Singapore, 117578 isecwcθnus edu. sg
Abstract
We propose novel inventory reserving algorithm which draws new insights into Bandits with Knapsacks (Bwk) problems in piccovise-stationay environments. Suppose parameters Tminn 7maa E (0, respectively lower and upper bound the ratio between the reward earned and the resources consumed a round. Our algo- rithm achieves provably near-optimal competitive ratio of Ollogí Mmasx/ / Mmin)) with a matching lower bound provided. Our performance guarantee is based on a dynamic benchmark that upper bounds the optimum, different from existing works on adversarial Bwk Immorlica et al.] (2019); Kesselheim and Singla (2020) who compare with the stationary benchmark. Different from existing non-stationary Bwk work Liu et al. (2022), we do not require a bounded global variation.
Introduction
In a bandits with knapsack (Bwk) problem, each action a the action set is associated with latent and random amount of reward earned, (a),, and resource consumed, (a in each round t I,...,T. A decision maker (DM) selects an action 0₂ E IC in round t, and observes bandit feedback (Re(a.), C.())).. The DM targets at maximizing the total reward Σ Ra(a)). while satisfying the hard capacity constraint س C.(a,) & B. Bwk has many real-life applications such as dynamic pricing [Babaiof et al. (2015), resource allocation Zhalechian et al.] (2022). online auction [Balseiro and Gur (2019) and assortment planning AArawal et al. (2019). Stochastic Bwk is first introduced by |Badanidiyuru et al.] (2018), followed by generalizations to concave reward with convex constraints Agrawal and Devanur (2014). combinatorial bandits Sankararaman and Slivkins (2018) 8) and contextual bandits Badanidiyuru et al. 2014); Agrawal and Devanur (2016). In stochastic Bwk problems. the expected feedback [[(RR(a). Co(a) (r(a),c(a)) is stationary for all e IC, t e (1...., T), and sublinear-in-T regret is achievable. Nevertheless, the stationary model could be too ideal many applications.
T
Adversarial Bwk firstly considered in Immorlica et al. (2019) where (re,c:) = ((r)(a).c((a)) (ae) can change arbitrarily over the horizon. They achieve competitive ratio (CR) of Old log(T)) with respect to static benchmark when there are budget constraints. A static benchmark picks fixed optimal action (or fixed optimal distribution over arms), and applies the same action (or distribution) in all T rounds. Kesselheim and Singla (2020) further improve the CR to OOlog d) log()")). Other papers consider different regimes such as unlimited rounds (Rangi et al. (2018)) ). large budget B = (2("") (Castiglioni et al. (2022a)), ) strict feasibility (Castiglioni et al. (2022b)) and approximate stationarity (Fikioris and Tardos (203)). All these works compare with static benchmarks (see Appendix Moreover, adversarial Bwk could be too conservative in certain real-life scenarios. For instance, sales patterns could be stationary for duration of time, but only change during periods of hot seasons/promottion//eew trends, which fits into our piecewise-stationay Bwk regime.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

An abundance of existing works explore adversarial online knapsack problems with full feedback, where (rr, (t) can change arbitrarily but their realized value of {(R, C,(a))aaek, is observed before choosing a, (Karp et al. (199);; Mehta et al. (2007); Zhou et al. (2008) ). Many of these works compare their accrued rewards with dynamic benchmarks (stronger than the static benchmarks used in adversarial Bwk), where the DM picks different optimal actions or in different rounds. However, the dynamic benchmarks considered in the above papers are best single arm benchmark, which only allows pulling a single arm in each round; while our benchmark is a best distribution over arms benchmark (see Appendix A.2 for a more detailed elaboration). Further, the ability of observing [[R((a), Ca(a)) aec before selecting a, is crucial in the algorithm designs in Karp et al. [1900); Mehta et al. (2007): ; Zhou et al. (2008). Their algorithm design cannot be readily generalized to the bandit setting, where the DM only observes (R)( C((a)) after selecting ag.
Another line of recent research investigates non-stationary online knapsack problems with either full feedback Jiang et al. (2020); [Balseiro et al.] (2022) or bandit feedback Liu et al. (022). These works quantify the scale of non-stationarity in terms of both the local variation loc
Σ dist( ( C(+1): (Ye, et)) and the global variation glo = Σx= dist dist(E"_,,re, (re, c,) c))),
where dist is certain metric. Assuming max/loc, glo) grows sublinearly in T, they achieve sublinear- in-7 regret bounds compared to the dynamic benchmark. However, glo growing sublinearly in 7 is rather strong assumption. We could have glo linear in T, even with one change point (see Remark A.3] for more detail). In this work, we consider piece-wise stationary models that allow a higher degree of non-stationarity, which is yet to be studied in all aforementioned works.
Our contributions. Firstly, on modeling (see Section 2). the DM does not know the number of change points and when changes happen. We formulate
single-resource problem, and extend to d-resource problems in Appendix [B.5 with an extra multiplicative factor of on the competitve ratio. Secondly, on algorithm design (see Sections 3.1 and 4.1. we propose novel algorithms which are natural, intuitive and easy to implement. Our idea of reserving inventory based on the reward- consumption ratio provides new insights into the problem. Thirdly, on performance guarantee (see Sections 3.2 (4.).. we achieve a provably near-optimal competitive ratio with respect to a best distribution over arms benchmark without requiring bounded glo, which distinguishes our work from the existing literature. Specifically, suppose there exists parameters Tmmin Tmmax E (0, 1] such that Mmin & re(a), ce(a) & T/max for all a, Our algorithms achieve competitive ratio of Olog (Toog(mmax//nn //mmn)) which requires a novel analysis. We prove the tightness of our competitive ratio by providing a matching lower bound (see Section 4.4). We also run some illustrative numerical experiments (see Section 5) to compare our algorithm performance with Immorlica et al. (2019) and Zhou et (008)) under the soccewise-stationale settings.
model
2 Model
2.1 Problem formulation
Problem dynamics. The online model involves T rounds, indexed as te T = 21, T).. We index an arm as a E K. Additionally, we define the null arm Onalls where no allocation is made when Gmull is chosen. In round E T, the DM chooses an a IC Uqmul) and observes a noisy outcome vector ( (Re(a,, (at)) E [o. 1]2 as the bandit feedback, where RG Ra,)) and (a.))) are the reward and the resource consumption in round respectively. We set Re (a(mul)) Cx (o(att)) 0 with certainty for all I E T. The DM is endowed with B & T units of the resource. The DM's goal is to maximize the total reward, with the constraint that the total resource consumption is most B with certainty. Denote ri = (re(a))aek- = [a] (a))eee and c2 = {c=(a))aek = [E[CC(a)]] consider piece-wise stationary setting, where the planning horizon T is partitioned into L stationary pieces {to = 1,...,t13 1, (ti + I,..., .e)....... (tz-1 + I,...,t,, 4r = T'. On each stationary piece I, we have (re,ct) = (r(9, (() for all t E (ti + 1,...,tt)
We
The DM does not know the number of rounds T. the number of stationary pieces L, the rounds t,,.... t--1 where changes happen, the values of ((r(1) (e(t...))....) and their realized outcomes. Goal and benchmark. Our goal is to develop an online algorithm that maximize the expected total reward - [a)) while satisfying the inventory constraint D Ce(at) & B, which can be formulated as the following dynamic program DP. In DP, X; (Xx(a) Foek is binary decision vari-

---

able indicating whether to pick arm a in round (i.e., X2(a) = 1) or not (i.e.. X((a) = 0). An online algorithm is non-anticipatory in the sense that X, depends only on B and (a.), Ca,,)), X.)
DP = max E
Σ R((a)x((a))
FA max
Σ (t)
t(-1) Σ (a))((a)
ask
1=1
ack
Σ ((aa) BB
s.t. Σ
(1) 1111) Σ (a)=i()) &
1=1 aeR
ask
xx(a) 1
VEET
Σ 21((a E === 1, I....,L
aei
aEK
Xx(a) E 10. Va TET.
(a) 00 Va K.
In non-stationary bandits without resource constraints, the performance bound of an online algorithm is in the form of Σ Re(as) > reward obtained by choosing the best arm in each round, and Reg is sublinear-in-7 regret character- izing the reward loss. In our Bwk setting, due to the inventory constraint, achieving sublinear-in-7 regret is impossible without assuming a bounded global variation (see Appendix (A.3). We denote Ppt(P) as the optimum of an optimization problem P. We aim for performance guarantee of the
Reg, where - is the optimal expected
form Σ Ra(aa)= 2 CR opt(DP) Reg. where opt(DP) is the optimum of DP, CR a competitive ratio, and Reg is a sublinear-in-T regret. Unfortunately, DP is hard to solve. Therefore, we define fluid approximation FA of DP, where RS and C, are replaced by their respective expectations, and the decision variables are fractional. In the following Lemma 2.1 (proved in Appendix C.I). we justify that oFt(FA) can serve as a benchmark for our algorithms' performance since
T Σ Re(a)) >
opt(FA) - -Reg 3
DDP - Reg,
CR
CR
and we aim to derive performance guarantees of the form Σx= Re(ar) > 1 CR opt(FA) Reg.
Lemma 2.1. (PF(F)))))))
2.2 Assumptions, limitations and discussions
Compared with the adversarial Bwk literature, our piecewise-stationar setting has two limitations. The first is on I., the number of change points. When I, is not known, our result is meaningful only when ol /T T 7/min)) When known, our result is meaningful when o(T 1/min) (see Theorem In contrast, existing works on adversarial Bwk generally allow L = T. The second is on the value range of non-null actions:
Assumption 2.2. For all E K, E L). there exists known constants Mmin Mmax E (0, 1] such that Maii & (a), (a) & Tmnxx.
While 7min be small 0 generally, argue that this assumption is mild. Assumption 2.2 holds in many real-life scenarios. For instance, in portfolio management, an investor allocates a limited budget among different investment options (arms) maximize the overall return. The investor has assessments on lower and upper ranges of the expected returns for each investment option. The lower range is usually strictly positive, since the investor would not consider investment options with O or negative expected return. In applications such as dynamic pricing, assortment planning, network resource allocation and energy management, expected profits and consumer demands usually within a known positive value range. We further justify that Assumption 2.2 theoretically in the following Lemma 2.3 provedd in Appendix C.5).
Lemma 2.3. For any online algorithm, there exist an instance for which 0 & rr(a), c((a) & for all K,, T, and that CR> ((log(7maxx) (aoogg(mmxx//// (maxx//mmn)))
Additionally, Appendix C.5 we demonstrate that knowing the values of Mmin Tmax necessary for achieving CR= O(log T/max/ //mnn)))
3

---

2.3 High-level idea of our algorithm
Decomposing (FA) in terms of reward-consumption ratios. Throughout our paper, we fix an optimal solution {xī li=1 1 to FA. We define the set L = {l (1..... L) LOEK 2 (a] > 0}. which indexes stationary pieces where non-null allocations are made under the optimal solution { [=]]__ to FA. For each 1 E L, we define
r (a)xf(a) EBEK (a)xx(a)
Ratio (1)*
E
Mmmn
Tmax 7min
Bi = (t) t1-1) Σ (a)af(a))) aeA
(I)
Mmax
Ratio (1) whose value range follows from Assumption 2.2 is the optimal expected reward earned per unit of consumed resource under 1|=1 We call Ratio the optimal expected reward- consumption ratio of stationary piece 1. Brr represents the optimal expected amount of resources assigned for stationary piece I. To aid our algorithm design, we define the following linear program:
LP B) = max Σ F(a)x(a) aek
s.t. Σ ((a)x(a)= B aek
Σ s(a) < ack
x(a) > 0
VaE K.
Then, we can express (Ft(FA) in terms of LP B) and Ratio (0) BB as follows:
opi(FA) = (4--4-1) opt opt (LP (10) e0) Bf - ((-1))
Σ IeC
Ratio 11) B,"
(2)
IEC
The first equation in 2 can be verified by noting that of is feasible LP c0) Btt(tt 4-1)) for each E (1..... T.), and the concatenation of the optimal solutions of (LP(r(), cl)), B+1(1 (t-1))tc forms a feasible solution to FA. The second equation in (2) holds, by the definitions of Ratio (1) BB and the fact that (pt(LP()-(), c(), B² /tz f(-1))) Enex r1()) (a)x7 (a).
Algorithm design. Fix an arbitrary constant a > 1 (we set a = by default, but our results hold for any constant a > 1). We define M = [log, (Tmax/ //nin) and partition ['mmin/Umass Tmaxx Bmaxx/ Mmin] * - M+1 For each stationary piece 1 E C.
into 2M intervals [a [a-M MM M +1 U[(a" a
we denote m E (-M,..., M - }} as the interval such that (1) (am mm +1]. In the forthcoming discussion, with some abuse of notation, we sometimes write interval [a- a- -++1 (a (a--M a M+1] and refer interval (a"", m* as reward-consumption ratio interval m, or "interval m² in short. Then we can decompose opt(FA) regarding reward-consumption ratio intervals:
M-1
opt(FA)
Σ
Σ
Ratio ( 1(Ratio (1) E aaatll)= B*
17
M Lec
Σ
Σ
Ratio (1) 1(m m)) B,
M lec
The key intuition of algorithm is to achieve reward guarantee for each interval regarding the reward-consumppier
ratio 1mm," m) Ratio and the resource consumption Σ 1(m; m). Bt, which is done by performing two tasks: (a) for each / E L, we guess the value of m such that Ratio (1)* (a"", 11 We guarantee that for at least 1/(M + 1) fraction of requests on each I, our guessed ratio interval are close to the correct interval m (b) for each interval m, we "reserve" B/2M resource units. That is, reserve inventory of B/2M resource units satisfy requests with guessed reward-consumption ratio interval m. When the inventory reserved for interval m is depleted, the DM rejects (by choosing (nat)) all future requests with guessed interval m.
By accomplishing task (a), we ensure that for each E L, least 1mm m)- B /M M+ requested resources served by resources reserved for interval m, generating reward at ratio of at least

---

a" Then, by accomplishing task (b), if the reserved inventory for interval m are not depleted by
round T, our algorithm earns reward of at least a 1(m m) By /M + 1) during stationary piece I. Else, if the reserved B/2M resource units for interval mn are depleted by round T, then the DM earns a reward of at least am* B/(2M) 2 am Eiec (m, m) B (2M) from resources
reserved for interval m, since -eec 1 (m m) Bi & B. By judiciously ana analyzing the relationship between stationary pieces and reward-consumption ratio intervals, for each interval m, we ensure that reward of
Σ Σam "amii = m) B
O(M)
leC
is accrued, which is 1/) of the benchmark resources consumed on all stationary pieces / e L whose (a (1)* E (a am+1]. By summing over {-M, --.,.... M 13, achieve 1/O(M)
fraction of reward 3
Warm-up: Full-feedback deterministic outcome setting
In this section, we introduce the main idea of our algorithm on the bandit model by relaxing the model uncertainty assumptions and specializing the full-feedback deterministic setting: (Re, C2) = (00),c()) with certainty for each f (f-- + I....,tt, tt.. Thus, (r("), c(9) observed the start of the stationary piece I. The DM does not know L and (f1...., t--1) before the online process begins. The DM's decision can fractional, which means on each stationary piece a decision can take the form of 24 {z E [0, 1] Exex z(a) & 1, x(a 2 0 Va e KJ,, resulting in a reward of Leex (00 (a)) and resource consumption of LnEx e (a)x)(() in a round.
3.1 Inventory REServing (IRES) algorithm
is equivalent guess- ing 27, which is equivalent to guessing B /(t 4411. since {a is an optimal solution to
Upon observing RR, Ct) (r(), guessing Ratio (1) (see Section 2.3
LP / (tz - t1-1)). )) In this section. when we say "Line xx", we refer to a line of Algorithm I. which displays IRES. At the start, the IRES reserves B/2M units of resource to each interval mE E {-M, M 1). and each resource unit is reserved by exactly one interval. In Line 5 for
each stationary piece I, we firstly solve LP(r((), c(l), Mmin a²) for each g E (0...., M). and get
an optimal solution zi (0)= (a, (1)* (a))ack- Each Mmmn a a guess of Bf /(t 4--1). For each
q E
we define
|atio (9) = Eoex (0) (a)a (1)*(a)
EEEK e (a)a (9)8
Claim in Appendix B.3 shows that, by guessing q such that Mmmn a is within factor of a from B+/(4 4-11), we also have Ratio to be at most factor of a from Ratio ( As time progresses on I, we go round-robin on the choices of g: E {0, (O..... M) for each
as a guess of (atio (1)*
round t (Lines 7 15 In round E {fi-1 +....... 1.,. we identify m, E {-M,.... M - 1} such that
Ratio (gt) (a mh +1+ (Line 8p. If there remains enough reserved resource units for interval m.
(Line 10 the DM fulfils the t-th request by selecting fractional action 2; 2 2((x)* (Line 11 which consumes resources reserved for m, (Lines 9 [T). Otherwise, the DM selects anall and rejects the
request (Line 13 By 9 we have T (m) {s (I....,4} m, m). which consists of rounds
in (1,...,t) when the DM attempts to fulfil a request with resources reserved for interval m.
3.2 Performance guarantee of IRES
We provide a performance guarantee to IRES in Theorem 3.1
Theorem 3.1. For any given 1, IRES achieves reward of at least
log, (Nhmas (Cemon [imin)+1
OPt(FA)
B
6a? log, (Meaax, Mmiu)
under mild requirements that 4 - 4-11 3 M + V L. In particular, IRES achieves a competitive ratio of O(loga (Tmax/ (noin) if > M(loga (Tmma/ Mminn).
(mmax/Mmnn)).
5

---

Algorithm Inventory REServing with deterministic input (IRES)
1: Input: resource capacity B, 7/minn 1mmax.
2: Initialize | 0, t
91 0, T Te for all m,t.
3: while t & T do
4: Set I =1 1.
5: Solve LP(r(0) c()), Mmin a²) Vg {0, (.......... M) for optimal 2/00* =(a(""(aa)) (a)
c0)
6: while stationary piece not end do
7:
Let (re, ca) (r(1) ())))
It I (g.)*
Find my E {-M,.... M 13 such that Ratio, (9t) E (a " m.
8:
Set T.(m)) T U(t).
9:
10:
E =T Loek (a)))_((a) &
B
then
EM
11:
Pick fractional arms Zt.
12:
else
Pick arm ag = Onull-
14:
end if
15:
gt & M then set 9++1 = 9: + else set q++1 0.
16:
Set t = t 1.
17:
end while
18:
end while
Remark 3.2 (Comparing with online knapsack problems). Our deterministic setting resembles online knapsack problems with adversarial (rz, revealed in each round Zhou et al. (2008), but our (r', remains the same for an unknown number of rounds. Assuming achieve competitive ratio of 2 log( 7max/ + and they provide nearly-matching lower bound. We recover their competitive ratio with an extra 3a² multiplicative factor in piece-wise wise stationary setting and a stricter requirement on B.
[27maxx Zhou et al. (2008)
3.3 Analysis
Denote Ti( (1(m ((m))),,,......))) T-(m) satisfying
where ((m) < ((m) ..... and (mm) is the prefix of
(m) (m)) Ti (m))
Σ s-1
Σ
(2) &
2M
neA
That is, (m) consist up to the last round assigned interval m such that the reserved inventory is not fully consumed. It is evident that if m Co (a.) & B/(2M) - 1, then 7(m) T ((m)
Define (t1-1 + I,...,tt,. the time interval of the (-th piece. The reward achieved by IRES is REW = EieT Eoex (a),) which can be decomposed as REW = M-1 - REW(n) where
(EW(m)
E1(m² = m)
Σ
Σ (((a))((a).
leC
BE(UM M TOO aeA
The set (U (1) NI consists of rounds in stationary piece 1, which requests are not rejected
due to shortage in reserved resource units. The summation Σie (m = m) yields the reward
accrued on pieces where m m. By the summation >M-1 (E)(m), we obtain the total reward accrued with resources reserved for 2M intervals.
Similarly, decompose the benchmark opt(FA) -MM-1 Opt(FA) (m) where
opt(FA)(m)
11(mm m) Ratio (1) B
lEC
To prove Theorem 3.1 it suffices to show (EW(m)
1- opt(FA) (m) for each interval m. 622
as in the following Claim and Claim Then Theorem can established by summing over E (-M,.... M 1).

---

Claim 1. For any interval m E (-M,.. .M 13, if for all (maxfm - 1, -M,, m] we have
T(m) - then REW(") 3 2 opt(FA) (m))
Claim 2. For any interval m E {-M,,.... M - 1}. if for at least one element n2 E {max(m
1,-M3, m) we have ( = T then REW(m) 1-22+11// opt(FA)(mm)
6a
Sketch proofs of Claims 2 Claims J 2 are proved in Appendices C.2 C.3 respectively. We
first show in Claim 3 in Appendix B.3 that on stationary piece / L, there exists a "correct"
(u (the optimal solution to the I
of E {O,...,M); M) such that when selecting decision It
LP c0), Mmin af )) our guess Ratio, (9 on the ground-truth Ratio (1)* (a"" (a"",a"""" +11 satisfies
n" -1 a Ju (a" aaa R (at)) E (am+ a (amm-11j -I] (a
(a we consume resources reserved for reward-consumption ratio intervals my - 1 or m Therefore by our round-robin design, on each stationary piece such that requests are assigned to intervals
When taking fractional action 2
mf m, at least (t: t1-1)/(M
m, under decision
(1t )+ It remains to analyze how many requests are fulfilled by resources reserved for the correct
interval m = m at the correct reward-consumption ratio Ratio (of) as discussed in Section 2.3
For an interval where 7(m) T (m- T (m1m-1) (Claim I case)) there are still remaining resources reserved for intervals m 1, m at the end of the horizon. Hence, for each stationary piece such that m m, at least (t: tt-1)/(M + 1) requests (consuming /M + 1) resource units) are indeed fulfilled by resources reserved for interval m -r m, accruing reward at the
ceward-consumption ratio of at least Ratio /a according to (4). Summing over all 7 such that
m? m, we have (EW(m) > Elec( (latioa (a)) 1mm -m) BT/(M 1) and Claim
is validated, For an interval m where there exists some E {max - 1, 11-M,) M3, m] such that
7(() $ -T(T)) (Claim 2 case). the B/2M resource units reserved for interval are depleted before the end the horizon. this case, some requests on stationary piece I where m m may be rejected, but the (2M resource units reserved for interval have been consumed, generating reward at a rewardd-onssmption ratio of at least a ? a m- Since the total resources that should be consumed w.r.t. interval m under the optimal FA solution is Lie c (m m) B < B, we have REW(m) > m-1, B/ B/(2M) > Elec (1)+ /a²) 1(m m) Br. and Claim validated.
4 Bandit-feedback stochastic outcome setting
In this section, we consider the original piece-wise stationary Bwk model, where the DM receives bandit feedback on outcomes (Re; Ct), and decisions are randomized.
4.1 Inventory REServing with change monitoring (IRES-CM) Algorithm
In this section, when we say "Line xx", we refer line of Algorithm 2 which displays IRES- CM. the bandit-feedback setting, guessing (atio (f) requires estimating (r-(1), c()). To do so, we adaptively partition T into exploration rounds and exploitation rounds. In each round 4, we conduct exploration with probability % Mv /[K (18)((()(() + 1)/VNt (reflected in Bernoulli random variable (t) in Line 7. where d (0, 1) is a confidence parameter and N is defined in (5). In an exploration round & (Lines I we uniformly sample an arm E K. and pull it for N consecutive rounds. We update an estimate (fx(a), (a)) on (r:(a), ca(a))
(r-( (a), el (a)) using the (a), Ca(a)))see7(t information, where 7,5(a) denotes the set of the most recent N exploration rounds before round i when arm a is pulled. That is, we set (a) = fr e (t
1}: a, a} where s, arg max, (E=1 Er=ta 1(a, a) N]. We define
27 log (2/5)
(a(a) ( (a)
aaaa) Emeriaa) Co(a) N
N (1- 11-1/v)2 Muin
(5)
N
The estimates fr. & have two sources of error: error due to random noise, which decreases with N; and error due to non-stationarity, which increases with N. We set N according to balance these two emror.. We let T.R denote the set of exploration rounds.
7

---

take turns to pull arms according to decision ((4))s
In exploitation round t (Lines
17 25
which is very similar to Algorithm with (fe, &e) in place of (re, cz). We define
Eoex (())) ()) (a) (f) - max { min Ratio,
Loek F((o)a) (a)
(nc) MMM aa-M).
Ratio
which can both be interpreted as guess of (atio at any round during stationary piece I. We reserve (/ units of resources for each interval m { f-M,....... M 1]. In round t, we serve request / using resources reserved for interval ni such that (t), E (a" a. If interval m, has remaining reserved inventory, then we pull arm a, a with probability (()))( or 0, 2f00)* in short. We let TT((m)))))))))(( denote the set of exploitation rounds using resources reserved for interval m. We finally highlight that the major performance difference between IRES and IRES-CM is due to estimating (re, ce) by (fr, G,,, which is detailed in Section 4.3
(a""
Algorithm 2 Inventory REServing with Change Monitoring
1: Input: resource capacity B, rate y, bounding parameters 7miiny 7max-
2: Set 7, Ø for all and 7. 7 Ø for all m, t.
3: Pull each arm a E IC for N times, get fr(a), (a(a) as in
4: Set = || 1.
5: while < do
6: Solve LP(ft, &c Mmin a4) Vg E {0, .0,,,....4.. M} for optimal $/00* = (3(0)((() (a)laxx.
7:
Sample (t) Bern(Tt).
8:
Ut) = then
9:
Pick arm
Uni(K), pull a, Set (s) = 1 for Se (t..... N 1}.
10:
11:
Set T. T Uft...., for SE (t...., t + N 1}.
12:
Set l = L L N, (f),))) = f--NC-N)
13:
Update ē(a),, (a) as in
14:
else
15:
for q 0...,,
MM do Set =
16:
Determine m (-M,...; ...; M - 13 such that (t)x E (a am
18:
Set T ((mea)) T
((me))
Ult).
19:
if > T((() Ca(a.)
<
2nd
B
then
Pick arm at 2t (9+)*
20:
21:
else
22:
end Pick arm 0t anull-
23:
24:
Set t t+ 1, (fr, â.) (f--1,
25:
end for
26:
end if
27:
end while
4.2
Performance guarantee of IRES-CM
We impose the following assumption on the ranges of B, opt(FA).
Assumption 4.1. min opt(FA)) ((LLK/ [K]T)) where ②2(-) hides multiplicative factors in terms of log,, 1mmax//minn (1/8), (log([K)) 1).
The performance of IRES- CM as follows: Theorem 4.2. For any given 1, with probability least 1 - 2| (log,, (Amax/ (oonax//mmi/ Mmin L + T)8. IRES-CM achieves a reward of at least
o(1)
(opi(FA) (0(VIAA)-(LLVV(AA))
10a4 log (Imax/ )
8

---

where o(-) hides multiplicatiive factors in terms of v /M/B and Ō(-) hides multiplicatiive factors in terms of loga /Tmax//hmin/ (oonin))loo(//0)) [[] + 1). In particular, IRES-CM achieves a competitive ratio of Olog, (hhax/ /miin)) as long as I. of VT. Mmmn))
under Assumption 4.1
The proof of Theorem can can be found in Appendix C.4 We provide a thorough comparison of our performance guarantee with existing works adversarial and non-stationary Bwk in Appendix A Remark 4.3 (Improved performance with known L). If the DM knows L, Assumption 4. can be relaxed to
min B, (P((F > S L.IKNT))
Furthermore, in our performance guarantee in Theorem 4.2 the deductive term
from opl(FA) can be improved to Ó(y by setting the exploration parameter Yt in IRES-CM. Without prior knowledge of L. the deduc- tive term ([LL/K]N) = o(T) if L = o(vT Mmin);; with prior information of L, the deductive term Ö (T) o()) if = o(T Mmiu)..
MVL [og(L/ + 1)/V
Remark 4.4 (Deterministic setting with bandit feedback). In our full-feedback deterministic setting, since ((0),(()) is given at the beginning of each stationary piece, our performance guarantee is independent on [AC], L. In a bandit-fcedbart deterministic setting. IRES-CM can be applicd by setting N 1. In this case, under Assumption 4.1 IRES-CM achieves reward of least
o(1)
(1P(FA)-O((//KTT))) - -((W/KI)))
2 loga (Tmax/ (hnin)
4.3 Analysis
We denote 0z(a)= min(s: : 8 (a)) the 1st element in (a). We partition the exploitation
round set 7 T into two sets (1mm) and fT(m) i..., TH!T = (mm) Ufl(mm, fl(m) 7T = Ø.
time index TH(()) belongs to the set 71(m) (referred to as "successful exploitation rounds
regarding interval m²) if and only if the following condition is satisfied for all a E K::
((ra(e),ca(4))een = {(Ta,(a((a), ())()))))) Vs (or(a),.....
(6)
For & E 7((m)) (referred to as "failed exploitation rounds regarding interval m²), inequality violated for at least one K. We denote ?l(m) (m'(m)(1), (2(m)(2), (2),...) where _((m)
6 is
(((m)(2) (2) .... We let Fl(m) be a prefix of (((m) satisfying
(1mm)
(1(0)))))) E 7l(m)
Σ Σ (ysto)()) (a,)m)(s)) &
B
2M
which consists up to the last exploitation round satisfying (6) for interval m. such that the reserved
resource is adequate. If Σ T( Ca(as) & B/(2M) - 1, then T((m) -lmm).
Sketch proof of Theorem 4.2, Recall that the performance guarantee of our algorithms in the form of IT= Ra:a:) e CR opt(FA) - Reg. The proof consists of mainly two steps: (a) we derive the CR= (() by bounding two different cases of interval m in a similar manner Claim and Claim
2 (see Appendix C.4 with (mmm (successful exploitation rounds in IRES-CM) in place of T (m) (all
rounds in IRES): (b) derive the Reg= O(LVIKNTT [T) by bounding the number of exploration
rounds [ and failed exploitation rounds U F((m)) (see Appendix B.7)
Comparing performance of IRES and IRES-CM. We highlight that the major performance difference between IRES and IRES-CM is the loss caused by estimating (rt, cz), reflected in the
following aspects: (i) reward loss caused by exploration (upper bounding [7R)): (ii) (a(()) contains
change points, causing failed estimation of (re, ct) (upper bounding U M-2 7((m))) (ii) 7,
does not contain change points, but the discrepancy between (rt, c.) and (fz, 4) results in assigning
Ratio (1) (estimated by Ratio, to the wrong interval. We remark that the losses due to (i, ii) are accounted for in Reg, while (ii) is accounted for in the CR.
(4)

---

4.4 A lower bound on competitive ratio
We complement analysis by showing the tightness of CR (see Appendix C.6 for proof).
Theorem 4.5. Consider fixed but arbitrary 1, and set Mmin a Mmax 1 for arbitrary E Zo0 For any online algorithm, there exist an instance for which 7mmin & rr(a), Cr(a) & Vmmax for all E K, T, and that 2 Re(ax)/opg (otts)/pp((AAA) (F((FA) & (111 log log (hnnx///mia))) Pmmia).
5 Numerical Experiments
We run numerical experiments single-resource problem where L 2, T 20000 (each stationary piece has 10000 rounds), ( B 9360 and we set a = e for our algorithms. The rewards and resource consumption in all rounds are uniformly distributed within a [-0.2, +.2 range from their mean values. compare the performance of IRES-CM with [mmorlic et al. (2019)'s algorithm and Zhou et al. (2008) algorithm. Recall that Immorlica et al. (2019) focus an adversarial Bwk problem and achieves a CR w.r.. a static benchmark. Zhou et al. (2008) study a full-feedback adversarial setting and achieves CR w.r.t. single best arm benchmark. In Figure [ each curve represents the average cumulative reward over 10 simulations, and the shaded area around each curve marks the variance over the simulations. We provide Zhou et al.) (2008)'s 's algorithm with extra information of (rt, o.) before making decisions each round, and compare the performance of algorithms with the linear program benchmark FA (dotted curves in Figure
Performance comparison of algorithms
Performance comparison of algorithms
1el
Immorlica al.
Immorica
Zhou et al. Benchmark
Benchmark
Cunulative reward
0.8
0.6
0.4
0.
0.0
0.75
1.00
0.00
0.25
0.50
1.00
1.25
150
175
2.00
(a) FA optimal solution: single arm
(b) FA optimal solution: mixed arms
Figure 1: Performance comparison of algorithms for peccewise-stationaal Bwk
(1) (() 0.5, (()))()) (2) for stationary piece 1 and set (1) (2) (2) = 0.5, (1) ())) for stationary piece 2. In Figure (b. we switch the values of (2) and (2). i.e., setting (1) 0.5, x()) 1. Observe that IRES-CM outperforms Immorlica et al. 2219)'s algorithm in both cases. This is mainly because Immorlica al. 2019)'s algorithm is designed for more general adversarial Bwk setting. In contrast, we utilize the extra information that Main 0.5. Therefore, IImmrlica et al. (2019)'s algorithm is significantly more conservative than IRES-CM in reserving inventories for future customers. Zhou et al.] (2008)'s 's algorithm outperforms IRES-CM CM in Figure I [)). but performs worse than IRES-CM in Figure bb). This is because that in Figure T a). the optimal solution of the benchmark FA chooses single arm on each stationary piece, which aligns with Zhou et al. (2008) single best arm benchmark. Zhou al. (2008)ss algorithm performs well with the extra information of (re, before making decisions. In Figure bb), the optimal solution of the benchmark FA chooses mixed arms on the second stationary piece, where (1) 1212, x (2) = 0.872. The numerical results are consistent with the theoretical results that Zhou et al. (2008) achieve sub-optimal rewards compared with a best distribution over arms benchmark, while our IRES-CM performs well. Finally, our experiments are on Surface Pro 7 with an 103504 processor. All results can be produced within 30 minutes.
In Figure a)).
10

---

Acknowledgement
We would like acknowledge the support from the Singapore Ministry of Education AcRF Tier Grant (Grant number: T2EP20121-0035),
References
Agrawal, S., Avadhanula, V., Goyal, V., and Zeevi, A. (2019). Mnl-bandit: A dynamic learning approach assortment selection. Operations Research, 1755511433
Agrawal, S. and Devanur, N. (2016). Linear contextual bandits with knapsacks. Advances Neural Information Processing Systems, 29.
Agrawal, S. and Devanur, N. R. (2014). Bandits with concave rewards and convex knapsacks. In Proceedings of the fifleenth ACM conference on Economics and computation, pages 989-1006.
Babaioff, M., Dughmi, S., Kleinberg, R., and Slivkins, A. (2015). Dynamic pricing with limited supply.
Badanidiyuru, A., Kleinberg, R., and Slivkins, A. (2018). Bandits with knapsacks. Journal of the ACM (JACM), 1555):1555.
Badanidiyuru, A., Langford, J., and Slivkins, A. (2014). Resourceful contextual bandits. In Confer- ence on Learning Theory, pages 1 109-11134, PMLR.
Balseiro, S. R. and Gur, Y. (2019). Learning in repeated auctions with budgets: Regret minimization and equilibrium. Management Science, 65(9):3952-3968.
Balseiro, S. R., Lu, H., and Mirrokni, V. (2022). The best of many worlds: Dual mirror descent for online allocation problems. Operations Research.
Castiglioni, M., Celli, A., and Kroer, C. (2022a). Online learning with knapsacks: the best of both worlds. In International Conference on Machine Learning, pages 2767-2783. PMLR.
Castiglioni, M., Celli, A., Marchesi, A., Romano, G., and Gatti, N. (2022b). A unifying framework for online optimization with long-term constraints. Advances in Neural Information Processing Systems, 35:33589-33602.
Fikioris, G. and Tardos, É. (2023). Approximately stationary bandits with knapsacks. arXiv preprint arXiv:2302.1 14686.
Immorlica, N., Sankararaman, K. A., Schapire, R., and Slivkins, A. (2019). Adversarial bandits with knapsacks. In 2019 IEEE 60th Annual Symposium on Foundations Computer Science (FOCS), pages 202-219. IEEE
Jiang, J., Li, X., and Zhang, J. (2020). Online stochastic optimization with wasserstein based non-stationarity. arXiv preprint arXiv:2012.06961.
Karp, R. M., Vazirani, U. V., and Vazirani, V. V. (1990). An optimal algorithm for on-line bipartite matching. In Proceedings of the twenty-eccond annual ACM symposium on Theory of computing, pages 352-358.
Kesselheim, T. and Singla, S. (2020). Online learning with vector costs and bandits with knapsacks. In Conference on Learning Theory, pages 2286-2305. PMLR.
Kim, W., Iyengar, G., and Zeevi, A. (2023). Improved algorithms for multi-period multi-class packing problems with bandit feedback. In International Conference on Machine Learning, pages 16458-16501. PMLR.
Kuszmaul, W. and Qi, Q. (2021). The multiplicative version of azuma's ' inequality, with an application to contention analysis. arXiv preprint arXiv:2102.0507.
Liu, S., Jiang, J., and Li, (2022). Non-stationary bandits with knapsacks. Advances in Neural Information Processing Systems, 35:16522-16632.

---

Mehta, A., Saberi, A., Vazirani, U., and Vazirani. V. (2007). Adwords and generalized online matching. Journal of the ACM (JACM), 54(5):22-es. es.
Rangi, A., Franceschetti, M., and Tran-Thanh, (2018). Unifying the stochastic and the adversarial bandits with knapsack. arXiv preprint arXiv:1811.12255
Sankararaman, K. A. and Slivkins, A. (2018). Combinatorial semi-bandits with knapsacks. In International Conference on Artificial Intelligence and Statistics, pages 1760-1770. PMLR.
Sivakumar, V., Zuo, S., and Banerjee, A. (2022). Smoothed adversarial linear contextual bandits with knapsacks. In International Conference on Machine Learning, pages 20253-20277. PMLR.
Yao, A. C.-C. (1977). Probabilistic computations: Toward unified measure of complexity. In 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), pages 222-227. IEEE Computer Society.
Zhalechian, M., Keyvanshokooh, E., Shi, C., and Van Oyen, M. P. (2022). Online resource allocation with personalized learning. Operations Research, 70(4):2138-21) 21611
Zhou, Y., Chakrabarty, D., and Lukose, R. (2008). Budget constrained bidding in keyword auctions and online knapsack problems. Proceedings of the 17th international conference on world wide web, pages 1243-1244.
12

---

A Comparing our performance guarantee with existing literature
A.1 Comparing with adversarial BwKs
Immorlica et al. (2019) (achieving (Td) competitive ratio) and Kesselheim and Singla (2020) (achieving O[log( d) (T)( competitive ratio) study the adversarial BwKs, where the ad versarial bandit feedback (Te (rr(a,), Ce(a))) is revealed in each time step after pulling arm az. Their setting more general than ours, since they require no boundedness assumption or piece-wise stationary assumption on their outcomes. Note that if our 7mii can be expressed as function of T, i.e., Mmnin T for a E (0, 1), our result can extend to multiple resources and achieve a competitive ratio of (Td)))(T)) (see Appendix B.5). However, we highlight that their result do not imply our result, due to the following two reasons.
Firstly, they consider a static benchmark, dubbed FD, which is FA with the additional constraint that 2.7 xx for all 1 L; while we compare our result with the dynamic benchmark FA. Specifically, Immorlica et al. 2019) prove that no algorithm can achieve competitive ratio smaller than T/B w.r.t the dynamic benchmark. We further improve this lower bound to ((T/B) in Lemma 2.3] a) by setting L = T/ B, and provide matching lower bound of ((log(T)) comparing with opt(FA) when M/min > 0. Secondly, they have more restrictive assumptions on the value ranges of B and opt(FD). Specifically, Immorlica et al. 2019) assume opt(FD) B/|K] > ((T7/1), which is strictly stronger than our 1.sumptionn4.1
Some research works consider more specific regimes, including Rangi et al. (2018); Castiglioni et al. (2022)); Fikioris and Tardos (2023). We highlight that all these works still compare with static benchmarks. Castiglioni et al. (2022a) focus on the regime where B = (T(T) and achieves competitive ratio of T/B. Fikioris and Tardos (2023) provides a competitive ratio depending on (max: /rt3/ ming(re). max, [ ming {cr f). Rangi et al. (2018) achieves a sublinear-in regret in
different setting with round limit (sales stop when the inventory is depleted). Therefore, their result is incomparable with ours.
Some recent papers focus on linear contextual Bwk with adversarial contextual vectors Sivakumar ctt al. (2022) (achieving ((d))) competitive ratio) or with multiple but stationary customer classes Kim et al. (2023) (achieving sublinear in T regret). We highlight that contextual vectors for each arm are observable before making decision in each round, while our model only observe bandit feedback after an arm is chosen. Therefore their results do not generalize our setting.
A.2 Comparing with adversarial online knapsack problems with full feedback
In our Section 3 we discuss a warm-up setting where { (R) C+(a)) aek: is observable upon the arrival of the round customer, which is similar with adversarial online knapsack with full feedback (Karp et al. (1990); Mehta et al.] (2007); Zhou et al. (2008)) Zhou et al. (2008) is the most closely related to our work, where they start off from an online matching problem and extends the results to the online knapsack problem. They define LB- = miin,.(re(()//c(()))
UB = maxo, (a)( (e(())))))))))))))))))) and achieves competitive ratio of log( UB/LB w.r.t. a dynamic best single arm benchmark, which differs from our FA by setting (a(a) E {0, for each a, I. Our FA, on the other hand, is a best distribution over arms benchmark. In fact, for stationary Bwk, (Badanidiyrru al. (2018) show (see their Appendix A) that the best single arm benchmark is strictly weaker than best distribution over arms, which could noticably affect the achievable CR. It is evident that in the srreiisesttationayy setting, this is also the case.
Additionally, this line of works crucially require knowing (a), C+(a)) before making decisions. By contrast, we take a different approach in algorithm design in Section allows a natural generalization from full to bandit feedback shown in Section
A.3 Comparing with non-stationary bandit/fulll online optimization with knapsacks
In Balseiro al. 2022); Jiang al. (2020): ; Liu et al. (2022). they measure the non-stationarity of a vime-varying knapsack model with a quantity called the global variation
glo Σ dist E (m..a)
T
13

---

While dist can be any metric, to give more concrete idea, we highlight an example form Liu et al. (022)) being
dist((r; c), (r', (r', (ax + max(
aEk.
aEX
They all have boundedness assumption on glo. In our setting (glo unbounded), their algorithms incur linear-in-T regret even when I. 1, and no non-trivial competitive ratio established in their work. To see the case of I. but glo = ( consider the case of K. = (1), and we have
(11(1), = -... (1T22()), = (1,0.5).
but
(1)2+-((), ... (rr(1), (0.5, 1).
In this case, verify that
T dist (mn (TT, (r1.))))
dist Σ (T 0.5,
have glo 0.57 despite I.
B
Auxiliary results
B.1
Notation
For functions f(x:) R30 - R2 and g(x) R200 - R20, we say f(x) O(g(z)) (resp. Mg(()))
there exist positive constants C and such that for all x t n, f(x) C-g(z) (resp. f(z) > C-g(z)).
We use (g)()) (resp. ((g()))) hide logarithmic terms in other than g(z).
B.2 Concentration inequalities
Lemma B.1 (Multiplicative Azuma-Hoeffding Inequality (Kuszmaul and Qi (202
XI.... Xa
[0, c) are real-valute random variables, and (Fn) Y7 is filtration. Let Li=1 Og where as veal-valued constants.
(i) Suppose E[ a; holds for all i (l,..., n} almost surely. Then for any E (0,
3c
log ()) 3 1-
Pr
X, &
1 [
(ii) Suppose F[X, > holds for all i f1,..., n. almost surely. Then for any d e (0, 1).
n
2c log (2)
Pr
X;
10
3 1-6.
Lemma B.2 (Lemma 2.1, Badanidiyuru al. (2018). Let X1 II...., XN E [0, be random variables.
Let X N.N X, be the sample average, and let μ > XI,.,, X Then, for any
8 10,
Pr (I (1X-11p -1|+ log(//)) + + 4log(1/6)
35.5.
B.3 Main claim on reward-consumption ratio
Recall that 2 (g)* is an optimal solution to LP(r()), c Main a²)), and x² is an optimal solution of LP ((()) cl BBt ((t: f)-1) which is optimal solution of our benchmark. In the following Claim 3 we show that the round-robin technique in IRES ensures that, on each stationary piece I at
(g)* for at least one e (0.... M] is close to x in terms of both the resource consumption and
the reward-consumption ratio. This leads the important result that for all E (42-1 I,...,4),
m, E {mf 1, 1,m,).
14

---

Claim 3. On stationary piece I E L, there exists E {0, 1, (0.1......M. M) that satisfies both
Amin a -1 < Lnex e (a)x & Linr e0 (a)o² (af (*(a))
(a) & Umin a
g > 0
(7)
(0- EeEk (a) (a) & Loek (a)x
(9) (a) $ Mmin a
q
0
and
Lnex (a)z)
(9 (a) (a)
E Lack E (a)a
Lnex (a)2,
(a)
Enck cl0
(9 (())
(a) LeEK (a)at()
a
Eeex cll (1)x) (a) 10 )+
(8)
Proof of Claim The existence of of satisfying is evident, since Mumin a Mmin and 7min
a M 7maxx To show that qt* also satisfy 8 define
d DEE c0 (a)o (a) (a)
(9)
Enex clt) (a))((a)
and claim that
Σ (a)af & Σ 100 (a)x (1 (()) & d Σ (a)a(()))))
(10)
The first inequality in 10 holds since B//(6 ty-1) Luex (a)xf
(a) & Mmin aa. Therefore, the resource constraint in LP(r((), (())),))))))))))))))) B (t1 t(-1)) is tighter than LP(r((), d0) Mmia a
We prove the second inequality in 10p by contradiction. Suppose Eaek (l)) (a)
(of
) (a)
d(l) E (a)= (a). Then we set 21 It ) (d(() and have
Σ (a)alaa) = d
Σ
(a)x)
Σ (a)a = B+/(4- - 4-1).
REA
acK
aek.
In this case, Iд is a feasible solution to LP ( B, (t: 1(-1)) and we have
(
(a)ai(a)))
1
Σ (a)x (9tt)
Σ (a)
d
aeiC
aEK
aeK
contradicting the fact that of an optimal solution of (P dli), combining and (OP, we establish
,,),, B$ (1r t1-1)). Therefore,
ELSR 100 (a)af())) Eaex c00 (a)xt(a) & d() Eeex (a)x, (9 (a*))()))
EEEK (a)a)) Σnex c0 (a)a (a)
(a)
Loex cll) (a) (0)))(a) (a)
To establish 8 it suffices show d(l) a. By and (9). it is evident that d() a when
q.t 0. of 0, then constraints Eaex 27 (a) & 1 and Eaex 2i (9 (a) & 1 are not tight in both LP(r(), (0)) 1B/(t(tt t(-1)) and (P(1(), cl) Mauin). In this case, both LPs are knapsack problems and have closed-form solutions of
47 (a)
(1: (1-b-)) e
B
a arg max
(a))
eWia))
41
10 lof)) (a) =
Tinin (())
= arg max
{
(())
(a))
otherwise
0
otherwise
Therefore, have
EBEK (1)) (a)a)) (9) (1))))))))))))))
(a)
Eoex ~00 E (a)x
Eoex c!l) (a).r)
(q, (a)
Eoek (a)x
which shows that d 1 when of =.
15

---

B.4
Decomposing ratio of REW to opt(FA) in deterministic setting
Recall
{(m)
(m)) (n) Σ Σ (1m)))))22,)0))0000 &
B
2M
and J. = 111-1 + 1,...,tth
tr..
Then for the reward achieved by IRES, we have
REW Σ Σ re(a)xr(a)
TET aek
Σ
Σ
Σ
(((a)
TeC NJ aek
Σ
Σ
Σ re(a)x;(a)
JeC te
1 RS-M T(m)
n aek
M
Σ
Σ
1(m m)
Σ
Σ (a(a)))(())
M IEC
te(UM=->e T(o) n aek
M-1
(EW(m)
m=
M-1
min(m I,M 1)
Σ
Σ
1mm = w)
Σ
Σ (r)a) (11)
3
m= M to max (m
M) lEC
s =u T(n) n aeK
Inequality 11 holds since by summing over w e [max(m 1, M), m, min(m + 1, M.M 1}} for each M...., M 1}, we repeat the sum for at most times.
For the reward achieved by FA, we have
LoEK (00) (a)at(a) (a)
opu(FA)
Σ
Br
(12)
Lxex (a)xt(((
lec.
M-1
Eaek (a)=
Σ
Σ 1(m = =m)-
B²
Eaexel (o)2
M lec
opt(FA)(m)
M
Inequality (12) follows from
Therefore, the ratio of the reward achieved by IRES to opt(FA) can be decomposed as:
EIEr Eoex (a)
opt(FA)
MM REW (m)
M
M OPt(FA) (m)
M--1
1, 1}
Liec 1(m w) LiE(UM n. Lnex (e(a)x((a)
(13)
ΣM-1 M Eiec (mm) = m) Eocr (00
Enex (a)) B²
Then, to prove Theorem 3.1 it suffices to show
REW(m) (m)
1 (2M 1)/B
133
(14)
M Opt(FA) (m)
6a2 M
16

---

To prove 11). we focus showing in Claims and 2
mmmnnmn+ 1 Liec 1 = w) 2u 1 N. Lnex re(a)zz(a)
REW (m)
opt(FA) mm)
Liec 1(m) = m) Lner el0 (a)=
Lask dl0 (a)= B
(2M 11/B
6a2 M
for each m {-M, , M 13.
B.5 Extending results to multiple resources
Our results be readily extend to the multiple-resource case, with [ d resources indexed by e Z. An upper bound for a multi-resource allocation problem (corresponding to FA in the single-resouree setting) can be formulated as:
FA MUL
Σ (1) 1-1)
Σ
U (a)x1(a)
== max
L
s.t.
(11 1(-1) Σ
(a)a((a) & B
ViEI
osk
Σ (a)
&
VI = 1, I.....L L
aek
<r((a) > 0
Ya E K, 1 = 1, 1,.... L.
which is evidently upper bounded by the following LP:
FA MUL-U
(44 4-1) Σ
1
(a)x((a)
ask
s.t.
(11 11-1) Σ
Σ
(a)
sz(la)
oe
Σ ma(aa 1
A1 = I....,
aeA
(1(a)
Va K., = I,..., L.
is evident that the LP below achieves reward of least 1/d fraction of opt(FA apI(FAMIL-U)
FA MUL-F
(ti 1 >
(1)
(a)x;(()
max
aek
s.t.
(t) 1(-1) Σ
Σ 12 (a)
xi(()) & B
oEK
Σ
= I,...,L L
aek
(a) > 0
Wa E K, 1 = L.
Therefore, FA MUL is transformed into a single-resource allocation problem FAA MUL-F with an extra multiplicative factor d in the competitive ratio.
B.6 Core lemma reward-consumption ratio in general setting
- 1} a, a} where s; arg max, (X--1 r-1 a) N) consists of the most recent N rounds where arm a is sampled by exploration; and (a(a) min(s: (a)) the 1-st element in (a)) Recall that
Recall that set (7( {T E (t- S
1(a,
( Ca(a)
(.(a) Eee (a)
a,(a)=
17

---

are the average resource consumption and the reward earned for the most recent N pulls of arm
Additionally, recall that we define a.(1) { (a) Joek solution LP &t, Mmin a²) (a being the optimal solution) for = ,,
We further define
EMTTPCO) (a(a)
Ea (s
Ce (a)
F2(a)
N
N
as the average mean resource consumption and the reward earned for the most recent pulls of arm Note that when condition (6)
{(ra(a), Ca ca(a)) = ((Tor(a) (a), (a) DEE Vs (o.....,t
satisfied for all e K. then rounds s for,...,tt) f] are on the same stationary piece and we have (a) = ce(a), Fr(a) re(a). We let x(") { [a)] be a solution to LP(r,, Ct Mmin a²)
( being the optimal solution) for q = 0, , M 1. By Claim
we know that there exists
o: M. such that for all E Jr.
Amin aa O < Enex (a)= & Laek ((()) (a) & Mmin o
< Laek (a)af(a) & Ca (0 (())
(a) & Mmann aa
(15)
(9t (a)
q
We show in the following Lemma B.3 that when condition
6 is satisfied for all a E K. our decisions
have several nice properties which facilitate our proofs.
Lemma B.3. Fix an arbitrary e (0, 1]. For any t > or(a), if
((r((a). cala)) {(rm (a)(a)) co, Ca (a)(()))))) leEk. Vs (ot....,tt)
then with probability at least 1 2 6, then all the following inequalities satisfied for all Tr:
(( (a)
Eoek rela)a (0
(a)
Vā. Losk Pcla) (a)
(16)
Va
&())a
Enek ct(a)
Enekdla)at (a)
Σ In((a)a (a)
(
Σ
(000 a Σ (r(a)a((M+
(17)
ava
ack:
aEk
Lnek P((a) (a)
Lark (a)x & saya. Laek Pela)s (9 (a)
1 =
ava
Eoek (())a) (a)
Eoek cl0) (a)x((a)
Eaex ca())s))) (1"))))((((())
(a(()
(18)
Proof of Lemma
B.3 We define
2
log
max
log
log
N Mmin
N M/nax
N
Maiin
Then by the multiplicative Azuma Azuma- Hoeffding inequality (Lemma
B.1 for any K. have
Pr[(1 (a) & (a) # (1+ ()a(aa)
> 1 5
(19)
Pr[(1 ()) & (a) & <)r((a))
8. re(a) & N Tmax
(20)
The above probability bounds (9 and 20 hold since
N Tmin
Σ Caaa,
Σ T (a)
(T),
We set 11-38
(1-3e)² = 1/a, and therefore
27 (2/5)
(1 - 1/ 1/v))2 1/min
Our following discussion conditioned on the good event that both (9) and 20 hold for all e K. This good event holds with probability 1 - 2
18

---

Validating (16.. Given that 19
and 20 hold, we have
1-c Lask P
(a)
Dox re(a)s, oa
it
(a)
1 c
P(ex (()) (a)
1 1+6
Eoex G(a)at (0)
(a)
(a))"()) (a)
Losk c(())) 1 (()
+ -e))- mmex fr(a)a 1 (a)
Liex
(a)
Loex P Pc(a)a, (()) (a)
(18
(a) Loek c(a)at
(a)
1 26
Loek c((asst (a) (() (21)
Since 1 - 3 1 - 3c = 1/a. 21
indicates
16
Validating 17 is evident that by letting # (a)
1
Et
19
(a)/(1 c), we have
( (a)
Ed(a)e 1 (a) = Σ 4(a)
(a)=
1+c
aek
ack
Ft ( (a)
Σ (1++))((a)
(22)
1+e
ask
Σ c((aa (a)
7min
0²
Since $ (9 (a) = 1.1 (a)((1 + c) is feasible
Inequality 22
follows from inequalities
19
solution to LP (P Ct Mmin a²") we have
(9 (a)) (a)
Σ aek
r2 (a) (())
(a) 3 Σ (((a)
It
I+c
ack
It (((*(a))
Σ f(())
(1+ e)
aEA
>11 2 Σ ft(a)
(a)
> (11 - 3c)
Σ rr(a) (a).
(a).
(23)
ask:
Similarly, by letting x,
(a) (1 c),,
(1 )+
(a), we have
(a) Σ
(1t)
E((a) (1-c)at (at))(((()
aek
Σ a(a)
(1 e)a² (af (())))))
(a)
Σ (()a)a )* (a)
Emmin a²
Since L (9 (a) = (1 e))
(1*)+ (a) is feasible solution to LP( Ct Mmin a ), we have
la )
E f((a)) 41 )+ (a) (1+ Σ ra)a) (a) Ir((a)=
(a)
1
E
Σ
(a).
2e
atk
aek
(24)
Since (1 3c)2 1/a, putting 23 and (4 together, we have
1
r((())
1a ) (a) a Σ r:(a)a (a 1+ (a) & Va.
Σ (r((a)(( 19 (a).
(25)
Va aek
aek
aek
19

---

By 10 in Claim
we have
19 x
(a) & Σ
& Σ
r()a (at) (a).
(26)
DEK:
ask
ack
Given 25 and 26
we prove
Validating 18 For L such that of = 0, we have EMEK c( (9 (a) = mwin all t Jt.
Given
for
1 va
Σ
c((aaat (()))
(a) & Mmnin
E(()) (a).
1mmin
Va
aEk
aEk
aEk
(27)
Putting
23 and
together, we have
Va re(a)
19f (a)
&
Σ
(t(a))((t**())) vá. Σ re(aa)
(f()))(?(((a)) (a).
(28)
Inequality
and 28 gives
Ener Fr(a) (a) Loex
(: (4 (a)
Loex Pr(a)s (4 (a)
VVa
(29)
ava Lae Ce (a) (a) Leex 2a (a)) (a)
((())(())
Lee (c()) (4+)*
Recall from in Claim 3
for all t Ji we we have
Loek re (a)
(()
& a. LneK re(a) {())
(30)
Enex Ca (a)
(a)
Enex (a)at
(8) (a) Eaex c((a)
Putting
(27 and together, we establish (8
B.7 Bounding exploration rounds and failed exploitation rounds
To upper bound |T UU {1))), it suffices to upper bound [T (forthcoming Claim 4
and U M-2 (m)) (forthcoming Claim
Claim 4. For any 8 e ().1). 17 < TNYr Ny 37
/3 or log (2) with probability least 6.
Proof of Claim 4 Define the event ER [Conduct exploration in round L)
F.
F.R(1)
Fe
R(2)
where ER(1) (]a s.t. L = (a)) and ER(2) = {Ja K.s.t. E (;)()) We
define random variables Y. 1(EB), R(1) 1 R(1) and Y RR()) 1(ER(2)) Define
event F. (Conduct exploitation in round 8} F.! U E.(()) where F.(1)) {gr
0} and
E!! {e: 0}. We define random variables Y! 1(E)), y! (EE!)) and Y!(2)
(E
We further define random variables Zr, where Z, = Y,R()) Bern(7)) for all such that Y, (R()) 1 or y(! = 1 and Ze Bern(1)) otherwise. is evident that in each round t, Ze follows a Bernoulli distribution with mean 7t and Z, y,R(1) Therefore, the total rounds of forced exploration over the planning horizon can be upper bounded as
Σ YR
R(I) vR(()
N E R(1) N Σ 7--
Since Z, are independent and E
(=1 2,1 = ΣT itt & 2T we can apply the Chernoff bound
(which is subcase Lemma B.
on Zt.
2
Pr
2, > 2T +
6T log
<
<
8
Hence we have [T
YR
2T 2T
6T log(2/0) with probability at least 1-6. G
20

---

Claim 5. Fix any 8 (0, (7(m) < L|K] log(1 + 1)/rr with probability at most 1 1- L8.
Proof of Claim 5 If round is change point, i.e. (re, ct) * ( we define set ((tt) = K such that c((a)) * (r--((a), (--((a) for all a K(t). Notice that after change happens, some exploitation rounds could run with condition 6 violated, resulting in consuming resources from the wrong swwrd-consumpteee
interval Hence, [T]m)] can be upper bounded by the total number of exploitation rounds run before all arms are updated after each change point. After all arms updated after change point, (6) is satisfied again. In the following Claim 6 suppose round t a change point, and upper bound the number exploitation rounds run before all arms a E K((t) updated.
Claim 6. Suppose round f is a change point. With probability [ IRES- EEMS-CM run at most |K]] (og (1/6) (5) (log(
1)/rr exploitation rounds (Algorithm Lines 17 25 before updating the change in exploration rounds (Algorithm
Lines 13
Proof of Claim 6 For some set K'' K., let random variable Y(K)) denote the number of exploitation samples (i.e., line 6 of Algorithm
2 giving U(t) = 0) between two nearest exploration samples (i.e., line of Algorithm 2 giving (()) = 1) applied for arms E K'. We denote K(t) as the j-th arm explored from set ((t). After each exploitation sample, IRES-CM runs for each E (-M,..., - 1}. Therefore, the number of exploitation rounds run before all E K((t) are updated is 2M (Y((C())+ + DjEO ((K(O)) U K(()("))). For any subset K'' KC()), we further denote random variable Z(K') as Y(K') plus the number of times that exploration is triggered for any E KO,KC' between two nearest exploration rounds applied for arms a K'.
It is evident that Z(K') is a geometric random variable with time-varying probability p. = >//K'///K of success in each round. Therefore, we have Pr(Z(K') > n) -
p.). Since for
any x E [0, 1]. it holds that 1 - x & e by requiring e Prr & ō. we have I - pa) & 6. In this case,
(1 pr)" n-r
PT & ő es n PT & log(1/5) es n log(1/6)
K log(/(1)))
Pr
Therefore, we have
|C] log(((())) KK|
[C] log(0/0)))
Pr Y(K))
< Pr
Z(KC)
5.
YT K'|
which suggests that with probability at least 6, we run at most rounds before updating (Fe(a), (a)) for each arm KC.
|C] log log(1/0)(<xx/111) exploitation
Plugging (CONN (())) in K", with probability (AC())6
[K(O
U Tx(ejon h-1
KK |K] log(1/0)
y(C(t))
Σ Y(K())
vT j
[AC(1)
AC log( 1/8)
Σ
1
Yr
[C] log(1 (1/8) (log(((((1)))) + 1).
(31)
rr
Inequality (TD holds since
[C(e)]
(K(1)) 1 j=1
Σ 1-1
1
j < 1 log((((())) log((1).
(32)
j
Notice that there are at most change points over the entire planning horizon, contributing to (m))) for at most 2. L/K] log(1/))(log((K)) 1)/yr rounds, with probability at most 1 - L8.
21

---

Combining Claim and
with probability at least 2M LM,
T1
[1m)
<TTNN NV 6T YT log
55)
2
Logg
77
mm= M
E4TNNr+ 4M log( (1og ((og(((])) + 1)
YT
Recall that N 27 log log(2/0))((1 1/a)² 7min)) and Tt = M [ + 1)/v Nt. further have
M-1 Flm))
T
-) (33)
M
Note that if the DM knows L priori, then we can set = M L/ + N/t which results in 1T U(U {mm)) ÖLVDKKINT)
Nt.
C Proofs
C.1 Proof of Lemma 2.1
Let be a non-anticipatory feasible policy that achieves the expected optimum opt(DP) in DP, i.e. E EI E.ex Ra(a)x7(a)) [[[op[[DP)] where X the decision variable under algorithm m.
We let
(a)
1
E
Σ
4 Σx7(w)
1=
for each = 1,... L in FA. We claim that {an)f=1 is feasible to FA, with objective value equal to E 1- E Doek XT (a)] E[opt(DP)], which indicates that under |=> have opt(FA) > E Dp)) Thus, verifying the claims about the feasibility and the objective value proves the claim.
We first verify the feasibility to FA. Since the policy satisfies the resource constraints, the inequality
D EL Eoex Cx(a)XX(o) B holds. Taking expectation over (a) and Ca(a) for t 44-1 +
1....,t gives
T Σ
Σ
(a(a)x((a)
Σ
(o)E
aek
(-ttt aek
Σ (11 4-1) Σ (a)a((()) aek
1-1
<B.
Similarly, by taking expectation over each of the reward constraints, we have B Eeek X7) the claim about the objective value is shown, and the Lemma is proved.
Σn Σi, 4-1) Easx r(0) (a))((a) B(opt(DP)). Hence,
C.2 Proof of Claim 1
Recall that Algorithm I we try each q E 10. ., .M in a round-robin manner. Then we know that on each stationary piece I, for at least (f: - / rounds, we choose q = 9," and take
(o )m such that 7 and (8) hold. By Claim inequality (8 resources consumed
fractional decision x;
(9ft are assigned with resources reserved for intervals (max/m² L.M,, mf).
under decision x Therefore, for interval m where m = m,
Σ
1(g 9;))
f-11
(34)
M + 1
tEU Ni - -1-) (m) 11
22

---

Recall that if we choose the optimal decision z on stationary piece 1, B units of resources would be consumed, i.c. (tr 1(-1) L e0 (a)xf (a) Brr Hence by Claim 3 inequality we have
20 ( (a)) Σ (a)af(())
B
3
(35)
4-1
aEK'
aEK
Putting everything together, we have
Σ
En (()
rel - M (mm)
ni+e
1 1
Σ
Σ r((a)x((a)
[EU pm (m
T(n) (1.
aek
Σ
1( 9t) Σ
p0(0) (a)x)
10 (a)
Tel 1 -M 76o ((
aEk:
Eoek (a)x
(f 1+
Σ
1( = xt) Σ
10 (a)x)
(n (nf)
(a)
16 p - (m 1, Mn
700) (1t
aeK
EoEk cll)
(a)
B
Eeek (a)x
Σ
1(9 ạ
(36)
t t-1 Laex cll) (a)af()))
[3 (=U m, Too 1(..)t......
- 4-44-1
B
Enex 14 (a)x (a)
(37)
M+1
a(4 4-11
Eeek cl)) (a)=f(a)
B LacK p:0) (a)
(38)
2a(M+1
Leek (a))f(()
Inequality (36) holds by plugging in 335 and (). Inequality (37g holds by plugging in 34 Inequality
(38) stands since we can assume I - 4111 >
2 + 11 without loss of generality. Because otherwise
we can ignore the stationary pieces where 4 4--1 2(M + 1), causing a reward loss of at most
OMM. Following 38), we have
min mm +on++1MM-- 1,M 1-1 1}
Σ
Σ 1(m = w)
Σ
[r((a)a(aa)
w max 178 1, le
1=UM-1 M f(m) NM +1..... aEk
1(m m)
Σ (r(a))a(a)
lef
M M F(m) N+
aek
Enek rlll (a)) (a)
Σ
1(m = m)
B
20 [ 11
Lmex cll (a)=((())
lec
Therefore, for m E (-M,..., M - 1) such that 71) = Tn(") for n E (max(m - 1, 1,MM,,m, we have
T==mast (m-1-----1---) 11-1 2d3 Elec 1(m w) Ere M-1 7(m) 1+ EoEx (e(a)xx((a)
1
Liee 1 1(m² = m) Ei o! (a)a, (a)
r'D (a)
2a M + 1)
(39)
23

---

C.3 Proof of Claim 2
We let in = m {maxfm - -, 3,
m). 7(m) = =Ti"); Then we have
Emer ((()x((()
Σ -
Σ
Σ c(())a((a) ask
Loex 2 (t())xi(a)
te ((n) aeti
tetm)
=a m Σ
Σ a(())=((a)
(40)
(ET(A) aE
( B (B-1
(1-1-1)-
(41)
2M
Inequality (40) stands since in rounds E ((m), we have L Tr(a)xx(()// (ao(a)/Enex (((a)xr(a)
[erm, m+ Inequality 41) holds since Liep(an Enex (()))x((a) 2 (B T 7m (2M
(B - ()) - 1 by the definition of (m)) Then we have
min 1.M--1
Σ
Σ 1(m7 w)
Σ
Σ re(a)xr(a)
|max I.- lec
M-1 Tim) M(
.. DE
min 1,M-13
Σ
Im w)
Σ
Σ rr(a)x:(a)
M) LEC
(07 nit--1 I.....t:) aek
Σ Σ r((a)a((a)
(42)
(e)) asK
za m (B (B-1 -11
2M
Inequality 42 holds since m, { {(max(m; -1, MM,, m²) for all f [fi-1 + 1,..., t.). Therefore,
(
is possible consume resources reserved for interval m (max(m 1, -M,, m) under x only when
MM) Ul 1, 13} (max/m-1, -1--1,,,MM M), m, min / M 1}}.
We also have
Leer r
L B & an B.
Σ lec
(mm
m)
By
a+
Σ
(43)
Enex (a)af(a
lec
Putting together
42 and 43 we know that for m
M - 1) satisfying case (ii), we have
min +m 1,M
--=man max m 1, 1,-11. Mo Eier 1(m = w) 2i N(4 ++1,.... Emex re(a)xe(a)
Eiec 1(m = =m) Losr (ll)
Eocx (a)) (a) B*
a (BB 1)/(2M) -1
am+1B B
2M+1 B
2a M
1 - o(1)
(44)
M
Inequality
holds since we require B > 9(M) (see Theorem 3.1
Combining
39 and 44 we
show that
o(1)
14
(45)
6a 2

---

C.4 Proof of Theorem 4.2
Note that for reward-consuun consumption ratio intervals n E (-M.... .... M 1} where 7l (x),, not all requests assigned to these intervals are necessarily satisfied. This is because resources could run out due to exploration before Sue Ca(an) > (2M) 1, i.e. when
Fum) NiET: E.,a,, & B B-11 Flim) nT.
1
It can be seen that requests in rounds (U Flm) Nit E T E.= C.(as) & B -311 satisfied. Therefore, we decompose the ratio of the IRES- CM reward to opt(FA) as follows:
1} are
Fuw) BB Laex ( (a)
Ri(aa opt(FA)
Re(as)
opt(FA)
H(I)
EET Re(as)
E Fam) MitT C(a,) Eaex re(a)s (a)
H(2)
To establish Theorem 4.2 it suffices to show H(1)
(1 o(1) (opt(FA)
Ölv ([LIKTTT))/(00 M op((FA) (see the forthcoming Section C.4.1 and H(2) > o(1)
(see the forthcoming Section C.4.2).
C.4.1 Bounding H(1)
Recall that Σnex f((a)a(0 10)) (a)/ & ((()) ((a)) (a) e af
I.. We further define m (+*
such that EaEx Pe (a)
(9
(o(T)((()))) (a)/ EbEK a(a)) 19 ) (a) la
_
m0 +1J. Likewise, define cn* +1 We define
m, mi such that Exex r(
(9t) (a)/ Ever (
)+ (a) Ta)
am
-- x .ITT Σ C.(a,) & B B-1 1
Then H(1) can be further decomposed as:
H(1) = ELE(UM- F(0))
) C= Eaek re re(u)a(a)e (a)
opt(FA)
Elec Ene Bie(UNN- M Fum)) n EmEr (((a))(())(())
ElEc Eierh Eosk r00) (a)x
2m=-M M Eiec EIE(UM n 1(m!") (1) m) Enex ((())((a)))
M-
(46)
MM-1 Eiec Eier, 1mm (m)
(1) m)) Eoex r(0) (a)x
M- mm Elec LieeUN M- Fum) N -w=max(m-- -u-max(m-22--1) 22- 1 1(m (1) w) Exex (e(a)s
Imin(m-2, M-M1
5
-M-1 M Evec Eier 1(m (1i = =m). Exek (())
(47)
Inequality 47 holds since by summing over (max/m 2, - -M...., min(m m + 2, M -1}}, we repeat the numerator of (46) for at most times.
We partition set (-M,..,, M 1} into two disjoint sets MI, M2. An interval E M1 if for all E {max(m 1,-M) J. m, min(m + 1, M -}}} have 7l(m) = _1mm), i.e. E. C. Ca,) < (2MM - 1. An interval m e M2 if for some n E {max/mm - 1, -M), m, min m + 1, M 13). have [()) ç: 7(1).
25

---

Regarding m E .M1. In the following analysis, we focus on the good event that (6 17 (8
in Lemma B.3 hold for all E T. We know that with probability at least 1 7 the good
event holds. On each stationary piece E L and all t E Jr, for all rounds t E (U M (()) N
such that my
(+)*
m, we know that mi (1) e {max/m - 1, - -M m. min + 1, M - 1 (see
(16) in Lemma B.3 Due the round-robin technique, at least 1/(M 1) fraction of all rounds
t e (Um-nr M T(n))
(0)+ m are allocated by resources reserved for N nh,le L such that m
intervals n E {maxfm m 1, - ), m. min(m + 1, 13}. Therefore, we have
Σ
Σ
1(m (+ = m) 1(: qtt) >
Σ
Σ
1m [1) = m) 1( qi
JEC te N
gminim L,A 11 lEC re (U
maxmax -1, 1r Fum)) Fwn))n n
ceec (u (eme(mmmmmmm M-11
mommatt 20 Fimm))
1mm (1) m)
M+1
(48)
We ignore the stationary pieces / where [J]] & 2M, since this cause a loss of at most O(M).
For m Mr. although we have Un M} 7()) Un-max(m-11-MM 71(n) (i.e..
Uminfn+t.M-
Exetion (a,) & B/(2M) - 1 for all n [max(m - 1, MM, m. min (m + 1, - 13)),
is not necessary that all requests assigned to intervals {max(m - 1, - M), m, min
-1
are satisfied. The resource units reserved for these intervals can run out due to exploration, i.e., when
min(m++ 11.
U
710) NIEE
T: C.(,))
< B BB-]
min(m+1.M-1)
U
71() nT.
1.n--1-MM)
m-max(m-1,--))
We define
(t)(m) = Σ
Σ
1(m (1) = m)) Σ
(r(a)s(aa*()) (a).
LEL te Flw NJAh
ask
Then we have
min(m+22 +2,
Σ
Σ
Σ
1(m (1+ = =w)- Σ
re(aa)(aae (a)
IEC IE LM Tw))
n w mm 2.-MM
aet
> Σ
Σ
1(m () = =m) Σ
re(a)ala)) (a)
lEC IEC N.
aek
Σ
Σ
1(m ()) m)) Σ
rr(a)alal 1 (a) (m)
IeC LECCE(UMMM Tw N.
aek
Σ
Σ
1(m (t)* m) Σ
re(a)a(m))) (1))) (a) (+)
lEC (E(UUM- Tun)
aek
Σ
Σ
1(m (0) = m) 1(g: = -q¹) In((a)af 10 (*)())((()))))))))()))))))))(( (m)
pinff++
fum) N.
ae
1
Σ
1 1(m ()) = m) 1(9- = g²)) Σ
t0 (a)x - (f) (m)
lEC,
mina LMM te
ask
mm-
(49)
Σ
1(m mm). Σ (a)) (50)
a(M + 1)
leL
U (mn (mn 1,- M1
Fkm)) F
26

---

Inequality 49 follows from 17 in Lemma B.3 and inequality (50) follows from inequality 48
Hence, we have
EmEm, Elec Lie(UN- F(mm)) n 1(m ()) m) Exex ( (a)
EmEM, Elec ElEr. (m, (m = m) ExEK (a)(())((()
a(M+1) Emems L E unneuums Tum) n 1(m (1) = m) Mnex (a) - Emmm (t)
2 max
EmEMI EVEc EnE 1(m (0) = m)) EOEK (a)af (a)
M(M+I) EmeM, Σt Eie( un-max(mm ( 1(mg (1) -m) LucK r (a)xf())) - 177
> max
EmEM, Elec ElEg. 1(m, (( = m) - (a)=2(())))
(51)
a(M+l) EmeM, Eiec EiEg, 1(m (1 m)
( T U (UM-- Fl(m)
> max
LmmeM Liee Zie 1(m, ()) m) Mnex (1l)(a) (a)
(52)
L(KITT)
2 max a(M+ EmEMi Eiec Eier. 1 (m, (mm (1) m) EaEx r(00 (10)())))())
w.p. 2M K.
(53)
Inequality (1) holds since N-M-1 _m--)((t(mm)
& |T Inequality 52 is valid since
min(m L,,M-
minfm +1,M-
min min 1.
U
7(())
N
U
F((n)
N T = J.
U n1 max (m 1,,-1111
7((m)
F1 - max (m 1.-
n- (m (,-1,-M)
Regarding m E M2. Suppose in some interval ñ E (max(m - -M min(m + 1, M 1)}. have Lie (a,a,) > B/(2M)- 1. We aim validate the following two inequalities respectively:
min 22 11
Σ TeL eE(U 'n 7 no m
Σ
Σ
1(m ()) w) Σ re(a))(1)* (a)
ask
1-122
log(1/0) 1og((100)
(54)
2M
M
ΣΣ
1 1mm
(0) m))
Σ (0) & m45/2 B,
(55)
LEC te
aek
Since given (54) and ffr for any interval m E M2,
EmeM, ElEc ELE (UM )KO) NJt Σ miin(m+ 2, 2-
m mm-max (m 2, M, 1(mg (1) w) EVEX (( (a)
Lme Liec Lno, 1(m 10 = m) Lnex r!1) (a)
a 1/2
1
4log(1/6) + 1
BM log(1/5)
V
+5/22
2M
B
3/2
1
4 (1)( +
log(1/8)
m55/2
2M
BM
B
1- -(1
(56)
2M
27

---

In algorithm. for any E Um--N Flmm) we have ar =((+) and hence,
Validating 54
([R((a)))
(o)" Fit1 _ae ( (a). (a). Therefore, by Lemma B.2 for any 8 (0, 1), with
probability least 36, we have
Σ Σ
Σ Ce(ar) 2 Σ Ci(ai) log(1/0) log(1/6)
7 ae
LET
(ETUm)
B
B
log (1/) Alog(1/8) 1.
(57)
2M
M
Inequality (57) holds since (/(2M) L Fun Ca(as) & (2M2)). Then we have
Enex (aa)a
Σ Σ (r(a)saa) (a)
Σ
Σ
ca(a)afau
Euex C4 ())+)))
(1))a)) (0)
1E aek
aEK
> 8-1/2,
Σ Σ
Ea(a)a (a)
(58)
(ETR(A) aEK
B
B log(1/8) 1log(1/8)-1) -1)
2a 8-12
(59)
2M
Inequality (58) holds since for all t E T((A) have LEEK (()))(()) (a)/ Emex ((())
a.. Then by inequality (16) in Lemma B.3 we have Liex Tz (a) (a)/ (a) c)(a) (a)
a-1 Inequality (59) follows from inequality 57p.
We further have
minfm -11
Σ
Σ
Σ
1(m,
(1) = w) Σ
rr(a)a (((a))(a)* (a)
lef t=(1 t=(UU= Flm) N (m
aek
min min(m m 2.M-1)
Σ
1(m, (0) = w) Σ
re(a)s(a)+
LEC (2))()) N w max (m 2,
acK
min(m+2.M -2,
Σ
1(m (0) =w)
w) Σ
(r(a))((1)0))
(60)
lec tef 100) NJ wm 2
ack
Σ
Σ
r((a)= (a)
(61)
LEC (4) NJ, ask
= Σ
Σ
rr(a)ala)=(() (a)
(IA) ack:
20 20
1/2 1-122
B
B M
log(1/0) 1log(1/0)-1 -1)
2M
Inequality (60 holds since the total B resource units have not out before the reserved B/(2M) resource units for interval î run out, i.e.,
Fu() n NIEET
tET T: C. < B <B-1 (((R) nT.
Inequality 61) valid since for t T((a), we have mi (1) n. Hence, we have
m (maxx(n-1) -M). min + 1,, M 1}} {max/m- m- 2, - ... -M).... +2, -M1]).
(
28

---

Validating 55
For E L such that q²¹ = 0. by (18 in Lemma B.3 we have
Σ te
1(m
m) Σ (a)=f(a)
aEA
Σ
Eaex (((a)at) (a)
(())
e la" , cmmttty)
Σ
rl0
(a)
mex (())s (a)
(())
ack
E EmEk (a)
[a m- m
(a)=f(a)
EOsic (a)2((a)
tE
aek
(a))
Eeek 7 (a)x)(a)
Σ1
{[a m-3/2 amttti) m (a)=f(a)
Σ (a)t((()))
Easrc (a)
Loek (a)
50 +5/2
(62)
TEJi aek
For / E such that at > 0, by 15 have
Σ
c (a) & Mmin
a < Σ (a)at(a).
ac
ack
In this case,
Σ 1 1(m
(1) =m). Σ (a)=f(a)
NETI
aE
<
> 1(m,
(1)* -m)- Σ
A((a)s (
(63)
[EJi
ask
=0 - 1(m m) A(lo)
Σ (a(a)s(o
E GaE) (a)
ask
m Σ Σ a(())a) (()))
(a)
AEJi ask
ta Σ Σ
(o)x
(64)
LEJ ask
Putting together 62 and
64
we have
Σ Σ 1(ml
(m))) m) Σ as/C
1 (a)=f() & a m+5/2
ΣΣ Σ
e (a)x & m55/2
TeC
lec JE ask
Finally,
let us combine the two cases where m
Mi and m
M2 If
53 = 0 and (1) = m) Eock ( & Ö(VLKK]NT) then EMEM, Elec Ener, 1(m
we have
EmeM, Eiec EntEUUML, Flw) NJt 1(m) m) ((()) (())
H(1
> 5
EM-IM M Elec ErEo 1 1(mg (1) (1) = =)) EaEk (a)a
>mm Ma Lieo ZiE(UH Nm 1(m (1) = =)) Teex)((()a)) (40) (a) opt(FA) LIK(NT
1
5
Emem, Eiec Ener, 1(m (+) m) EoEk (a))x)))))
opt(FA)
1 1- 1-0(1) opi(FA) - -OAA))-O((LL LIKINT
(65)
10
opt(FA)
If EIEE, ΣIEc Enen, 1(m ()) = -))
EoEK (e0c((((()))) > ((VLIKITT then 53 = (1 -
o(1))/(((M + 1)). Then
o-)(1) 1- o(1)
1- 1- o1)
H(I) 3 min
(66)
3a(M + +1) 10a M
10a M
29

---

Therefore, we conclude that
1- o(1) opt(FA) -((LKI
H() 10
opt(FA)
with probability at least - (
C.4.2 Bounding H(2)
H(2) is to bound the stochastic reward achieved by randomized decision and the expected re- ward. In IRES-CM, for L E Um--M 71mm), we have a/0))* and hence F:
DBEK Ta aa) have
(a). Then by Lemma B.1 for any 8 E (0, 1), with probability at least - 6, we
Σ
R E
rel UM- M F((m)
2
log 5
2
Σ
Σ
Σ
{rala)afu0((0 (a),
Elec Ene(UM= na Loek (((
LEC te te( Fum)) n aek
14
3
log (3)
2
Σ
Σ
Σ
re(a) ( (a)
Elec EIE(UN- prl)) n Lock (a)) (a)
IEC De ve(tUtt -M T(m) n aeA
2 H(1) opt(FA)
2 8
3
(
log
H(1) opt(FA), 1
log H(I) oPI(FA)
H(I) OpI(FA)
8
Since H(1) opt(FA) > (1 (1)) (opt(FA) D(VEKIIT))((100" > {((opt(AA)) >
② (T)))K] Then is evident that H(2) 3 1 -(1) with probability at least - 6.
C.5 Proof of Lemma
C.5.1 Proof of part (a)
The horizon T is partitioned into L T/B pieces with equal length B. We consider L instances with two arms = {1} and amoll, and instance n happen with probability Pn. All instances have deterministic outcomes, and they share the same consumption model Ct(1) for all i e T. Their reward functions are:
Instance 1: (1)
a a-L,...,a-t
,...,a a ....,
a b+1
L+1
Piece
Instance (1(2)(1)=
a T p..., T+1
T+1
Piece
2
Piece
Instance L: (L(
a ,..,,..,c0 a O,....0.
Denote FA (m) as the FA for instance n E (I...., I.). It is clear that opt(FA (*))
Ba-" Recall
X.(1) 1(Pull in round t). By the Yao's principle Yao 1977. the competitive ratio of any online algorithm is at most
B
T R(()) (1)x
Pn
OFA(FA (x))
(67)
30

---

for any Ps: 2 O with Σm= Pn. = 1. The expectation E(") is over the randomness in X2 in instance The instances are crafted such that during piece j {l..... L}. impossible to distinguish among
instances L. meaning that the quantity _ = E 1E Xx(1)] for n {j..... L} all identical, and equal common value By. Thus, for instance E {l...., L} we have E > (1)) & Σj_n B,a=) Consequently,
Pn Σ By.
1
(69
Pn
a n-
a.an
B
j=1
n=1
By defining P1 L11-1/a)+1/a
(1 - 1 a
Pn. for n = 2,..., L, we have for every j = -,....
Pn a nーj
L(1 1/0) + 1/a
leading to
Σ
B
a n-j
B
Pn
L(1 - 1/a) + 1/ex
1-1
n=1
by the inventory constraint Σ loga (fmax/ //mnx///min), Imin), we have shown that the CR can be significantly larger than log (fmmxx/ /miin) when Vmnin 0.
Bj
x B on instance 1. Since can generally be larger than
C.5.2 Proof of part (b)
While is possible to derive a worse bound without 7max by setting it to its upper bound of 1, knowing the lower bound essential for algorithm's functionality. To show that it is necessary know Mminn we suppose the DM be provided with looser lower range parameter Mhiin < Mmmnn & re(a), ca(() Va, f, and show that leads to sub-optimal CR.
general case construction. We firstly construct a case with N instances when 7mmn = 3 3-N for some absolute constant > 1. We consider N + 1 instances with arms K. (1} and Gnill+ and instance n happen with probability Pn- All instances have deterministic outcomes, and they share the same reward model R₂(1) = 1 for all t. Their consumption functions are:
Instance O: (²() (1)
Piece O: B rounds
Instance 1: (1)
1......]
1/B, 1/B
Piece B rounds
B.8 rounds
Instance 2: (12)
b....,
1/8,... 1/3 1/32,... 1/32
Piece O: B rounds Piece B.8 rounds Piece 2: B-B2 rounds
Instance N: (I)
1......
1/8
1/ 3
Piece B rounds Piece 1: B- rounds
Piece N: B.BN rounds
Denote FA (n) as the FA for instance [O....,N] It is clear that opt(FA (*) = B3" Recall X,(1) (Pull in round t). By the Yao's principle Yao 1977). the competitive ratio of an online
algorithm is at most
N
T R (1)x,(1)
Pn
(68)
OFt(FA(())
n=0
31

---

for any Ps 2 O with = Pn = 1. The expectation E(n) is over the randomness in X, in instance The instances are crafted such that during piece j E (0.....N;, it is impossible to distinguish among instances J....,N, .N, meaning that the quantity B)n) = ((n) Exppiece Ct (()) x1)) for E .. are all identical, and equal to common value Bj. Thus, for instance ,0,...,.N) . we have E E 1- (1) & Σソー B,B Consequently,
Dj-n Bg B .B
B
(68)
Pn
Pn
B
==0
1=0
R=0
By defining Po
(1-1/3) Pn for
N, we have for every j
2(N -04+)0011/0+-1/
O O,...,N.
Σ 11-0
B-at
Pn
(N+ + 1)(1 1/3)+1// 1/B
leading to
N Bj Σ J-0
1 (N + 1)(1 - 1/3) 1/3
Pn g-n+
by the inventory constraint -110 Bj & B on instance N. Therefore, when the DM is provided with information 7mnn B B-N for any N N, CR= O(N) lower bound derived based on N + 1
instances constructed above.
Not knowing Mmmin 3- but knowing 7min B-*xA, We suppose the real underlying JJmin B-A for some constant A, V/nax = 1, but the DM only has weaker prior information that 7/min 8- (N can be arbitrarily large) and Mmax 1. The pattern of Re: Ct) follows the above case, and therefore, different Main leads to different number of instances N. The DM only knows the number of instances no larger than k A. Then from the DM's point of view, the optimal CR she/he could derive is CR= (( A); while from the perspective of a clairvoyant who knows the real Tmin = A-A, the optimal CR should be ((A).
We first show that given Amin = = 3-xxA, the DM will not benefit from tightening the value ranges by blindly guessing a value of Mwin- We suppose the DM blindly tightens the value range to (3-(xeA-d) 1] for some d ? 1, without knowing the real Mmin- Then he/she derives a CR lower bound with N + 1 = K A - d + instances based on the above construction. Then the DM can expect to achieve total reward of
T TIGHT (1)
N.N = Pn- OPI(FA TIGITT(")
K (B:
B (B.3
Σ
Rx(1)x
θ
(N + - 1/33) + 1/3
d
However, since the DM does not know the real Mhiin it is possible that in fact Mhuin B-m-A, If this is indeed the case, the optimal reward can be as large as
Pn opt(FA (")) = [(B -
n- 0
based on the above constructed N achieve a sub-optimal CR of
k. A instances. Hence, from the DM's perspective, she/he could
ΣN Pn opI(FA (n)) Σ (1)XXTTTHHT
8 K.A 52 B gmn,
B B.
52(gd (k A d)),
she/he blindly assume 7mmn = 3 Ax-A-d), This is significantly worse than the optimal CR= (x-A) (if in fact Mmmn 3-=-A), Thus, the DM has no motivation to assume lower bound larger than the provided 7min.
Therefore, the DM must derive a CR on the full range [3 11, which involves + k- A instances as constructed above. Therefore the DM expects a reward of O(B gx /(- A)). However, since in fact there are only A + instances, the DM wastes all her/his resources reserved for instance + and she/he can only achieve a reward of O(B /A/(x A)). Compared with the actual optimal reward Q(B (4) with A + instances, the DM achieves sub-optimal CR of Q(K - A). Since x can be arbitrarily large, the CR derived without correct knowledge of Tmnn is significantly worse than the optimal CR= O(A).
A + 2,..., K
32

---

C.6 Proof of Theorem 4.5
We prove Theorem 4.5 by considering 2v + instances, which share the same K. {1}, B E Z and T = (2 1) (All instances have the null arm, as stipulated by our model definition). All instances have deterministic outcomes, and they share the same consumption model C₁(1) 1 for all / E T. By contrast, they differ in the reward model. The horizon ' is partitioned into 2v + pieces with equal length B. Their reward functions are:
Instance -v: (1)=
20+1
20+1
Piece
Instance 1: 1 ((-
a 2v
20+1
20+1
Piece -v
Piece -++1
Piece
Instance V (1)
a -
a
2v E.....,
E....,e
Piece
Piece -1+1
Piece
where a- 3v Denote FA (*) as the FA for instance E {-M,.... v). It clear that opt(FA(
Ba- Recall Xx(1) = 1(Pull in round t). By the Yao's principle Yao 1977). the competitive
ratio of an online algorithm is at most
E
R Re (1)x((I
Σ
Pa
(69)
(F)
22 V
for any Pa. with Σk_-e Pn The expectation E(x) over the randomness in X, in instance n. The instances are crafted such that during piece j {-v...., vV, impossible to distinguish among instances _...., -j. meaning that the quantity Bf")) EE()) D [Erepiece Xx(1) for E {-v,...,- -j} are all identical, and equal to common value Bj. Thus, for instance n E (-v,..., //} we have E R Σ B Consequently,
(1))((1)) & Be + Ex B & B B.o-3 -3v +
669
Σ Pn B.a-vnn
B a 3v By. a
1
+ Σ 1--v
B Σ
Pn tn
a" a".(1 1/a)
By defining p-v M1-1/0)+1/
(1- 2 Pr for + I,...,,, we have for every
j V,...,,,
Σ Pn tn
2v(1 - 1/a) 1/a
n--v
leading to
Σ
B B カーーツ
Σ
Pn
tn
2v 1/a) 1/a²
(70)
1=ール
by the inventory constraint Σ" Σy_ B₁ B. Since v loga (aitmax//mmi/)/ 3/3, the Theorem proved.
33

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: We have clearly stated the contributions made in the paper and important assumptions and limitations in our abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We have discussed the important assumption and limitation of our work, which is Mmin 0, in Section 2.2] AAssuptioon, limitation and discussion". When we establish theorems regarding performance guarantees of our algorithms, we also state clearly the preliminary requirements for them hold. We promise that we honest on the limitations of our algorithm.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
34

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We promise that our paper provides the full set of assumptions and complete (and correct) proof. Due to the page limit, our proofs are mostly appendix. In the main paper, we provide high-level ideas and sketch proofs of our claims, while pointing to the locations of formal proofs the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We firstly make it clear that paper is thcoretical paper. We only run simple experiments for sanity check and drawing insights. We are affirmative that our paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
35

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
Our data are numerically generated and codes can be provided.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https //nips.ccpput wwtpcccccppccccceee coroolicggiieeee www.deeeeeeeebemeeeeeeee
ssionollccy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: Our experiment does not involve training data, but we have specified the test details and settings.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Though the experiment is not as important as theory in our paper, we run the experiment repeatedly and plot variations of all tests.
Guidelines:
36

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Our experiment is very simple and can be run within a few minutes on any laptop.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: Our research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
37

---

Justification:
This is theoretical paper. There is no societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negatíve societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
The paper does not existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
38

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the palasets.papersstt paperssi thcode. com con/dataset package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does no involve human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
39

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
40


Reviews:
[{"review_id": "8lVL3p5m9S", "reviewer": "Reviewer_ifdP", "summary": "The paper studies Bandits with Knapsacks in a piecewise-stationary environment, where the underlying reward can change over time. \nThe authors provide provably near-optimal competitive ratio for this setting, which achieves a dynamic benchmark and obtains stronger results compared to existing adversarial Bwk works. Specifically, the algorithm proposed in the paper does not rely on the prior information of the number of stationary pieces and the time indexes when changes happen.", "questions": "For the non-stationary bandit research I known before, algorithms typically need to detect whether the reward has changed every round. When a change is detected, the algorithm usually employs a restart mechanism to forget the past information. However, in Algorithm 2 of this paper, there is no such detection-restart mechanism. In this regard, I am curious about how the non-stationary rewards impact the algorithm in this paper.", "limitations": "No limitations.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The contribution of this work is solid. Compared to previous works that use the global variation glo to quantify performance, the algorithm in this paper uses the number of reward changes as a measure. This is a better choice in non-stationary bandits in general.\n2. The paper is well written and provides adequate details to understand the flow of the material.", "weaknesses": "As I understand, the main idea of this paper is to categorize the rewards into $M$ levels based on the maximum per unit reward (Ratio*). Each level's maximum per unit reward is a multiple of the previous one, allowing to focus solely on the highest level's maximum per unit reward. In this setting, the algorithm allocates $\\frac{B}{2M}$ resources to each level. In this regard, the algorithm's reward is at least the maximum per unit reward multiplied by $ \\frac{B}{2M} $, while the optimal algorithm's profit is at most the maximum unit profit multiplied by $ B $. This leads to a competitive ratio $O(M) = O(\\log(\\eta_{max}/\\eta_{min} ))$. \nIn this regard, such a design seems somewhat trivial. I can understand that for this problem, perhaps this method is optimal. However, given such an algorithm, I am not sure if the problem itself is sufficiently meaningful.\n\n\nTypos: \n1. Line 160: The DM does not L...", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for the reviewer's time and effort in evaluating our manuscript. We highly value your feedback and would like to address your concerns and questions in what follows.\n\nRegarding \"Weaknesses\": \n\n1.\tClarification on Algorithm Details (Full-Feedback Deterministic Outcome Setting): We would like to point out some missing situations and details in the reviewer's summary, which could potentially resolve some possible misunderstanding. The reviewer’s summary, \"the algorithm's reward is at least the maximum per unit reward multiplied by $𝐵/2𝑀$, while the optimal algorithm's profit is at most the maximum unit profit multiplied by $𝐵$,\" captures only the special case when our reserved $𝐵/2𝑀$ units of inventory for each reward-consumption ratio interval are depleted before the end of the planning horizon. The more general and complex scenario arises when our reserved $𝐵/2𝑀$ units are fully consumed for some ratio intervals $m \\in \\mathcal{M}_2$ (see Claim 2, Section 3.3, on page 6) and not fully consumed for some ratio intervals $m \\in \\mathcal{M}_1$ (see Claim 1, Section 3.3, on page 6). In the latter case, our algorithm ensures that on each stationary piece $l$ with the optimal ratio $\\text{Ratio}^{(l)\\star}$ falling in intervals $m \\in \\mathcal{M}_1$, at least $B^*_l/M$ units are consumed at the optimal ratio. However, it does not provide any direct guarantee that $1/O(M)$ fraction of the optimal algorithm's profit is obtained for intervals $m \\in \\mathcal{M}_1$. Establishing our competitive ratio requires judicious analysis to bridge between the piece-wise and interval-wise results, which is not trivial (see Appendices B.4, C.2, C.3). \n\n2.\tClarification on Algorithm Details (Bandit-Feedback Stochastic Outcome Setting): Our primary focus is on the bandit-feedback stochastic outcome setting, where existing algorithms for non-stationary unconstrained multi-armed bandits (e.g., sliding window) cannot be naïvely generalized. Our novel design allows for monitoring underlying changes in parameters through sampling rounds rather than change point detection algorithms, which further simplifies the problem. More details, please refer to the next bubble where we address your questions.\n\n3.\tComparison with Prior Work: Previous works on online non-stationary optimization/bandits with knapsacks focus on either adversarial settings (Immorlica et al., 2019; Kesselheim and Singla, 2020) or a global variation budget (Jiang et al., 2020; Balseiro et al., 2022; Liu et al., 2022). We believe our piecewise-stationary setting is meaningful both theoretically and practically:\n\n  $\\bullet$\t Theoretically, Immorlica et al. (2019), Kesselheim and Singla (2020) consider a more general non-stationary setting than ours, but compare their performance with a stationary benchmark where a fixed optimal arm (or a fixed optimal distribution over arms) is applied in all $T$ rounds. Jiang et al. (2020), Balseiro et al. (2022), Liu et al. (2022) require the total non-stationarity to be bounded within a global variation budget (see Remark 4.2), which is a very strong assumption. Our setting does not require bounded global variation and our performance guarantee is compared with a dynamic benchmark, which we find to be an interesting and meaningful result. \n\n  $\\bullet$\tPractically, the adversarial setting may be too conservative, and the global variation budget setting can apply to very limited data structures. Our piecewise assumption on non-stationarity is reasonable and observable in many real-life scenarios, such as sales patterns that remain stationary for certain periods before changing during hot seasons/promotions/new trends. \n\n  We further argue that piecewise-stationary bandits without constraints has drawn significant research attention. We list some of the relevant papers in the following: \n\n  [1] Auer, P., Gajane, P., & Ortner, R. (2019, June). Adaptively tracking the best bandit arm with an unknown number of distribution changes. In Conference on Learning Theory (pp. 138-158). PMLR.\n\n  [2] Cao, Y., Wen, Z., Kveton, B., & Xie, Y. (2019, April). Nearly optimal adaptive procedure with change detection for piecewise-stationary bandit. In The 22nd International Conference on Artificial Intelligence and Statistics (pp. 418-427). PMLR.\n\n  [3] Besson, L., Kaufmann, E., Maillard, O. A., & Seznec, J. (2022). Efficient change-point detection for tackling piecewise-stationary bandits. Journal of Machine Learning Research, 23(77), 1-40.\n\n  [4] Bhatt, S., Fang, G., & Li, P. (2023, April). Piecewise stationary bandits under risk criteria. In International Conference on Artificial Intelligence and Statistics (pp. 4313-4335). PMLR.\n\n  Our work is the first to study piecewise-stationary bandits with knapsacks, which is a new and interesting setting that requires extra care in maintaining the order optimal competitive ratio in Section 4.\n\n4.\tSimplicity and Contribution: While our algorithm is not complex, its simplicity and intuitiveness enhance our contribution. We offer a novel perspective on non-stationary BwK, distinct from traditional gradient descent-based algorithms. Our approach simplifies the problem by focusing on two elements: guessing the reward-consumption ratio interval and reserving adequate inventory for each interval. Although the process of deciding ratio intervals via LPs in a round-robin manner may seem primitive, it leaves room for further refinement of our competitive ratio's coefficients (we already achieve the optimal competitive ratio’s order w.r.t. $\\eta_{\\max}/\\eta_{\\min}$). Nevertheless, given that our paper introduces this novel perspective, we believe our contribution is solid.", "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": "HaLCpfyvgC", "reviewer": "Reviewer_BBCY", "summary": "This paper addresses the challenge of piecewise non-stationary stochastic bandits with knapsacks. In bandit with knapsacks, at each round a learner is asked to choose an action and receives both a reward and a budget cost. The goal of the learner is to maximize its cumulative reward while satisfying some cumulative budget constraints. The authors prove a competitive ratio with respect to a non-stationary oracle with $L$ changes of order $O(1/\\log(\\eta_{\\max}/\\eta_{\\min}))$ under the assumption that budget costs smaller than $\\eta_\\max$ and rewards larger than $\\eta_\\min$ and if L is sufficiently small. Earlier results on non-stationary bandit with knapsacks are recent and depend on a global variation measure (glo) that is hardly satisfied in practice.", "questions": "- I suggest the authors to address my limitations.\n- The paper only considers piecewise stationarity, would it be possible to generalize it to smooth variations of losses and budget costs?\n\nTypos: \n- p3, l117: $B^2/T$\n- p5, l160: \"The DM does not *know*\"", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The considered setting is relevant and of interest for practical applications. \n- The authors design an algorithm that achieves an optimal competitive ratio with a matching lower bound. \n- The non-stationary assumption is much more realistic than previous work. \n- Experiments included in the appendix demonstrate that the performance improvements with respect to the only existing baseline. The latter is however designed for the adversarial setting and is thus too conservative in their setting.", "weaknesses": "- The main part of the paper is too technical with many different notations, inline mathematical formulas, and not easy too follow. \n- The algorithm needs to know the loss and budget bounds in advances.\n- The dependence of the regret in $L$ seems suboptimal since the results only hold for $L \\leq o(\\sqrt{T\\eta_{\\min}})$ while we expect $L$ to be possibly as large as $o(T)$. \n- I am not convinced by the lower bound of Lemma 2.3 which uses $L = T/B$ and is thus in a setting where the upper-bound does not hold. The result would be stronger for a fixed value of $L$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your time and effort in reviewing our paper. We address your concerns and questions one by one below:\n\n\n1. “The main part of the paper is too technical with many different notations, inline mathematical formulas, and not easy to follow.”\n\nResponse: We apologize for the dense notation in our paper. Given the highly technical and unconventional nature of our work, detailed notation is necessary to convey our ideas accurately. To help readers, we have included a high-level overview and intuition in Section 2.3 (pages 3-4). We hope this section clarifies the technical discussions and makes our novel contributions more accessible.\n\n\n2. “The algorithm needs to know the loss and budget bounds in advances.”\n\nResponse: We believe there may be a misunderstanding. Our algorithm requires knowing the range where the reward and resource consumption fall in, but it does **not** require prior knowledge of budget bounds. In the full-feedback deterministic outcome setting in Section 3, not only our algorithm, but also our performance guarantee does not rely on the budget $L$ (see Theorem 3.2 on page 6). In the bandit-feedback stochastic outcome setting in Section 4, while our performance guarantee (see Theorem 4.2 on page 8) depends on $L$, the algorithm itself does not need to know $L$. That being said, we do provide an improved performance guarantee when $L$ is known (see Remark 4.3 on pages 8-9).\n\n\n3. “The dependence of the regret in $L$ seems suboptimal since the results only hold for $L = o(\\sqrt{T \\eta_{\\min}})$ while we expect $L$ to be possibly as large as $o(T)$.”\n\nResponse: We acknowledge that this is indeed a limitation of our piecewise-stationary setting, as discussed in Section 2.2. In the bandit-feedback stochastic outcome setting, without prior knowledge of $L$, our result is meaningful only when $L = o(\\sqrt{T \\cdot \\eta_{\\min}})$.  With prior information of $L$, our result is meaningful when $L=o(T \\cdot \\eta_{\\min})$. In the full-feedback deterministic outcome setting, our result is meaningful even when $L=T$.\n\nThis limitation arises from our exploration process (line 9-13, Algorithm 2 on page 8) in the bandit-feedback setting. There could potentially be other change point monitoring algorithms where this restriction can be lifted. Nevertheless, our main contribution lies in our novel design of breaking the problem down into guessing the reward-consumption ratio interval and reserving adequate inventory for each interval. This design allows us to achieve a near-optimal competitive ratio without knowing the exact change points, making our contribution meaningful despite this limitation. \n\n\n4. \"I am not convinced by the lower bound of Lemma 2.3 which uses $L=T/B$ and is thus in a setting where the upper-bound does not hold. The result would be stronger for a fixed value of $L$.\"\n\nResponse: We appreciate the reviewer’s careful inspection and insightful concern. The competitive ratio (CR) lower bound in Lemma 2.3 is derived for a full-feedback deterministic outcome setting, where our algorithm has no restriction on $L$. Our deterministic performance guarantee (for $\\eta_{\\min}>0$) in Theorem 3.2 holds even when $L=T$.  Therefore, $L=T/B$ is in a setting where the upper-bound holds, in a full-feedback deterministic setting. \n\nWe do agree with the reviewer that in the bandit-feedback stochastic setting, we require $L = o(\\sqrt{T \\cdot \\eta_{\\min}})$ (or $L=o(T \\cdot \\eta_{\\min})$ with prior knowledge of $L$), which indeed contradict Lemma 2.3 where we set $L=T/B$, when $B$ is small. The rationale behind Lemma 2.3 is that we want to provide a bound that surpasses Immorlica et al. (2019), where the CR depends on $T$. \n\nIn fact, our Theorem 4.5 on page 9 already provides a valid CR lower bound, where we set $L$ to be a fixed value $2 \\log(\\eta_{\\max}/\\eta_{\\min})$. The lower bound also show that $\\eta_{\\min}>0$ is a necessary condition for obtaining a non-trivial CR. \n\n\n5. “The paper only considers piecewise stationarity, would it be possible to generalize it to smooth variations of losses and budget costs?”\n\nResponse: We think it could be possible to generalize our approach to smooth variations, since Algorithm 1 (full-feedback deterministic outcome setting) applies to any non-stationarity (see Theorem 3.2 on page 6). The performance dependence on $L$ in the bandit-feedback stochastic setting arises from our exploration process in Algorithm 2. There could potentially be more refined change point monitoring algorithms that adapt to other types of non-stationarity. \n\nOur key contribution is the new perspective of decomposing the reward into the reward-consumption ratio and the amount of resources assigned for each stationary piece $l$ (see equation (3) on page 4). Then by reserving a fixed amount of inventory for each ratio interval, our task simplifies to guessing the optimal reward-consumption ratio interval in each round. Since our paper is the first to propose this design, we believe a simpler non-stationarity helps us better illustrate our main contribution and make the paper easier to follow.  We will continue to refine our algorithm to adapt to more complex non-stationarity.\n\n\nFinally, we thank the reviewer for the careful inspection and insightful question, which indeed help us to improve our paper! We have corrected the typos and hope that we have clarified your concerns. We are happy and open to discussing any further questions.", "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": "rILjfJX7xi", "reviewer": "Reviewer_SDDb", "summary": "This paper studies the bandits with knapsacks problem in a piecewise-stationary environment and designs an algorithm that achieves a provably near-optimal competitive ratio. Instead of using a static benchmark, the performance guarantee is present based on a dynamic benchmark.", "questions": "- In line 5 of algorithm 1, why using $\\eta_{\\min}\\cdot\\alpha^q$ with restricting $q$ in ${\\0,1,...,M-1\\}$ to guess $B^*_l/(t_l-t_{l-1})$?\n- In Theorem 4.2, is it possible that $opt(FA)$ is close to the term $\\tilde{O}(L\\sqrt{|\\mathcal{K}NT|})$? In this case, would this bound be close to zero regardless of the preceding product term?", "limitations": "The authors have discussed the limitations as they claimed in the paper checklist.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The problem setup, piecewise-stationary BwK, complements the BwK literature.\n- This paper is well-structured. The warm-up section 3 on deterministic outcome setting really helps in understanding the algorithm for stochastic outcome setting.\n- For each algorithm/theoretical result, there are detailed explanations trying to give the intuition behind it.\n- The theoretical results are built on mild assumptions. They are solid and technical.", "weaknesses": "- It is hard for readers not having expertise in BwK to get the intuition of why the algorithm is near-optimal. Specifically, why IRES is good by reserving an equal budget for each ratio?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer’s time and effort in evaluating our manuscript. Your feedback is highly valued, and we would like to address your concerns and questions point by point. \n\nRegading \"Weaknesses\": “It is hard for readers not having expertise in BwK to get the intuition of why the algorithm is near-optimal. Specifically, why IRES is good by reserving an equal budget for each ratio?”\n\nResponse: We understand and share the concern about making the intuition behind our algorithm clear. In addition to the warm-up section 3, we have included a high-level overview and intuition in Section 2.3 (pages 3-4) to help clarify the technical discussions and makes our contributions more accessible. Based on the reviewer’s feedback, we recognize the need to introduce more foundational concepts of BwK before presenting our idea and will modify our paper accordingly. \n\nBwK differs from traditional multi-armed bandits (MAB) due to resource constraints. Each action in BwK not only yields a reward but also consumes resources from a limited budget, making it crucial to balance exploration and exploitation while ensuring the resource budget is not exceeded. In piecewise-stationary MAB, the performance of a non-anticipatory algorithm $\\pi$ is expressed as $\\sum_{t=1}^T R_t(a_t) \\geq \\sum_{t=1}^T r_t(a_t^{\\star}) - Reg$, where $\\sum_{t=1}^T R_t(a_t)$ is the cumulative reward achieved by algorithm $\\pi$, $\\sum_{t=1}^T r_t(a_t^{\\star})$ is the cumulative expected reward obtained by the best arm selections (with prior knowledge on $r_t$ over the entire planning horizon), and Reg is a sublinear-in-$T$ regret. \n\nIn piecewise-stationary Bwk, without assuming bounded global variation (Appendix A.2 on page 11), achieving a sublinear-in-$T$ regret is impossible. Therefore, the performance guarantee is in the form $\\sum^T_{t=1} R_t(a_t) \\geq \\frac{1}{\\text{CR}}\\cdot \\text{opt(FA)} - \\text{Reg}$, where opt(FA) is the cumulative expected reward obtained by the best dynamic policy (with prior knowledge on $(r_t, c_t)$ over the entire planning horizon, see Section 2.1 on page), CR is the competitive ratio and Reg is a deductive regret. In our work, we aim to develop algorithms that minimizes CR and ensures Reg to be sublinear-in-$T$. Specifically, IRES (full-feedback deterministic algorithm) and IRES-CM (bandit-feedback stochastic algorithm) both achieve CR=$O(\\log (\\eta_{\\max}/ \\eta_{\\min})) = O(M)$ (Theorem 3.2, Theorem 4.2), and we provide a matching CR lower bound (Theorem 4.5). \n\nRecall that we decompose the optimal reward opt(FA) into the reward-consumption ratio product the amount of resources assigned for each stationary piece $l$ (see equation (3) on page 4, sorry that the math formulation in the rebuttal may not show well). \n\\begin{equation}\n\\text{opt(FA)} = \\sum_{m=-M}^{M-1} \\sum_{l \\in \\mathcal{L}} \\text{Ratio}^{(l)\\star} \\cdot \\mathbf{1}(m^{\\star}_l =m) \\cdot B^{\\star}_l.\n\\end{equation}\n\nIRES aims to achieve a reward guarantee for each interval $m$ regarding the reward-consumption ratio $1(m_l^{\\star} =m) \\cdot \\text{Ratio}^{(l)\\star}$ and the resource consumption $\\sum_{l \\in \\mathcal{L}} 1(m_l^{\\star} =m) \\cdot B_l^{\\star}$. Regarding why IRES is good by reserving an equal budget for each ratio, a high-level explanation is that by doing so, we reserve adequate inventory (compared to $\\sum_{l \\in \\mathcal{L}} 1(m_l^{\\star} =m) \\cdot B_l^{\\star}$) for the correct guess of $1(m_l^{\\star} =m) \\cdot \\text{Ratio}^{(l)\\star}$ for each interval $m$. Specifically, we achieve the guarantee by performing two tasks: \n\n(a) for each $l \\in \\mathcal{L}$, we guess the value of $m$ such that $\\text{Ratio}^{(l) \\star} \\in (\\alpha^m, \\alpha^{m+1}]$. By solving a series of LPs in a round-robin manner, we guarantee that for at least $1/(M+1)$ fraction of requests on each $l$, our guessed ratio interval are close to the correct interval $m^{\\star}_l$. By accomplishing task (a), we ensure that for each $l \\in \\mathcal{L}$, at least $1(m_l^{\\star} =m) \\cdot B_l^{\\star}/(M+1)$ requested resources are served by resources reserved for interval $m$, generating reward at a ratio of at least $\\alpha^m$.\n\n(b) for each interval $m$, we \"reserve\" $B/2M$ resource units. That is, we reserve an inventory of $B/2M$ resource units to satisfy requests with a guessed reward-consumption ratio interval $m$. When the inventory reserved for interval $m$ is depleted, the DM rejects (by choosing $a_{\\text{null}}$) all future requests with a guessed interval $m$. By accomplishing task (b), if the reserved inventory for interval $m$ are not depleted by round $T$, our algorithm earns a reward of at least $\\alpha^m \\cdot 1(m_l^{\\star} =m) \\cdot B_l^{\\star}/(M+1)$ during stationary piece $l$. Else, if the reserved $B/2M$ resource units for interval $m$ are depleted by round $T$, then the DM earns a reward of at least $\\alpha^m \\cdot B/(2M) \\geq \\alpha^m \\cdot \\sum_{l \\in \\mathcal{L}} 1(m_l^{\\star} =m) \\cdot B_l^{\\star}/(2M)$ from resources reserved for interval $m$, since $\\sum_{l \\in \\mathcal{L}} 1(m_l^{\\star} =m) \\cdot B_l^{\\star} \\leq B$. \n\nGiven (a) & (b), a judicious analysis on the relationship between stationary pieces and reward-consumption ratio intervals is required to ensure a reward of \n\\begin{align}\n\\frac{1}{O(M)} \\cdot \\sum_{l \\in \\mathcal{L}} \\alpha^m \\cdot \\mathbf{1}(m^{\\star}_l =m) \\cdot B^{\\star}_l\n\\end{align}\nis accrued for each interval $m$. Hence, we achieve CR$=O(M)$.", "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": "ubVNshYlRP", "reviewer": "Reviewer_betX", "summary": "The paper studies the bandits with knapsacks problem in a piecewise-stationary environment. The paper proposes an algorithm guaranteering a near-optimal competitive ratio for the problem. The guarantees hold wrt a dynamic benchmark which is stronger than the standard stationary benchmark employed in adversarial BwK settings.", "questions": "Is the overhead of solving the LP at each iteration significant in your experiments? For example, how does it compare to \"lighter\" per-iteration updates, such as the primal-dual approach by Immorlica et al.?", "limitations": "n.a.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The setup is interesting and well motivated, and it fits nicely within the line of works trying to bridge between fully stochastic and fully adversarial environments. Moreover, the proposed algorithm provides some interesting insights on the problem and a new perspective with respect to the standard LagrangeBwK approach of Immorlica et al.", "weaknesses": "See questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are genuinely grateful to the reviewer for dedicating time and effort to evaluating our paper. We are glad to address your question.\n\nIn fact, the computational load of our algorithm is noticeably lighter than Immorlica et al. (2019). We solve $\\text{LP}(r^{(l)}, c^{(l)},\\eta_{\\min} \\cdot \\alpha^q)$ for each $q \\in ${$0,1, \\ldots, M$} in each iteration, which leads to no more than $(M+1)T = \\lceil \\log(\\eta_{\\max}/\\eta_{\\min}) \\rceil T$ LPs solved over the planning horizon. Immorlica et al. (2019) needs to solve $\\hat{g}(t) = \\max_{\\tau \\in [t]} \\tau \\cdot \\text{opt}(\\text{LP}(\\bar{M}^{\\text{ips}}_{\\tau}, B, \\tau))$ in each iteration (see their Algorithm 3 on page 20), which involves solving $t$ LPs in each round $t$. Thus, their primal-dual algorithm requires solving $T(T+1)/2$ LPs over the planning horizon. Since our $M$ is a logarithmic factor regarding the value range of $r_t(a), c_t(a) \\in [0,1]$ for all $t,a$, we typically have $M<<T$.  \n\nOur numerical experiments consistently exhibit computational time aligned with the theoretical complexity, with our algorithm being around 5-6 times faster than that of Immorlica et al. (2019). However, given that our paper is primarily theoretical, we conducted demonstrative experiments on smaller datasets where the overhead of solving LPs is not prominent.\n\nWe do agree that solving $(M+1)T$ LPs could still be expensive, and there could potentially be lighter approaches regarding per-iteration updates. Concerning non-stationary Bwk, the following papers do not require solving more than one LP per iteration: Fikioris and Tardos (2023) study an approximate stationary setting; Castiglioni et al. (2022a) study a large budget setting; Liu et al. (2022) focus on a bounded global variation setting. Their algorithms are lighter than ours in terms of computational buren, but their settings are significantly different from ours. Therefore, these works are not directly comparable with ours. \n\nFinally, we thank the reviewer for the valuable point on computational complexity. We will continue to work on reducing the computational load of our algorithm. We are happy and open to discussing any further questions. \n\nReferences\n\n[1] Fikioris, G., & Tardos, É. (2023, July). Approximately stationary bandits with knapsacks. In The Thirty Sixth Annual Conference on Learning Theory (pp. 3758-3782). PMLR.\n\n[2] Castiglioni, M., Celli, A., & Kroer, C. (2022, June). Online learning with knapsacks: the best of both worlds. In International Conference on Machine Learning (pp. 2767-2783). PMLR.\n\n[3] Liu, S., Jiang, J., & Li, X. (2022). Non-stationary bandits with knapsacks. Advances in Neural Information Processing Systems, 35, 16522-16532.", "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": "FSHz1z7Dry", "reviewer": "Reviewer_engA", "summary": "The paper studies Bandits with Knapsack (BwK) under a piecewise stationary environment. For the online matching problem where the true reward is fully known in each time period, the paper obtains a $\\Omega(1/\\ln(\\eta_{\\max}/\\eta_{\\min}))$ where $\\eta_{\\min}$ and $\\eta_{\\max}$ are such that all rewards and resources are in $[\\eta_{\\min}, \\eta_{\\min}]$. The paper also studies the online learning problem and gives theoretical results.", "questions": "1. The ratio of $\\ln(\\eta_{\\max}/\\eta_{\\min})$ seems to be weak. Imagine if $r_t=r$ and $c_t=c$ for all $t$, but $r$ and $c$ are dramatically different. It is reasonable to claim that the ratio approaches $1$ when the budget is not too low. Is it possible to refine the definition of $\\eta$ so that it only concerns $r/c$ (similar to that in Zhou et al. (2008))?\n2. In your contribution, you claim your performance guarantee is w.r.t. a dynamic benchmark, while existing adversarial BwK literature focus on the stationary benchmark. I think in many online matching papers the benchmark is also a dynamic one (see. e.g., Zhou et al. (2008)). Can you elaborate on this?\n3. In the online matching part, the algorithm design is not entirely novel. From my perspective, the inventory reserving idea is a deterministic version of the initial randomized policy in Immorlica et al. (2019). It is also similar to the booking limit or nested booking limit in the online matching/booking problem (see, e.g, [1]). Another issue with regard to the inventory reserving design is that it is not adaptive enough and may waste some resources because the reservation policy is fixed at the beginning. Can you elaborate on the technical novelty in your policy design?\n4. In the online learning problem, it seems you are essentially decreasing the competitive ratio in exchange for $\\sqrt{T}$ regret. Is this necessary? And also how do you set $\\alpha$?\n5. There are very limited numerical experiments for the planning problem and there is no experiment for the learning problem. I think only comparing to Immorlica et al. (2019) is not convincing. The authors may also consider comparing their algorithms with that in Zhou et al. (2008),\n\n[1] Ball, Michael O., and Maurice Queyranne. \"Toward robust revenue management: Competitive analysis of online booking.\" Operations Research 57.4 (2009): 950-963.", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The writing is good, and mostly easy-to-follow.\n2. The work gives theoretical guarantees to both the online matching and the online learning problem.", "weaknesses": "I appreciate all the technical proofs in the paper. However, it seems the paper lacks enough technical novelty as well as strong theoretical results. For details, please see Questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for the reviewer's time and effort in evaluating our manuscript. We highly value your feedback and would like to address your concerns and questions point by point.\n\n1. “The ratio of $\\ln (\\eta_{\\max}/\\eta_{\\min})$ seems to be weak. Imagine if $r_t=r$ and $c_t=c$ for all $t$, but $r$ and $c$ are dramatically different. It is reasonable to claim that the ratio approaches $1$ when the budget is not too low. Is it possible to refine the definition of $\\eta$ so that it only concerns $r/c$ (similar to that in Zhou et al. (2008))?\n\nResponse: We are grateful for your keen observation. Indeed, we can refine the definition of $\\eta$ so that it only concerns $r/c$. We will explain the change based on IRES in Section 3, and the same follows for IRES-CM in Section 4.\n\nBy our orignal definition, in line 5 of Algorithm 1, we solve $\\text{LP}(r^{(l)}, c^{(l)},\\eta_{\\min} \\cdot \\alpha^q)$ $\\forall q \\in \\{0,1, \\ldots, M\\}$. In this step, each $\\eta_{\\min} \\cdot \\alpha^q$ is a guess of $B_l^{\\star}/(t_l - t_{l-1})$. This is the only step we require $c^{(l)} \\in [\\eta_{\\min}, \\eta_{\\max}]$, in order to show that a “correct” guess of $B_l^{\\star}/(t_l - t_{l-1})$ leads to a “correct” guess of $ m^{\\star}_l$ where $\\text{Ratio}^{(l)\\star} \\in (\\alpha^{m_l^{\\star}}, \\alpha^{m_l^{\\star}+1}]$. All other steps only depend on the reward-consumption ratio. However, essentially line 5 only requires to output a guess of  an arbitrary decision $x_l$ such that\n\n\\begin{align}\n\\frac{\\sum_{a \\in \\mathcal{K}} r^{(l)}(a) x_l(a)}{\\sum_{a \\in \\mathcal{K}} c^{(l)}(a) x_l(a)} \\in (\\alpha^{m^{\\star}_l}, \\alpha^{m^{\\star}_l+1}]\n\\end{align}\n\nand $\\sum_{a \\in \\mathcal{K}} c^{(l)}(a) x_l(a) \\geq B_l^{\\star}/(t_l - t_{l-1})$. \n\nIn our revision, we re-define $\\eta_{\\min} = \\min_{t,a} \\frac{r_t(a)}{c_t(a)}, \\eta_{\\max} = \\max_{t,a} \\frac{r_t(a)}{c_t(a)}$, similar with $L$ and $U$ in Zhou et al. (2008) but considering multiple arms. Then $\\text{Ratio}^{(l)\\star} \\in [\\eta_{\\min},\\eta_{\\max}]$. We define $M=\\lceil\\log_{\\alpha}(\\eta_{\\max}/\\eta_{\\min})\\rceil$ and partition $[\\eta_{\\min}, \\eta_{\\max}]$ into $M$ intervals $(\\eta_{\\min}\\cdot \\alpha^{m-1}, \\eta_{\\min} \\cdot \\alpha^m]$ where $m=1,\\ldots,M$. For each stationary piece $l \\in \\mathcal{L}$, we denote $m_l^{\\star} \\in ${$0,\\ldots, M-1$} as the interval such that $\\text{Ratio}^{(l)\\star} \\in (\\eta_{\\min} \\cdot \\alpha^{m_l^{\\star}}, \\eta_{\\min} \\cdot \\alpha^{m_l^{\\star}+1}]$. Most of our paper remains the same, with only $M$ intervals and $m_l^{\\star}$ replaced by their new definitions. \n\nThe only major change happens in line 5 of Algorithm 1. Specifically, we change it into solving the following LPs for all $q \\in ${$0, \\ldots, M-1$} for the optimal solution $x_l^{(q)\\star}$:\n\\begin{align}\n\\max \\sum_{a \\in \\mathcal{K}} c^{(l)}(a) x_l^{(q)}(a) \n\\end{align}\n\\begin{align}\n\\text{s.t.} \\sum_{a \\in \\mathcal{K}} r^{(l)}(a) x_l^{(q)}(a) \\geq \\alpha^{q} \\cdot \\sum_{a \\in \\mathcal{K}} c^{(l)}(a) x_l^{(q)}(a)\n\\end{align}\n\\begin{align}\n\\sum_{a \\in \\mathcal{K}} r^{(l)}(a) x_l^{(q)}(a) \\leq \\alpha^{q+1} \\cdot \\sum_{a \\in \\mathcal{K}} c^{(l)}(a) x_l^{(q)}(a)\n\\end{align}\n\\begin{align}\n\\sum_{a \\in \\mathcal{K}} x_l^{(q)}(a)\\leq 1\n\\end{align}\n\\begin{align}\nx_l^{(q)}(a) \\geq 0       \\qquad \\forall a \\in \\mathcal{K}. \n\\end{align}\n\nIt can be seen that the modified line 5 of Algorithm 1 realizes its essential function. Then rest of the proofs remain valid (with updated definitions). We maintain a CR of $O(\\log(\\eta_{\\max}/\\eta_{\\min}))$, with $\\eta$ only depending on $r/c$ . We have modified the manuscript accordingly.", "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:
Dear Review Team, we are grateful for your careful reading and thoughtful comments. They are highly relevant and very insightful. On top of the point-to-point responses to individual reviewers, we would like to summarize and clarify critical concerns.

1. Are the problem and the algorithm sufficiently meaningful? 

Response: We believe our piecewise-stationary setting is meaningful. Theoretically, unconstrained piecewise-stationary bandits has drawn significant attention in recent years, with many interesting results derived. However, no prior paper addresses the bandits with knapsacks (Bwk) case. In the presence of resource constraints, merely detecting change points in {$(r_t, c_t)$}$_{t=1}^T$ is insufficient. Even with known change points, not knowing the means ${r^{(l)}, c^{(l)}}$ in each stationary piece $l = 1, \ldots, L$ prevents us from determining the optimal resource consumption in each stationary piece. Thus, besides hedging against arbitrary change points, we must address the uncertainty in ${r^{(l)}, c^{(l)}}$ and its impact on the "correct" amount of resource consumption. This marks a difference from unconstrained non-stationary bandits. Practically, our setting is more realistic than existing stationary/pure adversarial/bounded global variation settings.

We believe our algorithm is highly meaningful. Our Sections 3, 4 concern the **full** and **bandit** feedback settings respectively. In the former, the DM observes $r_t(a), c_t(a)$ before choosing $A_t$. In the latter, the DM only observes $R_t(A_t), C_t(A_t)$ (with means $r_t(A_t), c_t(A_t)$) after choosing $A_t$. In Section 3, we provide a novel perspective on the non-stationary Bwk problem, where we decompose the reward into two terms: the reward-consumption ratio multiplied by the resource consumption on each stationary piece. Correspondingly, we propose an intuitive inventory reservation algorithm by reserving a certain amount of inventory for each ratio interval and guessing the optimal reward-consumption ratio interval in each round. In Section 4, we carefully control the estimation procedure on {$(r_t, c_t)$}$_{t=1}^T$, which maintains the competitive ratio while achieving a regret term similar to that in unconstrained piecewise-stationary bandits. We provide the first provably near-optimal performance guarantee in the piecewise stationary BwK), which (a) **compares against the true optimum**, and (b) **allows bandit feedback**. Our ideas and algorithms are completely novel, and the technical details of our proofs are not at all trivial or similar to any existing paper. 

2. Requiring $r_t(a), c_t(a) \in [\eta_{\min}, \eta_{\max}]$ for all $t,a$ weakens the result.

Response: We have redefined $\eta$ so that $r_t(a)/c_t(a) \in [\eta_{\min}, \eta_{\max}]$ for all $t,a$. We have revised our algorithm mildly to achieve the same near-optimal competitive ratio, which is a stronger result. More details are provided in the response to question 1 of Reviewer engA. 

3. Novelty of algorithm design compared to Immorlica et al. (2019), Zhou et al. (2008) and other existing works.

Response: 

$\bullet$ Comparing with online matching papers (e.g. Zhou et al. (2008)): 

&nbsp;&nbsp;&nbsp; (i) Requiring less information: Our Section 3 has the same full feedback setting as online matching papers, which crucially require observing the actual values of $(R_t(a), C_t(a))$ for all $a \in \mathcal{K}$ **before** choosing $A_t$. Online matching algorithms cannot be readily generalized to our bandit setting (Section 4), where the DM only observes the outcomes $(R_t(A_t), C_t(A_t))$ **after** pulling arm $A_t$. The natural generalization from full to bandit feedback is one of our core contributions. 

&nbsp;&nbsp;&nbsp; (ii) Stronger benchmark: Zhou et al. (2008) measures the performance of their algorithm by the **best single arm** benchmark which requires pulling a single arm in each round; while our benchmark opt(FA) is a **best distribution over arms** benchmark, which is theoretically much stronger than Zhou et al. (2008)'s benchmark. 

&nbsp;&nbsp;&nbsp; (iii) More general results: In the full feedback setting, our performance guarantee encompasses Zhou et al. (2008), and in Section 4 we bypass the difficulty in Zhou et al. (2008) with the bandit setting. 

$\bullet$ Comparing with inventory reservation papers: Immorlica et al. (2019)’s inventory reservation strategy depends solely on the cumulated reward without considering the reward-consumption ratio, using traditional gradient descent-based algorithms. Our experiments demonstrate that their inventory reservation strategy is significantly more conservative than ours in the piecewise-stationary setting. Other works such as Ball and Queyranne (2009) all focus on different or more specialized settings. Our inventory reservation strategy is highly distinctive from existing methods.

$\bullet$ Comparing with non-stationary Bwk papers: Adversarial Bwk papers (Immorlica et al. (2019)) consider a more general non-stationary setting than ours, but compare their performance with a stationary benchmark where a fixed optimal arm (or a fixed distribution over arms) is applied in all $T$ rounds. Bwk with bounded variation papers (Liu et al. (2022)) require the total parameter variation to be bounded in terms of a global budget, which is a very strong assumption. Our setting does not require bounded global variation and our performance guarantee is compared with a dynamic benchmark, which makes our result strong both theoretically and practically, and comparatively more realistic.

4. Lower bound of Lemma 2.3 requires $L=T/B$, which does not look convincing.

Response: Theorem 4.5 already provides a valid CR lower bound, where we set $L$ to be a fixed value $2 \log(\eta_{\max}/\eta_{\min})$ and show that $\eta_{\min}>0$ is a necessary condition for obtaining a non-trivial CR.

We thank the review team for the valuable comments, and we are happy and open to discussing any further questions.

Meta-review: The paper studies the bandits with knapsacks (BwK) problem under a piecewise-stationary setting. The setting is different from the existing works on adversarial BwK and nonstationary BwK. It develops a new algorithm with the corresponding competitiveness ratio; in my opinion, the competitiveness ratio provides a different characterization (compared to the existing works) on how the algorithm performance is related to the distribution shift over time. 

Please consider including (i) more motivation for the setup, (ii) discussions compared to related works, and (iii) the new experiments in your future version of the paper.
Decision: Accept (poster)