Multi-Agent Reinforcement Learning with Submodular Reward

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.

When a fleet of drones monitors a city or robots explore an unknown building together, adding more agents doesn't always proportionally increase the team's performance. E.g. two drones covering the same area produce redundant information, not double the benefit. Existing AI coordination methods ignore this overlap, causing agents to duplicate each other's work. We developed the first framework for AI teams whose shared reward follows this "diminishing returns" structure, proving that a simple greedy strategy, i.e. optimizing agents one at a time rather than all at once, efficiently finds a coordination policy guaranteed to be worth at least half the theoretical best, without exponential computation. When the environment is unknown, our algorithm learns effective teamwork from experience, with formal performance guarantees. This enables reliable, scalable AI collaboration in search-and-rescue, environmental monitoring, and autonomous robotics.