# Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting

arXiv: https://arxiv.org/abs/2001.08655 · HTML: https://mlsanity.com/paper/2001.08655/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jan 2020.

## Built on by (most cited first, 5 of 5)

- [Optimal Clustering with Bandit Feedback](https://mlsanity.com/paper/2202.04294/) (2022)
- [Best Arm Identification in Restless Markov Multi-Armed Bandits](https://mlsanity.com/paper/2203.15236/) (2022)
- [Fixed Budget is No Harder Than Fixed Confidence in Best-Arm Identification up to Logarithmic Factors](https://mlsanity.com/paper/2602.03972/) (2026)
- [CoCoB: Adaptive Collaborative Combinatorial Bandits for Online Recommendation](https://mlsanity.com/paper/2505.03840/) (2025)
- [Cascading Bandits With Feedback](https://mlsanity.com/paper/2511.10938/) (2025)

## Abstract (arXiv)

We design and analyze CascadeBAI, an algorithm for finding the best set of K items, also called an arm, within the framework of cascading bandits. An upper bound on the time complexity of CascadeBAI is derived by overcoming a crucial analytical challenge, namely, that of probabilistically estimating the amount of available feedback at each step. To do so, we define a new class of random variables (r.v.'s) which we term as left-sided sub-Gaussian r.v.'s; these are r.v.'s whose cumulant generating functions (CGFs) can be bounded by a quadratic only for non-positive arguments of the CGFs. This enables the application of a sufficiently tight Bernstein-type concentration inequality. We show, through the derivation of a lower bound on the time complexity, that the performance of CascadeBAI is optimal in some practical regimes. Finally, extensive numerical simulations corroborate the efficacy of CascadeBAI as well as the tightness of our upper bound on its time complexity.