| | |
| | |
Stat |
Members: 3645 Articles: 2'504'585 Articles rated: 2609
24 April 2024 |
|
| | | |
|
Article overview
| |
|
Thompson Sampling for Combinatorial Semi-bandits with Sleeping Arms and Long-Term Fairness Constraints | Zhiming Huang
; Yifan Xu
; Bingshan Hu
; Qipeng Wang
; Jianping Pan
; | Date: |
14 May 2020 | 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}{2eta} +
Oleft(frac{sqrt{mNTln T}}{T}
ight)$, 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
ightarrow 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. | Source: | arXiv, 2005.6725 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |