A Theory of Multi-Agent Generative Flow Networks

Conference: NeurIPS 2025 arXiv: 2509.20408 Code: None Area: Reinforcement Learning Keywords: GFlowNet, multi-agent, flow matching, CTDE, cooperative decision-making

TL;DR

This paper proposes a theoretical framework for Multi-Agent Generative Flow Networks (MA-GFlowNets) and establishes a "local-global principle" — the joint flow function can be decomposed into a product of individual agents' local flows. Four algorithms are designed (CFN/IFN/JFN/CJFN), among which JFN and CJFN realize Centralized Training with Decentralized Execution (CTDE). The proposed methods outperform RL and MCMC baselines on Hyper-Grid and StarCraft environments.

Background & Motivation

Background: GFlowNet is a generative model that learns stochastic policies via flow matching losses, sampling objects with probabilities proportional to their rewards. Unlike RL, which pursues a single maximum-reward policy, GFlowNet maintains diversity. However, existing GFlowNet theory and algorithms are limited to single-agent settings.

Limitations of Prior Work: (a) Existing GFlowNets cannot support multi-agent systems — multi-agent settings require a joint action space whose complexity grows exponentially with the number of agents. (b) Multi-agent RL (MARL) enables cooperative decision-making but tends to collapse to a single optimal policy, precluding diverse sampling. (c) Existing distributed GFlowNets (e.g., Meta-GFlowNet) require all agents to share the same observations and goals, making them inapplicable to partially observable multi-agent problems.

Key Challenge: Centralized training (CFN) is accurate but suffers from exponential joint action space complexity \(O(|A|^N)\); independent training (IFN) is efficient but faces non-stationarity due to spurious local rewards (each agent's local reward is influenced by other agents' actions), leading to mode collapse.

Goal - How to establish a theoretical framework for multi-agent GFlowNets? - How to design GFlowNet algorithms that realize CTDE (Centralized Training with Decentralized Execution)?

Key Insight: Drawing an analogy to value decomposition methods in MARL (VDN, QMIX), the paper decomposes the global flow function into a product of local flows and establishes a theoretical connection between global and local flow matching constraints via the "local-global principle."

Core Idea: The flow of a global GFlowNet can be decomposed into the product of local GFlowNet flows for each agent, such that training local models under global flow matching constraints is both theoretically sound and enables CTDE.

Method

Overall Architecture

MA-GFlowNet is a tuple \(((F^{(i)})_{i \in I}, F)\), consisting of local GFlowNets \(F^{(i)}\) for each agent and a global GFlowNet \(F\). Some GFlowNets may be "virtual" (not explicitly instantiated). Four algorithms arise depending on which components are instantiated and which are virtual.

Key Designs

1. CFN (Centralized Flow Network)

   • Function: Treats the multi-agent problem as a single-agent GFlowNet trained over the joint action space with flow matching.
   • Advantage: Accurate; existing GFlowNet theory applies directly.
   • Disadvantage: Action space grows as \(O(|A|^N)\); requires full global observation sharing.

2. IFN (Independent Flow Network)

   • Function: Each agent independently trains its own local GFlowNet.
   • Advantage: Efficient; linear complexity.
   • Disadvantage: Local rewards are intractable (\(R^{(i)}(o^{(i)}) = \mathbb{E}[R(s)|o^{(i)}]\) is uncomputable); using stochastic reward surrogates introduces non-stationarity and mode collapse.

3. JFN (Joint Flow Network) — Core Contribution

   • Function: Realizes CTDE based on the local-global principle.
   • Mechanism (Theorem 2): If the local GFlowNet flows satisfy the product decomposition \(F_{\text{out}}^* = \prod_i F_{\text{out}}^{(i),*}\) and \(F_{\text{in}} = \prod_i F_{\text{in}}^{(i)}\), then the virtual global GFlowNet constructed from local flows satisfies the flow matching constraints, with global reward \(R = \prod_i \hat{R}^{(i)}\).
   • Training: Each agent samples trajectories using its local policy \(\pi^{(i)}(o_t^{(i)} \to a_t^{(i)})\), and all local models are trained with the global flow matching loss \(\mathcal{L}_{\text{FM}}^{\text{stable}}(F^{\theta, \text{joint}})\).
   • Design Motivation: Combines the accuracy of CFN with the efficiency of IFN — action complexity is linear (agents act independently) while rewards are global (no spurious rewards).

4. CJFN (Conditioned Joint Flow Network)

   • Function: Addresses the limitation of JFN, which can only exactly sample rewards of product form.
   • Mechanism: Introduces a shared latent state \(\omega \in \Omega\) as a "cooperative strategy," analogous to augmented flows in Normalizing Flows. At the beginning of each episode, \(\omega\) is sampled and all agents condition their decisions on it. The augmented local transition kernel \(T^{(i)}(\cdot; \omega)\) enables more flexible coupling and can theoretically make the virtual global transition equal to the true transition.
   • Design Motivation: Overcomes the product-reward restriction of JFN by enabling more general reward functions through conditioning.

Loss & Training

• Flow matching loss: \(\mathcal{L}_{\text{FM}}^{\text{stable}}(F^\theta) = \mathbb{E}_{s \sim \nu_{\text{state}}} g(F_{\text{in}}^\theta(s) - F_{\text{out}}^\theta(s))\), where \(g(x) = x^2\) or \(g(x) = \log(1 + \alpha |x|^\beta)\).
• Global inflow and outflow for JFN/CJFN are computed as products of local flows — a key advantage.
• A replay buffer is used to store trajectories.

