# My Fair Bandit: Distributed Learning of Max-Min Fairness with Multi-player Bandits

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

## Key facts

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

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

- [Heterogeneous Multi-player Multi-armed Bandits: Closing the Gap and Generalization](https://mlsanity.com/paper/2110.14622/) (2021)
- [Fairness and Welfare Quantification for Regret in Multi-Armed Bandits](https://mlsanity.com/paper/2205.13930/) (2022)
- [Socially Fair Reinforcement Learning](https://mlsanity.com/paper/2208.12584/) (2022)
- [Nash Regret Guarantees for Linear Bandits](https://mlsanity.com/paper/2310.02023/) (2023)
- [Achieving Fairness in Multi-Agent Markov Decision Processes Using Reinforcement Learning](https://mlsanity.com/paper/2306.00324/) (2023)
- [Cooperative Stochastic Multi-agent Multi-armed Bandits Robust to Adversarial Corruptions](https://mlsanity.com/paper/2106.04207/) (2021)
- [Decentralized Task Offloading in Edge Computing: A Multi-User Multi-Armed Bandit Approach](https://mlsanity.com/paper/2112.11818/) (2021)
- [Learning to Control Unknown Strongly Monotone Games](https://mlsanity.com/paper/2407.00575/) (2024)
- [Active Learning for Fair and Stable Online Allocations](https://mlsanity.com/paper/2406.14784/) (2024)
- [Medium Access Control protocol for Collaborative Spectrum Learning in Wireless Networks](https://mlsanity.com/paper/2111.12581/) (2021)
- [Fairness in Reinforcement Learning with Bisimulation Metrics](https://mlsanity.com/paper/2412.17123/) (2024)
- [Bandit based centralized matching in two-sided markets for peer to peer lending](https://mlsanity.com/paper/2105.02589/) (2021)
- [Near-Optimal Privacy-Preserving Learning for Max-Min Fair Multi-Agent Bandits](https://mlsanity.com/paper/2306.04498/) (2023)
- [Fair Resource Allocation in Weakly Coupled Markov Decision Processes](https://mlsanity.com/paper/2411.09804/) (2024)
- [Fair PCA, One Component at a Time](https://mlsanity.com/paper/2503.21563/) (2025)
- [Fair Policy Optimization in Major-Minor Weakly Coupled Markov Decision Processes](https://mlsanity.com/paper/2609.36174/) (2026)

## Abstract (arXiv)

Consider N cooperative but non-communicating players where each plays one out of M arms for T turns. Players have different utilities for each arm, representable as an NxM matrix. These utilities are unknown to the players. In each turn players select an arm and receive a noisy observation of their utility for it. However, if any other players selected the same arm that turn, all colliding players will all receive zero utility due to the conflict. No other communication or coordination between the players is possible. Our goal is to design a distributed algorithm that learns the matching between players and arms that achieves max-min fairness while minimizing the regret. We present an algorithm and prove that it is regret optimal up to a loglog T factor. This is the first max-min fairness multi-player bandit algorithm with (near) order optimal regret.