acceptodds
Under review as a conference paper at ICLR 2027

Continual Graph Multi-Agent Reinforcement Learning

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.

Primary area:
reinforcement learning
Keywords:
continual reinforcement learning, graph-based multi-agent reinforcement learning

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_yBNdOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces Continual Graph Multi-Agent Reinforcement Learning (CGMARL), a framework for cooperative MARL where agents sequentially encounter tasks characterized by different graph structures. The authors formalize three types of structural changes—Topology Switch, Connectivity Switch, and Graph Features Switch—and introduce Graph-based Formation, a benchmark for evaluating continual adaptation and catastrophic forgetting under these changes.

To address structural forgetting, the authors propose Frozen Graph Encoder (FROG), which freezes the GNN-based representation module after learning the first task while allowing the policy head to adapt using existing continual-learning techniques. Experiments with InforMARL and several regularization-based methods demonstrate that FROG generally improves average performance and mitigates forgetting across the proposed task sequences.

Critical strengths
  1. The paper identifies an interesting limitation of existing continual MARL formulations: task changes can involve not only reward functions or agent populations but also underlying interaction structures that influence environment dynamics. The proposed CGMARL formulation and its three structural-switch settings provide a systematic way to investigate this problem. I particularly appreciate the introduction of GRAFO, which enables controlled experiments with changing graph structures and agent populations. This is arguably the strongest contribution because it provides a foundation for future research beyond the specific algorithm proposed in this paper.

  2. The manuscript is well organized, and the motivation, framework, benchmark, and method are generally easy to follow. The experiments cover three CGMARL scenarios, multiple continual-learning approaches, and ten independent seeds. The authors also examine task-order sensitivity and compare trained versus randomly initialized frozen graph encoders. These analyses provide encouraging evidence that separating structural representation learning from continual policy adaptation can be beneficial.

Critical weaknesses

1. Insufficient motivation and differentiation from adaptive graph-based MARL.

The paper argues that existing CMARL methods fail to leverage task-specific structural information. However, recent graph-based MARL approaches, such as Group-Aware Coordination Graph (IJCAI 2024) and Bayesian Ego-graph Inference (NeurIPS 2025) (already cited in the paper), already learn dynamic, context-dependent interaction structures. Although graph inference and continual learning address different challenges, the manuscript does not clearly explain why existing adaptive graph-learning approaches are insufficient for handling structural task changes or how CGMARL complements them. This distinction is important for establishing the motivation and novelty of the proposed framework.

2. Limited algorithmic novelty and insufficient justification for freezing graph representations.

FROG essentially freezes a GNN encoder after the first task and applies existing continual-learning methods to the action-prediction module. While reasonable, freezing pretrained representations is already a well-established strategy for mitigating catastrophic forgetting. More importantly, preserving encoder parameters does not guarantee that the resulting representations remain informative for subsequent tasks with potentially different graph structures. The experiments also do not clearly isolate whether the improvements come from preserving structural information specifically or simply from reducing trainable parameters. Comparisons with alternative freezing strategies or adaptive graph encoders under the same continual-learning protocol would strengthen the contribution.

3. Theoretical justification and empirical generality need clarification.

The forgetting decomposition in Eq. (5) and Appendix A relies on a Lipschitz-continuity assumption, but the transition from Eq. (7) to Eq. (8) appears to omit the constant KπK_\pi. The norm and assumptions needed to bound performance differences through policy-output distances also require clarification. Moreover, freezing the encoder trivially eliminates its parameter-induced changes but does not guarantee reduced overall forgetting.

Experimentally, the evaluation is limited to GRAFO with a single MARL backbone (InforMARL) and primarily assumes known task identities with separate task heads. Although the results are encouraging, broader validation would help establish whether the findings generalize beyond this particular benchmark and learning protocol.

Questions for authors
  1. Existing graph-based MARL methods can dynamically infer interaction structures. Why are such approaches insufficient for continual learning across structurally changing tasks? What specific advantage does FROG provide by freezing graph representations rather than adapting them with continual-learning regularization?

  2. Could the authors clarify the assumptions behind the forgetting bound in Eq. (5) and Appendix A? In particular, why is the Lipschitz constant $ K_\pi$ omitted in the final inequality, and under what conditions does the policy-output distance bound performance forgetting?

  3. How much of FROG's improvement comes specifically from preserving structural representations rather than simply freezing part of the network? Are comparisons with alternative freezing strategies or capacity-matched partially frozen policies available?

  4. How strongly does FROG depend on known task identities and separate task heads? Could the authors clarify the results of the task-identity ablation and discuss whether the method remains effective when structural changes occur without explicit task labels?

3 comments

Thank you for the review; we are pleased that you found our paper interesting and sound. Please find our answers below.

Question 1 (limitations of existing methods)

We agree that approaches designed to infer the interaction structure, such as GACG (IJCAI 2024) or BayesG (NeurIPS 2025), can effectively adapt to graph changes in a CGMARL sequence. However, as stated in lines 279-285, those methods are not designed to retain past structural knowledge, making the corresponding policies prone to forgetting past tasks when learning new ones. Indeed, GNNs learn local (node-level) rules specific to the current graph (task). In a sequential setting, these rules are overwritten when learning new tasks, making them ineffective on past ones. We empirically show this behavior in a simple 2-task sequence in Table 1.

