betaFeedback

WorksComputer Science

Cooperative Multi-Agent Reinforcement Learning with Submodular Trajectory Rewards

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.

Introduction

In standard reinforcement learning (RL), a single agent maximizes an expected sum of stage rewards, which depend on the agent’s current state and action. Extending the single-agent formulation, cooperative multi-agent reinforcement learning (MARL) studies a team of agents that coordinate their actions to maximize a common objective. Each stage reward then depends on the agents’ current joint state and action. A further simplifying assumption is that each stage reward is a sum of the agents’ local rewards [19]. These two forms of additivity separate rewards over time and across agents, respectively. However, in many cooperative applications, the objective is not additive over time or across agents. Without these forms of additivity, an optimal policy may depend on the history of all agents.

In this paper, we consider a common monotone submodular reward defined over the visits along the trajectories of all agents. A visit is a time-state pair (t,s)(t, s) indicating that at least one agent is in state ss at time tt. Submodularity captures diminishing returns both across agents and over time. This setting is relevant to informative sensing and path planning [10, 22], cooperative coverage and biodiversity monitoring [16], and multi-agent persistent monitoring [2, 5, 20]. Traffic monitoring with multiple unmanned aerial vehicles (UAVs) [9, 12, 15] is a form of persistent monitoring that we use as a running example. In this example, monitoring a road adds less value if it was monitored recently or if another UAV monitors it at the same time. To study such rewards, we formulate a submodular multi-agent Markov decision process (MDP) with decoupled dynamics, in which the next state of each agent depends only on its own current state and action.

Emails: {yasaman.zolfimoselo, nikolas.geroliminis, maryam.kamgarpour}@epfl.ch

Related Work

Submodular maximization and path planning. The greedy algorithm achieves a (1−1/e)(1 - 1/e)-approximation for maximizing a monotone submodular set function under a cardinality constraint [14]. This guarantee improves when the function has total curvature c<1c < 1 [6]. These results were extended to settings where the objective function depends on the order of selection [13, 23, 25]. In all these works, removing elements from a feasible selection leaves it feasible. In our setting, visits must form trajectories consistent with the dynamics, so removing a visit can make a feasible selection infeasible. Informative path planning maximizes submodular objectives under such constraints [3, 21]. For multiple robots, sequential allocation yields a team guarantee when each robot’s marginal problem under fixed predecessor policies is solved optimally or with an approximation guarantee [1, 21, 22]. These planning models assume deterministic transition dynamics. Under stochastic dynamics, agents must optimize policies that account for uncertain next states.

Submodular RL. Submodular RL extends these planning models to stochastic dynamics. In this setting, an agent maximizes an expected monotone submodular reward over visits along its trajectory [17, 24]. Global RL generalizes submodular RL to broader classes of trajectory rewards and proposes semi-gradient methods for their optimization [7]. For submodular rewards, constant-factor approximation is generally intractable [17], but a (1−c)(1-c)-factor approximation is possible with total curvature c<1c < 1 [7, 17]. These results are limited to a single agent. Treating a team as one agent makes the joint state space exponential in the number of agents. Moreover, diminishing returns across agents at the same time step can make the (1−c)(1-c) guarantee vacuous even for time-additive rewards, as we show in § 3.1.

Submodular MARL. In the multi-agent setting, Chen et al. [4] consider time-additive rewards that are monotone submodular across agents at each stage. Under known decoupled dynamics, they optimize the policies sequentially and obtain a 12\frac{1}{2}-approximation in time polynomial in the number of agents. Liu et al. [11] study stage rewards defined as marginal gains of a submodular trajectory reward, but their guarantee requires every choice to remain feasible regardless of earlier actions. Hence, the guarantees of Chen et al. [4] and Liu et al. [11] do not cover rewards with diminishing returns over time when the dynamics constrain future visits.

Multi-agent persistent monitoring. Persistent monitoring coordinates mobile agents to revisit important locations [2, 5]. Closest to our setting, Rezazadeh and Kia [20] consider rewards that grow with the time since the last visit and plan over a receding horizon under deterministic dynamics. Their 12\frac{1}{2}-factor approximation is relative to the optimum within each planning horizon, not to the full-horizon optimal return.

To our knowledge, no prior work gives a polynomial-time algorithm with a curvature-dependent guarantee for MARL with submodular trajectory rewards when stochastic dynamics constrain future visits. Our formulation addresses this setting under decoupled dynamics and contains the settings of Chen et al. [4] and Prajapat et al. [17] as special cases, as Remark 1 shows.

Contributions

