Non-stationary Bandits with Knapsacks
Authors: Shang Liu
Jiashuo Jiang
Xiaocheng Li
Venue: NeurIPS 2022 Accept (2022)
Keywords: Bandits with knapsacks
linear program
non-stationarity
UCB

Abstract: In this paper, we study the problem of bandits with knapsacks (BwK) in a non-stationary environment. The BwK problem generalizes the multi-arm bandit (MAB) problem to model the resource consumption associated with playing each arm. At each time, the decision maker/player chooses to play an arm, and s/he will receive a reward and consume certain amount of resource from each of the multiple resource types. The objective is to maximize the cumulative reward over a finite horizon subject to some knapsack constraints on the resources. Existing works study the BwK problem under either a stochastic or adversarial environment. Our paper considers a non-stationary environment which continuously interpolates between these two extremes. We first show that the traditional notion of variation budget is insufficient to characterize the non-stationarity of the BwK problem for a sublinear regret due to the presence of the constraints, and then we propose a new notion of global non-stationarity measure. We employ both non-stationarity measures to derive upper and lower bounds for the problem. Our results are based on a primal-dual analysis of the underlying linear programs and highlight the interplay between the constraints and the non-stationarity. Finally, we also extend the non-stationarity measure to the problem of online convex optimization with constraints and obtain new regret bounds accordingly. 

Non-stationary Bandits with Knapsacks
Shang Liu' Jiashuo Jiang'
Xiaocheng Li
IIperial College Business School, Imperial College London
'NYU Stern School of Business
s.liu21 @ @mmperial.ac.uk, jj2398 @tteentttueeeu. xiancheng. li imperial.
Abstract
In this paper, we study the problem of bandits with knapsacks (BwK) in a non- stationary environment. The BwK problem generalizes the multi-arm bandit (MAB) problem to model the resource consumption associated with playing each arm. At each time, the decision maker/player chooses play arm, and s/he will receive reward and consume certain amount of resource from each of the multiple resource types. The objective is to maximize the cumulative reward over finite horizon subject to some knapsack constraints on the resources. Existing works study the BwK problem under either stochastic or adversarial environment. Our paper considers non-stationary environment which continuously interpolates these two extremes. We first show that the traditional notion of variation budget is insufficient to characterize the non-stationarity of the BwK problem for sublinear regret due to the presence the constraints, and then we propose a new notion of global non-stationarity measure. We employ both non-stationarity measures to derive upper and lower bounds for the problem. Our results are based on a primal-dual analysis of the underlying linear programs and highlight the interplay between the constraints and the -on-staiionarity Finally, we also extend the -tatinationarttty measure to the problem of online convex optimization with constraints and obtain new regret bounds accordingly.
Introduction
The multi-armed bandit (MAB) problem characterizes problem for which limited amount of resource must allocated between competing (alternative) choices in a way that maximizes the expected gain. The bandits with knapsacks (BwK) problem generalizes the multi-armed bandits problem to allow more general resource constraints structure on the decisions made over time, in addition the customary limitation the time horizon. Specifically, for the BwK problem, the decision maker/player chooses to play an arm at each time period; s/he will receive a reward and consume certain amount of resource from each of the multiple resource types. Accordingly, the objective is to maximize the cumulative reward over a finite time horizon and subject to an initial budget of multiple resource types. The BwK problem was first introduced by (Badanidiyuru (0033 as a general framework to model a wide range of applications, including dynamic pricing and revenue management (Besbes and Zeevi 2012), Adwords problem (Mehta al. 2005 and more.
al.
The standard setting of the BwK problem stochastic where the joint distribution reward and resource consumption for each arm remains stationary (identical) over time. Under such setting, linear program (LP). that takes the expected reward and resource consumption of each arm as input, both serves the benchmark for regret analysis and drives the algorithm design (Badanidiyuru et al. 2013 Agrawal and Devanur 2014). Notably, a static best distribution prescribed by the LP's optimal solution is used for defining the regret benchmark. An alternative setting is the adversarial BwK K problem where the reward and the consumption may no long follow a distribution and they can be chosen arbitrarily over time. Under the adversarial setting, sublinear regret is not achievable in
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the worst case; Immorlica et al. [019 derive O T') competitive ratio against the static best distribution benchmark which is aligned with the static optimal benchmark in the adversarial bandits problem [Auer et al., 1995]. Another key of the BwK problem is the number of resource types d. When d = 1, one optimal decision is to play the arm with largest (expected) reward to (expected) resource consumption ratio, where the algorithm design and analysis can be largely reduced to the MAB problem. When d > 1, the optimal decision in general requires to play a combination of arms (corresponding the optimal basis of the underlying LP). Rangi al. [2018] focus the case of d = 1 and propose an EXP3-based algorithm that attains a regret of Oiyy mB log m) against the best fixed distribution benchmark. Their result thus bridges the gap between the stochastic BwK problem and the adversarial BwK problem for the case of = 1. The difference between the cases of d = 1 and d >>>>> 1 is also exhibited in the derivation of -edeeeddddeedennttt regret bounds for the stochastic BwK problem Flajolet and Jaillet 2015 Li et al. 2021 Sankararaman and Slivkins 202T].
In this paper, we study the non-stationary BwK problem where the reward and the resource consump- tion each time are sampled from distribution as the stochastic BwK problem but the distribution may change over time. The setting relaxes the temporally i.i.d. assumption in the stochastic setting and it can be viewed as a soft measure of adversity. We aim to relate the non-stationarity (or adversity) of the distribution change with the best-achievable algorithm performance, and thus result bridges the two extremes of BwK problem: stochastic BwK and adversarial Bw We consider a dynamic benchmark to define the regret, while such benchmark is aligned with the dynamic benchmark in other non- stationaato learning problem (Besbes et al. 2014, 2015] Cheung et al. 2019 Faury et al. 2021]. it is stronger than the static distribution benchmark adversarial BwK Rangi et al. [0018] Immorlica et al., 2019]. Importantly, we use simple examples and lower bound results to show that the traditional non-stationarity measures such change points and variation budget are not suitable for the BwK problem due to the presence of the constraints. We introduce a new non-stationarity measure called global variation budget and employ both of this new measure and the original variation budget to capture the underlying non-stationarity of the BwK problem. We analyze the performance of a Bldding-window UCB-based BwK algorithm and derive a near-optimal regret bound. Furthermore, we show that the new son-stationarity measure can also be applied to the problem of online convex optimization with constraints (OCOwC) and extend the analyses therein.
1.1 Related literature
The study of non-stationary bandits problem begins with the change-point or
setting where the distribution of the rewards remains constant over epochs and changes unknown time instants Garivier and Moulines 2008 Yu and Mannor 2009]. The prototype of non-stationary algorithuss such discounted UCB and Hiding-window UCB are proposed and analyzed in GGarivier and Moulines| 2008) to robustify the standard UCB algorithm against the environment change. The
prevalent variation budget measure V = Ei= IP, - Pt+ill (where P. and the norm bear different meaning under different context) later proposed and widely studied under different contexts, such as non-stationary stochastic optimization (Besbes et al. [2015)). non-stationary MAB (Besbes et al. (2014), ) non-stationary linear bandits (Cheung et al. 2019]), D. and non-stationary generalized linear bandits (Faury al. (202]) ) problems. In general, these works derive lower bound of 32 3 T
and propose algorithms that achieve near-optimal regret of Ö(V ( Cheung et al. [2019] and Faury et al. (202T) require various assumptions on the decision set to attain such upper bound; under more general conditions, regret bound of Ö(V 3T ) can be obtained [Faury al. 2021). With the soft measure of non-stationarity, the existing results manage to obtain sublinear regret bounds in T against dynamic optimal benchmarks. In contrast, a linear regret in T is generally inevitable against the dynamic benchmark when the underlying environment is adversarial. We remark that while all these existing works consider the unconstrained setting, our work complements this line of literature with proper measure of non-stationarity in the constrained setting.
Another related stream of literature is the problem of online convex optimization with constraints (OCOwC) which extends the OCO problem in a constrained setting. There are two types of constraints considered: the long-term constraint [Jenation et al. 2016 Neely and Yu! 2017) and the cumulative constraint (Yuan and Lamperski 2018 Yi et al. [2021] ). The former defines the constraint violation by
| 1 9r +1 || whilst the latter defines it by EEn (x:))) where (-)+ is the positive-part function. The existing works mainly study the setting where gt = g for all l and g is known priori. Neely and Yu [017]] considers setting where gi is i..dd generated from some distribution. In
2

