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: This paper studied the problem of contextual bandits with knapsack constraints, where, in each round, given the stochastic i.i.d. context and the selected arm, a conversion rate is obtained. The reward and costs are coupled through the binary variable measuring conversion. The authors proposed a new adaptive policy that solves a linear program based on upper-confidence estimates of the probabilities of conversion in each round, and they show that the proposed policy achieves $(\mathrm{OPT}/B)\sqrt{T}$, where $B$ is the total budget allowed, $\mathrm{OPT}$ is the optimal expected reward, and $T$ is the number of rounds. The authors also showed that their proposed techniques can also be applied to the linear structures considered in [Agrawal and Devanur 2016].
strengths_and_weaknesses: Strengths:

+ This paper studied a new MAB model that integrates contextual stochastic bandits and knapsack constraints, which is well motivated in practice.
+ The authors proposed an adaptive policy that achieves $O(\sqrt{T})$ regret for the proposed contextual MAB model with knapsack constraints.
+ The proposed adaptive policy can also be applied to traditional linear contextual bandits with knapsacks.

Weaknesses:

- The proposed adaptive policy requires a finite context set.
- The computational complexity of the proposed adaptive policy is high: Phase 1 of the proposed policy requires a non-trivial projection step and Phase 2 assumes a finite context set. 
- Theoretical analysis techniques are standard and some theoretical regret bounds are not sharp.
questions: - For the projection step in Phase 1 of the proposed adaptive policy, could the authors elaborate on how the projection problem should be formulated and solved?

- The authors stated in quite a few places that their regret bounds can likely be improved. Could they provide a tighter analysis?

- The proposed adaptive policy and its analysis are based on or inspired by integrating several existing techniques (e.g., Logistic-UCB1 by [Faury et al. 2020], [Agrawal and Devanur 2016]). The key analysis steps are standard and similar to these existing works. Could the authors highlight the key differences, challenges, novelty, and contributions in their proofs?
limitations: This paper is theoretical and irrelevant to negative societal impact.
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 the contextual bandits with knapsack problem, where the rewards and costs are coupled through a conversion term. The authors proposed an adaptive policy for the proposed setting, and showed that it achieves a regret bound of order $\tilde{O}(\frac{\text{OPT}}{B} \sqrt{T})$, regardless of whether the context distribution is known or unknown. Finally, the authors also briefly discussed how their approach also applies to the linear contextual bandits with knapsack setting studied in [Agrawal and Devanur 2016].

strengths_and_weaknesses: Strengths:
1. The authors considered a novel setting that couples reward and cost using a conversion term, which corresponds to whether the customer accepts the offer. This is a realistic setting (though it will be ideal if the authors can move some of the discussion on real-world examples to the main body of the paper). 
2. The authors proposed an adaptive policy for their setting and provided detailed discussion about each stage. They also provided theoretical results for the settings of both known and unknown context distributions and the proof appears sound. 

Weaknesses:
1. The finiteness of the context set does appear limited. The authors mentioned that this is required only for Phase 2 of the algorithm and I wonder what are the theoretical results when one discretizes a continuous context set $\mathcal{X}$ for Phase 2? 
2. Some numerical studies should be included in the main body of the paper. In particular, an illustration of the regret bound can be helpful in illustrating the dependency of the algorithm on $T$.
3. Including the lower bound results in the paper could be helpful, even though the authors referred to other works. Currently it is unclear how good the regret upper bounds are. 

questions: 1. The authors mentioned that the regret bound in Theorem 2 can be further improved if the uniform deviation can be improved. Could you provide more details related to this statement? Why is the bound in equation (7) likely to be improved?
2. The authors state that the projection step in Phase 1 could be an issue. I wonder how this issue is dealt with? Do you do something different in numerical studies? Can you make certain changes to this step to improve the theoretical complexity? 

limitations: None.
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: This paper proposes a new contextual bandit model with knapsacks. In this new model, the decision-maker sequentially offers actions to arriving users after observing their contexts. Rewards and costs are only realized if the users accept the offer (a conversion happens). Conversion probabilities follow a logistic model that depends on action-context features and an unknown parameter vector. The goal is to design an adaptive policy that performs almost as well as the best static policy that knows the context distribution and conversion probabilities. The authors propose logistic-UCB1 algorithm to solve this problem. The proposed algorithm at each round computes the MLE estimate of the unknown parameter vector based on history. Then, it computes action selection probabilities by solving an optimization problem with expected constraints. This is a linear program that can be computationally manageable for finite context spaces. Sublinear regret upper bounds are shown both when the learner knows the context distribution and when the learner uses an empirical estimate of the context distribution. Supplemental material provides a motivating example from the banking sector, where the actions correspond to discounts on offered loans. They also investigate how to extend the current work to linear contextual bandits with knapsacks and come up with an algorithm with better budget requirements and parameter tuning capabilities, albeit requiring the finiteness of contexts.
strengths_and_weaknesses: Strengths:

This paper is well written. It proposes a new structural model called conversion for contextual bandits with knapsacks inspired by work on logistic bandits. The model has interesting real-world applications. The regret metric and the proposed algorithm are intuitive. I think the main paper does a good job positioning the current work within the literature on contextual bandits with knapsacks. Comparison with existing works is sufficient. 


Weaknesses: 

The paper can do a better job of highlighting the technical novelty in the analysis. In the main paper, attention is paid to describing steps that bear similarities with the earlier works. Please elaborate if any non-trivial new technical machinery was introduced in the regret analysis apart from the KKT analysis. 

A discussion on lower bounds and tightness of the results will help readers understand the merits of the proposed work better. 
questions: Why negative regret appears in simulations? 

When justifying comparing with the optimal static policy in regret, the work of Agrawal and Devanur (2016) is mentioned. However, the setup here is not the same due to the conversion model. How is it ensured that the relation between the optimal static policy and the best feasible adaptive policy remains the same as in this prior work under the conversion model? 
limitations: This work does not have any societal impact. Limitations are well discussed.
review_title: null

Meta-review: metareview: As acknowledged in the reviews (and I concur), this is a well written paper that introduces a relevant and interesting contextual-bandits model and gives solid technical results.  The paper certainly has its limitations, but overall the technical contributions are novel and well executed.  The authors have effectively addressed the questions and concerns brought up in the reviews.  I recommend acceptance.
confidence: Certain
Decision: Accept