Building on the above past work, our contributions are summarized as follows.

  1. We introduce a new notion of curvature called pre-window curvature cmc_m, which measures the maximum relative reduction in marginal gains caused by visits before an mm-step window.

  1. Using this notion of curvature, we modify the objective so that stage rewards depend only on the visits of all agents in the last m+1m+1 steps. Jointly maximizing this objective yields a policy that achieves a (1−cm)(1-c_m)-approximation of the optimal return.

  1. We develop Greedy Windowed Policy Optimization (GWPO), which sequentially optimizes each agent’s policy using marginal rewards based on complete predecessor trajectories and its own mm-step history. For fixed mm, it runs in polynomial time and achieves the 1−cm2−cm\frac{1-c_m}{2-c_m} approximation guarantee of Theorem 2 relative to the optimal global history-dependent return.

  1. We formulate multi-UAV traffic monitoring as a submodular multi-agent MDP, capturing diminishing returns from repeated monitoring across UAVs and time, and we evaluate GWPO in this setting.

Problem Setting

In this section, we first introduce the notation. We then recall submodularity and curvature, which our analysis builds on. Finally, we define the submodular multi-agent MDP and the optimization problem, and illustrate the framework through traffic monitoring.

Notation

Throughout the paper, we write [n]={1,…,n}[n]=\{1,\ldots,n\} for n≥1n \ge1, and [0]=∅[0]=\emptyset. Bold symbols denote joint quantities over the NN agents. For example, x\boldsymbol{x} denotes (x1,…,xN)(x_1,\ldots,x_N). For a function gg on a product set X×Y\mathcal{X}\times\mathcal{Y} and z=(x,y)\boldsymbol{z}=(x,y), we write g(z)g(\boldsymbol{z}) and g(x,y)g(x,y) interchangeably. Let P(X)\mathcal{P}(\mathcal{X}) denote the probability simplex over a finite set X\mathcal{X}. Fix a set S\mathcal{S}. For a set B⊆{0,1,2,…}×SB \subseteq\{0,1,2,\ldots\}\times\mathcal{S} and integers tt and t′t', let

Bt:t′={(u,s)∈B:t≤u≤t′}.(1)B_{t:t'}=\{(u,s)\in B:t\leq u\leq t'\}. \tag*{(1)}

