Venue: NeurIPS 2022 Conference

Reviews:

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 revisits the cascading bandits problem where the decision maker must choose an ordered list of $K$ distinct items (from a universe of $L \geqslant K$ items) at each round $t\in\left\lbrace 1,...,n \right\rbrace$ to display to users arriving sequentially. Each item in the universe has a latent attraction probability; users are homogeneous, scan the ordered list displayed to them in a fixed order (left-to-right), and click on the first item that attracts them (subsequent items are left unexamined). The decision maker only observes Bernoulli feedback (governed by the underlying attraction probabilities) for the items that were examined (including the one that was ultimately clicked upon). Note that a user may potentially scan through an entire list of $K$ items and click on none; this would be denoted by a $K$-dimensional vector of all $0$'s. The goal of the decision maker is to maximize the total number of clicks (in expectation) over $n$ rounds.

For the aforementioned problem, the authors study the regret minimization problem where the learner competes against an oracle that always plays an action (an ordered list of $K$ distinct items) that maximizes the click probability.

The paper proposes matching problem-independent (worst-case) upper and lower bounds (the former based on a UCB approach) for the tabular version of the problem described above. For the linear setting, the authors propose an upper bound (again, using a UCB-based approach) that improves upon the current best known.
strengths_and_weaknesses: The paper is well-written with a clear technical exposition. The observation that variance-aware algorithms lead to bounds that are order-wise better in this setting than their counterparts relying on fixed variance proxies is an interesting one in light of known results for the standard MAB setting.

I did not evaluate the technical details very rigorously, but proof sketches and arguments appear correct. I reckon this paper makes sound theoretical contributions to this area and would therefore vote for an accept.
questions: For the tabular case, the bounds match in $n$ and $L$ (up to log factors). Would it be possible to capture explicitly dependencies also w.r.t. $K$?
limitations: Appears to be well-addressed.
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 studies the cascading bandits in both tabular and linear cases. The paper's main contribution is to find out that the hardest problem instances (where means are small) also yield small variance, meaning that the estimation for these instances is naturally more accurate. Based on this observation, the authors use variance-aware algorithms to give improved regret bounds, reducing the $K$-related factors. Specifically, for the tabular case, the authors show that the previous Cascade-KL and Cascade-V algorithms can achieve the improved regret upper bound by a factor of $O(K)$, compared with previous works. The authors also show that the newly proposed bounds are optimal up to log terms, using their newly proposed lower bounds. For the linear case, the authors propose the CascadeWOFUL algorithm and use the mean to replace the unknown variance. The regret bound of CascadeWOFUL improves the existing results by a factor of $O(\sqrt{K\min(d,K)})$. Finally, the experiments show that the proposed algorithms achieve superior performance compared to baselines.
strengths_and_weaknesses: Strength.

1. The current paper makes solid contributions to the cascading bandits and combinatorial multi-armed bandits literature. For the tabular case, both upper and lower bounds strictly improve the existing works. For the linear case, the derived upper bound also significantly improves the existing works.

2. The presentation is very clear, and I enjoy the flow of showing their results. The intuition of the algorithm design and the proof is quite clear and easy to follow. Both the novelty and the challenge of the problem are properly illustrated.

3. Beyond the theoretical analysis, the authors also give promising empirical results, which adds more practical value to their work.

Weakness.
1. I wonder what the gap-dependent regret bound is. I believe the distribution-dependent regret bound is harder to derive, since the gap-independent regret bound can be derived by optimizing the gap $\Delta$ using the distribution-dependent bound. Can the gap-dependent bound be easily shown using the current paper’s analysis?

2. In appendix A, the authors claim Li and Zhang [2018] requires additional assumptions. In fact, the additional assumptions (cluster regularity, user uniformness and item regularity) are to deal with the varying $\theta$. If $\theta$ are the same, they are not needed to give the result of Corollary 3. So I think the authors could double-check their claim.

questions: Please justify the questions proposed in the weakness part.
limitations: The authors adequately addressed the limitations and potential negative societal impact of their work.
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 cascading-bandits problem considers a scenario where the agent aims to choose K out of L items, and each item corresponds to an independent Bernoulli random variable. In each iteration, the agent chooses an ordered list of K items, and the underlying variable is revealed in the same order until a 1 is observed. So the overall reward and regret for each action can be written in terms of the product of the probabilities of getting 0 for the K chosen actions. 

In prior works, the best known upper bound for the optimal regret given n iterations is increasing in K. The best known lower bound is decreasing in K, leaving an otherwise gap. This work completely resolves this problem for $K\leq L/4$.  
strengths_and_weaknesses: The main strength of this work is the complete resolution of cascading bandits, at least for $K\leq L/4$. Besides the results, the techniques/algorithms proposed in this work are also interesting. Note that when the reward function is linear (i.e., being the sum of expected values for the K items), the minimax regret is known. Cascading bandits have a non-linear regret function, and I imagined the solution of cascading bandits would be something that handles the non-linearity through sophisticated analysis. The presented algorithm uses KL divergence, which is surprisingly clean. 

Perhaps one limitation of this work is that the lower bound only holds for $L/K\geq C$ with a constant $C>1$, leaving the minimax regret for the $K\rightarrow L$ regime open. The minimax regret in that regime is known to follow a different rule, and it would be of interest whether the proposed solution or techniques can provide optimal bounds in that regime as well.
questions: Theorem 1 is stated only for the discrete case of L/K being an integer. As far as I understand, this should imply the same lower bound for any $L/K\geq 4$ (within a constant factor), or even $L/K\geq C$ for general $C>1$. Is there any reason that the integer constraint is imposed in the theorem statement?
limitations: --
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 work studied the regret minimization in cascading bandits. It closed the gap for the upper and lower bounds on the regret in the tabular setting by developing a variance-aware UCB-based algorithm. It also studied the linear setting and evaluated the algorithms with numerical experiments. 
strengths_and_weaknesses: Strengths: This work is easy to follow and the claims are generally sound. It improved the existing upper and lower bounds and closed the gap in the tabular setting. It also discussed why involving variance in the design of the algorithm can help. The numerical experiments compared different UCB-type algorithms.

Weaknesses: The key difference between the analysis in this work and previous work should be better elaborated, and more experiments are appreciated. See the "Questions" part for more details.
questions: 1. What are the key analytical challenges? These should be described in greater detail in Section 5. The current analytical framework in Section 5 looks quite standard for most cascading bandit algorithms.
2. Is it possible to also provide a lower bound in the linear setting? This may further complete the analysis in cascading bandits.
3. As shown in previous works such as Zhong et al. [2021], Thompson sampling algorithms can also be applied in cascading bandits, why don't the authors compare them in numerical experiments?

limitations: I don't see any issue regarding societal impact.
review_title: null

Meta-review: metareview: All the reviewers were generally happy with this paper. There were some comments about a better experimental section and maybe a better discussion of results and extensions (e.g. gap-dependent bounds, what happens in the K->L regime), but everyone felt that the manuscript as written was solid enough to merit acceptance. I encourage the authors to incorporate the discussions on these points in the final manuscript.





confidence: Certain
Decision: Accept