2019/09/12 by Lingda Wang, Huozhi Zhou, Wang, Lingda +7 · 1 citation
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Optimization and Search Problems #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.1909.05886
openalex publication_date 2019/09/12 · arxiv created 2020/02/17 · arxiv updated 2020/02/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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, GLRT-CascadeUCB and GLRT-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 Ω(√(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.