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 proposes the general bandit problem that subsumes Bandits with Knapsacks and Bandits with fairness constraints. UCB-LP, inspired by  SemiBwK algorithm [30], is proposed and its regret bound archives $O(mN \log T/\Delta_{\min})$. They also study the special class for fairness constraints and show that UCB-LP guarantees a constant regret. Finally, UCB-PLLP algorithm is proposed as a computational efficient algorithm and its regret bound archives $\tilde{O}(m \sqrt{T})$. 

strengths_and_weaknesses: Strength:
1. Though UCB-LP is designed based on SemiBwK algorithm [30], generalization to linear constraints and regret analysis is done in a novel way. Naive analysis will suffer from the bound with size of extreme points of a feasible region of LP, i.e.,  $|\mathcal{B}|$ which is exponentially large. \


2. UCB-LP does not need prior knowledge while existing work [12, 29, 31] requires some knowledge of the problem instance, and UCB-LP reduces to the standard UCB-1 algorithm for the special case. 



Weakness:

The whole procedure (pseudocode) for UCB-LP is missing in the main paper and supplemental material. 
 

questions: Any new difficulties that arise from changing from a single-armed setting to a combinatorial (size constraint) setting?

Are there any lower bounds for fairness setting with respect to the $r_{\min}$?

===Post Rebuttal===

Thank you for the author feedback. I have read other reviews and discussion. 

Especially, comparison with [Cayci et al., 2021]  and discussion on how this paper uses virtual queue techniques is clearer.
I hope the authors will incorporate them and position this paper in the literature.

So I will keep my score.
limitations: The paper is missing the section for conclusion and does not discuss any limitation or future direction. More discussion is appreciated.
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: The authors study the Combinatorial bandits problem with linear constraints. This problem captures multiple existing problems including fairness constraints, and Knapsack constraints. The authors show that using UCB estimates for the mean reward of each arm in a constrained LP, and playing the arms according to the optimal solution of that LP ensures in expectation 0 constraint violation and logarithmic regret. As a special case, fairness constraints incurs constant regret when each arm is forced to choose a constant fraction of time. They augment this result with a Lagrangian based computationally efficient algorithm with $O(\sqrt{T})$ problem independent regret, and 0 constraint violation with high probability.   
strengths_and_weaknesses: Strengths
- The proposed UCB-LP algorithm solves multiple well studied problems, such as semi-bandits with knapscak, and bandits with fairness constraints.
- The constant regret in fairness constraint is an interesting result (though not very surprising).
- The Lagrangian based optimization process (UCB-PLLP) is computationally efficient, and shows optimal minimax regret with no constraint violation with high probability. 

Weakness
The paper is not well placed in the literature, in my opinion. 
- The paper "The Combinatorial multi-armed bandit: General framework and applications." by Wei Chen et al.  already addresses the main challenge discussed in the paper, i.e. tackling exponential extreme points in the LP.  Similar ideas are used in a slightly different context in "Contextual Blocking Bandits" by Basu et al. 
- The virtual queue based approach used in the UCB-PLLP is used in a series of work by H Yu and MJ Neely. E.g. "A Low Complexity Algorithm with $O(\sqrt{T})$ Regret and $O(1)$ Constraint Violations for Online Convex Optimization with Long Term Constraints" H Yu and MJ Neely. 

Post Rebuttal: Upon discussing with the authors, I came to the conclusion that the current work indeed improves upon the technique used in  [Basu et al. 2021] for regret bounds in constrained LP with blocking, which was based on  [Chen et al., 2013] and [Wang and Chen, 2017]. The novelty in the virtual queue based technique was also made clear from discussions. The authors are requested to include these works and brief summary of discussions in the paper.  
questions: Please compare the current work with the prior works mentioned in the weakness section.
limitations: Any negative societal impact for this work is hard to foresee.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies a general formulation of combinatorial bandits with linear constraints, which contains bandits with fairness and knapsacks as special cases. The authors propose and analyze an algorithm that combines UCB-based estimation with a linear program solution to yield logarithmic regret and zero constraint violation performance. Authors also propose a low-complexity variant of the algorithm that utilizes virtual queues to iteratively solve the LP component of the original design. 
strengths_and_weaknesses: The work provides a solid contribution to the literature on constrained MABs by encapsulating knapsack and fairness constraints within a unified formulation. The design and analysis are valuable contributions to this literature. 

The novelty of the design is limited as it relies largely on well-known principles. However, the analysis yielding the logarithmic regret bound in this setting is important.

While the literature review is extensive, there are several other works that are worth including, such as: 

A Lyapunov-Based Methodology for Constrained Optimization with Bandit Feedback
Semih Cayci, Yilin Zheng and Atilla Eryilmaz
Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022

Budget-Constrained Bandits over General Cost and Reward Distributions
Semih Cayci, Atilla Eryilmaz, R. Srikant
International Conference on Artificial Intelligence and Statistics (AISTATS), PMLR 108, 2020.

The first of these works in particular also uses the lyapunov drift minimization techniques for constrained MABs, which is utilized in the PLLP algorithm design. 
questions: The examples in the discussion are limited. Please expand on them to clarify how the formulation fits into the generic form. 


limitations: I have not seen a discussion on limitations of this work. The emphasis has been on its contributions, which is understandable. It would be good to note any limitations that the authors recognize.
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: 
The paper studies a combinatorial multi-armed bandits with linear long-term constraints, where the combinatorial constraints are cardinality constraints and the linear constraints are deterministic and known. The paper proposes an upper-confidence bound LP-style algorithm for this problem that provides a logarithmic instance-dependent regret and no constraint violations in expectation. Then, the authors develop a second algorithm with better running time, a $\tilde O(\sqrt{T})$ regret, and no constraints violation in high probability.
strengths_and_weaknesses: I have a huge concern about the meaningfulness of the problem studied in the paper.
I think that the study of BwK is meaningful when at least one of the following condition is satisfied:
1) the costs are unknown,
2) the costs are not in expectation, i.e., if the regret minimizer chooses a vector x the actual suffered cost is not g(x) but g(a) where a is sampled from x. Then, if the budget ends the game is over.

If none of the conditions is satisfied, the problem reduces to a classical Linear bandit.
In particular, any no-regret algorithm for linear bandits with action space defined by the constraints in Problem (4) does satisfies the constraints in expectation and provides no-regret.
Notice that your algorithm in Theorem 1 follows this approach: it satisfies the constraints at each round (in expectation).


Minor comments:

The abstract does not specify all the assumptions in the framework. For instance, I suggest to specify in the abstract that the constraints are deterministic and time invariant, while the combinatorial constraints are cardinality constraints.

At line 42. I don’t see a clear relation with the result in [4]. In [4] the constraints are not deterministic and it could happen that the algorithm have to stop before round T since it ended the budget. For this reason $OPT(T)$ could be strictly smaller than $T\ OPT_{LP}$. 
I’m quite sure that $OPT(T)=T \ OPT_{LP}$ with deterministic constraints that need to be satisfied in expectation, since the algorithm never stop.


Post rebuttal update: I'm completely convinced by the authors' answers.


questions: Let me know if I’m missing something about the relation between classical bandit problems and your framework.
For instance, are there some previous works in which neither condition 1) nor condition 2) is satisfied?



limitations: The authors have adequately addressed the limitations and potential negative societal impact of their work
review_title: null

Meta-review: metareview: We thank the authors for their submission.

This work presents a novel framework for bandits with long-term constraints, generalizing both bandits with knapsacks and bandits with fairness constraints. The authors present efficient no-regret algorithms as well as remove some problem-specific assumptions made by prior work.
confidence: Certain
Decision: Accept