A Theory of Multi-Agent Generative Flow Networks

To begin with, we thank you for the time you took to write this detailed review.

Response to Question 1: First of all, we generalize the measure GFN framework to the multi-agent framework. In order to reflect the differences of measure GFN framework, we redescribe different algorithms in Li et.al 2023 to serve as the basis for subsequent theoretical analysis. Moreover, we provide the theoretical setting of Global-local principle which justifies the key contribution of the aformentionned work: joint flow based training. Our theory (a) justifies the algorithm with a local-global principle (b) describe shortcomings of this algorithm (c) provide an extension solving these shortcomings via conditionning.

Response to Question 2: Regarding cycles, we leverage non-acyclic losses defined by Brunswic et al [1]. This prior work provides theoretical account of the acyclic limitation of GFN and how to bypass it via so-called stable losses.

Response to Question 3: There are two main reasons for the large L1-error. The first is the calculation sampling. In the multi-agent setting, there are a large number of grids that need to be used to calculate the L1-error. For example, the two-agent scene has 4096 grids, but only 16 samples are sampled per round. When calculating the index, we sampled 20 rounds, so the sampling value is much smaller than the number of grids, which will lead to a large L1-error. When the number of sampling rounds is increased, the L1-error will be further reduced. When the number of rounds increases to 2000, the normalized L1-error indicator decreases to less than 1. But this will increase the additional calculation overhead. The second reason is the magnitude of the value. Different from the standard empirical L1 error, we used normalized L1-error, i.e., $\mathbb{E}[|p(x)-\pi(x)|] \times N$, where $p(x)$ is the density of the target $x$, and $N$ is the number of target. As the number of final targets with rewards increases, the density of each target will become relatively smaller. In order to visualize the data, an additional scale of the number of grids is multiplied when calculating the L1-error. Moreover, the L1-error is on the order of $10^{-4}$. The corresponding comparison has been made on hypergrid. Since the multi-agent problem can also be regarded as a single agent, as the dimension and the number of agents increase, the original GFlowNets often have difficulty solving the above problems.

Response to Question 4: We use 3m scenario to verify the performance of the proposed algorithm. Although this task is the simplest, it is already more complex than the existing research work. In addition, this task is a typical winning-oriented task, which is slightly different from the goal of GFlowNets, but it can still illustrate the fitting ability of the proposed algorithm to the reward distribution.

[1] Leo Maxime Brunswic, Yinchuan Li, Yushun Xu, Shangling Jui, Lizhuang Ma. A Theory of Non-Acyclic Generative Flow Networks. AAAI 2024

Response to Comment 1: Thank you very much for your advice. One of our key contributions are two fold: (a) the generalization of the Measure GFN framework under multi-agent and (b) a theoretical account of the Joint Flow Loss introduced in Li et al [3].

In particular, our theoretical setting is not limited to DAG or even to continuous setting with absorbing policy such as in Lahlou et al. [2], cycles are allowed via the use of stable losses. The formulation in this manuscript can be regarded as the extension of Bunswic et al. [3], providing a unified description of the algorithms introduced in \cite{luo2024multi} in a more general setting. This allows us to provide a deeper description of the joint flow algorithm, its shortcoming and ways to solve them via conditional JFN.

Regarding notation choices, our definition of GFlowNets is equivalent to the original formulation as well as that of [2] and [3]. We do not provide all the details of the equivalency but the appendix of [3] provides an equivalency between edgeflow formulation and measure-policy formulation. We are merely decomposition further to better distinguish the parametrizable part of the GFlowNet FlowInit-starpolicy- from say the reward. We modified the paper to smoothen this transition and provide a justification for our choice: in the multi-agent setting, local rewards and local edgeflow of a local agent depend on other agents. The theoretical frameworks becomes burdened with too many implicits and hidden relations between local GFlowNets. Our formulation allows to explicitly separate what the local agent actually controls from what depends on global, possibly intractable, information. Moreover, in some settings the reward may not be accessible during inference. The stopping condition based on the reward is then replaced by the virtual reward ie $\hat R:=\mathrm{ReLU}(F_{\text{in}}-F{\text{out}})$. Restricting to the starpolicy ensures the GFlowNets using the true reward or the virtual reward are more easily comparable.

Response to Comment 2: GFN in the multiagent setting may be realized easily in two contexts: (a) if the reward is local, then the independent agent has their own independent policy given by a GFN. (b) if the reward is global with small communication costs (small observation encoding) and tractable global transitions.

Centralized algorithm is the formalization of (b) while independent is the formalizaiton of (a) in our framework. We argue in the paper that the condition for a reasonable centralized algorithm is restrictive and that, in general, the reward is global: the Starcraft 3m task is an example where each marine has its own policy, but the reward depends on the state of all three marines at the end of the sequence. The goal of the JFN is to train local agents with independent GFN policies to fit a global reward.

Response to Comment 3: The key property of the JFN is the decomposition of the action flow of an abstract global GFN as a product of local action flows. Such a property does allow detailed balance or Trajectory balance objectives. DB and FM loss are very closely related and mostly differ by the implementation choice of the backward policy (FM implements the backward policy by finding parents and computing the forward edge flow for each transition to the current state while DB implements an extra model, the backward policy, either fixed or trainable). Unfortunately, Brunswic et al [3] do not provide stable TB loss suitable for the non-acylic case such as the Starcraft 3m task.

