# Fair Algorithms with Probing for Multi-Agent Multi-Armed Bandits

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 48 references that are in the map.
- First posted on arXiv 17 Jun 2025.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Algorithmic Fairness](https://mlsanity.com/paper/2001.09784/) (2020)
- [Achieving Fairness in the Stochastic Multi-armed Bandit Problem](https://mlsanity.com/paper/1907.10516/) (2019)
- [Fairness Behind a Veil of Ignorance: A Welfare Analysis for Automated Decision Making](https://mlsanity.com/paper/1806.04959/) (2018)
- [Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints](https://mlsanity.com/paper/1311.2106/) (2013)
- [Fair Algorithms for Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2007.06699/) (2020)
- [Neural Approximate Dynamic Programming for On-Demand Ride-Pooling](https://mlsanity.com/paper/1911.08842/) (2019)
- [Hierarchical Conversational Preference Elicitation with Bandit Feedback](https://mlsanity.com/paper/2209.06129/) (2022)
- [An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regret](https://mlsanity.com/paper/2209.11817/) (2022)
- [Observe Before Play: Multi-armed Bandit with Pre-observations](https://mlsanity.com/paper/1911.09458/) (2019)
- [Joint AP Probing and Scheduling: A Contextual Bandit Approach](https://mlsanity.com/paper/2108.03297/) (2021)
- [Online Learning for Adaptive Probing and Scheduling in Dense WLANs](https://mlsanity.com/paper/2212.13585/) (2022)

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

- [RAM: Recover Any 3D Human Motion in-the-Wild](https://mlsanity.com/paper/2603.19929/) (2026)

## Abstract (arXiv)

We propose a multi-agent multi-armed bandit (MA-MAB) framework aimed at ensuring fair outcomes across agents while maximizing overall system performance. A key challenge in this setting is decision-making under limited information about arm rewards. To address this, we introduce a novel probing framework that strategically gathers information about selected arms before allocation. In the offline setting, where reward distributions are known, we leverage submodular properties to design a greedy probing algorithm with a provable performance bound. For the more complex online setting, we develop an algorithm that achieves sublinear regret while maintaining fairness. Extensive experiments on synthetic and real-world datasets show that our approach outperforms baseline methods, achieving better fairness and efficiency.