# Cascading Non-Stationary Bandits: Online Learning to Rank in the Non-Stationary Cascade Model

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 May 2019.

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

- [Minimax Regret for Cascading Bandits](https://mlsanity.com/paper/2203.12577/) (2022)
- [Off-Policy Evaluation for Action-Dependent Non-Stationary Environments](https://mlsanity.com/paper/2301.10330/) (2023)
- [BayesCNS: A Unified Bayesian Approach to Address Cold Start and Non-Stationarity in Search Systems at Scale](https://mlsanity.com/paper/2410.02126/) (2024)
- [On Learning to Rank Long Sequences with Contextual Bandits](https://mlsanity.com/paper/2106.03546/) (2021)
- [Optimizing Ranking Systems Online as Bandits](https://mlsanity.com/paper/2110.05807/) (2021)

## Abstract (arXiv)

Non-stationarity appears in many online applications such as web search and advertising. In this paper, we study the online learning to rank problem in a non-stationary environment where user preferences change abruptly at an unknown moment in time. We consider the problem of identifying the K most attractive items and propose cascading non-stationary bandits, an online learning variant of the cascading model, where a user browses a ranked list from top to bottom and clicks on the first attractive item. We propose two algorithms for solving this non-stationary problem: CascadeDUCB and CascadeSWUCB. We analyze their performance and derive gap-dependent upper bounds on the n-step regret of these algorithms. We also establish a lower bound on the regret for cascading non-stationary bandits and show that both algorithms match the lower bound up to a logarithmic factor. Finally, we evaluate their performance on a real-world web search click dataset.