%0 Journal Article %1 huang2020thompson %A Huang, Zhiming %A Xu, Yifan %A Hu, Bingshan %A Wang, Qipeng %A Pan, Jianping %D 2020 %K bandits bayesian constrains sampling %T Thompson Sampling for Combinatorial Semi-bandits with Sleeping Arms and Long-Term Fairness Constraints %U http://arxiv.org/abs/2005.06725 %X We study the combinatorial sleeping multi-armed semi-bandit problem with long-term fairness constraints~(CSMAB-F). To address the problem, we adopt Thompson Sampling~(TS) to maximize the total rewards and use virtual queue techniques to handle the fairness constraints, and design an algorithm called TS with beta priors and Bernoulli likelihoods for CSMAB-F~(TSCSF-B). Further, we prove TSCSF-B can satisfy the fairness constraints, and the time-averaged regret is upper bounded by $N2\eta + Ołeft(\sqrtmNTTT\right)$, where $N$ is the total number of arms, $m$ is the maximum number of arms that can be pulled simultaneously in each round~(the cardinality constraint) and $\eta$ is the parameter trading off fairness for rewards. By relaxing the fairness constraints (i.e., let $\eta ınfty$), the bound boils down to the first problem-independent bound of TS algorithms for combinatorial sleeping multi-armed semi-bandit problems. Finally, we perform numerical experiments and use a high-rating movie recommendation application to show the effectiveness and efficiency of the proposed algorithm.

@article{huang2020thompson, abstract = {We study the combinatorial sleeping multi-armed semi-bandit problem with long-term fairness constraints~(CSMAB-F). To address the problem, we adopt Thompson Sampling~(TS) to maximize the total rewards and use virtual queue techniques to handle the fairness constraints, and design an algorithm called \emph{TS with beta priors and Bernoulli likelihoods for CSMAB-F~(TSCSF-B)}. Further, we prove TSCSF-B can satisfy the fairness constraints, and the time-averaged regret is upper bounded by $\frac{N}{2\eta} + O\left(\frac{\sqrt{mNT\ln T}}{T}\right)$, where $N$ is the total number of arms, $m$ is the maximum number of arms that can be pulled simultaneously in each round~(the cardinality constraint) and $\eta$ is the parameter trading off fairness for rewards. By relaxing the fairness constraints (i.e., let $\eta \rightarrow \infty$), the bound boils down to the first problem-independent bound of TS algorithms for combinatorial sleeping multi-armed semi-bandit problems. Finally, we perform numerical experiments and use a high-rating movie recommendation application to show the effectiveness and efficiency of the proposed algorithm.}, added-at = {2020-05-15T14:22:56.000+0200}, author = {Huang, Zhiming and Xu, Yifan and Hu, Bingshan and Wang, Qipeng and Pan, Jianping}, biburl = {https://www.bibsonomy.org/bibtex/2b5e2ceef5efcfe5b54aa6daf68e8b13b/kirk86}, description = {[2005.06725] Thompson Sampling for Combinatorial Semi-bandits with Sleeping Arms and Long-Term Fairness Constraints}, interhash = {16ebe5d5d1d30d652bc09f5ed758fbd8}, intrahash = {b5e2ceef5efcfe5b54aa6daf68e8b13b}, keywords = {bandits bayesian constrains sampling}, note = {cite arxiv:2005.06725}, timestamp = {2020-05-15T14:22:56.000+0200}, title = {Thompson Sampling for Combinatorial Semi-bandits with Sleeping Arms and Long-Term Fairness Constraints}, url = {http://arxiv.org/abs/2005.06725}, year = 2020 }