A Separation Principle for Cooperative Multi-Agent Reinforcement Learning

We study cooperative multi-agent reinforcement learning (MARL) problems in which agents evolve under decoupled noisy dynamics but are coupled via a population objective. A canonical example is a mobility operator that orchestrates a fleet of vehicles in an urban environment 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. By studying the problem as a control problem over probability measures, we prove a separation principle: the population-level 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 result simplifies the multi-agent problem to learning a single-agent policy and coordinating the agents via optimal transport. Thus, 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 RL algorithm, and then coordinate the agents via optimal transport. Because 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 in south Manhattan’s road network, where MARL baselines are computationally prohibitive, SALT improves travel times by up to 20% over a shortest-path routing heuristic and transfers without retraining to different fleet sizes. In stochastic grid worlds, SALT reduces average travel times by more than 40% relative to MARL baselines and scales to population sizes where these methods fail.