mlsanityData to 14 Oct 2026

Multi-Agent Reinforcement Learning with Submodular Reward

arXiv 2603.06810 ↗First posted 6 Mar 2026cs.LG cs.DScited by 0

Not on the map. Why?

Abstract (arXiv)

In this paper, we study cooperative multi-agent reinforcement learning (MARL) where the joint reward exhibits submodularity, which is a natural property capturing diminishing marginal returns when adding agents to a team. Unlike standard MARL with additive rewards, submodular rewards model realistic scenarios where agent contributions overlap (e.g., multi-drone surveillance, collaborative exploration). We provide the first formal framework for this setting and develop algorithms with provable guarantees on sample efficiency and regret bound. For known dynamics, our greedy policy optimization achieves a 1/2-approximation with polynomial complexity in the number of agents K, overcoming the exponential curse of dimensionality inherent in joint policy optimization. For unknown dynamics, we propose a UCB-based learning algorithm achieving a 1/2-regret of O(H2KS√AT) over T episodes.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 33 of its 49 references that are in the map. First posted on arXiv 6 Mar 2026.

Builds on

33 of 49 references.

References · 33

  1. 2016Learning to Communicate with Deep Multi-Agent Reinforcement Learningcited by 575
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  3. 2017Value-Decomposition Networks For Cooperative Multi-Agent Learningcited by 503
  4. 2018Is Q-learning Provably Efficient?cited by 487
  5. 2020Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learningcited by 485
  6. 2016Learning Multiagent Communication with Backpropagationcited by 366
  7. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  8. 2019MAVEN: Multi-Agent Variational Explorationcited by 185
  9. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  10. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  11. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 106
  12. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
21 more
  1. 2021Celebrating Diversity in Shared Multi-Agent Reinforcement Learningcited by 98
  2. 2020Submodular Combinatorial Information Measures with Applications in Machine Learningcited by 88
  3. 2019Influence-Based Multi-Agent Explorationcited by 75
  4. 2020A Unifying View of Optimism in Episodic Reinforcement Learningcited by 52
  5. 2017Guided Deep Reinforcement Learning for Swarm Systemscited by 44
  6. 2021Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learningcited by 34
  7. 2021Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysiscited by 26
  8. 2020The Emergence of Individualitycited by 22
  9. 2023Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedbackcited by 19
  10. 2023Combinatorial Stochastic-Greedy Banditcited by 18
  11. 2024Randomized Exploration in Cooperative Multi-Agent Reinforcement Learningcited by 17
  12. 2020Submodular Bandit Problem Under Multiple Constraintscited by 15
  13. 2015Noisy Submodular Maximization via Adaptive Sampling with Applications to Crowdsourced Image Collection Summarizationcited by 11
  14. 2016Submodular Optimization under Noisecited by 11
  15. 2021Streaming Submodular Maximization under Matroid Constraintscited by 9
  16. 2021Modeling the Interaction between Agents in Cooperative Multi-Agent Reinforcement Learningcited by 7
  17. 2023Dynamic Algorithms for Matroid Submodular Maximizationcited by 7
  18. 2022Understanding Value Decomposition Algorithms in Deep Cooperative Multi-Agent Reinforcement Learningcited by 6
  19. 2023Bandit Submodular Maximization for Multi-Robot Coordination in Unpredictable and Partially Observable Environmentscited by 6
  20. 2024Fair Submodular Covercited by 6
  21. 2024Linear Submodular Maximization with Bandit Feedbackcited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Submodular Multi-Agent Policy Learning for Online Distributed Task Allocation in Open Multi-Agent Systems ↗
  2. 2025Scalable Submodular Policy Optimization via Pruned Submodularity Graph
  3. 2024Fully Decentralized Cooperative Multi-Agent Reinforcement Learning: A Survey
  4. 2024Global Reinforcement Learning: Beyond Linear and Convex Rewards via Submodular Semi-gradient Methods
  5. 2024Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learning
  6. 2024Multi-agent cooperation through learning-aware policy gradients
  7. 2025Preference-Guided Learning for Sparse-Reward Multi-Agent Reinforcement Learning
  8. 2025Structured Cooperative Multi-Agent Reinforcement Learning: a Bayesian Network Perspective