Multi-Agent Combinatorial-Multi-Armed-Bandit framework for the Submodular Welfare Problem under Bandit Feedback

Subham Pokhriyal; Shweta Jain; Vaneet Aggarwal

cs.GTFeb 18, 2026

Multi-Agent Combinatorial-Multi-Armed-Bandit framework for the Submodular Welfare Problem under Bandit Feedback

Authors: Subham Pokhriyal, Shweta Jain, Vaneet Aggarwal

Organizations: Indian Institute of Technology Ropar, Rupnagar, India · Purdue University, West Lafayette, USA

Abstract

We study the Submodular Welfare Problem (SWP), where items are partitioned among agents with monotone submodular utilities to maximize the total welfare under bandit feedback. Classical SWP assumes full value-oracle access, achieving $(1-1/e)$ approximations via continuous-greedy algorithms. We extend this to a multi-agent combinatorial bandit framework (MA-CMAB), where actions are partitions under full-bandit feedback with non-communicating agents. Unlike prior single-agent or separable multi-agent CMAB models, our setting couples agents through shared allocation constraints. We propose an explore-then-commit strategy with randomized assignments, achieving $\tilde{\mathcal{O}}(T^{2/3})$ regret against a $(1-1/e)$ benchmark, the first such guarantee for partition-based submodular welfare problem under bandit feedback.

Figures & tables

App.	Objective $f$	$\alpha$	$\delta$	$\eta$	Regret Bound
USW	$\max\texttt{(Sub)}$	$1-\frac{1}{e}$	$(4MN+2M)$	$(MN)^{8}$	$\mathcal{O}\!\left(\delta^{2/3}\eta^{1/3}C^{2/3}T^{2/3}\log^{1/3}(T)\right)$

Table 1: Summary of Resilience Parameters and Regret Guarantee for MA-CMAB. This table outlines the key components underlying the regret analysis of the MA-CMAB algorithm for online submodular welfare maximization. It includes the approximation factor

\alpha=1-1/e

, the robustness parameter

\delta

capturing noise sensitivity, and the oracle complexity

\eta

. The framework achieves a sublinear

\mathcal{O}(T^{2/3})

regret bound with respect to the best offline allocation, under stochastic full-bandit feedback.

\omega_{ij}(t)\approx\mathbb{E}[w_{i}(R_{i}(t)\cup\{j\})-w_{i}(R_{i}(t))]

Algorithm 1 Continuous Greedy (Partition Matroid)

Explore similar work

Multi-Objective Multi-Agent Bandits: From Learning Efficiency to Fairness Optimization
May 7, 2026John Wang, Mengfan XuMulti-Armed Bandits Multi-Agent System Optimization
University of Massachusetts Amherst
Distributed Online Bandit Submodular Maximization with Bounded Sampling Violations
Jul 1, 2026Bin Du, Chang Liu, Dingqi Zhu +2Submodular Optimization Distributed Optimization
College of Automation Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China · School of Artificial Intelligence and Automation at the Huazhong University of Science and Technology, Wuhan, China · School of Aeronautics and Astronautics, Purdue University, West Lafayette, IN 47906, USA
Bandit Submodular Maximization under Matroid Constraints: Learning Compressed Exchange Policy
Aug 25, 2026Zongqi Wan, Zhijie ZhangSubmodular Optimization Adversarial Bandits
Great Bay University · Fuzhou University

May 7, 2026J/K move · Enter open · S save

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

John Wang, Mengfan Xu

University of Massachusetts Amherst

Multi-Armed Bandits Multi-Agent System Optimization Algorithmic Fairness Multi-Objective Optimization

Open paper AskPDF 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 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 Simulated NSW UCB Gossip, which integrates preference-based reward simulation, gossip-based utility estimation, and UCB-style exploration. We prove that Pareto UCB1 Gossip achieves

\mathcal{O}(\log T)

regret and an instance-independent rate of

\mathcal{O}(\sqrt{T})

, while 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.

Abstract

Explore similar work

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

Distributed Online Bandit Submodular Maximization with Bounded Sampling Violations

Bandit Submodular Maximization under Matroid Constraints: Learning Compressed Exchange Policy