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 cm, which quantifies how states visited more than m 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+1 states, we propose a greedy algorithm that exploits the decoupled dynamics to optimize local policies sequentially. For fixed m, the algorithm achieves a 2−cm1−cm 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/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
Figure 1: Part of the road grid with five UAV positions s1,…,s5 . For i≤4 , the roads C(si) monitored from si share the color of si . Each dashed road in C(s5) is colored, so it is also monitored from one of s1,…,s4 .
Figure 2: Performance improvement and computational cost of memory in GWPO. (a) Return improvement of GWPO with different memory lengths m over GPO [ 4 ] for N=20 agents and different recovery rules. (b) Computation time for different numbers of agents N , comparing GWPO with m=0,3 and GPO at β=0.4 .
Figure 3: Return gap between each baseline and GWPO with m=3 at β=0.4 , as a percentage of the GWPO return. Negative values indicate higher returns for GWPO. SubPO-M and SubPO-NM are allowed computation times of (a) TN , (b) 5TN , and (c) 20TN , where TN is the computation time of GWPO for N agents.
Appendix figures & tables11 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: The m -step window moving from time t to time t+1 . Each row is the trajectory of one agent, and the arrows are transitions under its dynamics. (a) At time t , the window covers times t−m to t−1 , and earlier visits form the pre-window part. (b) After the transition to time t+1 , the window shifts by one step, and the visits at time t−m join the pre-window part. Pre-window curvature cm bounds how much pre-window visits, of any agent, reduce the marginal gain of a current visit.
Figure 5: Monitoring times of road e around the added element xt=(t,s) . Filled circles denote monitoring times from Z , the open square denotes the nearest monitoring time from B , and the cross denotes xt . Elements of B occur before time t−m , so adding B changes the earlier gap from ℓ− to min{ℓ−,ℓB} and leaves the later gap ℓ+ unchanged.
Figure 6: History-augmented state of agent i with memory length m , for t≥m . The augmented state s~i,t contains the history hi,t (blue) and the current state si,t (orange). The next state si,t+1 is drawn from Pi,t , and the history appends si,t and drops the oldest state si,t−m (dashed).
Figure 7: Adding an agent lowers the windowed objective in the example of Appendix D.4 . Shaded nodes are visits to state a , which monitors road e . The gray region denotes the window at time 2 , and the values below the axis are the stage rewards, which sum to the windowed objective. (a) With agent 1 alone, the window at time 2 contains no visit to a . (b) With both agents, the window at time 2 contains the visit (1,a) of agent 2. This visit lowers the stage reward at time 2 , although the true reward F increases.
β
m
cm
Approximation factor
0.1
0
0.905
0.087
0.1
3
0.670
0.248
0.4
0
0.670
0.248
0.4
3
0.202
0.444
0.8
0
0.449
0.355
0.8
3
0.041
0.490
Appendix
Table 1: Pre-window curvature cm=e−β(m+1) and the approximation factor (1−cm)/(2−cm) of Theorem 2 for the traffic-monitoring reward at the listed recovery rates β and memory lengths m .
N=6
N=20
K
ϵ
J
K
ϵ
J
17
1.19×10−2
0.6635±0.0064
17
1.20×10−2
1.8028±0.0116
166
3.79×10−3
0.6711±0.0050
173
3.77×10−3
1.8050±0.0058
1,656
1.20×10−3
0.6654±0.0016
1,730
1.19×10−3
1.8034±0.0067
16,556
3.80×10−4
0.6663±0.0005
17,295
3.77×10−4
1.8021±0.0055
165,556
1.20×10−4
0.6661±0.0002
172,952
1.19×10−4
1.8015±0.0009
Appendix
Table 2: Sample counts K , associated ϵ , and returns J for GWPO with m=3 , β=0.4 , and uniform initial state distributions. We fix δ=10−6 . Each return is the mean over seeds {1,2,3} with its 95% confidence interval. The second row gives the counts used in the remaining experiments.
SubPO-M
SubPO-NM
N
Depth
Width
Learning rate
Depth
Width
Learning rate
2
1
512
10−3
2
256
10−3
6
1
256
10−3
1
512
3×10−4
10
1
512
10−3
1
512
3×10−4
15
1
512
3×10−4
1
512
10−3
20
1
256
10−3
1
512
10−3
Appendix
Table 3: Selected neural network architectures and hyperparameters for SubPO . Depth denotes the number of ReLU layers; the recurrent policy additionally uses one GRU layer.
Figure 8: Returns of GWPO with m=3 , GPO, and the two SubPO variants at β=0.4 . From left to right, the allowed computation times for SubPO are TN , 5TN , and 20TN . SubPO curves show means over five training seeds with 95% confidence intervals. GWPO and GPO each use a single seed.
N
GWPO
Policy
TN
5TN
20TN
2
0.2484
SubPO-M
0.2526±0.0019
0.2551±0.0014
0.2560±0.0014
SubPO-NM
0.2552±0.0008
0.2570±0.0003
0.2578±0.0003
6
0.6691
SubPO-M
0.6747±0.0026
0.6888±0.0013
0.6909±0.0020
SubPO-NM
0.6714±0.0027
0.6979±0.0019
0.7095±0.0029
10
1.0312
SubPO-M
1.0254±0.0041
1.0545±0.0035
1.0583±0.0021
SubPO-NM
0.9884±0.0054
1.0657±0.0040
1.0841±0.0033
Appendix
Table 4: Returns of the selected policies at β=0.4 with uniform initial state distributions. The SubPO budgets use the isolated timing calibration and 10% allowance described above. Each SubPO entry is the mean over five training seeds ± the half-width of its 95% confidence interval. GWPO with m=3 uses seed 1. Intervals describe training-seed variation on the fixed map and evaluation states.
Figure 9: Return differences between each baseline and GWPO with m=3 , expressed as percentages of the GWPO return, at β=0.1 (top) and β=0.8 (bottom). Negative values indicate higher returns for GWPO. From left to right, the allowed computation times for SubPO are TN , 5TN , and 20TN . SubPO curves show means over five training seeds with 95% confidence intervals. GWPO and GPO each use a single seed.
Figure 10: Training of SubPO-M and SubPO-NM at β=0.4 . Curves show the highest validation return reached by each epoch, averaged over five training runs with 95% confidence intervals. A curve ends when all five runs have stopped. Markers indicate the epoch budgets corresponding to TN , 5TN , and 20TN that fall within each curve. The horizontal line shows the test return of GWPO with m=3 .
Cooperative multi-agent reinforcement learning (MARL) trains agents to coordinate toward shared goals under partial information and decentralized control.
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(H2KSAT) over T episodes.
Wenjing Chen, Chengyuan Qian, Shuo Xing +2
Department of Computer Science and Engineering, Texas A&M University
To promote cooperation in Multi-Agent Reinforcement Learning, the reward signals of all agents can be aggregated together, forming global rewards that are commonly known as the fully cooperative setting. However, global rewards are usually noisy because they contain the contributions of all agents, which have to be resolved in the credit assignment process. On the other hand, using local reward benefits from faster learning due to the separation of agents' contributions, but can be suboptimal as agents myopically optimize their own reward while disregarding the global optimality. In this work, we propose a method that combines the merits of both approaches. By using a graph of interaction between agents, our method discerns the individual agent contribution in a more fine-grained manner than a global reward, while alleviating the cooperation problem with agents' local reward. We also introduce a practical approach for approximating such a graph. Our experiments demonstrate the flexibility of the approach, enabling improvements over the traditional local and global reward settings.
Bang Giang Le, Viet Cuong Ta
Human-Machine Interaction Laboratory VNU University of Engineering and Technology, Hanoi, Vietnam
Cooperative multi-objective multi-agent reinforcement learning (MOMARL) models team decision making under multiple, potentially conflicting objectives. In this setting, conflicts arise not only across objectives but also across agents with different observations, roles, and contributions. We propose Preference Coordinated Multi-agent Policy Optimization (PCMA), which learns coordinated agent-specific preferences to enable complementary trade-offs among agents. Theoretically, we formulate cooperative MOMARL as a team-optimal equilibrium problem, and show that, under suitable conditions, preference diversity yields a first-order improvement in the team objective. Experiments on multiple cooperative MOMA environments and a practical traffic-control scenario show that PCMA improves both performance and trade-off coordination.
Pengxin Wang, Lihao Guo, Yi Xie +3
Department of Electrical and Computer Engineering, University of Arizona