In contrast, by leveraging a frozen graph encoder, FROG mitigates forgetting by preserving the previously learned graph representations: when re-evaluating past topologies, the representations extracted by the graph encoder do not change, preventing representation drift that may be caused by sequentially training on different tasks.

Question 2 (theoretical analysis)

Eq. 5 holds under the assumption of a Lipschitz continuous objective, and removing the Lipschitz constant is a typo; thank you for the comment. We will fix it.

Eq. 5 is not meant to bound the performance forgetting, but rather to show that forgetting caused by the graph representation learning module (first term on the right-hand side of Eq. 5) can be eliminated by freezing the graph encoder. This analysis motivates adopting FROG to prevent performance loss on past tasks (graphs) caused by the graph encoder (see also our answer to Question 1). However, this does not fully eliminate forgetting: as stated in lines 330-334, forgetting can still emerge due to changes in the action-prediction module (second term on the right-hand side of Eq. 5). Future work may build on this analysis to account for such changes and obtain a performance bound, but this is not the purpose of Eq. 5 and is beyond the scope of this paper.

Question 3 (FROG's improvement and comparisons)

Preserving structural information using graph representations is necessary to prevent performance degradation on past tasks. This claim is supported by the comparison in Sec. 6.2 (lines 414-423), where we compared FROG against a completely untrained graph encoder. This variant performs poorly compared to FROG.

To further investigate this aspect, we conducted an additional experiment on the TS sequence using a variant of FROG in which the graph encoder is frozen after learning the second task, instead of after the first one.

The results reported at https://anonymous.4open.science/r/cgmarl-code/rebuttal-imgs/analysis_freeze_from_second_task.pdf show that freezing the graph encoder after learning the second task deteriorates performance on the first task, as it does not preserve the previously learned graph representations. To make this explicit, we report here the performance achieved by both variants on the first task after learning the last one:

Variant / CL MethodL2EWC (M)EWC (O)MAS (M)MAS (O)
FROG0.47±0.340.47 \pm 0.340.82±0.160.82 \pm 0.160.80±0.190.80 \pm 0.190.87±0.170.87 \pm 0.170.72±0.250.72 \pm 0.25
Freeze after 2nd task0.26±0.250.26\pm 0.250.22±0.190.22 \pm 0.190.21±0.160.21 \pm 0.160.33±0.190.33 \pm 0.190.16±0.140.16 \pm 0.14

These results indicate FROG's improvements depend not merely on reducing the number of trainable parameters, but also on when the graph encoder is frozen. Thank you for the comment; we will include this new experiment in the main text.

Question 4 (task identities)

The experiment in App. D.4 shows that both FROG and the standard CL methods do not depend on known task identities. In particular, removing them does not compromise performance, with average results falling within the uncertainty of the corresponding variant with task identities (Figure 10). On the contrary, preliminary runs showed that both FROG and standard CL methods require separate task heads to prevent catastrophic forgetting on past tasks. These results are consistent with CMARL literature (please refer to the “Ablation Study” in Figure 5 of [1]).

[1] Tomilin, Tristan, et al. "MEAL: a benchmark for continual multi-agent reinforcement learning." arXiv preprint arXiv:2506.14990 (2025).

Thank you for the detailed rebuttal and additional experiments. I appreciate the authors' efforts to address my concerns regarding the motivation, theoretical analysis, methodological novelty, and task-identity assumptions.

The response provides a clearer distinction between adaptive graph-based MARL and continual structural knowledge retention. I also appreciate the clarification that freezing the graph encoder prevents encoder-induced representation drift rather than guaranteeing the elimination of overall catastrophic forgetting.

The additional freezing-strategy experiment is particularly useful. It provides stronger empirical evidence that preserving the graph encoder after the first task can significantly improve knowledge retention compared with freezing it after subsequent tasks.

I still have some reservations about the algorithmic novelty of FROG, since freezing pretrained representations is an established continual-learning strategy. Furthermore, the current experiments do not fully isolate the advantages of freezing graph representations specifically, and the framework continues to rely on separate task-specific heads.

I have two remaining questions:

  1. Task identities and separate task heads: The response indicates that removing task-identity information does not significantly affect performance. However, Appendix D.4 appears to remove only the one-hot task-identity features while retaining separate task-specific heads. Could the authors clarify how the appropriate head is selected at inference time when task identity is unavailable?

  2. Methodological differentiation and related work: The additional freezing experiment demonstrates that the freezing stage affects knowledge retention, but does not fully isolate the advantage of freezing graph representations over other network components. Could the authors clarify whether any existing results support this distinction? I also encourage incorporating the discussion of adaptive graph-based MARL from the rebuttal into the Related Work, particularly Group-Aware Coordination Graph for Multi-Agent Reinforcement Learning (IJCAI 2024) [1], to better distinguish dynamic coordination-graph inference from continual structural knowledge preservation.

Nevertheless, I recognize that the proposed CGMARL formulation and GRAFO benchmark represent meaningful contributions beyond the specific FROG algorithm. The manuscript is well organized, the experimental evaluation is relatively comprehensive, and the rebuttal has improved my confidence in the methodological motivation and empirical findings.

I am therefore raising my rating from 2 to 3 (Weak Accept), primarily in recognition of the problem formulation, benchmark contribution, and additional experimental evidence, while retaining some reservations about the novelty and generality of FROG.

Reference

[1] W. Duan, J. Lu, and J. Xuan, "Group-Aware Coordination Graph for Multi-Agent Reinforcement Learning," Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI), pp. 3926–3934, 2024. DOI: 10.24963/ijcai.2024/434.

