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 \emph{efficient learning}, measured by Pareto regret, and incorporate \emph{fair learning} as an additional goal, captured via social welfare. To measure efficiency, we formulate Pareto regret and develop $\text{textsc}ParetoUCB1Gossip$, 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 $\text{textsc}SimulatedNSWUCBGossip$, which integrates preference-based reward simulation, gossip-based utility estimation, and UCB-style exploration. We prove that $\text{textsc}ParetoUCB1Gossip$ achieves $\mathcal{O}(\log T)$ regret and an instance-independent rate of $\mathcal{O}(\sqrt{T})$, while $\text{textsc}SimulatedNSWUCBGossip$ achieves an instance-independent regret bound of $\mathcal{O}(T^{3\mathrm{/}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\mathrm{\%}$ and $50\mathrm{\%}$ in the efficiency and fairness settings, respectively.