Continual Graph Multi-Agent Reinforcement Learning

Tommaso Marzi; Ahmed Hendawy; Jan Peters; Carlo D'Eramo; Andrea Cini; Cesare Alippi

cs.LGOct 7, 2026

Continual Graph Multi-Agent Reinforcement Learning

Authors: Tommaso Marzi, Ahmed Hendawy, Jan Peters, Carlo D'Eramo, Andrea Cini, Cesare Alippi

Organizations: IDSIA USI-SUPSI, Università della Svizzera italiana, Lugano, Switzerland · Technical University of Darmstadt, Darmstadt, Germany · Robotics Institute Germany (RIG) · German Research Center for AI (DFKI) · University of Würzburg, Würzburg, Germany · EPFL, Lausanne, Switzerland · Politecnico di Milano, Milan, Italy

Abstract

In Continual Multi-Agent Reinforcement Learning (CMARL), agents learn cooperative policies across sequences of tasks, aiming to adapt effectively to new tasks while preserving the ability to solve previously encountered ones. In many applications, tasks differ in their underlying structure, which can represent, for example, distinct operational conditions or target configurations (e.g., different network topologies in power grids or arrangements in formation control). Existing CMARL methods lack dedicated mechanisms to leverage this structural information when learning new tasks, failing to promote transfer and mitigate forgetting. To fill this gap, we propose Continual Graph Multi-Agent Reinforcement Learning (CGMARL), a novel framework for CMARL problems in which task sequences are mapped into a series of attributed graphs, each modeling a task-specific structure. In CGMARL, each graph determines the environment dynamics (next states and/or rewards) and the number of agents for the corresponding task. Then, we present Graph-based Formation (GRAFO), the first CGMARL benchmark, and show how forgetting arises in this setting. Finally, to address this limitation, we propose Frozen Graph Encoder (FROG), a method that relies on a frozen graph backbone to preserve past structural information in graph-based CMARL policies. Experiments on GRAFO show that pairing FROG with existing CL methods substantially improves performance on multiple CGMARL scenarios.

Figures & tables

Figure 1: Scheme of the CGMARL problem. In the left panel, we illustrate the general setup, in which edges are generated dynamically across timesteps using task-specific connectivity functions (indicated by different colors for edges). In the right panel, we illustrate relevant classes of the CGMARL problem. In Topology Switch (TS), both nodes and edges can change across tasks. In Connectivity Switch (CS), edges can change while the node set is fixed. In Graph Features Switch (GFS), the topology is kept static, and graph features can change; this is highlighted by using different dashed patterns to represent nodes and/or edges.

Figure 2: Example of a GRAFO task with five agents (circles). Left: agent graph identifying the task. Right: current state of the environment, where the green solid cross is the landmark known to all agents, i.e., the target position of the green agent, while the dashed crosses are the target positions of other agents. These positions are defined based on the graph, but are not explicitly provided.

Panel of Table 1 — Table 1: Solved percentage at test time (median $\pm$ standard deviation of $5$ seeds) for two GRAFO tasks in both zero-shot transfer (TRAN.) and continual (CONT.) settings.

Figure 3: Boxplot showing the distribution of

10

independent seeds for the different CL methods (with and without FROG) across the three scenarios, i.e., TS (top), CS (middle), and GFS (bottom). Boxes represent the IQR, horizontal lines indicate medians, and whiskers extend to

1.5\times\text{IQR}


	AFP $\uparrow$	AF $\uparrow$	AP $\uparrow$

FROG	$\bm{0.69}\pm\scriptstyle{0.13}$	$-{0.33}\pm\scriptstyle{0.14}$	$\bm{0.99}\pm\scriptstyle{0.02}$
FROG (RND)	${0.38}\pm\scriptstyle{0.037}$	$\bm{-0.29}\pm\scriptstyle{0.04}$	${0.64}\pm\scriptstyle{0.03}$

Table 2: Aggregated medians (average

\pm

standard deviation) for the different CL methods combined with FROG and FROG (RND) on the TS sequence. Complete boxplots are reported in Fig. 7 .

Figure 4: Boxplot showing the distribution of

10

independent seeds for the different CL methods (with and without FROG) across the TS (inc) and TS (dec) sequences, i.e., the incremental/decremental variants of the TS sequence (top and bottom panels, respectively). Boxes represent the IQR, horizontal lines indicate medians, and whiskers extend to

1.5\times\text{IQR}

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 5: One-step transition in GRAFO. At the beginning of the episode, an initial state in which the agents (colored circles) and known landmark (solid, green cross) positions are randomly assigned is generated. Then, at each step, agents take actions depending on the current state. Each agent’s reward is the negative of the distance to its corresponding target (dashed cross with the same color). In the case of two symmetric agents, i.e., with a non-empty set

{\mathcal{K}}

of structurally-equivalent nodes, a linear sum assignment problem is solved to assign the targets.


	GRAFO- $3$	GRAFO- $4$	GRAFO- $5$	GRAFO- $6$ (1)	GRAFO- $6$ (3)	GRAFO- $7$

InforMARL	$\bm{1}\pm\scriptstyle{0}$	$\bm{1}\pm\scriptstyle{0}$	$\bm{1}\pm\scriptstyle{0}$	$\bm{0.994}\pm\scriptstyle{0.009}$	$\bm{1}\pm\scriptstyle{0}$	$\bm{0.997}\pm\scriptstyle{0.007}$
InforMARL (no GNN)	${0.531}\pm\scriptstyle{0.013}$	${0.328}\pm\scriptstyle{0.091}$	${0.297}\pm\scriptstyle{0.258}$	${0}\pm\scriptstyle{0}$	${0.172}\pm\scriptstyle{0.169}$	${0}\pm\scriptstyle{0}$

