STPE-MARL: Spatio-Temporal Multi-Agent Population Evolution Reinforcement Learning

Achieving joint goals efficiently in complex real-world tasks demands effective collaboration among multiple agents. Multi-Agent Reinforcement Learning (MARL) faces two interrelated challenges: limited exploration leads to early convergence on suboptimal behaviors, which in turn exacerbates non-stationarity under partial observability. To address these issues, we propose a novel framework, Spatio-Temporal Multi-agent Population Evolution (STPE-MARL). By integrating Evolutionary Algorithms (EAs) with MARL, our method enhances exploration diversity and facilitates global policy optimization. We further incorporate Graph Neural Networks (GNNs) to mitigate partial observability by encoding permutation symmetry through graph-based message passing. Two GNN-based training modes, Graph Relation and Graph Decomposition, are introduced to extend agents’ receptive fields and capture spatio-temporal dependencies through time-series trajectory sampling. We evaluate STPE-MARL in two complex environments: micromanagement tasks in StarCraft II and large-scale traffic simulations in SUMO (Simulation of Urban MObility). Experimental results demonstrate that STPE-MARL significantly improves policy convergence and outperforms baseline methods, highlighting the complementary roles of EAs in exploration and GNNs in addressing observation limitations.