Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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. 
strengths_and_weaknesses: + I really like the presentation of the paper, its very well-written especially Sec 2 and 3.
+ The theoretical results on the regret bounds, both the upper and lower bounds, seem technically sound


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

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


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.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: 
The 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.
strengths_and_weaknesses: 
Strength: 
- Strong theoretical results with matching lower bounds guarantees for some cases
- Motivating applications


Weakness: 
- Technical novelty in problem formulation as well as algorithmic ideas
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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 

strengths_and_weaknesses: Strengths:
1. 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.
2. 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. 
3. 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. 

Weaknesses: 
1. 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? 
2. 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$. 

questions: 1. Is the linear growth assumption only used for introducing the single-step LP? What happens when we do not have this assumption? 
2. 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? 
3. 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? 

limitations: None.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.

strengths_and_weaknesses: Originality

- Considers a new setting in the bandits with knapsacks literature not previously considered.
- 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.

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


Quality

- Overall the paper is of high-quality. The considered problem, theory and algorithm are interesting and has new ideas.

Clarity

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

Significance

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

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

limitations: Yes, the author's have adequately addressed it.
review_title: null

Meta-review: metareview: The paper provides a nontrivial extension of dynamic regret minimization to knapsack bandit problems in the mixed (obliviously adversarially chosen distributions), and identifies new measures of complexity for constrained decision making problems. Its algorithmic novelty is rather limited, though, as it borrows the 'usual' ideas of windowed averaging with statistical upper/lower bounds for enabling 'forgetting' which is crucially required in nonstationary environments. 

The reviewers for the paper are largely appreciative of the paper's contributions in developing and arguing for new measures of nonstationarity, in terms of dependence on both the constraint and the reward side. Their concerns have been responded to in detail by the author(s), explaining both technical and motivation-related aspects on one hand, and connections to existing related work on the other. With the belief that this line of work may spur other creative directions in constrained decision-making / bandit problems, I am happy to recommend acceptance. I urge the author(s) to use the extra page of space to incorporate their responses to many of the reviewers' queries. 
confidence: Less certain
Decision: Accept