# An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regret

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 35 references that are in the map.
- First posted on arXiv 23 Sep 2022.

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

- [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)
- [Bandits and Experts in Metric Spaces](https://mlsanity.com/paper/1312.1277/) (2013)
- [Kernel-based methods for bandit convex optimization](https://mlsanity.com/paper/1607.03084/) (2016)
- [Online Learning with an Unknown Fairness Metric](https://mlsanity.com/paper/1802.06936/) (2018)
- [Distributed Cooperative Decision-Making in Multiarmed Bandits: Frequentist and Bayesian Algorithms](https://mlsanity.com/paper/1606.00911/) (2016)
- [Calibrated Fairness in Bandits](https://mlsanity.com/paper/1707.01875/) (2017)
- [Fair Algorithms for Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2007.06699/) (2020)
- [Multi-scale exploration of convex functions and bandit convex optimization](https://mlsanity.com/paper/1507.06580/) (2015)
- [Fair Algorithms for Infinite and Contextual Bandits](https://mlsanity.com/paper/1610.09559/) (2016)
- [Projection-Free Bandit Convex Optimization](https://mlsanity.com/paper/1805.07474/) (2018)

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

- [Incentivizing Truthful Language Models via Peer Elicitation Games](https://mlsanity.com/paper/2505.13636/) (2025)
- [No-Regret Learning for Fair Multi-Agent Social Welfare Optimization](https://mlsanity.com/paper/2405.20678/) (2024)
- [Revisiting Social Welfare in Bandits: UCB is (Nearly) All You Need](https://mlsanity.com/paper/2510.21312/) (2025)
- [Fairness Aware Reinforcement Learning via Proximal Policy Optimization](https://mlsanity.com/paper/2502.03953/) (2025)
- [Bandit Max-Min Fair Allocation](https://mlsanity.com/paper/2505.05169/) (2025)
- [Fair Algorithms with Probing for Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2506.14988/) (2025)
- [Multi-Objective Multi-Agent Bandits: From Learning Efficiency to Fairness Optimization](https://mlsanity.com/paper/2605.06864/) (2026)
- [Multi-agent Multi-armed Bandits with Minimum Reward Guarantee Fairness](https://mlsanity.com/paper/2502.15240/) (2025)
- [Procedural Fairness in Multi-Agent Bandits](https://mlsanity.com/paper/2601.10600/) (2026)
- [Multi-User Dueling Bandits: A Fair Approach using Nash Social Welfare](https://mlsanity.com/paper/2605.01961/) (2026)

## Abstract (arXiv)

Recently a multi-agent variant of the classical multi-armed bandit was proposed to tackle fairness issues in online learning. Inspired by a long line of work in social choice and economics, the goal is to optimize the Nash social welfare instead of the total utility. Unfortunately previous algorithms either are not efficient or achieve sub-optimal regret in terms of the number of rounds T. We propose a new efficient algorithm with lower regret than even previous inefficient ones. For N agents, K arms, and T rounds, our approach has a regret bound of tildeO(√NKT + NK). This is an improvement to the previous approach, which has regret bound of tildeO( min(NK, √N K3/2)√T). We also complement our efficient algorithm with an inefficient approach with tildeO(√KT + N2K) regret. The experimental findings confirm the effectiveness of our efficient algorithm compared to the previous approaches.