Thank you for the positive feedback and for the additional questions. We are glad that our rebuttal addressed most of your concerns and that you find our contributions interesting. Please find the answers to the follow-up questions below.

Question 1 (task identities and separate task heads):

Could the authors clarify how the appropriate head is selected at inference time when task identity is unavailable?

We do not consider the setting where task IDs are completely unknown at evaluation time. In the ablation in App. D.4, we simply removed them as features. Both the baselines and FROG use a separate task head (lines 350-353). This is known as the task incremental setting [1], and several works on continual RL/MARL follow this paradigm [2,3,4]. We agree that, in future work, an analysis in other CL settings would be interesting, but this is beyond the scope of this paper. Thank you for the comment, we will clarify this aspect in the revised version.

We hope this clarifies your doubt; please let us know if this is not the case.

Question 2 (methodological differentiation and related work):

The additional freezing experiment demonstrates that the freezing stage affects knowledge retention, but does not fully isolate the advantage of freezing graph representations over other network components. Could the authors clarify whether any existing results support this distinction? I also encourage incorporating the discussion of adaptive graph-based MARL from the rebuttal into the Related Work

Thank you for the comment. The main idea of freezing the graph encoder only (rather than also components in the action-prediction module) is to allow flexibility in learning new tasks. To assess this, we ran an additional experiment to validate our approach against an alternative strategy that freezes a different component of the policy. Specifically, we compare EWC (M) with/without FROG against a variant of FROG in which we freeze the action-prediction module (refer to Eq. 4) while we allow for updates in the graph encoder. Results at https://anonymous.4open.science/r/cgmarl-code/rebuttal-imgs/analysis_frozen_APM.pdf show that this variant (EWC (M) + Frozen APM) loses plasticity (lower AP), failing to learn as effectively as FROG on new tasks (AF is lower because there is “less” to forget, see also lines 405-408). This indicates that alternative freezing strategies can hinder learning, further supporting our proposed design. Note that the EWC (M) + Frozen APM variant performs similarly to EWC (M), suggesting that freezing the action-prediction module does not provide advantages over the base approach.

As for the graph-based MARL methods, we will add the discussion to the Related Work. Thank you for the suggestion.

We are available for any further clarification, if needed.

References

[1] Wang, Liyuan, et al. "A comprehensive survey of continual learning: Theory, method and application." IEEE transactions on pattern analysis and machine intelligence 46.8 (2024): 5362-5383.

[2] Wołczyk, Maciej, et al. "Continual world: A robotic benchmark for continual reinforcement learning." Advances in Neural Information Processing Systems 34 (2021): 28496-28510.

[3] Tomilin, Tristan, et al. "Coom: A game benchmark for continual reinforcement learning." Advances in Neural Information Processing Systems 36 (2023): 67794-67832.

[4] Tomilin, Tristan, et al. "MEAL: a benchmark for continual multi-agent reinforcement learning." arXiv preprint arXiv:2506.14990 (2025).

Reviewer_w2cCOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces Continual Graph Multi-Agent Reinforcement Learning (CGMARL), a framework for cooperative multi-agent reinforcement learning in which tasks differ in their underlying graph structures. Each graph represents a task-specific configuration that determines the environment's transition dynamics and/or reward function, and may also change the number of agents. The authors distinguish three settings: Topology Switch (TS), Connectivity Switch (CS), and Graph Features Switch (GFS).

To study this problem, the paper introduces Graph-based Formation (GRAFO), a graph-based navigation benchmark in which agents must reach target configurations determined by a partially observed task graph. The authors demonstrate that graph-based policies trained on individual tasks can fail to transfer across different formations and can suffer severe forgetting when tasks are learned sequentially.

The paper then proposes Frozen Graph Encoder (FROG), which separates a graph-based policy into a GNN encoder and an action prediction module. After training on the first task, the encoder is frozen, preserving its parameters throughout subsequent tasks, while the action prediction module continues learning. FROG can be combined with conventional continual learning methods, including L2 regularization, Elastic Weight Consolidation (EWC), and Memory Aware Synapses (MAS).

Experiments on GRAFO cover TS, CS, and GFS task sequences, using Average Final Performance (AFP), Average Forgetting (AF), and Average Plasticity (AP) as evaluation metrics. The results suggest that FROG generally improves the performance of its corresponding continual learning baselines and often reduces forgetting. Additional experiments examine untrained encoders, task order, regularization coefficients, and task-identity conditioning. The paper's main contribution is the formalization of continual structure-based MARL, together with a benchmark and a simple architectural intervention for mitigating representation-level forgetting.

