Venue: NeurIPS 2022 Conference

Reviews:

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: The paper introduced a generalization of BwK model which admits increasing in budget. The authors then proposed an offline MDP-based algorithm named "CB", follows by a learning algorithm that combines the offline version with Li et.al's algorithms. The regret analysis of proposed algorithms is provided and it is tight. Interestingly, the offline algorithm achieves constant regret against OPT_LP, implying the gaps between the expected total reward of "CB", OPT and OPT_LP are not larger than a constant. Besides, the regret of the learning algorithm matches the result in [14] when applying to the classic BwK model. 
strengths_and_weaknesses: Pros: 
The introduced model is new and can serve as a generalisation of BwK model. Accordingly, the two proposed algorithm is new and the  regret is tight.

The offline method and its analysis is new and insightful. 

Cons:
The paper sometimes lacks clarity and I found the its organisation is not easy to follow.

questions: I have 3 following questions:

Q1: While the problem is well motivated as the resources can be renewed, the proposed model is rather unnatural. Particularly, the assumption that both consumption and replenishment depend on arm pulled and are represented by only one variable does not sound reasonable to me. Moreover, I understand that the notion of the null arm is technical and only serves for the analysis. Is there any practical motivation to introduce this arm into the model? 

Q2: I found the proof of lemma 3.1 and its generalization (line 209) are not clear. Which properties of LPs and case analysis are used? Perhaps it is based on the assumption that |X*| =|J*| as in [14]? I do think the authors should be more specific to avoid confusion here.

C3: What is the advantage of the offline MDP-based algorithm (Algorithm 2) over solving the LP (1), as the algorithm also requires solving linear programming within its procedure?

 
limitations: No
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: This paper introduced a generalization of the stochastic bandit with knapsacks (BwK), where in each round, the decision maker observes an outcome consisting of a reward and a vector of resource drifts that can be positive, or negative, or zero. The authors considered two problems depending on whether the knowledge of true outcome distributions is available. If the knowledge is available, the authors developed a Markov decision process (MDP) policy that has constant regret against a linear program (LP) relaxation. Based on this result, the authors developed a learning algorithm that has logarithmic regret against the same LP relaxation when the distribution knowledge is not available. The authors also showed that their regret bound matches a reduction from BwK to their model.
strengths_and_weaknesses: Strengths:

+ The authors proposed a generalized BwK model with non-monotonic resource utilization that has several interesting applications.
+ This paper proposed two policies that achieve constant and logarithmic regrets for cases with or without true outcome distributions, respectively.

Weaknesses:

- The rationale of the null arm modeling assumption appears to be somewhat strong and unclear.
- The UCB/LCB-type learning and regret analysis techniques appear to be standnard.
- Lack of experiments to verify the proposed algorithms.

questions: - The key difference in this paper is that there exists a null arm $x_0$ such that, if played, the expected drift for each resource is positive. This seems to suggest that the resource will increase linearly on average due to the expected positive drift when the null arm is played. To some extent, the resource replenishment rate is quite fast and hence this modeling assumption is quite strong. With this modeling assumption, one can use this null arm to quickly increase the resource budget to sustain the bandit learning. As a result, the strong constant and logarithmic regret under this modeling assumption is not very surprising. Can this assumption be weakened? 

- In the ExploreThenControlBudget learning algorithm, the first while-loop is quite similar to the literature and the associated regret analysis appears to be standard and not surprising. It's unclear what is the major difference, challenges, novelty, and new contributions in this part. It would be great if the authors could clarify the challenges and their contributions in this part.

- Although I understand this paper is of theoretical nature, it's still worth providing some numerical experiments to verify the performance of the proposed learning algorithms, particularly given the fact some of the constants in the theoretical results are likely not optimal (e.g., 4096 in Definition 4 and 2048 in Corollary 4.1). Could the authors provide some experimental results?
limitations: This paper is theoretical and not relevant to negative societal imapcts.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: Authors introduce a generalization of the Bandits with Knapsack problem in which resources can be stochastically replenished over time. They introduce an algorithm which achieves constant regret with respect to an upper bound of the optimal reward both for the single-resource case and the multi-resource case, which involves non-trivial analysis. They then introduce a learning algorithm that they prove has log(T) regret. They finish by showing that BwK can be reduced to their generalization and as such, the same bounds can apply, matching the state of the art.
strengths_and_weaknesses: 
Strengths:
 - Theoretical analysis is thorough, including some relatively non-intuitive results, e.g., Lemma 3.5 which shows that the proper choice of budget threshold can eliminate the regret's dependency on the horizon T. Main results are:
   - Constant regret achieved in the case where reward and cost distributions are known. They achieve mainly by making assumptions necessary to ensure that the optimal solution can reduce to cases amenable to analysis, i.e., there is a subset of arms+resources manipulated in the upper bound solution, and that each arm is "positive" or "negative" drift with respect to a given resource -- these allow analysis of small number of individual cases where the challenge is to compute in expectation how often the authors' proposed policy plays arms that deviate from the upper bound solution.
   - Log(T) regret achieved in the online learning case, via building off of pieces of a previously used multi-stage learning approach which identifies and improves confidence about the "best arms" in the first stages in log(T) time, then runs the optimal algorithm in the final stage.
   - The reduction from BwK is helpful in grounding their results in current literature
 - The paper is relatively clearly written for what is a very math-dense submission. Authors do a nice job providing intuitive explanations within their proof sketches of how they arrived at certain key results, e.g., lines 183-190.
 - This seems to be a novel bandits problem.

Weaknesses:
 - In my view, the authors do not do enough to motivate the problem they introduce. The example they give is "in a dynamic pricing application a seller may receive shipments that increase their inventory level," but it is not clear that the author's model is the proper one even for this example. I.e., is it reasonable to assume that shipments would arrive stochastically and without respect to current supply? More examples should be given, or citations suggesting that this generalization will have impact on the theory community would be helpful. Without a stronger motivation for the problem, it is challenging to evaluate the significance/potential impact of the work. 
 - In my view, it is a weakness not to provide any empirical results. These would help readers understand the current practical usefulness of the theoretical results.
 - Authors also do not provide much commentary on how restrictive their assumptions in section 2.3 are, which also limits understanding the practical usefulness.


questions: 
- Can the authors please provide more motivation for why this generalization of BwK is significant?
- Can the authors please provide either minimal empirical results or a commentary on the practical usefulness of their theoretical results, especially as related to the assumptions made in section 2.3?
- Can the authors comment on how their algorithm and results adapt to the case of deterministic costs, e.g., Case 2 of Flajolet and Jaillet, which also has many real-world applications?


limitations: The authors acknowledge that their work does not achieve the optimal regret bound. They do not discuss the social implications of their work, which is ok for this mostly theoretical submission.
review_title: null

Meta-review: metareview: The paper investigates a generalisation of the BwK problem where the budget is increasing. The authors first propose an offline MDP-based algorithm called "CB”, and an online learning algorithm that combines the offline version with an algorithm from Li et.al. The authors also provide a regret analysis for the proposed online algorithm and they show that it is tight. Interestingly, the offline algorithm achieves constant regret against OPT_LP, implying the gaps between the expected total reward of "CB", OPT and OPT_LP are not larger than a constant. This is probably due to the fact that the pulling costs are bounded (which matches with the known results from the knapsack literature). The authors also mention that the regret of the learning algorithm matches the result in [14] when applying to the classic BwK model.

After the rebuttal phase, all the reviewers are happy with the responses, and suggest accepting this paper.
confidence: Certain
Decision: Accept