Batched Cascading Bandits

Cascading bandits model ordered recommendation under stochastic prefix feedback: in each round, a learner selects and orders $K$ out of $L$ items but observes outcomes only up to the first click. Standard cascading bandit algorithms update after every round, which can be impractical in real-world scenarios where instant feedback is not always available. We study batched cascading bandits, where the learner commits all recommendation lists in a batch using the feedback available at its start and updates the policy only at its batch endpoint. To address different batch constraints, we propose two algorithms: Batched Cascade Successive Accepts and Rejects (BC-SAR) and Batched Cascade Upper Confidence Bound (BC-UCB). Both algorithms combine first-position rotation with mechanisms tailored to their respective batch constraints. On homogeneous-gap instances with common attraction-probability gap $\Delta$ and constant algorithm parameters, BC-SAR has expected regret $\mathcal{O}(K(L-K)\log (LT)/\Delta )$ using $\mathcal{O}(\log T)$ batches. BC-UCB has expected regret $\mathcal{O}((L-K)\log (LT)/\Delta )$ using $\mathcal{O}(L\log (1+KT/L))$ batches. Numerical experiments evaluate our algorithms and examine their empirical performance under batched feedback.