For t′=tt'=t, we write BB for Bt:tB_{t:t}. For a set BiB_i of agent ii, we write Bi,t:t′B_{i,t:t'}, and for a tuple B=(B1,…,BN)\boldsymbol{B}=(B_1,\ldots,B_N) of such sets, we apply this definition componentwise, Bt:t′=(B1,t:t′,…,BN,t:t′)\boldsymbol{B}_{t:t'}=(B_{1,t:t'},\ldots,B_{N,t:t'}).

Submodularity and Curvature

We recall monotone submodular functions and their total curvature.

Definition 1 (Monotone submodular function). Let V\mathcal{V} be a finite ground set and let F:2V→R≥0F:2^{\mathcal{V}}\to\mathbb{R}_{\ge0} satisfy F(∅)=0F(\varnothing)=0. For X,B⊆VX,B\subseteq\mathcal{V}, the marginal gain of XX given BB is

Δ(X∣B)=F(X∪B)−F(B),\Delta(X\mid B)=F(X\cup B)-F(B),

abbreviated as Δ(x∣B)\Delta(x\mid B) when X={x}X=\{x\}. The function FF is monotone if Δ(x∣B)≥0\Delta(x\mid B)\ge0 for every B⊆VB\subseteq\mathcal{V} and x∈Vx\in\mathcal{V}. It is submodular if

Δ(x∣B)≥Δ(x∣B′)\Delta(x\mid B)\ge\Delta(x\mid B')

whenever B⊆B′B\subseteq B' and x∈Vx\in\mathcal{V}.

Submodularity states that marginal gains decrease as BB grows, but it does not quantify how much Δ(x∣B)\Delta(x\mid B) can decrease relative to Δ(x∣∅)=F({x})\Delta(x\mid\varnothing)=F(\{x\}). Total curvature measures this worst-case relative decrease.

Definition 2 (Total curvature). The total curvature of a normalized monotone submodular function FF is

c=1−min⁡B⊆V, x∈V∖BF({x})>0Δ(x∣B)F({x}).c=1-\min_{\substack{B\subseteq\mathcal{V},\ x\in\mathcal{V}\setminus B\\F(\{x\})>0}}\frac{\Delta(x\mid B)}{F(\{x\})}.

For every B⊆VB\subseteq\mathcal{V} and x∈V∖Bx\in\mathcal{V}\setminus B, Δ(x∣B)≥(1−c)F({x})\Delta(x\mid B)\ge(1-c)F(\{x\}), including when F({x})=0F(\{x\})=0. An additive function has c=0c=0. At the other extreme, c=1c=1 occurs exactly when some element with F({x})>0F(\{x\})>0 has zero marginal gain in the presence of a set of other elements.

Submodular Multi-Agent MDP

With submodularity and curvature defined, we now introduce the submodular multi-agent MDP on which our method builds.

Definition 3 (Submodular multi-agent MDP). A submodular multi-agent MDP is specified by the tuple

⟨N,H,S,A,{Pi}i∈[N],{ρi}i∈[N],F⟩,\langle N,H,\mathcal{S},\mathcal{A},\{P_i\}_{i\in[N]},\{\rho_i\}_{i\in[N]},F\rangle,

where NN denotes the number of agents and HH is the horizon length. The finite state space of each agent is S\mathcal{S}, also called the local state space. The joint state space is S=SN\mathcal{S}=\mathcal{S}^{N}. The finite action space of each agent is A\mathcal{A}, and the joint action space is A=AN\mathcal{A}=\mathcal{A}^{N}. The transition dynamics of agent ii are Pi=(Pi,0,…,Pi,H−1)P_i=(P_{i,0},\ldots,P_{i,H-1}), where Pi,t:S×A→D(S)P_{i,t}:\mathcal{S}\times\mathcal{A}\to\mathcal{D}(\mathcal{S}) and Pi,t(⋅∣s,a)P_{i,t}(\cdot\mid s,a) is the distribution of its state at time t+1t+1. The transition dynamics are decoupled, so the joint transition dynamics P=(P1,…,PN)\mathbf{P}=(P_1,\ldots,P_N) give the joint next-state distribution

Pt(s′∣s,a)=∏i∈[N]Pi,t(si′∣si,ai).P_t(s'\mid s,a)=\prod_{i\in[N]}P_{i,t}(s_i'\mid s_i,a_i).

The initial state distribution of agent ii is ρi∈D(S)\rho_i\in\mathcal{D}(\mathcal{S}). Initial states are independent, so ρ=∏i∈[N]ρi\rho=\prod_{i\in[N]}\rho_i. The common reward is a monotone submodular function F:2V→R≥0F:2^{\mathcal{V}}\to\mathbb{R}_{\ge0} over trajectories. Its ground set V={0,…,H}×S\mathcal{V}=\{0,\ldots,H\}\times\mathcal{S} contains all possible visits, with Vt:t′\mathcal{V}_{t:t'} defined as in (1). We assume that the reward function satisfies F(B)>0F(B)>0 for at least one B⊆VB\subseteq\mathcal{V}.

Agent ii’s trajectory is the set of its visits,

τi={(t,si,t):0≤t≤H}⊆V,\tau_i=\{(t,s_{i,t}):0\le t\le H\}\subseteq\mathcal{V},

and the joint trajectory is τ=(τ1,…,τN)\tau=(\tau_1,\ldots,\tau_N). In set operations we identify a tuple of trajectories with the union of its components. Using the notation in (1), this gives

F(τt:t′):=F(⋃i∈[N]τi,t:t′).F(\tau_{t:t'}) := F\left(\bigcup_{i\in[N]}\tau_{i,t:t'}\right).

For example, if τ1={(0,s1)}\tau_1=\{(0,s_1)\} and τ2={(0,s2)}\tau_2=\{(0,s_2)\}, then τ=(τ1,τ2)\tau=(\tau_1,\tau_2) is treated as {(0,s1),(0,s2)}\{(0,s_1),(0,s_2)\} whenever it appears in a set operation.

The formulation and analysis extend to monotone submodular rewards on the ground set {0,…,H−1}×S×A\{0,\ldots,H-1\}\times\mathcal{S}\times\mathcal{A} by including actions in the trajectories. For simplicity, we present the results using V={0,…,H}×S\mathcal{V}=\{0,\ldots,H\}\times\mathcal{S}.

References

  1. [1]Nikolay Atanasov, Jerome Le Ny, Kostas Daniilidis, and George J Pappas. Decentralized active information acquisition: Theory and application to multi-robot SLAM. In International Conference on Robotics and Automation (ICRA), pages 4775–4782. IEEE, 2015.DOI
  2. [2]Christos G. Cassandras, Xuchao Lin, and Xu Chu Ding. An optimal control approach to the multi-agent persistent monitoring problem. IEEE Transactions on Automatic Control, 58(4):947–961, 2013.
  3. [3]Chandra Chekuri and Martin Pal. A recursive greedy algorithm for walks in directed graphs. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 245–253. IEEE, 2005.DOI
  4. [4]Wenjing Chen, Chengyuan Qian, Shuo Xing, Yi Zhou, and Victoria Crawford. Multi-agent reinforcement learning with submodular reward. In International Conference on Machine Learning, 2026.arxiv.org/abs/2603.06810
  5. [5]Yann Chevaleyre. Theoretical analysis of the multi-agent patrolling problem. In IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT), pages 302–308, 2004.DOI
  6. [6]Michele Conforti and Gérard Cornuéjols. Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem. Discrete Applied Mathematics, 7(3):251–274, 1984.DOI
  7. [7]Riccardo De Santi, Manish Prajapat, and Andreas Krause. Global reinforcement learning: Beyond linear and convex rewards via submodular semi-gradient methods. In International Conference on Machine Learning, pages 10235–10266. PMLR, 2024.arxiv.org/abs/2407.09905
  8. [8]Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13–30, 1963.
  9. [9]Konstantinos Kanistras, Goncalo Martins, Matthew J Rutherford, and Kimon P Valavanis. A survey of unmanned aerial vehicles (UAVs) for traffic monitoring. In 2013 International Conference on Unmanned Aircraft Systems (ICUAS), pages 221–234. IEEE, 2013.DOI
  10. [10]Andreas Krause, Ajit Singh, and Carlos Guestrin. Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies. Journal of Machine Learning Research, 9:235–284, 2008.
  11. [11]Jing Liu, Luca Ballotta, Yangyang Yang, Fangfei Li, Yang Tang, and Ruggero Carli. Submodular policy learning for distributed task allocation in open multi-agent systems. arXiv preprint arXiv:2608.14390, 2026.arxiv.org/abs/2608.14390
  12. [12]Marko Maljkovic and Nikolas Geroliminis. On learning-based traffic monitoring with a swarm of drones. In European Control Conference (ECC), pages 1842–1847. IEEE, 2025.arxiv.org/abs/2503.21433
  13. [13]Marko Mitrovic, Ehsan Kazemi, Moran Feldman, Andreas Krause, and Amin Karbasi. Adaptive sequence submodularity. In Advances in Neural Information Processing Systems, volume 32, 2019.arxiv.org/abs/1902.05981
  14. [14]George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. An analysis of approximations for maximizing submodular set functions—I. Mathematical Programming, 14(1):265–294, 1978.DOI
  15. [15]Fatma Outay, Hanan Abdullah Mengash, and Muhammad Adnan. Applications of unmanned aerial vehicle (UAV) in road safety, traffic and highway infrastructure management: Recent advances and challenges. Transportation Research Part A: Policy and Practice, 141:116–129, 2020.DOI
  16. [16]Manish Prajapat, Matteo Turchetta, Melanie Zeilinger, and Andreas Krause. Near-optimal multi-agent learning for safe coverage control. In Advances in Neural Information Processing Systems, volume 35, pages 14998–15012, 2022.arxiv.org/abs/2210.06380
  17. [17]Manish Prajapat, Mojmir Mutny, Melanie Zeilinger, and Andreas Krause. Submodular reinforcement learning. In International Conference on Learning Representations, pages 15190–15212, 2024.arxiv.org/abs/2307.13372
  18. [18]Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 1994.
  19. [19]Guannan Qu, Adam Wierman, and Na Li. Scalable reinforcement learning of localized policies for multi-agent networked systems. In Learning for Dynamics and Control, pages 256–266. PMLR, 2020.
  20. [20]Navid Rezazadeh and Solmaz S. Kia. A submodular receding horizon solution for mobile multi-agent persistent monitoring. Automatica, 127: 109460, 2021.arxiv.org/abs/1908.04425
  21. [21]Amarjeet Singh, Andreas Krause, Carlos Guestrin, and William J. Kaiser. Efficient informative sensing using multiple robots. Journal of Artificial Intelligence Research, 34:707–755, 2009.DOI
  22. [22]Amarjeet Singh, Andreas Krause, and William J. Kaiser. Nonmyopic adaptive informative path planning for multiple robots. In International Joint Conference on Artificial Intelligence, 2009.
  23. [23]Sebastian Tschiatschek, Adish Singla, and Andreas Krause. Selecting sequences of items via submodular maximization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.DOI
  24. [24]Ruosong Wang, Hanrui Zhang, Devendra Singh Chaplot, Denis Gragaric, and Ruslan Salakhutdinov. Planning with submodular objective functions. arXiv preprint arXiv:2010.11863, 2020.arxiv.org/abs/2010.11863
  25. [25]Zhenliang Zhang, Edwin K. P. Chong, Ali Pezeshki, and William Moran. String submodular functions with curvature constraints. IEEE Transactions on Automatic Control, 61(3):601–616, 2016.DOI

Paper details

vlnc:W_4873j6u3
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

generative AI tools

View statement
Looking for related papers…
Contents