# Multi-Agent Reinforcement Learning with Submodular Reward

arXiv: https://arxiv.org/abs/2603.06810 · HTML: https://mlsanity.com/paper/2603.06810/

## 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 (most cited first, 30 of 33)

- [Learning to Communicate with Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1605.06676/) (2016)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Value-Decomposition Networks For Cooperative Multi-Agent Learning](https://mlsanity.com/paper/1706.05296/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2003.08839/) (2020)
- [Learning Multiagent Communication with Backpropagation](https://mlsanity.com/paper/1605.07736/) (2016)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [MAVEN: Multi-Agent Variational Exploration](https://mlsanity.com/paper/1910.07483/) (2019)
- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [Generalization and Exploration via Randomized Value Functions](https://mlsanity.com/paper/1402.0635/) (2014)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon](https://mlsanity.com/paper/2009.13503/) (2020)
- [Celebrating Diversity in Shared Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2106.02195/) (2021)
- [Submodular Combinatorial Information Measures with Applications in Machine Learning](https://mlsanity.com/paper/2006.15412/) (2020)
- [Influence-Based Multi-Agent Exploration](https://mlsanity.com/paper/1910.05512/) (2019)
- [A Unifying View of Optimism in Episodic Reinforcement Learning](https://mlsanity.com/paper/2007.01891/) (2020)
- [Guided Deep Reinforcement Learning for Swarm Systems](https://mlsanity.com/paper/1709.06011/) (2017)
- [Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/2107.01264/) (2021)
- [Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysis](https://mlsanity.com/paper/2109.03699/) (2021)
- [The Emergence of Individuality](https://mlsanity.com/paper/2006.05842/) (2020)
- [Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback](https://mlsanity.com/paper/2302.01324/) (2023)
- [Combinatorial Stochastic-Greedy Bandit](https://mlsanity.com/paper/2312.08057/) (2023)
- [Randomized Exploration in Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2404.10728/) (2024)
- [Submodular Bandit Problem Under Multiple Constraints](https://mlsanity.com/paper/2006.00661/) (2020)
- [Noisy Submodular Maximization via Adaptive Sampling with Applications to Crowdsourced Image Collection Summarization](https://mlsanity.com/paper/1511.07211/) (2015)
- [Submodular Optimization under Noise](https://mlsanity.com/paper/1601.03095/) (2016)
- [Streaming Submodular Maximization under Matroid Constraints](https://mlsanity.com/paper/2107.07183/) (2021)
- [Modeling the Interaction between Agents in Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2102.06042/) (2021)
- [Dynamic Algorithms for Matroid Submodular Maximization](https://mlsanity.com/paper/2306.00959/) (2023)
- [Understanding Value Decomposition Algorithms in Deep Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2202.04868/) (2022)

## 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.