# Thompson Sampling for Combinatorial Semi-bandits with Sleeping Arms and Long-Term Fairness Constraints

arXiv: https://arxiv.org/abs/2005.06725 · HTML: https://mlsanity.com/paper/2005.06725/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 May 2020.

## Built on by (most cited first, 3 of 3)

- [Thompson Sampling for (Combinatorial) Pure Exploration](https://mlsanity.com/paper/2206.09150/) (2022)
- [Combinatorial Allocation Bandits with Nonlinear Arm Utility](https://mlsanity.com/paper/2603.07005/) (2026)
- [Learning to Assign Prediction Tasks to Agents with Capacity Constraints](https://mlsanity.com/paper/2605.27999/) (2026)

## Abstract (arXiv)

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 fracN2η + Oleft(frac√mNTln TTright), 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 η is the parameter trading off fairness for rewards. By relaxing the fairness constraints (i.e., let η rightarrow ∞), 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.