Enhancing Graph-based Coordination with Evolutionary Algorithms for Episodic Multi-agent Reinforcement Learning

Multi-agent Reinforcement Learning (MARL) has made significant progress in addressing coordination problems, but two key challenges persist in environments with partial observability: limited exploration and inaccurate evaluation of individual agents. To address these challenges, we propose a novel MARL framework that integrates Evolutionary Algorithms (EAs), episodic learning, and curiosity-driven exploration to optimize the coordination of joint policies using graph-based methods, named EECG. EAs are employed for their global optimization capabilities, particularly through population diversity and a gradient-free search mechanism, to enhance policy exploration. Initially, multiple agent teams explore and learn independently while sharing a common experience pool to enable data diversity. During the evolution phase, new joint policies are generated through crossover, mutation, and pareto-based selection. During the RL phase, diverse data is used to model and update the relationships among agents via Graph Neural Networks (GNNs), which help evaluate the effectiveness of individual agents' behaviors. GNNs treat agents as nodes and their interactions as edges, capturing coordination relationships effectively while dynamically assigning representations to nodes and edges. Furthermore, curiosity-based exploration motivates teams to discover new states, while a memory system stores high-reward experiences. We evaluated EECG on several benchmarks, including StarCraft II, SUMO autonomous driving, and the Multi-Agent Particle Environment. Our empirical results show that EECG consistently outperforms current baselines, with its components significantly contributing to faster convergence, especially by improving exploration and agent coordination. Our code is available: https://github.com/MercyM/EECG.