Appendix

Table 3: Solved percentage of InforMARL and the variant without GNN in the actor on the single tasks of the TS sequence (reported as median

\pm

standard deviation of

5

seeds).

Figure 6: Boxplot showing the distribution of

10

independent seeds in the sensitivity analysis of

\lambda_{\mu}

for EWC (M) in the TS sequence. Specifically, we consider different values for the regularization coefficient

\lambda_{\mu}

of the action prediction module. The regularization coefficient of the graph encoder is fixed to

\lambda_{\psi}=10^{10}

. When the coefficient for the action module is

\lambda_{\mu}=10^{10}

(pink box), the results coincide with those reported in Fig. 3 . We also report the results achieved by FROG, where we remark that the graph encoder is kept fixed, i.e., the coefficient

\lambda_{\mu}=10^{4}

regularizes only the action prediction module. Boxes represent the IQR, horizontal lines indicate medians, and whiskers extend to

1.5\times\text{IQR}

Figure 7: Boxplot showing the distribution of

10

independent seeds for FROG and FROG (RND) combined with different CL methods in the TS scenario. Boxes represent the IQR, horizontal lines indicate medians, and whiskers extend to

1.5\times\text{IQR}

Figure 8: Boxplot showing the distribution of

10

independent seeds for different CL methods in the TS scenario with and without conditioning on task identities. Boxes represent the IQR, horizontal lines indicate medians, and whiskers extend to

1.5\times\text{IQR}

Figure 9: GRAFO tasks used to define the CGMARL sequences. The green circle is the reference node, i.e., the agent for which the target position corresponds to the reference landmark. Blue circles represent agents for which the corresponding target positions

{\bm{g}}=({\bm{g}}_{1},\dots,{\bm{g}}_{n})

are unknown, and are reported as relative shifts (one per agent) with respect to the green node. Dashed blue nodes indicate agents in

{\mathcal{K}}\subset{\mathcal{G}}

with a structurally equivalent role in the graph, i.e., that can be exchanged without altering the topology and for which a linear assignment with respect to the target positions is solved.


Context	Parameter	Value

Architecture (InforMARL)	Activation	$ReLU$
	Num. of hidden layers (action module)	$2$
	Hidden feature dim (action module)	$128$
	Recurrent unit (action module)	False

Appendix

Table 4: Hyperparameters used in our experiments. We note that the parameters specific to the online variants of EWC and MAS (with and without FROG), i.e., online decay, importance episodes, importance steps, and normalization, are common for all methods.

Explore similar work

Coordination Graphs for Constrained Multi-Agent Reinforcement Learning
Jun 1, 2026Santiago Amaya-Corredor, Miguel Calvo-Fullana, Anders JonssonMulti-Agent Reinforcement Learning Coordination
Department of Engineering, Universitat Pompeu Fabra, Barcelona, Spain
GCT-MARL: Graph-Based Contrastive Transfer for Sample-Efficient Cooperative Multi-Agent Reinforcement Learning
Jun 23, 2026Animesh Animesh, Satheesh K Perepu, Kaushik DeyMulti-Agent Reinforcement Learning Iterative Co-Training
Department of Artificial Intelligence, Indian Institute of Technology Kharagpur, India · Work done during research internship at Ericsson Research, Bangalore, India · Ericsson Research, Bangalore, India
A Self-Evolving Default Action for Cooperative Tasks with Continuous Action Space
Jul 21, 2026Shuangyao HuangMulti-Agent Reinforcement Learning Action Space
Xi’an Jiaotong-Liverpool University School of Internet of Things

Jun 1, 2026, cs.AIJ/K move · Enter open · S save

Coordination Graphs for Constrained Multi-Agent Reinforcement Learning

Santiago Amaya-Corredor, Miguel Calvo-Fullana, Anders Jonsson

Department of Engineering, Universitat Pompeu Fabra, Barcelona, Spain

Multi-Agent Reinforcement Learning Coordination

Open paper AskPDF arXiv

Constrained Multi-agent reinforcement learning (CMARL) faces two intertwined challenges: the joint action space grows exponentially with the number of agents, and additional requirements couple agents in ways that reward structure alone does not capture. We introduce Coordination Graphs for Constrained Multi-Agent Reinforcement Learning (CG-CMARL), a framework that addresses both challenges by combining coordination graphs with Lagrangian duality. The system decomposes the joint problem into pairwise regions, each served by a set of shared Q-functions, one for the primary objective and one for each of the constraints, so that the number of learned models is independent of the number of agents. At execution time, Max-Sum message passing coordinates actions across the factor graph, while a Lagrangian multiplier controls the objective--constraint tradeoff, allowing a single trained model to trace a Pareto front without retraining. We provide convergence guarantees under mild conditions, together with a compositional error bound that decomposes into separate interpretable sources, each traceable to a specific design choice and independently controllable. Experiments on cooperative navigation tasks (where teams of up to 10 agents must coordinate to reach target positions while satisfying pairwise constraints) show that our method produces Pareto fronts dominating established baselines trained at fixed reward-shaping ratios, while scaling to team sizes where centralized approaches become intractable.

Abstract

Explore similar work

Coordination Graphs for Constrained Multi-Agent Reinforcement Learning

GCT-MARL: Graph-Based Contrastive Transfer for Sample-Efficient Cooperative Multi-Agent Reinforcement Learning

A Self-Evolving Default Action for Cooperative Tasks with Continuous Action Space