Contextual Combinatorial Cascading Thompson Sampling

Abstract

We design and analyze contextual combinatorial cascading Thompson sampling ($C^3$-TS). $C^3$-TS is a Bayesian heuristic to balance the exploration-exploitation tradeoff in the cascading bandit model. And it incorporates the linear structure to share information among different items. These two important features allow us to prove an expected cumulative regret bound of the form ${\tilde{O}}(d\sqrt{KT})$, where d and K are the dimension of the feature space and the length of the chosen list respectively, and T is the number of time steps. This regret bound matches the regret bounds for the state-of-the-art UCB-based algorithms. More importantly, it is the first theoretical guarantee on a contextual Thompson sampling algorithm for cascading bandit problem. Empirical results demonstrate the advantage of $C^3$-TS over existing UCB-based algorithms and non-contextual TS in terms of both the cumulative reward and time complexity.