cs.LGNov 3, 2026

Cooperative Multi-Agent Reinforcement Learning with Submodular Trajectory Rewards

Authors: Yasaman Zolfimoselo, Nikolas Geroliminis, Maryam Kamgarpour

Organizations: EPFL, Switzerland

Abstract

We study cooperative multi-agent reinforcement learning with decoupled dynamics and a monotone submodular reward function over joint trajectories. Due to the non-additive reward, an optimal policy may depend on the history of all agents. This dependence makes exact optimization exponential in the horizon and the number of agents. To overcome this challenge while retaining theoretical guarantees, we introduce pre-window curvature cmc_m, which quantifies how states visited more than mm steps earlier reduce current marginal gains. Using this curvature to control the error from restricting the policy of each agent to depend only on its last m+1m+1 states, we propose a greedy algorithm that exploits the decoupled dynamics to optimize local policies sequentially. For fixed mm, the algorithm achieves a 1−cm2−cm\frac{1-c_m}{2-c_m} approximation guarantee up to estimation error, and its computation time is polynomial in the number of agents and the horizon. We recover the known 1/21/2-factor approximation for time-additive rewards and obtain an approximation factor no smaller than the known total-curvature bound for a single agent. We formulate multi-agent traffic monitoring as an example of this framework and evaluate our algorithm on it.

Figures & tables

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Multi-Agent Reinforcement Learning with Submodular Reward

    Mar 6, 2026Wenjing Chen, Chengyuan Qian, Shuo Xing +2Cooperative MARLMulti-Agent Reinforcement Learning

  2. Explicit Credit Assignment through Local Rewards and Dependence Graphs in Multi-Agent Reinforcement Learning

    Jan 29, 2026Bang Giang Le, Viet Cuong TaCredit Assignment in RLCredit Assignment

  3. Learning Coordinated Preference for Multi-Objective Multi-Agent Reinforcement Learning

    Jun 12, 2026Pengxin Wang, Lihao Guo, Yi Xie +3Multi-Objective Reinforcement LearningMulti-Agent System Optimization