Topic-Aware Contextual Cascading Bandits

We propose a contextual cascading bandit model in which the click probability at each position depends on both the displayed item and the topics of previously shown items. This captures how previously displayed topics affect later click probabilities, allowing different topic orders to induce different user responses. Unlike standard cascading bandits, the optimal cascade is no longer determined only by the selected set of items, since the ordering itself affects the expected reward. To address the resulting planning challenge, we reformulate cascade construction as a Markov decision process whose state summarizes the previously selected topics. Based on this formulation, we develop an optimism-based algorithm and prove a regret upper bound of $\widetilde{\mathcal O}(\bar p^{\frac{K-1}{2}}d\sqrt{T})$, where $d$ is the number of unknown parameters, $T$ is the horizon, $K$ is the cascade length, and $\bar p<1$ upper bounds the no-click probability of an examined item. A key implication is that the regret decreases with the cascade length $K$, a phenomenon that had not been established even in order-insensitive contextual cascading bandits. We further provide a local regret lower bound showing that this decreasing dependence on $K$ is intrinsic, and validate our theory through experiments with topic-order-dependent click probabilities.