True Impact of Cascade Length in Contextual Cascading Bandits

We revisit the contextual cascading bandit, where a learning agent recommends an ordered list (cascade) of items, and a user scans the list sequentially, stopping at the first attractive item. Although cascading bandits underpin various applications including recommender systems and search engines, the role of the cascade length K in shaping regret has remained unclear. Contrary to prior results that regret grows with K, we prove that regret actually decreases once K is large enough. Leveraging this insight, we design a new upper-confidence-bound algorithm built on online mirror descent that attains the sharpest known regret upper bound, Õ minK pK-1 , 1d √ T for contextual cascading bandits. To complement this new regret upper bound, we provide a nearly matching lower bound of Ω minKp K-1 , 1d √ T , where 0 ≤ p ≤ p < 1. Together, these results fully characterize how regret truly scales with K, thereby closing the theoretical gap for contextual cascading bandits. Finally, comprehensive experiments validate our theoretical results and show the effectiveness of our proposed method. K pK-1 , revealing that the regret can decrease with larger cascade length. This result is further supported by a matching problem-dependent regret lower bound, which confirms the correct Kscalability of our upper bound. To the best of our knowledge, this is the first lower bound analysis for contextual cascading bandits. Finally, the proposed analysis is directly applicable to the contextual cascading linear bandits, where the regret bound Õ(minK pK-1 , 1 d √ T ) remains valid, demonstrating that the K pK-1 term captures an intrinsic property of the cascade structure rather than a peculiarity of the feedback model.

Our main contributions are summarized as follows.

• We propose a UCB algorithm for cascading logistic bandits and establish the T -step regret upper bound of Õ(min K pK-1 , 1 d √ T ) where 0 ≤ p < 1 (Theorem 5.6).

• To our best knowledge, this regret upper bound is the tightest bound among all the existing regret bounds for contextual cascading bandits. In contrast to previous studies that suggest the bound increases with K, our finding demonstrates that the regret bound decreases with sufficiently large K.

• By leveraging online mirror descent for parameter estimation in cascading logistic bandits, our algorithm achieves constant per-round computational and storage costs, independent of T , thereby ensuring computational efficiency.

• We also derive an N -independent lower bound on the regret in cascading logistic bandits as Ω(min Kp K-1 , 1 d √ T ) (in Theorem 5.7), where 0 ≤ p ≤ p < 1. To the best of our knowledge, this is the first derivation of a lower bound in contextual cascading bandits.

• We show that the regret bound derived in the logistic setting also holds in the linear model under mild assumptions, highlighting the generality of our theoretical results.