# Nearly Optimal Algorithms for Piecewise-Stationary Cascading Bandits

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Sep 2019.

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

- [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)

## Abstract (arXiv)

Cascading bandit (CB) is a popular model for web search and online advertising, where an agent aims to learn the K most attractive items out of a ground set of size L during the interaction with a user. However, the stationary CB model may be too simple to apply to real-world problems, where user preferences may change over time. Considering piecewise-stationary environments, two efficient algorithms, textttGLRT-CascadeUCB and textttGLRT-CascadeKL-UCB, are developed and shown to ensure regret upper bounds on the order of O(√NLTlogT), where N is the number of piecewise-stationary segments, and T is the number of time slots. At the crux of the proposed algorithms is an almost parameter-free change-point detector, the generalized likelihood ratio test (GLRT). Comparing with existing works, the GLRT-based algorithms: i) are free of change-point-dependent information for choosing parameters; ii) have fewer tuning parameters; iii) improve at least the L dependence in regret upper bounds. In addition, we show that the proposed algorithms are optimal (up to a logarithm factor) in terms of regret by deriving a minimax lower bound on the order of Omega(√NLT) for piecewise-stationary CB. The efficiency of the proposed algorithms relative to state-of-the-art approaches is validated through numerical experiments on both synthetic and real-world datasets.