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:
- 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).
- 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.
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.
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