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 considers the combinatorial semi-bandits problem under two different settings: (1) probabilistically triggered arms setting where the set of played arms can trigger reward on other arms, (2) the non-triggering setting with independent arms. For both these settings the authors improve batch-size dependence in regret as compared to previous work by considering a new variance-based condition on the underlying reward distributions. The authors show that this condition is satisfied in many applications such as cascading bandits, influence maximization on DAGs etc, and leads to significant improvements in the regret achievable for these applications. 
strengths_and_weaknesses: Strengths: The paper provides a good contribution to the literature on combinatorial semi-bandits as it improves the dependence on batch size from linear to logarithmic in many practical applications. The paper is very well-written and provides clear intuition behind various ideas/assumptions. The comparison with prior work is also adequate.
questions: 1. In Section 4, is the notion of regret still (\alpha, \beta)-approximate regret? If yes, then I do not understand the reason behind using this notion of regret. In the independent arms setting you are not using the oracle to return a (\alpha, \beta)-approximate set of arms, instead you are computing the argmax using brute force. In that case you should be able to compete with the best set. 

2. It would be great if the authors can provide experimental results for some applications which support the theoretical improvements.
limitations: I do not foresee any negative societal impact.
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 new smoothness conditions for the well-known combinatorial semi-bandit problem with probabilistically triggered arms. It is shown that well-known combinatorial learning problems of interest, including combinatorial cascading, influence maximization, and probabilistic maximum coverage bandits, satisfy these conditions. With the so-called triggering probability and variance modulated smoothness condition, the authors significantly improved the O(K) factor that appears in the previous regret bounds, where K represents the batch size. The authors also propose a non-triggering version of the smoothness condition and show that dependency on K can be completely removed for the non-triggering combinatorial semi-bandit. In order to achieve the improved regret bounds for the triggering version of the problem, the paper relies on empirical Bernstein inequality to construct upper confidence bounds of base arms. For the non-triggering version, batch size independence is achieved by constructing sub-exponential concentrated confidence intervals. 
strengths_and_weaknesses: Strengths: 

Finding general enough smoothness conditions under which the effect of batch size on the regret can be significantly improved is an important problem. This paper intuitively develops new smoothness conditions and algorithms that use tailored confidence intervals to address this problem. 

Computationally efficient algorithms are proposed for triggering and non-triggering cases. 

Writing is clear. Theorems are well organized. 

Weakness:

True batch size independence comes with an algorithm that requires enumeration of all possible actions. I wonder if any computationally efficient algorithm can achieve batch size independence. 
questions: I wonder if any computationally efficient algorithm can achieve batch size independence. 
limitations: Limitations are adequately discussed. This work is theoretical in nature and does not have a societal impact.
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: Remark: Throughout my review, [n] refers to the n-th reference in the full paper (with appendix) from the supplementary material. (I mention this because the reference numbers differ in the 9-page submission.)

This paper studies Combinatorial Multi-Armed Bandit (CMAB) problems with probabilistically-Triggered arms (CMAB-T). In essence, CMAB is a variant of the standard bandit setting where the learner chooses a subset of arms (a.k.a. a “super arm” or “action”) and the mean reward is a function of the chosen subset and of its component arms’ mean rewards, and for CMAB-T the learner only observes feedback on a random subset of the chosen arms. This formulation generalizes problems including cascading bandits for ranking search results, online influence maximization, etc.

Prior work [27] introduced a smoothness condition (with respect to the function that maps the component arms’ mean rewards to the subset’s mean reward) that improved existing regret bounds [7] by a factor of $1/p^*$ (see Line 36 for details). This work provides a refined smoothness condition that involves the variance of the arms’ reward distribution, i.e., the condition is less restrictive when the variances are smaller (simply because the mean rewards are easier to learn in such cases). Provided this condition holds, the authors develop a variance-aware UCB-style algorithm based on the empirical Bernstein inequality [1] and show its regret improves existing work with respect to the “batch size” K, which is the maximum of arms that can be triggered at each round (e.g., the number of search results that a cascading bandit algorithm chooses).

In addition, the authors study non-triggered arms (Section 4) and specialize their results to various application settings (Section 5).
strengths_and_weaknesses: STRENGTHS:

In my opinion, the strengths of the paper are (1) a novel and fairly natural smoothness condition that incorporates variance information, (2) algorithms that exploit low variance problem instances via empirical Bernstein confidence sets (instead of “variance-unaware” Hoeffding-based confidence sets), and (3) analysis that shows exploiting variance in this manner can dramatically reduce regret in terms of $K$ (e.g., from $K$ to $log K$ in some settings).

