Multi-Agent Reinforcement Learning with Submodular Reward

Wenjing Chen, Chengyuan Qian, Shuo Xing, Yi Zhou, Victoria G. Crawford
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:16387-16417, 2026.

Abstract

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(H^2KS\sqrt{AT})$ over $T$ episodes.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-chen26dk, title = {Multi-Agent Reinforcement Learning with Submodular Reward}, author = {Chen, Wenjing and Qian, Chengyuan and Xing, Shuo and Zhou, Yi and Crawford, Victoria G.}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {16387--16417}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/chen26dk/chen26dk.pdf}, url = {https://proceedings.mlr.press/v306/chen26dk.html}, abstract = {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(H^2KS\sqrt{AT})$ over $T$ episodes.} }
Endnote
%0 Conference Paper %T Multi-Agent Reinforcement Learning with Submodular Reward %A Wenjing Chen %A Chengyuan Qian %A Shuo Xing %A Yi Zhou %A Victoria G. Crawford %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-chen26dk %I PMLR %P 16387--16417 %U https://proceedings.mlr.press/v306/chen26dk.html %V 306 %X 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(H^2KS\sqrt{AT})$ over $T$ episodes.
APA
Chen, W., Qian, C., Xing, S., Zhou, Y. & Crawford, V.G.. (2026). Multi-Agent Reinforcement Learning with Submodular Reward. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:16387-16417 Available from https://proceedings.mlr.press/v306/chen26dk.html.

Related Material