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

2025/06/17 by Tianyi Xu, Xu, Tianyi, Jiaxin Liu +5
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Artificial Intelligence (cs.AI) #Auction Theory and Applications #Data Stream Mining Techniques #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.2506.14988

openalex publication_date 2025/06/17 · openalex created_date 2025/10/19 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• Online Learning with Probing for Sequential User-Centric Selection
• Online Learning for Adaptive Probing and Scheduling in Dense WLANs
• An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regret
• Hierarchical Conversational Preference Elicitation with Bandit Feedback
• Joint AP Probing and Scheduling: A Contextual Bandit Approach
• Fair Algorithms for Multi-Agent Multi-Armed Bandits
• Bandit Algorithms
• Algorithmic Fairness
• Neural Approximate Dynamic Programming for On-Demand Ride-Pooling
• Achieving Fairness in the Stochastic Multi-armed Bandit Problem
• Introduction to Multi-Armed Bandits
• Observe Before Play: Multi-armed Bandit with Pre-observations
• Fairness Behind a Veil of Ignorance: A Welfare Analysis for Automated Decision Making
• Fairness in Learning: Classic and Contextual Bandits
• Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
• Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints
• Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
• Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization

Related

• Fair Algorithms for Multi-Agent Multi-Armed Bandits
• Multi-agent Multi-armed Bandits with Minimum Reward Guarantee Fairness
• Fair Contextual Multi-Armed Bandits: Theory and Experiments
• Group Fairness in Bandit Arm Selection
• Multi-agent Multi-armed Bandits with Stochastic Sharable Arm Capacities