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.

该研究设计并分析了CascadeBAI算法，该算法适用于级联赌博框架中找到最佳集合的K个项目，提出了一种新的随机变量类型作为左侧子高斯随机变量，使用一个紧密的Bernstein类型浓度不等式，推导出CascadeBAI的时间复杂度的上界，并且通过推导出时间复杂度下界显示CascadeBAI在某些实用范围内的性能是最优的，并通过广泛的数值模拟证实了CascadeBAI的有效性以及时间复杂度上限的紧密性。

基于固定置信度的级联赌博机的最佳臂识别