# Combinatorial Sleeping Bandits with Fairness Constraints

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

## Key facts

- Cited by 68 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jan 2019.

## Built on by (most cited first, 30 of 68)

- [Fairness of Exposure in Stochastic Bandits](https://mlsanity.com/paper/2103.02735/) (2021)
- [An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints](https://mlsanity.com/paper/2102.05295/) (2021)
- [Low-Latency Federated Learning over Wireless Channels with Differential Privacy](https://mlsanity.com/paper/2106.13039/) (2021)
- [On Kernelized Multi-Armed Bandits with Constraints](https://mlsanity.com/paper/2203.15589/) (2022)
- [Survey on Fair Reinforcement Learning: Theory and Practice](https://mlsanity.com/paper/2205.10032/) (2022)
- [Planning to Fairly Allocate: Probabilistic Fairness in the Restless Bandit Setting](https://mlsanity.com/paper/2106.07677/) (2021)
- [Efficient Resource Allocation with Fairness Constraints in Restless Multi-Armed Bandits](https://mlsanity.com/paper/2206.03883/) (2022)
- [Recommendation Fairness: From Static to Dynamic](https://mlsanity.com/paper/2109.03150/) (2021)
- [Group Meritocratic Fairness in Linear Contextual Bandits](https://mlsanity.com/paper/2206.03150/) (2022)
- [No-regret Algorithms for Fair Resource Allocation](https://mlsanity.com/paper/2303.06396/) (2023)
- [Mitigating Disparity while Maximizing Reward: Tight Anytime Guarantee for Improving Bandits](https://mlsanity.com/paper/2208.09254/) (2022)
- [Learning While Scheduling in Multi-Server Systems with Unknown Statistics: MaxWeight with Discounted UCB](https://mlsanity.com/paper/2209.01126/) (2022)
- [Honor Among Bandits: No-Regret Learning for Online Fair Division](https://mlsanity.com/paper/2407.01795/) (2024)
- [Long-Term Resource Allocation Fairness in Average Markov Decision Process (AMDP) Environment](https://mlsanity.com/paper/2102.07120/) (2021)
- [BanditQ: Fair Bandits with Guaranteed Rewards](https://mlsanity.com/paper/2304.05219/) (2023)
- [Precarity: Modeling the Long Term Effects of Compounded Decisions on Individual Instability](https://mlsanity.com/paper/2104.12037/) (2021)
- [Fairer LP-based Online Allocation via Analytic Center](https://mlsanity.com/paper/2110.14621/) (2021)
- [Decentralized Task Offloading in Edge Computing: A Multi-User Multi-Armed Bandit Approach](https://mlsanity.com/paper/2112.11818/) (2021)
- [Towards Soft Fairness in Restless Multi-Armed Bandits](https://mlsanity.com/paper/2207.13343/) (2022)
- [Fairness and Sequential Decision Making: Limits, Lessons, and Opportunities](https://mlsanity.com/paper/2301.05753/) (2023)
- [Offline Learning for Combinatorial Multi-armed Bandits](https://mlsanity.com/paper/2501.19300/) (2025)
- [Efficient Learning-based Scheduling for Information Freshness in Wireless Networks](https://mlsanity.com/paper/2101.00257/) (2021)
- [Fair Online Bilateral Trade](https://mlsanity.com/paper/2405.13919/) (2024)
- [Keep Everyone Happy: Online Fair Division of Numerous Items with Few Copies](https://mlsanity.com/paper/2408.12845/) (2024)
- [Stochastic Bandits for Egalitarian Assignment](https://mlsanity.com/paper/2410.05856/) (2024)
- [Joint AP Probing and Scheduling: A Contextual Bandit Approach](https://mlsanity.com/paper/2108.03297/) (2021)
- [Ranked Prioritization of Groups in Combinatorial Bandit Allocation](https://mlsanity.com/paper/2205.05659/) (2022)
- [Fair Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/2408.17313/) (2024)
- [On the Low-Complexity of Fair Learning for Combinatorial Multi-Armed Bandit](https://mlsanity.com/paper/2501.00924/) (2025)
- [Improved Regret Bounds for Online Fair Division with Bandit Learning](https://mlsanity.com/paper/2501.07022/) (2025)

## Abstract (arXiv)

The multi-armed bandit (MAB) model has been widely adopted for studying many practical optimization problems (network resource allocation, ad placement, crowdsourcing, etc.) with unknown parameters. The goal of the player here is to maximize the cumulative reward in the face of uncertainty. However, the basic MAB model neglects several important factors of the system in many real-world applications, where multiple arms can be simultaneously played and an arm could sometimes be "sleeping". Besides, ensuring fairness is also a key design concern in practice. To that end, we propose a new Combinatorial Sleeping MAB model with Fairness constraints, called CSMAB-F, aiming to address the aforementioned crucial modeling issues. The objective is now to maximize the reward while satisfying the fairness requirement of a minimum selection fraction for each individual arm. To tackle this new problem, we extend an online learning algorithm, UCB, to deal with a critical tradeoff between exploitation and exploration and employ the virtual queue technique to properly handle the fairness constraints. By carefully integrating these two techniques, we develop a new algorithm, called Learning with Fairness Guarantee (LFG), for the CSMAB-F problem. Further, we rigorously prove that not only LFG is feasibility-optimal, but it also has a time-average regret upper bounded by fracN2η+fracβ1√mNTlogT+β2 NT, where N is the total number of arms, m is the maximum number of arms that can be simultaneously played, T is the time horizon, β1 and β2 are constants, and η is a design parameter that we can tune. Finally, we perform extensive simulations to corroborate the effectiveness of the proposed algorithm. Interestingly, the simulation results reveal an important tradeoff between the regret and the speed of convergence to a point satisfying the fairness constraints.