[1] S. Luo, Y. Li, S. Liu, X. Zhang, Y. Shao, and C. Wu, “Multi-agent continuous control with generative flow networks,” Neural Networks,vol. 174, p. 106243, 2024. [2] S. Lahlou, T. Deleu, P. Lemos, D. Zhang, A. Volokhova, A. Hern´andez-Garcıa, L. N. Ezzine, Y. Bengio, and N. Malkin, “A theory of continuous generative flow networks,” in International Conference on Machine Learning. PMLR, 2023, pp. 18 269–18 300. [3] L. Brunswic, Y. Li, Y. Xu, Y. Feng, S. Jui, and L. Ma, “A theory of non-acyclic generative flow networks,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 38, no. 10, 2024, pp. 11 124–11 131

To begin with, we thank you for the time you took to write this detailed review.

General Response: We are sorry for the misunderstanding caused by the motations in this paper. In order to solve this problem, we first modified the multi-agent setting and GFlowNets from the perspective of measure theory, and explained the misunderstood notations in detail. Then we add a section in the appendix, called An Introduction for Notations, which illustrates the necessity of this definition, in the sense that it improves the generality of notations. The structure of Hyper-grid is given to explain the definition of symbols such as policy and flow function.

Notation Motivation: To begin with, our motivation to formalize the action space as a measurable bundle $\mathcal{A} := \{(s,a) | s \in \mathcal{S}, a\in \mathcal{A}_s\}\xrightarrow{S} \mathcal{S}$ is three fold:

1. The available actions from a state may depend on the state itself: on a grid, the actions available while on the boundary of the grid are certainly more limited than while in the middle. More generally, on a graph, actions are typically formalized by edges $s\xrightarrow{a} s'$ of the graph, the data of an edge contains both the origin $s$ and the destination $s'$. In other words, on graphs, actions are bundled with an origin state. It is thus natural to consider the actions as bundled with the origin state. When an agent is transiting from a state to another via an action, the state map tells where it comes from while the transition map tells where it is going.

2. We want our formalism to cover as many cases as possible in a unified way: Graphs, vector spaces with linear group actions or mixture of discrete and continuous state spaces. Measures and measurable spaces provide a nice formalism to capture the quantity of reward on a given set or a probability distribution.

3. We want a well-founded and possibly standardized mathematical formalism. In particular, the policy takes as input a state and returns a distribution of actions. the actions should correspond to the input state. To avoid having a cumbersome notion of policy as a family of distributions $\pi_s$ each on $\mathcal{A} _ s$, we prefer to consider the union of the state-dependent action spaces $\mathcal{A}:= \bigcup_{s\in \mathcal{S}} \mathcal{A}_s$ and define the policy as Markov kernel $\mathcal{S}\rightarrow \mathcal{A}$. However, we still need to satisfy the constraint that the distribution $\pi(s)$ is supported by $\mathcal A_s$. Bundles are usual mathemcatical objects formalizing such situations and constraints and are thus well suited for this purpose and the constraint is easily expressed as $S\circ \pi(s) = s, \forall s\in\mathcal{S}$. \end{enumerate}

Our synthetic formalism comes with a few drawbacks due to the level of abstraction:

1. The notation $\pi(s)$ differs from the more common notation $\pi(s, a)$ as the action already contains $s$ implicitly.

2. We need to use Radon-Nikodym derivative. At a given state, on a graph, a GFlowNets has a probability to stop $\mathbb P(STOP | s) = \frac{R(s)}{F _ {out}(s)}.$ On a continuous statespace with reference measure $\lambda$, the stop probability is $\mathbb P(STOP | s) = \frac{r(s)}{f_{\mathrm{out}}(s)}$ where $r(s)$ is the density of reward at $s$ and $f_{\mathrm{out}}(s)$ is the density of outflow at $s$. A natural measure-theoretic way of writing these equations as one is via Radon-Nikodym derivation: given two measures $\mu,\nu$; if $\mu(X)=0 \Rightarrow \nu(X)=0$ for any measurable $X\subset \mathcal{S}$ then $\mu$ is said to dominate $\nu$ and, by Radon-Nikodym Theorem, there exists a measurable function $\varphi \in L^1(\mu)$ such that $\nu(X)=\int_{x\in X}\varphi(x) d\nu(x)$ for all measurable $X\subset \mathcal{S}$. This $\varphi$ is the Radon-Nikodym derivative $\frac{d\nu}{d\mu}$. If one has a measure $\lambda$ dominating both $R$ and $F _ {out}$ and if $F _ {out}$ dominated $R$ then
   $\mathbb P(STOP | s) := \frac{dR}{dF _ {out}}(s) = \frac{dR}{d\lambda}(s) \times \left( \frac{dF _ {out}}{d\lambda}\right)^{-1}.$ When $\mathcal{S}$ is discrete, we choose $\lambda$ as the counting measure and we recover the graph formula above. When $\mathcal{S}$ is continuous, we choose $\lambda$ as the Lebesgue measure and we recover the second formula.