# On the Regularity and Fairness of Combinatorial Multi-Armed Bandit

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 66 references that are in the map.
- First posted on arXiv 15 Sep 2025.

## Builds on (most cited first, 22 of 22)

- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Linear Stochastic Bandits Under Safety Constraints](https://mlsanity.com/paper/1908.05814/) (2019)
- [Achieving Fairness in the Stochastic Multi-armed Bandit Problem](https://mlsanity.com/paper/1907.10516/) (2019)
- [Combinatorial Sleeping Bandits with Fairness Constraints](https://mlsanity.com/paper/1901.04891/) (2019)
- [An Efficiency-boosting Client Selection Scheme for Federated Learning with Fairness Guarantee](https://mlsanity.com/paper/2011.01783/) (2020)
- [Multi-Armed Bandit Based Client Scheduling for Federated Learning](https://mlsanity.com/paper/2007.02315/) (2020)
- [Combinatorial Multi-Armed Bandit with General Reward Functions](https://mlsanity.com/paper/1610.06603/) (2016)
- [An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints](https://mlsanity.com/paper/2102.05295/) (2021)
- [On Kernelized Multi-Armed Bandits with Constraints](https://mlsanity.com/paper/2203.15589/) (2022)
- [Scheduling Policies for Minimizing Age of Information in Broadcast Wireless Networks](https://mlsanity.com/paper/1801.01803/) (2018)
- [Age of Information: Whittle Index for Scheduling Stochastic Arrivals](https://mlsanity.com/paper/1801.03422/) (2018)
- [A Whittle Index Approach to Minimizing Functions of Age of Information](https://mlsanity.com/paper/1908.10438/) (2019)
- [Rectified Pessimistic-Optimistic Learning for Stochastic Continuum-armed Bandit with Constraints](https://mlsanity.com/paper/2211.14720/) (2022)
- [Minimizing the Age of Information in Wireless Networks with Stochastic Arrivals](https://mlsanity.com/paper/1905.07020/) (2019)
- [Stochastic Network Utility Maximization with Unknown Utilities: Multi-Armed Bandits Approach](https://mlsanity.com/paper/2006.09997/) (2020)
- [Regret of Age-of-Information Bandits](https://mlsanity.com/paper/2001.09317/) (2020)
- [Efficient Learning-based Scheduling for Information Freshness in Wireless Networks](https://mlsanity.com/paper/2101.00257/) (2021)
- [On the Low-Complexity of Fair Learning for Combinatorial Multi-Armed Bandit](https://mlsanity.com/paper/2501.00924/) (2025)
- [Throughput-Optimal Scheduling Design with Regular Service Guarantees in Wireless Networks](https://mlsanity.com/paper/1405.0625/) (2014)
- [Correlated Age-of-Information Bandits](https://mlsanity.com/paper/2011.05032/) (2020)
- [Towards Efficient Dynamic Uplink Scheduling over Multiple Unknown Channels](https://mlsanity.com/paper/2212.06633/) (2022)
- [Age of Information Optimization in Multi-Channel Network with Sided Information](https://mlsanity.com/paper/2212.07114/) (2022)

## Abstract (arXiv)

The combinatorial multi-armed bandit model is designed to maximize cumulative rewards in the presence of uncertainty by activating a subset of arms in each round. This paper is inspired by two critical applications in wireless networks, where it's not only essential to maximize cumulative rewards but also to guarantee fairness among arms (i.e., the minimum average reward required by each arm) and ensure reward regularity (i.e., how often each arm receives the reward). In this paper, we propose a parameterized regular and fair learning algorithm to achieve these three objectives. In particular, the proposed algorithm linearly combines virtual queue-lengths (tracking the fairness violations), Time-Since-Last-Reward (TSLR) metrics, and Upper Confidence Bound (UCB) estimates in its weight measure. Here, TSLR is similar to age-of-information and measures the elapsed number of rounds since the last time an arm received a reward, capturing the reward regularity performance, and UCB estimates are utilized to balance the tradeoff between exploration and exploitation in online learning. By exploring a key relationship between virtual queue-lengths and TSLR metrics and utilizing several non-trivial Lyapunov functions, we analytically characterize zero cumulative fairness violation, reward regularity, and cumulative regret performance under our proposed algorithm. These theoretical outcomes are verified by simulations based on two real-world datasets.