Multi-Objective Multi-Agent Bandits: From Learning Efficiency to Fairness Optimization

We study multi-objective multi-agent multi-armed bandits (MO-MA-MAB) under stochastic rewards, where agents observe heterogeneous reward vectors and communicate over time-varying graphs. We formulate this emerging problem setting to address efficient learning, measured by Pareto regret, and incorporate fair learning as an additional goal, captured via social welfare. To measure efficiency, we formulate Pareto regret and develop textscPareto UCB1 Gossip, whose novel exploration radius explicitly separates statistical uncertainty in Pareto-based inference from consensus error. To express the fairness constraint, we formulate a Nash Social Welfare objective over preference-scalarized rewards and propose textscSimulated NSW UCB Gossip, which integrates preference-based reward simulation, gossip-based utility estimation, and UCB-style exploration. We prove that textscPareto UCB1 Gossip achieves (O(log T)) regret and an instance-independent rate of (O(√T)), while textscSimulated NSW UCB Gossip achieves an instance-independent regret bound of (O(T3/4)). This separation reveals the cost of imposing the fairness constraint to our efficiency objective: fairness limits information aggregation and slows convergence. Experiments show that our methods consistently outperform baselines, improving performance by approximately (100%) and (50%) in the efficiency and fairness settings, respectively.