Key Experimental Results

Main Results: Hyper-Grid (L1 Error↓, Mode Found↑)

Method	Small-Scale L1 Error	Large-Scale L1 Error	Mode Found
MCMC	High	High	Moderate
Multi-Agent SAC	High	High	Low
MAPPO	Moderate	Moderate	Moderate
CFN	Lowest	Degrades	Highest (small scale)
CJFN	Low	Lowest	Highest (large scale)

Ablation Study: CFN vs. JFN as Scale Increases

Scale	CFN Performance	JFN/CJFN Performance
Small (small joint action space)	Optimal	Good
Large (large joint action space)	Degrades (complexity explosion)	Remains good

StarCraft 3m

Method	Win Rate	Diversity
MAPPO, etc.	Comparable	Low
MA-GFlowNet	Comparable	Higher (varied number of surviving units)

Key Findings

• CFN is accurate at small scale but does not scale: CFN achieves the best accuracy when the joint action space is small, but degrades rapidly as the number of agents or action space size increases.
• IFN suffers from non-stationarity: Independent training yields poor L1 error and mode discovery, empirically validating the theoretical analysis of spurious-reward-induced problems.
• JFN/CJFN achieve both accuracy and scalability: The local-global principle keeps complexity linear while leveraging global rewards to avoid non-stationarity.
• GFlowNet's diversity advantage over RL is clear: In StarCraft, RL methods converge to a single optimal strategy, whereas GFlowNet samples diverse strategies across different reward levels.

Highlights & Insights

• The local-global principle (Theorem 2) is the core theoretical contribution: it proves that global flows can be decomposed into a product of local flows, and that global flow matching constraints imply local ones (on the essential domain). This is analogous to value decomposition in MARL (additive decomposition in VDN), but a multiplicative decomposition is more natural in the GFlowNet framework.
• The augmented strategy space of CJFN is an elegant design: a shared latent variable enables agents to "synchronize" their cooperative strategies at the beginning of each episode, breaking the product-reward restriction. The idea is inspired by augmented flows in Normalizing Flows.
• The unique value of MA-GFlowNet: For cooperative tasks requiring diverse sampling (e.g., diverse molecular design, diverse strategy search), MA-GFlowNet is more suitable than MARL.

Limitations & Future Work

• Product-reward assumption (JFN): JFN requires the global reward to be a product of local rewards, which is overly restrictive for many practical settings (e.g., team rewards in cooperative tasks are typically non-decomposable).
• Incomplete theoretical guarantees for CJFN: Using \(\mathbb{E}_\omega \mathcal{L}_{\text{FM}}\) rather than \(\mathcal{L}_{\text{FM}}(\mathbb{E}_\omega F)\) as the training loss does not theoretically guarantee that the product-reward restriction is lifted.
• Approximation of virtual local transition kernel \(T^{(i)}\): The virtual global transition \(\tilde{T}\) constructed by JFN may not equal the true transition \(T\) when transitions are highly coupled, which can affect convergence.
• Limited experimental scale: Hyper-Grid is a synthetic environment, and StarCraft 3m is a small map; large-scale multi-agent experiments are absent.
• Continuous action spaces: The framework is validated only in discrete action spaces; extension to continuous action spaces requires further development of measure-theoretic GFlowNets.

Related Work & Insights

• vs. VDN/QMIX (MARL value decomposition): VDN decomposes value functions additively; QMIX uses monotonic mixing; JFN in MA-GFlowNet uses multiplicative flow decomposition — different mathematical structures but analogous motivation (CTDE).
• vs. MAPPO/SAC (multi-agent RL): RL methods maximize expected reward and tend toward mode collapse; GFlowNet samples proportionally to rewards, maintaining diversity.
• vs. Meta-GFlowNet: Meta-GFlowNet requires all agents to share the same observations and goals; MA-GFlowNet supports partial observability and heterogeneous agents.
• vs. single-agent GFlowNet: This paper presents the first rigorous multi-agent GFlowNet theoretical framework, extending measure-theoretic GFlowNet methodology to the multi-agent setting.

Rating

• Novelty: ⭐⭐⭐⭐⭐ First theoretical framework for multi-agent GFlowNets; the local-global principle and CTDE algorithm design are original.
• Experimental Thoroughness: ⭐⭐⭐ Hyper-Grid + StarCraft 3m; limited scale; real-world application scenarios are absent.
• Writing Quality: ⭐⭐⭐⭐ Theoretical derivations are rigorous, but the notation system is heavy and readability is moderate.
• Value: ⭐⭐⭐⭐ Opens a new direction for diverse sampling in multi-agent settings, but experimental validation requires more real-world scenarios.

Related Papers

• [NeurIPS 2025] Multi-Agent Collaboration via Evolving Orchestration
• [NeurIPS 2025] PARCO: Parallel AutoRegressive Models for Multi-Agent Combinatorial Optimization
• [NeurIPS 2025] Sequential Multi-Agent Dynamic Algorithm Configuration
• [NeurIPS 2025] Learning Interestingness in Automated Mathematical Theory Formation
• [NeurIPS 2025] Extending NGU to Multi-Agent RL: A Preliminary Study