Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper tackles the Bandits with Knapsacks (BwK) problems, where the learner is not just looking for the arm with per-round maximal expected reward, but has to take into account the consumption of ressources that can end prematurely the whole process.
While existing work on BwK have already characterized the worst-case regret scaling in sqrt(T), this paper provides additional theoretical guarantees: problem depend upper bounds in log(T) for a UCB-like algorithm called UcbBwK, lower bounds matching the worst-case rate, as well as guarantees on the simple regret. Finally, when the problem instance presents some specific structure (e.g. in combinatorial semi-bandit, linear contextual bandits, multinomial-logit bandits), all these bounds for UcbBwK are improved.
main_review: - The paper is nicely written and contains extensive discussion on the related literature.
- Strong theoretical guarantees are provided for the BwK problem.
- Unfortunately, no numerical experiments are provided to illustrate some mathematical claims. For instance, it would be interesting to verify empirically the relation between the parameter " beta " (line 326), the number of arms K, and the regret. In practice, how large can beta be?
limitations_and_societal_impact:
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the problem of bandits with knapsacks (BwK). In a BwK instance, there are $K$ arms and multiple types of resources with limited budgets, while in standard bandits there is only one resource time. Each pull of an arm returns a random reward and consumes a random amount of each resource. The pulling ends as soon as one of the resources runs out, and the goal is to maximize the cumulative reward before a resource runs out. 

In particular, this paper focuses on the case (denoted as $C$) where there are only two types of resources and the optimal policy is always pulling some arm $a^*$. In this specific case, the authors showed a regret upper bound in the form of $O(\frac{K}{\Delta^2}\log{T})$ or $O(\frac{K}{\Delta}\log{T})$ under some conditions. The authors also showed that if $C$ does not hold, then no algorithm can do better than $\Omega(\sqrt{T})$ and thus, no logarithmic regret can be obtained.

The authors also studied the simple regret of BwK and showed that their algorithm can achieve $O(\log{T})$ simple regret. 
main_review: The logarithmic regret of BwK has been a difficult problem, and there are only a very few works that have focused on this topic. To the best of my knowledge, this work is the first to obtain a logarithmic regret with i) more than one type of resource and ii) random or non-deterministic regrets. When one of i) or ii) does not hold, then previous works have shown logarithmic regrets, but when both of them are true, then this work is the first. However, I do not find a lot of novelty in the algorithm design and this specific case may be limited in practice. 

This paper is not quire well written as there are too many notations. Perhaps the authors can try simplifying or hiding some of the notations in the next version. 

In my opinion, the logarithmic lower bound of BwK is also difficult, but it would be better if the authors can provide some results on the lower bound. It is not clear whether $G_{\mbox{LAG}$ is a good or tight enough gap for deriving the regret. 

Thus, I will vote a 6 for this submission. This work has significant contribution to a specific case, the contribution is limited in practice and lacks the justification that this result is good enough. 
limitations_and_societal_impact: See the comments in the box Main Review.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper introduces a new algorithm for the BwK Problem achieving $O(\log T)$ regret for a "best-arm-optimal" instance. The algorithm is based on a variant of UcbBwK. Moreover, they show $\Omega(\sqrt{T})$ lower bound and they provide a general reduction from BwK to stochastic bandits.

Pros:
(i) Characterizing the problem-dependent lower bound by a new quantity, Lagrangian gap. In the language of linear programming (LP), this is related to minimal non-zero reduced cost for the underlying LP that does not include the null arm.
(ii) Better bound. From certain "best-arm-optimal" instances, their regret bound is better than the existing work. 
(iii) One-round performance. It shows that the rewards collected by UcbBwK are approximately optimal for all but a few rounds.  
(iv) Reduction from BwK to stochastic bandits.


main_review: Given the merits summarized above, I have the following concerns:

The recent work [44] studies the BwK problem under a more general setting without the best-arm-optimal condition. It would be helpful to present a comparison of the bound in this paper and the bound therein (when reduced to a best-arm-optimal instance). 

There might be some issues with the lower bound proof:
(i) The second line on the inequalities at the bottom of page 22 might not hold. First, intuitively, for an algorithm that only plays non-null arms at the last few rounds, $V({Y})$ can be larger than $V({X}^*)$ in those rounds since during those rounds, the resources average budget is more than the initial average budget and scaled average budget. Second, theoretically, in the proof of E.4, it seems that authors assume that the policy ${Y}$ at each round must be a feasible solution to the LP corresponding to ${X}^*$ (thus the performance of ${Y}$ can not be better than $V(X^*)$ in that step). However, the average budget in a step can be larger than the initial average budget. Thus, even if ${Y}$ and ${X}^*$ are different, $V({Y})$ can still be larger than $V({X}^*)$ in this case.

(ii) The first paragraph of Appendix F might require more clarifications. First, it seems unclear why the perturbation on $r$ and ${C}$ is equivalent to perturbing the vector ${b}$ in general. More importantly, Proposition 3.1 in [46] only provides a sufficient condition that small perturbation can help a degenerate LP to become non-degenerate. Authors might need more explanation on how the perturbation can render an LP from non-degenerate to degenerate (reversely from [46]). 
limitations_and_societal_impact: There is no negative societal impact that I can see.
review_title: null

Meta-review: This paper investigates the bandits with knapsack (BwK) problem. It extends the state of the art by looking beyond the worst case regret analysis and provides logarithmic regret upper and lower bounds, first of their kinds. The second contribution of the paper is the analysis of BwK from the simple regret's perspective. Here the authors have proved that for any $\epsilon > 0$, apart from $O(K/\epsilon^2)\log(KTd))$ time steps, this simple regret is typically smaller than $\epsilon$. The final main contribution of the paper is the new proving concept that helps converting proof techniques from the classical bandit to the BwK setting, making the regret analysis in the BwK domain more seamless. Apart from this, the paper also introduces a number of new gap concepts and proof techniques.

As someone quite familiar with the BwK literature, I find this paper to be fascinating. If any weaknesses I need to mention then perhaps the denseness of the paper. It was a bit difficult to follow all the new concepts and terms. However, overall I find the amount of novelty and new ideas compensate this weakness.

From the reviewers' comments I can conclude that they also (more or less) share my judgement that this is a good paper. It is quite unfortunate that the reviewers were not involved in the discussion with the authors in a more active way to further elaborate on the strengths and weaknesses of the paper. Nevertheless, none of the reviewers did mention any reasons for rejecting this paper. Therefore, I recommend it to be accepted as a poster. 

Decision: Accept (Poster)