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
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.
Users
Please
log in to take part in the discussion (add own reviews or comments).