# Minimax Regret for Cascading Bandits

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 54 references that are in the map.
- First posted on arXiv 23 Mar 2022.

## Builds on (most cited first, 12 of 12)

- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Cascading Bandits: Learning to Rank in the Cascade Model](https://mlsanity.com/paper/1502.02763/) (2015)
- [Cascading Bandits for Large-Scale Recommendation Problems](https://mlsanity.com/paper/1603.05359/) (2016)
- [Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications](https://mlsanity.com/paper/1703.01610/) (2017)
- [Combinatorial Cascading Bandits](https://mlsanity.com/paper/1507.04208/) (2015)
- [TopRank: A practical algorithm for online stochastic ranking](https://mlsanity.com/paper/1806.02248/) (2018)
- [Online Learning to Rank in Stochastic Click Models](https://mlsanity.com/paper/1703.02527/) (2017)
- [Online Clustering of Contextual Cascading Bandits](https://mlsanity.com/paper/1711.08594/) (2017)
- [Online Learning to Rank with Features](https://mlsanity.com/paper/1810.02567/) (2018)
- [Thompson Sampling Algorithms for Cascading Bandits](https://mlsanity.com/paper/1810.01187/) (2018)
- [Cascading Non-Stationary Bandits: Online Learning to Rank in the Non-Stationary Cascade Model](https://mlsanity.com/paper/1905.12370/) (2019)
- [Nearly Optimal Algorithms for Piecewise-Stationary Cascading Bandits](https://mlsanity.com/paper/1909.05886/) (2019)

## Built on by (most cited first, 10 of 10)

- [Contextual Combinatorial Bandits with Probabilistically Triggered Arms](https://mlsanity.com/paper/2303.17110/) (2023)
- [Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms](https://mlsanity.com/paper/2208.14837/) (2022)
- [Adversarial Attacks on Online Learning to Rank with Click Feedback](https://mlsanity.com/paper/2305.17071/) (2023)
- [Adversarial Attacks on Online Learning to Rank with Stochastic Click Models](https://mlsanity.com/paper/2305.19218/) (2023)
- [Offline Learning for Combinatorial Multi-armed Bandits](https://mlsanity.com/paper/2501.19300/) (2025)
- [Cascading Reinforcement Learning](https://mlsanity.com/paper/2401.08961/) (2024)
- [Adversarial Attacks on Combinatorial Multi-Armed Bandits](https://mlsanity.com/paper/2310.05308/) (2023)
- [Overcoming Prior Misspecification in Online Learning to Rank](https://mlsanity.com/paper/2301.10651/) (2023)
- [Online Learning to Rank under Corruption: A Robust Cascading Bandits Approach](https://mlsanity.com/paper/2511.03074/) (2025)
- [Stochastic Reset Pathfinding: Path-Level Regret for Cascading Bandits over Graph Paths](https://mlsanity.com/paper/2607.15440/) (2026)

## Abstract (arXiv)

Cascading bandits is a natural and popular model that frames the task of learning to rank from Bernoulli click feedback in a bandit setting. For the case of unstructured rewards, we prove matching upper and lower bounds for the problem-independent (i.e., gap-free) regret, both of which strictly improve the best known. A key observation is that the hard instances of this problem are those with small mean rewards, i.e., the small click-through rates that are most relevant in practice. Based on this, and the fact that small mean implies small variance for Bernoullis, our key technical result shows that variance-aware confidence sets derived from the Bernstein and Chernoff bounds lead to optimal algorithms (up to log terms), whereas Hoeffding-based algorithms suffer order-wise suboptimal regret. This sharply contrasts with the standard (non-cascading) bandit setting, where the variance-aware algorithms only improve constants. In light of this and as an additional contribution, we propose a variance-aware algorithm for the structured case of linear rewards and show its regret strictly improves the state-of-the-art.