# Multi-agent Multi-armed Bandits with Minimum Reward Guarantee Fairness

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 21 references that are in the map.
- First posted on arXiv 21 Feb 2025.

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

- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Achieving Fairness in the Stochastic Multi-armed Bandit Problem](https://mlsanity.com/paper/1907.10516/) (2019)
- [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018)
- [Calibrated Fairness in Bandits](https://mlsanity.com/paper/1707.01875/) (2017)
- [Fairness of Exposure in Stochastic Bandits](https://mlsanity.com/paper/2103.02735/) (2021)
- [Fair Algorithms for Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2007.06699/) (2020)
- [An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regret](https://mlsanity.com/paper/2209.11817/) (2022)
- [Mitigating Disparity while Maximizing Reward: Tight Anytime Guarantee for Improving Bandits](https://mlsanity.com/paper/2208.09254/) (2022)
- [No-Regret Learning for Fair Multi-Agent Social Welfare Optimization](https://mlsanity.com/paper/2405.20678/) (2024)
- [BanditQ: Fair Bandits with Guaranteed Rewards](https://mlsanity.com/paper/2304.05219/) (2023)
- [p-Mean Regret for Stochastic Bandits](https://mlsanity.com/paper/2412.10751/) (2024)

## Abstract (arXiv)

We investigate the problem of maximizing social welfare while ensuring fairness in a multi-agent multi-armed bandit (MA-MAB) setting. In this problem, a centralized decision-maker takes actions over time, generating random rewards for various agents. Our goal is to maximize the sum of expected cumulative rewards, a.k.a. social welfare, while ensuring that each agent receives an expected reward that is at least a constant fraction of the maximum possible expected reward. Our proposed algorithm, RewardFairUCB, leverages the Upper Confidence Bound (UCB) technique to achieve sublinear regret bounds for both fairness and social welfare. The fairness regret measures the positive difference between the minimum reward guarantee and the expected reward of a given policy, whereas the social welfare regret measures the difference between the social welfare of the optimal fair policy and that of the given policy. We show that RewardFairUCB algorithm achieves instance-independent social welfare regret guarantees of tildeO(T1/2) and a fairness regret upper bound of tildeO(T3/4). We also give the lower bound of Omega(√T) for both social welfare and fairness regret. We evaluate RewardFairUCB's performance against various baseline and heuristic algorithms using simulated data and real world data, highlighting trade-offs between fairness and social welfare regrets.