2506.14988

Total: 1

#1 Fair Algorithms with Probing for Multi-Agent Multi-Armed Bandits [PDF] [Copy] [Kimi4] [REL]

Authors: Tianyi Xu, Jiaxin Liu, Zizhan Zheng

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.

Subjects: Machine Learning , Artificial Intelligence

Publish: 2025-06-17 21:43:21 UTC