# Cascading Bandits: Learning to Rank in the Cascade Model

arXiv: https://arxiv.org/abs/1502.02763 · HTML: https://mlsanity.com/paper/1502.02763/

## Key facts

- Cited by 77 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Feb 2015.

## Built on by (most cited first, 30 of 77)

- [Advances and Challenges in Conversational Recommender Systems: A Survey](https://mlsanity.com/paper/2101.09459/) (2021)
- [Cost-Effective Online Multi-LLM Selection with Versatile Reward Models](https://mlsanity.com/paper/2405.16587/) (2024)
- [Hierarchical Bayesian Bandits](https://mlsanity.com/paper/2111.06929/) (2021)
- [Multinomial Logit Contextual Bandits: Provable Optimality and Practicality](https://mlsanity.com/paper/2103.13929/) (2021)
- [Measuring Recommender System Effects with Simulated Users](https://mlsanity.com/paper/2101.04526/) (2021)
- [Deep Hierarchy in Bandits](https://mlsanity.com/paper/2202.01454/) (2022)
- [Heterogeneous Multi-player Multi-armed Bandits: Closing the Gap and Generalization](https://mlsanity.com/paper/2110.14622/) (2021)
- [A Survey on LLM-based Conversational User Simulation](https://mlsanity.com/paper/2604.24977/) (2026)
- [Optimal Design for Human Preference Elicitation](https://mlsanity.com/paper/2404.13895/) (2024)
- [Combinatorial Neural Bandits](https://mlsanity.com/paper/2306.00242/) (2023)
- [Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms](https://mlsanity.com/paper/2208.14837/) (2022)
- [Towards Scalable and Robust Structured Bandits: A Meta-Learning Framework](https://mlsanity.com/paper/2202.13227/) (2022)
- [Minimax Regret for Cascading Bandits](https://mlsanity.com/paper/2203.12577/) (2022)
- [Active Learning for Direct Preference Optimization](https://mlsanity.com/paper/2503.01076/) (2025)
- [Be Greedy in Multi-Armed Bandits](https://mlsanity.com/paper/2101.01086/) (2021)
- [Fast online inference for nonlinear contextual bandit based on Generative Adversarial Network](https://mlsanity.com/paper/2202.08867/) (2022)
- [Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyond](https://mlsanity.com/paper/2406.01386/) (2024)
- [Robust Generalization and Safe Query-Specialization in Counterfactual Learning to Rank](https://mlsanity.com/paper/2102.05990/) (2021)
- [PairRank: Online Pairwise Learning to Rank by Divide-and-Conquer](https://mlsanity.com/paper/2103.00368/) (2021)
- [Federated Multi-Armed Bandits Under Byzantine Attacks](https://mlsanity.com/paper/2205.04134/) (2022)
- [Online Learning and Bandits with Queried Hints](https://mlsanity.com/paper/2211.02703/) (2022)
- [Adversarial Attacks on Online Learning to Rank with Click Feedback](https://mlsanity.com/paper/2305.17071/) (2023)
- [Competing for Shareable Arms in Multi-Player Multi-Armed Bandits](https://mlsanity.com/paper/2305.19158/) (2023)
- [Adversarial Attacks on Online Learning to Rank with Stochastic Click Models](https://mlsanity.com/paper/2305.19218/) (2023)
- [Federated Contextual Cascading Bandits with Asynchronous Communication and Heterogeneous Users](https://mlsanity.com/paper/2402.16312/) (2024)
- [Probably Approximately Precision and Recall Learning](https://mlsanity.com/paper/2411.13029/) (2024)
- [Offline Learning for Combinatorial Multi-armed Bandits](https://mlsanity.com/paper/2501.19300/) (2025)
- [Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality](https://mlsanity.com/paper/2505.18828/) (2025)
- [Safe Data Collection for Offline and Online Policy Learning](https://mlsanity.com/paper/2111.04835/) (2021)
- [Cascading Reinforcement Learning](https://mlsanity.com/paper/2401.08961/) (2024)

## Abstract (arXiv)

A search engine usually outputs a list of K web pages. The user examines this list, from the first web page to the last, and chooses the first attractive page. This model of user behavior is known as the cascade model. In this paper, we propose cascading bandits, a learning variant of the cascade model where the objective is to identify K most attractive items. We formulate our problem as a stochastic combinatorial partial monitoring problem. We propose two algorithms for solving it, CascadeUCB1 and CascadeKL-UCB. We also prove gap-dependent upper bounds on the regret of these algorithms and derive a lower bound on the regret in cascading bandits. The lower bound matches the upper bound of CascadeKL-UCB up to a logarithmic factor. We experiment with our algorithms on several problems. The algorithms perform surprisingly well even when our modeling assumptions are violated.