Critical strengths
  1. A useful problem formulation for continual graph-based MARL. The paper explicitly models task changes through attributed graphs that determine environment dynamics and/or rewards. The distinction between Topology Switch, Connectivity Switch, and Graph Features Switch provides a clear taxonomy of structural changes that can occur in cooperative multi-agent systems. This is a useful conceptual contribution because it distinguishes changes in the underlying problem structure from graphs used merely for agent communication.

  2. A benchmark that makes structural information essential. GRAFO requires agents to infer target configurations from a task graph rather than directly observing every agent's target. As described on page 5 and in Appendix C, this design makes the graph relevant to solving the task, rather than merely an optional communication mechanism. The benchmark also supports sequences with different agent counts and graph configurations, making it useful for studying structural transfer and forgetting.

  3. A simple and interpretable intervention. FROG separates graph representation learning from action prediction and freezes the encoder after learning the first task. This directly prevents subsequent training from modifying the encoder parameters, isolating one potential source of representation drift. The method can also be combined with existing continual learning algorithms, making it easy to implement and evaluate without introducing an entirely new learning objective.

  4. A reasonably comprehensive evaluation within the proposed benchmark. The experiments cover three task-sequence families and compare L2, EWC, and MAS, including online and multi-task variants where applicable. Figure 3 on page 8 reports distributions over 10 independent seeds. The authors also examine task-order sensitivity and compare FROG with a randomly initialized frozen encoder. In Table 2 on page 8, the reported TS-sequence aggregate for FROG is AFP = 0.69 ± 0.13 and AP = 0.99 ± 0.02, compared with AFP = 0.38 ± 0.037 and AP = 0.64 ± 0.03 for FROG (RND). These results support the importance of learning useful representations before freezing the encoder.

  5. An appropriately decomposed analysis of forgetting. The paper distinguishes changes caused by the graph representation module from changes caused by the action prediction module. This decomposition motivates FROG and clarifies why freezing one component alone cannot eliminate every form of continual learning failure. The authors also acknowledge the limitations of their approach and identify additional benchmarks and off-policy MARL algorithms as future directions.

Critical weaknesses
  1. The theoretical guarantee is narrower than the overall continual learning objective. The paper argues that freezing the graph encoder eliminates forgetting in the graph representation learning module caused by structural changes. This is reasonable at the parameter level: subsequent training cannot modify a frozen encoder. However, the overall policy also contains a trainable action prediction module, whose parameters can change and degrade performance on previous tasks. Equation (5) decomposes the performance difference into representation-learning and action-prediction terms, but the practical implication of the first term being eliminated depends on the assumptions and interpretation of this bound. The paper should more clearly distinguish a guarantee against encoder parameter drift from a guarantee of preserved task performance. The latter does not follow from freezing alone and still depends on the continual learning method used for the action module.

  2. FROG depends on the first task and may sacrifice plasticity. The encoder is trained on the first task and then frozen, so the learned representation must be sufficiently expressive for all subsequent graph structures. The authors investigate task-order effects in Section 6.2 and Appendix D. The TS-incremental experiment shows that when the first task involves only three agents, FROG paired with L2 or MAS can exhibit reduced plasticity on later, more demanding tasks. This is an important limitation rather than a minor implementation detail: a continual learner generally cannot assume that its first task will provide representations adequate for future tasks. The paper would benefit from stronger alternatives to first-task-dependent freezing, such as periodically evaluated representation expansion or a principled mechanism for deciding when new structural features are needed.

  3. The benchmark does not establish broad external validity. GRAFO is a useful controlled benchmark, but the main evaluation focuses on graph-based formation and navigation. The TS sequence contains six tasks with three to seven agents, CS contains five tasks with six agents, and GFS contains four tasks with four agents. These experiments establish a proof of concept for the proposed setting, but they do not establish that FROG will behave similarly in substantially larger or more heterogeneous multi-agent systems, or in tasks with different dynamics and reward structures. The paper discusses applications such as power grids and traffic networks, but these applications are motivations rather than empirical validation. Additional benchmarks would be necessary to substantiate the method's broader applicability.

  4. The task-incremental setting simplifies task identification. The main experiments use separate task heads and known task identities. This is consistent with the selected continual learning protocol, but it assumes that the learner already knows which task it is solving. In many realistic settings, task transitions may be gradual, the current graph may be only partially observed, or the task identity may not be supplied explicitly. Although Appendix D.4 investigates conditioning on task identity, the main results do not establish robustness to unknown task boundaries or task identity. The scope of the conclusions should therefore be limited to task-incremental CGMARL unless further evidence is provided.

  5. The benefits over conventional continual learning methods are not uniformly established. The authors report that FROG generally improves the corresponding continual learning baselines, but the results vary by method and scenario. In the TS sequence, for example, the paper explicitly notes an exception involving EWC and its forgetting metric, attributable to reduced plasticity. The sensitivity analysis also shows that regularization strength has a substantial effect on the trade-off between adaptation and retention. These observations make it difficult to attribute the improvements solely to the frozen encoder without a more systematic analysis of the interaction between encoder freezing and regularization. More direct component-level comparisons and uncertainty estimates for paired differences would strengthen the empirical argument.

  6. The novelty relative to frozen representations in continual learning requires sharper positioning. Freezing a feature extractor while adapting a prediction head is a simple and established design pattern in machine learning. The paper's contribution is its application to structural forgetting in graph-based MARL and its accompanying formalization and benchmark. However, the empirical method itself is relatively lightweight. The paper should more clearly identify which aspects of FROG are specific to CGMARL and demonstrate when its advantages exceed those of a generic frozen-backbone approach. The comparison against an untrained frozen encoder is useful, but it does not fully establish the advantage of the proposed design over alternative approaches that preserve or adapt graph representations without permanently freezing the encoder.

Questions for authors
  1. Scope of the theoretical guarantee: In Equation (5), freezing the graph encoder eliminates the representation-learning term associated with changes in the encoder. Under what assumptions does this decomposition provide a meaningful bound on actual task-performance degradation? Can the authors distinguish formally between preventing encoder parameter drift and guaranteeing retention of expected return on previous tasks?

  2. Sensitivity to the first task: Since FROG freezes the encoder after the first task, how sensitive is its performance to the choice of that task? Could the authors evaluate several substantially different first-task configurations or compare against a strategy that updates or expands the representation when later tasks cannot be learned effectively?

  3. Generalization beyond GRAFO: Can the authors evaluate FROG on an additional graph-based MARL benchmark with different dynamics and reward functions, such as traffic signal control or networked control? Such experiments would help establish whether the observed improvements extend beyond formation and navigation.

  4. Unknown task identities: How does FROG behave when task identities are not provided, or when task transitions are not explicitly marked? Can the method infer when a new graph structure requires adaptation while retaining previously acquired behaviors?

  5. Attribution of improvements: Can the authors provide paired comparisons with uncertainty estimates between each continual learning baseline and its FROG counterpart? In particular, how much of the improvement is attributable to freezing the encoder rather than differences in the regularization applied to the action prediction module?

  6. Representation capacity and plasticity: Is there a measurable relationship between the complexity of the first task and the ability of the frozen encoder to support subsequent tasks? Can the authors characterize when freezing is beneficial and when it prevents the learner from acquiring representations needed for future graph structures?

  7. Comparison with alternative frozen-backbone methods: How does FROG compare with generic frozen-feature approaches or methods that selectively freeze, expand, or adapt the graph encoder? A comparison against such alternatives would help establish the specific methodological contribution of FROG beyond applying a standard freezing strategy to a GNN-based policy?

3 comments

Thank you for the review. We are glad that you found our paper relevant and sound, and we appreciate the questions and comments on FROG. We would also like to emphasize that our contributions go beyond simply introducing FROG, as the core novelty lies in the proposed CGMARL framework, together with a novel benchmark (GRAFO) and an effective method for this setting. Please find our answers below.

Question 1 (scope of the theoretical guarantee)

Eq. 5 does not directly bound performance degradation, but it serves a different purpose. Specifically, Eq. 5 shows that, with a decoupled policy as in Eq. 4, freezing the graph encoder removes forgetting associated with the graph representation learning module (lines 324 - 330). This motivates the design of FROG, which preserves graph representations across different graphs (tasks) over time, thereby mitigating forgetting caused by different task structures. Nevertheless, this alone does not guarantee performance retention, since the action-prediction module continues to adapt to new tasks. Forgetting in this part (second term on the right-hand side of Eq. 5) can be mitigated by pairing the action-prediction module in FROG with existing CL methods (lines 330-334).

The inequality in Eq. 5 holds under the common assumption of a Lipschitz-continuous objective. Although future work may extend this analysis to provide a performance-degradation bound, obtaining this bound was not the goal of the analysis in Eq. 5 and is not something we aim to study in this paper.

Question 2 (sensitivity to the first task)

We did a new experiment to assess the impact of different first tasks on FROG. To do so, we considered EWC (M) + FROG on the TS Sequence and tested how FROG performs when changing the first task of the sequence. The results at https://anonymous.4open.science/r/cgmarl-code/rebuttal-imgs/analysis_first_task.pdf show that, although the first task can have an impact on FROG, it is generally robust. Specifically, when the first task exhibits sufficiently rich structures, the action-prediction module can better adapt to subsequent graphs. Conversely, graphs with fewer agents or simpler structures may limit the representational capacity of the frozen graph encoder, causing lower AP values. We will add this new experiment to the main text.

Finally, designing a strategy that dynamically adapts the frozen graph encoder to future tasks is challenging, as it requires developing mechanisms tailored to CGMARL to expand the representations. This would be a novel contribution by itself, and we therefore leave this direction for future work.

Question 3 (generalization beyond GRAFO)

We agree that it would be valuable to evaluate FROG on more CGMARL benchmarks. However, this is the first work formalizing CGMARL problems and, consequently, GRAFO is the first benchmark tailored to this class of continual learning problems. No other equivalent CGMARL benchmarks exist as of today. Designing and validating additional benchmarks for this setting is an important direction for future work (as stated in lines 537-539), but requires substantial effort and falls outside the focus of this paper (which already has several contributions). Moreover, note that the GRAFO benchmark already allows for testing three different CGMARL scenarios, which already provide plenty of evidence on the effectiveness of the proposed design/framework.

Question 4 (unknown task identities)

We analyzed the impact of task identities in App. D.4. On average, removing task identities does not compromise performance, both for FROG and standard CL methods. This is also consistent with results achieved in CMARL literature [1]. At the current stage, FROG has no explicit mechanisms to account for changes in the graph structure, but future work can build upon FROG to further develop this point.

[1] Tomilin, Tristan, et al. "MEAL: a benchmark for continual multi-agent reinforcement learning." arXiv preprint arXiv:2506.14990 (2025).

Question 5 (attribution of improvements)

The action-prediction module of FROG is equivalent to the corresponding standard CL counterparts. For example, consider L2: the comparison in Fig. 3 shows the difference between the continual learning baseline (L2) and the same method with a frozen graph encoder (L2 + FROG). Therefore, for each CL method (i.e., L2, EWC, or MAS), performance improvements of FROG come entirely from the proposed freezing mechanism, as the empirical and architectural setups are the same. Please let us know if this is not clear.

Question 6 (representation capacity and plasticity)

FROG relies on the graph encoder frozen after learning the first task, which inevitably impacts subsequent tasks. The “Task Order” analysis conducted in Sec. 6.2 makes the tradeoff between representation capacity and complexity of the first task explicit. In the decremental sequence, where the first task has the highest number of agents and a sufficiently rich structure, FROG maintains its plasticity (high AP) and can effectively learn subsequent tasks. In contrast, in the incremental setting, the learned graph encoder provides less effective representations, resulting in lower AP values. The new experiment presented in the answer to Question 2 further supports this observation.

Finally, we agree that establishing a measurable relationship between the first task complexity and effectiveness of the representations, but that we argue cannot possibly be entirely resolved in the scope of this paper (which, again, is not only proposing a practical method, but an entirely new framework).

Thank you for the comment; we will improve the presentation on these points.

Question 7 (comparison with alternative frozen-backbone methods)

We provide a comparison against the fully randomized variant (FROG (RND)) in Sec. 6.2, which suggests that using a completely frozen backbone may be ineffective in CGMARL scenarios. In addition, we conducted a new experiment where we freeze the graph encoder after learning the second task, rather than the first one (https://anonymous.4open.science/r/cgmarl-code/rebuttal-imgs/analysis_freeze_from_second_task.pdf). This design choice strongly deteriorates performance on the first task. This can be seen from the task resolution percentage on the first task after learning the last one:

Variant / CL MethodL2EWC (M)EWC (O)MAS (M)MAS (O)
FROG0.47±0.340.47 \pm 0.340.82±0.160.82 \pm 0.160.80±0.190.80 \pm 0.190.87±0.170.87 \pm 0.170.72±0.250.72 \pm 0.25
Freeze after 2nd task0.26±0.250.26\pm 0.250.22±0.190.22 \pm 0.190.21±0.160.21 \pm 0.160.33±0.190.33 \pm 0.190.16±0.140.16 \pm 0.14

This alternative freezing strategy suggests that correctly defining when the graph encoder is frozen is crucial for achieving good performance.

We agree that comparing FROG with other freezing/randomization mechanisms could be interesting. However, adapting these mechanisms to CGMARL is non-trivial (see also our answer to Question 2) and would, in itself, constitute a novel contribution. Given the multiple contributions of our paper, we do not explore this further here to keep the scope contained. Instead, following the CMARL literature [1], we included traditional regularization CL methods in our evaluation, alongside different variants of FROG.

[1] Tomilin, Tristan, et al. "MEAL: a benchmark for continual multi-agent reinforcement learning." arXiv preprint arXiv:2506.14990 (2025).

Dear reviewer,

We hope that our answers have clarified your concerns.

As the discussion period closes, we wanted to follow up on our rebuttal to check whether there are any issues left preventing you from considering a higher score.

Thank you again for reviewing our paper.

Reviewer_it5LOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper introduces Continual Graph Multi-Agent Reinforcement Learning (CGMARL), a framework for continual MARL in which sequential tasks are characterized by attributed graphs. Each graph determines the number of agents and influences the environment's transition dynamics and/or rewards.

The authors introduce GRAFO, a graph-based formation benchmark, and propose Frozen Graph Encoder (FROG), which freezes the graph encoder after learning the first task to mitigate catastrophic forgetting. Experiments on GRAFO demonstrate that combining FROG with existing continual learning methods improves performance across several task sequences.

Critical strengths

1.The paper investigates an interesting problem involving continual learning and structural changes in multi-agent systems.

  1. The proposed GRAFO benchmark supports different types of graph-structured task sequences, providing a useful testbed for studying catastrophic forgetting.
Critical weaknesses
  1. Motivation of the proposed CGMARL setting is not convincing. The paper introduces three types of structural changes: Topology Switch (TS), Connectivity Switch (CS), and Graph Features Switch (GFS). The necessity of continual learning under these structural changes is not sufficiently established. The distinction between CGMARL and existing CMARL formulations remains unclear.

  2. FROG lacks of novelty. It is unclear what fundamentally distinguishes FROG from existing continual learning approaches or how it specifically exploits graph-structured knowledge.

  3. Theoretical justification is not convincing. Could you provide some empirical bound of the right side of the equation

  4. Experiment is not strong enough. Please check the below questions

Questions for authors

CONTINUAL GRAPH MARL

  1. You mention: “In our formulation, the graph represents the problem structure and determines the dynamics.” From my understanding, dynamics refers to p(st+1∣st,at)p(s_{t+1} \mid s_t, a_t). Could you give me some examples of how the graph influences the transition dynamics in a multi-agent setting?
  2. I think for graph-based MAS, you should first have an application that can be modeled as a graph with corresponding graph changes. For your three kinds of switches, do you have application scenarios to support that these switches are meaningful and realistic?
  3. Could you explain why continual learning is necessary in your Continual Graph MARL setting with three kinds of switches? How could continual learning benefit cooperative policy learning?

GRAFO

  1. I want to ask whether it is a static benchmark or an interactive RL environment where I can obtain the next state and reward given the current state and action.
  2. Why do you choose GNN-based policies as an example to show the failure to preserve structural information in CGMARL problems? Is this an important method in this setting?

FROG

  1. With Eq. 4, you learn a deterministic policy, if I understand correctly. How do you enable exploration during training?
  2. Please explain why Eq. 4 can mitigate forgetting in CGMARL.
  3. Eq. 5 is not convincing. Could you show that the right-hand side of Eq. 5 is a valid bound? Could you provide some empirical validation?
  4. How does FROG differ fundamentally from existing continual learning approaches?

EXPERIMENT

  1. Could you report the training curves?
  2. Which part of the method matters most for avoiding forgetting?
  3. Does task order matter in your setting?
  4. Can FROG handle graph-based MARL environments with more complex dynamics beyond the proposed GRAFO formation benchmark?
7 comments

Thank you for your review. We would like to point out that most of the questions you raised are already addressed in the paper and, in our view, clearly presented, as the other reviewers also acknowledged. Please find our answers below.

CONTINUAL GRAPH MARL

Question 1 (graph-based dynamics)

Environment dynamics refer to both the transition and reward functions (see, e.g., lines 21-22, 49-51, or 118-120). As reported in the main text (lines 47-50), there are several MARL scenarios in which the graph influences the dynamics, such as traffic-light control (lines 201-205), power grid management (lines 219-224), or composable robotic agents (lines 234-243). For example, in traffic-light control, the next observation and reward for a specific intersection (agent) depend only on incoming/outgoing vehicles from/to connected intersections (neighbours in the graph), making the dynamics graph-dependent (lines 124-127).

Finally, as we note in lines 136-145, graph-based tasks in CGMARL differ fundamentally from communication MARL, where, instead, graphs are used to exchange messages and improve coordination across agents, but do not influence the environment dynamics.

Question 2 (CGMARL examples)

For each of the three scenarios proposed, we have already reported an example of a corresponding real-world application in the main text. For the Topology Switch, we reported a traffic light control application (lines 201-205); for the Connectivity Switch, we considered power distribution management (lines 219-224); for the Graph Features Switch (GFS), we reported a composable robotic example, where we considered both node-level and edge-level feature changes (lines 234-243). Similar examples can be found across many applications; please let us know if these are not enough.

Question 3 (why CL is necessary)

Continual learning methods are necessary in CGMARL because task switches alter the corresponding graph-dependent dynamics, which, in turn, makes previously learned policies ineffective when directly applied to novel task structures. Despite that, learning previous tasks can facilitate adapting to new ones and improve sample efficiency. Finally, simply learning sequentially on new tasks without any regularization deteriorates performance on previous tasks (forgetting).

Sec. 5 focuses exactly on explaining and showing (also empirically, see, e.g., Table 1) how forgetting emerges in CGMARL. Is there anything specific you wish us to add on top of what we discuss in Sec. 5?

GRAFO

Question 1 (interactive environment)

As clearly explained in Sec. 4 and App. C, GRAFO is an “interactive” MARL environment where next states and rewards depend on the current state and actions, and trajectories are collected via exploration.

Question 2 (importance of GNNs)

GNN-based policies are arguably one of the most effective methods for tackling MARL problems in structured domains (see, e.g., [1, 2]), as they leverage structural information by relying on graph representations. This also holds in our GRAFO benchmark: as shown in App. D.1, a policy that does not rely on a GNN fails to consistently learn in any task. As for the use of such representations in continual MARL (CGMARL), this is the paper's core contribution, the relevance of which is discussed at length. In short: we show that a sequence of graphs is a natural way to represent a sequence of tasks, and we introduce (1) CGMARL, the framework for continually learning control policies in such a context, (2) FROG, a practical method to address challenges in CGMARL, and (3) GRAFO, a benchmark enabling further research on the topic.

[1] Duan, Wei, Jie Lu, and Junyu Xuan. "Bayesian ego-graph inference for networked multi-agent reinforcement learning." Advances in Neural Information Processing Systems 38 (2026): 73072-73105.

[2] Rashwan, Ahmed, et al. "Factored Value Functions for Graph-Based Multi-Agent Reinforcement Learning." arXiv preprint arXiv:2601.11401 (2026).

FROG

Question 1 (exploration)

In Eq. 4, we considered a deterministic policy to simplify the derivations, but as we write in lines 312-313, the analysis of Sec. 5.2 can be easily generalized to stochastic ones by considering an appropriate statistical distance metric (e.g., total variation). Indeed, in our experiments, we used a stochastic policy where actions are sampled at each step from a categorical distribution. This follows the standard practice of PPO-based policies, which is the underlying optimization algorithm of InforMARL (App. E.1).

Question 2 (Eq. 4)

There must be a misunderstanding here. Eq. 4 does not mitigate forgetting, and we never made such a claim. Eq. 4 just shows how a deterministic policy outputs actions at each step (the difference would be minimal for a stochastic policy). It decouples the part of the architecture that processes the input graph representation from the part that simply maps the extracted representations to actions. The result in Eq. 5 builds on this decoupling to show how both have an impact on forgetting.

Question 3 (Eq. 5)

Could you clarify which aspect of the result is “not convincing” and what kind of empirical validation do you have in mind?

For what concerns the theoretical aspects, the only assumption we make is that the objective is Lipschitz continuous (a standard assumption in many theoretical analyses in RL). We will make it more clear the revision of the paper. As for empirical validation, the design of FROG is based on this analysis, so the best validation we can think of is showing that FROG can mitigate forgetting. This is the focus of Section 6, which shows plenty of evidence, including sensitivity analyses and more. Please let us know if anything is not clear. Is there a specific reason for such a low score on soundness in your evaluation? Let us know if you see any errors in our derivations.

Question 4 (novelty of FROG)

FROG is the first continual MARL approach specifically tailored to sequences of MARL tasks represented as graphs. Moreover, it tackles the problem using frozen representations, which is again something that has not been explored in continual MARL. Is there a specific method that you believe is analogous to FROG to justify a low novelty score here?

EXPERIMENT

Question 1 (training curves)

The goal of continual learning is learning new tasks while retaining performance on previously observed ones (i.e., avoiding forgetting while preserving plasticity). The metrics we use in the paper (average final performance, forgetting, and plasticity) are designed to explicitly show these aspects (which are not captured by learning curves) and show that FROG is effective in a CL scenario. Nonetheless, we agree that looking at training curves is a useful sanity check, and we will include them in the Appendix (results can also be found at https://anonymous.4open.science/r/cgmarl-code/rebuttal-imgs/full_training_curves.pdf). The training curves confirm that FROG does not hinder the ability of the agents to learn new tasks compared to the baselines.

Question 2 (forgetting in FROG)

In our framework, each task is captured by an input graph structure. As such, avoiding forgetting requires accounting for a sequence of graphs rather than overfitting to the current one. By relying on a frozen encoder, FROG is constrained to keep fixed the representations associated with different graphs over time, thus mitigating forgetting.

Question 3 (task order)

Yes, task order matters in CGMARL for both standard CL methods and FROG, and we dedicated a full paragraph to this analysis (lines 423-468) by considering different task orderings for the TS sequence. This is consistent with CL literature, which showed that task ordering can have a substantial impact on performance [3].

Since FROG relies on freezing the graph encoder after learning the first task, we also conducted new experiments to further assess the impact of this initial task on FROG. We tested EWC (M) + FROG on the TS Sequence by changing the first task. Results at https://anonymous.4open.science/r/cgmarl-code/rebuttal-imgs/analysis_first_task.pdf suggest that FROG is generally robust to different initializations. We observe that it performs better when the first task has a richer graph structure, while smaller graphs may limit the model’s plasticity to learn subsequent tasks.

[3] Bell, Samuel J., and Neil D. Lawrence. "The effect of task ordering in continual learning." arXiv preprint (2022).

Question 4 (beyond GRAFO benchmark)

FROG is a general method and, in principle, can be applied to any CGMARL benchmark. Some modifications to adapt the graph encoder to a specific environment may be required (e.g., a deeper GNN), but these are orthogonal to FROG. We argue that GRAFO already exhibits complex dynamics, and this is supported by the widespread use of similar navigation environments as single-task problems for graph-based MARL.

Thank you for the detailed rebuttal and additional experiments. I appreciate the clarifications regarding the CGMARL formulation, the GRAFO benchmark, and the exploration mechanism. However, my main concerns remain unresolved.

  1. My main concern is the methodological novelty of FROG. From my understanding, FROG freezes the GNN encoder after learning the first task and applies existing continual learning methods to the action prediction module. Freezing representations is already a well-established technique in continual learning. It remains unclear what fundamentally distinguishes FROG from existing frozen-representation approaches. The authors state that "no existing approaches have investigated frozen GNN-based encoders for graph-based CMARL", which suggests that the novelty comes from the new setting rather than from the method itself.

  2. All experiments are conducted on the proposed GRAFO benchmark. Although the CGMARL formulation considers graph-dependent transition and reward functions, GRAFO retains the same transition function across tasks, with structural changes mainly affecting target configurations and rewards. Therefore, the effectiveness of FROG in more complex graph-based MARL environments remains unverified.

  3. The analysis in Eq. 5 primarily decomposes policy changes into two terms. Freezing the graph encoder eliminates the representation-change term, but does not necessarily guarantee small overall forgetting, since changes in the action prediction module remain uncontrolled by this argument.

Therefore, I maintain my original rating.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response

We thank the reviewers for their feedback. To support our rebuttal, we summarize the main points here and add a revised version of the manuscript (changes are marked in teal).

Robustness of FROG (Section 6.2, lines 468-477). Since FROG relies on freezing the graph after learning the first task, we tested FROG’s robustness to this initial task. To do so, we evaluated EWC (M) + FROG in four variants of the TS sequence where we used different first tasks. The results in Figure 5 show that FROG achieves relatively consistent performance across these variants, suggesting it is generally robust. In more detail, the first graph structure can influence adaptation to subsequent tasks: richer structures may facilitate learning new tasks, while graphs with fewer agents may limit its plasticity. Combined with the “Task Order” analysis in Section 6.2, this additional experiment further supports our proposed method.

Alternative freezing strategy (Section 6.2, lines 478-485). To validate the freezing mechanism of FROG, in addition to the comparison with FROG (RND) in Section 6.2, we compare it against a variant where, instead of freezing the graph encoder after learning the first task, we freeze it after the second one. As shown in Figure 6, this variant slightly deteriorates performance across all methods. Table 3 shows that this is caused by the performance loss on the first task: after learning the last one, this variant performs poorly on the first task compared to FROG. This analysis indicates that this performance loss comes specifically from preserving structural information on the first task, validating our design choice.

Meaning of Equation 5. The purpose of Eq. 5 is not to directly bound performance degradation. Instead, it serves to support FROG: it shows that, using a decoupled policy as in Eq. 4, we can eliminate forgetting associated with the graph representation learning module (first term on the right-hand side of Eq. 5). This alone does not guarantee performance retention, since the action-prediction module is updated to new tasks, causing forgetting (second term on the right-hand side of Eq. 5).

Full training curves (Appendix D.5, lines 1173-1177). In Figure 11, we reported the training curves for each CL method with and without FROG.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.