PaperlayerView exact revision on arXiv

Source-linked AI summary

Continual Graph Multi-Agent Reinforcement Learning

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

arXiv:2610.10302v1cs.LG

TL;DR

Continual MARL methods often train on one problem, while task sequences can involve changing graph structures. CGMARL models these tasks with attributed graphs, and FROG pairs a frozen graph encoder with standard continual-learning methods; experiments on GRAFO show consistent performance improvements across scenarios.

  • Problem

    Many MARL methods train agents on a single problem, and standard continual-learning approaches do not account for forgetting in graph representation learning.

    Source: §1 · p. 1, §5.2 · p. 6

  • Method

    CGMARL represents task sequences as attributed graphs, while FROG decouples graph representation learning from action prediction using a frozen graph backbone.

    Source: §1 · p. 2, §5.2 · p. 6, §8 · p. 10

  • Results

    Across three CGMARL scenarios, FROG consistently improves performance over standard continual-learning counterparts and is generally less prone to forgetting, with an exception for EWC on the TS sequence.

    Source: §6.1 · p. 8

  • Takeaways & Limitations

    GRAFO provides a benchmark for designing arbitrary CGMARL task sequences and studying transfer and forgetting across graphs.

    Source: §1 · p. 2

    The considered setting assumes homogeneous agents with identical single-agent policies.

    Source: §2 · p. 3

Abstract

from arXiv · show

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.

1 Introduction

Continual MARL must adapt to unfamiliar tasks without losing performance on earlier ones, but task-specific structure is largely overlooked. The paper formalizes CGMARL, introduces GRAFO, and proposes FROG to address structural forgetting.

1 Introduction

  • In CMARL, multiple learners must adapt to new tasks while preserving earlier performance, despite other agents changing their behavior during learning.This couples adaptation to environmental change with adaptation to teammates’ policy updates.Source: §1 · pp. 1–2
  • Task-specific structures shape environment dynamics, yet existing CMARL frameworks and standard continual-learning methods largely overlook structural information.Graphs offer a way to represent agents as nodes and their dependencies as edges.Source: §1 · p. 2
  • CGMARL models task sequences as attributed graphs that determine task structure, environment dynamics, and agent count.The framework also formalizes this problem setting and its task sequences.Source: §1 · p. 2
  • GRAFO is introduced as the first CGMARL benchmark, while FROG freezes a graph backbone and can pair with standard CL methods to mitigate forgetting.The paper reports that FROG paired with existing CL methods improves performance across multiple CGMARL sequences.Source: §1 · p. 2

2 Preliminaries

The preliminaries represent cooperative MARL as a Dec-POMDP and CMARL as a sequence of tasks. Agents share a joint objective, with homogeneous agents assumed in the setup.

2 Preliminaries

  • A cooperative MARL problem is modeled as a Dec-POMDP with agents, states, observations, actions, transition and reward functions, and a discount factor.The transition and reward functions depend on the joint state and action.Source: §2 · p. 2
  • The agents learn a joint policy to maximize expected discounted cumulative reward, with identical single-agent policies assumed for homogeneous agents.The policy is composed of agent-specific policies.Source: §2 · pp. 2–3
  • CMARL models learning as a sequence of tasks drawn from a fixed but unknown distribution, with task components such as agent sets, transitions, or rewards potentially differing.Each task lasts for a fixed number of iterations.Source: §2 · p. 3

3 Continual Graph MARL

The section defines graph-based MARL tasks and extends continual MARL to sequences identified by attributed graphs. It distinguishes task classes according to whether topology or graph features change.

3.1 Graph-based MARL Task

  • Graph-based MARL equips a Dec-POMDP with an attributed graph whose structure determines transitions and/or rewards, while state-dependent connectivity can change edges during an episode.Static node and edge features are distinct from dynamic features represented by agents’ observations.Source: §3.1 · p. 3

3.2 CGMARL Sequence

  • CGMARL represents each task by a graph drawn from an unknown distribution, with that graph identifying the task and determining its graph-dependent transition and reward functions.The framework assumes the graph-dependent dynamics are fixed across tasks; the figure illustrates dynamic edge generation and the task classes.Source: §3.2 · pp. 3–4, Figure 1 · p. 4

3.2.1 Topology Switch

  • In Topology Switch, each task has a fixed edge set, but node and edge sets may differ between tasks.Traffic networks with different topologies are one motivating example.Source: §3.2.1 · p. 4

3.2.2 Connectivity Switch

  • Connectivity Switch keeps the node set fixed while task-specific edge configurations and graph features may change.The setting is motivated by power grids whose connections vary with operational conditions.Source: §3.2.2 · p. 5

3.2.3 Graph Features Switch

  • Graph Features Switch keeps topology fixed and varies static node or edge features across tasks.Examples include robot configurations with task-dependent limb lengths or node-level body masses.Source: §3.2.3 · p. 5

4 GRAFO Benchmark

GRAFO is a graph-based navigation benchmark for generating CGMARL task sequences. Agents use a task graph to infer a formation when only one target position is explicitly known.

4 GRAFO Benchmark

  • GRAFO supports arbitrarily long CGMARL sequences in which a static task graph determines the agents’ target configuration.Agents must use graph structure to identify targets that are not directly observable.Source: §4 · pp. 5–6
  • In the five-agent example, the graph identifies the task, while only the green agent’s target is explicitly shown and the other targets are graph-defined.The other target positions are not explicitly provided in the environment state.Source: Figure 2 · p. 5
  • The discussed Connectivity Switch variant with within-task state-dependent edges is left for future work when fixed dynamics restrict edge configurations and induce task similarity.The limitation concerns this variant, not the stated benchmark generally.Source: §4 · p. 5

5 Emergence of Forgetting in CGMARL

This section shows how graph-dependent dynamics make continual learning difficult for GNN-based policies, then presents FROG, which freezes the graph encoder to mitigate forgetting while the action module adapts.

5.1 GNN-based Policies in Graph-based MARL

  • Although GNNs process graphs of varying sizes, their learned local rules may not apply when graph-dependent dynamics change, requiring previously learned rules to be overwritten.The authors identify this as a reason GNN-based policies are prone to forgetting across CGMARL sequences.Source: §5.1 · p. 6
  • InforMARL solves GRAFO-3 and GRAFO-5 individually but transfers poorly across target formations, and sequential training completely forgets the first task.The reported comparison covers zero-shot transfer and continual training on both tasks.Source: §5.1 · p. 6, Table 1 · p. 6

5.2 FROG: A Simple Approach to Mitigate Forgetting in CGMARL

  • FROG freezes the graph encoder after learning the first task, preserving its parameters while the action module adapts to new tasks alongside existing continual-learning methods.The frozen encoder still generates distinct representations for task-specific graphs.Source: §5.2 · pp. 6–7

6 Empirical Evaluation

Across three GRAFO scenarios, standard continual-learning methods perform inconsistently, while FROG generally improves performance and reduces forgetting. Additional analyses find that random graph features hinder learning and that task order affects both FROG and standard methods.

6 Empirical Evaluation

  • The evaluation uses InforMARL with L2, EWC, MAS, and fine-tuning baselines, across six-task TS, five-task CS, and four-task GFS sequences.It measures Average Final Performance, Average Forgetting, and Average Plasticity using the percentage of solved episodes.Source: §6 · p. 7

6.1 Main Results

  • FROG consistently improves performance and is less prone to forgetting across TS, CS, and GFS, with EWC on TS the stated exception for forgetting.Standard methods show mixed results; EWC has better average AFP than MAS and L2 but lower AP, and the EWC-on-TS exception is attributed to plasticity loss.Source: §6.1 · p. 8, Figure 3 · p. 8

6.2 Additional Analyses

  • On TS, random frozen graph features hinder learning, with models struggling to learn the hardest tasks and achieving low Average Plasticity.Table 2 aggregates medians, averages, and standard deviations for CL methods paired with FROG or FROG (RND).Source: §6.2 · p. 8, Table 2 · p. 8
  • FROG’s first-task representations make task order consequential: TS (inc) causes plasticity loss with MAS and L2, while TS (dec) favors FROG.Standard CL methods also achieve lower average AFP and AP on TS (inc).Source: §6.2 · p. 9, Figure 4 · p. 9

7 Related Work

The paper situates its work at the intersection of graph-based MARL and continual learning, noting that it is the first to consider continual graph-based MARL settings.

7 Related Work

  • Graph-based MARL uses graph structure to characterize task structure, and in some settings that structure conditions local agent dynamics.The paper distinguishes this from communication MARL, which uses graphs to improve coordination without necessarily making them determinants of environment dynamics.Source: §7 · p. 9
  • Communication MARL commonly uses GNN message passing to support coordination, while CRL seeks adaptation to new tasks without losing performance on earlier ones.Replay and parameter regularization are cited as approaches to prevent forgetting.Source: §7 · p. 9
  • The authors identify their work as the first investigation of continual graph-based MARL, building on prior uses of frozen representations in continual learning.The cited prior work includes frozen modules or representations used to mitigate forgetting.Source: §7 · p. 9

8 Conclusion and Future Work

The paper introduces CGMARL for sequences of MARL tasks with different structures and proposes FROG, validated with standard continual-learning methods on GRAFO. It points to theoretical analysis, off-policy algorithms, and further benchmarks as future directions.

8 Conclusion and Future Work

  • CGMARL formalizes sequences of MARL tasks characterized by different structures, and the paper identifies real-world applications induced by different task-graph distributions.The supplied conclusion passage ends before specifying those applications.Source: §8 · pp. 9–10
  • FROG uses frozen graph representations to mitigate forgetting, and experiments on GRAFO validate its effectiveness when combined with standard continual-learning methods.GRAFO is presented as a novel CGMARL benchmark.Source: §8 · p. 10
  • Future work includes analyzing standard methods’ failure modes, testing experience-based continual learning with off-policy MARL, and developing benchmarks for other applications.Suggested applications include power distribution management and traffic light control.Source: §8 · p. 10

A Theoretical Analysis of Forgetting

The appendix frames forgetting as a performance drop on an earlier task after later-task training and separates representation-learning and action-prediction contributions. It also reviews related graph-based MARL, continual learning, and frozen-representation work.

A Theoretical Analysis of Forgetting

  • For tasks k and h with k > h, the analysis defines forgetting on earlier task h after training on task k as a performance difference.The supplied passage introduces the definition but does not include its displayed expression.Source: A Theoretical Analysis of Forgetting · p. 17
  • Under a Lipschitz-continuous objective, the analysis decomposes the performance drop into representation-learning and action-prediction terms.The decomposition follows from substituting a decoupled policy and applying the triangle inequality.Source: A Theoretical Analysis of Forgetting · p. 17

B Extended Related Work

  • Graph-based MARL can make environment dynamics depend on the underlying graph, unlike communication MARL, which focuses on coordination and need not use graphs to determine dynamics.The related-work discussion describes graph-dependent local dynamics and graph-based decision-making policies.Source: B Extended Related Work · p. 17
  • Continual MARL extends continual learning to cooperative multi-agent systems, where replay, parameter regularization, or parameter isolation are among established approaches.The discussion cites EWC and MAS as parameter-regularization examples.Source: B Extended Related Work · p. 17
  • Prior work uses frozen representations in learning, but the authors identify frozen GNN encoders for graph-based CMARL as uninvestigated.Examples include randomized graph representations in continual learning and frozen modules or representations in continual reinforcement learning.Source: B Extended Related Work · pp. 17–18

C Graph-based Formation (GRAFO) Benchmark

GRAFO is a graph-based navigation benchmark for continual MARL, with tasks specified by graphs and target configurations. Its task sequences vary graph topology, connectivity, or features.

C Graph-based Formation (GRAFO) Benchmark

  • GRAFO provides graph-based navigation tasks in which agents navigate to target configurations resembling input graphs, which can be generated arbitrarily.This makes it suitable for constructing CGMARL task sequences.Source: C Graph-based Formation (GRAFO)… · p. 18

C.1 Single-Task Description

  • A single task is specified by adjacency matrix A, target shifts g, optionally structurally equivalent nodes K, and optional static node or edge features.A influences environment dynamics and may define communication structure; g is measured relative to a known landmark.Source: §C.1 · p. 18
  • Agents must infer unknown targets from graph structure; rewards depend on distance to targets, with equivalent agents assigned targets to minimize total distance.The reference agent’s target coincides with the known landmark, but the team does not know which agent is the reference.Source: §C.1 · p. 18, Figure 5 · p. 19

C.2 Continual GRAFO

  • A continual GRAFO sequence is formed by varying task specifications across graphs, allowing procedural generation of potentially infinite sequences.The paper uses this construction to instantiate different CGMARL settings.Source: §C.2 · p. 19
  • Topology Switch sequences change nodes or edges between tasks; the example changes from four agents to three.Source: §C.2 · p. 19
  • Connectivity Switch sequences vary edges while keeping the node set fixed; the example uses six agents in both tasks.Source: §C.2 · p. 19
  • Graph Features Switch keeps topology fixed and distinguishes tasks through graph features that encode target positions, such as node shifts or edge distances.The example uses four agents with fixed edges.Source: §C.2 · p. 20

D.1 Single-Task Performance in GRAFO

The experiments examine single-task graph-policy performance and how regularization, encoder initialization, and task identities affect continual learning in GRAFO.

D.1 Single-Task Performance in GRAFO

  • Graph-based InforMARL solves each TS single task, whereas the actor variant without a GNN fails to do so.Table 3 reports solved percentages as median ± standard deviation over five seeds.Source: §D.1 · p. 20, Table 3 · p. 20

D.2 Impact of Regularization Coefficients

  • λμ = 10^6 gives the best reported EWC (M) tradeoff, below the graph encoder’s λψ = 10^10; very low λμ risks forgetting, while strong λμ reduces plasticity.The sensitivity analysis evaluates configurations across the full TS sequence, unlike the more restrictive first-task tuning used in the main experiments; FROG requires tuning only λμ.Source: §D.2 · pp. 20–21, Figure 6 · p. 21

D.3 Comparison with Untrained FROG

  • Across CL methods, FROG (RND), with its encoder frozen at initialization, has lower plasticity and worse average final performance than FROG.The authors suggest random graph features may lack the expressiveness needed for hard GRAFO tasks.Source: Figure 7 · p. 21, §D.3 · p. 21

D.4 Impact of Task Identities

  • Removing one-hot task identities does not alter the overall trend between standard CL methods and FROG, and within-method differences mostly fall within the uncertainty range.Source: §D.4 · p. 22, Figure 8 · p. 22

E Experimental Setting

The experimental setting uses InforMARL on graph-defined GRAFO tasks and sequences, evaluates continual-learning metrics, and selects method hyperparameters using early tasks.

E.1 InforMARL

  • InforMARL is a multi-agent actor-critic based on multi-agent PPO, using a GNN to exchange messages across connected agents and a graph-level critic.Agents use a relative frame of reference for other agents’ positions and landmarks.Source: §E.1 · p. 22

E.2 CGMARL Sequences

  • GRAFO task diagrams identify the reference agent, unknown target shifts, and structurally equivalent agents whose target positions can be exchanged.Source: §E.2 · pp. 22–23, Figure 9 · p. 23
  • The experiments use topology-, connectivity-, and feature-switch sequences; the CS sequence has six agents, while GFS fixes topology and varies features across four-agent tasks.The TS sequence includes increasing and decreasing agent-count orders; GFS encodes target-distance information as edge features.Source: §E.2 · p. 23

E.3 Evaluation Metrics

  • Evaluation uses solved-episode percentages to calculate AFP after the final task, AF on past tasks after the final task, and AP immediately after learning a task.Source: §E.3 · p. 24

E.4.1 Software and Hardware

  • The benchmark builds on the JAX InforMARL implementation, and experiments ran on HPC clusters at USI and TU Darmstadt.Source: §E.4.1 · p. 24

E.4.2 Hyperparameters

  • The policy’s single-task hyperparameters were held fixed across CL methods, while each CL method was tuned using three seeds on the first two TS tasks.Configurations were selected by average final performance; the table reports the experiment hyperparameters and shared online EWC/MAS settings.Source: §E.4.2 · p. 24, Table 4 · p. 25
Loading 2610.10302v1…