# Near-Optimal Privacy-Preserving Learning for Max-Min Fair Multi-Agent Bandits

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 52 references that are in the map.
- First posted on arXiv 7 Jun 2023.

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

- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Fairness in Reinforcement Learning](https://mlsanity.com/paper/1611.03071/) (2016)
- [Competing Bandits in Matching Markets](https://mlsanity.com/paper/1906.05363/) (2019)
- [SIC-MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Bandits](https://mlsanity.com/paper/1809.08151/) (2018)
- [Group Retention when Using Machine Learning in Sequential Decision Making: the Interplay between User Dynamics and Fairness](https://mlsanity.com/paper/1905.00569/) (2019)
- [The True Sample Complexity of Identifying Good Arms](https://mlsanity.com/paper/1906.06594/) (2019)
- [A Practical Algorithm for Multiplayer Bandits when Arm Means Vary Among Players](https://mlsanity.com/paper/1902.01239/) (2019)
- [Concurrent bandits and cognitive radio networks](https://mlsanity.com/paper/1404.5421/) (2014)
- [On Regret-Optimal Learning in Decentralized Multi-player Multi-armed Bandits](https://mlsanity.com/paper/1505.00553/) (2015)
- [Individual Regret in Cooperative Nonstochastic Multi-Armed Bandits](https://mlsanity.com/paper/1907.03346/) (2019)
- [My Fair Bandit: Distributed Learning of Max-Min Fairness with Multi-player Bandits](https://mlsanity.com/paper/2002.09808/) (2020)
- [Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without](https://mlsanity.com/paper/1904.12233/) (2019)
- [Game of Thrones: Fully Distributed Learning for Multi-Player Bandits](https://mlsanity.com/paper/1810.11162/) (2018)
- [Multi-Player Bandits: The Adversarial Case](https://mlsanity.com/paper/1902.08036/) (2019)
- [Distributed Learning for Channel Allocation Over a Shared Spectrum](https://mlsanity.com/paper/1902.06353/) (2019)
- [Fully distributed optimal channel assignment for open spectrum access](https://mlsanity.com/paper/1312.7685/) (2013)
- [Expected time complexity of the auction algorithm and the push relabel algorithm for maximal bipartite matching on random graphs](https://mlsanity.com/paper/1401.0119/) (2013)
- [The Effect of Communication on Noncooperative Multiplayer Multi-Armed Bandit Problems](https://mlsanity.com/paper/1711.01628/) (2017)

## Abstract (arXiv)

We study fair multi-agent multi-armed bandit learning under collision-only coordination. Agents cannot communicate explicitly during learning and observe only their own rewards and whether collisions occur when several agents access the same arm. The goal is to learn a max-min fair allocation while keeping each agent's reward samples and empirical reward estimates local. We propose a fully distributed algorithm for bounded rewards with unknown support, achieving regret O!left(N3 f(log T)log Tright), where f is any nondecreasing diverging function satisfying f(k-1)/f(k)→ 1. The algorithm combines distributed agent ordering, cumulative round-robin exploration, endpoint-revalidated warm-started bisection, and a collision-based distributed auction for threshold-feasibility tests. Unlike leader-based optimal algorithms, no agent collects the reward observations, empirical estimates, or preferences of the others. Thus, the protocol preserves reward privacy in the operational sense of avoiding reward sharing, while coordinating only through collision outcomes. Compared with previous privacy-preserving algorithms for max--min fair bandits, which have exponential dependence on the number of agents, our method achieves polynomial N3 dependence while retaining near-logarithmic dependence on T. The analysis uses concentration of cumulative empirical estimates and stability of endpoint-revalidated bisection. Simulations confirm the predicted scaling with horizon, number of agents, and max--min gap across representative numerical settings.