Piecewise-Stationary Bandits with Knapsacks

Authors: xilin  zhang
cheung  wang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 07:54:44

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.

Main paper: 
 introduction: 
 In a bandits with knapsack (Bwk) problem, each action a in the action set K is associated with a latent and random amount of reward earned, R t paq, and resource consumed, C t paq, in each round t " 1, . . . , T . A decision maker (DM) selects an action a t P K in round t, and observes bandit feedback pR t pa t q, C t pa t qq. The DM targets at maximizing the total reward ř T t"1 R t pa t q, while satisfying the hard capacity constraint ř T t"1 C t pa t q ď B. Bwk has many real-life applications such as dynamic pricing Babaioff et al. (2015) , resource allocation Zhalechian et al. (2022) , online auction Balseiro and Gur (2019) and assortment planning Agrawal 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) and contextual bandits Badanidiyuru et al. (2014) ; Agrawal and Devanur (2016) . In stochastic Bwk problems, the expected feedback ErpR t paq, C t paqqs " prpaq, cpaqq is stationary for all a P K, t P t1, . . . , T u, and a sublinear-in-T regret is achievable. Nevertheless, the stationary model could be too ideal in many applications.An abundance of existing works explore adversarial online knapsack problems with full feedback, where pr t , c t q can change arbitrarily but their realized value of tpR t paq, C t paqqu aPK is observed before choosing a t (Karp et al. (1990) ; 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 a t 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 tpR t paq, C t paqqu aPK before selecting a t is crucial in the algorithm designs in Karp et al. (1990) ; Mehta et al. (2007) ; Zhou et al. (2008) . Their algorithm design cannot be readily generalized to the bandit setting, where the DM only observes pR t pa t q, C t pa t qq after selecting a t .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. (2022) . These works quantify the scale of non-stationarity in terms of both the local variation loc " ř T ´1t"1 distppr t`1 , c t`1 q, pr t , c t qq and the global variation glo " ř T t"1 distp ř T t"1 pr t , c t q{T, pr t , c t qq, where dist is a certain metric. Assuming maxtloc, glou grows sublinearly in T , they achieve sublinearin-T regret bounds compared to the dynamic benchmark. However, glo growing sublinearly in T 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 our model as a single-resource problem, and extend to d-resource problems in Appendix B.5 with an extra multiplicative factor of d 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 rewardconsumption ratio provides new insights into the problem. Thirdly, on performance guarantee (see Sections 3.2 and 4.2), we achieve a provably near-optimal competitive ratio with respect to a best distribution over arms benchmark without requiring a bounded glo, which distinguishes our work from the existing literature. Specifically, suppose there exists parameters η min , η max P p0, 1s such that η min ď r t paq, c t paq ď η max for all t, a. Our algorithms achieve a competitive ratio of Oplogpη max {η min qq, 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 al. (2008) under the piecewise-stationary settings. 
problem formulation: 
 Problem dynamics. The online model involves T rounds, indexed as t P T " t1, 2, . . . , T u. We index an arm as a P K. Additionally, we define the null arm a null , where no allocation is made when a null is chosen. In round t P T , the DM chooses an arm a t P K Ť ta null u, and observes a noisy outcome vector pR t pa t q, C t pa t qq P r0, 1s 2 as the bandit feedback, where R t pa t q and C t pa t q are the reward and the resource consumption in round t respectively. We set R t pa null q " C t pa null q " 0 with certainty for all t P 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 at most B with certainty. Denote r t " tr t paqu aPK " tErR t paqsu aPK and c t " tc t paqu aPK " tErC t paqsu aPK . We consider a piece-wise stationary setting, where the planning horizon T is partitioned into L stationary pieces tt 0 " 1, . . . , t 1 u, tt 1 `1, . . . , t 2 u, . . . , tt L´1 `1, . . . , t L " T u. On each stationary piece l, we have pr t , c t q " pr plq , c plq q for all t P tt l´1 `1, . . . , t l u.The DM does not know the number of rounds T , the number of stationary pieces L, the rounds t 1 , . . . , t L´1 where changes happen, the values of tpr plq , c plq qu lPt1,...,Lu and their realized outcomes.Goal and benchmark. Our goal is to develop an online algorithm that maximize the expected total reward Er ř T t"1 R t pa t qs while satisfying the inventory constraint ř T t"1 C t pa t q ď B, which can be formulated as the following dynamic program DP. In DP, X t " tX t paqu aPK is a binary decision vari-able indicating whether to pick arm a in round t (i.e., X t paq " 1) or not (i.e., X t paq " 0). An online algorithm is non-anticipatory in the sense that X t depends only on B and tpR s pa s q, C s pa s q, X s qu t´1 s"1 .DP x l paq ď 1 @l " 1, . . . , Lx l paq ě 0 @a P K, l " 1, . . . , L.In non-stationary bandits without resource constraints, the performance bound of an online algorithm is in the form of ř T t"1 R t pa t q ě ř T t"1 r t pa t q ´Reg, where ř T t"1 r t pa t q is the optimal expected reward obtained by choosing the best arm in each round, and Reg is a sublinear-in-T regret characterizing the reward loss. In our Bwk setting, due to the inventory constraint, achieving a sublinear-in-T regret is impossible without assuming a bounded global variation (see Appendix A.3). We denote optpPq as the optimum of an optimization problem P. We aim for a performance guarantee of the form ř T t"1 R t pa t q ě 1 CR ¨opt(DP) ´Reg, where opt(DP) is the optimum of DP, CR is a competitive ratio, and Reg is a sublinear-in-T regret. Unfortunately, DP is hard to solve. Therefore, we define a fluid approximation FA of DP, where R t and C t are replaced by their respective expectations, and the decision variables are fractional. In the following Lemma 2.1 (proved in Appendix C.1), we justify that opt(FA) can serve as a benchmark for our algorithms' performance sinceT ÿ t"1 R t pa t q ě 1 CR ¨optpFAq ´Reg ě 1 CR ¨opt(DP) ´Reg,and we aim to derive performance guarantees of the form ř T t"1 R t pa t q ě 1 CR ¨optpFAq ´Reg. Lemma 2.1. opt(FA)ěopt(DP).Compared with the adversarial Bwk literature, our piecewise-stationary setting has two limitations. The first is on L, the number of change points. When L is not known, our result is meaningful only when L " op ? T ¨ηmin q. When L is known, our result is meaningful when L " opT ¨ηmin q (see Theorem 4.2). 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 a P K, l P t1, . . . , Lu, there exists known constants η min , η max P p0, 1s such that η min ď r plq paq, c plq paq ď η max .While η min can be as small as 0 generally, we 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) to 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 0 or negative expected return. In applications such as dynamic pricing, assortment planning, network resource allocation and energy management, expected profits and consumer demands are usually within a known positive value range. We further justify that Assumption 2.2 theoretically in the following Lemma 2.3 (proved in Appendix C.5).Lemma 2.3. For any online algorithm, there exist an instance for which 0 ď r t paq, c t paq ď 1 for all a P K, t P T , and that CRą Ωplogpη max {η min qq.Additionally, in Appendix C.5 we demonstrate that knowing the values of η min , η max is necessary for achieving CR" Oplogpη max {η min qq.Decomposing opt(FA) in terms of reward-consumption ratios. Throughout our paper, we fix an optimal solution tx l u L l"1 to FA. We define the set L " tl P t1, . . . , Lu : ř aPK x l paq ą 0u, which indexes stationary pieces where non-null allocations are made under the optimal solution tx l u L l"1 to FA . For each l P L, we define Ratio plq˚" ř aPK r plq paqx l paq ř aPK c plq paqx l paqP " η min η max , η max η min ȷ , B l " pt l ´tl´1 q ÿ aPK c plq paqx l paq. (1)Ratio plq˚, whose value range follows from Assumption 2.2, is the optimal expected reward earned per unit of consumed resource under tx l u L l"1 . We call Ratio plq˚t he optimal expected rewardconsumption ratio of stationary piece l. B l represents the optimal expected amount of resources assigned for stationary piece l. To aid our algorithm design, we define the following linear program:LPpr, c, Bq :" max ÿ aPK rpaqxpaq s.t. ÿ aPK cpaqxpaq ď B ÿ aPK xpaq ď 1 xpaq ě 0 @a P K.Then, we can express optpFAq in terms of LPpr, c, Bq and Ratio plq˚, B l as follows:EQUATIONThe first equation in ( 2) can be verified by noting that x l is feasible to LPpr plq , c plq , B l {pt l ´tl´1 qq for each l P t1, . . . , Lu, and the concatenation of the optimal solutions of tLPpr plq , c plq , B l {pt l tl´1 qu lPL forms a feasible solution to FA. The second equation in (2) holds, by the definitions of Ratio plq˚, B l and the fact that optpLPpr plq , c plq , B l {pt l ´tl´1 qqq " ř aPK r plq paqx l paq. Algorithm design. Fix an arbitrary constant α ą 1 (we set α " e by default, but our results hold for any constant α ą 1). We define M " rlog α pη max {η min qs and partition rη min {η max , η max {η min s into 2M intervals rα ´M , α ´M `1s Ť tpα m , α m`1 su M ´1 m"´M `1. For each stationary piece l P L, we denote m l P t´M, . . . , M ´1u as the interval such that Ratio plq˚P pα m l , α m l `1s. In the forthcoming discussion, with some abuse of notation, we sometimes write interval rα ´M , α ´M `1s as pα ´M , α ´M `1s, and we refer to interval pα m , α m`1 s as reward-consumption ratio interval m, or "interval m" in short. Then we can decompose opt(FA) regarding reward-consumption ratio intervals:opt(FA) " p2q " M ´1 ÿ m"´M ÿ lPL Ratio plq˚¨1 pRatio plq˚P pα m , α m`1 sq ¨Bl " M ´1 ÿ m"´M ÿ lPL Ratio plq˚¨1 pm l " mq ¨Bl .(3)The key intuition of our algorithm is to achieve a reward guarantee for each interval m regarding the reward-consumption ratio 1pm l " mq ¨Ratio plq˚a nd the resource consumption ř lPL 1pm l " mq ¨Bl , which is done by performing two tasks: (a) for each l P L, we guess the value of m such that Ratio plq˚P pα m , α m`1 s. We guarantee that for at least 1{pM `1q fraction of requests on each l, our guessed ratio interval are close to the correct interval m l ; (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 null ) all future requests with a guessed interval m.By accomplishing task (a), we ensure that for each l P L, at least 1pm l " mq¨B l {pM `1q requested resources are served by resources reserved for interval m, generating reward at a ratio of at least α m . Then, 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 α m ¨1pm l " mq ¨Bl {pM `1q 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 α m ¨B{p2M q ě α m ¨řlPL 1pm l " mq ¨Bl {p2M q from resources reserved for interval m, since ř lPL 1pm l " mq ¨Bl ď B. By judiciously analyzing the relationship between stationary pieces and reward-consumption ratio intervals, for each interval m, we ensure that a reward of 1 OpM q ¨ÿ lPL α m ¨1pm l " mq ¨Bl is accrued, which is 1{OpM q of the benchmark resources consumed on all stationary pieces l P L whose Ratio plq˚P pα m , α m`1 s. By summing over m P t´M, . . . , M ´1u, we achieve 1{OpM q fraction of reward (3).3 Warm-up: Full-feedback deterministic outcome settingIn this section, we introduce the main idea of our algorithm on the bandit model by relaxing the model uncertainty assumptions and specializing to the full-feedback deterministic setting: pR t , C t q " pr plq , c plq q with certainty for each t P tt l´1 `1, . . . , t l u. Thus, pr plq , c plq q is observed at the start of the stationary piece l. The DM does not know L and tt 1 , . . . , t L´1 u before the online process begins. The DM's decision can be fractional, which means on each stationary piece l, a decision can take the form of x l P tx P r0, 1s |K| : ř aPK xpaq ď 1, xpaq ě 0 @a P Ku, resulting in a reward of ř aPK r plq paqx l paq and resource consumption of ř aPK c plq paqx l paq in a round. 
inventory reserving (ires) algorithm: 
 Upon observing pR t , C t q " pr plq , c plq q, guessing Ratio plq˚( see Section 2.3) is equivalent to guessing x l , which is equivalent to guessing B l {pt l ´tl´1 q, since tx l u L l"1 is an optimal solution to LPpr plq , c plq , B l {pt l ´tl´1 qq. In this section, when we say "Line xx", we refer to a line of Algorithm 1, which displays IRES. At the start, the IRES reserves B{2M units of resource to each interval m P t´M, . . . , M ´1u, and each resource unit is reserved by exactly one interval. In Line 5, for each stationary piece l, we firstly solve LPpr plq , c plq , η min ¨αq q for each q P t0, . . . , M u, and get an optimal solution x pqql " tx pqql paqu aPK . Each η min ¨αq is a guess of B l {pt l ´tl´1 q. For each q P t0, . . . , M u, we define Ratio pqq l :" ř aPK r plq paqx pqql paq ř aPK c plq paqx pqql paq as a guess of Ratio plq˚. Claim 3 in Appendix B.3 shows that, by guessing a q such that η min ¨αq is within a factor of α from B l {pt l ´tl´1 q, we also have Ratio pqq l to be at most a factor of α from Ratio plq˚. As time progresses on l, we go round-robin on the choices of q t P t0, . . . , M u for each round t (Lines 7, 15). In round t P tt l´1 `1, . . . , t l u, we identify m t P t´M, . . . , M ´1u such that Ratio pqtq l P pα mt , α mt`1 s (Line 8). If there remains enough reserved resource units for interval m t (Line 10), the DM fulfils the t-th request by selecting fractional action x t " x pqtql (Line 11), which consumes resources reserved for m t (Lines 9, 11). Otherwise, the DM selects a null and rejects the request (Line 13). By Line 9, we have T pmq t " ts P t1, . . . , tu : m s " mu, which consists of rounds in t1, . . . , tu when the DM attempts to fulfil a request with resources reserved for interval m.We provide a performance guarantee to IRES in Theorem 3.1. Theorem 3.1. For any given α ą 1, IRES achieves a reward of at least´1 ´2 log α pηmax{ηminq`1 B ¯¨opt(FA)6α 2 ¨log α pη max {η min q , under mild requirements that t l ´tl´1 ě M `1 @l P L. In particular, IRES achieves a competitive ratio of Oplog α pη max {η min qq if B ě Ωplog α pη max {η min qq.Algorithm 1 Inventory REServing with deterministic input (IRES)1: Input: resource capacity B, η min , η max . 2: Initialize l " 0, t " 1, q 1 " 0, T pmq t" H for all m, t. 3: while t ď T do 4:Set l " l `1.Solve LPpr plq , c plq , η min ¨αq q @q P t0, 1, . . . , M u for optimal x pqql " tx pqql paqu aPK .6:while stationary piece l not end do 7:Let pr t , c t q " pr plq , c plq q, x t " x pqtql .8:Find m t P t´M, . . . , M ´1u such that Ratio pqtq l P pα mt , α mt`1 s. if q t ď M ´1 then set q t`1 " q t `1 else set q t`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 pr t , c t q revealed in each round Zhou et al. (2008) , but our pr t , c t q remains the same for an unknown number of rounds. Assuming B ě Ωpη max q, Zhou et al. ( 2008) achieve a competitive ratio of 2 logpη max {η min q `1 and they provide a nearly-matching lower bound. We recover their competitive ratio with an extra 3α 2 multiplicative factor in a piece-wise stationary setting and a stricter requirement on B.Denote T pmq T " tτ pmq p1q, τ pmq p2q, . . .u where τ pmq p1q ă τ pmq p2q ă . . ., and T pmq is the prefix of T That is, T pmq consist up to the last round assigned to interval m such that the reserved inventory is not fully consumed. It is evident that if ř sPT pmq T c s pa s q ď B{p2M q ´1, then T pmq " T pmq T .Define J l " tt l´1 `1, . . . , t l u, the time interval of the l-th piece. The reward achieved by IRES is REW " ř tPT ř aPK r t paqx t paq, which can be decomposed as REW "ř M ´1 m"´M REW pmq where REW pmq " ÿ lPL 1pm l " mq ÿ tPp Ť M ´1 n"´M T pnq q Ş J l ÿ aPK r t paqx t paq. The set p Ť M ´1 n"´MT pnq q Ş J l consists of rounds in stationary piece l, which requests are not rejected due to shortage in reserved resource units. The summation ř lPL 1pm l " mq yields the reward accrued on pieces where m l " m. By the summation ř M ´1 m"´M REW pmq , we obtain the total reward accrued with resources reserved for 2M intervals.Similarly, we decompose the benchmark opt(FA) " ř M ´1 m"´M opt(FA) pmq where opt(FA) pmq " ÿ lPL 1pm l " mq ¨Ratio plq˚¨Bl , To prove Theorem 3.1, it suffices to show REW pmq ě 1´p2M `1q{B 6α 2 M ¨opt(FA) pmq for each interval m, as in the following Claim 1 and Claim 2. Then Theorem 3.1 can be established by summing over m P t´M, . . . , M ´1u.Claim 1. For any interval m P t´M, . . . , M ´1u, if for all n P tmaxtm ´1, ´M u, mu we have T pnq " T pnq T , then REW pmq ě 1 2αM ¨opt(FA) pmq . Claim 2. For any interval m P t´M, . . . , M ´1u, if for at least one element n P tmaxtm 1, ´M u, mu we have T pnq Ĺ T pnq T , then REW pmq ě 1´p2M `1q{B 6α 2 M ¨opt(FA) pmq . Sketch proofs of Claims 1, 2. Claims 1, 2 are proved in Appendices C.2, C.3 respectively. We first show in Claim 3 in Appendix B.3 that on a stationary piece l P L, there exists a "correct" q l P t0, . . . , M u, such that when selecting decision x t " x pq l ql (the optimal solution to the LPpr plq , c plq , η min ¨αq l q), our guess Ratio pq l q l on the ground-truth Ratio plq˚P pα m l , α m l `1s satisfies RatioEQUATION)When taking fractional action x pq l ql , we consume resources reserved for reward-consumption ratio intervals m l ´1 or m l . Therefore by our round-robin design, on each stationary piece l such that m l " m, at least pt l ´tl´1 q{pM `1q requests are assigned to intervals m ´1 or m, under decision , as discussed in Section 2.3.For an interval m where T pmq " T pmq T , T pm´1q " T pm´1q T (Claim 1 case), there are still remaining resources reserved for intervals m ´1, m at the end of the horizon. Hence, for each stationary piece l such that m l " m, at least pt l ´tl´1 q{pM `1q requests (consuming B l {pM `1q resource units) are indeed fulfilled by resources reserved for interval m ´1 or m, accruing reward at the reward-consumption ratio of at least Ratio plq˚{ α according to (4). Summing over all l such that m l " m, we have REW pmq ě ř lPL pRatio plq˚{ αq ¨1pm l " mq ¨Bl {pM `1q and Claim 1 is validated. For an interval m where there exists some n P tmaxtm ´1, ´M u, mu such that T pnq Ĺ T pnq T (Claim 2 case), the B{2M resource units reserved for interval n are depleted before the end of the horizon. In this case, some requests on stationary piece l where m l " m may be rejected, but the B{p2M q resource units reserved for interval n have been consumed, generating reward at a reward-consumption ratio of at least α n ě α m´1 . Since the total resources that should be consumed w.r.t. interval m under the optimal FA solution is ř lPL 1pm l " mq ¨Bl ď B, we have REW pmq ě α m´1 ¨B{p2M q ě ř lPL pRatio plq˚{ α 2 q ¨1pm l " mq ¨Bl , and Claim 2 is validated.4 Bandit-feedback stochastic outcome settingIn this section, we consider the original piece-wise stationary Bwk model, where the DM receives bandit feedback on outcomes pR t , C t q, and decisions are randomized. 
inventory reserving with change monitoring (ires-cm) algorithm: 
 In this section, when we say "Line xx", we refer to a line of Algorithm 2, which displays IRES-CM. In the bandit-feedback setting, guessing Ratio plq˚r equires estimating pr plq , c plq q. To do so, we adaptively partition T into exploration rounds and exploitation rounds. In each round t, we conduct exploration with probability γ t " M a |K| logp1{δqplogp|K|q `1q{ ? N t (reflected in a Bernoulli random variable U ptq in Line 7), where δ P p0, 1q is a confidence parameter and N is defined in (5). In an exploration round t (Lines 9-13), we uniformly sample an arm a P K and pull it for N consecutive rounds. We update an estimate pr t paq, ĉt paqq on pr t paq, c t paqq " pr plq paq, c plq paqq using the tpR s paq, C s paqqu sPT S t paq information, where T S t paq denotes the set of the most recent N exploration rounds before round t when arm a is pulled. That is, we set T S t paq " tτ P tt´s t , . . . , t1 u : a τ " au where s t " arg max s t ř t´1 τ "t´s 1pa τ " aq " N u. We defineEQUATIONThe estimates rt , ĉt 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 (5) to balance these two errors. We let T R t denote the set of exploration rounds.In an exploitation round t (Lines 17-25), we take turns to pull arms according to decision xpqtqt , which is very similar to Algorithm 1 with pr t , ĉt q in place of pr t , c t q. We definez Ratio pqq t " ř aPK rt paqx pqqt paq ř aPK ĉt paqx pqqt paq , p:q t " max " min " z Ratio pqtq t , α M * , α ´M * ,which can both be interpreted as a guess of Ratio plq˚a t any round t during stationary piece l. We reserve B{p2M q units of resources for each interval m P t´M, . . . , M ´1u. In round t, we serve request t using resources reserved for interval mt such that p:q t P pα mt , α mt`1 s. If interval mt has remaining reserved inventory, then we pull arm a t " a with probability xpqtqt paq, or a t " xpqtqt in short. We let T Ipmq t 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 pr t , c t q by pr t , ĉt q, which is detailed in Section 4.3. " H for all m, t. 3: Pull each arm a P K for N times, get rt paq, ĉt paq as in (5). 4: Set t " N |K| `1. 5: while t ď T do 6:Solve LPpr t , ĉt , η min ¨αq q @q P t0, 1, . . . , M u for optimal xpqqt " tx pqqt paqu aPK .Sample U ptq " Bernpγ t q.8:if U ptq " 1 then 9:Pick arm a " UnipKq, pull arm a s " a.Set U psq " 1 for s P tt, . . . , t `N ´1u.11:Set T R s " T R t´1 Ť tt, .. . , su for s P tt, . . . , t `N ´1u.12:Set t " t `N , pr t , ĉt q " pr t´N , ĉt´N q.13:Update ĉt paq, rt paq as in (5).14: else 15:for q " 0, . . . , M do 16:Set q t " q.17:Determine mt P t´M, . . . , M ´1u such that p:q t P pα mt , α mt`1 s.Set TIp mtq t " T Ip mtq t´1 Ť ttu. 19: if ř sPT Ip mt q t´1 C s pa s q ď B 2M ´1 then 20:Pick arm a t " xpqtqt .21:else 22:Pick arm a t " a null .end ifSet t " t `1, pr t , ĉt q " pr t´1 , ĉt´1 q.25:end for 26:end if 27: end whileWe impose the following assumption on the ranges of B, opt(FA).Assumption 4.1. mintB, opt(FA)u ě ΩpL a |K|N T q, where Ωp¨q hides multiplicative factors in terms of log α pη max {η min q, logp1{δq, plogp|K|q `1q.The performance of IRES-CM is as follows: Theorem 4.2. For any given α ą 1, with probability at least 1 ´2|K| ¨plog α pη max {η min qL `T qδ, IRES-CM achieves a reward of at least1 ´op1q 10α 4 ¨log α pη max {η min q ¨´opt(FA) ´Õ ´La |K|N T ¯8under Assumption 4.1, where op¨q hides multiplicative factors in terms of a M {B and Õp¨q hides multiplicative factors in terms of log α pη max {η min q, logp1{δq, plogp|K|q `1q. In particular, IRES-CM achieves a competitive ratio of Oplog α pη max {η min qq as long as L " op ? T ¨ηmin q.The proof of Theorem 4.2 can be found in Appendix C.4. We provide a thorough comparison of our performance guarantee with existing works on adversarial and non-stationary Bwk in Appendix A. Remark 4.3 (Improved performance with known L). If the DM knows L, Assumption 4.1 can be relaxed to mintB, opt(FA)u ě Ωp a L|K|N T q.Furthermore, in our performance guarantee in Theorem 4.2, the deductive term ÕpL a |K|N T q from opt(FA) can be improved to Õp a L|K|N T q by setting the exploration parameter γ t " M a L|K| logp1{δqplogp|K|q `1q{ ? N t in IRES-CM. Without prior knowledge of L, the deductive term ÕpL a |K|N T q " opT q if L " op ? T ¨ηmin q; with prior information of L, the deductive term Õp a L|K|N T q " opT q if L " opT ¨ηmin q. Remark 4.4 (Deterministic setting with bandit feedback). In our full-feedback deterministic setting, since pr plq , c plq q is given at the beginning of each stationary piece, our performance guarantee is independent on |K|, L. In a bandit-feedback deterministic setting, IRES-CM can be applied by setting N " 1. In this case, under Assumption 4.1, IRES-CM achieves a reward of at least1 ´op1q 6α 2 ¨log α pη max {η min q ¨´opt(FA) ´ÕpL a |K|T q ¯.We denote σ t paq " mints : s P T S t paqu as the 1st element in T S t paq. We partition the exploitation round set T Ipmq T into two sets q T Ipmq and p T Ipmq , i.e., TIpmq T " q T Ipmq Ť p T Ipmq , q T Ipmq Ş p T Ipmq " H. A time index t P T Ipmq Tbelongs to the set q T Ipmq (referred to as "successful exploitation rounds regarding interval m") if and only if the following condition is satisfied for all a P K: tpr s paq, c s paqqu aPK " tpr σtpaq paq, c σtpaq paqqu aPK , @s P tσ t paq, . . . , tu.(6)For t P p T Ipmq (referred to as "failed exploitation rounds regarding interval m"), inequality ( 6) is violated for at least one a P K. We denote p T Ipmq " tτ Ipmq p1q, τ Ipmq p2q, . . .u where τ Ipmq p1q ă τ Ipmq p2q ă . . .. We let T Ipmq be a prefix of p T Ipmq satisfyingT Ipmq " # τ Ipmq pnq P q T Ipmq : n ÿ s"1 ÿ aPK C τ Ipmq psq `aτ Ipmq psq ˘ď B 2M ´1+which consists up to the last exploitation round satisfying (6) for interval m, such that the reserved resource is adequate. Ifř sPT Ipmq T C s pa s q ď B{p2M q ´1, then T Ipmq " q T Ipmq .Sketch proof of Theorem 4.2. Recall that the performance guarantee of our algorithms is in the form of ř T t"1 R t pa t q ě 1 CR ¨optpFAq ´Reg. The proof consists of mainly two steps: (a) we derive the CR" OpM q by bounding two different cases of interval m in a similar manner to Claim 1 and Claim 2 (see Appendix C.4), with q T Ipmq (successful exploitation rounds in IRES-CM) in place of T 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 pr t , c t q, reflected in the following aspects: (i) reward loss caused by exploration (upper bounding |T R T |); (ii) T S t paq contains change points, causing failed estimation of pr t , c t q (upper bounding | Ť M m"´M ´2 p T Ipmq |); (iii) T S t paq does not contain change points, but the discrepancy between pr t , c t q and pr t , ĉt q results in assigning Ratio plq˚( estimated by z Ratio pqq t ) to the wrong interval. We remark that the losses due to (i, ii) are accounted for in Reg, while (iii) is accounted for in the CR.We complement our analysis by showing the tightness of our CR (see Appendix C.6 for proof).Theorem 4.5. Consider a fixed but arbitrary α ą 1, and set η min " α ´3ν , η max " 1 for an arbitrary ν P Z ą0 . For any online algorithm, there exist an instance for which η min ď r t paq, c t paq ď η max for all a P K, t P T , and that ř T t"1 R t pa t q{opt(FA) ď Θp1{ log α pη max {η min qq.Question: Does the 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 (regardless of whether the code and data are provided or not)? Answer: [Yes] Justification: We firstly make it clear that our paper is a theoretical 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 to 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 a 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 is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to 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 to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. Justification: This is a 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 negative 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
numerical experiments: 
 We run numerical experiments on a single-resource problem where L " 2, T " 20000 (each stationary piece has 10000 rounds), K " t1, 2u, B " 9360 and we set α " e for our algorithms. 2008)'s algorithm with extra information of pr t , c t q before making decisions in each round, and compare the performance of algorithms with the linear program benchmark FA (dotted curves in Figure 1 ). In Figure 1 (a), we set r p1q p1q " r p1q p2q " 0.5, c p1q p1q " c p1q p2q " 1 for stationary piece 1; and set r p2q p1q " 1, r p2q p2q " 0.5, c p2q p1q " 0.5, c p2q p2q " 1 for stationary piece 2. In Figure 1 2008)'s algorithm performs well with the extra information of pr t , c t q before making decisions. In Figure 1 (b), the optimal solution of the benchmark FA chooses mixed arms on the second stationary piece, where x 2 p1q " 0.128, x 2 p2q " 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 run on a Surface Pro 7 with an i5-1035G4 processor. All results can be produced within 30 minutes. Kesselheim and Singla (2020) (achieving Oplogpdq ¨logpT qq competitive ratio) study the adversarial BwKs, where the adversarial bandit feedback pr t pa t q, c t pa t qq is revealed in each time step after pulling arm a t . Their setting is more general than ours, since they require no boundedness assumption or piece-wise stationary assumption on their outcomes. Note that if our η min can be expressed as a function of T , i.e., η min " T ´β for a β P p0, 1q, our result can extend to multiple resources and achieve a competitive ratio of Opd logpT qq (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 x l " x ˚for all l P L; while we compare our result with the dynamic benchmark FA. Specifically, 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 to our setting.In our Section 3, we discuss a warm-up setting where tR t paq, C t paqu aPK is observable upon the arrival of the round t customer, which is similar with adversarial online knapsack with full feedback (Karp et al. (1990) They all have boundedness assumption on glo. In our setting (glo unbounded), their algorithms incur a linear-in-T regret even when L " 1, and no non-trivial competitive ratio is established in their work.To see the case of L " 1 but glo " ΘpT q, consider the case of K " t1u, and we have pr 1 p1q, c 1 p1qq " . . . " pr T {2 p1q, c T {2 p1qq " p1, 0.5q, but pr T {2`1 p1q, c T {2`1 p1qq " . . . " pr T p1q, c T p1qq " p0.5, 1q. In this case, we can verify that dist˜T ÿ t"1 pr t , c t q{T, pr 1 , c 1 q ¸" dist ˜T ÿ t"1pr t , c t q{T, pr T {2`1 , c T {2`1 q ¸" 0.5, so we have glo " 0.5T despite L " 1.For functions f pxq : R ě0 Ñ R ě0 and gpxq : R ě0 Ñ R ě0 , we say f pxq is Opgpxqq (resp. Ωpgpxqq) if there exist positive constants C and n, such that for all x ě n, f pxq ď C ¨gpxq (resp. f pxq ě C ¨gpxq). We use Õpgpxqq (resp. Ωpgpxqq) to hide logarithmic terms in x other than gpxq.Lemma B.1 (Multiplicative Azuma-Hoeffding Inequality (Kuszmaul and Qi (2021) )). X 1 , . . . , X n P r0, cs are real-valued random variables, and tF n u n i"0 is a filtration. Let µ " ř n i"1 a i where a i are real-valued constants. (i) Suppose ErX i |F i´1 s ď a i holds for all i P t1, . . . , nu almost surely. Then for any δ P p0, 1q, Pr« n ÿ i"1 X i ď ˜1 `d 3c µ log ˆ1 δ ˙¸µ ff ě 1 ´δ.(ii) Suppose ErX i |F i´1 s ě a i holds for all i P t1, . . . , nu almost surely. Then for any δ P p0, 1q, Pr Badanidiyuru et al. (2018) ). Let X 1 , . . . , X N P r0, 1s be random variables. Let X " ř N i"1 X i be the sample average, and let µ "« n ÿ i"1 X i ě ˜1 ´d 2c µ log ˆ1 δ ˙¸µ ff ě 1 ´δ. Lemma B.2 (Lemma 2.1,ř N i"1 ErX i |X 1 , . . . , X N s.Then, for any δ P p0, 1q, Pr ´|X ´µ| ď a 2X logp1{δq `4 logp1{δq ¯ě 1 ´3δ.Recall that x pqql is an optimal solution to LPpr plq , c plq , η min ¨αq qq, and x l is an optimal solution of LPpr plq , c plq , B l {pt l ´tl´1 qq which is an 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 l, x pqql for at least one q P t0, . . . , M u is close to x l in terms of both the resource consumption and the reward-consumption ratio. This leads to the important result that for all t P tt l´1 `1, . . . , t l u, m t P tm l ´1, m l u.Claim 3. On stationary piece l P L, there exists q l P t0, 1, . . . , M u that satisfies both Proof of Claim 3. The existence of q l satisfying ( 7) is evident, since η min ¨α0 " η min and η min αM " η max . To show that q l also satisfy (8), we define The first inequality in (10) holds since B l {pt l ´tl´1 q " ř aPK c plq paqx l paq ď η min ¨αq l . Therefore, the resource constraint in LPpr plq , c plq , B l {pt l ´tl´1 qq is tighter than LPpr plq , c plq , η min ¨αq l q.We prove the second inequality in (10) by contradiction. Suppose To establish (8), it suffices to show d plq ď α. By ( 7) and ( 9), it is evident that d plq ď α when q l ą 0. If q l " 0, then constraints ř aPK x l paq ď 1 and ř aPK x pq l ql paq ď 1 are not tight in both LPpr plq , c plq , B l {pt l ´tl´1 qq and LPpr plq , c plq , η min q. In this case, both LPs are knapsack problems and have closed-form solutions of , which shows that d plq " 1 ă α when q l " 0.Inequality (11) holds since by summing over w P tmaxtm ´1, ´M u, m, mintm `1, M ´1uu for each m P t´M, . . . , M ´1u, we repeat the sum for at most 3 times. Therefore, the ratio of the reward achieved by IRES to opt(FA) can be decomposed as:EQUATIONThen, to prove Theorem 3.1, it suffices to showEQUATION)To prove ( 14), we focus on showing in Claims 1 and 2.REW pmq opt(FA) pmq ě1 3 ¨řmintm`1,M´1u w"m´1 ř lPL 1pm l " wq ř tP Ť M ´1 m"´MT pmq Ş J l ř aPK r t paqx t paq ř lPL 1pm l " mq ¨řaPK r plq paqx l paq ř aPK c plq paqx l paq ¨Bl ě 1 ´p2M `1q{B 6α 2 M for each m P t´M, . . . , M ´1u.Our results can be readily extend to the multiple-resource case, with |I| " d resources indexed by i P I. An upper bound for a multi-resource allocation problem (corresponding to FA in the single-resource setting) can be formulated as:FA MUL :" max L ÿ l"1 pt l ´tl´1 q ÿ aPK r plq paqx l paq s.t. L ÿ l"1 pt l ´tl´1 q ÿ aPK c plq i paqx l paq ď B @i P I ÿ aPK x l paq ď 1 @l " 1, . . . , Lx l paq ě 0 @a P K, l " 1, . . . , L. which is evidently upper bounded by the following LP: x l paq ď 1 @l " 1, . . . , Lx l paq ě 0 @a P K, l " 1, . . . , L.It is evident that the LP below achieves a reward of at least 1{d fraction of opt(FA MUL-U q.FA MUL-F :" maxL ÿ l"1 pt l ´tl´1 q ÿ aPK r plq paqx l paq s.t. L ÿ l"1 pt l ´tl´1 q ÿ aPK ˜ÿ iPI c plq i paq ¸xl paq ď B ÿ aPK x l paq ď 1 @l " 1, . . . , Lx l paq ě 0 @a P K, l " 1, . . . , L.Therefore, FA MUL is transformed into a single-resource allocation problem FA MUL-F , with an extra multiplicative factor d in the competitive ratio.Recall that set T S t paq " tτ P tt ´st , . . . , t ´1u : a τ " au where s t " arg max s t ř t´1 τ "t´s 1pa τ " aq " N u consists of the most recent N rounds where arm a is sampled by exploration; and σ t paq " mints : s P T S t paqu is the 1-st element in T S t paq. Recall that ĉt paq "ř sPT S t paq C s paq N , rt paq " ř sPT S t paq R s paq Nare the average resource consumption and the reward earned for the most recent N pulls of arm a.Additionally, recall that we define xpqq t " tx pqq t paqu aPK as a solution to LPpr t , ĉt , η min ¨αq q (x pqqt being the optimal solution) for q " 0, 1, . . . , M ´1.We further define ct paq " ř sPT S t paq c s paq N , rt paq " ř sPT S t paq r s paq N as the average mean resource consumption and the reward earned for the most recent N pulls of arm a. Note that when condition (6) tpr s paq, c s paqqu aPK " tpr σtpaq paq, c σtpaq paqqu aPK , @s P tσ t , . . . , tu is satisfied for all a P K, then rounds s P tσ t , . . . , tu are on the same stationary piece and we have ct paq " c t paq, rt paq " r t paq. We let xpqq t " tx pqq t paqu aPK be a solution to LPpr t , c t , η min ¨αq q (x pqqt being the optimal solution) for q " 0, 1, . . . , M ´1. By Claim 3, we know that there exists q l P t0, 1, . . . , M u such that for all t P J l ,η min ¨αq l ´1 ă ř aPK c plq paqx l paq ďEQUATION)We show in the following Lemma B.3 that when condition ( 6) is satisfied for all a P K, our decisions have several nice properties which facilitate our proofs. Lemma B.3. Fix an arbitrary α P p0, 1s. For any t ě σ t paq, if tpr s paq, c s paqqu aPK " tpr σtpaq paq, c σtpaq paqqu aPK , @s P tσ t , . . . , tu,then with probability at least 1 ´2|K|δ, then all the following inequalities are satisfied for all t P J l : 1 ? α ¨řaPKEQUATIONProof of Lemma B.3. We defineϵ " d 3 N ¨ηmin log ˆ2 δ ˙ě max #d 3 N ¨ηmax log ˆ2 δ ˙, d 2 N ¨ηmin log ˆ2 δ ˙+ .Then by the multiplicative Azuma-Hoeffding inequality (Lemma B.1), for any a P K we have Prrp1 ´ϵqc t paq ď ĉt paq ď p1 `ϵqc t paqs ě 1 ´δ (19) Prrp1 ´ϵqr t paq ď rt paq ď p1 `ϵqr t paqs ě 1 ´δ.(20)The above probability bounds ( 19) and ( 20) hold sinceN ¨ηmin ď ÿ sPT S t paq c t paq, ÿ sPT S t paq r t paq ď N ¨ηmax .We set p1 ´3ϵq 2 " 1{α, and therefore N " 27 logp2{δq p1 ´1{ ? αq 2 ¨ηmin .Our following discussion is conditioned on the good event that both ( 19) and ( 20) hold for all a P K. This good event holds with probability 1 ´2|K|δ.Validating ( 16). Given that ( 19) and ( 20) hold, we have Given ( 25) and ( 26), we prove (17).1Validating (18). For l P L such that q l " 0, we have řPutting ( 27) and ( 30) together, we establish (18). . Therefore, the total rounds of forced exploration over the planning horizon can be upper bounded asT ÿ t"1 Y R t " T ÿ t"1 Y Rp1q t `Y Rp2q t " N ¨T ÿ t"1 Y Rp1q t ď N ¨T ÿ t"1 Z t .Since Z t are independent and Er ř T t"1 Z t s "ř T t"1 γ t ď 2T γ T , we can apply the Chernoff bound (which is a subcase of Lemma B.1) on Z t , Pr « T ÿ t"1 Z t ą 2T γ T `d6T γ T log ˆ2 δ ˙ff ă δ.Hence we have |T R T | "ř T t"1 Y R t ď 2T N γ T `N a6T γ T logp2{δq with probability at least 1´δ.Claim 5. Fix any δ P p0, 1q, | p T Ipmq | ď L|K| logp1{δqplogp|K|q `1q{γ T with probability at most 1 ´|K|Lδ.Proof of Claim 5. If round t is a change point, i.e., pr t , c t q ‰ pr t´1 , c t´1 q, we define set Kptq Ă K such that pr t paq, c t paqq ‰ pr t´1 paq, c t´1 paqq for all a P Kptq. Notice that after a change happens, some exploitation rounds could run with condition (6) violated, resulting in consuming resources from the wrong reward-consumption interval m. Hence, | p T Ipmq | can be upper bounded by the total number of exploitation rounds run before all arms are updated after each change point. After all arms are updated after a change point, ( 6) is satisfied again. In the following Claim 6, we suppose round t is a change point, and upper bound the number of exploitation rounds run before all arms a P Kptq are updated. Claim 6. Suppose round t is a change point. With probability 1 ´|Kptq|δ, IRES-CM run at most |K| logp1{δqplogp|Kptq|q `1q{γ T exploitation rounds (Algorithm 2, Lines 17-25) before updating the change in exploration rounds (Algorithm 2, Lines 9-13).Proof of Claim 6. For some set K 1 Ă K, let random variable Y pK 1 q denote the number of exploitation samples (i.e., line 6 of Algorithm 2 giving U ptq " 0) between two nearest exploration samples (i.e., line 6 of Algorithm 2 giving U ptq " 1) applied for arms a P K 1 . We denote Kptq pjq as the j-th arm explored from set Kptq. After each exploitation sample, IRES-CM runs for each q P t´M, . . . , M ´1u. Therefore, the number of exploitation rounds run before all a P Kptq are updated is 2M ¨pY pKptqq `ř|Kptq| j"2 Y pKptqz Ť j´1 h"1 Kptq phq qq. For any subset K 1 P Kptq, we further denote random variable ZpK 1 q as Y pK 1 q plus the number of times that exploration is triggered for any a P KzK 1 between two nearest exploration rounds applied for arms a P K 1 .It is evident that ZpK 1 q is a geometric random variable with time-varying probability p t " γ t |K 1 |{|K| of success in each round. Therefore, we have PrpZpK 1 q ě nq " ś t`n´1 s"t p1 ´ps q. Since for any x P r0, 1s, it holds that 1 ´x ď e ´x, by requiring e ´n¨p T ď δ, we have ś t`n´1 s"t p1 ´ps q ď p1 ´pT q n ď e ´n¨p T ď δ. In this case,e ´n¨p T ď δ ô ´n ¨pT ď ´logp1{δq ô n ě logp1{δq p T " |K| logp1{δq γ T |K 1 | .Therefore, we havePr ˆY pK 1 q ě |K| logp1{δq γ T |K 1 | ˙ď Pr ˆZpK 1 q ě |K| logp1{δq γ T |K 1 | ˙ď δ,which suggests that with probability at least δ, we run at most |K| logp1{δq{pγ T |K 1 |q exploitation rounds before updating pr t paq, ĉt paqq for each arm a P K 1 .EQUATIONInequality (31) holds sinceEQUATIONNotice that there are at most L change points over the entire planning horizon, contributing to p T Ipmq for at most 2M L|K| logp1{δqplogp|K|q `1q{γ T rounds, with probability at most 1 ´|K|Lδ.Combining Claim 4 and 5, with probability at least 1 ´2M |K|Lδ,ˇˇˇˇT R T ď ˜M´1 ď m"´M p T Ipmq ¸ˇˇˇˇď 2T N γ T `N d 6T γ T log ˆ2 δ ˙`4M 2 L|K| logp1{δqplogp|K|q `1q γ T ď4T N γ T `4M 2 L|K| logp1{δqplogp|K|q `1q γ T .Recall that N " 27 logp2{δq{pp1 ´1{αq 2 ¨ηmin q and γ t " M a |K| logp1{δqplogp|K|q `1q{EQUATION)Note that if the DM knows L a priori, then we can setγ t " M a L|K| logp1{δqplogp|K|q `1q{ ? N t, which results in |T R T Ť p Ť M ´1 m"´M p T Ipmq q| ď Õp a L|K|N T q. C Proofs C.1 Proof of Lemma 2.1Let π be a non-anticipatory feasible policy that achieves the expected optimum opt(DP) in DP, i.e. Er ř T t"1 ř aPK R t paqX π t paqs " Eropt(DP)s where X π t is the decision variable under algorithm π. We letx l paq " 1 t l ´tl´1 E « t l ÿ t"t l´1 `1 ÿ aPK X π t paqff for each l " 1, . . . , L in FA. We claim that tx l u L l"1 is feasible to FA, with objective value equal to Er ř T t"1 ř aPK R t paqX π t paqs " Eropt(DP)s, which indicates that under tx l u L l"1 we have opt(FA) ě Eropt(DP)s. 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 ř T t"1 ř aPK C t paqX π t paq ď B holds. Taking expectation over X π t paq and C t paq for t " t l´1 1, . . . , t l givesE « T ÿ t"1 ÿ aPK C t paqX π t paq ff " L ÿ l"1 t l ÿ t"t l´1 `1 ÿ aPK c plq paqErX π t paqs " L ÿ l"1 pt l ´tl´1 q ÿ aPK c plq paqx l paq ďB.Similarly, by taking expectation over each of the reward constraints, we haveEr ř T t"1 ř aPK R t paqX π t paqs "ř L l"1 pt l ´tl´1 q ř aPK r plq paqx l paq " Eropt(DP)s. Hence, the claim about the objective value is shown, and the Lemma is proved.C.2Recall that in Algorithm 1, we try each q P t0, 1, . . . , M u in a round-robin manner. Then we know that on each stationary piece l, for at least pt l ´tl´1 q{M ´1 rounds, we choose q " q l and take fractional decision x pq l ql such that ( 7) and ( 8) hold. By Claim 3 inequality (8), resources consumed under decision x pq l ql are assigned with resources reserved for intervals tmaxtm l ´1, ´M u, m l u. Therefore, for interval m where m l " m,EQUATIONC.4 Proof of Theorem 4.2Note that for reward-consumption ratio intervals n P t´M, . . . , M ´1u where T Ipnq " q T Ipnq , not all requests assigned to these intervals are necessarily satisfied. This is because resources could run out due to exploration before ř sP q T Ipnq C s pa s q ą B{p2M q ´1, i.e., whenT Ipnq č # t P T : t ÿ s"1 C s pa s q ď B ´1+ Ĺ T Ipnq č T .It can be seen that requests in rounds p Ť M ´1n"´M T Ipnq q Ş tt P T : ř t s"1 C s pa s q ď B ´1u are satisfied. Therefore, we decompose the ratio of the IRES-CM reward to opt(FA) as follows:ř tPT R t pa t q opt(FA) " ř tPp Ť M ´1 n"´M T Ipnq q Ş ttPT : ř t s"1 CspasqďB´1u ř aPK r t paqx pqtqt paq opt(FA) loooooooooooooooooooooooooooooooooooooooomoooooooooooooooooooooooooooooooooooooooon H(1) ¨řtPT R t pa t q ř tPp Ť M ´1 n"´M T Ipnq q Ş ttPT : ř t s"1 CspasqďB´1u ř aPK r t paqx pqtqt paq loooooooooooooooooooooooooooooooooooooooomoooooooooooooooooooooooooooooooooooooooon H(2).To establish Theorem 4.2, it suffices to show H(1) ě p1 ´op1qq ¨popt(FA) Óp a L|K|N T qq{p10α 4 M ¨opt(FA)q (see the forthcoming Section C.4.1) and H(2) ě 1 ´op1q (see the forthcoming Section C.4.2). paq P rα m plqt , α m plqt `1s. We defineJl " J l č # t P T : t ÿ s"1 C s pa s q ď B ´1+ .Then H(1) can be further decomposed as: EQUATIONInequality (47) holds since by summing over w P tmaxtm ´2, ´M u, . . . , mintm `2, M ´1uu, we repeat the numerator of (46) for at most 5 times.We partition set t´M, . . . , M ´1u into two disjoint sets M 1 , M 2 . An interval m P M 1 if for all n P tmaxtm ´1, ´M u, m, mintm `1, M ´1uu, we have T Ipnq " q T Ipnq , i.e. ř sP q T Ipnq C s pa s q ď B{p2M q ´1. An interval m P M 2 if for some n P tmaxtm ´1, ´M u, m, mintm `1, M ´1uu, we have T Ipnq Ĺ q T Ipnq . (53)Inequality (51) holds since ř M ´1 m"´M p:q pmq ď |T R T |. Inequality (52) is valid since ¨mintm`1,M´1u ď n"maxtm´1,´M u T Ipnq ‚č J l " ¨mintm`1,M´1u ď n"maxtm´1,´M u q T Ipnq ‚č J l " J l z ¨mintm`1,M´1u ď n"maxtm´1,´M u p T Ipnq ‚.Regarding m P M 2 . Suppose in some interval n P tmaxtm ´1, ´M u, . . . , mintm `1, M ´1uu, we have ř tP T Ip nq C s pa s q ą B{p2M q´1. We aim validate the following two inequalities respectively:EQUATIONEQUATIONSince given ( 54) and ( 55),for any interval m P M 2 ,EQUATION)Validating (55). For l P L such that q l " 0, by ( 18 ÿ tP Ť M ´1 m"´M T Ipmq R t pa t q P » - -¨1 ´g f f e 2 ř lPL ř tPp Ť M ´1 n"´M T Ipnq q Ş Jl ř aPK r t paqx pqtqt paq log ˆ2 δ ˙‹ ‚¨ÿ lPL ÿ tPp Ť M ´1 n"´M T Ipnq q Ş Jl ÿ aPK r t paqx pqtqt paq, ¨1 `g f f e 3 ř lPL ř tPp Ť M ´1 n"´M T Ipnq q Ş Jl ř aPK r t paqx pqtqt paq log ˆ2 δ ˙‹ ‚¨ÿ lPL ÿ tPp Ť M ´1 n"´M T Ipnq q Ş Jl ÿ aPK r t paqx pqtqt paq fi ffi fl " «˜1 ´d 2 H(1) ¨opt(FA) log ˆ2 δ ˙¸¨H(1) ¨opt(FA), ˜1 `d 3 H(1) ¨opt(FA) log ˆ2 δ ˙¸¨H(1) ¨opt(FA)ff .Since H(1) ¨opt(FA) ě p1 ´op1qq ¨popt(FA) ´Õp a L|K|N T qq{p10α 4 M q ě Ωpopt(FA)q ě Ωp a L|K|N T q. Then it is evident that H(2) ě 1 ´op1q with probability at least 1 ´δ.C.5 Proof of Lemma 2.3 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 K " t1u and a null , and instance n happen with probability p n . All instances have deterministic outcomes, and they share the same consumption model C t p1q " 1 for all t P T . Their reward functions are:Instance 1: R p1q p1q " ¨α´L , . . . , α ´L looooooomooooooonPiece 1, α ´L`1 , . . . , α Denote FA pnq as the FA for instance n P t1, . . . , Lu. It is clear that optpFA pnq q " Bα ´n. Recall X t p1q " 1pPull 1 in round tq. By the Yao's principle Yao (1977) , the competitive ratio of any online algorithm is at mostEQUATIONQuestion: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] Justification: We promise that our paper provides the full set of assumptions and a complete (and correct) proof. Due to the page limit, our proofs are mostly in appendix. In the main paper, we provide high-level ideas and sketch proofs of our claims, while pointing to the locations of formal proofs in 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 crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs 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 to 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. 
safeguards: 
 Question: 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 (e.g., pretrained language models, image generators, or scraped datasets)?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 a 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a 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 use existing assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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 package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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 not available online, the authors are encouraged to reach out to the asset's creators. 
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 of 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 is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
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 not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS 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. 
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 crowdsourcing nor research with human subjects.• 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. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_summary: The paper studies Bandits with Knapsacks in a piecewise-stationary environment, where the underlying reward can change over time. 
The 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.
strength_weakness: strength_weakness: 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} ))$. 
In 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.


Typos: 
1. Line 160: The DM does not L...
questions: 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: limitations: No limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: - The main part of the paper is too technical with many different notations, inline mathematical formulas, and not easy too follow. 
- The algorithm needs to know the loss and budget bounds in advances.
- 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)$. 
- 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$.
questions: questions: - I suggest the authors to address my limitations.
- The paper only considers piecewise stationarity, would it be possible to generalize it to smooth variations of losses and budget costs?

Typos: 
- p3, l117: $B^2/T$
- p5, l160: "The DM does not *know*"
limitations: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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?
questions: 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})$?
- 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: limitations: The authors have discussed the limitations as they claimed in the paper checklist.
paper_summary: paper_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.
strength_weakness: strength_weakness: See questions.
questions: 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: limitations: n.a.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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))?
2. 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?
3. 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?
4. 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$?
5. 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),

[1] Ball, Michael O., and Maurice Queyranne. "Toward robust revenue management: Competitive analysis of online booking." Operations Research 57.4 (2009): 950-963.
limitations: limitations: N/A

Comments: title: Numerical experiments regarding Zhou et al.'s algorithm and the bandit learning setting
More on improving the computational overhead
General response to the comment by Reviewer BBCY
Demonstrating why knowing $\eta_{\min}$ is necessary
Regarding "Questions"
Response to "Questions"
comment: Dear reviewer, pardon our late supplementation. We would like to provide some numerical results regarding the Zhou et al. and the bandit setting that you mentioned.

We present a two-piece stationary illustrative case here. We let the rewards and resource consumption in all rounds be uniformly distributed within a $[-0.2,+0.2]$ range regarding their mean values. We let $B=9360$ and $T=20000$ as in our original manuscript. We remark that Zhou et al. require observing $(R_t, C_t)$ in each round before making decisions, which is a way too strong requirement. Hence, we assume that Zhou et al. observe $(r_t, c_t)$ instead of $(R_t, C_t)$ before making decisions in each round, which is still a stronger assumption than the bandit setting considered by us and Immorlica et al. 

In the following tables, we take the average rewards over 10 experiments for each algorithm and present the cumulative rewards in a multiple of every 1000 rounds.

We first consider the $(r_t, c_t)$ values in our original manuscript, where we let $r^{(1)}(1)=r^{(1)}(2)=0.5, c^{(1)}(1)=c^{(1)}(2)=1$, $r^{(2)}(1)=1, r^{(2)}(2)=0.5, c^{(2)}(1)=0.5, c^{(2)}(2)=1$. In this case, the optimal solution of the benchmark FA chooses a single arm on each stationary piece, and Zhou el al. outperform both Immorlica et al. and our IRES-CM.

| t                | 1000   | 2000   | 3000    | 4000    | 5000    | 6000    | 7000    | 8000    | 9000    | 10000   | 11000   | 12000   | 13000   | 14000   | 15000   | 16000   | 17000   | 18000   | 19000   | 20000   |
|------------------|--------|--------|---------|---------|---------|---------|---------|---------|---------|---------|---------|---------|---------|---------|---------|---------|---------|---------|---------|---------|
| Immorlica et al. | 409.42 | 668.89 | 868.46  | 959.76  | 1004.28 | 1047.26 | 1081.50 | 1338.21 | 1379.11 | 1415.21 | 1486.26 | 1556.22 | 1611.23 | 1680.19 | 1743.14 | 1810.03 | 1873.71 | 1938.27 | 2001.66 | 2066.87 |
| Zhou et al.      | 498.39 | 998.42 | 1499.79 | 1998.63 | 2100.68 | 2100.68 | 2100.68 | 2100.68 | 2100.68 | 2100.68 | 3100.24 | 4099.27 | 5098.96 | 6096.99 | 7099.31 | 8099.78 | 9025.09 | 9025.09 | 9025.09 | 9025.09 |
| IRES-CM          | 468.43 | 866.61 | 1294.79 | 1680.58 | 2060.31 | 2471.52 | 2863.14 | 3252.99 | 3544.64 | 3647.43 | 4580.54 | 5579.57 | 6433.62 | 7148.54 | 7148.54 | 7148.54 | 7148.54 | 7148.54 | 7148.54 | 7148.54 |

We next consider a case with a slight change on $(r_t, c_t)$ on the second stationary piece. Specifically, we let $r^{(1)}(1)=r^{(1)}(2)=0.5, c^{(1)}(1)=c^{(1)}(2)=1$, $r^{(2)}(1)=0.5, r^{(2)}(2)=1, c^{(2)}(1)=0.5, c^{(2)}(2)=1$. In this case, the optimal solution of the benchmark FA chooses a distribution over arms on the second stationary piece, where $x^*_{2}(1)=0.128, x^*_{2}(2)=0.872$. As shown, in this case our IRES-CM outperforms both Immorlica et al. and Zhou et al. This is consistent with the theoretical results that Zhou et al. achieve sub-optimal rewards compared with a **best distribution over arms** benchmark.

| t                | 1000   | 2000   | 3000    | 4000    | 5000    | 6000    | 7000    | 8000    | 9000    | 10000   | 11000   | 12000   | 13000   | 14000   | 15000   | 16000   | 17000   | 18000   | 19000   | 20000   |
|------------------|--------|--------|---------|---------|---------|---------|---------|---------|---------|---------|---------|---------|---------|---------|---------|---------|---------|---------|---------|---------|
| Immorlica et al. | 434.69 | 656.97 | 909.24  | 943.53  | 988.01  | 1030.39 | 1064.42 | 1101.87 | 1144.65 | 1181.05 | 1248.60 | 1314.08 | 1372.59 | 1437.17 | 1508.36 | 1572.78 | 1631.64 | 1691.74 | 1751.38 | 1826.37 |
| Zhou et al.      | 494.79 | 988.91 | 1488.38 | 1990.28 | 2444.41 | 2444.41 | 2444.41 | 2444.41 | 2444.41 | 2444.41 | 3442.66 | 4442.90 | 4465.25 | 4465.25 | 4465.25 | 4465.25 | 4465.25 | 4465.25 | 4465.25 | 4465.25 |
| IRES-CM          | 442.14 | 850.82 | 1273.24 | 1721.91 | 2186.27 | 2636.42 | 3049.17 | 3467.15 | 3884.67 | 4339.88 | 4772.74 | 5021.60 | 5021.60 | 5021.60 | 5021.60 | 5021.60 | 5021.60 | 5021.60 | 5021.60 | 5021.60 |

We believe the above results further validates the strength of our algorithm. We will supplement the figure format results of the above case and more large-scale cases in our revision. We hope this supplementation further addresses your concern, and thank you for your valuable comments!
(We apologize for writing $\hat{r}, \hat{c}$ as $r,c$ in this comment. Complicated math notation cannot show well.)

Pardon our supplement discussion. In fact, the computational load of our algorithm can be easily reduced to solving no more than $1$ LP per iteration. Instead of solving LP$(r_t, c_t, \eta_{\min} \cdot \alpha^{q})$ for all $q \in${$0,1, \ldots, M-1$} in each round (line 6 of Algorithm 2), we can solve a single LP$(r_t, c_t,\eta_{\min} \cdot \alpha^{q_t})$ after deciding the $q_t$ value in line 16. By doing so, we retain the same performance guarantee as the original manuscript.

In our original manuscript (and our rebuttal), we didn't write down Algorithm 2 in the most computationally efficient way. Since we mainly focused on illustrating the learning process naturally, we chose to present Algorithm 2 in a way that shows how it naturally generalizes from Algorithm 1. In the deterministic outcome setting (Algorithm 1), we solve $M+1$ LPs for each stationary piece. Then in the bandit setting (Algorithm 2), we largely keep the structure of Algorithm 1 for the purpose of demonstrating the main ideas. However, after running more experiments on problems with larger scales, we find that the aforementioned modification significantly enhanced our algorithm's efficiency. Therefore, we think it's better to implement our algorithm more efficiently. We will revise the manuscript so that Algorithm 2 solves no more than $1$ LP per iteration. We will also supplement more experiments with larger scales in our revised manuscript. 

Thank you so much for your valuable advice on computational overhead!
Thanks for these detailed explanations. As I am unfamiliar with this topic, it is hard for me to evaluate the value of this job and I prefer to keep my score.
Thank you for your understanding and for increasing the score; we appreciate your thoughtful consideration of the challenges involved. All the best to you!
Thank you for your detailed response. I understand know the difficulties better and increase my score to 6. All the best.
Thank you for the feedback! We will surely add more theoretical results to support our revision, and we will also add more discussions distinguishing our work from existing literature that you kindly mentioned. If granted an additional page in the main text, we plan to incorporate the numerical results currently in the appendix, and add further numerical experiments and discussions in the next iteration. At present, we have maximized our page limit to effectively present our results and novel ideas, so we put the numerical results in the appendix.
I would like to thank the authors for the very detailed response. My concerns have been moderately addressed and thus I have raised my score. While I very much appreciate authors' efforts and clarifications, I think the paper may require a significant re-structure by adding more results (theoretical & numerical) and discussions in the next iteration.
We appreciate the reviewer’s insightful and pointed concerns. Please allow us to address them further.

Regarding the requirement on the knowledge of the reward and resource ranges, unfortunately, it is necessary. While it is possible to derive a worse bound without $\eta_{\max}$ by setting it to its upper bound of 1, knowing the lower bound is essential for our algorithm's functionality. We have provided a case with some light proof in the comment above this one to show that, to achieve a near-optimal CR, it is indeed a necessary condition to know $\eta_{\min}$. To our knowledge, existing literature that derives near-optimal performance bounds with respect to $\eta_{\max}/\eta_{\min}$ typically requires knowledge of both $\eta_{\min}$ and $\eta_{\max}$ (Zhou et al., 2008; Im et al., 2021; Zeynali et al., 2021). Thus, we believe this assumption is reasonable. 

Regarding the analysis in Section 3.2, our algorithm aims to perform two tasks: (i) ensuring at least one out of every $M+1$ guesses on the reward-consumption ratio is accurate for each stationary time segment; (ii) allocating sufficient resources for each reward-consumption ratio interval (interval for short), to establish a near-optimal CR. Our algorithm IRES guarantees a interval-wise $O(M)$ CR. To attain this, we focus on two scenarios: intervals where the reserved resources are depleted before the end of the horizon (Claim 2, see Line 199) and intervals where the reserved resources are not fully consumed until the end (Claim 1, see Line 197). The interval-wise CR naturally leads to the overall CR result.

For Claim 1, we need the total number of stationary pieces where $t_{l} - t_{l-1} \leq M$ to be at most $o(T)$. Thus we cannot set $L=T/B$ even in the deterministic setting. We have clarified Theorem 3.2’s dependence on $L$ in the revised manuscript and removed Lemma 2.3. Our original mentality behind providing Lemma 2.3 is that we find a CR lower bound which is better than Immorlica et al. (2019) w.r.t. $T$, but we indeed fail to keep it aligned with our assumptions. Thank you very much for pointing this out! We could potentially make Theorem 3.2 stands when $L=O(T)$ by modifying the algorithm to draw $q$ (see line 5 of Algorithm 1) in a randomized manner (instead of a round-robin manner). However, we agree with you that this is only applicable in the full-feedback setting. 

Despite the limitation behind Lemma 2.3, we highlight that its proof (see Appendix C.5) still provides a valid CR lower bound of $\Omega(L)$, which applies to any legit $L$ values. In the proof of Theorem 4.5 (Appendix C.6), we essentially show that $L$ can be no larger than $\log(\eta_{\max}/\eta_{\min})$ in our constructed instance, leading to a matching CR lower bound to our performance guarantee. We will revise these proofs to clearly present the lower bound for all valid $L$ values. We hope this addresses your concern regarding the CR lower bound.

We further remark that demonstrating Claim 1 and Claim 2 involves a judicious analysis on the rewards gained on each stationary piece and the rewards gained for each ratio interval, which depend heavily on the resource consumption status for each interval. Hence, the somewhat complex analysis involving the term $\tilde{\mathcal{T}}^{(m)}$ (defined in Section 3.3) is necessary. We understand and share the concern about making the intuitions clear (as our paper is technical and highly unconventional). Thus, we strive to shed light on our analysis by providing a high-level overview and intuition in Section 2.3 (pages 3-4), making our contributions more accessible. We have also revised Theorem 3.2 to clearly show the dependence on $L$.

To conclude our comments: 

1. Knowing $\eta_{\min}, \eta_{\max}$ beforehand is a necessary condition for any non-anticipatory algorithm to achieve a CR of $O(\log(\eta_{\max}/\eta_{\min})), but we believe it is a mild assumption since it is assumed in relevant papers. We will clearly point out this limitation in Section 2.2.

2. Our Lemma 2.3 of setting $L=T/B$ is not aligned with our assumption, yet we do provide a CR lower bound for all legit $L$. 

3. While the notation in our analysis are unavoidable, we will ensure that the dependence on $L$ is clearly highlighted in Theorem 3.2.

We hope this addresses all your concerns. Despite the limitations, we believe our paper is novel and makes significant advances over existing works.

References

[1] Im, S., Kumar, R., Montazer Qaem, M., & Purohit, M. (2021). Online knapsack with frequency predictions. Advances in neural information processing systems, 34, 2733-2743.

[2] Zeynali, A., Sun, B., Hajiesmaili, M., & Wierman, A. (2021, May). Data-driven competitive algorithms for online knapsack and set cover. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 35, No. 12, pp. 10833-10841).
To show that it is necessary to know $\eta_{\min}$, we let the DM be provided with a lower range $<\eta_{\min}$ (a looser range), and show that it leads to sub-optimal CR. We first construct a general case with $N+1$ instances when $\eta_{\min} = \beta^{-N}$ for some absolute constant $\beta >1$. We consider $N+1$ instances with two arms $\mathcal{K}= \{1\}$ and $a_{\text{null}}$, and instance $n$ happen with probability $p_n$. All instances have deterministic outcomes, and they share the same reward model $R_t(1) = 1$ for all $t$. Their consumption functions are:

$\text{Instance $1$: }C^{(1)}(1)= \left(\underbrace{1, \ldots, 1}_{B\text{ rounds}}\right)$

$\text{Instance $2$: }C^{(2)}(1)= (\underbrace{1, \ldots, 1},\underbrace{1/\beta, \ldots, 1/\beta}_{B \cdot \beta\text{ rounds}})$

$\text{Instance $3$: }C^{(3)}(1)= \left(\underbrace{1, \ldots, 1}, \underbrace{1/\beta, \ldots, 1/\beta}, \underbrace{1/\beta^2, \ldots, 1/\beta^2}_{B \cdot \beta^2\text{ rounds}}\right)$

$\ldots$

$\text{Instance }N: C^{(N)}(1)=  \left(\underbrace{1, \ldots, 1}, \underbrace{1/\beta, \ldots, 1/\beta}, \ldots, \underbrace{1/\beta^{N-1}, \ldots, 1/\beta^{N-1}}_{B \cdot \beta^{N-1}\text{ rounds}}\right)$

$\text{Instance }N+1: C^{(N+1)}(1)=  \left(\underbrace{1, \ldots, 1}, \underbrace{1/\beta, \ldots, 1/\beta}, \ldots, \underbrace{1/\beta^{N-1}, \ldots, 1/\beta^{N-1}}, \underbrace{1/\beta^{N}, \ldots, 1/\beta^{N}}_{B \cdot \beta^{N}\text{ rounds}}\right).$

(We are sorry that the subfixes for the underbraces cannot show properly in this bubble. In any instance, the $n$-th stationary piece has a length of $B \cdot \beta^{n-1}$ rounds.) 

Through a similar analysis to the proof of Lemma 2.3, we can derive a CR lower bound of $N(1-1/\beta)+1/\beta$ using the instance family above. In the following CR expressions, we omit coefficient regarding $1/\beta$ as they are constants. For example, we write CR$=N(1-1/\beta)+1/\beta$ simply as CR$=\Theta(N)$. When the DM is provided with information $\eta_{\min} = \beta^{-N}$ for any $N \in \mathbb{N}$, a CR lower bound is derived based on $N+1$ instances as constructed above.

We suppose the real $\eta_{\min} = \min_{t,a} \frac{r_t(a)}{c_t(a)} = \beta^{-\Lambda}$, $\eta_{\max} = \max_{t,a} \frac{r_t(a)}{c_t(a)} = 1$, but the DM only has weak prior information that 

$\tilde{\eta}_{\min}=\beta^{- \kappa \cdot \Lambda}$ 

($\kappa>1$ can be set to be arbitrarily large) and $\eta_{\max} = 1$. Then from the DM's point of view, the optimal CR she/he could derive is CR$=\Theta(\kappa \cdot \Lambda)$, while from the perspective of who knows the real $\eta_{\min} = \beta^{-\Lambda}$, the optimal CR should be $\Theta(\Lambda)$. 

We first show that given the loose lower range $\beta^{- \kappa \cdot \Lambda}$, the DM will not benefit from tightening the value ranges by blindly guessing a value of $\eta_{\min}$. We suppose the DM tightens the value range to $[\beta^{-(\kappa \cdot \Lambda - d)}, 1]$ for some $d \geq 1$, without knowing the real $\eta_{\min}$. Then he/she derives a CR lower bound with $N +1= \kappa \cdot \Lambda - d+1$ instances based on the above construction. Then the DM can expect to achieve a total reward of $\Theta(B \cdot \beta^{\kappa \cdot \Lambda-d}/(\kappa \cdot \Lambda-d))$ (similar analysis with proof of Theorem 2.3). However, since the DM does not know the real $\eta_{\min}$, it is possible that in fact $\eta_{\min} = \beta^{- \kappa \cdot \Lambda}$. In this case, the optimal reward can be as large as $\Omega(B \cdot \beta^{\kappa \cdot \Lambda})$ if $N = \kappa \cdot \Lambda$. Hence, from the DM's perspective, she/he could achieve a sub-optimal CR of $\Theta(\beta^d \cdot (\kappa \cdot \Lambda-d))$ if she/he blindly assume $\eta_{\min} = \beta^{-(\kappa \cdot \Lambda - d)}$, which is significantly worse than the optimal CR$=\Theta(\kappa \cdot \Lambda)$. 

Therefore, the DM must derive a CR on the full range $[\beta^{\kappa \cdot \Lambda},1]$, which involves $N+1=\kappa \cdot \Lambda+1$ instances as constructed above. Therefore the DM expects a reward of $\Theta(B \cdot \beta^{\kappa \cdot \Lambda}/(\kappa \cdot \Lambda))$ when there are indeed $N+1 =\kappa \cdot \Lambda+1$ instances. However, since in fact there are only $\Lambda+1$ instances, the DM wastes all her/his resources reserved for instance $\Lambda+2, \ldots, \kappa \cdot \Lambda+1$ and she/he can only achieve a reward of $O(B \cdot \beta^{\Lambda}/(\kappa \cdot \Lambda))$. Compared with the actual optimal reward $\Omega(B \cdot \beta^{\Lambda})$ with $\Lambda+1$ instances, the DM achieves a sub-optimal CR of $\Omega(\kappa \cdot \Lambda)$. Since $\kappa$ can be arbitrarily large, the CR derived without correct knowledge of $\eta_{\min}$ is significantly worse than the optimal CR$=\Theta(\Lambda)$.
Thank you for your response. This addresses some of the points I raised.

> 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.

This was actually what I meant by my point. Is is possible to not require the knowledge of the reward and ressource ranges?

> 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$.

Thank you. I understand better but this is still unfortunate to have the result for the full-information feedback only. Wouldn't it be possible to have a lower-bound for any fixed value L?
Additionally, after revisiting Theorem 3.2, I realize that the paper is indeed quite challenging to engage and the analysis of Thm. 3.2 hard to follow. It's also unclear to me how the dependence on  $L$ is reflected in the result.
4. "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$?"

Response: Thank you for the insightful concern. We do not yet know what is the minimal decrease in competitive ratio in exchange for a sublinear-in-$T$ regret. We choose a simpler way to explore so that we do not need to detect the exact change points. There could potentially be more refined exploration approaches that lead to better coefficients in the competitive ratio, while maintaining a worse regret. We will keep exploring in our future research. Regarding $\alpha$, it can be set as any constant $> 1$, such as $2$ or $e$.

5. "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)."

Response: Thanks for the reviewer’s comment! Given that our paper is primarily theoretical, we conduct only demonstrative experiments on smaller datasets. We clarify that our experiments focus on a bandit feedback setting, which indeed involves a learning problem. The underlying rewards and resource consumption are set to be deterministic for convenience, but the algorithm does not know they are deterministic. We apologize for the misleading typo in line 632 where "known" should have been "unknown", and we have correct it. Hence we believe comparing our proposed IRES-CM and the existing benchmark by Immorlica et al. (2019) is appropriate. We will provide a study on the full feedback setting, and compare with Zhou et al. (2008) which only works with full feedback. This supplements our main study with bandit feedback.

Finally, we sincerely thank the reviewer for the careful inspection and insightful concerns! Your suggestions have significantly helped us improve the quality of our paper. We genuinely hope you could re-evaluate our contributions given our clarifications. We are happy and open to any further discussion.
3. “In the online matching part, the algorithm design is not entirely novel.... 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?”

Response: We appreciate the reviewer’s comment, but we argue that it is not accurate to say our inventory reserving idea is a deterministic version of other works such as Immorlica et al. (2019). While some papers consider different inventory reservation strategies, ours offers a novel perspective on the problem, and its simplicity and intuitiveness enhance our contribution. Our approach splits the reward into two terms: the reward-consumption ratio multiplied by the resource consumption on each stationary piece $l$ (see Section 2.3). By reserving a certain amount of inventory for each ratio interval, our task simplifies to guessing the optimal reward-consumption ratio interval in each round. Our idea and corresponding strategy are crucially different from existing literature. Moreover, the technical details of our proofs are not at all similar with any existing paper.

Immorlica et al. (2019)’s inventory reservation strategy depends solely on the cumulated reward (see the definition of their $\hat{g}$ in Algorithm 3), 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.  Ball and Queyranne (2009) study a rather restrictive setting with two customer classes, prior knowledge of each class's fare, and fixed resource consumption of $1$. This is a very simple setting, which allows them to consider a strategy depending only on the ratio between each fare class. If our strategy is perceived as a similar version of existing methods, then by that logic, all inventory reservation strategies could be viewed as fundamentally similar.

We do agree that our algorithm is not as adaptive as some best-of-both-world algorithms, but it does provide a near-optimal competitive ratio in our non-stationarity setting. Although the process of guessing ratio intervals via LPs in a round-robin manner may seem primitive, it leaves room for further refinement which may lead to less resource waste. Our experiments show that although our algorithm wastes some resources, it is less conservative in inventory reservation compared to Immorlica et al. (2019)’s adversarial algorithm, leading to better performance in our piecewise-stationary setting. We also believe that our piecewise-stationary setting is more realistic than stationary/adversarial/non-stationary with bounded global variation settings in practice, and thus worth studying. 

To sum up, given that we introduce a novel and intuitive perspective of the piecewise-stationary Bwk, develops new inventory reservation algorithms and proof techniques, and achieves a near-optimal performance guarantee (compared to the best distribution over arms dynamic benchmark), we believe our contribution is solid.
2. “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?”

Response: When we mention “while existing adversarial BwK literature focus on the stationary benchmark,” we are focusing solely on research works that consider the **bandit feedback** setting. That is, the DM only observes the outcomes $(R_t(A_t), C_t(A_t))$ **after** pulling arm $A_t$, which is studied in our Section 4. The bandit feedback setting is more stringent than the **full feedback setting** in online matching, which require observing the actual values of $(R_t(a), C_t(a))$ for all $a \in \mathcal{K}$ **before** choosing $A_t$. 

Our intuitive discussions in Section 3 has the same full feedback setting as online matching papers (which certainly resonates with your comment), for example [Karp et al. (1990), Mehta et al. (2007), Zhou et al. (2008)], which crucially require knowing $(R_t(a), C_t(a))$ in crafting their potential function [Mehta et al. (2007), Zhou et al. (2008)], or algorithm gadget [Karp et al. (1990)], which cannot be readily generalized to the bandit setting. By contrast, we take a different approach in algorithm design in Section 3, which circumvent the difficulty is transiting from full feedback to bandit feedback setting. The natural generalization from full to bandit feedback shown in Section 4 is one of our core contributions. To this end, we emphasize that bandit feedback does hinder optimization, as illustrated by how the regret term in the bandit setting (Theorem 4.2) degrades with an increasing $L$, the number of change points.

Regarding the benchmark considered by Zhou et al. (2008), it is indeed dynamic. However, it is a **best single arm** benchmark allowing pulling a single arm in each round; while our opt(FA) is a **best distribution over arms** benchmark. In fact, in the bandit-feedback stationary outcome setting, Badanidiyuru et al. (2018) consider a best distribution over arms benchmark, which is similar with our opt(FA). They show, in their Appendix A, that it requires optimizing over the set of probability distributions on the $K$ arms to get the optimal regret, while pulling a best single arm yields significantly worse regret (which could noticably affect the achievable CR). It is not hard to show that in the picewise-stationary setting, this is also the case. Thus, our benchmark is **strictly stronger** than Zhou et al. (2008).

To conclude, our benchmark is strictly stronger than Zhou et al. (2008) and we consider a more difficult setting than online matching in Section 4. We appreciate the reviewer’s comment and will cite and compare with the online matching literature in our revised manuscript.

Reference

[1] Karp, Vazirani, Vazirani, An Optimal Algorithm for On-line Bipartite Matching, STOC 1990

[2] Mehta, Saberi, Vazirani, Vazirani, AdWords and Generalized On-line Matching, JACM 2007

[3] Badanidiyuru, A., Kleinberg, R., & Slivkins, A. (2018). Bandits with knapsacks. Journal of the ACM (JACM), 65(3), 1-55.
(We apologize for the weird section division in this part. Otherwise the math notation do not show correctly.)

1. "In line 5 of algorithm 1, why using $\eta_{\min}\cdot\alpha^q$ with restricting $q \in${$0,1,\ldots,M−1$} to guess $B_l ^{\star} /(t_l-t_{l-1})$?"

Response: We are sorry that there is a typo in line 5 of Algorithm 1. It should be “solve $\text{LP}(r^{(l)}, c^{(l)},\eta_{\min} \cdot \alpha^q)$ $\forall q \in${$0,1,\ldots,M$}” instead of solving for $q \in${$0,1,\ldots,M−1$}. We will correct this typo. Rest asured that the algorithm description and proofs are all correct regarding the value range of $q$. We next explain why we use $\eta_{\min}⋅\alpha^q$ with restricting $q \in${$0,1,\ldots,M$} to guess $B_l ^{\star} /(t_l-t_{l-1})$.

Recall from Section 2.1 that $r^{(l)}(a), c^{(l)}(a) \in [\eta_{\min}, \eta_{\max}]$ for all $l, a$, and recall from Section 2.3 that we define the set $\mathcal{L} = ${$l \in ${$1, \ldots, L$}: $\sum_{a \in \mathcal{K}} x_l^{\star}(a) > 0$}. Then we have $\sum_{a \in \mathcal{K}} c^{(l)}(a) x_l^{(q)\star}(a) \in [\eta_{\min}, \eta_{\max}]$ since $0<\sum _{a \in \mathcal{K}} x^{(q)\star}_l(a) \leq 1$ for all $l \in \mathcal{L}$. 

This further indicates that $B_l ^{\star} /(t_l-t_{l-1}) \in [\eta_{\min}, \eta_{\max}]$. Plugging in $q \in${$0,1,\ldots,M$}, we essentially use $M+1$ intervals $[\eta_{\min}, \eta_{\min} \cdot \alpha],  (\eta_{\min} \cdot \alpha, \eta_{\min} \cdot \alpha^2], \ldots, (\eta_{\min} \cdot \alpha^{M-1}, \eta_{\max}]$ to cover $[\eta_{\min}, \eta_{\max}]$ and guess which interval $B_l ^{\star} /(t_l-t_{l-1})$ falls into. 

In Claim 3 (see Appendix B.3 on page 12), we show that the round-robin technique in IRES ensures that, on each stationary piece $l$, $x_l^{(q)\star}$ (optimal solution to $\text{LP}(r^{(l)}, c^{(l)},\eta_{\min} \cdot \alpha^q)$) for at least one $q \in${$0,1,\ldots,M$} is close to the $x^{\star}_l$ (optimal solution to FA) in terms of both the resource consumption and the reward-consumption ratio. Recall that we denote $m^{\star}_l \in ${$-M,\ldots, M-1$} as the interval such that $\text{Ratio}^{(l) \star} \in (\alpha^{m^{\star}_l}, \alpha^{m^{\star}_l+1}]$, and we denote $m_t \in ${$-M, \ldots, M-1$} such that $\text{Ratio}_l^{(q_t)} \in (\alpha^{m_t},\alpha^{m_t+1}]$. 

Then Claim 3 leads to the important result that for all $l$, in at least $1/(M+1)$ fraction of rounds $t \in ${$t_{l-1}+1, \ldots, t_l$}, we have $m_t \in ${$m^{\star}_l-1,m^{\star}_l$}. 

To conclude, by guessing a $q$ such that $\eta_{\min} \cdot \alpha^q$ is within a factor of $\alpha$ from $B_l^{\star}/(t_l - t_{l-1})$ (which happens in at least $1/(M+1)$ fraction of rounds), we also have $\text{Ratio}_l ^{(q)} $ to be at most a factor of $\alpha$ from $\text{Ratio}^{(l)\star}$. Therefore, for at least $1/(M+1)$ fraction of rounds, we have the correct guess of the reward-consumption ratio interval on each stationary piece.

2. "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?"

Response: Yes, the reviewer’s point is correct. If opt(FA) is close to $\tilde{O}(L\sqrt{|\mathcal{K}|NT})$, then the bound in Theorem 4.2 will be close to zero. Unfortunately, this order of loss is unavoidable in bandit problems. In stationary unconstrained MAB, the optimal regret is $\tilde{O}(\sqrt{|\mathcal{K}|T})$; in piecewise-stationary unconstrained MAB, the optimal regret is $\tilde{O}(\sqrt{L|\mathcal{K}|T})$. We emphasize that even the theoretical regret exceeds the optimal reward, these results, as well as our result, are still meaningful from the following aspects: (1) The performance bound serves as a measure of how well our algorithm performs relative to the best possible strategy. Even if the theoretical regret exceeds the optimal reward, the bound indicates that our algorithm's regret grows sub-linearly with time $T$; (2) The bound provides a worst-case scenario guarantee, reassuring users that the algorithm won't perform significantly worse than the optimal strategy, even in less favorable conditions; (3) The regret bound provides a theoretical guarantee that the performance will remain within certain limits, offering confidence in the algorithm's consistency and reliability.

Finally, we thank the reviewer for the thoughtful feedback, which has significantly helped us improve our paper. We are happy and open to discussing any further questions.
Regarding "Questions": We appreciate your question on how our algorithm monitors changes in rewards and resource consumption without a restarting mechanism. The key is that we decompose the reward 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 comment may not show well). 
\begin{equation}
\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.
\end{equation}
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. 

In the full-feedback deterministic outcome setting (Algorithm 1 on page 5),
\begin{equation}
\text{Ratio}^{(q)} := \frac{\sum_{a \in K} r^{(l)}(a) x_l^{(q) \star}(a)}{\sum_{a \in K} c^{(l)}(a) x_l^{(q)\star}(a)},
\end{equation}
which is a guess of $\text{Ratio}^{(l)\star}$, is observable for each $q$. Then it suffices to check the ratio interval that $\text{Ratio}_{l}^{(q)}$ belongs to.

In the bandit-feedback stochastic outcome setting, we only need an additional estimate on $(r_t(a), c_t(a))$ to ensure the estimated $Ratio^{(l)\star}$  falls within the correct interval. This is achieved through random sampling rounds, termed "exploration rounds" (see Lines 7-13 in Algorithm 2). Specifically, in each round $t$, we conduct sampling with probability $\gamma_t$, where we uniformly at random choose an arm $a \in \mathcal{K}$ and pull it for $N$ times (see equation (5) on page 7). Then we update $(\hat{r}_t(a), \hat{c}_t(a))$, which is an estimate on $(r_t(a), c_t(a))$, as in equation (5) on page 7. We then guess $\text{Ratio}^{(l)\star}$ based on $(\hat{r}_t(a), \hat{c}_t(a))$. 

We highlight that the major performance difference between IRES and IRES-CM is the loss caused by estimating $(r_t,c_t)$, reflected in the following aspects: (i) reward loss caused by exploration rounds; (ii) the most recent exploration rounds contain change points, causing failed estimation of $(r_t, c_t)$; (iii) the most recent exploration rounds do not contain change points, but there is a large discrepancy between $(r_t,c_t)$ and $(\hat{r}_t,\hat{c}_t)$ (due to untimely update). 

The performance guarantee of our algorithms is in the form of $\sum^T_{t=1} R_t(a_t)\geq \frac{1}{\text{CR}}\cdot \text{opt}(\text{FA}) - \text{Reg}$. In Appendix B.7 & C.4, we respectively prove that the losses due to (i, ii) are accounted for in Reg, while (iii) is accounted for in the CR, with high probability. 

In the full-feedback deterministic outcome setting, our performance guarantee holds as long as $L=o(T)$. Nevertheless, in the bandit-feedback stochastic outcome setting, $L$ shows up in Reg$=\tilde{O}(L \sqrt{|\mathcal{K}|NT})$ (or Reg=$\tilde{O}(\sqrt{L|\mathcal{K}|NT})$ when $L$ is known) (see Theorem 4.2 on page 8). Reg is a sublinear-in-$T$ reward loss, provided $L=o(\sqrt{\eta_{\min}T})$ (or $L=o(\eta_{\min}T)$ when $L$ is known). While our sampling process is effective, we acknowledge that it could potentially be complemented or replaced by other change point monitoring algorithms.

We finally remark that our algorithm design does not need to detect the exact change points, but our sampling (exploration rounds) works primarily due to the piecewise-stationary nature. The intuition is that, given the presence of resource constraints, identifying the change point is not enough, different from the unconstrained setting. Indeed, even in the simple case when we know there is only one change point occurring at $t=T/2$, the DM still needs to estimate how many resource units are consumed in the first piece $\{1, \ldots, T/2\}$ and in the second piece $\{T/2 + 1, \ldots, T\}$ in the optimal solution. This means that, during $\{1, \ldots, T/2\}$, the DM shall need some form of knowledge on the mean outcome in the second piece. Such a need is different from the setting without resource constraint, where the DM can achieves a SOTA regret bound by restarting the standard UCB at $t=T/2$. This explains why we do not have a detect-restart mechanism frequently used in unconstrained cases, but we discover that our sampling strategy is better suited for the resource constrained setting.

We thank the reviewer for the valuable comments, and we have corrected the typos. We hope we have clarified all your concerns, and we hope you will consider re-evaluating our contributions after the clarification. We are happy and open to discussing any further questions.