---

this paper, we show that our non-stationarity measure naturally extends to this problem and derives bounds for OCOwC when g. 's are generated in a non-stationary manner.
2 Problem Setup
We first introduce the formulation of the BwK problem. The finite set of arms A (with |A| m) called as action set. There are d knapsack constraints with known initial budget of B, for j E [d]. Without loss of generality, we assume B, = B for all j. There finite time horizon T, which also known advance. At each time 1. = 1, ...: T, the learner must choose either to play an arm i to do nothing but wait. If the learner plays the arm i at time t, s/he will receive reward Tr,4 E [0, 1] and consume Cr.iá E [0, 1] amount of each resource j from the initial budget B. As the convention, generates a reward of zero and consumes no resource at all. We assume (rr, Ce) is sampled from some distribution P; independently over time where r, = {rr, he|ml and Ct {cr, Heejl hefmm..jfd) In the stochastic BwK problem, the distribution P. remains unchanged over time, while in the adversarial BwK problem, P. is chosen adversarially. In our paper, we allow P. be chosen adversarially, while we use some non-statinnarity measure to control the extent of adversity in choosing P; 's.
is given fixed
introduce null arm to model "doing nothing" which
At each time f, the learner needs to pick it using the past observations until time - 1 but without observing the outcomes of time step f. The resource constraints are assumed to be hard constraints, i.e., the learner must stop at the earliest time when at least one constraint is violated, i.e. Σn= Ct.j.i, > B, or the time horizon T is exceeded. The objective is to maximize the expected cumulative reward until time т, i.. E E r....]. To measure the performance of a learner, we define the regret of the algorithm/policy adopted by the learner
Reg(t, T) = OPT(T) - E Σ
Tr π
Here OPT(T) denotes the expected cumulative reward of the optimal dynamic policy given all the knowledge of PP's 's in advance. Its definition is based on the dynamic optimal benchmark which allows the arm play decisionss/isstribttions change over time.
2.1 A Motivating Example
The conventional variation budget is defined by
dist(P (Pt, P.+1).
By twisting the definition of the metric dist(...). it captures many of the existing non-stationary measures for unconstrained learning problems. Now we simple example to illustrate why V no longer fits for the constrained setting. Similar examples have been used to motivate algorithm design and lower bound analysis in [Golrezaei et al., 2014 Cheung et al. 2019 Jiang et al. (2020), but have not been yet be exploited in partial-informante
setting such as bandits problems.
Consider BwK problem instance that has two arms (one actual arm and one null arm), and single resource constraint with initial capacity of T Without loss of generality, we assume is even. The null arm has zero reward and zero resource consumption throughout the horizon, and the actual arm always consumes 1 unit of resource (deterministically) for each play and outputs unit of reward (deterministicallly) for the first half of the horizon, i.c., when f = 1, ..., 2.2 For the second half of the horizon t + +1,,.... 1,.... T, the reward of the actual arm will change to either + À or 1 A, and the change happens adversarially. For this problem instance, the distribution Pe only changes once, i... V A (varying up to constant due to the metric definition). But for this problem instance, regret of T-A is inevitable. To see this, if the player plays the actual arm no less than T' 4 times, then A, and this will result
4__
the distributions of the second half can adversarially change to the reward in T-4 regret at least. The same for the case of playing the actual arm for the case of no more than T times, and we defer the formal analysis the proof of the lower bounds in Theorem 2
This problem instance implies that a sublinear dependency on 7 cannot be achieved with merely the variation budget V to characterize the non-stationarity. Because with the presence of the constraint(s),
3

---

the arm play decisions over time are all coupled together not only through the learning procedure, but also through the "global" resource constraint(s). For the unconstrained problems, the non- stationarity affects the effectiveness of the learning of the system; for the constrained problems, the non-stationarity further challenges the decision making process through the lens of the constraints.
2.2 Non-stationarity Measure and Linear Programs
We denote the expected reward vector as p4: {Pr,) and the expected consumption matrix as C. = [ed i.e.,
Me = Brraa Cra. = Elcssal.
We first follow the conventional variation budget and define the local non-stationarity budget:
V1 Pe 12+1llo01
V2 =
Σ |[Ct, Cct1,5llo; 1/2 max V2.--
15
We refer to the measure as local one in that they capture the local change of the distributions between time t and time t +.
Next, we define the global non-stationarity budget:
W1 =
|t 10.000
t=1
W2 = Σ t=1
|0, Cll..
where μ = 1 Et= and = C, These measures capture the total deviations for all the 7 p4 's and C, from their global averages. By definition, W1 and W2 upper bound V1 and V/2 (up to constant), so they can be viewed as a more strict measure of non-stationarity than the local budget. In essential and it aims sharpen the regret bounds.
the definition of W2, the L1 norm
the existing analyses of the BwK problem utilize the underlying linear program (I.P) and establish the LP's optimal objective value upper bound of the regret benchmark OPT(T). In non- stationary environment, the underlying LP is given by
T E
LP ((w)), (C.),T)
max
Me æt.
t=l
S.L.
Σ Ca. & B,
D1 E Am 1 t= 1,...,, T,
where B = T) and Am denotes the m-dimensional standard simplex. We know that LP((u)) (C.), OPT(T).
In the rest of our paper, will use LP((u)). (C for the analysis of regret upper bound. We remark that in terms this LP upper bound, the dynamic benchmark allows the æ, to take different values, while the static benchmark will impose an additional constraint require all the æ, be the same.
For notation simplicity. we introduce the following linear growth assumption. All the results in this paper still hold without this condition.
Throughhut the paper, for a vector E R", we denote L1 norm Loo norm by ||l|]] Σn lec)
max [us]. For matrix M ma denote its Li norm and Loe norm by ||]] =
|Melll maxisisv D Mas. || := sup [alloo
|M maxigism Σ5 MMyl.
sup
mll

---

Assumption (Linear Growth). We have the resource budget B = bT for some b > 0.
Define the single-step LP by
LP( C) max 1 T x
15
s.t. Ca S b, x 1 amAm
where b=
The single-step LP's optimal objective value can be interpreted as the single- step optimal reward under normalized resource budget b.
Throughout the paper, we will use the dual program and the dual variables to relate the resource consumption with the reward, especially for the non-stationary environment. The dual of the benchmark LP( (C,,,))
DLP(( (C.)) = min T- b q Σ 0tt
t=1
s.t. q 2 0,
1e C. q 1m S 0, t= 1=
where Im denotes an m-dimensional all-one vector. Here we denotes one optimal solution as (q", a²).
The dual of the single-step LP( C+) is
DLP(14; Ci) = min b% + q,a
s.t. 2 0,
- C, q - 1m 50.
Here we denotes one optimal solution as (g) aÿ). The dual optimal solutions q" and of are also known as the dual price, and they quantify the cost efficiency of each arm play. Define
= max (1lq" 11 : L..,
The quantity & captures the maximum amount of achievable reward by each unit of resource con- sumption. We will return with more discussion on this quantity after we present the regret bound. Lemma 1, We have the following upper bound on 4.
1
b
Proposition 1. We have
Σ LP(p, C₁) < (P(())) TTLP(I, < Σ LP +))+2(W++WW3)
Proposition Tellates the optimal value of the benchmark LP(( (C.).T) with the optimal values of the single-step LPs. To interpret the bound, (P(())) (C.). T) works upper bound of the OPT(T) in defining the regret, and the summation of LP C.) corresponds to the total reward obtained by evenly allocating the resource over all time periods. In stationary environment, these two are the same as the optimal decision naturally corresponds to an even allocation of the resources. In non-stationary environment, can happen that the optimal allocation of the resource corresponds an uneven one for LP(())) {C.), T). For the problem instance in Section 2. the optimal allocation may be either to exhaust all the resource first half of time periods or preserve all the resource for the second half. In such case, forcing an even allocation will reduce the total reward obtained. The proposition tells that the reduction can be bounded by 2W, + 2gW2 where the con-stationarity in resource consumption W2 is weighted by the dual price upper bound q.
3 Biddng-Wiindww UCB for Non-stationary BwK
In this section, we adapt the standard sliding- UCB algorithm for the BwK problem (Algorithm and derive near-optimal regret bound. The algorithm will terminate when any type of the resources
5

---

is exhausted. At each time t, it constructs standard sliding- -widdowwwwdoww confidence bounds for the reward and the resource consumption. Specifically, we define the sliding-windde window estimators by
L==Iv(t- Fes" 1 i
2==1i((--a) Ct. à 1 i}
E
[(w) 2,j.
Peçi
(w) 4 +1
(w) 4455
+
(wr) where n2, -==Iv((-w) 1f. = 8) denotes the number of times that the i-th arm has been played in the last w time periods. To be optimistic on the objective value, UCBs are computed for rewards and LCBs are computed for the resource consumption, respectively. With the confidence bounds, the algorithm solves single-step LP to prescribe a randomized rule for the arm play decision.
Our algorithm can be viewed as combination of the standard sliding-window UCB algorithm Garivver and Moulines 2008 Besbes al. 2013] with the UCB for BwK algorithm [Agrawal and Devanur 2014]. It makes minor change compared to [Agrwall and Devanur (014] which solves ves a single-step LP with shrinkage factor (1 -1-66 c) on the right-hand-side The shrinkage factor therein ensures that the resources will not be exhausted until the end of the horizon, but it is not essential to solving the problem. For simplicity,
choose the more natural version of the algorithm which directly solves the single-step I.P. We remark that the knowledge of the initial resource budget B and the time horizon T will only be used for defining the fight-hand-side of the constraints for this I.P (PCCCB, (Pa), LC,)
Algorithm Sliding-Winnn Window UCB Algorithm for BwK
Input: Initial resource budget B, time horizon T, window sizes wy (for reward) and W2 (for resource consumption).
Output: Arm play indices (it)'s
1: while /. < T do
if - Cr.j > B for some j then
2:
3:
Break
4: %6% Terminate the procedure if any resource is exhausted.
5: end if
6: Construct confidence bounds (C)) LCB,(C;) with window size W1, W2
UC Pi,
(w11)
2
log(1 12mT3)
(wr1)
ni, +
LCB.,,((C,) ((az))
log (12md())))
(wz)
n4.5
+1
7: Solve the single-step problem (H)
8: Denote its optimal solution by x; (2 m. zt.m)
9: Pick arm & randomly according to xj. i.e., P(4 = = o
Observe the realized reward rt and resource consumption Cr,y for j [d]
11: end while
Now we begin to analyze the algorithm's 's performance. For starters, the following lemma states a standard concentration result for the sliding window confidence bound.
sliding-window
Lemma 2. The following inequalities hold for all t = 1,..., T with probability at least 3T
(C) +
1u.-Me Msttllloo 2 Mess Vi,
smIv(t-wr))
I.CB,ss(C.)
Σ
|C.., Csttalbo Caja. Vj,i
e=Iv(t-wa)
where the UCB and LCB estimators defined in Algorithm
With Lemma 2 we can employ a concentration argument to relate the realized reward (or resource consumption) with the reward (or resource consumption) of the LP under its optimal solution. In

---

Lemma recall that T is the termination time of the algorithm where some type of resources is exhausted, and x is defined in A the optimal solution of the LP solved at time s. Lemma 3. For Algorithm
7
the following inequalities hold for all min(
Σ (n (L.) Tax')
< <4vT (ITTlo((12m7)) 8 log (1mm 12m773mm ym
+ wi V1,
v
T
(c. - (CB))(Cs.)) xx)))
S 4vv (12(11mm7))) /os/og(1/1///000 (og(12mdT33))
+ V2 for all j,
Vw2
with probability at least 1 7.
We note that the single-step LP's optimal solution is always subject the resource constraints. So the second group of inequalities in Lemma iippies the following bound on the termination time т. Recall that b is the resource budget per time period; for larger b, the resource consumption process becomes more stable and the budget is accordingly less likely to be exhausted too early.
If we choose W2 = min [m V2z" T log& (12mdT")1, T) Algorithm the following inequality holds
Corollary
T P-TE T 5 1 (10m f logà (1 + 8vmT V /lo((12dTT3) = (f + vmll)
A Tooloo01mm (12mdT))
with probability at least
27
To summarize, Lemma 3 compares the realized reward with the cumulative reward of the single-step LPs. and Corollary [ bounds the termination time of the algorithm. Recall that Proposition relates the cumulative reward of the single-step LPs with the underlying LP - the regret benchmark. Putting together these results, we can optimize wh and wz by choosing
w1 min [ Vi V 3 log* )1,T). wy min { [Im v 373 log (12mdT"))
and then obtain the final regret upper bound as follows. Theorem 1. Under Assumption
7 the regret of Algorithm is upper bounded as
Reg( 11, 1) b (4v log (ogmdd + (10 + 2d)m + V log (12mdT + 8V mf log( 32 +1)
+ +4 +4vTlog(12mTT 12m 3 V log (12m7 2(W QW2)
=ō (f VmT m V m av W1 + W1+
QW2
where कi denotes the policy specified by Algorithm 1 and Ö(-) hides the universal constant and the logarithmic factors.
Theorem I provides a regret upper bound for Algorithm 1 that consists several parts. The first part of the regret bound is on the order 1 VmT and it captures the regret when the underlying environment is stationary. The remaining parts of the regret bound characterize the relation between the intensity non non-stationarity and the algorithm performance. The non non-stationarity from both the reward and the resource consumption will contribute the regret bound and that from the resource consumption will be weighted by a factor of 5 or & (See Lemma for the relation between these two). For the local non-stationarity V1 and V2, the algorithm requires prior knowledge of them to decide the window length, aligned with the existing works on non- stttstation in unconstrained settings. For the global non-stationarity W1 and W2, the algorithm does not require any prior knowledge and they will contribute additively to the regret bound. Together with the lower bound results Theorem 2 argue that the regret bound cannot be further improved even with the knowledge of W, and W2.
When the underlying environment degenerates from a non-stationary one a stationary one, all the terms related to V1, V2, Wi and W2 will disappear and then the upper bound in Theorem | matches
7

---

the regret upper bound for the stochastic BwK setting. In Theorem 1 we choose to represent the upper bound in terms b and T so as to reveal its dependency on T' and draw better comparison with the literature on unconstrained bandits problem. We provide a second version of Theorem 1 in Appendix E that matches the existing high probability bounds using OPT(T) (Badanidiyuru et al. 2013 Agrawal and Devanur 20144. In contrast to the (log 7) comperiitivesss result in the adversarial BwK lmmorlica et al. 20191, our result implies that with a property measure of the won-stationarrity/aversiii the sliding- window design provides effective approach to robustify the algorithm performance when the underlying environment changes from stationary to non-stationary, and the according algorithm performance will not drastically deteriorate when the intensity of the non-stationarity is small.
When the resource constraints become non- con-binding for the underlying LPs, the underlying environ- ment degenerates from a constrained setting to an unconstrained setting. We separate the discussion for the two cases: (i) the benchmark LP and all the single-step LPs have only non-binding constraints; (ii) the benchmark LP have only non-binding constraints but some single-step LP have binding constraints. For case (i), the regret bound in Theorem [ will match the non-stationary MAB bound [Besbes et al., 2014). For case (ii), the match will not happen and this is inevitable. We elaborate the discussion in Section D.
Theorem 2 (Regret lower bounds). The following lower bounds hold for any policy
(i) Reg(Tt, T) = 2m
(ii) Reg(TT, T) = 2 m v2)
(iii) Reg(T, T) = ?(W + (.2).
Theorem 2 presents a few lower bounds for the problem. The first and the second lower bounds are adapted from the lower bound example in non-stationary MAB [Besbes al. 2014] and the third lower bound is adapted from the motivating example in in There are simple examples where each one of these three lower bounds dominates over the other two. In this sense, all the non-stationarity- related terms in the upper bound of Theorem [ are necessary including the parameters 1/b and q. There is one gap between the lower bound and the upper bound with regard the number of constraints d in the term related to 1/2. We leave it as future work to reduce the factor to log d with some finer analysis. Furthermore, we provide a sharper definition of the global nonstationarity measure W Wiiin and Warti in replacement of Wi and W2 in Appendix C2. It makes no essential change our analysis, and the two measures coincide with each other on the lower bound problem instance. We choose to use W1 and W2 for presentation simplicity, while Witin and Wniin can capture the more detailed temporal structure of the nonstationarity. The discussion leaves an open question that whether the knowledge of some additional structure of the environment can further reduce the global non-stationarity.
4 Extension to Online Convex Optimization with Constraints
In this section, we show how our notion of non-stationarity measure can be extended to the problem of online convex optimization with constraints (OCOwC). Similar to BwK, OCOwC also models sequential decision making problem under the presence of constraints. Specifically, at each time t, the player chooses an action x; from some convex set X. After the choice, a convex cost function
fe X' + R and a concave resource consumption function 9t (gt.1..... ..... It.d) : X + Id are revealed. As in the standard setting of OCO, the functions ft adversarially chosen and thus a static benchmark is consider and defined by
OPT(T) = min ΦEX
(a)))
T
S.t. Σ
(x) < 0, for i E [d].
Denote its optimal solution x" and its dual optimal solution as q"
8

---

While the existing works consider the case when are static or sample i..d. from some distribution P. We consider non-stationary setting where 9t may change adversarially over time. We define global non-stationarity measure by
T
W.
19. 0,110
where 0j = Ei= It.j and || == sup [f())
The OCOwC problem considers the following bi-objective performance measure:
T
Reg (T,
f(()))
Σ f((x")
1=1
t=1
T
Reg2 (T, 7)
(t,s(
1=1
where (.)+ denotes the positive-pan function and denotes the policy/algorithm.
In analogous to the single-step LPs, we consider an optimization problem with more restricted
constraints as
OPT = min #EX
Σ (x) 1=1 s.t. (x) S 0, for t E [T], i [d].
Denote its optimal solution xt', and its dual optimal solution as q²' The following proposition relates the two optimal objective values.
We assume that Slater's condition holds for both the standard OCOwC program OPT(T) and the restricted OCOwC program OPT((T) We assume that St, V St.., and V gt are uniformly bounded on X and that X itself is bounded. Moreover, we assume that their dual optimal solutions are uniformly bounded by q. i.e.
Assumption 2.
= max { {119r oloo 11
The following proposition relates the two optimal objective values. Proposition 2. For OCOwC problem, under Assumption 2 we have
0 S OPT OPT(T) S GW.
Utilizing the proposition, we can show that the gradient- gradient-bbsedd algorithm of [Neely and Yu 2017] achieves the following regret for the setting of OCO with non-stationary constraints. Moreover, further extend the results and discuss Appendix F on an oblivious adversarial setting where gi is sampled from
distribution P. and the distribution P, may change over time.
Theorem 3. Under Assumption 2 the Virtual Queue Algorithm of (Neely and Yu 2017 for any OCOwC problem (denoted by σ²) produces a decision sequence {xt} such that
Regi (m2, T) < (((T)) +WW,
Rega (TT, T) - (dVTT)
The theorem tells that the non-stationarity when measured properly will drastically deteriorate the performance of the algorithm for the OCOwC problem as well. Moreover, the non-stationarity will not affect the constraint violation at all. Together with the results for the BwK problem, we argue that the new global non-stationarity measure serves as a proper one for the constrained online learning problems. Note that the upper and lower bounds match up to a logarithmic factor (in a worst-case sense) subject to the non-stationarity measures. The future direction can be to refine the bounds in a more instance-dependent way and identify useful prior knowledge on the stationntny for better algorithm design and analysis.

---

5 Discussions
In this paper, we study the non-stationary setting of the BwK problem. We remark that our formulation is not different from stochastic BwK and adversarial BwK, but it should be viewed as a generalization of both:
When the underlying distribution Pa is i..dd, our formulation degenerates into the stochastic BwK problem.
Our formulation allows Pe to be point-mass distributions and also allows it to be chosen adversarially, so it recovers the setting of adversarial Bwk. Different from the existing worst- case results on adversarial BwK, result characterizes problem-dependent performance that relates the regret with the temporal change of Pa's.
Two important applications (among others, see Badanidiyuru et al., 2013) are AdWords problem (under pay-by-click and pay-by-conversion), and the pricing problem, where the knapsack constraints capture the bidder's budget or the available inventory. Under such application context, the distri- bution of the arms' reward and/or resource consumption may change over time; for example, the bidder's 's bidding policy may change according to their remaining budget, and the underlying market environment may change due to seasonality, day-of-week effect, promotions etc. Both our work and the adversarial BwK aim to capture such violation of the i.i.d. assumption in the stochastic BwK. Speaking of these applications, the stochastic setting is too ideal, while the adversarial setting too worst-case/com consttccse/cooserativee
manssttiionartt provides smooth connection between these two ends. The spirit inherits the study of non non-stationary environment for unconstrained online learning problem
Besbes et al. 2014 2015 Cheung et al. 2019 Faury et al. 2021
Technically, we first make comparison between the existing results on MAB and BwK. For the stochastic setting, as we discussed in Appendix D, when the constraints are non-binding, the stochastic BwK's regret bound can recover the regret bound of corresponding MAB problem. However, for the adversarial setting, the EXP3 algorithm achieves O(VT) regret bound for adversarial MAB problem against a static benchmark, while the state-of-the-arr adversarial BwK algorithm only achieves an (log 7) competitiveness ratio against the static benchmark, i.e., even worse than a linear regret. In comparison. we believe the BwK problem in a non-i.i.d. (non-stochastic) environment is pessimistically difficult and far from being resolved. In this light, our work provides a positive result for the problem. We provide in Appendix CI detailed discussion and comparison of the benchmarks used in the existing BwK works. Numerical experiments compare the performance of our algorithm with existing BwK algorithms and are presented in Appendix A.
The key for our paper to achieve this result the proposal of of the new non-stationarity measure, while the algorithm and analysis are largely standard as in the UCB literature. The standard analysis also appears in existing works on non-stationary online leaming/optimization [Besbes al., 2014 2015. Cheung et al. 2019, Faury et al, [2021] where the techniques more or less follow the paradigm of combining the Moddingwwndoon concentration argument with the analysis in a corresponding context of stochastic optimization. MAB, linear bandits, or RL. Our measure is new as all existing works on non-stationarity study unconstrained settings. Our measure is also critical for a constrained setting: we believe its application goes beyond the BwK and OCO problem and it also provides useful measure for other constrained problems such as constrained MDP and safe RL. Insight-wise, our discussion in Section 2.1 not only validates the criticality of such a measure but also highlights that even if one does not need to perform any learning to the system, the non-stationarity problem can still hurt. This intuition is orthogonal to the existing implications of the current works on non-stationarity which mainly focus on remedying the negative effect nonstationary induced on the learning of the system.
a constrained
References
Shipra Agrawal and Nikhil R Devanur. Bandits with concave rewards and convex knapsacks. In Proceedings of the fifteenth ACM conference on Economics and computation, pages 989-1006, 2014.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. Gambling in rigged casino: The adversarial multi-armed bandit problem. In Proceedings of IEFE 36th annual foundations of computer science, pages 322-331. IEEE, 1995.
10

---

Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knapsacks. In 2013 IEEE 54th Anmual Symposium on Foundations of Computer Science, pages 207-216. IEEE, 2013.
Omar Besbes and Assaf Zeevi. Blind network revenue management. Operations research, 60(6): 1537-1550, 2012.
Omar Besbes, Yonatan Gur, and Assaf Zeevi. Stochastic multi-armed-bandii problem with non- stationary rewards. Advances neural information processing systems, 27, 2014.
Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Operations research, 1227):122, 2015.
Wang Chi Cheung, David Simchi- Levi, and Ruihao Zhu. Learning optimize under non-stationarity. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1079-1087. PMLR, 2019.
Louis Faury, Yoan Russac, Marc Abeille, and Clément Calauzènes. Regret bounds for generalized linear bandits under parameter drift. arXiv preprint vrXiv:2103.057555 2021.
Arthur Flajolet and Patrick Jaillet. Logarithmic regret bounds for bandits with knapsacks. arXiv preprint
2015.
Aurélien Garivier and Eric Moulines. On upper-confidence bound policies for non-stationary bandit problems. arXiv preprint arXiv:0805.3415 2008.
Negin Golrezaei, Hamid Nazerzadeh, and Paat Rusmevichientong. Real-time optimization of personalized assortments. Management Science, 60(6):1532-1551, 2014.
Nicole Immorlica, Karthik Abinav Sankararaman, Robert Schapire, and Aleksandrs Slivkins. Adver- sarial bandits with knapsacks. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 202-219. IEEE, 2019.
Rodolphe Jenatton, Jim Huang, and Cédric Archambeau. Adaptive algorithms for online convex optimization with long-term constraints. In International Conference on Machine Learning, pages 402-411. PMLR, 2016.
Jiashuo Jiang, Xiaocheng Li, and Jiawei Zhang. Online stochastic optimization with wasserstein based non-stationarity, arXiv preprini arXiv:2012.069661, 2020.
Xiaocheng Li, Chunlin Sun, and Yinyu Ye. The symmetry between and knapsacks: A primal- dual approach for bandits with knapsacks. In International Conference on Machine Learning, pages 6483-6492. PMLR, 2021.
Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. Adwords and generalized on- on-line matching. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'OS), pages 264-273. IEEE, 2005.
Michael J Neely and Hao Yu. Online convex optimization with time-varying constraints. arXiv preprint arXiv:1702.04777 2017.
Anshuka Rangi, Massimo Franceschetti, and Long Tran-Thanh. Unifying the stochastic and the adversarial bandits with knapsack. arXiv preprint arXiv: 18/11222 2018.
Karthik Abinav Sankararaman and Aleksandrs Slivkins. Bandits with knapsacks beyond the worst case. Advances Neural Information Processing Systems, 34, 2021.
Xinlei Yi, Xiuxian Li, Tao Yang, Lihua Xie, Tianyou Chai, and Karl Johansson. Regret and cumulative constraint violation analysis for online convex optimization with long term constraints. In International Conference on Machine Learning, pages 11998-12008 PMLR, 2021.
Jia Yuan Yu and Shie Mannor. Piccewise-stationary bandit problems with side observations. In Proceedings of the 26th annual international conference on machine learning, pages 1177-1184, 2009.
Jianjun Yuan and Andrew Lamperski. Online convex optimization for cumulative constraints. Advances in Neural Information Processing Systems, 31, 2018.


Reviews:
[{"review_id": "Z21Xe48Iz61", "reviewer": "Reviewer_JHmo", "summary": "\nThe authors studied the problem of bandits with knapsacks (BwK) in a non-stationary environment. In BwK problem the objective is to maximize the cumulative reward over a finite horizon subject to some knapsack constraints on the resources. Their first result shows that the traditional notion of variation budget is insufficient to characterize the non-stationarity of the BwK problem for a sublinear regret due to the presence of the constraints. Following, the authors propose a new notion of global non-stationarity measure and establish upper and lower bounds for the problem. The results are based on a primal-dual analysis of the underlying linear programs which highlights the interplay between the constraints and the non-stationarity. Finally, the paper also extends to the setting of online convex optimization with constraints and analyze new regret bounds.", "questions": "Is there any new idea introduced in this paper? I agree this being the first work on non-stationary-BwK, however the problem formulation seems to be an extention from that of MAB literature and so are the algorithmic ideas + analysis techniques. For example, the sliding window UCB idea is popularly studied in non-stationary bandit literature. The subsequent regret analysis and the nature of the bounds also look very similar to that of MAB (e.g. O(V^1/3 T^2/3) regret etc.). The measure of non-stationarity in Non-stationary BwK (or OCOwC) are new but they are most intuitive ones and possibly can not be considered as enough contribution for this venue. ", "limitations": "The lack of technical novelty in the problem formulation, as well as the solution approach (both of which seem like an aggregation of ideas from MAB literature), is the key limitation of the paper. ", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nStrength: \n- Strong theoretical results with matching lower bounds guarantees for some cases\n- Motivating applications\n\n\nWeakness: \n- Technical novelty in problem formulation as well as algorithmic ideas", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "LCPVAiUrlQz", "reviewer": "Reviewer_jSi5", "summary": "The paper extends the problem of multiarmed bandits with knapsack to the situation where the underlying environment is allowed to vary. Further, the paper extends the sliding window UCB algorithm to be applied to this setting. The authors show lower bounds for this problem and also show how the extension of the sliding window UCB algorithm can achieve near optimal worst-case regret. Finally, they extend their methods to general online convex optimization problems with constraints. ", "questions": "1) I am  unclear of the usefulness/applicability of such a model. Stochastisticity and Adversity make sense to me, but can the authors give a concrete practical situation (other than for theoretical completion) where such a setting indeed makes sense.\n\n2) Can the authors supply a simulation result where standard SOTA algorithms designed stochastic knapsack problem fail when applied to the setting proposed, while the algorithm proposed overcomes this.\n\n", "limitations": "While the paper does not have a \"Discussion\" or \"Conclusion\" section (due to paucity of space probably), the authors provide some hints on the future directions and the limitations of their work.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ I really like the presentation of the paper, its very well-written especially Sec 2 and 3.\n+ The theoretical results on the regret bounds, both the upper and lower bounds, seem technically sound\n\n\n- While doing a good job on explaining things, still I am a little unsure about the motivation of the problem itself, i.e., how and when such a setting is applicable given that one already has algorithms for the stochastic and adversarial settings. Let me know if I missed something.\n- The paper can benefit further with some simulations comparing how standard SOTA algorithm for stochastic knapsack problem can fail when applied to such settings, while the modification proposed can overcome such an issue.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "A6f0fvKhnC", "reviewer": "Reviewer_EkgL", "summary": "They study the problem of Bandits with Knapsacks where the underlying distribution from which the outcomes are drawn are non-stationary. In this paper, the authors first find a reasonable measure of complexity to measure non-stationarity where we can achieve low-regret. Then they device a sliding-window based algorithm and combine that with UCBBwK from prior work to show that this algorithm achieves low-regret with respect to the new complexity measure they deviced. The paper additionally also proves lower-bound on the best regret achievable.\n", "questions": "he main question I have is around the fact that the defined LP is an upper-bound OPT. First, what type of OPT are we considering here? It seems like we are restricting it to distributions that do not exhaust budget until T rounds. Note in the non-stationary case this coincides with that of the optimal algoritm. However, in the adversarial setting, these are two different benchmarks and one is arguably much weaker than the other. Moreover, this is also weaker than the best fixed distribution that can exhaust budget early (like in Immorlica et al., 2019). The stated fact that the LP is an upper-bound only holds if the OPT considered cannot exhaust budget early. If it can, then this inequality is incorrect. Could you please elaborate and also reflect in the paper that this is the OPT being used? Also some motivation around why this OPT makes sense would be useful to see.\n", "limitations": "Yes, the author's have adequately addressed it.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality\n\n- Considers a new setting in the bandits with knapsacks literature not previously considered.\n- At the outset, the setting seems that achieving low-regret is not possible (a lower-bound example in Immorlica et al., 2019). However, the authors come up with a different notion of non-stationarity (of course much weaker, but still interesting nonetheless) to bypass this lower-bound and show that low-regret with respect to this complexity measure is possible. Of course, in the lower-bound example case this regret bound reduces to being O(T), but in other more fine-grained settings the regret can be sub-linear.\n\n- In mny opinion, the main contribution of this paper is identifying this notion of complexity. The algorithm idea itself is borrowed from prior works and combined together. The proof requires some work (also see my question below) and then they are able to prove the upper-bound. Its also interesting that they prove a matching (upto log factors) lower bounds.\n\n\nQuality\n\n- Overall the paper is of high-quality. The considered problem, theory and algorithm are interesting and has new ideas.\n\nClarity\n\n- The paper is well-written and the main setting, algorithmic idea and related work is explained well. However, I think it would help if the authors described a bit more on the benchmark, what optimum they are comparing against a bit more carefully.\n\nSignificance\n\n- The problem setting is a nice mid-ground between the pure stochastic stationary case and the fully pessimistic adversarial case. When the distribution changes over time, but slowly (like in many practical systems) this is a reasonably practical setting. The results are complete in that both upper and lower bounds are proved. The general problem of bandits with knapsacks is well-studied and is interesting to the machine learning community.\n\nThe main qualm I have with this paper is that the OPT they have considered seems to be much weaker than prior works. I wonder, if the authors can provide more motivation on why this OPT makes sense.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-oSbHFd1ypM", "reviewer": "Reviewer_3Kci", "summary": "In this paper, the authors studied bandits with knapsacks in a non-stationary environment, which differs from existing literature that studied this problem under either the stationary or adversarial settings. The authors characterized a notion called global non-stationary budget, which is different from the notion of variation budget and required due to the presence of the knapsack constraints. They presented a sliding-window UCB algorithm for the non-stationary BwK, established both regret upper and lower bounds, and showed that the algorithm is near-optimal. Finally, the authors also discussed how the non-stationary measure can also be applied in the problem of online convex optimization with constraints. \n", "questions": "1. Is the linear growth assumption only used for introducing the single-step LP? What happens when we do not have this assumption? \n2. Could you provide some intuition on why we have linear dependency on $d$ in the third term of the regret bound on Theorem 1? Any thoughts on why $\\log{d}$ might be attainable? \n3. Could you provide some more intuitions/details about how $W_1^{\\min}$ and $W_2^{\\min}$ differ from $W_1$ and $W_2$? Why does it make no change to the analysis? \n", "limitations": "None. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The notion of global non-stationary budget is novel and appears crucial to the problem with knapsack constraints. The authors also provided good intuitions on why the common variation budget does not fit the constrained setting in Section 2.1.\n2. The sliding-window algorithm presented in Section 3 is shown to attain a near-optimal regret bound based on the results shown in Theorem 1 & 2. The theoretical results here are well explained and appear solid. The authors also provided detailed explanations on how these results compared to previous works. \n3. The authors also applied the non-stationary measure beyond the bandits with knapsack framework and showed that it’s also a proper measure for constrained convex optimization. \n\nWeaknesses: \n1. More motivations should be provided for why the authors wished to consider such a setting. Is it simply combining the works from (i) bandits with knapsack and (ii) non-stationary bandits? What kind of real-world problems can we model using such a setting? \n2. While the results presented in this paper appear theoretically sound, it is unclear how the proposed algorithms perform in practice. What are the realistic implications of the global non-stationary budget? Some numerical experiments could be helpful in illustrating the performance of the algorithm under different variation budgets $W_1$ and $W_2$. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept