Research Article
Collaborative Contextual Combinatorial Cascading Thompson Sampling
@INPROCEEDINGS{10.1007/978-3-030-30146-0_9, author={Zhenyu Zhu and Liusheng Huang and Hongli Xu}, title={Collaborative Contextual Combinatorial Cascading Thompson Sampling}, proceedings={Collaborative Computing: Networking, Applications and Worksharing. 15th EAI International Conference, CollaborateCom 2019, London, UK, August 19-22, 2019, Proceedings}, proceedings_a={COLLABORATECOM}, year={2019}, month={8}, keywords={}, doi={10.1007/978-3-030-30146-0_9} }- Zhenyu Zhu
Liusheng Huang
Hongli Xu
Year: 2019
Collaborative Contextual Combinatorial Cascading Thompson Sampling
COLLABORATECOM
Springer
DOI: 10.1007/978-3-030-30146-0_9
Abstract
We design and analyze collaborative contextual combinatorial cascading Thompson sampling (-TS). -TS is a Bayesian heuristic to address the cascading bandit problem in the collaborative environment. -TS utilizes posterior sampling strategy to balance the exploration-exploitation tradeoff and it also incorporates the collaborative effect to share information across similar users. Utilizing these two novel features, we prove that the regret upper bound for -TS is , where is the dimension of the feature space, is the number of users, is the number of clusters, is the length of the recommended list and is the time horizon. This regret upper bound matches the theoretical guarantee for UCB-like algorithm in the same settings. We also conduct a set of simulations comparing -TS with the state-of-the-art algorithms. The empirical results demonstrate the advantage of our algorithm over existing works.