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

• URL: http://arxiv.org/abs/2605.06864v1
• Date: Thu, 07 May 2026 19:06:34 GMT
• Title: Multi-Objective Multi-Agent Bandits: From Learning Efficiency to Fairness Optimization
• Abstract summary: We study multi-objective multi-agent multi-armed bandits (MO-MA-MAB) under rewards, where agents observe heterogeneous reward vectors and communicate over time-varying graphs.<n>We formulate this emerging problem setting to address emphefficient learning, measured by Pareto regret, and incorporate emphfair learning as an additional goal, captured via social welfare.<n>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
• Score: 4.774863352469391
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Learning Shared Representations for Multi-Task Linear Bandits [7.978226788634307]
  Multi-task representation learning is an approach that learns shared latent representations across related tasks.<n>We consider a setting with T concurrent linear bandit tasks, each with feature dimension d, that share a common latent representation of dimension r ll mind,T$.<n>We propose a new Optimism in the Face of Uncertainty Linear (OFUL) algorithm that leverages shared low-rank representations to enhance decision-making.
  arXiv  Detail & Related papers  (2026-04-01T06:18:17Z)
• Blockwise Advantage Estimation for Multi-Objective RL with Verifiable Rewards [39.489554597919145]
  Group Relative Policy Optimization (GRPO) assigns a single scalar advantage to all tokens in a completion.<n>For structured generations with explicit segments and objectives, this couples unrelated reward signals across segments, leading to objective interference and misattributed credit.<n>We propose Blockwise Advantage Estimation, a family of GRPO-compatible methods that assigns each objective its own advantage and applies it only to the tokens in the corresponding text block.
  arXiv  Detail & Related papers  (2026-02-10T19:22:37Z)
• Thompson Sampling for Multi-Objective Linear Contextual Bandit [29.777578580338584]
  We study the multi-objective linear contextual bandit problem, where multiple possible conflicting objectives must be optimized simultaneously.<n>We propose textttMOL-TS, the textitfirst Thompson Sampling algorithm with Pareto regret guarantees for this problem.<n> Empirical results confirm the benefits of our proposed approach, demonstrating improved regret minimization and strong multi-objective performance.
  arXiv  Detail & Related papers  (2025-11-30T15:18:01Z)
• Modest-Align: Data-Efficient Alignment for Vision-Language Models [67.48633659305592]
  Cross-modal alignment models often suffer from overconfidence and degraded performance when operating in resource-constrained settings.<n>We propose Modest-Align, a lightweight alignment framework designed for robustness and efficiency.<n>Our method offers a practical and scalable solution for cross-modal alignment in real-world, low-resource scenarios.
  arXiv  Detail & Related papers  (2025-10-24T16:11:10Z)
• Learning from N-Tuple Data with M Positive Instances: Unbiased Risk Estimation and Theoretical Guarantees [33.15955234458642]
  Weakly supervised learning often operates with coarse aggregate signals rather than labels.<n>We show that counts admit a trainable unbiased risk estimator (URE) by linking the instance-generation process to latent marginals.<n>We demonstrate that count-only supervision can be exploited effectively through a theoretically grounded and practically stable objective setting.
  arXiv  Detail & Related papers  (2025-10-21T08:28:07Z)
• Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update [70.38810219913593]
  We study the generalized linear bandit (GLB) problem, a contextual multi-armed bandit framework that extends the classical linear model by incorporating a non-linear link function.<n>GLBs are widely applicable to real-world scenarios, but their non-linear nature introduces significant challenges in achieving both computational and statistical efficiency.<n>We propose a jointly efficient algorithm that attains a nearly optimal regret bound with $mathcalO(1)$ time and space complexities per round.
  arXiv  Detail & Related papers  (2025-07-16T02:24:21Z)
• Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits [58.63897489864948]
  Reinforcement learning with outcome-based feedback faces a fundamental challenge.<n>How do we assign credit to the right actions?<n>This paper provides the first comprehensive analysis of this problem in online RL with general function approximation.
  arXiv  Detail & Related papers  (2025-05-26T17:44:08Z)
• Concurrent Learning with Aggregated States via Randomized Least Squares Value Iteration [40.73142019282658]
  We study whether injecting randomization can help a society of agents it concurently explore an environment.<n>We demonstrate worst-case regret bounds in both finite- and infinite-horizon environments.<n>We reduce the space complexity by a factor of $K$ while incurring only a $sqrtK$ increase in the worst-case regret bound.
  arXiv  Detail & Related papers  (2025-01-23T05:37:33Z)
• Noisy Correspondence Learning with Self-Reinforcing Errors Mitigation [63.180725016463974]
  Cross-modal retrieval relies on well-matched large-scale datasets that are laborious in practice. We introduce a novel noisy correspondence learning framework, namely textbfSelf-textbfReinforcing textbfErrors textbfMitigation (SREM)
  arXiv  Detail & Related papers  (2023-12-27T09:03:43Z)
• Contextual Model Aggregation for Fast and Robust Federated Learning in Edge Computing [88.76112371510999]
  Federated learning is a prime candidate for distributed machine learning at the network edge. Existing algorithms face issues with slow convergence and/or robustness of performance. We propose a contextual aggregation scheme that achieves the optimal context-dependent bound on loss reduction.
  arXiv  Detail & Related papers  (2022-03-23T21:42:31Z)
• Boosting Discriminative Visual Representation Learning with Scenario-Agnostic Mixup [54.09898347820941]
  We propose textbfScenario-textbfAgnostic textbfMixup (SAMix) for both Self-supervised Learning (SSL) and supervised learning (SL) scenarios. Specifically, we hypothesize and verify the objective function of mixup generation as optimizing local smoothness between two mixed classes. A label-free generation sub-network is designed, which effectively provides non-trivial mixup samples and improves transferable abilities.
  arXiv  Detail & Related papers  (2021-11-30T14:49:59Z)
• Scalable Personalised Item Ranking through Parametric Density Estimation [53.44830012414444]
  Learning from implicit feedback is challenging because of the difficult nature of the one-class problem. Most conventional methods use a pairwise ranking approach and negative samplers to cope with the one-class problem. We propose a learning-to-rank approach, which achieves convergence speed comparable to the pointwise counterpart.
  arXiv  Detail & Related papers  (2021-05-11T03:38:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.