mlsanityData to 7 Oct 2026

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

arXiv 2602.16183 ↗First posted 18 Feb 2026cs.GT cs.LG stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

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 (textscMA-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 tildeO(T2/3) regret against a (1-1/e) benchmark, the first such guarantee for partition-based submodular welfare problem under bandit feedback.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 29 of its 52 references that are in the map. First posted on arXiv 18 Feb 2026.

Builds on

29 of 52 references.

References · 29

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2018Federated Optimization in Heterogeneous Networkscited by 2,971
  3. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,461
  4. 2019Introduction to Multi-Armed Banditscited by 475
  5. 2014Lazier Than Lazy Greedycited by 97
  6. 2020Differentially-Private Federated Linear Banditscited by 83
  7. 2020Federated Bandit: A Gossiping Approachcited by 55
  8. 2019Competing Bandits in Matching Marketscited by 54
  9. 2016Distributed Clustering of Linear Bandits in Peer to Peer Networkscited by 50
  10. 2019Social Learning in Multi Agent Multi Armed Banditscited by 48
  11. 2013Distributed Exploration in Multi-Armed Banditscited by 46
  12. 2018SIC-MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Banditscited by 46
17 more
  1. 2021Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimizationcited by 40
  2. 2020The Gossiping Insert-Eliminate Algorithm for Multi-Agent Banditscited by 37
  3. 2016Collaborative Learning of Stochastic Bandits over a Social Networkcited by 29
  4. 2021Multi-Agent Multi-Armed Bandits with Limited Communicationcited by 29
  5. 2014Concurrent bandits and cognitive radio networkscited by 23
  6. 2022FedNew: A Communication-Efficient and Privacy-Preserving Newton-Type Method for Federated Learningcited by 23
  7. 2020Kernel Methods for Cooperative Multi-Agent Contextual Banditscited by 21
  8. 2023A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedbackcited by 19
  9. 2023Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedbackcited by 19
  10. 2022Near-Optimal Collaborative Learning in Banditscited by 18
  11. 2023Combinatorial Stochastic-Greedy Banditcited by 18
  12. 2024Federated Combinatorial Multi-Agent Multi-Armed Banditscited by 11
  13. 2017Competing Bandits: Learning under Competitioncited by 9
  14. 2020Multi-Agent Low-Dimensional Linear Banditscited by 8
  15. 2013Distributed Online Learning via Cooperative Contextual Banditscited by 5
  16. 2023FilFL: Client Filtering for Optimized Client Participation in Federated Learningcited by 5
  17. 2023Collaborative Multi-Agent Heterogeneous Multi-Armed Banditscited by 4

Built on by

Not cited yet.