Fair Algorithms with Probing for Multi-Agent Multi-Armed Bandits
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910001438654464 |
|---|---|
| author | Xu, Tianyi Liu, Jiaxin Mattei, Nicholas Zheng, Zizhan |
| author_facet | Xu, Tianyi Liu, Jiaxin Mattei, Nicholas Zheng, Zizhan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_14988 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fair Algorithms with Probing for Multi-Agent Multi-Armed Bandits Xu, Tianyi Liu, Jiaxin Mattei, Nicholas Zheng, Zizhan Machine Learning Artificial Intelligence 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. |
| title | Fair Algorithms with Probing for Multi-Agent Multi-Armed Bandits |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2506.14988 |