Nearly Optimal Algorithms for Piecewise-Stationary Cascading Bandits

Abstract

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, \texttt{GLRT-CascadeUCB} and \texttt{GLRT-CascadeKL-UCB}, are developed and shown to ensure regret upper bounds on the order of $\mathcal{O}(\sqrt{NLT\log T})$, 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 (\sqrt{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.

References in corpus (12)

• Unbiased Offline Evaluation of Contextual-bandit-based News Article Recommendation Algorithms
• The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond
• Combinatorial Bandits Revisited
• Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms
• More Adaptive Algorithms for Adversarial Bandits
• Online Learning to Rank in Stochastic Click Models
• Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Bandit
• Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications
• Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals
• Combinatorial Semi-Bandit in the Non-Stationary Environment
• Stochastic Bandits with Delay-Dependent Payoffs
• Thompson Sampling Algorithms for Cascading Bandits

Cited by in corpus (4)

• Nonstationary Reinforcement Learning with Linear Function Approximation
• Optimizing for the Future in Non-Stationary MDPs
• Combinatorial Semi-Bandit in the Non-Stationary Environment
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations