A Separation Principle for Cooperative Multi-Agent Reinforcement Learning
Organizations: ETH Zürich · Caltech · University of Zürich
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.
Figures & tables
Appendix figures & tables11 assets
Supplementary material from the paper’s appendix.
Appendix
| Object | Definition | Intuition |
| Random element of | Distribution of noise experienced by agents in at time | |
| Distribution of | Describes the probability distribution associated with the noise realizations | |
| Probability measure in | Collects all across bins, encoding population-level randomness | |
| Joint state-action-noise distribution |
| Quantity | Value |
| Grid / horizon | , |
| Agents / targets | |
| Training seeds | – (5 independent runs) |
| Evaluation instances | 50 per training seed, 250 pooled |
| Noise probabilities | |
| Noise modes | individual, local, global |
| Hyperparameter | SALT-Q | SALT-DDQN | SALT-PPO | SALT-A2C |
| Discount | 0.98 | 0.98 | 0.98 | 0.98 |
| Learning rate | 0.25 0.02 | actor critic | actor critic | |
| Learning-rate decay | 20,000 episodes | – | – | – |
| Hidden size | – | 64 | 64 | 64 |
| GAE | – | – | 0.95 | 0.95 |
| PPO clip / epochs | – | – | 0.2 / 4 | – |
| Hyperparameter | MAPPO | IPPO | HAPPO | QMIX | VDN | MFQ |
| Discount | 0.98 | 0.98 | 0.98 | 0.98 | 0.98 | 0.98 |
| Learning rate | actor critic | actor critic | actor critic | |||
| 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 | – | – | – |
| Agents | 2 | 4 | 6 | 8 | 16 | 32 | 64 | 128 |
| Grid dimensions | ||||||||
| 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 |
| Quantity | ||
| Training seeds | – | – |
| Nominal interaction budget | agent steps | agent steps |
| Assignment observations | ||
| Population episodes | ||
| Learning rate | ||
| Learning-rate decay | episodes | episodes |
Cooperative MARL
Cooperative multi-agent reinforcement learning (MARL) trains agents to coordinate toward shared goals under partial information and decentralized control.
See all 263 papers