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

arXiv: https://arxiv.org/abs/2605.06864 · HTML: https://mlsanity.com/paper/2605.06864/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 31 references that are in the map.
- First posted on arXiv 7 May 2026.

## Builds on (most cited first, 11 of 11)

- [Emergent Coordination Through Competition](https://mlsanity.com/paper/1902.07151/) (2019)
- [Social Learning in Multi Agent Multi Armed Bandits](https://mlsanity.com/paper/1910.02100/) (2019)
- [Multi-Objective Multi-Agent Decision Making: A Utility-based Analysis and Survey](https://mlsanity.com/paper/1909.02964/) (2019)
- [Fair Algorithms for Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2007.06699/) (2020)
- [On Distributed Cooperative Decision-Making in Multiarmed Bandits](https://mlsanity.com/paper/1512.06888/) (2015)
- [Multi-objective Bandits: Optimizing the Generalized Gini Index](https://mlsanity.com/paper/1706.04933/) (2017)
- [Decentralized Randomly Distributed Multi-agent Multi-armed Bandit with Heterogeneous Rewards](https://mlsanity.com/paper/2306.05579/) (2023)
- [An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regret](https://mlsanity.com/paper/2209.11817/) (2022)
- [No-Regret Learning for Fair Multi-Agent Social Welfare Optimization](https://mlsanity.com/paper/2405.20678/) (2024)
- [Heterogeneous Multi-agent Multi-armed Bandits on Stochastic Block Models](https://mlsanity.com/paper/2502.08003/) (2025)
- [Communication-Corruption Coupling and Verification in Cooperative Multi-Objective Bandits](https://mlsanity.com/paper/2601.11924/) (2026)

## Built on by (most cited first, 1 of 1)

- [The Optimization Trilemma: Efficiency, Comfort and Fairness in Decentralized Multi-agent Coordination](https://mlsanity.com/paper/2607.17311/) (2026)

## Abstract (arXiv)

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.