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

John Wang; Mengfan Xu

cs.LGMay 7, 2026

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

Authors: John Wang, Mengfan Xu

Organizations: University of Massachusetts Amherst

Abstract

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 \textsc{Pareto 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 \textsc{Simulated NSW UCB Gossip}, which integrates preference-based reward simulation, gossip-based utility estimation, and UCB-style exploration. We prove that \textsc{Pareto UCB1 Gossip} achieves $\mathcal{O}(\log T)$ regret and an instance-independent rate of $\mathcal{O}(\sqrt{T})$ , while \textsc{Simulated NSW UCB Gossip} achieves an instance-independent regret bound of $\mathcal{O}(T^{3/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.

Explore similar work

May 3, 2026cs.LG

Multi-User Dueling Bandits: A Fair Approach using Nash Social Welfare

Learning from human preference data is becoming a useful tool, from fine-tuning large language models to training reinforcement learning agents. However, in most scenarios, the model is trained on the average preference of all human evaluators, which, under large variations of preferences, can be unfair to minority groups. In this work, we consider fairness in dueling bandits, a standard framework for online learning from preference data. We assume that each user has a (potentially distinct) Condorcet winner, which is an arm preferred to every other arm. Using these user-specific Condorcet winners as reference points, we evaluate and score arms according to their performance relative to the corresponding winner. To promote fairness across heterogeneous users, we adopt the well-established Nash Social Welfare objective, which maximizes the product of user utilities, thereby inherently penalizing inequality and preventing the marginalization of any single user. Within this framework, we construct a hard instance to establish a regret lower bound of

Ω(T^{2/3}\min(K,D)^\frac{1}{3})

for a time horizon

T

K

arms, and

D

users, which, to the best of our knowledge, is the first result quantifying the cost of fairness in dueling bandits with heterogeneous preferences. We then present the Fair-Explore-Then-Commit and Fair-

ε

-Greedy algorithms with a Condorcet winner identification phase. We further derive their regret upper bounds that match the lower-bound dependence on

T

up to logarithmic factors.

Maheed H. Ahmed, Mahsa Ghasemi

Bandits

Ask PDF

May 13, 2026cs.LG

Collaborating in Multi-Armed Bandits with Strategic Agents

We study collaborative learning in multi-agent Bayesian bandit problems, where strategic agents collectively solve the same bandit instance. While multiple agents can accelerate learning by sharing information, strategic agents might prefer to free-ride and avoid exploration. We consider a setting with persistent agents that participate in multiple time periods. This is in contrast to most previous works on incentives in multi-agent MAB, which assume short-lived agents, namely each agent has a single decision to make and optimizes their expected reward in that single decision. As in the multi-agent MAB model with incentives, our model does not have monetary transfers, and the only incentives are through information sharing. We propose \texttt{CAOS}, a mechanism that sustains collaboration as a Nash equilibrium while achieving strong regret guarantees. Our results demonstrate that collaborative exploration can be sustained purely through information sharing, achieving performance close to that of fully cooperative systems despite strategic behavior.

Idan Barnea, Ofir Schlisselberg, Yishay Mansour

Heterogeneous Agents Exploration-Exploitation Dilemma Curiosity-Driven Exploration

Ask PDF

Jan 30, 2026cs.LG

Improved Algorithms for Nash Welfare in Linear Bandits

Nash regret has recently emerged as a principled fairness-aware performance metric for stochastic multi-armed bandits, motivated by the Nash Social Welfare objective. Although this notion has been extended to linear bandits, existing results suffer from suboptimality in ambient dimension

d

, stemming from proof techniques that rely on restrictive concentration inequalities. In this work, we resolve this open problem by introducing new analytical tools that yield an order-optimal Nash regret bound in linear bandits. Beyond Nash regret, we initiate the study of

p

-means regret in linear bandits, a unifying framework that interpolates between fairness and utility objectives and strictly generalizes Nash regret. We propose a generic algorithmic framework, FairLinBandit, that works as a meta-algorithm on top of any linear bandit strategy. We instantiate this framework using two bandit algorithms: Phased Elimination and Upper Confidence Bound, and prove that both achieve sublinear

p

-means regret for the entire range of

p

. Extensive experiments on linear bandit instances generated from real-world datasets demonstrate that our methods consistently outperform the existing state-of-the-art baseline.

Dhruv Sarkar, Nishant Pandey, Sayak Ray Chowdhury

Dynamic Regret Bounds Fairness-Aware Learning

Ask PDF