A Separation Principle for Cooperative Multi-Agent Reinforcement Learning

Lucia Pezzetti, Nicolas Lanzetti, Antonio Terpin, Florian Dörfler, Giorgia RamponiarXiv 2026 · arXiv

TL;DR

The SALT framework breaks the "curse of dimensionality" in cooperative multi-agent reinforcement learning (MARL) by mathematically separating agent assignment from individual routing. By leveraging a novel separation principle based on optimal transport, SALT enables training on single-agent tasks that scale to massive fleets and generalize to unseen population sizes without retraining.

What Problem Does This Paper Address?

Imagine managing a fleet of hundreds of autonomous delivery vehicles in a city. At every moment, you must decide two things: which vehicle should serve which request (assignment) and how each vehicle should navigate to its destination (routing).

These decisions are tightly coupled—the best assignment depends on actual travel times, which are influenced by stochastic factors like traffic lights and congestion. Standard MARL approaches try to learn a joint policy for the entire fleet. However, the joint state-action space grows exponentially with the number of agents, making these methods computationally prohibitive beyond a handful of agents. Conversely, simple heuristics like "assign to the nearest vehicle based on shortest path" often fail because they ignore the underlying stochasticity of the environment.

Methods

The authors introduce SALT (Separation-based Assignment and Learning via optimal Transport), which simplifies the complex multi-agent problem into two manageable steps:

  1. Single-Agent Learning: Instead of learning a joint policy, SALT learns a shared, target-conditioned single-agent policy $\pi(a|s, z)$ and its corresponding cost-to-go function $\hat{j}(s, z)$. This can be done using any standard RL algorithm (e.g., PPO, Q-learning).
  2. Optimal Transport Coordination: The agents are coordinated by solving an Optimal Transport (OT) problem. The learned single-agent cost-to-go $\hat{j}$ serves as the "transportation cost" to assign agents to targets.

The core theoretical contribution is a Separation Principle. The authors prove that for agents with decoupled dynamics sharing a population objective, the total population cost-to-go is upper-bounded by this OT assignment. This justifies decoupling the global coordination from local control.

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.

Datasets

The researchers evaluated SALT on two primary benchmarks:

  • Stochastic Grid Worlds: A controlled environment where agents must reach targets while facing random movement perturbations. This was used to test scalability from $N=2$ up to $N=128$ agents.
  • Manhattan Urban Logistics: A high-fidelity simulation of the southern Manhattan road network (2,087 intersections, 4,255 roads) using real-world map data from OpenStreetMap. It includes realistic traffic light cycles and stochastic congestion noise.

Key Insights and Ideas

  • Averaging Out Noise: While exact separation of assignment and routing was previously known for deterministic systems, this paper proves it holds as a useful upper bound in stochastic settings. By "averaging out" future noise in the single-agent cost function, the OT solver can make robust global assignments.
  • Permutation Invariance: By formulating the problem over probability measures (treating the fleet as a distribution rather than labeled individuals), the learning complexity becomes independent of the number of agents.
  • Zero-Shot Transfer: Because the policy is learned at the single-agent level, a model trained with 20 vehicles can be deployed on a fleet of 100 vehicles (or just 1) without any additional training.
  • Trajectory Pooling: During training, trajectories from all $N$ agents are pooled to update the single shared policy, significantly boosting sample efficiency.

Key Results

  • Superior Performance: In stochastic grid worlds, SALT variants reduced average travel times by 23–61% compared to state-of-the-art MARL baselines like MAPPO and QMIX.
  • Massive Sample Efficiency: Using PPO as the base learner, SALT reached performance milestones with up to 480× fewer environment interactions than MAPPO.
  • Extreme Scalability: SALT successfully scaled to $N=128$ agents, whereas MAPPO failed to reach even basic performance milestones for $N=8$ within the same computational budget.
  • Real-World Viability: In the Manhattan logistics task, SALT improved travel times by 15–21% over a standard shortest-path routing heuristic.
**Figure 2 (from paper Fig 6):** Reach rate comparison. SALT variants (top rows) consistently achieve near 100% reach rates across different noise levels, significantly outperforming standard MARL baselines (bottom rows).

Limitations and Future Work

  • Decoupled Dynamics: The current theory assumes agents' dynamics are decoupled. It does not explicitly account for "hard" interactions like physical collisions or narrow bottlenecks where agents must wait for one another.
  • Objective Constraints: The separation principle relies on a terminal cost that can be expressed via optimal transport. It may not directly apply to non-transport objectives (e.g., formation flying with specific relative distance constraints).
  • Target Generalization: The single-agent policy must generalize well across the entire target space. If targets in a new environment are sampled from a distribution very different from the training one, performance may degrade.

The authors suggest that extending this principle to "weakly coupled" systems (where agents have minor interactions like soft congestion) is a promising direction for future research.

Summary updated

Abstract

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.
BibTeX
@misc{pezzetti2026separation,
  author = {Lucia Pezzetti and Nicolas Lanzetti and Antonio Terpin and Florian Dörfler and Giorgia Ramponi},
  title = {{A Separation Principle for Cooperative Multi-Agent Reinforcement Learning}},
  year = {2026},
  eprint = {2611.09644},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.09644},
}
Figure