True Impact of Cascade Length in Contextual Cascading Bandits

Abstract

We revisit the contextual cascading bandit, where a learning agent recommends an ordered list ($\text{textit{cascade}}$) of items and a user scans the list sequentially, stopping at the first attractive item. Although cascading bandits underpin various search and recommendation engines, the role of the cascade length $K$ in shaping regret has remained ambiguous. Contrary to prior results that regret grows with $K$, we prove that in the contextual setting it actually $\text{textit{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, $\tilde{\mathcal{O}}(K{\overline{p}}^{K-1}d\sqrt{T})$ for contextual cascading bandits. To complement this new regret upper bound, we match it with a lower bound of $\mathrm{\Omega }(K{\underset{―}{p}}^{K-1}d\sqrt{T})$, where $0\le \underset{―}{p}\le \overline{p}<1$. Together, these results fully characterize how regret truly scales with $K$ and close the theoretical gap for contextual cascading bandits. Finally, extensive experiments validate our theoretical results and show the effectiveness of our proposed method.

Joongkyu Lee

Ph.D. candidate in Data Science