We study cooperative multi-agent reinforcement learning (MARL) problems in which agents evolve under decoupled noisy dynamics but share a population objective. A canonical example is a mobility operator that orchestrates a fleet of vehicles to meet customer demand. The stochastic and time-varying nature of these problems calls for learning approaches, yet existing MARL algorithms do not scale: learning assignment and routing jointly over the full state-action space becomes prohibitive as the number of agents grows. Formulating the problem over the space of probability measures, we prove a separation principle: the population cost-to-go function is upper bounded by an optimal transport problem whose transportation cost is the target-conditioned single-agent cost-to-go function. This simplifies the multi-agent problem to learning a single-agent policy and coordinating the agents via optimal transport. Building on this principle, we introduce SALT (Separation-based Assignment and Learning via optimal Transport), a family of algorithms that learn a target-conditioned single-agent policy using any standard reinforcement learning algorithm, and then coordinate the agents via optimal transport. Since learning occurs at the single-agent level, SALT scales to fleet sizes where MARL baselines become intractable and transfers without retraining to fleet sizes unseen during training. In a vehicle-delivery experiment on the southern Manhattan road network, where MARL baselines are computationally prohibitive, SALT improves travel time by 15-21% over a shortest-path routing heuristic. In stochastic grid worlds, SALT reduces average travel times by 23-61% relative to MARL baselines and scales to population sizes where these methods fail.
Figures & tables
Figure 1: Overview of SALT . (1) Cooperative MARL learns a joint fleet policy and scales poorly with N . (2) Formulating the problem over probability measures replaces agent labels with an empirical population μt and target distribution ν , but remains intractable. (3) The separation principle decouples assignment from routing, upper bounding the population cost-to-go by an optimal transport assignment with cost j^(s,z) . SALT assigns targets through this optimal transport problem and routes agents with a shared single-agent policy π , yielding scalable and sample-efficient learning.
Figure 2: Average travel time to targets as a function of noise probability p under individual, local, and global noise. Cells show the pooled arithmetic mean over 50 evaluation rollouts from each of 5 independently trained policies. Figure 7 shows the corresponding distributions. Brighter cells indicate worse relative performance. SALT variants consistently outperform standard MARL baselines.
Figure 3: Training environment interactions required by SALT-PPO and MAPPO to attain each reach-rate milestone ( 70 – 99% ) for 10 consecutive batches as population size N increases (grid area scaled proportionally to maintain target density). Each cell reports the mean over 5 training seeds, a dash (–) indicates that no seed attained the milestone within the training budget.
Figure 4: Relative travel-time improvement of SALT-Q over static shortest-path routing on the time-varying Manhattan road network, as a function of fleet size. Boxplots pool 500 evaluation instances from each of 8 training seeds. Boxes span the interquartile range, center lines show medians, and whiskers follow the Tukey 1.5 -interquartile-range rule. The dashed line indicates zero improvement. SALT-Q is trained with 20 vehicles and evaluated without retraining on fleets of 1 – 100 vehicles.
Appendix figures & tables11 assets
Supplementary material from the paper’s appendix.
Appendix
Object
Definition
Intuition
ξ^ts,a
Random element of P(W)
Distribution of noise experienced by agents in (s,a) at time t
ηts,a
Distribution of ξ^ts,a
Describes the probability distribution associated with the noise realizations
ηt
Probability measure in P(P(W)S×A)
Collects all ηts,a across bins, encoding population-level randomness
ρt
λt⊗ξ^ts,a
Joint state-action-noise distribution
Appendix
Table 1: Notation for Appendices A – F .
Quantity
Value
Grid / horizon
11×30 , T=100
Agents / targets
N=7
Training seeds
0 – 4 (5 independent runs)
Evaluation instances
50 per training seed, 250 pooled
Noise probabilities
0,0.1,0.25
Noise modes
individual, local, global
Appendix
Table 2: Shared grid-world training budget and evaluation settings for Section 5.1 .
Hyperparameter
SALT-Q
SALT-DDQN
SALT-PPO
SALT-A2C
Discount γ
0.98
0.98
0.98
0.98
Learning rate
0.25 → 0.02
3×10−4
actor 3×10−4 critic 10−3
actor 3×10−4 critic 10−3
Learning-rate decay
20,000 episodes
–
–
–
Hidden size
–
64
64
64
GAE λ
–
–
0.95
0.95
PPO clip / epochs
–
–
0.2 / 4
–
Appendix
Table 3: Hyperparameters used for SALT in Section 5.1 .
Hyperparameter
MAPPO
IPPO
HAPPO
QMIX
VDN
MFQ
Discount γ
0.98
0.98
0.98
0.98
0.98
0.98
Learning rate
actor 3×10−4 critic 10−3
actor 3×10−4 critic 10−3
actor 3×10−4 critic 10−3
3×10−4
3×10−4
3×10−4
Hidden size
64
64
64
64
64
64
GAE λ
0.95
0.95
0.95
–
–
–
PPO clip / epochs
0.2 / 4
0.2 / 4
0.2 / 4
–
–
–
Entropy coefficient
0.01 → 0.001
0.01 → 0.001
0.01 → 0.001
–
–
–
Appendix
Table 4: Hyperparameters used for MARL baselines in Section 5.1 .
Figure 5: Terminal optimal transport cost as a function of the noise probability p . Each cell shows the pooled arithmetic mean under the training and evaluation protocol described above. Figure 7 shows the corresponding distributions. Brighter cells indicate higher cost.
Figure 6: Reach rate as a function of the noise probability p . Each cell shows the pooled arithmetic mean under the training and evaluation protocol described above. Figure 7 reports the corresponding 95% confidence intervals. Darker cells indicate higher reach rate.
Figure 7: Reach rate, terminal optimal transport cost, and average travel time under the evaluation protocol described above. Reach-rate bars show pooled means and two-sided 95% crossed two-way bootstrap confidence intervals. The remaining panels show the pooled outcome distributions. Boxes span the interquartile range, center lines are medians, and whiskers show the observed minimum and maximum.
Agents N
2
4
6
8
16
32
64
128
Grid dimensions
10×10
14×14
17×17
20×20
28×28
40×40
57×57
80×80
Horizon
20
28
34
40
56
80
114
160
Maximum planned batches
781,250
279,018
153,186
97,656
34,877
12,207
4,283
1,526
Appendix
Table 5: Population sizes and grid sizes used in the scalability experiment.
Quantity
N=20
N=5
Training seeds
0 – 4
0 – 4
Nominal interaction budget
2×109 agent steps
2×109 agent steps
Assignment observations
20,000,000
20,000,000
Population episodes
1,000,000
4,000,000
Learning rate
0.25→0.05
0.25→0.05
Learning-rate decay
800,000 episodes
3,200,000 episodes
Appendix
Table 6: Training settings for the origin–destination coverage experiment.
Figure 8: OD-pair coverage and population-size transfer after training SALT-Q with N=20 or N=5 agents at the same nominal interaction budget. (a) Share of nontrivial evaluation assignments grouped by training count; within each evaluation fleet, the left and right bars correspond to training with N=5 and N=20 . (b) Overall per-agent completion; lines show pooled episode means and shaded regions the episode-level fifth–ninety-fifth percentiles. (c–d) Per-agent completion conditioned on the fraction of assignments satisfying n(s,z)≤20 , shown separately for the two training fleets. Points are means and error bars span the minimum and maximum over five training seeds. The x coordinate is the mean realized fraction within each bin.
Figure 9: Relative travel-time improvement of SALT-Q against nominal shortest-path routing with a static assignment (left), reassignment every five routing steps (center), or reassignment every ten routing steps (right). The evaluation samples and boxplot conventions match Figure 4 .
Cooperative multi-agent reinforcement learning (MARL) trains agents to coordinate toward shared goals under partial information and decentralized control.