At a higher level, I feel the main strength of this paper is to show that variance-aware algorithms lead to polynomial improvement in terms of K, and to do so in a fairly general setting (CMAB-T). More specifically, paper A (see below) recently proved something similar for cascading bandits (a special case of CMAB-T), although it focuses on gap-free bounds so is complementary to the current work (which focuses on gap-dependent bounds). More broadly, a number of recent papers have demonstrated similar (in spirit) polynomial improvements resulting from variance-aware algorithms in various bandit and RL settings (e.g., paper C below achieves a polynomial improvement in terms of the horizon for finite-horizon RL; see also the references therein and in paper B below). Thus, the current paper seems rather timely given the similar flavor to these works.

(To be clear, I’m not demanding these papers be cited — reference A is a very recent preprint and the others are on different topics — but rather, emphasizing the timeliness of the current work).

(A) Vial, Sanghavi, Shakkottai, Srikant, “Minimax Regret for Cascading Bandits”, arXiv preprint

(B) Zhang, Yang, Ji, Du, “Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP”, arXiv preprint

(C) Zhou, Gu, Szepesvari, “Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes”, COLT 2021

WEAKNESSES:

(1) While mostly well-written, the paper is very dense, particularly the first few technical sections (i.e., starting from Section 2). I imagine this is mostly a side effect of packing many technical definitions and results into a short page limit, but it was hard to follow at times. For example, Section 2 would have been easier to understand if the authors had used a simple special case of the CMAB-T model (e.g., cascading bandits) as a running example to help illustrate the technical definitions (of which there are many in Section 2).

(2) Along these lines, I did not find the proof sketches very illuminating, and it was difficult to glean much intuition from the full proofs in the appendix given their length and density. In other words, I would have preferred an intermediate explanation -- high-level like the proof sketches, but more detailed like the actual proofs -- to illustrate the key ideas of the analysis (again, perhaps in a simpler special case of CMAB-T).

~~(3) Unless I'm mistaken (in which case I'll gladly update during the discussion period), the improvement over prior work in the disjunctive cascading bandit setting is oversold. (See "Questions" section for details.)~~

Update post-rebuttal: Weakness (3) has been satisfactorily addressed and I remain in support of acceptance.
questions: ~~In the first row of Table 3, the authors claim that their regret bound for disjunctive cascading bandits improves the existing one from [16] by a factor of $K / log K$. The existing bound is not explicitly shown, but the authors’ bound has the form $log(K) log(T) \sum_i \Delta_i^{-1}$, so I assume the existing bound refers to the bound $K \log(T) \sum_i \Delta_i^{-1}$ from [16]. However, as best I can tell, this bound from [16] is specialized to cascading bandits from a more general setting; if one restricts to the special case like in the original cascading bandit paper [15], the bound $\log(T) \sum_i \Delta_i^{-1}$ from Theorems 2 and 3 in [15] actually seems better than the bound from the current paper ... or at least, much better than the bound in [16], since [15] has no explicit multiplicative dependence on $K$? (Note: [15] does not refer to its model as "disjunctive", but I believe it's the same formulation.)~~

Update post-rebuttal: This question has been satisfactorily addressed and I remain in support of acceptance.
limitations: Overall, I feel the limitations were acknowledged -- for example, the assumptions are clearly stated in each of the theorems, Remark 3 acknowledges that additional assumptions are needed to ensure the proposed Condition 3 implies the existing Condition 2, etc. In terms of negative societal impact, the authors simply state (in the checklist) that there is no foreseeable impact. Personally, I feel this view is somewhat narrow -- while the paper is theoretical, the algorithms could obviously have real-world impact if deployed -- but I understand the authors' point and view this more as a difference of opinion than an objective weakness.
review_title: null

Meta-review: metareview: Thank the authors for their submission.

The paper studies combinatorial multi-armed bandit with probabilistically triggered arms. That is an MAB setting in which, at each round, the learner chooses a subset of the arms and obtains a reward that is some function of expected rewards of the chosen arms. In addition, the learner only observes feedback on a random subset of her chosen arms (triggered arms). 

The paper relaxes a smoothness assumption laid by a previous work, and further improves the dependence on K in the regret bound, where K is the batch size (maximum number of triggered arms)
The authors provide computationally-efficient algorithms that are based on Bernstein concentration inequality, facilitating the improved bounds. 
The paper is well-written and organized, and the theoretical results are sound.
confidence: Certain
Decision: Accept