Thompson Sampling Algorithms for Cascading Bandits
arXiv:1810.01187
Abstract
Motivated by the pressing need for efficient optimization in online recommender systems, we revisit the cascading bandit model proposed by Kveton et al. (2015). While Thompson sampling (TS) algorithms have been shown to be empirically superior to Upper Confidence Bound (UCB) algorithms for cascading bandits, theoretical guarantees are only known for the latter. In this paper, we first provide a problem-dependent upper bound on the regret of a TS algorithm with Beta-Bernoulli updates; this upper bound is tighter than a recent derivation under a more general setting by Huyuk and Tekin (2019). Next, we design and analyze another TS algorithm with Gaussian updates, TS-Cascade. TS-Cascade achieves the state-of-the-art regret bound for cascading bandits. Complementarily, we consider a linear generalization of the cascading bandit model, which allows efficient learning in large cascading bandit problem instances. We introduce and analyze a TS algorithm, which enjoys a regret bound that depends on the dimension of the linear model but not the number of items. Finally, by using information-theoretic techniques and judiciously constructing cascading bandit instances, we derive a nearly matching regret lower bound for the standard model. Our paper establishes the first theoretical guarantees on TS algorithms for stochastic combinatorial bandit problem model with partial feedback. Numerical experiments demonstrate the superiority of the proposed TS algorithms compared to existing UCB-based ones.
arXiv comment62 pages, 6 figures
References in corpus (15)
- A Contextual-Bandit Approach to Personalized News Article Recommendation
- Analysis of Thompson Sampling for the multi-armed bandit problem
- Thompson Sampling for Contextual Bandits with Linear Payoffs
- Further Optimal Regret Bounds for Thompson Sampling
- Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits
- Combinatorial Bandits Revisited
- Cascading Bandits: Learning to Rank in the Cascade Model
- Matroid Bandits: Fast Combinatorial Optimization with Learning
- Combinatorial Cascading Bandits
- Online Learning to Rank in Stochastic Click Models
- DCM Bandits: Learning to Rank with Multiple Clicks
- Efficient Learning in Large-Scale Combinatorial Semi-Bandits
- Thompson Sampling for Combinatorial Semi-Bandits
- Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications
- Thompson Sampling for the MNL-Bandit